City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Two-Party Differential Privacy and Deterministic Extraction from Santha-Vazirani Sources (Г. Ярославцев, Pennsylvania State University)
Seminar on Computer Science

What: Lecture
When: Sunday, 19 December 2010, 17:20–18:55
Where: ПОМИ РАН

Description

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.

Video