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

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,


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.


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


[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.