**Computational Complexity in Differential Privacy**

In this talk, I will describe how computational resource constraints can affect the achievability of differential privacy. We will consider both resource constraints on the curator (making privacy harder to achieve) and on the adversary (making privacy easier to achieve).

*Efficiency of the Curator: * With no computational constraints, Blum, Ligett, and Roth showed that it is possible to produce differentially private synthetic datasets that approximately preserve broad classes of statistics about the original dataset (including all marginals). But for computationally efficient curators, we will show that it is not possible to produce differentially private synthetic data, even for preserving 2-way marginals (under standard cryptographic assumptions). For non-synthetic data, we have a less complete understanding, but the general question has a close connection to an open problem about the existence of “traitor tracing schemes” in cryptography.

*Efficiency of the Adversary:* Constraining the resources of the adversary gives rise to computational analogues of the definitions of differential privacy. There are several different analogues, and we do not yet fully understand the relations between them. However, all of them provide a provable benefit over the standard information-theoretic notion of differential privacy, as we demonstrate with the example of 2-party protocols to estimate the Hamming distance of n-bit strings. With computational differential privacy, a constant additive error is sufficient, whereas with standard differential privacy roughly a \sqrt{n} error is required.

Based on joint works with Cynthia Dwork, Andrew McGregor, Ilya Mironov, Moni Naor, Omer Reingold, Guy Rothblum, Omkant Pandey, Toni Pitassi, Kunal Talwar, and Jon Ullman.

- Talk at
*IPAM Workshop on Statistical and Learning-Theoretic Challenges in Data Privacy,*February 22-26, 2010. (For audience of privacy experts.) [ppsx] - Talk at
*MIT Applied Math Colloquium,*April 11, 2011. (For general tcs audience, focuses on efficiency of curator.) [ppsx] - Talk at
*Microsoft Research New England,*May 11, 2011. (For general tcs audience, focuses on efficiency of adversary.) [ppsx] - See also papers The Complexity of Differentially Private Data Release: Efficient Algorithms and Hardness Results, Computational Differential Privacy, and PCPs and the Hardness of Generating Synthetic Data.