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

TLDR

Dalenius (1977) argued that no individual's information should be learnable from a statistical database beyond what could be learned without the database, a principle that later motivated the development of differential privacy to formalize this privacy guarantee. The authors prove that a natural formalization of Dalenius’ goal cannot be achieved while maintaining database usefulness. They show that side information available to adversaries is the key obstacle, and that their impossibility result holds under general conditions, even threatening the privacy of individuals not present in the database.

Abstract

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.