Paper 2024/320

POPSTAR: Lightweight Threshold Reporting with Reduced Leakage

Hanjun Li, University of Washington
Sela Navot, University of Washington
Stefano Tessaro, University of Washington

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.

Available format(s)
Cryptographic protocols
Publication info
private heavy hittersreduced leakage
Contact author(s)
hanjul @ cs washington edu
senavot @ cs washington edu
tessaro @ cs washington edu
2024-02-26: approved
2024-02-24: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.