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

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 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 15, 16, a strong ad omnia privacy which, intuitively, captures the increased risk to one’s privacy incurred by participating in a database.