# The Privacy Blanket of the Shuffle Model

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

## Key facts

- Cited by 74 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Mar 2019.

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

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation](https://mlsanity.com/paper/2102.06387/) (2021)
- [Differentially Private Federated Learning on Heterogeneous Data](https://mlsanity.com/paper/2111.09278/) (2021)
- [Composition of Differential Privacy & Privacy Amplification by Subsampling](https://mlsanity.com/paper/2210.00597/) (2022)
- [The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning](https://mlsanity.com/paper/2203.03761/) (2022)
- [Optimal Algorithms for Mean Estimation under Local Differential Privacy](https://mlsanity.com/paper/2205.02466/) (2022)
- [Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses](https://mlsanity.com/paper/2106.09779/) (2021)
- [Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacy](https://mlsanity.com/paper/2208.04591/) (2022)
- [Lossless Compression of Efficient Private Local Randomizers](https://mlsanity.com/paper/2102.12099/) (2021)
- [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)
- [Optimal Compression of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2111.00092/) (2021)
- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [Differentially Private Stochastic Linear Bandits: (Almost) for Free](https://mlsanity.com/paper/2207.03445/) (2022)
- [How Much Privacy Does Federated Learning with Secure Aggregation Guarantee?](https://mlsanity.com/paper/2208.02304/) (2022)
- [Privacy Amplification via Shuffling for Linear Contextual Bandits](https://mlsanity.com/paper/2112.06008/) (2021)
- [Privacy-Aware Compression for Federated Data Analysis](https://mlsanity.com/paper/2203.08134/) (2022)
- [Discrete Distribution Estimation under User-level Local Differential Privacy](https://mlsanity.com/paper/2211.03757/) (2022)
- [On the Renyi Differential Privacy of the Shuffle Model](https://mlsanity.com/paper/2105.05180/) (2021)
- [Differentially Private Speaker Anonymization](https://mlsanity.com/paper/2202.11823/) (2022)
- [Privacy amplification by random allocation](https://mlsanity.com/paper/2502.08202/) (2025)
- [Distributed Differential Privacy in Multi-Armed Bandits](https://mlsanity.com/paper/2206.05772/) (2022)
- [On Differentially Private Federated Linear Contextual Bandits](https://mlsanity.com/paper/2302.13945/) (2023)
- [Differentially Private Exploration in Reinforcement Learning with Linear Representation](https://mlsanity.com/paper/2112.01585/) (2021)
- [Towards Sparse Federated Analytics: Location Heatmaps under Distributed Differential Privacy with Secure Aggregation](https://mlsanity.com/paper/2111.02356/) (2021)
- [Private Frequency Estimation via Projective Geometry](https://mlsanity.com/paper/2203.00194/) (2022)
- [Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming](https://mlsanity.com/paper/2104.01808/) (2021)
- [Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed Learning](https://mlsanity.com/paper/2107.08763/) (2021)
- [Nonparametric extensions of randomized response for private confidence sets](https://mlsanity.com/paper/2202.08728/) (2022)
- [Network Shuffling: Privacy Amplification via Random Walks](https://mlsanity.com/paper/2204.03919/) (2022)

## Abstract (arXiv)

This work studies differential privacy in the context of the recently proposed shuffle model. Unlike in the local model, where the server collecting privatized data from users can track back an input to a specific user, in the shuffle model users submit their privatized inputs to a server anonymously. This setup yields a trust model which sits in between the classical curator and local models for differential privacy. The shuffle model is the core idea in the Encode, Shuffle, Analyze (ESA) model introduced by Bittau et al. (SOPS 2017). Recent work by Cheu et al. (EUROCRYPT 2019) analyzes the differential privacy properties of the shuffle model and shows that in some cases shuffled protocols provide strictly better accuracy than local protocols. Additionally, Erlingsson et al. (SODA 2019) provide a privacy amplification bound quantifying the level of curator differential privacy achieved by the shuffle model in terms of the local differential privacy of the randomizer used by each user. In this context, we make three contributions. First, we provide an optimal single message protocol for summation of real numbers in the shuffle model. Our protocol is very simple and has better accuracy and communication than the protocols for this same problem proposed by Cheu et al. Optimality of this protocol follows from our second contribution, a new lower bound for the accuracy of private protocols for summation of real numbers in the shuffle model. The third contribution is a new amplification bound for analyzing the privacy of protocols in the shuffle model in terms of the privacy provided by the corresponding local randomizer. Our amplification bound generalizes the results by Erlingsson et al. to a wider range of parameters, and provides a whole family of methods to analyze privacy amplification in the shuffle model.