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.
Category / Keywords: foundations / Differentially Private Protocols, Oblivious Transfer, Noisy Channels, Cryptographic Completeness Date: received 9 Nov 2015 Contact author: dakshita at cs ucla edu Available format(s): PDF | BibTeX Citation Version: 20151110:173043 (All versions of this report) Short URL: ia.cr/2015/1090 Discussion forum: Show discussion | Start new discussion