No free lunch in data privacy

Daniel Kifer, Ashwin Machanavajjhala

Research output: Chapter in Book/Report/Conference proceedingConference contribution

412 Scopus citations


Differential privacy is a powerful tool for providing privacy-preserving noisy query answers over statistical databases. It guarantees that the distribution of noisy query answers changes very little with the addition or deletion of any tuple. It is frequently accompanied by popularized claims that it provides privacy without any assumptions about the data and that it protects against attackers who know all but one record. In this paper we critically analyze the privacy protections offered by differential privacy. First, we use a no-free-lunch theorem, which defines non-privacy as a game, to argue that it is not possible to provide privacy and utility without making assumptions about how the data are generated. Then we explain where assumptions are needed. We argue that privacy of an individual is preserved when it is possible to limit the inference of an attacker about the participation of the individual in the data generating process. This is different from limiting the inference about the presence of a tuple (for example, Bob's participation in a social network may cause edges to form between pairs of his friends, so that it affects more than just the tuple labeled as "Bob"). The definition of evidence of participation, in turn, depends on how the data are generated - this is how assumptions enter the picture. We explain these ideas using examples from social network research as well as tabular data for which deterministic statistics have been previously released. In both cases the notion of participation varies, the use of differential privacy can lead to privacy breaches, and differential privacy does not always adequately limit inference about participation.

Original languageEnglish (US)
Title of host publicationProceedings of SIGMOD 2011 and PODS 2011
PublisherAssociation for Computing Machinery
Number of pages12
ISBN (Print)9781450306614
StatePublished - 2011
Event2011 ACM SIGMOD and 30th PODS 2011 Conference - Athens, Greece
Duration: Jun 12 2011Jun 16 2011

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078


Other2011 ACM SIGMOD and 30th PODS 2011 Conference

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems


Dive into the research topics of 'No free lunch in data privacy'. Together they form a unique fingerprint.

Cite this