mlsanityData to 7 Oct 2026

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

arXiv 2208.04591 ↗First posted 9 Aug 2022cs.CR cs.DS cs.LGcited by 29

Not on the map. Why?

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.

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

Builds on

23 of 33 references.

References · 23

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2017Renyi Differential Privacycited by 643
  3. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  4. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
  5. 2018Amplification by Shuffling: From Local to Central Differential Privacy via Anonymitycited by 163
  6. 2017Collecting Telemetry Data Privatelycited by 147
  7. 2016Concentrated Differential Privacycited by 139
  8. 2020The Discrete Gaussian for Differential Privacycited by 134
  9. 2018Distributed Differential Privacy via Shufflingcited by 115
  10. 2020Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shufflingcited by 96
  11. 2019The Privacy Blanket of the Shuffle Modelcited by 73
  12. 2017Prochlo: Strong Privacy for Analytics in the Crowdcited by 51
11 more
  1. 2020Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluationcited by 39
  2. 2020Privacy Amplification via Random Check-Inscited by 39
  3. 2017Prio: Private, Robust, and Scalable Computation of Aggregate Statisticscited by 35
  4. 2020Private Summation in the Multi-Message Shuffle Modelcited by 34
  5. 2017Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacycited by 28
  6. 2019Scalable and Differentially Private Distributed Aggregation in the Shuffled Modelcited by 20
  7. 2019Separating Local & Shuffled Differential Privacy via Histogramscited by 16
  8. 2019Private Aggregation from Fewer Anonymous Messagescited by 15
  9. 2020Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offscited by 15
  10. 2020The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimationcited by 7
  11. 2021Tight Accounting in the Shuffle Model of Differential Privacycited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 6; 2024: 8; 2025: 8; 2026: 5.

29 papers.

Sort:

  1. 2022Composition of Differential Privacy & Privacy Amplification by Subsamplingcited by 42
  2. 2023One-shot Empirical Privacy Estimation for Federated Learningcited by 35
  3. 2023Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimationcited by 22
  4. 2024How Private are DP-SGD Implementations?cited by 22
  5. 2022Individual Privacy Accounting with Gaussian Differential Privacycited by 19
  6. 2024Scalable DP-SGD: Shuffling vs. Poisson Subsamplingcited by 16
  7. 2023Unified Enhancement of Privacy Bounds for Mixture Mechanisms via f-Differential Privacycited by 13
  8. 2025Privacy amplification by random allocationcited by 13
  9. 2024A Statistical Viewpoint on Differential Privacy: Hypothesis Testing, Representation and Blackwell's Theoremcited by 8
  10. 2025Leveraging Randomness in Model and Data Partitioning for Privacy Amplificationcited by 7
  11. 2024To Shuffle or not to Shuffle: Auditing DP-SGD with Shufflingcited by 6
  12. 2024Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacycited by 4
17 more
  1. 2026Fundamental Limitations of Favorable Privacy-Utility Guarantees for DP-SGDcited by 4
  2. 2025Mitigating Privacy-Utility Trade-off in Decentralized Federated Learning via f-Differential Privacycited by 3
  3. 2026Efficient privacy loss accounting for subsampling and random allocationcited by 3
  4. 2023Multi-Message Shuffled Privacy in Federated Learningcited by 2
  5. 2023Differentially Private Heavy Hitter Detection using Federated Analyticscited by 2
  6. 2024Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacycited by 2
  7. 2023Training generative models from privatized datacited by 1
  8. 2024Beyond Statistical Estimation: Differentially Private Individual Computation via Shufflingcited by 1
  9. 2024Universally Harmonizing Differential Privacy Mechanisms for Federated Learning: Boosting Accuracy and Convergencecited by 1
  10. 2025Learning from End User Data with Shuffled Differential Privacy over Kernel Densitiescited by 1
  11. 2025How to Securely Shuffle? A survey about Secure Shufflers for privacy-preserving computationscited by 1
  12. 2025Practical and Private Hybrid ML Inference with Fully Homomorphic Encryptioncited by 0
  13. 2025Federated Learning with Enhanced Privacy via Model Splitting and Random Client Participationcited by 0
  14. 2025Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiencycited by 0
  15. 2026Jacobian-Guided Anisotropic Noise Reshaping for Enhancing Representation Utility under Local Differential Privacycited by 0
  16. 2026Dithered Gaussian Mechanism for Randomness-Efficient Differential Privacycited by 0
  17. 2026Robust Estimation of Sparse Numerical Vectors under Local Differential Privacycited by 0