Title:
Answering n^{2 + o(1)} Counting Queries with Differential Privacy is Hard

Abstract:
A central problem in differentially private data analysis is how to
design efficient algorithms capable of answering large numbers of
\emph{counting queries} on a sensitive database.  Counting queries of
the form ``What fraction of individual records in the database satisfy
the property q?''  We prove that if one-way functions exist, then
there is no algorithm that takes as input a database D in ({0,1}^d)^n,
and k = \tilde{\Theta}(n^2) arbitrary efficiently computable counting
queries, runs in time poly(d, n), and returns an approximate answer to
each query, while satisfying differential privacy.  We also consider
the complexity of answering ``simple'' counting queries, and make some
progress in this direction by showing that the above result holds even
when we require that the queries are computable by constant depth
(AC^0) circuits.

Our result is almost tight in the sense that nearly n^2 counting
queries can be answered efficiently while satisfying differential
privacy.  Moreover, super-polynomially many queries can be answered in
exponential time.

We prove our results by extending the connection between
differentially private counting query release and cryptographic
traitor-tracing schemes to the setting where the queries are given to
the sanitizer as input, and by constructing a traitor-tracing scheme
that is secure in this setting.