Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Computational Differential Privacy

Ilya Mironov, Omkant Pandey, Omer Reingold, and Salil Vadhan

Abstract

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. 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.

Details

Publication typeInproceedings
Published inAdvances in Cryptology—CRYPTO 2009
URLhttp://research.microsoft.com/users/mironov/papers/cdp.pdf
SeriesLecture Notes in Computer Science
PublisherSpringer
> Publications > Computational Differential Privacy