Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation

By Ú. Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, Abhradeep Thakurta. 2020

94 citations recorded by the source corpus.

Recently, a number of approaches and techniques have been introduced for reporting software statistics with strong privacy guarantees. These range from abstract algorithms to comprehensive systems with varying assumptions and built upon local differential privacy mechanisms and anonymity. Based on the Encode-Shuffle-Analyze (ESA) framework, notable results formally clarified large improvements in privacy guarantees without loss of utility by making reports anonymous. However, these results either comprise of systems with seemingly disparate mechanisms and attack models, or formal statements with little guidance to practitioners. Addressing this, we provide a formal treatment and offer prescriptive guidelines for privacy-preserving reporting with anonymity. We revisit the ESA framework with a simple, abstract model of attackers as well as assumptions covering it and other proposed systems of anonymity. In light of new formal privacy bounds, we examine the limitations of sketch-based encodings and ESA mechanisms such as data-dependent crowds. We also demonstrate how the ESA notion of fragmentation (reporting data aspects in separate, unlinkable messages) improves privacy/utility tradeoffs both in terms of local and central differential-privacy guarantees. Finally, to help practitioners understand the applicability and limitations of privacy-preserving reporting, we report on a large number of empirical experiments. We use real-world datasets with heavy-tailed or near-flat distributions, which pose the greatest difficulty for our techniques; in particular, we focus on data drawn from images that can be easily visualized in a way that highlights reconstruction errors. Showing the promise of the approach, and of independent interest, we also report on experiments using anonymous, privacy-preserving reporting to train high-accuracy deep neural networks on standard tasks---MNIST and CIFAR-10.

Subfields: Artificial Intelligence, Privacy & Security

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 Privacy & Security

Citations in the corpus

Breaking the Communication-Privacy-Accuracy Trilemma (2020, methodology): “For instance, when n = Ω (d), one can combine LDP with amplification techniques [14], [15], [16] to ensure stronger central differential privacy.”
Privacy Amplification via Random Check-Ins (2020, methodology): “For this reason, DP has been adopted by companies including Google [20, 10, 18], Apple [2], Microsoft [13], and LinkedIn [31], as well as the US Census Bureau [26].”
Private Aggregation from Fewer Anonymous Messages (2019, methodology): “Indeed, the power of the shuffled model has been illustrated by a number of recent works that have designed algorithms in this model for a wide range of problems such as privacy amplification, histograms, heavy hitters, and range queries [8, 12, 4, 13, 11].”
Federated Learning with Buffered Asynchronous Aggregation (2021, background): “LDP for high dimensional data has been criticized for poor privacy-utility trade-off [24, 25].”
On Large-Cohort Training for Federated Learning (2021, methodology): “For example, when using the distributed differential privacy model [6, 11, 16, 65] in federated learning, noise is typically added to the updates sent from the clients to the server [54].”
Lossless Compression of Efficient Private Local Randomizers (2021, methodology): “For deletion privacy the optimal error is achieved by a symmetric setting α0 = 1/(e + 1) and α1 = e/(e + 1) (Erlingsson et al., 2020).”
Improving utility and security of the shuffler-based differential privacy (2019, methodology): “We note that [29] operate on a novel removal LDP notion.”
Privacy-Preserving Bandits (2019, methodology): “As an extension to RAPPOR, the ESA architecture (Bittau et al., 2017; Erlingsson et al., 2020) adds two more layers to the LDP layer, called shufﬂer and analyzer, that are aimed to obscure the identity of the data owner through oblivious shufﬂing with trusted hardware.”
How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy (2023, methodology): “For this reason, it may be technically preferable to instead use a zero-out notion where datasets are adjacent if any one record is replaced with a special “zero” record (often exactly zero for numeric data) (Erlingsson et al., 2020; Kairouz et al., 2021c).”