On the Difficulties of Disclosure Prevention in Statistical Databases
The Case for Differential Privacy

Cynthia Dwork        Moni Naor


In 1977 Tore Dalenius articulated a desideratum for statistical databases:  nothing about an individual should be learnable from the database that cannot be learned without access to the database. We give a general impossibility result showing that a natural formalization of Dalenius' goal along the lines of semantic security for cryptosystems cannot be achieved if the database is useful. The key obstacle is the side information that may be available to an adversary. Our results hold under very general conditions regarding the database, the notion of privacy violation, and the notion of utility.

Contrary to intuition, a variant of the result threatens the privacy even of someone not in the database. This state of affairs motivated the notion of differential privacy a strong ad omnia privacy which, intuitively, captures the increased risk to one's privacy incurred by participating in a database.

The paper: Postscript, gzipped PostscirptPDF. Slides: ppt.

Related On-Line Papers:

Back to: On-Line PublicationsRecent Papers

Back Home