On the Difficulties of Disclosure Prevention in Statistical Databases
or
The Case for Differential Privacy
Cynthia Dwork Moni Naor
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
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
Postscirpt, PDF. Slides:
ppt.
Related On-Line Papers:
- Cynthia Dwork, Krishnaram Kenthapadi,
Frank McSherry, Ilya Mironov and Moni Naor, Our Data, Ourselves: Privacy via
Distributed Noise Generation, Eurocrypt 2006.
Abstract, Postscript,
gzipped
Postscript, PDF
Back to: On-Line Publications, Recent Papers
Back Home