Lightweight Techniques for Private Heavy Hitters

Prof. Henry-Corrigan Gibbs MIT Tuesday, June 7, 2022 @ 3:00 pm Room BC 420 Hosted by: Prof. Bryan Ford

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.

Bio

Henry Corrigan-Gibbs (he/him) is an assistant professor at MIT. Henry builds computer systems that provide strong security and privacy properties using ideas from cryptography, computer security, and computer systems. Henry completed his PhD in the Applied Cryptography Group at Stanford, where he was advised by Dan Boneh. After that, he was a postdoc in Bryan Ford’s research group at EPFL.

For their research efforts, Henry and his collaborators have received an ACM Doctoral Dissertation Honorable Mention Award, three IACR Best Young Researcher Paper Awards (at Eurocrypt in 2020, the Theory of Cryptography Conference in 2019 and at Eurocrypt in 2018), the 2016 Caspar Bowden Award for Outstanding Research in Privacy Enhancing Technologies, and the 2015 IEEE Security and Privacy Distinguished Paper Award. Henry’s work has been cited by IETF and NIST, and his Prio system for privacy-preserving telemetry data collection is used today in the Firefox web browser, Apple’s iOS, and Google’s Android operating system.