Differential Privacy
đź“ś Abstract
In 1977 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 formalization of Dalenius’ goal along the lines of semantic security cannot be achieved. Contrary to intuition, a variant of the result threatens the privacy even of someone not in the database. This state of affairs suggests a new measure, differential privacy, which, intuitively, captures the increased risk to one’s privacy incurred by participating in a database. The techniques developed in a sequence of papers [8, 13, 3], culminating in those described in [12], can achieve any desired level of privacy under this measure. In many cases, extremely accurate information about the database can be provided while simultaneously ensuring very high levels of privacy.
✨ Summary
Summary
The paper examines how to define privacy for statistical and general-purpose data analysis when an adversary may possess substantial auxiliary information. It first shows that a strong, semantic-security-like requirement—ensuring that database access reveals nothing about an individual that could not otherwise be learned—is impossible to satisfy in useful statistical databases. The impossibility can affect people who are not present in the database, because auxiliary information can combine with aggregate database outputs to reveal sensitive facts.
The paper therefore introduces ε-differential privacy, a relative privacy guarantee based on neighboring data sets that differ in one participant. A randomized mechanism satisfies ε-differential privacy when the probability of every possible output event changes by at most a multiplicative factor of exp(ε) between neighboring data sets. This definition limits the additional risk caused by an individual’s participation while still permitting aggregate information to be released. The guarantee extends to groups, with privacy loss growing approximately linearly in the group size in the exponent.
The paper also presents a construction for achieving differential privacy by adding independent symmetric exponential noise to query answers. The required noise is calibrated to the query’s global L1-sensitivity, defined as the largest L1 change in the query output caused by adding or removing one data element. The same approach handles vector-valued queries, histograms, complex database functions, and adaptively selected sequences of queries, provided the mechanism is calibrated to the maximum sensitivity among the possible queries. A key observation is that histogram queries can have low overall sensitivity even when they contain many coordinates, allowing substantially less noise than treating each histogram cell as an independent query.
The impossibility proof uses randomness extractors and fuzzy extractors to show that useful released information can act as a one-time pad for auxiliary information, allowing an adversary with database access to recover a privacy breach that a simulator without such access cannot recover. This establishes why absolute disclosure prevention is unattainable under the paper’s utility assumptions and motivates the relative-risk formulation of differential privacy.
Influence
The paper formalized differential privacy as a central framework for privacy-preserving statistical analysis and became a foundational reference for subsequent work, including surveys and research on statistical estimation, privacy semantics, composition, machine learning, and practical mechanisms. The related 2010 survey by Dwork and Smith explicitly reviews the definition and subsequent results in differentially private statistics. (doi.org)
The framework also influenced deployed privacy systems. Apple describes its products as using local differential privacy to collect aggregate insights while perturbing data on users’ devices. (apple.com) The U.S. Census Bureau adopted a differential-privacy-based Disclosure Avoidance System for the 2020 Census, describing it as a formal method for balancing disclosure risk and statistical accuracy. (census.gov) The paper’s publication and conference metadata are confirmed by Microsoft Research and the author’s publication record. (microsoft.com)