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.