Henry Corrigan-Gibbs: Lightweight Techniques for Private Heavy Hitters

Friday, May 14, 2021 - 1:00pm to 2:30pm
email dlehto@mit.edu for Zoom Link
Henry Corrigan-Gibbs, MIT

ABSTRACT:  This talk will present a new protocol 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 our protocol to figure out which homepages are popular, without learning any user’s homepage.

Our protocols use two data-collection servers and, in a protocol run, each client send sends only a single message to the servers. Our protocols protect client privacy against arbitrary misbehavior by one of the servers. Our approach avoids relatively expensive general-purpose multiparty-computation techniques. 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. Our implementation of the system can process hundreds of thousands of client submissions in under an hour.

This talk is based on joint work with Dan Boneh, Elette Boyle, Niv Gilboa, and Yuval Ishai.