Paper 2019/245

Distributed Differential Privacy via Shuffling

Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev


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 multiparty computation (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., SOSP 2017), 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.

Available format(s)
Publication info
Published by the IACR in EUROCRYPT 2019
differential privacy
Contact author(s)
cheu a @ husky neu edu
ads22 @ bu edu
jullman @ ccs neu edu
dzeber @ mozilla com
maxim zhilyaev @ gmail com
2019-02-28: received
Short URL
Creative Commons Attribution


      author = {Albert Cheu and Adam Smith and Jonathan Ullman and David Zeber and Maxim Zhilyaev},
      title = {Distributed Differential Privacy via Shuffling},
      howpublished = {Cryptology ePrint Archive, Paper 2019/245},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.