A learning theory approach to non-interactive database privacy

ABSTRACT

We demonstrate that, ignoring computational constraints, it is possible to release privacy-preserving databases that are useful for all queries over a discretized domain from any given concept class with polynomial VC-dimension. We show a new lower bound for releasing databases that are useful for halfspace queries over a continuous domain. Despite this, we give a privacy-preserving polynomial time algorithm that releases information useful for all halfspace queries, for a slightly relaxed definition of usefulness. Inspired by learning theory, we introduce a new notion of data privacy, which we call distributional privacy, and show that it is strictly stronger than the prevailing privacy notion, differential privacy.

REFERENCES

• 1: Martin M. Anthony , Peter Bartlett, Learning in Neural Networks: Theoretical Foundations, Cambridge University Press, New York, NY, 1999
• 2: Maria-Florina Balcan , Avrim Blum , Santosh Vempala, Kernels as features: On kernels, margins, and low-dimensional mappings, Machine Learning, v.65 n.1, p.79-94, October 2006 [doi>10.1007/s10994-006-7550-1]
• 3: Boaz Barak , Kamalika Chaudhuri , Cynthia Dwork , Satyen Kale , Frank McSherry , Kunal Talwar, Privacy, accuracy, and consistency too: a holistic solution to contingency table release, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265569]
• 4: Avrim Blum , Cynthia Dwork , Frank McSherry , Kobbi Nissim, Practical privacy: the SuLQ framework, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065184]
• 5: S. Dasgupta and A. Gupta. An elementary proof of the Johnson-Lindenstrauss Lemma. International Computer Science Institute, Technical Report, pages 99--006, 1999.
• 6: Irit Dinur , Kobbi Nissim, Revealing information while preserving privacy, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.202-210, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773173]
• 7: C. Dwork. Differential privacy. Proc. ICALP, 2006.
• 8: C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our Data, Ourselves: Privacy via Distributed Noise Generation. Proceedings of Advances in CryptologyEurocrypt 2006, pages 486--503, 2006.
• 9: C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. Proceedings of the 3rd Theory of Cryptography Conference, pages 265--284, 2006.
• 10: Cynthia Dwork , Frank McSherry , Kunal Talwar, The price of privacy and the limits of LP decoding, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250804]
• 11: C. Dwork and K. Nissim. Privacy-preserving datamining on vertically partitioned databases. Proc. CRYPTO, pages 528--544, 2004.
• 12: Alexandre Evfimievski , Johannes Gehrke , Ramakrishnan Srikant, Limiting privacy breaches in privacy preserving data mining, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.211-222, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773174]
• 13: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 14: Shiva Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? http://arxiv.org/abs/0803.0924v1.
• 15: Frank McSherry , Kunal Talwar, Mechanism Design via Differential Privacy, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.94-103, October 21-23, 2007 [doi>10.1109/FOCS.2007.41]
• 16: Kobbi Nissim , Sofya Raskhodnikova , Adam Smith, Smooth sensitivity and sampling in private data analysis, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250803]
• 17: Vibhor Rastogi , Dan Suciu , Sungho Hong, The boundary between privacy and utility in data publishing, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 18: A. J. Smola and B. Scholkopf. Learning with Kernels. MIT Press, 2002.
• 19: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Algorithms, Security, Theory

Keywords:
learning theory, non-interactive database privacy