# Improved Summation from Shuffling

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Sep 2019.

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

- [On the Renyi Differential Privacy of the Shuffle Model](https://mlsanity.com/paper/2105.05180/) (2021)
- [Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed Learning](https://mlsanity.com/paper/2107.08763/) (2021)
- [Learning from End User Data with Shuffled Differential Privacy over Kernel Densities](https://mlsanity.com/paper/2502.14087/) (2025)
- [How to Securely Shuffle? A survey about Secure Shufflers for privacy-preserving computations](https://mlsanity.com/paper/2507.01487/) (2025)

## Abstract (arXiv)

A protocol by Ishai et al. (FOCS 2006) showing how to implement distributed n-party summation from secure shuffling has regained relevance in the context of the recently proposed shuffle model of differential privacy, as it allows to attain the accuracy levels of the curator model at a moderate communication cost. To achieve statistical security 2-σ, the protocol by Ishai et al. requires the number of messages sent by each party to em grow logarithmically with n as O(log n + σ). In this note we give an improved analysis achieving a dependency of the form O(1+σ/log n). Conceptually, this addresses the intuitive question left open by Ishai et al. of whether the shuffling step in their protocol provides a "hiding in the crowd" amplification effect as n increases. From a practical perspective, our analysis provides explicit constants and shows, for example, that the method of Ishai et al. applied to summation of 32-bit numbers from n=104 parties sending 12 messages each provides statistical security 2-40.