Computational Differential Privacy


Ilya Mironov, Omkant Pandey, Omer Reingold, and Salil Vadhan. 2009. “Computational Differential Privacy.” In Advances in Cryptology–-CRYPTO `09, 5677: 126–142. Santa Barbara, CA: Springer-Verlag. Date Presented: 16–20 August. Springer Link


The definition of differential privacy has recently emerged as a leading standard of privacy guarantees for algorithms on statistical databases. We offer several relaxations of the definition which require privacy guarantees to hold only against efficient—i.e., computationally-bounded—adversaries. We establish various relationships among these notions, and in doing so, we observe their close connection with the theory of pseudodense sets by Reingold et al.[1]. We extend the dense model theorem of Reingold et al. to demonstrate equivalence between two definitions (indistinguishability- and simulatability-based) of computational differential privacy. Our computational analogues of differential privacy seem to allow for more accurate constructions than the standard information-theoretic analogues. In particular, in the context of private approximation of the distance between two vectors, we present a differentially-private protocol for computing the approximation, and contrast it with a substantially more accurate protocol that is only computationally differentially private.

Acknowledgements: This paper was supported, in part, by US-Israel BSF grant 2006060, Microsoft Research, and Harvard's Center for Research on Computation and Society.
Last updated on 01/05/2017