Distributed differential privacy via shuffling
From MaRDI portal
Publication:2292652
Abstract: 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.
Recommendations
- The privacy blanket of the shuffle model
- Spreading the privacy blanket: differentially oblivious shuffling for differential privacy
- On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy
- Amplification by shuffling: from local to central differential privacy via anonymity
- On the round complexity of the shuffle model
Cited in
(40)- On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy
- Non-interactive anonymous router
- Spreading the privacy blanket: differentially oblivious shuffling for differential privacy
- Private aggregation from fewer anonymous messages
- On the round complexity of the shuffle model
- Efficient noise generation to achieve differential privacy with applications to secure multiparty computation
- The privacy blanket of the shuffle model
- Computational differential privacy from lattice-based cryptography
- Distributed private heavy hitters
- Distributed Private Data Analysis: Simultaneously Solving How and What
- Near Optimal Coded Data Shuffling for Distributed Learning
- Amplification by shuffling: from local to central differential privacy via anonymity
- Separating Local & Shuffled Differential Privacy via Histograms
- The power of synergy in differential privacy: combining a small curator with local randomizers
- Pure differentially private summation from anonymous messages
- High-dimensional \(M\)-estimation for Byzantine-robust decentralized learning
- A theory of composition for differential obliviousness
- An accurate, scalable and verifiable protocol for federated differentially private averaging
- Approximate distance-comparison-preserving symmetric encryption
- PAC privacy: automatic privacy measurement and control of data processing
- Zero-knowledge succinct non-interactive arguments of knowledge based on sets of polynomials
- Additive randomized encodings and their applications
- Differential privacy: getting more for less
- Total variation distance privacy: accurately measuring inference attacks and improving utility
- Who started this rumor? Quantifying the natural differential privacy of gossip protocols
- Byzantine-resilient decentralized network learning
- Non-interactive anonymous router with quasi-linear router computation
- Privacy-preserving Frank-Wolfe on shuffle model
- Differentially private aggregation via imperfect shuffling
- MPC for tech giants (GMPC): enabling Gulliver and the Lilliputians to cooperate amicably
- Computationally differentially private inner-product protocols imply oblivious transfer
- Information-theoretic single-server PIR in the shuffle model
- Pure-DP aggregation in the shuffle model: error-optimal and communication-efficient
- Advanced composition theorems for differential obliviousness
- Private distribution testing with heterogeneous constraints: your epsilon might not be mine
- Review of mathematical optimization in federated learning
- Private stochastic optimization with large worst-case Lipschitz parameter: optimal rates for (non-smooth) convex losses and extension to non-convex losses
- Infinitely divisible noise in the low privacy regime
- On distributed differential privacy and counting distinct elements
- Secret-shared shuffle from authenticated correlations
This page was built for publication: Distributed differential privacy via shuffling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2292652)
