Paper 2016/820

Separating Computational and Statistical Differential Privacy in the Client-Server Model

Mark Bun, Yi-Hsiu Chen, and Salil Vadhan


Differential privacy is a mathematical definition of privacy for statistical data analysis. It guarantees that any (possibly adversarial) data analyst is unable to learn too much information that is specific to an individual. Mironov et al.~(CRYPTO 2009) proposed several computational relaxations of differential privacy (CDP), which relax this guarantee to hold only against computationally bounded adversaries. Their work and subsequent work showed that CDP can yield substantial accuracy improvements in various multiparty privacy problems. However, these works left open whether such improvements are possible in the traditional client-server model of data analysis. In fact, Groce, Katz and Yerukhimovich~(TCC 2011) showed that, in this setting, it is impossible to take advantage of CDP for many natural statistical tasks. Our main result shows that, assuming the existence of sub-exponentially secure one-way functions and 2-message witness indistinguishable proofs (zaps) for NP, that there is in fact a computational task in the client-server model that can be efficiently performed with CDP, but is infeasible to perform with information-theoretic differential privacy.

Note: Fixed some typos.

Available format(s)
Publication info
Published by the IACR in TCC 2016
differential privacycomputational differential privacywitness indistinguishability
Contact author(s)
yihsiuchen @ g harvard edu
2016-08-28: received
Short URL
Creative Commons Attribution


      author = {Mark Bun and Yi-Hsiu Chen and Salil Vadhan},
      title = {Separating Computational and Statistical Differential Privacy in the Client-Server Model},
      howpublished = {Cryptology ePrint Archive, Paper 2016/820},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.