# Pure Differentially Private Summation from Anonymous Messages

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

## Key facts

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

## Built on by (most cited first, 15 of 15)

- [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)
- [Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging](https://mlsanity.com/paper/2206.05091/) (2022)
- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (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)
- [Differentially Private Multi-Site Treatment Effect Estimation](https://mlsanity.com/paper/2310.06237/) (2023)
- [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)
- [How to Securely Shuffle? A survey about Secure Shufflers for privacy-preserving computations](https://mlsanity.com/paper/2507.01487/) (2025)
- [Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2602.00417/) (2026)
- [Uniformity Testing in the Shuffle Model: Simpler, Better, Faster](https://mlsanity.com/paper/2108.08987/) (2021)
- [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 shuffled (aka anonymous) model has recently generated significant interest as a candidate distributed privacy framework with trust assumptions better than the central model but with achievable errors smaller than the local model. We study pure differentially private (DP) protocols in the shuffled model for summation, a basic and widely used primitive: - For binary summation where each of n users holds a bit as an input, we give a pure ε-DP protocol for estimating the number of ones held by the users up to an error of Oε(1), and each user sends Oε(log n) messages each of 1 bit. This is the first pure protocol in the shuffled model with error o(√n) for constant ε. Using this protocol, we give a pure ε-DP protocol that performs summation of real numbers in [0, 1] up to an error of Oε(1), and where each user sends Oε(log3 n) messages each of O(loglog n) bits. - In contrast, we show that for any pure ε-DP protocol for binary summation in the shuffled model having absolute error n0.5-Omega(1), the per user communication has to be at least Omegaε(√log n) bits. This implies the first separation between the (bounded-communication) multi-message shuffled model and the central model, and the first separation between pure and approximate DP protocols in the shuffled model. To prove our lower bound, we consider (a generalization of) the following question: given γ in (0, 1), what is the smallest m for which there are two random variables X0, X1 supported on 0, dots ,m such that (i) the total variation distance between X0 and X1 is at least 1-γ, and (ii) the moment generating functions of X0 and X1 are within a constant factor of each other everywhere? We show that the answer is m = Theta(√log(1/γ)).