Title: Privacy-Preserving Data Release: Efficient Algorithms and Hardness Results

Speaker:  Guy Rothblum, IAS 
 
Abstract: 

We consider privacy-preserving data analysis in the setting in which a
trusted and trustworthy curator, having obtained a data set containing
sensitive information, releases to the public a ``sanitization'' of
the data set. The goal is for the sanitization to both protect the
privacy of the individual contributors of data and offer aggregate
statistical utility to a data analyst.

In a remarkable recent result, Blum et al. [STOC '08] showed that it
is theoretically possible (in exponential time) to generate a
synthetic data-set that allows rich statistical analysis, while
ensuring a strong privacy guarantee known as differential privacy.

We investigate the possibility of *efficiently* achieving rich
statistical data analysis that protects the privacy of individuals.
The main result we will present is the first efficient mechanism that
achieves rich general privacy-preserving data analysis by answering
large sets of predicate counting queries. We will also show strong
lower bounds based on standard cryptographic hardness assumptions.

Based on joint work with Cynthia Dwork, Moni Naor, Omer Reingold and
Salil Vadhan.