Black-box separations for differentially private protocols

Dakshita Khurana, Hemanta K. Maji, Amit Sahai

Research output: Contribution to journalConference articlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)386-405
Number of pages20
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
StatePublished - Jan 1 2014
Externally publishedYes
Event20th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2014 - Kaoshiung, Taiwan, Province of China
Duration: Dec 7 2014Dec 11 2014


  • Black-box Separation
  • Computational Complexity
  • Differentially Private Protocols
  • Key-agreement Protocols
  • Random Oracle

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Black-box separations for differentially private protocols'. Together they form a unique fingerprint.

Cite this