Prochlo: Strong Privacy for Analytics in the Crowd

By Andrea Bittau, Ú. Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnés, Bernhard Seefeld. 2017

293 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Sociology and Political Science, Privacy & Security, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Sociology and Political Science

In Privacy & Security

In Signal Processing

Citations in the corpus

Foundation Models and Fair Use (2023, background): “, Smart Compose, telemetry collection) (Miraglia, 2019; Erlingsson et al., 2014; Ding et al., 2017; Bittau et al., 2017; Cheu et al., 2019).”
Advances and Open Problems in Federated Learning (2019, methodology): “Distributed DP via secure shuffling Another distributed differential privacy model is the shuffling model, which was kicked off by the recently introduced Encode-Shuffle-Analyze (ESA) framework [67] (illustrated in Figure 3).”
The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation (2021, background): “FL with SecAgg and Distributed DP Despite the recent surge of interest in distributed DP, much of the work in this space focuses on the shuffled model of DP where a trusted third party (or a trusted execution environment) shuffles the noisy client updates before forwarding them to the server (Erling”
On Distributed Differential Privacy and Counting Distinct Elements (2020, methodology): “We brieﬂy review the shuﬄe model of DP [8, 24, 12].”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, methodology): “While the shuffled model was originally studied in the field of cryptography by Ishai et al. (2006) in their work on cryptography from anonymity, it was first suggested as a framework for privacy-preserving computations by Bittau et al. (2017) in their Encode-Shuffle-Analyze architecture.”
The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, methodology): “New models for di ﬀ erentially private computation have recently emerged to alleviate the (inevitable) low accuracy of the local model, of which we will discuss the shu ﬄ e model [38, 14, 19, 6, 5, 32] and the hybrid model [2].”
Federated Heavy Hitters Discovery with Differential Privacy (2019, methodology): “Another approach is to use the ESA architecture of [7] to ensure shuffling and anonymization of the votes.”
The Power of the Hybrid Model for Mean Estimation (2018, background): “However, it is well understood theoretically and empirically that utility outcomes are far worse in the LM than in the TCM [11, 16, 22, 27, 38].”
Distributed Differential Privacy via Shuffling (2018, methodology): “[20] and the discussion in [5]).”
Contamination Attacks and Mitigation in Multi-Party Machine Learning (2018, neutral): “Secure MPC can be enabled with cryptographic techniques [6, 11, 18, 29, 32], and systems based on trusted processors such as Intel SGX [3, 5, 33].”
Collecting and Analyzing Multidimensional Data with Local Differential Privacy (2019, background): “[6] evaluate real-world implementations of LDP.”
Separating Local & Shuffled Differential Privacy via Histograms (2019, neutral): “Because the local and central models lie at the extremes of trust, recent work has focused on the intermediate shuﬄed model [6, 8].”
Connecting Robust Shuffle Privacy and Pan-Privacy (2020, positive): “Building on the empirical work of Bittau, Erlingsson, Maniatis, Mironov, Raghunathan, Lie, Rudominer, Kode, Tinnes, and Seefeld [13], Cheu, Smith, Ullman, Zeber, and Zhilyaev [17] and Erlingsson, Feldman, Mironov, Raghunathan, Talwar, and Thakurta [22] independently and simultaneously introduced dif”
On the Round Complexity of the Shuffle Model (2020, background): “The shuffle collects messages from the participating parties and presents them to the analyzer in a random order, hence potentially disassociating between messages and their senders [11, 20, 15].”