Paper 2015/1090

Do Distributed Differentially-Private Protocols Require Oblivious Transfer?

Vipul Goyal, Dakshita Khurana, Ilya Mironov, Omkant Pandey, and Amit Sahai

Abstract

We study the cryptographic complexity of two-party differentially-private protocols for a large natural class of boolean functionalities. Information theoretically, McGregor et al. [FOCS 2010] and Goyal et al. [Crypto 2013] demonstrated several functionalities for which the maximal possible accuracy in the distributed setting is significantly lower than that in the client-server setting. Goyal et al. [Crypto 2013] further showed that ``highly accurate'' protocols in the distributed setting for any non-trivial functionality in fact imply the existence of one-way functions. However, it has remained an open problem to characterize the exact cryptographic complexity of this class. In particular, we know that semi-honest oblivious transfer helps obtain optimally accurate distributed differential privacy. But we do not know whether the reverse is true. We study the following question: Does the existence of optimally accurate distributed differentially private protocols for any class of functionalities imply the existence of oblivious transfer? We resolve this question in the affirmative for the class of boolean functionalities that contain an XOR embedded on adjacent inputs. - We construct a protocol implementing oblivious transfer from any optimally accurate, distributed differentially private protocol for any functionality with a boolean XOR embedded on adjacent inputs. - While the previous result holds for optimally accurate protocols for any privacy parameter \epsilon > 0, we also give a reduction from oblivious transfer to distributed differentially private protocols computing XOR, for a constant small range of non-optimal accuracies and a constant small range of values of privacy parameter \epsilon. At the heart of our techniques is an interesting connection between optimally-accurate two-party protocols for the XOR functionality and noisy channels, which were shown by Crepeau and Kilian [FOCS 1988] to be sufficient for oblivious transfer.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Differentially Private ProtocolsOblivious TransferNoisy ChannelsCryptographic Completeness
Contact author(s)
dakshita @ cs ucla edu
History
2015-11-10: received
Short URL
https://ia.cr/2015/1090
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1090,
      author = {Vipul Goyal and Dakshita Khurana and Ilya Mironov and Omkant Pandey and Amit Sahai},
      title = {Do Distributed Differentially-Private Protocols Require Oblivious Transfer?},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1090},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1090}},
      url = {https://eprint.iacr.org/2015/1090}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.