Distributed Differential Privacy via Shuffling

By Albert Cheu, Adam D. Smith, Jonathan Ullman, David Zeber, Maxim Zhilyaev. 2018

433 citations recorded by the source corpus.

We consider the problem of designing scalable, robust protocols for computing statistics about sensitive data. Specifically, we look at how best to design differentially private protocols in a distributed setting, where each user holds a private datum. The literature has mostly considered two models: the "central" model, in which a trusted server collects users' data in the clear, which allows greater accuracy; and the "local" model, in which users individually randomize their data, and need not trust the server, but accuracy is limited. Attempts to achieve the accuracy of the central model without a trusted server have so far focused on variants of cryptographic MPC, which limits scalability. In this paper, we initiate the analytic study of a shuffled model for distributed differentially private algorithms, which lies between the local and central models. This simple-to-implement model, a special case of the ESA framework of [Bittau et al., '17], augments the local model with an anonymous channel that randomly permutes a set of user-supplied messages. For sum queries, we show that this model provides the power of the central model while avoiding the need to trust a central server and the complexity of cryptographic secure function evaluation. More generally, we give evidence that the power of the shuffled model lies strictly between those of the central and local models: for a natural restriction of the model, we show that shuffled protocols for a widely studied selection problem require exponentially higher sample complexity than do central-model protocols.

Subfields: Federated & Distributed Learning, 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 Federated & Distributed Learning

In Privacy & Security

Citations in the corpus

Foundation Models and Fair Use (2023, background): “, Smart Compose, telemetry collection) (Miraglia, 2019; Erlingsson et al., 2014; Ding et al., 2017; Bittau et al., 2017; Cheu et al., 2019).”
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, background): “FL with SecAgg and Distributed DP Despite the recent surge of interest in distributed DP, much of the work in this space focuses on the shuffled model of DP where a trusted third party (or a trusted execution environment) shuffles the noisy client updates before forwarding them to the server (Erling”
DISCO: Dynamic and Invariant Sensitive Channel Obfuscation for deep neural networks (2020, methodology): “Additionally, techniques such as multi-party computation [14, 15] and differential privacy [16, 17, 18, 19] have been employed to improve the privacy in federated-learning.”
Privacy Amplification by Decentralization (2020, methodology): “Recent work has also considered the so-called shuffle model of DP [11, 17, 4, 3, 20], where users send their contribution to a trusted/secure shuffler which permutes the set of messages so as to hide their source.”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, methodology): “Cheu et al. (2019) showed that the standard Randomized Response (which goes back to Warner (1965) in the local DP case) is (ε, δ)-DP and incurs a squared error of O( 1ε2 · log 1 δ ) with high probability.”
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, methodology): “[9] show that with a single message one could achieve MSE Θ(n), and O(n) messages where enough to achieve error O(1).”
The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, background): “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].”
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, methodology): “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): “In contrast, protocols based on shufﬂing work with much weaker assumptions on the server [5, 7].”
The Power of the Hybrid Model for Mean Estimation (2018, background): “Conversely, the LM users may experience privacy amplification through the combination of their locally-added noise; however, this is solely due to intra-group interaction in the LM, and related topics are currently an active area of research on the LM [5, 6, 16, 19, 26, 33].”
Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation (2020, background): “This lack of clarity is especially concerning because of recent formal results—known colloquially as “privacy amplification by shuffling” [3], [13], [14], [19]—which have fundamentally changed privacy/utility tradeoffs and forced a reconsideration of previous approaches, like those described above.”