You are looking at a specific version 20210921:115418 of this paper. See the latest version.

Paper 2021/1257

Spreading the Privacy Blanket: Differentially Oblivious Shuffling for Differential Privacy

S. Dov Gordon and Jonathan Katz and 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
2022-06-15: revised
2021-09-21: received
See all versions
Short URL
https://ia.cr/2021/1257
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.