International Association
for Cryptologic Research

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.