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

arXiv: https://arxiv.org/abs/2001.03618 · HTML: https://mlsanity.com/paper/2001.03618/

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jan 2020.

## Built on by (most cited first, 30 of 39)

- [Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2106.06639/) (2021)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [On Large-Cohort Training for Federated Learning](https://mlsanity.com/paper/2106.07820/) (2021)
- [Optimal Algorithms for Mean Estimation under Local Differential Privacy](https://mlsanity.com/paper/2205.02466/) (2022)
- [Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses](https://mlsanity.com/paper/2106.09779/) (2021)
- [Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacy](https://mlsanity.com/paper/2208.04591/) (2022)
- [Lossless Compression of Efficient Private Local Randomizers](https://mlsanity.com/paper/2102.12099/) (2021)
- [Private Non-Convex Federated Learning Without a Trusted Server](https://mlsanity.com/paper/2203.06735/) (2022)
- [Differentially Private Multi-Armed Bandits in the Shuffle Model](https://mlsanity.com/paper/2106.02900/) (2021)
- [Privacy Amplification for Federated Learning via User Sampling and Wireless Aggregation](https://mlsanity.com/paper/2103.01953/) (2021)
- [Optimal Compression of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2111.00092/) (2021)
- [Shuffle Private Stochastic Convex Optimization](https://mlsanity.com/paper/2106.09805/) (2021)
- [Privacy Amplification via Shuffling for Linear Contextual Bandits](https://mlsanity.com/paper/2112.06008/) (2021)
- [On the Renyi Differential Privacy of the Shuffle Model](https://mlsanity.com/paper/2105.05180/) (2021)
- [SoK: Machine Learning Governance](https://mlsanity.com/paper/2109.10870/) (2021)
- [Towards Sparse Federated Analytics: Location Heatmaps under Distributed Differential Privacy with Secure Aggregation](https://mlsanity.com/paper/2111.02356/) (2021)
- [User-Level Private Learning via Correlated Sampling](https://mlsanity.com/paper/2110.11208/) (2021)
- [ULDP-FL: Federated Learning with Across Silo User-Level Differential Privacy](https://mlsanity.com/paper/2308.12210/) (2023)
- [Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed Learning](https://mlsanity.com/paper/2107.08763/) (2021)
- [To Shuffle or not to Shuffle: Auditing DP-SGD with Shuffling](https://mlsanity.com/paper/2411.10614/) (2024)
- [Differential Secrecy for Distributed Data and Applications to Robust Differentially Secure Vector Summation](https://mlsanity.com/paper/2202.10618/) (2022)
- [Group privacy for personalized federated learning](https://mlsanity.com/paper/2206.03396/) (2022)
- [OLIVE: Oblivious Federated Learning on Trusted Execution Environment against the risk of sparsification](https://mlsanity.com/paper/2202.07165/) (2022)
- [Shuffle Gaussian Mechanism for Differential Privacy](https://mlsanity.com/paper/2206.09569/) (2022)
- [Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimation](https://mlsanity.com/paper/2407.03289/) (2024)
- [CYCle: Choosing Your Collaborators Wisely to Enhance Collaborative Fairness in Decentralized Learning](https://mlsanity.com/paper/2501.12344/) (2025)
- [Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation](https://mlsanity.com/paper/2601.21636/) (2026)
- [Concurrent Shuffle Differential Privacy Under Continual Observation](https://mlsanity.com/paper/2301.12535/) (2023)
- [Multi-Message Shuffled Privacy in Federated Learning](https://mlsanity.com/paper/2302.11152/) (2023)

## Abstract (arXiv)

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.