|When:||Sunday, 19 December 2010, 17:20–18:55|
The talk presents recent results (from a paper at FOCS 2010) on
differential privacy in a distributed setting: two parties holding sensitive data would like to analyze the union of their data sets while preserving the privacy of the individuals whose data they hold.
The paper gives almost tight bounds on the accuracy of such analysis for the Hamming distance function. These bounds show the contrast between information theoretic and computational differential privacy in the two-party setting and also between the two-party and the client-server setting. The proof technique introduces a connection between differential privacy and deterministic extraction from independent Santha-Vazirani sources.
The talk is mostly based on the paper
The Limits of Two-Party Differential Privacy by Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar and Salil Vadhan (http://research.microsoft.com/apps/pubs/default.aspx?id=137029).
Basic background knowledge of information theory and probability theory can be useful.