Paper 2011/487

Noiseless Database Privacy

Raghav Bhaskar, Abhishek Bhowmick, Vipul Goyal, Srivatsan Laxman, and Abhradeep Thakurta


The notion of differential privacy has recently emerged as a gold standard in the field of database privacy. While this notion has the benefit of providing concrete theoretical privacy (compared to various previous ad-hoc approaches), the major drawback is that the mechanisms needs to inject some noise the output limiting its applicability in many settings. In this work, we initiate the study of a new notion of privacy called \emph{noiseless privacy}. The (very natural) idea we explore is to exploit the entropy already present in the database and substitute that in the place of external noise to the output. The privacy guarantee we provide is very similar to DP but where that guarantee ``comes from" is very different in the two cases. While differential privacy focuses on generality, we make assumptions about the database distribution, the auxiliary information which the adversary may have and the type of queries. This allows us to obtain ``privacy for free" whenever the underlying assumptions are satisfied. In this work, we first formalize the notion of noiseless privacy, introduce two definitions and show that they are equivalent. We then study certain types of boolean and real queries and show natural (and well understood) conditions under which noiseless privacy can be obtained with good parameters. We also study the issue of composability and introduce models under which it can be achieved in the noiseless privacy framework.

Note: Full version with all proofs.

Available format(s)
Publication info
Published elsewhere. Asiacrypt 2011. This is the full and expanded version.
anonymityprivacydifferential privacy
Contact author(s)
rbhaskar @ microsoft com
2012-06-14: last of 5 revisions
2011-09-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Raghav Bhaskar and Abhishek Bhowmick and Vipul Goyal and Srivatsan Laxman and Abhradeep Thakurta},
      title = {Noiseless Database Privacy},
      howpublished = {Cryptology ePrint Archive, Paper 2011/487},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.