Paper 2021/017

Lightweight Techniques for Private Heavy Hitters

Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai

Abstract

This paper presents Poplar, a new system for solving the private heavy-hitters problem. In this problem, there are many clients and a small set of data-collection servers. Each client holds a private bitstring. The servers want to recover the set of all popular strings, without learning anything else about any client’s string. A web-browser vendor, for instance, can use Poplar to figure out which homepages are popular, without learning any user’s homepage. We also consider the simpler private subset-histogram problem, in which the servers want to count how many clients hold strings in a particular set without revealing this set to the clients. Poplar uses two data-collection servers and, in a protocol run, each client send sends only a single message to the servers. Poplar protects client privacy against arbitrary misbehavior by one of the servers and our approach requires no public-key cryptography (except for secure channels), nor general-purpose multiparty computation. Instead, we rely on incremental distributed point functions, a new cryptographic tool that allows a client to succinctly secret-share the labels on the nodes of an exponentially large binary tree, provided that the tree has a single non-zero path. Along the way, we develop new general tools for providing malicious security in applications of distributed point functions. A limitation of Poplar is that it reveals to the servers slightly more information than the set of popular strings itself. We precisely define and quantify this leakage and explain how to ameliorate its effects. In an experimental evaluation with two servers on opposite sides of the U.S., the servers can find the 200 most popular strings among a set of 400,000 client-held 256-bit strings in 54 minutes. Our protocols are highly parallelizable. We estimate that with 20 physical machines per logical server, Poplar could compute heavy hitters over ten million clients in just over one hour of computation.

Note: This version fixes a typo in the introduction.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision.IEEE Symposium on Security and Privacy 2021
Keywords
privacyheavy hittersdistributed point function
Contact author(s)
dabo @ cs stanford edu
eboyle @ alum mit edu
henrycg @ csail mit edu
gilboan @ bgu ac il
yuvali @ cs technion ac il
History
2022-05-06: last of 4 revisions
2021-01-06: received
See all versions
Short URL
https://ia.cr/2021/017
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/017,
      author = {Dan Boneh and Elette Boyle and Henry Corrigan-Gibbs and Niv Gilboa and Yuval Ishai},
      title = {Lightweight Techniques for Private Heavy Hitters},
      howpublished = {Cryptology ePrint Archive, Paper 2021/017},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/017}},
      url = {https://eprint.iacr.org/2021/017}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.