Scalable and Differentially Private Distributed Aggregation in the Shuffled Model

By Badih Ghazi, Rasmus Pagh, Ameya Velingker. 2019

105 citations recorded by the source corpus.

Federated learning promises to make machine learning feasible on distributed, private datasets by implementing gradient descent using secure aggregation methods. The idea is to compute a global weight update without revealing the contributions of individual users. Current practical protocols for secure aggregation work in an "honest but curious" setting where a curious adversary observing all communication to and from the server cannot learn any private information assuming the server is honest and follows the protocol. A more scalable and robust primitive for privacy-preserving protocols is shuffling of user data, so as to hide the origin of each data item. Highly scalable and secure protocols for shuffling, so-called mixnets, have been proposed as a primitive for privacy-preserving analytics in the Encode-Shuffle-Analyze framework by Bittau et al., which was later analytically studied by Erlingsson et al. and Cheu et al.. The recent papers by Cheu et al., and Balle et al. have given protocols for secure aggregation that achieve differential privacy guarantees in this "shuffled model". Their protocols come at a cost, though: Either the expected aggregation error or the amount of communication per user scales as a polynomial $n^{\Omega(1)}$ in the number of users $n$. In this paper we propose simple and more efficient protocol for aggregation in the shuffled model, where communication as well as error increases only polylogarithmically in $n$. Our new technique is a conceptual "invisibility cloak" that makes users' data almost indistinguishable from random noise while introducing zero distortion on the sum.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, 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 Computational Theory and Mathematics

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, neutral): “[180] log( n εδ ) log( δ ) 1 ε √ log 1 δ”
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].”
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): “Furthermore, the recent histogram protocols of Ghazi et al. (2019a); Erlingsson et al. (2020), are also not applicable since they all incur an MSE of Ω(log n).”
Privacy in Deep Learning: A Survey (2020, background): “More recent work [122] mitigates the incurred error and communication overheads in shuffle model.”
Private Summation in the Multi-Message Shuffle Model (2020, positive): “Quantitatively, our noise addition technique makes the error independent of δ, saving a factor of O(log(1/δ)) in the MSE, and our communication complexity is independent of saving a factor of O(log(1/ )) over [13].”
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].”
Private Aggregation from Fewer Anonymous Messages (2019, methodology): “is σ-secure even for m = Θ ( 1 + σ+log q logn ) messages, improving upon the known bounds of O(log n+ σ + log q) [17, 3, 15].”
Improved Summation from Shuffling (2019, methodology): “[5] which, by a black-box application of the IKOS protocol, showed that in the shuffle model one can achieve the same accuracy/privacy trade-offs than in the central model of DP for the task of real summation.”
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].”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “Thus, while SMC cannot guarantee protection from information leakage, it can be combined with differential privacy to achieve stronger privacy guarantees.”
Separating Local & Shuffled Differential Privacy via Histograms (2019, background): “For data drawn from an underlying distribution, the results from [7, 1, 10] all imply a polynomial separation in sample complexity between the local and shuffled models.”
Connecting Robust Shuffle Privacy and Pan-Privacy (2020, methodology): “For an example of a formal argument, see work by Ghazi, Pagh, and Velingker [24].”
Survey on Federated Learning Threats: concepts, taxonomy on attacks and defences, experimental study and challenges (2022, background): “aggregation schemes have been improved in terms of privacy with the addition of DP mechanisms [149, 150, 151, 152] .”