nips nips2010 nips2010-175 nips2010-175-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Manas Pathak, Shantanu Rane, Bhiksha Raj
Abstract: As increasing amounts of sensitive personal information finds its way into data repositories, it is important to develop analysis mechanisms that can derive aggregate information from these repositories without revealing information about individual data instances. Though the differential privacy model provides a framework to analyze such mechanisms for databases belonging to a single party, this framework has not yet been considered in a multi-party setting. In this paper, we propose a privacy-preserving protocol for composing a differentially private aggregate classifier using classifiers trained locally by separate mutually untrusting parties. The protocol allows these parties to interact with an untrusted curator to construct additive shares of a perturbed aggregate classifier. We also present a detailed theoretical analysis containing a proof of differential privacy of the perturbed aggregate classifier and a bound on the excess risk introduced by the perturbation. We verify the bound with an experimental evaluation on a real dataset. 1
[1] Arvind Narayanan and Vitaly Shmatikov. De-anonymizing social networks. In IEEE Symposium on Security and Privacy, pages 173–187, 2009.
[2] Andrew Yao. Protocols for secure computations (extended abstract). In IEEE Symposium on Foundations of Computer Science, 1982.
[3] Jaideep Vaidya, Chris Clifton, Murat Kantarcioglu, and A. Scott Patterson. Privacy-preserving decision trees over vertically partitioned data. TKDD, 2(3), 2008.
[4] Jaideep Vaidya, Murat Kantarcioglu, and Chris Clifton. Privacy-preserving naive bayes classification. VLDB J, 17(4):879–898, 2008.
[5] Jaideep Vaidya, Hwanjo Yu, and Xiaoqian Jiang. Privacy-preserving svm classification. Knowledge and Information Systems, 14(2):161–178, 2008.
[6] Cynthia Dwork. Differential privacy. In International Colloquium on Automata, Languages and Programming, 2006.
[7] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, pages 265–284, 2006.
[8] Kamalika Chaudhuri and Claire Monteleoni. Privacy-preserving logistic regression. In Neural Information Processing Systems, pages 289–296, 2008.
[9] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In ACM Symposium on Theory of Computing, pages 75–84, 2007.
[10] Adam Smith. Efficient, differentially private point estimators. arXiv:0809.4794v1 [cs.CR], 2008.
[11] Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, 1999.
[12] Mikhail Atallah and Jiangtao Li. Secure outsourcing of sequence comparisons. International Journal of Information Security, 4(4):277–287, 2005.
[13] Michael Ben-Or, Shari Goldwasser, and Avi Widgerson. Completeness theorems for noncryptographic fault-tolerant distributed computation. In Proceedings of the ACM Symposium on the Theory of Computing, pages 1–10, 1988.
[14] Karthik Sridharan, Shai Shalev-Shwartz, and Nathan Srebro. Fast rates for regularized objectives. In Neural Information Processing Systems, pages 1545–1552, 2008.
[15] A. Frank and A. Asuncion. UCI machine learning repository, 2010.
[16] John Platt. Fast training of support vector machines using sequential minimal optimization. In Advances in Kernel Methods — Support Vector Learning, pages 185–208, 1999. 9