Paper 2021/1257

Spreading the Privacy Blanket: Differentially Oblivious Shuffling for Differential Privacy

S. Dov Gordon, George Mason University
Jonathan Katz, University of Maryland, College Park
Mingyu Liang, George Mason University
Jiayu Xu, Algorand

In the shuffle model for differential privacy, $n$ users locally randomize their data and submit the results to a trusted “shuffler” who mixes the results before sending them to a server for analysis. This is a promising model for real-world applications of differential privacy, as several recent results have shown that the shuffle model sometimes offers a strictly better privacy/utility tradeoff than what is possible in a purely local model. A downside of the shuffle model is its reliance on a trusted shuffler, and it is natural to try to replace this with a distributed shuffling protocol run by the users themselves. While it would of course be possible to use a fully secure shuffling protocol, one might hope to instead use a more-efficient protocol having weaker security guarantees. In this work, we consider a relaxation of secure shuffling called differential obliviousness that we prove suffices for differential privacy in the shuffle model. We also propose a differentially oblivious shuffling protocol based on onion routing that requires only $O(n \log n)$ communication while tolerating any constant fraction of corrupted users. We show that for practical settings of the parameters, our protocol outperforms existing solutions to the problem in some settings.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Applied Cryptography and Network Security 2022
Differential privacy Onion routing
Contact author(s)
gordon @ gmu edu
jkatz2 @ gmail com
mliang5 @ gmu edu
jiayux @ uci edu
2022-06-15: revised
2021-09-21: received
See all versions
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.