The Privacy Blanket of the Shuffle Model

By Borja Balle, James Bell, Adrià Gascón, Kobbi Nissim. 2019

283 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Sociology and Political Science, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Sociology and Political Science

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “This can enable differentially private protocols with far smaller error than what is possible in the local model, while relying on weaker trust assumptions than in the central model [105, 157, 43, 179, 178].”
The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation (2021, methodology): “For more information on the shuffled model of DP, we refer the reader to Ghazi et al. (2020b; 2021; 2020c;a); Ishai et al. (2006); Balle et al. (2019; 2020); Balcer & Cheu (2020); Balcer et al. (2021); Girgis et al. (2020).”
Privacy Amplification by Decentralization (2020, methodology): “Our theoretical analysis leverages recent results on privacy amplification by subsampling [2], shuffling [17, 11, 4] and iteration [18], drawing interesting connections with these schemes.”
Secure Single-Server Aggregation with (Poly)Logarithmic Overhead (2020, methodology): “This primitive is the basis of the shuffle model of differential privacy [3, 4, 11, 19] and could be used for anonymized submissions [6].”
Breaking the Communication-Privacy-Accuracy Trilemma (2020, methodology): “For instance, when n = Ω (d), one can combine LDP with amplification techniques [14], [15], [16] to ensure stronger central differential privacy.”
Privacy Amplification via Random Check-Ins (2020, methodology): “There is also a growing line of works on privacy amplification by shuffling [10, 19, 12, 4, 6, 22, 18] that focus on various ways in which protocols can be designed using trusted shuffling primitives.”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, background): “Several recent works have aimed to determine the optimal trade-offs between communication, accuracy, and privacy in this model for various algorithmic tasks (Balle et al., 2019; Ghazi et al., 2019b;a; 2020b; Balle et al., 2020; Balcer & Cheu, 2020).”
Privacy in Deep Learning: A Survey (2020, background): “have proposed secure aggregation protocols that satisfy differential privacy guarantees in the shuffle model [120, 121].”
Private Summation in the Multi-Message Shuffle Model (2020, neutral): “messages [9] O(log(n/δ)/ ) O( √ n) [2] O(n/ ) 1 [13] O(log(1/δ)/ ) O(log(n/ δ)) [15] O(1/ ) O(1 + logn(1/δ)) Section 4 O((log log n) log(1/δ)/ ) O(log log n) Section 5 O(1/ ) O(log(n/δ)) Section 6 O(1/ ) O(1 + logn(1/δ))”
The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, methodology): “New models for differentially private computation have recently emerged to alleviate the (inevitable) low accuracy of the local model, of which we will discuss the shuffle model [38, 14, 19, 6, 5, 32] and the hybrid model [2].”
Differentially Private Summation with Multi-Message Shuffling (2019, background): “A proof that one message is not enough is given in [1].”
The Power of the Hybrid Model for Mean Estimation (2018, background): “Several works have since improved the original analyses and expanded the shuffle model to achieve even greater improvements in the users’ DP guarantee [6, 7, 30–33].”
Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation (2020, background): “Through an extensive set of experiments with data sets having long-tail distributions we show that attribute fragmenting help recover much larger fraction of the tail for the same central privacy guarantee (as compared to generically applying privacy amplification by shuffling for locally private al”
Separating Local & Shuffled Differential Privacy via Histograms (2019, methodology): “This separation was previously shown by [2, 1] for the summation problem.”