Eastern Great Lakes Theory Workshop Talk

The Limits of Two Party Differential Privacy

Toniann Pitassi, University of Toronto

Saturday, October 9, 1:30-2:30pm

ABSTRACT

We study differential privacy in a distributed setting where two or more parties wish to perform analysis of their joint data while preserving privacy for all datasets. Our main results arestrong lower bounds on the accuracy of such data analyses, both for specific natural functions (such as Hamming distance) and for other functions as well. Our bounds expose a a sharp contrast between the two party setting and the simpler client-serversetting. In addition, our results imply a dramatic gap between the accuracy that can be obtained by differentially private data analysis versus the accuracy obtainable when privacy is relaxed to be a computational variant of differential privacy.

Our proofs techniques reveal new connections with several fundamental concepts in complexity theory, including deterministic extraction from Santha-Vazirani sources, as well as connections to fundamental concepts in communication complexity such as information content and low communication/discrepancy.

This is joint work with Andrew McGregor, Ilya Mironov, Omer Reingold, Kunal Talwar and Salil Vadhan.

Speaker Bio

< Schedule < EaGL-III homepage