December – 2008 ^January

We consider private data analysis in the setting in which a trusted and trustworthy curator, having obtained a large data set containing private information, releases to the public a ``sanitization'' of the data set that simultaneously protects the privacy of the individual contributors of data and offers utility to the data analyst. We focus on the case where the process is non-interactive; once the sanitization has been released the original data and the curator play no further role.

Blum et al. [STOC '08] showed a remarkable result: for any collection of counting predicate queries, the exponential mechanism of McSherry and Talwar [FOCS '07] can be used to (inefficiently) generate a synthetic data set that maintains approximately correct fractional counts for all of the queries, while ensuring a strong privacy guarantee, known as differential privacy.

In this work we investigate the computational complexity of such non-interactive privacy mechanisms, mapping the boundary between feasibility and infeasibility. We show:

1. For any polynomial-size query set C and polynomial-size data universe there is an efficient algorithm for generating a privacy-preserving synthetic data-set that maintains approximate fractional counts, even when the size of the original dataset is sub-polynomial in |C|.

2. When either the query set or the data universe are super-polynomial, assuming one-way functions exist, there is no efficient general method for releasing a privacy-preserving synthetic data-set that maintains approximate fractional counts. In particular, this is a case where the exponential mechanism cannot, in general, be implemented efficiently.

3. Turning to the potentially easier problem of privately generating an arbitrary data structure (not necessarily synthetic data) from which it is possible to approximate counts for a given concept, there is a tight connection between hardness of sanitization and the existence of traitor tracing schemes, methods of content distribution in which keys are assigned to subscribers in a way that given any useful ``pirate'' decoding box, constructed by a coalition of malicious subscribers, it is possible to identify at least one of them.

Joint work with Cynthia Dwork, Moni naor, Omer Reingold and Salil Vadhan.

I will discuss a notion of privacy called *differential privacy* in conjunction with *learning problems*, and give a complexity-theoretic classification of learning problems that can be efficiently solved in a differentially private manner.

Roughly speaking, the challenge in constructing private learning algorithms is that the outcome should depend very weakly on each of the specific examples. Interestingly, it happens that two of the main models considered in computational learning theory – PAC and SQ – exactly correspond to Imposing restrictions on the way private information is distributed, and on interaction. I will discuss this correspondence, and also issues of efficiency of private learning, and a few of the open problems related to private learning.

The talk with be self-contained.

Joint work with Shiva Kasiviswanathan, Homin Lee, Sofya Raskhodnikova, and Adam Smith, FOCS 2008.