# Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacy

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 33 references that are in the map.
- First posted on arXiv 9 Aug 2022.

## Builds on (most cited first, 23 of 23)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [The Privacy Blanket of the Shuffle Model](https://mlsanity.com/paper/1903.02837/) (2019)
- [Prochlo: Strong Privacy for Analytics in the Crowd](https://mlsanity.com/paper/1710.00901/) (2017)
- [Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation](https://mlsanity.com/paper/2001.03618/) (2020)
- [Privacy Amplification via Random Check-Ins](https://mlsanity.com/paper/2007.06605/) (2020)
- [Prio: Private, Robust, and Scalable Computation of Aggregate Statistics](https://mlsanity.com/paper/1703.06255/) (2017)
- [Private Summation in the Multi-Message Shuffle Model](https://mlsanity.com/paper/2002.00817/) (2020)
- [Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacy](https://mlsanity.com/paper/1702.00610/) (2017)
- [Scalable and Differentially Private Distributed Aggregation in the Shuffled Model](https://mlsanity.com/paper/1906.08320/) (2019)
- [Separating Local & Shuffled Differential Privacy via Histograms](https://mlsanity.com/paper/1911.06879/) (2019)
- [Private Aggregation from Fewer Anonymous Messages](https://mlsanity.com/paper/1909.11073/) (2019)
- [Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs](https://mlsanity.com/paper/2008.07180/) (2020)
- [The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation](https://mlsanity.com/paper/2009.08000/) (2020)
- [Tight Accounting in the Shuffle Model of Differential Privacy](https://mlsanity.com/paper/2106.00477/) (2021)

## Built on by (most cited first, 29 of 29)

- [Composition of Differential Privacy & Privacy Amplification by Subsampling](https://mlsanity.com/paper/2210.00597/) (2022)
- [One-shot Empirical Privacy Estimation for Federated Learning](https://mlsanity.com/paper/2302.03098/) (2023)
- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [How Private are DP-SGD Implementations?](https://mlsanity.com/paper/2403.17673/) (2024)
- [Individual Privacy Accounting with Gaussian Differential Privacy](https://mlsanity.com/paper/2209.15596/) (2022)
- [Scalable DP-SGD: Shuffling vs. Poisson Subsampling](https://mlsanity.com/paper/2411.04205/) (2024)
- [Privacy amplification by random allocation](https://mlsanity.com/paper/2502.08202/) (2025)
- [Unified Enhancement of Privacy Bounds for Mixture Mechanisms via f-Differential Privacy](https://mlsanity.com/paper/2310.19973/) (2023)
- [A Statistical Viewpoint on Differential Privacy: Hypothesis Testing, Representation and Blackwell's Theorem](https://mlsanity.com/paper/2409.09558/) (2024)
- [Leveraging Randomness in Model and Data Partitioning for Privacy Amplification](https://mlsanity.com/paper/2503.03043/) (2025)
- [To Shuffle or not to Shuffle: Auditing DP-SGD with Shuffling](https://mlsanity.com/paper/2411.10614/) (2024)
- [Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacy](https://mlsanity.com/paper/2405.02341/) (2024)
- [Fundamental Limitations of Favorable Privacy-Utility Guarantees for DP-SGD](https://mlsanity.com/paper/2601.10237/) (2026)
- [Learning from End User Data with Shuffled Differential Privacy over Kernel Densities](https://mlsanity.com/paper/2502.14087/) (2025)
- [Mitigating Privacy-Utility Trade-off in Decentralized Federated Learning via f-Differential Privacy](https://mlsanity.com/paper/2510.19934/) (2025)
- [Efficient privacy loss accounting for subsampling and random allocation](https://mlsanity.com/paper/2602.17284/) (2026)
- [Multi-Message Shuffled Privacy in Federated Learning](https://mlsanity.com/paper/2302.11152/) (2023)
- [Differentially Private Heavy Hitter Detection using Federated Analytics](https://mlsanity.com/paper/2307.11749/) (2023)
- [Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacy](https://mlsanity.com/paper/2407.04884/) (2024)
- [Training generative models from privatized data](https://mlsanity.com/paper/2306.09547/) (2023)
- [Beyond Statistical Estimation: Differentially Private Individual Computation via Shuffling](https://mlsanity.com/paper/2406.18145/) (2024)
- [Universally Harmonizing Differential Privacy Mechanisms for Federated Learning: Boosting Accuracy and Convergence](https://mlsanity.com/paper/2407.14710/) (2024)
- [How to Securely Shuffle? A survey about Secure Shufflers for privacy-preserving computations](https://mlsanity.com/paper/2507.01487/) (2025)
- [Practical and Private Hybrid ML Inference with Fully Homomorphic Encryption](https://mlsanity.com/paper/2509.01253/) (2025)
- [Federated Learning with Enhanced Privacy via Model Splitting and Random Client Participation](https://mlsanity.com/paper/2509.25906/) (2025)
- [Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency](https://mlsanity.com/paper/2510.07136/) (2025)
- [Jacobian-Guided Anisotropic Noise Reshaping for Enhancing Representation Utility under Local Differential Privacy](https://mlsanity.com/paper/2605.16812/) (2026)
- [Dithered Gaussian Mechanism for Randomness-Efficient Differential Privacy](https://mlsanity.com/paper/2607.06320/) (2026)
- [Robust Estimation of Sparse Numerical Vectors under Local Differential Privacy](https://mlsanity.com/paper/2607.27815/) (2026)

## Abstract (arXiv)

The shuffle model of differential privacy has gained significant interest as an intermediate trust model between the standard local and central models [EFMRTT19; CSUZZ19]. A key result in this model is that randomly shuffling locally randomized data amplifies differential privacy guarantees. Such amplification implies substantially stronger privacy guarantees for systems in which data is contributed anonymously [BEMMRLRKTS17]. In this work, we improve the state of the art privacy amplification by shuffling results both theoretically and numerically. Our first contribution is the first asymptotically optimal analysis of the R'enyi differential privacy parameters for the shuffled outputs of LDP randomizers. Our second contribution is a new analysis of privacy amplification by shuffling. This analysis improves on the techniques of [FMT20] and leads to tighter numerical bounds in all parameter settings.