Privacy-Preserving Distributed Mining of Association Rules on Horizontally Partitioned Data

ABSTRACT

Data mining can extract important knowledge from large data collections¿but sometimes these collections are split among various parties. Privacy concerns may prevent the parties from directly sharing the data and some types of information about the data. This paper addresses secure mining of association rules over horizontally partitioned data. The methods incorporate cryptographic techniques to minimize the information shared, while adding little overhead to the mining task.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 2: David W. Cheung , Jiawei Han , Vincent T. Ng , Ada W. Fu , Yongjian Fu, A fast distributed algorithm for mining association rules, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.31-43, December 18-20, 1996, Miami Beach, Florida, United States
• 3: David W. Cheung , Vincent T. Ng , Ada W. Fu , Yongjian Fu, Efficient Mining of Association Rules in Distributed Databases, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.911-922, December 1996 [doi>10.1109/69.553158]
• 4: 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
• 5: 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]
• 6: 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]
• 7: S.J. Rizvi and J.R. Haritsa, “Maintaining Data Privacy in Association Rule Mining,” <i>Proc. 28th Int'l Conf. Very Large Data Bases,</i> pp. 682-693, 2002, available: http://www.vldb.org/conf/2002/S19P03.pdf.
• 8: 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
• 9: O. Goldreich, “Secure Multiparty Computation,” (working draft), Sept. 1998, available: http://www.wisdom.weizmann.ac.il/~oded/pp.html.
• 10: 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]
• 11: A.C. Yao, “How to Generate and Exchange Secrets,” <i>Proc. 27th IEEE Symp. Foundations of Computer Science,</i> pp. 162-167, 1986.
• 12: I. Ioannidis and A. Grama, “An Efficient Protocol for Yao's Millionaires'Problem,” <i>Proc. Hawaii Int'l Conf. System Sciences (HICSS-36),</i> 2003.
• 13: O. Goldreich, “Encryption Schemes,” (working draft), Mar. 2003, available: http://www.wisdom.weizmann.ac.il/~oded/PSBook Frag/enc.ps.
• 14: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 15: S.C. Pohlig and M.E. Hellman, “An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance,” <i>IEEE Trans. Information Theory,</i> vol. IT-24, pp. 106-110, 1978.
• 16: Michael K. Reiter , Aviel D. Rubin, Crowds: anonymity for Web transactions, ACM Transactions on Information and System Security (TISSEC), v.1 n.1, p.66-92, Nov. 1998 [doi>10.1145/290163.290168]
• 17: Josh Cohen Benaloh, Secret sharing homomorphisms: keeping shares of a secret secret, Proceedings on Advances in cryptology---CRYPTO '86, p.251-260, January 1987, Santa Barbara, California, United States
• 18: Benny Chor , Eyal Kushilevitz, A communication-privacy tradeoff for modular addition, Information Processing Letters, v.45 n.4, p.205-210, March 22, 1993 [doi>10.1016/0020-0190(93)90120-X]
• 19: C. Clifton M. Kantarcioglu and J. Vaidya, “Defining Privacy for Data Mining,” <i>Proc. US Nat'l Science Foundation Workshop on Next Generation Data Mining,</i> H. Kargupta, A. Joshi, and K.nbspSivakumar,nbspeds., pp. 126-133, 2002.
• 20: Bernardo A. Huberman , Matt Franklin , Tad Hogg, Enhancing privacy and trust in electronic communities, Proceedings of the 1st ACM conference on Electronic commerce, p.78-86, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337012]
• 21: Josh Benaloh , Michael de Mare, One-way accumulators: a decentralized alternative to digital signatures, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.274-285, January 1994, Lofthus, Norway
• 22: W. Diffie and M. Hellman, “New Directions in Cryptography,” <i>IEEE Trans. Information Theory,</i> vol. 22, no. 6, pp. 644-654, Nov. 1976.
• 23: T. ElGamal, “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,” <i>IEEE Trans. Information Theory,</i> vol. IT-31, no. 4, pp. 469-472, July 1985.
• 24: A. Shamir R.L. Rivest and L.M. Adleman, “Mental Poker,” Technical Memo MIT-LCS-TM-125, Laboratory for Computer Science, MIT, Feb. 1979.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Data sharing

General Terms:
Algorithms, Performance

Keywords:
Index Terms- Data mining, security, privacy.