Paper 2021/1257

Spreading the Privacy Blanket: Differentially Oblivious Shuffling for Differential Privacy

S. Dov Gordon, Jonathan Katz, Mingyu Liang, and Jiayu Xu


In the shuffle model for differential privacy, users locally randomize their data and then submit the results to a trusted ``shuffler'' who mixes the responses before sending them to a server for analysis. This is a promising model for real-world applications of differential privacy, as a series of recent results have shown that, in some cases, the shuffle model offers a strictly better privacy/utility tradeoff than what is possible in a purely local model. The recent ``privacy blanket'' notion provides a simple method for analyzing differentially private protocols in the shuffle model. A downside of the shuffle model is its reliance on a trusted shuffling mechanism, and it is natural to try to replace this with a distributed shuffling protocol run by the users themselves. Unfortunately, with only one exception, existing fully secure shuffling protocols require $\Omega(n^2)$ communication. In this work, we put forth a notion of differential obliviousness for shuffling protocols, and prove that this notion provides the necessary guarantees for the privacy blanket, without requiring a trusted shuffler. We also show a differentially oblivious shuffling protocol based on onion routing that can tolerate any constant fraction of corrupted users and requires only $O(n \log n)$ communication.

Available format(s)
Cryptographic protocols
Publication info
Preprint. Minor revision.
Differential privacyProtocolsOnion routing
Contact author(s)
gordon @ gmu edu
jkatz2 @ gmail com
mliang5 @ gmu edu
jiayux @ uci edu
2021-09-21: received
Short URL
Creative Commons Attribution


      author = {S.  Dov Gordon and Jonathan Katz and Mingyu Liang and Jiayu Xu},
      title = {Spreading the Privacy Blanket: Differentially Oblivious Shuffling for Differential Privacy},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1257},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.