mlsanityData to 7 Oct 2026

Distributed Differential Privacy via Shuffling

arXiv 1808.01394 ↗First posted 4 Aug 2018cs.CR cs.DScited by 115

Not on the map. Why?

Abstract (arXiv)

We consider the problem of designing scalable, robust protocols for computing statistics about sensitive data. Specifically, we look at how best to design differentially private protocols in a distributed setting, where each user holds a private datum. The literature has mostly considered two models: the "central" model, in which a trusted server collects users' data in the clear, which allows greater accuracy; and the "local" model, in which users individually randomize their data, and need not trust the server, but accuracy is limited. Attempts to achieve the accuracy of the central model without a trusted server have so far focused on variants of cryptographic MPC, which limits scalability. In this paper, we initiate the analytic study of a shuffled model for distributed differentially private algorithms, which lies between the local and central models. This simple-to-implement model, a special case of the ESA framework of [Bittau et al., '17], augments the local model with an anonymous channel that randomly permutes a set of user-supplied messages. For sum queries, we show that this model provides the power of the central model while avoiding the need to trust a central server and the complexity of cryptographic secure function evaluation. More generally, we give evidence that the power of the shuffled model lies strictly between those of the central and local models: for a natural restriction of the model, we show that shuffled protocols for a widely studied selection problem require exponentially higher sample complexity than do central-model protocols.

Key facts. Cited by 115 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 Aug 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 30; 2022: 30; 2023: 18; 2024: 13; 2025: 11; 2026: 13.

115 papers.

Sort:

  1. 2021The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregationcited by 127
  2. 2021Deep Learning with Label Differential Privacycited by 113
  3. 2023Foundation Models and Fair Usecited by 112
  4. 2021Label Leakage and Protection in Two-party Split Learningcited by 87
  5. 2021Differentially Private Federated Learning on Heterogeneous Datacited by 74
  6. 2021On Large-Cohort Training for Federated Learningcited by 73
  7. 2022Composition of Differential Privacy & Privacy Amplification by Subsamplingcited by 42
  8. 2022Optimal Algorithms for Mean Estimation under Local Differential Privacycited by 36
  9. 2022On Privacy and Personalization in Cross-Silo Federated Learningcited by 36
  10. 2022SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compressioncited by 34
  11. 2021Differentially Private Federated Bayesian Optimization with Distributed Explorationcited by 32
  12. 2021Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Lossescited by 30
38 more
  1. 2022Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacycited by 29
  2. 2021Lossless Compression of Efficient Private Local Randomizerscited by 27
  3. 2022Shuffle Private Linear Contextual Banditscited by 27
  4. 2022Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averagingcited by 27
  5. 2022Label Leakage and Protection from Forward Embedding in Vertical Federated Learningcited by 26
  6. 2022Private Non-Convex Federated Learning Without a Trusted Servercited by 26
  7. 2021Differentially Private Multi-Armed Bandits in the Shuffle Modelcited by 24
  8. 2021Efficient Differentially Private Secure Aggregation for Federated Learning via Hardness of Learning with Errorscited by 23
  9. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  10. 2023Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimationcited by 22
  11. 2021Defending against Reconstruction Attack in Vertical Federated Learningcited by 20
  12. 2021Label differential privacy via clusteringcited by 20
  13. 2023Differentially Private Natural Language Models: Recent Advances and Future Directionscited by 20
  14. 2021Locally Private k-Means in One Roundcited by 19
  15. 2022Differentially Private Stochastic Linear Bandits: (Almost) for Freecited by 19
  16. 2021Shuffle Private Stochastic Convex Optimizationcited by 17
  17. 2021Privacy Amplification via Shuffling for Linear Contextual Banditscited by 17
  18. 2022Discrete Distribution Estimation under User-level Local Differential Privacycited by 17
  19. 2024The Privacy Power of Correlated Noise in Decentralized Learningcited by 17
  20. 2021On the Renyi Differential Privacy of the Shuffle Modelcited by 16
  21. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
  22. 2023On Differentially Private Federated Linear Contextual Banditscited by 14
  23. 2023Fast Optimal Locally Private Mean Estimation via Random Projectionscited by 14
  24. 2023Unified Enhancement of Privacy Bounds for Mixture Mechanisms via f-Differential Privacycited by 13
  25. 2025Privacy amplification by random allocationcited by 13
  26. 2021Differentially Private Exploration in Reinforcement Learning with Linear Representationcited by 11
  27. 2021Towards Sparse Federated Analytics: Location Heatmaps under Distributed Differential Privacy with Secure Aggregationcited by 10
  28. 2023Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraintscited by 10
  29. 2021User-Level Private Learning via Correlated Samplingcited by 9
  30. 2022Private Frequency Estimation via Projective Geometrycited by 9
  31. 2023ULDP-FL: Federated Learning with Across Silo User-Level Differential Privacycited by 9
  32. 2022Differentially Private Linear Bandits with Partial Distributed Feedbackcited by 8
  33. 2024Differentially Private Decentralized Learning with Random Walkscited by 8
  34. 2025Towards Trustworthy Federated Learning with Untrusted Participantscited by 8
  35. 2022DPAUC: Differentially Private AUC Computation in Federated Learningcited by 7
  36. 2022Skellam Mixture Mechanism: a Novel Approach to Federated Learning with Differential Privacycited by 7
  37. 2021Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed Learningcited by 6
  38. 2022Differential Privacy Amplification in Quantum and Quantum-inspired Algorithmscited by 6

50 most cited of 115 All 115 (JSON)