Data Management

Computational Differential Privacy

Download Now Free registration required

Executive Summary

The definition of differential privacy has recently emerged as a leading standard of privacy guarantees for algorithms on statistical databases. The authors offer several relaxations of the definition which require privacy guarantees to hold only against efficient - i.e., computationally bounded - adversaries. They establish various relationships among these notions, and in doing so, they observe their close connection with the theory of pseudodense sets by Reingold et al.. They extend the dense model theorem of Reingold et al. to demonstrate equivalence between two definitions (Indistinguishability- and simulatability-based) of computational differential privacy. The computational analogues of differential privacy seem to allow for more accurate constructions than the standard information-theoretic analogues.

  • Format: PDF
  • Size: 198.18 KB