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

by Jonathan Ullman

#### Oded's comments

The abstract does a good job in explaining the work and its contents.

#### The original abstract

A central problem in differentially private data analysis is how to design
efficient algorithms capable of answering large numbers of 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 = O(n^2 log n)$ 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 (AC0) 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.

Back to
list of Oded's choices.