Paper 2017/1107

Hardness of Non-Interactive Differential Privacy from One-Way Functions

Lucas Kowalczyk
Tal Malkin
Jonathan Ullman
Daniel Wichs
Abstract

A central challenge in differential privacy is to design computationally efficient non-interactive algorithms that can answer large numbers of statistical queries on a sensitive dataset. That is, we would like to design a differentially private algorithm that takes a dataset $D \in X^n$ consisting of some small number of elements $n$ from some large data universe $X$, and efficiently outputs a summary that allows a user to efficiently obtain an answer to any query in some large family $Q$. Ignoring computational constraints, this problem can be solved even when $X$ and $Q$ are exponentially large and $n$ is just a small polynomial; however, all algorithms with remotely similar guarantees run in exponential time. There have been several results showing that, under the strong assumption of indistinguishability obfuscation (iO), no efficient differentially private algorithm exists when $X$ and $Q$ can be exponentially large. However, there are no strong separations between information-theoretic and computationally efficient differentially private algorithms under any standard complexity assumption. In this work we show that, if one-way functions exist, there is no general purpose differentially private algorithm that works when $X$ and $Q$ are exponentially large, and $n$ is an arbitrary polynomial. In fact, we show that this result holds even if $X$ is just subexponentially large (assuming only polynomially-hard one-way functions). This result solves an open problem posed by Vadhan in his recent survey.

Note: Update on 5/22/24: We thank Mark Zhandry for pointing out a bug in our previous construction of two-message functional encryption (section 6) which appeared in the CRYPTO 2018 version of the paper, and suggesting the fix that we implemented in the current updated version. While the construction is more complex, the final results and parameters remain unchanged.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in CRYPTO 2018
Keywords
differential privacyone-way functionstraitor tracingfunctional encryption
Contact author(s)
danwichs @ gmail com
History
2024-05-23: last of 3 revisions
2017-11-20: received
See all versions
Short URL
https://ia.cr/2017/1107
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1107,
      author = {Lucas Kowalczyk and Tal Malkin and Jonathan Ullman and Daniel Wichs},
      title = {Hardness of Non-Interactive Differential Privacy from One-Way Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/1107},
      year = {2017},
      url = {https://eprint.iacr.org/2017/1107}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.