# Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity

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

## Key facts

- Cited by 164 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2018.

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

- [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)
- [The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation](https://mlsanity.com/paper/2102.06387/) (2021)
- [Deep Learning with Label Differential Privacy](https://mlsanity.com/paper/2102.06062/) (2021)
- [Label Leakage and Protection in Two-party Split Learning](https://mlsanity.com/paper/2102.08504/) (2021)
- [Toward Training at ImageNet Scale with Differential Privacy](https://mlsanity.com/paper/2201.12328/) (2022)
- [Differentially Private Federated Learning on Heterogeneous Data](https://mlsanity.com/paper/2111.09278/) (2021)
- [DP-Forward: Fine-tuning and Inference on Language Models with Differential Privacy in Forward Pass](https://mlsanity.com/paper/2309.06746/) (2023)
- [Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning](https://mlsanity.com/paper/2211.06530/) (2022)
- [Composition of Differential Privacy & Privacy Amplification by Subsampling](https://mlsanity.com/paper/2210.00597/) (2022)
- [Large Scale Transfer Learning for Differentially Private Image Classification](https://mlsanity.com/paper/2205.02973/) (2022)
- [The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning](https://mlsanity.com/paper/2203.03761/) (2022)
- [Optimal Algorithms for Mean Estimation under Local Differential Privacy](https://mlsanity.com/paper/2205.02466/) (2022)
- [On Privacy and Personalization in Cross-Silo Federated Learning](https://mlsanity.com/paper/2206.07902/) (2022)
- [Federated Learning with Sparsified Model Perturbation: Improving Accuracy under Client-Level Differential Privacy](https://mlsanity.com/paper/2202.07178/) (2022)
- [Sparse Random Networks for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2209.15328/) (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)
- [An Efficient DP-SGD Mechanism for Large Scale NLP Models](https://mlsanity.com/paper/2107.14586/) (2021)
- [Shuffle Private Linear Contextual Bandits](https://mlsanity.com/paper/2202.05567/) (2022)
- [Label Leakage and Protection from Forward Embedding in Vertical Federated Learning](https://mlsanity.com/paper/2203.01451/) (2022)
- [Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging](https://mlsanity.com/paper/2206.05091/) (2022)
- [Stronger Privacy for Federated Collaborative Filtering with Implicit Feedback](https://mlsanity.com/paper/2105.03941/) (2021)
- [Private Non-Convex Federated Learning Without a Trusted Server](https://mlsanity.com/paper/2203.06735/) (2022)
- [Efficient Differentially Private Secure Aggregation for Federated Learning via Hardness of Learning with Errors](https://mlsanity.com/paper/2112.06872/) (2021)
- [Differentially Private Multi-Armed Bandits in the Shuffle Model](https://mlsanity.com/paper/2106.02900/) (2021)
- [DP-PCA: Statistically Optimal and Differentially Private PCA](https://mlsanity.com/paper/2205.13709/) (2022)
- [How Private are DP-SGD Implementations?](https://mlsanity.com/paper/2403.17673/) (2024)
- [Privacy Amplification for Federated Learning via User Sampling and Wireless Aggregation](https://mlsanity.com/paper/2103.01953/) (2021)

## Abstract (arXiv)

Sensitive statistics are often collected across sets of users, with repeated collection of reports done over time. For example, trends in users' private preferences or software usage may be monitored via such reports. We study the collection of such statistics in the local differential privacy (LDP) model, and describe an algorithm whose privacy cost is polylogarithmic in the number of changes to a user's value. More fundamentally---by building on anonymity of the users' reports---we also demonstrate how the privacy cost of our LDP algorithm can actually be much lower when viewed in the central model of differential privacy. We show, via a new and general privacy amplification technique, that any permutation-invariant algorithm satisfying varepsilon-local differential privacy will satisfy (O(varepsilon √log(1/δ)/n), δ)-central differential privacy. By this, we explain how the high noise and √n overhead of LDP protocols is a consequence of them being significantly more private in the central model. As a practical corollary, our results imply that several LDP-based industrial deployments may have much lower privacy cost than their advertised varepsilon would indicate---at least if reports are anonymized.