Privacy-preserving decision trees over vertically partitioned data

ABSTRACT

Privacy and security concerns can prevent sharing of data, derailing data-mining projects. Distributed knowledge discovery, if done correctly, can alleviate this problem. We introduce a generalized privacy-preserving variant of the ID3 algorithm for vertically partitioned data distributed over two or more parties. Along with a proof of security, we discuss what would be necessary to make the protocols completely secure. We also provide experimental results, giving a first demonstration of the practical complexity of secure multiparty computation-based data mining.

REFERENCES

• 1: Dakshi Agrawal , Charu C. Aggarwal, On the design and quantification of privacy preserving data mining algorithms, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.247-255, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375602]
• 2: Rakesh Agrawal , Alexandre Evfimievski , Ramakrishnan Srikant, Information sharing across private databases, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872771]
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 4: Atallah, M. J., Elmongui, H. G., Deshpande, V., and Schwarz, L. B. 2003. Secure supply-chain protocols. In Proceedings of the IEEE International Conference on E-Commerce, Newport Beach, CA. IEEE Computer Society Press, 293--302.
• 5: Blake, C. and Merz, C. 1998. UCI repository of machine learning databases. http://citeseer.comp.nus.edu.sg/context/123650/0.
• 6: Henri Cohen , Atsuko Miyaji , Takatoshi Ono, Efficient Elliptic Curve Exponentiation Using Mixed Coordinates, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.51-65, October 18-22, 1998
• 7: Cox, M. J., Engelschall, R. S., Henson, S., and rie, B. L. 1998--2005. The OpenSSL Toolkit.
• 8: Ronald Cramer , Ivan Damgård , Jesper Buus Nielsen, Multiparty Computation from Threshold Homomorphic Encryption, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.280-299, May 06-10, 2001
• 9: Damgard, I., Jurik, M., and Nielsen, J. 2003. A generalization of Paillier's public-key system with applications to electronic voting.
• 10: Wenliang Du , Mikhail J. Atallah, Secure multi-party computation problems and their applications: a review and open problems, Proceedings of the 2001 workshop on New security paradigms, September 10-13, 2001, Cloudcroft, New Mexico [doi>10.1145/508171.508174]
• 11: Wenliang Du , Zhijun Zhan, Building decision tree classifier on private data, Proceedings of the IEEE international conference on Privacy, security and data mining, p.1-8, December 01, 2002, Maebashi City, Japan
• 12: Duda, R. and Hart, P. E. 1973. Pattern Classification and Scene Analysis. John Wiley & Sons, Hoboken, NJ.
• 13: Alexandre Evfimievski , Ramakrishnan Srikant , Rakesh Agrawal , Johannes Gehrke, Privacy preserving mining of association rules, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775080]
• 14: Evidence-Based Medicine Working Group. 1992. Evidence-Based medicine. A new approach to teaching the practice of medicine. J. Amer. Medical Assoc. 268, 17 (Nov.), 2420--2425.
• 15: Freedman, M. J., Nissim, K., and Pinkas, B. 2004. Efficient private matching and set intersection. In Proceedings of the 23rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, International Association for Cryptologic Research (IACR), Interlaken, Switzerland. Springer, 1--19.
• 16: Goethals, B., Laur, S., Lipmaa, H., and Mielikäinen, T. 2004. On secure scalar product computation for privacy-preserving data mining. In Proceedings of the 7th Annual International Conference in Information Security and Cryptology (ICISC), New York, C. Park and S. Chee, Eds. vol. 3506, Springer, 104--120.
• 17: Goldreich, O. 2004. General Cryptographic Protocols, Vol. 2. In The Foundations of Cryptography, vol. 2. Cambridge University Press, Cambridge, UK, 599--764.
• 18: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 19: Zhengli Huang , Wenliang Du , Biao Chen, Deriving private information from randomized data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066163]
• 20: Geetha Jagannathan , Rebecca N. Wright, Privacy-preserving distributed k-means clustering over arbitrarily partitioned data, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081942]
• 21: Kantarcioglu, M. and Clifton, C. 2002. Privacy-Preserving distributed mining of association rules on horizontally partitioned data. In Proceedings of the ACM SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery (DMKD), Madison, WI. ACM Press, New York, 24--31.
• 22: Murat Kantarcioglu , Jaideep Vaidya, An architecture for privacy-preserving mining of client information, Proceedings of the IEEE international conference on Privacy, security and data mining, p.37-42, December 01, 2002, Maebashi City, Japan
• 23: Murat Kantarcioglu , Chris Clifton, Privacy-Preserving Distributed Mining of Association Rules on Horizontally Partitioned Data, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1026-1037, September 2004 [doi>10.1109/TKDE.2004.45]
• 24: Hillol Kargupta , Souptik Datta , Qi Wang , Krishnamoorthy Sivakumar, On the Privacy Preserving Properties of Random Data Perturbation Techniques, Proceedings of the Third IEEE International Conference on Data Mining, p.99, November 19-22, 2003
• 25: Lewis, M. 2003. Department of defense appropriations act, 2004. Title VIII Section 8120. Enacted as Public Law 108-87.
• 26: Xiaodong Lin , Chris Clifton , Michael Zhu, Privacy-preserving clustering with distributed EM mixture modeling, Knowledge and Information Systems, v.8 n.1, p.68-81, July 2005 [doi>10.1007/s10115-004-0148-7]
• 27: Yehuda Lindell , Benny Pinkas, Privacy Preserving Data Mining, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.36-54, August 20-24, 2000
• 28: Lindell, Y. and Pinkas, B. 2002. Privacy preserving data mining. J. Cryptol. 15, 3, 177--206.
• 29: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• 30: Shariq J. Rizvi , Jayant R. Haritsa, Maintaining data privacy in association rule mining, Proceedings of the 28th international conference on Very Large Data Bases, p.682-693, August 20-23, 2002, Hong Kong, China
• 31: Schneier, B. 1995. Applied Cryptography, 2nd ed. John Wiley & Sons, Hoboken, NJ.
• 32: Shirao, K., Hoff, P., Ohtsu, A., Loehrer, P., Hyodo, I., Wadler, S., Wadleigh, R., O'Dwyer, P., Muro, K., Yamada, Y., Boku, N., Nagashima, F., and Abbruzzese, J. 2004. Comparison of the efficacy, toxicity, and pharmacokinetics of a uracil/tegafur (UFT) plus oral leucovorin (LV) regimen between Japanese and American patients with advanced colorectal cancer: Joint United States and Japan study of UFT/LV. J. Clinical Oncol. 22, 17 (Sept. 1), 3466--3474.
• 33: Jaideep Vaidya , Chris Clifton, Privacy preserving association rule mining in vertically partitioned data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775142]
• 34: Jaideep Vaidya , Chris Clifton, Privacy-preserving k-means clustering over vertically partitioned data, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956776]
• 35: Vaidya, J. and Clifton, C. 2004. Privacy preserving naïve Bayes classifier for vertically partitioned data. In Proceedings of the SIAM International Conference on Data Mining. SIAM, Philadelphia, PA, 522--526.
• 36: Jaideep Vaidya , Chris Clifton, Privacy-preserving k-means clustering over vertically partitioned data, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956776]
• 37: Jaideep Vaidya , Chris Clifton, Secure set intersection cardinality with application to association rule mining, Journal of Computer Security, v.13 n.4, p.593-622, July 2005
• 38: Wang, K., Xu, Y., She, R., and Yu, P. S. 2006. Classification spanning private databases. In Proceedings of the 21st National Conference on Artificial Intelligence (AAAI). AAAI Press, Menlo Park, CA.
• 39: Ian H. Witten , Eibe Frank, Data mining: practical machine learning tools and techniques with Java implementations, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 40: Rebecca Wright , Zhiqiang Yang, Privacy-preserving Bayesian network structure computation on distributed heterogeneous data, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014145]
• 41: Andrew Chi-Chih Yao, How to generate and exchange secrets, Proceedings of the 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), p.162-167, October 27-29, 1986 [doi>10.1109/SFCS.1986.25]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases
      H.2.8 Database applications
          Subjects: Data mining

Keywords:
Decision tree classification, privacy