Black-Box Separations for Differentially Private Protocols

We study the maximal achievable accuracy of distributed differentially private protocols for a large natural class of boolean functions, in the computational setting.

In the information theoretic model, McGregor et al.[FOCS 2010] and Goyal et al.[CRYPTO 2013] demonstrate several functionalities whose differentially private computation results in much lower accuracies in the distributed setting, as compared to the client-server setting.

We explore lower bounds on the computational assumptions under which this accuracy gap can possibly be reduced for two-party boolean output functions. In the distributed setting, it is possible to achieve optimal accuracy, i.e. the maximal achievable accuracy in the client-server setting, for any function, if a semi-honest secure protocol for oblivious transfer exists. However, we show the following strong impossibility results:

For

any

general boolean function and fixed level of privacy, the maximal achievable accuracy of any (fully) black-box construction based on existence of key-agreement protocols is at least a constant smaller than optimal achievable accuracy. Since key-agreement protocols imply the existence of one-way functions, this separation also extends to one-way functions.

Our results are tight for the

AND

and

XOR

functions. For

AND

, there exists an accuracy threshold such that any accuracy up to the threshold can be information theoretically achieved; while no (fully) black-box construction based on existence of key-agreement can achieve accuracy beyond this threshold. An analogous statement is also true for

XOR

(albeit with a different accuracy threshold).

Our results build on recent developments in black-box separation techniques for functions with private input [1,16,27,28]; and translate information theoretic impossibilities into black-box separation results.