ABSTRACT:

We consider the noise complexity of differentially private mechanisms in the setting where the user asks d linear queries non-interactively on a histogram of length n.

We show that the problem is characterized by two geometric parameters of a convex body associated with the set of queries. Using this connection we give upper and lower bounds on how much noise a mechanism must add in order to guarantee differential privacy. Our bounds are tight for random linear queries and they are nearly optimal for any set of linear queries assuming the truth of a deep conjecture from convex geometry known as the Hyperplane Conjecture.

Quantitatively, our result shows that when d is at most n it is necessary and sufficient to add total Euclidean error \Theta(min{d\sqrt{\log n},d\sqrt{d}}) to achieve differential privacy. The best previous upper bound (Laplacian mechanism) gives a bound of O(d\sqrt{d}), while the best known lower bound was \Omega(d). In contrast, our lower bound is strong enough to separate differential privacy from the notion of approximate differential privacy where an upper bound of O(d) can be achieved.

Joint work with Kunal Talwar.