Threshold Cryptosystem Mining of Association Rules using Horizontal Distributed Database

International Journal of Computer Science and Engineering

© 2016 by SSRG - IJCSE Journal

Volume 3 Issue 3

Year of Publication : 2016

Authors : T.Satish Vijay Rajeev, Gousiya Begum

10.14445/23488387/IJCSE-V3I3P101

How to Cite?

T.Satish Vijay Rajeev, Gousiya Begum, "Threshold Cryptosystem Mining of Association Rules using Horizontal Distributed Database," SSRG International Journal of Computer Science and Engineering , vol. 3,  no. 3, pp. 1-8, 2016. Crossref, https://doi.org/10.14445/23488387/IJCSE-V3I3P101

Abstract:

We propose a protocol for secure mining of association rules in horizontally distributed databases. The current leading protocol is that of Kantarcioglu and Clifton[18]. Our protocol, like theirs, is based on the Fast Distributed Mining (FDM) algorithm of Cheung et al[8]. which is an unsecured distributed version of the Apriori algorithm. The main ingredients in our protocol are two novel secure multi-party algorithms — one that computes the union of private subsets that each of the interacting players hold, and another that tests the inclusion of an element held by one player in a subset held by another. Our protocol offers enhanced privacy with respect to the protocol in [18]. In addition, it is simpler and is significantly more efficient in terms of communication rounds, communication cost and computational cost.

Keywords:

threshold-c, mergekc, privacy, association rules, FDM.

References:

[1] R. Agrawal and R. Srikant. Fast algorithms for mining association rules in large databases. In VLDB, pages 487–499, 1994.
[2] R. Agrawal and R. Srikant. Privacy-preserving data mining. In SIGMOD Conference, pages 439–450, 2000.
[3] D. Beaver, S. Micali, and P. Rogaway. The round complexity of secure protocols. In STOC, pages 503– 513, 1990.
[4] M. Bellare, R. Canetti, and H. Krawczyk. Keying hash functions for message authentication. In Crypto, pages 1–15, 1996.
[5] A. Ben-David, N. Nisan, and B. Pinkas. FairplayMP - A system for secure multi-party computation. In CCS, pages 257–266, 2008.
[6] J.C. Benaloh. Secret sharing homomorphisms: Keeping shares of a secret secret. In Crypto, pages 251– 260, 1986.
[7] J. Brickell and V. Shmatikov. Privacy-preserving graph algorithms in the semi-honest model. In ASIACRYPT, pages 236– 252, 2005.
[8] D.W.L. Cheung, J. Han, V.T.Y. Ng, A.W.C. Fu, and Y. Fu. A fast distributed algorithm for mining association rules. In PDIS, pages 31– 42, 1996.
[9] D.W.L Cheung, V.T.Y. Ng, A.W.C. Fu, and Y. Fu. Efficient mining of association rules in distributed databases. IEEE Trans. Knowl. Data Eng., 8(6):911– 922, 1996.
[10] T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31:469–472, 1985.
[11] A.V. Evfimievski, R. Srikant, R. Agrawal, and J. Gehrke. Privacy preserving mining of association rules. In KDD, pages 217– 228, 2002. 
[12] R. Fagin, M. Naor, and P. Winkler. Comparing Information Without Leaking It. Communications of the ACM, 39:77–85, 1996.
[13] M. Freedman, Y. Ishai, B. Pinkas, and O. Reingold. Keyword search and oblivious pseudorandom functions. In TCC, pages 303– 324, 2005.
[14] M.J. Freedman, K. Nissim, and B. Pinkas. Efficient private matching and set intersection. In EUROCRYPT, pages 1–19, 2004.
[15] O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In STOC, pages 218– 229, 1987.
[16] H. Grosskreutz, B. Lemmen, and S. R¨uping. Secure distributed subgroup discovery in horizontally partitioned data. Transactions on Data Privacy, 4:147– 165, 2011.
[17] W. Jiang and C. Clifton. A secure distributed framework for achieving k-anonymity. The VLDB Journal, 15:316–333, 2006.
[18] M. Kantarcioglu and C. Clifton. Privacy-preserving distributed mining of association rules on horizontallypartitioned data. IEEE Transactions on Knowledge and Data Engineering, 16:1026–1037, 2004.
[19] M. Kantarcioglu, R. Nix, and J. Vaidya. An efficient approximate protocol for privacy-preserving association rule mining. In PAKDD, pages 515–524, 2009.
[20] L. Kissner and D.X. Song. Privacy-preserving set operations. In CRYPTO, pages 241–257, 2005.
[21] X. Lin, C. Clifton, and M.Y. Zhu. Privacy-preserving clustering with distributed EM mixture modeling. Knowl. Inf. Syst., 8:68–81, 2005.
[22] Y. Lindell and B. Pinkas. Privacy preserving data mining. In Crypto, pages 36–54, 2000.
[23] J.S. Park, M.S. Chen, and P.S. Yu. An effective hash based algorithm for mining association rules. In SIGMOD Conference, pages 175–186, 1995.
[24] S.C. Pohlig and M.E. Hellman. An improved algorithm for computing logarithms over gf(p) and its cryptographic significance. IEEE Transactions on Information Theory, 24:106–110, 1978.
[25] R.L. Rivest, A. Shamir, and L.M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 21(2):120–126, 1978.
[26] A. Schuster, R. Wolff, and B. Gilburd. Privacy-preserving association rule mining in large-scale distributed systems. In CCGRID, pages 411– 418, 2004.
[27] R. Srikant and R. Agrawal. Mining generalized association rules. In VLDB, pages 407–419, 1995.
[28] T. Tassa and D. Cohen. Anonymization of centralized and distributed social networks by sequential clustering. IEEE Transactions on Knowledge and Data Engineering, 2012.
[29] T. Tassa and E. Gudes. Secure distributed computation of Anonymized views of shared databases. Transactions on Database Systems, 37, Article 11, 2012.
[30] T. Tassa, A. Jarrous, and J. Ben-Ya’akov. Oblivious evaluation of multivariate polynomials. Submitted.
[31] J. Vaidya and C. Clifton. Privacy preserving association rule mining in vertically partitioned data. In KDD, pages 639–644, 2002.
[32] A.C. Yao. Protocols for secure computation. In FOCS, pages 160–164, 1982.
[33] J. Zhan, S. Matwin, and L. Chang. Privacy preserving collaborative association rule mining. In Data and Applications Security, pages 153– 165, 2005.
[34] S. Zhong, Z. Yang, and R.N. Wright. Privacy-enhancing kanonymization of customer data. In PODS, pages 139–147, 2005.