"On the Complexity of Differentially Private Data Release" (CRCS Lunch Seminar)

Presentation Date: 

Wednesday, April 29, 2009

CRCS Privacy and Security Lunch Seminar

Date: Wednesday, April 29, 2009
Speaker: Guy Rothblum
Title: On the Complexity of Differentially Private Data Release: Efficient Algorithms and Hardness Results

Abstract: We consider private 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.

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

Bio: Guy Rothblum is a Ph.D. candidate at MIT. His research focuses on foundational cryptography. Recently he is especially interested in studying methods for protecting individual’s privacy, for reliably delegating computations and for obfuscation and software protection.