Comparative Evaluation of Elliptic Curve Cryptography Based Homomorphic Encryption Schemes for a Novel Secure Multiparty Computation

Sankita J. Patel, Ankit Chouhan, Devesh C. Jinwala

Department of Computer Engineering, S V National Institute of Technology, Surat, India.

DOI: 10.4236/jis.2014.51002                

Abstract

In this paper, we focus on Elliptic Curve Cryptography based approach for Secure Multiparty Computation (SMC) problem. Widespread proliferation of data and the growth of communication technologies have enabled collaborative computations among parties in distributed scenario. Preserving privacy of data owned by parties is crucial in such scenarios. Classical approach to SMC is to perform computation using Trusted Third Party (TTP). However, in practical scenario, TTPs are hard to achieve and it is imperative to eliminate TTP in SMC. In addition, existing solutions proposed for SMC use classical homomorphic encryption schemes such as RSA and Paillier. Due to the higher cost incurred by such cryptosystems, the resultant SMC protocols are not scalable. We propose Elliptic Curve Cryptography (ECC) based approach for SMC that is scalable in terms of computational and communication cost and avoids TTP. In literature, there do exist various ECC based homomorphic schemes and it is imperative to investigate and analyze these schemes in order to select the suitable for a given application. In this paper, we empirically analyze various ECC based homomorphic encryption schemes based on performance metrics such as computational cost and communication cost. We recommend an efficient algorithm amongst several selected ones, that offers security with lesser overheads and can be applied in any application demanding privacy.

Keywords

Elliptic Curve Cryptography; Privacy Preservation; Secure Multiparty Computation

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	O. Goldreich, “The Foundations of Cryptography,” Vol. 2. Cambridge Univ. Press, Cambridge, 2004.
[2]	Y. Lindell and B. Pinkas, “Secure Multiparty Computation for Privacy-Preserving Data Mining,” Journal of Privacy and Confidentiality, Vol. 1, No. 1, 2009, pp. 59-98.
[3]	M. Rabin, “How to Exchange Secrets by Oblivious Transfer,” Technical Report Tech. Memo TR-81, Aiken Computation Laboratory, 1981.
[4]	D. Josep Ferrer, “A new privacy homomorphism and applications,” Information Processing Letters, Vol. 60, No. 5, 1996, pp. 277-282. http://dx.doi.org/10.1016/S0020-0190(96)00170-6
[5]	A. Shamir, “How to Share a Secret,” Communication of the ACM, Vol. 22, No. 11, 1979, pp. 612-613. http://dx.doi.org/10.1145/359168.359176
[6]	T. B. Pedersen, Y. Saygin and E. Savas, “Secret Sharing vs. Encryption-Based Techniques for Privacy Preserving Data Mining,” UNECE/Eurostat Work Session on SDC, 2007.
[7]	S. Patel, S. Garasia and D. Jinwala, “An Efficient Approach for Privacy Preserving Distributed K-Means Clustering using Shamir’s Secret Sharing Scheme,” In: T. Dimitrakos, R. Moona and D. Patel, Eds., Trust Management VI, IFIP Advances in Information and Communication Technology, Vol. 347, Springer, Boston, 2012, pp. 129-144.
[8]	G. Jagannathan and R. N. Wright, “Privacy-Preserving Distributed k-Means Clustering over Arbitrarily Partitioned Data,” KDD, ACM Press, 2005, pp. 593-599.
[9]	S. Jha, L. Kruger and P. McDaniel, “Privacy Preserving Clustering,” 10th European Symposium on Research in Computer Security, 2005, pp. 397-417.
[10]	N. Koblitz, “Elliptic Curve Cryptosystems,” Mathematics of Computation, Vol. 48, 1987, pp. 203-209. http://dx.doi.org/10.1090/S0025-5718-1987-0866109-5
[11]	V. S. Miller, “Use of Elliptic Curve in Cryptography,” In: Proceedings of Advances in Cryptology (CRYPTO’85), Springer Verlag, 1986, pp. 417-426.
[12]	Certicom Research, “Standards for Efficient Cryptography—SEC 1: Elliptic Curve Cryptography,” 2009.
[13]	A. C. Patel, U. P. Rao and D. R. Patel, “Privacy Preserving Association Rules in Unsecured Distributed Environment Using Elliptic Curve Cryptography,” Proceedings of International Conference on Computing Communication & Networking Technologies (ICCCNT), 2012, pp. 1-5.
[14]	M. Rajalakshmi and T. Purusothaman, “Privacy Preserving Distributed Data Mining using Randomized Site Selection,” European Journal of Scientific Research, Vol. 64, No. 4, 2011, pp. 610-624.
[15]	A. C. Yao, “Protocols for Secure Computations,” Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, 1982, pp. 160-164.
[16]	O. Goldreich, S. Micali and A. Wigderson, “How to Play any Mental Game,” Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, pp. 218-229.
[17]	B. Pinkas, “Privacy Preserving Data Mining,” Journal of Cryptology, Vol. 50, No. 3, 2002, pp. 177-206. http://dx.doi.org/10.1007/s00145-001-0019-2
[18]	B. Pinkas, “Cryptographic Techniques for Privacy-Preserving Data Mining,” SIGKDD Explorations Newsletter, Vol. 4, No. 2, 2002, pp. 12-19. http://doi.acm.org/10.1145/772862.772865.
[19]	W. L. Du and M. J. Atallah, “Privacy-Preserving Cooperative Scientific Computations,” 14th IEEE Computer Security Foundations Workshop, Nova Scotia, 11-13 June 2001, pp. 273-282.
[20]	W. L. Du and M. J. Atallah, “Privacy-Preserving Statistical Analysis,” Proceedings of the 17th Annual Computer Security Applications Conference, New Orleans, 10-14 December 2001, pp. 102-110.
[21]	W. L. Du and M. J. Atallah, “Protocols for Secure Remote Database Access with Approximate Matching,” 7th ACM Conference on Computer and Communications Security (ACMCCS 2000), The First Workshop on Security and Privacy in E-Commerce, Athens, 1-4 November 2000, pp. 87-111.
[22]	Y. Lindell and B. Pinkas, “Privacy Preserving Data Mining,” In Advances in Cryptology—Crypto2000, Lecture Notes in Computer Science, volume 1880, 2000.
[23]	J. Vaidya and C. Clifton, “Privacy-Preserving k-Means Clustering over Vertically Partitioned Data,” Proceedings of 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM Press, 2003, pp. 205-216.
[24]	J. Vaidya and C. Clifton, “Privacy Preserving Association Rule Mining in Vertically Partitioned Data,” 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2002, pp. 639-644.
[25]	S. Jha, L. Kruger and P. McDaniel, “Privacy Preserving Clustering,” Proceedings of 10th European Symposium on Research in Computer Security, 2005, pp. 397-417.
[26]	D. Naccache and J. Stern, “A New Public Key Cryptosystem Based on Higher Residues,” ACM Conference on Computer and Communications Security, 1998, pp. 59-66.
[27]	T. Okamotoand S. Uchiyama, “A New Public-key Cryptosystem as Secure as Factoring,” EUROCRYPT, 1998, pp. 308-318.
[28]	P. Paillier, “Public-Key Cryptosystems Based on Composite Degree Residuosity Classes,” EUROCRYPT, 1999, pp. 223-238.
[29]	T. ElGamal, “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,” CRYPTO, IT, Vol. 31, No. 4, 1985, pp. 469-472.
[30]	P. Paillier, “Trapdooring Discrete Logarithms on Elliptic Curves over Rings,” ASIACRYPT, 2000, pp. 573-584.