Paper 2024/320
POPSTAR: Lightweight Threshold Reporting with Reduced Leakage
, University of WashingtonAbstract
This paper proposes POPSTAR, a new lightweight protocol for the private computation of heavy hitters, also known as a private threshold reporting system. In such a protocol, the users provide input measurements, and a report server learns which measurements appear more than a pre-specified threshold. POPSTAR follows the same architecture as STAR (Davidson et al, CCS 2022) by relying on a helper randomness server in addition to a main server computing the aggregate heavy hitter statistics. While STAR is extremely lightweight, it leaks a substantial amount of information, consisting of an entire histogram of the provided measurements (but only reveals the actual measurements that appear beyond the threshold). POPSTAR shows that this leakage can be reduced at a modest cost ($\sim$7$\times$ longer aggregation time). Our leakage is closer to that of Poplar (Boneh et al, S&P 2021), which relies however on distributed point functions and a different model which requires interactions of two non-colluding servers (with equal workloads) to compute the heavy hitters.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- private heavy hittersreduced leakage
- Contact author(s)
-
hanjul @ cs washington edu
senavot @ cs washington edu
tessaro @ cs washington edu - History
- 2024-02-26: approved
- 2024-02-24: received
- See all versions
- Short URL
- https://ia.cr/2024/320
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/320,
author = {Hanjun Li and Sela Navot and Stefano Tessaro},
title = {POPSTAR: Lightweight Threshold Reporting with Reduced Leakage},
howpublished = {Cryptology ePrint Archive, Paper 2024/320},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/320}},
url = {https://eprint.iacr.org/2024/320}
}
