Distributed privacy preserving k-means clustering with additive secret sharing

ABSTRACT

Recent concerns about privacy issues motivated data mining researchers to develop methods for performing data mining while preserving the privacy of individuals. However, the current techniques for privacy preserving data mining suffer from high communication and computation overheads which are prohibitive considering even a modest database size. Furthermore, the proposed techniques have strict assumptions on the involved parties which need to be relaxed in order to reflect the real-world requirements. In this paper we concentrate on a distributed scenario where the data is partitioned vertically over multiple sites and the involved sites would like to perform clustering without revealing their local databases. For this setting, we propose a new protocol for privacy preserving k-means clustering based on additive secret sharing. We show that the new protocol is more secure than the state of the art. Experiments conducted on real and synthetic data sets show that, in realistic scenarios, the communication and computation cost of our protocol is considerably less than the state of the art which is crucial for data mining applications.

REFERENCES

• 1: 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
• 2: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 3: Chris Clifton , Murat Kantarcioglu , Jaideep Vaidya , Xiaodong Lin , Michael Y. Zhu, Tools for privacy preserving distributed data mining, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.28-34, December 2002 [doi>10.1145/772862.772867]
• 4: Marc Fischlin, A Cost-Effective Pay-Per-Multiplication Comparison Method for Millionaires, Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA, p.457-472, April 08-12, 2001
• 5: 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]
• 6: S. V. Kaya, T. B. Pedersen, E. Savaş, and Y. Saygin. Efficient privacy preserving distributed clustering based on secret sharing. In PAKDD 2007 International Workshops: Emerging Technologies in Knowledge Discovery and Data Mining, pages 280--291. Springer, 2007.
• 7: Selim Volkan Kaya. Toolbox for Privacy Preserving Data Mining. Master's thesis, Sabanci University, Istanbul, TURKEY, July 2007.
• 8: Sven Laur , Helger Lipmaa , Taneli Mielikäinen, Cryptographically private support vector machines, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150477]
• 9: Kun Liu , Hillol Kargupta , Jessica Ryan, Random Projection-Based Multiplicative Data Perturbation for Privacy Preserving Distributed Data Mining, IEEE Transactions on Knowledge and Data Engineering, v.18 n.1, p.92-106, January 2006 [doi>10.1109/TKDE.2006.14]
• 10: Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Advances in Cryptology --- EUROCRYPT '99. International Conference on the Theory and Application of Cryptographic Techniques, Lecture Notes in Computer Science, pages 223--238. Springer-Verlag, May 1999.
• 11: Tomas Sander , Adam Young , Moti Yung, Non-Interactive CryptoComputing For NC1, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.554, October 17-18, 1999
• 12: 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]
• 13: Jaikumar Vijayan. House committee chair wants info on cancelled dhs data-mining programs. Computer World, September 18 2007.
• 14: 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]
• 15: Andrew C. Yao, Protocols for secure computations, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), p.160-164, November 03-05, 1982

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics

Keywords:
k-means clustering, privacy preserving data mining, secret sharing, secure multiparty computation