Paper 2021/1257

Spreading the Privacy Blanket: Differentially Oblivious Shuffling for Differential Privacy

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

Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
Differential privacyProtocolsOnion routing
Contact author(s)
gordon @ gmu edu
jkatz2 @ gmail com
mliang5 @ gmu edu
jiayux @ uci edu
History
2021-09-21: received
Short URL
https://ia.cr/2021/1257
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1257,
      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{https://eprint.iacr.org/2021/1257}},
      url = {https://eprint.iacr.org/2021/1257}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.