Noiseless Database Privacy

  • Raghav Bhaskar
  • Abhishek Bhowmick
  • Vipul Goyal
  • Srivatsan Laxman
  • Abhradeep Thakurta

Proceedings of the Seventeenth International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2011 |

Published by Lecture Notes in Computer Science

Diff erential Privacy (DP) has emerged as a formal, flexible framework for privacy protection, with a guarantee that is agnostic to auxiliary information and that admits simple rules for composition. Benefi ts notwithstanding, a major drawback of DP is that it provides noisy responses to queries, making it unsuitable for many applications. We propose a new notion called Noiseless Privacy that provides exact answers to queries, without adding any noise whatsoever. While the form of our guarantee is similar to DP, where the privacy comes from is very di fferent, based on statistical assumptions on the data and on restrictions to the auxiliary information available to the adversary. We present a first set of results for Noiseless Privacy of arbitrary Boolean-function queries and of linear Real-function queries, when data are drawn independently, from nearly-uniform and Gaussian distributions respectively. We also derive simple rules for composition under models of dynamically changing data.