mlsanityData to 7 Oct 2026

Private Summation in the Multi-Message Shuffle Model

arXiv 2002.00817 ↗First posted 3 Feb 2020cs.CRcited by 34

Not on the map. Why?

Abstract (arXiv)

The shuffle model of differential privacy (Erlingsson et al. SODA 2019; Cheu et al. EUROCRYPT 2019) and its close relative encode-shuffle-analyze (Bittau et al. SOSP 2017) provide a fertile middle ground between the well-known local and central models. Similarly to the local model, the shuffle model assumes an untrusted data collector who receives privatized messages from users, but in this case a secure shuffler is used to transmit messages from users to the collector in a way that hides which messages came from which user. An interesting feature of the shuffle model is that increasing the amount of messages sent by each user can lead to protocols with accuracies comparable to the ones achievable in the central model. In particular, for the problem of privately computing the sum of n bounded real values held by n different users, Cheu et al. showed that O(√n) messages per user suffice to achieve O(1) error (the optimal rate in the central model), while Balle et al. (CRYPTO 2019) recently showed that a single message per user leads to Theta(n1/3) MSE (mean squared error), a rate strictly in-between what is achievable in the local and central models. This paper introduces two new protocols for summation in the shuffle model with improved accuracy and communication trade-offs. Our first contribution is a recursive construction based on the protocol from Balle et al. mentioned above, providing poly(log log n) error with O(log log n) messages per user. The second contribution is a protocol with O(1) error and O(1) messages per user based on a novel analysis of the reduction from secure summation to shuffling introduced by Ishai et al. (FOCS 2006) (the original reduction required O(log n) messages per user).

Key facts. Cited by 34 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Feb 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 10; 2022: 9; 2023: 3; 2024: 5; 2025: 5; 2026: 2.

34 papers.

Sort:

  1. 2021The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregationcited by 127
  2. 2022The Fundamental Price of Secure Aggregation in Differentially Private Federated Learningcited by 39
  3. 2022Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacycited by 29
  4. 2022Shuffle Private Linear Contextual Banditscited by 27
  5. 2021Differentially Private Multi-Armed Bandits in the Shuffle Modelcited by 24
  6. 2021Locally Private k-Means in One Roundcited by 19
  7. 2021On the Renyi Differential Privacy of the Shuffle Modelcited by 16
  8. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
  9. 2021Towards Sparse Federated Analytics: Location Heatmaps under Distributed Differential Privacy with Secure Aggregationcited by 10
  10. 2021User-Level Private Learning via Correlated Samplingcited by 9
  11. 2021Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed Learningcited by 6
  12. 2023Samplable Anonymous Aggregation for Private Federated Data Analysiscited by 6
22 more
  1. 2021Tight Accounting in the Shuffle Model of Differential Privacycited by 5
  2. 2022Differential Secrecy for Distributed Data and Applications to Robust Differentially Secure Vector Summationcited by 5
  3. 2022Group privacy for personalized federated learningcited by 5
  4. 2022Federated Calibration and Evaluation of Binary Classifierscited by 5
  5. 2024Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messagescited by 5
  6. 2023Toward the Tradeoffs between Privacy, Fairness and Utility in Federated Learningcited by 4
  7. 2022Transfer Learning In Differential Privacy's Hybrid-Modelcited by 3
  8. 2023Multi-Message Shuffled Privacy in Federated Learningcited by 2
  9. 2024FastLloyd: Federated, Accurate, Secure, and Tunable k-Means Clustering with Differential Privacycited by 2
  10. 2021The Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Modelcited by 1
  11. 2024Beyond Statistical Estimation: Differentially Private Individual Computation via Shufflingcited by 1
  12. 2025Learning from End User Data with Shuffled Differential Privacy over Kernel Densitiescited by 1
  13. 2025PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectorscited by 1
  14. 2025How to Securely Shuffle? A survey about Secure Shufflers for privacy-preserving computationscited by 1
  15. 2021Infinitely Divisible Noise in the Low Privacy Regimecited by 0
  16. 2022Anonymized Histograms in Intermediate Privacy Modelscited by 0
  17. 2024Amalgam: A Framework for Obfuscated Neural Network Training on the Cloudcited by 0
  18. 2024Differential Privacy on Trust Graphscited by 0
  19. 2025Dropout-Robust Mechanisms for Differentially Private and Fully Decentralized Mean Estimationcited by 0
  20. 2025Securing Private Federated Learning in a Malicious Setting: A Scalable TEE-Based Approach with Client Auditingcited by 0
  21. 2026Shuffle and Joint Differential Privacy for Generalized Linear Contextual Banditscited by 0
  22. 2026Accurate, private, secure, federated U-statistics with higher degreecited by 0