Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity

By Ú. Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, Abhradeep Thakurta. 2018

512 citations recorded by the source corpus.

Sensitive statistics are often collected across sets of users, with repeated collection of reports done over time. For example, trends in users' private preferences or software usage may be monitored via such reports. We study the collection of such statistics in the local differential privacy (LDP) model, and describe an algorithm whose privacy cost is polylogarithmic in the number of changes to a user's value. More fundamentally---by building on anonymity of the users' reports---we also demonstrate how the privacy cost of our LDP algorithm can actually be much lower when viewed in the central model of differential privacy. We show, via a new and general privacy amplification technique, that any permutation-invariant algorithm satisfying e-local differential privacy will satisfy [MATH HERE]-central differential privacy. By this, we explain how the high noise and [MATH HERE] overhead of LDP protocols is a consequence of them being significantly more private in the central model. As a practical corollary, our results imply that several LDP-based industrial deployments may have much lower privacy cost than their advertised e would indicate---at least if reports are anonymized.

Subfields: Artificial Intelligence, Safety, Robustness & Interpretability

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 Safety, Robustness & Interpretability

Citations in the corpus

The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks (2018, background): “Of course, these improved proof techniques often rely on additional (albeit realistic) assumptions, such as that random shuffling can be used to provide unlinkability [17] or that the intermediate model weights computed during training can be hidden from the adversary [18].”
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].”
Practical and Private (Deep) Learning without Sampling or Shuffling (2021, methodology): “The privacy analysis heavily uses tools like privacy amplification by sampling/shuffling [1, 6, 23, 30, 42, 72, 76] to obtain the best privacy/utility tradeoffs.”
Privacy Amplification by Decentralization (2020, methodology): “We can obtain a similar result for histograms by bounding the privacy loss incurred for each cycle by using ampliﬁcation by shuﬄing (Erlingsson et al., 2019; Balle et al., 2019b; Feldman et al., 2020), similar to what we did for the ring topology (Section 3.2).”
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): “Source of Privacy Amplification ε for Central DP None [14, 32] ε0 Uniform subsampling [25, 9, 1] O (e0/ √ n) Shuffling [19] O ( e0/ √ n )”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, methodology): “DP in the shuffled model was first formally investigated, independently, by Erlingsson et al. (2019) and Cheu et al. (2019).”
Private Summation in the Multi-Message Shuffle Model (2020, methodology): “3 The Shuffle Model The shuffle model of differential privacy [6, 4] considers a data collector that receives messages from n users (possibly multiple messages from each user).”
The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, methodology): “2Furthermore, the shuffle model provides new “privacy amplification” tools that can be used in the design of differentially private algorithms [27, 6].”
Secure Federated Submodel Learning (2019, background): “[58] considered a similar setting, in particular the collection of user statistics (e.”
Honeycrisp: large-scale differentially private aggregation without a trusted core (2019, background): “More recent theoretical work tackles similar challenges of infrequently changing data – [45] assumes that the data is drawn from some set of underlying distributions that aren’t changing, while [31] assumes that individuals’ data aren’t changing very frequently – by contrast Honeycrisp only makes as”
Private Aggregation from Fewer Anonymous Messages (2019, methodology): “The shuffled model is based on the Encode-Shuffle-Analyze architecture of [6] and was first analytically studied by [8,12] and further studied in recent work [4,13].”
Improved Summation from Shuffling (2019, background): “is of significant relevance in the context of the recently proposed shuffle model of Differential Privacy (DP) [2] (see also [4, 3]).”
Differentially Private Summation with Multi-Message Shuffling (2019, background): “The shuffle model of differential privacy [3, 2] considers a data collector that receives messages from n users (possibly multiple messages from each user).”
Scalable and Differentially Private Distributed Aggregation in the Shuffled Model (2019, methodology): “We consider the problem of privately summing n numbers in the shufﬂed model which is based on the Encode-Shufﬂe-Analyze architecture of Bittau et al. [5] and was ﬁrst analytically studied in [9, 7].”