Main Article Content
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.
Copyright is retained by the authors. By submitting to this journal, the author(s) license the article under the Creative Commons License – Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0), unless choosing a more lenient license (for instance, public domain). For situations not allowed under CC BY-NC-ND, short sections of text, not to exceed two paragraphs, may be quoted without explicit permission provided that full credit, including © notice, is given to the source.
Authors of articles published by the journal grant the journal the right to store the articles in its databases for an unlimited period of time and to distribute and reproduce the articles electronically.