# Private Summation in the Multi-Message Shuffle Model

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

## Key facts

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

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

- [The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation](https://mlsanity.com/paper/2102.06387/) (2021)
- [The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning](https://mlsanity.com/paper/2203.03761/) (2022)
- [Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacy](https://mlsanity.com/paper/2208.04591/) (2022)
- [Shuffle Private Linear Contextual Bandits](https://mlsanity.com/paper/2202.05567/) (2022)
- [Differentially Private Multi-Armed Bandits in the Shuffle Model](https://mlsanity.com/paper/2106.02900/) (2021)
- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [On the Renyi Differential Privacy of the Shuffle Model](https://mlsanity.com/paper/2105.05180/) (2021)
- [Distributed Differential Privacy in Multi-Armed Bandits](https://mlsanity.com/paper/2206.05772/) (2022)
- [Towards Sparse Federated Analytics: Location Heatmaps under Distributed Differential Privacy with Secure Aggregation](https://mlsanity.com/paper/2111.02356/) (2021)
- [User-Level Private Learning via Correlated Sampling](https://mlsanity.com/paper/2110.11208/) (2021)
- [Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed Learning](https://mlsanity.com/paper/2107.08763/) (2021)
- [Samplable Anonymous Aggregation for Private Federated Data Analysis](https://mlsanity.com/paper/2307.15017/) (2023)
- [Tight Accounting in the Shuffle Model of Differential Privacy](https://mlsanity.com/paper/2106.00477/) (2021)
- [Differential Secrecy for Distributed Data and Applications to Robust Differentially Secure Vector Summation](https://mlsanity.com/paper/2202.10618/) (2022)
- [Group privacy for personalized federated learning](https://mlsanity.com/paper/2206.03396/) (2022)
- [Federated Calibration and Evaluation of Binary Classifiers](https://mlsanity.com/paper/2210.12526/) (2022)
- [Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages](https://mlsanity.com/paper/2404.10201/) (2024)
- [Toward the Tradeoffs between Privacy, Fairness and Utility in Federated Learning](https://mlsanity.com/paper/2311.18190/) (2023)
- [Transfer Learning In Differential Privacy's Hybrid-Model](https://mlsanity.com/paper/2201.12018/) (2022)
- [Learning from End User Data with Shuffled Differential Privacy over Kernel Densities](https://mlsanity.com/paper/2502.14087/) (2025)
- [Multi-Message Shuffled Privacy in Federated Learning](https://mlsanity.com/paper/2302.11152/) (2023)
- [FastLloyd: Federated, Accurate, Secure, and Tunable k-Means Clustering with Differential Privacy](https://mlsanity.com/paper/2405.02437/) (2024)
- [The Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Model](https://mlsanity.com/paper/2103.15690/) (2021)
- [Beyond Statistical Estimation: Differentially Private Individual Computation via Shuffling](https://mlsanity.com/paper/2406.18145/) (2024)
- [PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors](https://mlsanity.com/paper/2503.11897/) (2025)
- [How to Securely Shuffle? A survey about Secure Shufflers for privacy-preserving computations](https://mlsanity.com/paper/2507.01487/) (2025)
- [Securing Private Federated Learning in a Malicious Setting: A Scalable TEE-Based Approach with Client Auditing](https://mlsanity.com/paper/2509.08709/) (2025)
- [Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2602.00417/) (2026)
- [Infinitely Divisible Noise in the Low Privacy Regime](https://mlsanity.com/paper/2110.06559/) (2021)
- [Anonymized Histograms in Intermediate Privacy Models](https://mlsanity.com/paper/2210.15178/) (2022)

## 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).