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 …

Over the past five years a new approach to privacy-preserving data analysis has born fruit
[13, 18, 7, 19, 5, 37, 35, 8, 32]. This approach differs from much (but not all!) of the related
literature in the statistics, databases, theory, and cryptography communities, in that a formal
and ad omnia privacy guarantee is defined, and the data analysis techniques presented are
rigorously proved to satisfy the guarantee. The key privacy guarantee that has emerged is
differential privacy. Roughly speaking, this ensures that (almost, and quantifiably) no risk is …