Consider a trusted data collection center that wishes to release global statistics about a population without breaching individuals'
privacy. A line of research originating with Dinur and Nissim (PODS'03) set out meaningful definitions of privacy in this context, and constructed protocols for revealing "low-sensitivity" statistics with relatively little noise.
This talk will discuss impossibility results for this model, which separate the power of several classes of protocols. I'll consider two valuable resources in private data analysis protocols: *interaction* and *locality*. One can show that interactive, non-local protocols are incomparable to local, interactive protocols (this is follows from two separate impossibility results). The results establish a clear picture about the relative power of these resources. I'll explain the ideas behind the proofs and speculate about future research directions they suggest.
Based on joint work with Kobbi Nissim and Enav Weinreb. Some results appeared in TCC '06, joint with Cynthia Dwork, Frank McSherry and Kobbi Nissim.
Audio (MP3 File, Podcast Ready)
Copyright. All Rights Reserved.