Two-Party Differential Privacy and Deterministic Extraction from Santha-Vazirani Sources

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.

Basic background knowledge of information theory and probability theory can be useful.

Страница лекции на сайте Computer Science клуба