Paper 2016/721
Strong Hardness of Privacy from Weak Traitor Tracing
Lucas Kowalczyk, Tal Malkin, Jonathan Ullman, and Mark Zhandry
Abstract
A central problem in differential privacy is to accurately answer a large family $Q$ of statistical queries over a data universe $X$. A statistical query on a dataset $D \in X^n$ asks ``what fraction of the elements of $D$ satisfy a given predicate $p$ on $X$?'' Ignoring computational constraints, it is possible to accurately answer exponentially many queries on an exponential size universe while satisfying differential privacy (Blum et al., STOC'08). Dwork et al. (STOC'09) and Boneh and Zhandry (CRYPTO'14) showed that if both $Q$ and $X$ are of polynomial size, then there is an efficient differentially private algorithm that accurately answers all the queries. They also proved that if $Q$ and $X$ are both exponentially large, then under a plausible assumption, no efficient algorithm exists. We show that, under the same assumption, if either the number of queries or the data universe is of exponential size, then there is no differentially private algorithm that answers all the queries. Specifically, we prove that if oneway functions and indistinguishability obfuscation exist, then: 1) For every $n$, there is a family $Q$ of $\tilde{O}(n^7)$ queries on a data universe $X$ of size $2^d$ such that no $poly(n,d)$ time differentially private algorithm takes a dataset $D \in X^n$ and outputs accurate answers to every query in $Q$. 2) For every $n$, there is a family $Q$ of $2^d$ queries on a data universe $X$ of size $\tilde{O}(n^7)$ such that no $poly(n,d)$ time differentially private algorithm takes a dataset $D \in X^n$ and outputs accurate answers to every query in $Q$. In both cases, the result is nearly quantitatively tight, since there is an efficient differentially private algorithm that answers $\tilde{\Omega}(n^2)$ queries on an exponential size data universe, and one that answers exponentially many queries on a data universe of size $\tilde{\Omega}(n^2)$. Our proofs build on the connection between hardness results in differential privacy and traitortracing schemes (Dwork et al., STOC'09; Ullman, STOC'13). We prove our hardness result for a polynomial size query set (resp., data universe) by showing that they follow from the existence of a special type of traitortracing scheme with very short ciphertexts (resp., secret keys), but very weak security guarantees, and then constructing such a scheme.
Note: Changed constants in differential privacy requirement to match that of theorem.
Metadata
 Available format(s)
 Publication info
 Preprint. Minor revision.
 Keywords
 differential privacytraitortracingindistinguishability obfuscation
 Contact author(s)
 luke @ cs columbia edu
 History
 20180531: last of 2 revisions
 20160721: received
 See all versions
 Short URL
 https://ia.cr/2016/721
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/721, author = {Lucas Kowalczyk and Tal Malkin and Jonathan Ullman and Mark Zhandry}, title = {Strong Hardness of Privacy from Weak Traitor Tracing}, howpublished = {Cryptology ePrint Archive, Paper 2016/721}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/721}}, url = {https://eprint.iacr.org/2016/721} }