PROCHLO: Strong Privacy for Analytics in the Crowd

The large-scale monitoring of computer users’ software activities has become commonplace, e.g., for application telemetry, error reporting, or demographic profiling. This paper describes a principled systems architecture—Encode, Shuffle, Analyze (ESA)—for performing such monitoring with high utility while also protecting user privacy. The ESA design, and its PROCHLO implementation, are informed by our practical experiences with an existing, large deployment of privacy-preserving software monitoring. With ESA, the privacy of monitored users’ data is guaranteed by its processing in a three-step pipeline. First, the data is encoded to control scope, granularity, and randomness. Second, the encoded data is collected in batches subject to a randomized threshold, and blindly shuffled, to break linkability and to ensure that individual data items get “lost in the crowd” of the batch. Third, the anonymous, shuffled data is analyzed by a specific analysis engine that further prevents statistical inference attacks on analysis results. ESA extends existing best-practice methods for sensitive data analytics, by using cryptography and statistical techniques to make explicit how data is elided and reduced in precision, how only common-enough, anonymous data is analyzed, and how this is done for only specific, permitted purposes. As a result, ESA remains compatible with the established workflows of traditional database analysis. Strong privacy guarantees, including differential privacy, can be established at each processing step to defend against malice or compromise at one or more of those steps. PROCHLO develops new techniques to harden those steps, including the Stash Shuffle, a novel scalable and efficient oblivious-shuffling algorithm based on Intel’s SGX, and new applications of cryptographic secret sharing and blinding. We describe ESA and PROCHLO, as well as experiments that validate their ability to balance utility and privacy.This paper is dedicated to the memory of Andrea Bittau, our colleague who wrote much of PROCHLO. We thank Kunal Talwar for his help analyzing Stash Shuffle’s security properties. We thank the anonymous reviewers for their detailed feedback, and Martín Abadi, Johannes Gehrke, Lea Kissner, Noé Lutz, and Nicolas Papernot for their valuable advice on earlier drafts. Our shepherd, Nickolai Zeldovich, provided invaluable help with this final paper version