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
of statistical queries over a data universe . A statistical query
on a dataset asks ``what fraction of the elements of satisfy a given
predicate on ?'' 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 and are of polynomial size,
then there is an efficient differentially private algorithm that
accurately answers all the queries. They also proved that if and 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 one-way functions and
indistinguishability obfuscation exist, then:
1) For every , there is a family of queries on a data universe of size such that no time differentially private algorithm takes a dataset and outputs accurate answers to every query in .
2) For every , there is a family of queries on a data universe of size such that no time differentially private algorithm takes a dataset and outputs accurate answers to every query in .
In both cases, the result is nearly quantitatively tight, since there
is an efficient differentially private algorithm that answers
queries on an exponential size data universe,
and one that answers exponentially many queries on a data universe of
size .
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.
Note: Changed constants in differential privacy requirement to match that of theorem.