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

Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, Abhradeep ThakurtaarXiv 2020 · OpenReview

Abstract

Recently, a number of approaches have been introduced for reporting software statistics with strong privacy guarantees, ranging from local differential privacy (LDP) to the Encode-Shuffle-Analyze (ESA) framework. While ESA formally clarifies how anonymity can amplify privacy without sacrificing utility, practitioners lack clear guidance on its deployment. This paper provides a formal treatment and prescriptive guidelines for privacy-preserving reporting with anonymity. We introduce techniques such as "attribute fragmentation" and "removal LDP" to improve privacy-utility tradeoffs. Through empirical evaluation on large-scale real-world datasets—including high-dimensional spatial data and deep learning benchmarks like MNIST and CIFAR-10—we demonstrate that the ESA framework can achieve high accuracy while maintaining robust local and central differential privacy guarantees.

Introduction: The Privacy Tug-of-War

In the field of differential privacy (DP), there is a persistent tension between utility and trust. Local DP (LDP), utilized by major technology firms, adds noise to data directly on a user's device. This model requires no trust in a central server, but the accumulated noise often destroys data utility, particularly for high-dimensional datasets. Conversely, Central DP adds noise at the server level, preserving high utility but requiring users to trust the server with their raw data.

Recent theoretical breakthroughs suggest that passing LDP reports through an anonymous shuffler—a middleman that strips metadata and mixes reports—can mathematically "amplify" privacy guarantees. This is the core of the ESA framework. However, bridging the gap between this theory and practical deployment requires addressing how data should be encoded and how complex, real-world distributions should be handled.

Methodology and Practical Primitives

We propose a simplified architecture for the ESA framework based on several key primitives designed to optimize the privacy-utility tradeoff:

  • Removal LDP: We shift the mathematical definition of LDP from "replacement" (swapping a user's data) to "removal" (the absence of a user's report). This subtle shift effectively doubles the local privacy guarantee without adding further noise.
  • Attribute Fragmentation: Instead of sending a single large, noisy report, a user's data is broken into individual attributes (e.g., bits of a one-hot vector). Each attribute is randomized and sent as a separate, unlinkable message to the shuffler.
  • Report Fragmentation with Privacy Backstops: To prevent leakage from intercepted messages, users can send multiple randomized fragments. This maintains a strict mathematical cap (a "backstop") on total privacy loss while allowing for higher utility per fragment.
  • LDP-SGD: We adapt Stochastic Gradient Descent to work within the ESA framework, enabling the training of deep learning models using shuffled, locally private gradients.

Empirical Evaluation

To prove these methods work on difficult, real-world distributions, we evaluated them against several datasets, including a "Heavy-Hitter" dataset of 200 million browser reports and high-dimensional image proxies for sensitive 2D location data.

Spatial Data Visualization

One of our primary benchmarks was a "Map" dataset consisting of 236 million points based on NYC smartphone location data. This dataset is naturally high-dimensional and serves as a perfect proxy for sensitive spatial data where visual reconstruction can easily highlight noise errors.

Figure 1: Visualization of the NYC location dataset used to evaluate the ESA framework's ability to reconstruct high-dimensional, sensitive spatial data.

Using attribute fragmentation and one-hot encoding, we successfully reconstructed this complex dataset with a strong central privacy guarantee ($\epsilon_c \le 1.0$) and a reasonable local privacy backstop ($\epsilon_\infty \approx 13$).

Machine Learning Performance

The ESA framework successfully trained deep neural networks with strong central privacy and a per-epoch local privacy of $\epsilon \approx 1.9$. The models achieved accuracies of 95% on MNIST, 78% on Fashion-MNIST, and 70% on CIFAR-10, approaching state-of-the-art performance for differentially private models while providing the added benefit of local DP guarantees.

Key Insights for Practitioners

Our research yielded several surprising insights for those deploying privacy-preserving systems:

  1. One-Hot Encoding vs. Sketching: While many LDP deployments use complex "sketching" (hashing data into smaller buckets) to save bandwidth, we found that sketching adds massive estimation error that ruins utility under anonymity. Simple one-hot encoding, combined with attribute fragmentation, yields vastly superior results.
  2. Fragmentation is the Secret Weapon: Breaking data into tiny, independently shuffled pieces allows for a higher local $\epsilon$ (less noise per piece) while relying on the shuffler to achieve a very strong central $\epsilon_c$.
  3. Obsolescence of Crowd IDs: Earlier ESA designs suggested grouping users by data-derived traits (Crowd IDs) before shuffling. We prove that under modern shuffling math, splitting the privacy budget to protect these IDs actually hurts overall performance; it is more effective to shuffle all reports together.

Limitations and Future Work

While the results are promising, some limitations remain. The poor performance of sketch-based LDP in our tests is partly due to a lack of precise mathematical bounds for how sketching interacts with shuffling. Additionally, the central DP accounting for machine learning experiments currently relies on standard advanced composition, which may be loose. Future work could tighten these bounds using Rényi Differential Privacy to further improve the utility of private ML models.

Summary updated

Abstract

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.
BibTeX
@misc{erlingsson2020encode,
  author = {Úlfar Erlingsson and Vitaly Feldman and Ilya Mironov and Ananth Raghunathan and Shuang Song and Kunal Talwar and Abhradeep Thakurta},
  title = {{Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation}},
  year = {2020},
  eprint = {2001.03618},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2001.03618},
}
Figure