You are looking at a specific version 20160730:020900 of this paper. See the latest version.

Paper 2016/721

Strong Hardness of Privacy from Weak Traitor Tracing

Lucas Kowalczyk and Tal Malkin and Jonathan Ullman and Mark Zhandry

Abstract

Despite much study, the computational complexity of differential privacy remains poorly understood. In this paper we consider the computational complexity of accurately answering a family $Q$ of statistical queries over a data universe $X$ under differential privacy. 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$?'' 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, and if both $Q$ and $X$ are exponential size, 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 one-way 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 $\mathrm{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 $\mathrm{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 traitor-tracing 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 traitor-tracing scheme with very short ciphertexts (resp., secret keys), but very weak security guarantees, and then constructing such a scheme.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
differential privacytraitor-tracingindistinguishability obfuscation
Contact author(s)
jullman @ ccs neu edu
History
2018-05-31: last of 2 revisions
2016-07-21: received
See all versions
Short URL
https://ia.cr/2016/721
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.