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.
Category / Keywords: anonymity, privacy, differential privacy Publication Info: Asiacrypt 2011. This is the full and expanded version. Date: received 9 Sep 2011, last revised 14 Jun 2012 Contact author: rbhaskar at microsoft com Available format(s): PDF | BibTeX Citation Note: Full version with all proofs. Version: 20120614:134226 (All versions of this report) Short URL: ia.cr/2011/487 Discussion forum: Show discussion | Start new discussion