EEH: AGGH-like public key cryptosystem over the eisenstein integers using polynomial representations

Document Type: ORIGINAL RESEARCH PAPER

Authors

1 Department of Computer Engineering, University of Guilan, Rasht, Iran.

2 Department of Mathematics, University of Guilan, Rasht, Iran.

3 School of Computer Science, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran.

Abstract

GGH class of public-key cryptosystems relies on computational problems based on the closest vector problem (CVP) in lattices for their security. The subject of lattice based cryptography is very active and there have recently been new ideas that revolutionized the field. We present EEH, a GGH-Like public key cryptosystem based on the Eisenstein integers Z [ζ3] where ζ3 is a primitive cube root of unity. EEH applies representations of polynomials to the GGH encryption scheme and we discuss its key size and parameters selection. We also provide theoretical and experimental data to compare the security and efficiency of EEH to GGH with comparable parameter sets and show that EEH is an improvement over GGH in terms of security and efficiency.

Keywords


[1] V. Lyubashevsky, and D. Micciancio, Generalized compact knapsacks are collision resistant, In Proceedings of ICALP, (2006), Vol. 4052 of LNCS, pages 144-155.

[2] C. Peikert, and A. Rosen, Lattices that admit logarithmic worst-case to average-case connection factors, In Proceedings of STOC, ACM, (2007), pages 478-487.

[3] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of ACM, (2009), Vol. 56, pages 6-34.

[4] C. Peikert, and B. Waters, Lossy trapdoor functions and their applications, In Proceedings of STOC, (2008), pages 187-196.

[5] V. Lyubashevsky, A. Palacio, and G. Segev, Public-key cryptographic primitives provably as secure as subset sum, In D. Micciancio, editor, Proceedings of TCC, (2010), Vol. 5978 of LNCS, pages 382-400.

[6] C. Gentry, C. Peikert, and V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, In Proceedings of STOC, (2008), pages 197-206.

[7] V. Lyubashevsky, and D. Micciancio, Asymptotically efficient lattice-based digital signatures, In Proceedings of TCC, (2008), Vol. 4948 of LNCS, pages 37-54.

[8] D. Gordon, J. Katz, and V. Vaikuntanathan, A group signature scheme from lattice assumptions, Advances in Cryptology-ASIACRYPT, (2010), Springer Berlin Heidelberg, pages 395-412.

[9] S. Agrawal, D. Boneh, and X. Boyen, Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical ibe, Advances in Cryptology CRYPTO, (2010), Springer Berlin Heidelberg, pages 98-115.

[10] C. Gentry, S. Halevi, and V. Vaikuntanathan, A simple bgn-type cryptosystem from lwe, In H. Gilbert, editor, Advances in Cryptology EUROCRYPT, (2010), Vol. 6110 of Lecture Notes in Computer Science, pages 506-522.

[11] C. Gentry, Fully homomorphic encryption using ideal lattices, In Proceedings of STOC, ACM, (2009), pages 169-178.

[12] D. Stehle, and R. Steinfeld, Faster fully homomorphic encryption, In M. Abe, editor, ASIACRYPT, (2010), Vol. 6477 of Lecture Notes in Computer Science, pages 377-394.

[13] N. Ogura, G. Yamamoto, T. Kobayashi, and S. Uchiyama, An improvement of key generation algorithm for gentrys homomorphic encryption scheme, In IWSEC, (2010), Vol. 6434 of LNCS, pages 70-83.

[14] P. Cayrel, R. Lindner, M. Ruckert, and R. Silva, Improved zero-knowledge identification with lattices, Tatra Mountains Mathematical Publications 53.1 (2012), pages 33-63.

[15] V. Lyubashevsky, Lattice-based identification schemes secure under active attacks, In Proceedings of PKC, (2008), No. 4939 in LNCS, pages 162-179.

[16] P. Gaborit, J. Ohler, and P. Sole, CTRU, a polynomial analogue of NTRU, Technical report, INRIA, France, 2002. Available at ftp://ftp.inria.fr/INRIA/publication/ publipdf/RR/RR-4621.pdf.

[17] M. Coglianese, and B.M. Goi, MaTRU: A New NTRU-Based Cryptosystem, In Proceedings of the 6th International Conference on Cryptology in India (INDOCRYPT), (2005), pages 232-243.

[18] N. Vats, NNRU, a Non-commutative Analogue of NTRU, The Computing Research Repository (CoRR), abs/0902.1891, (2009). Available at; http://arxiv.org/abs/0902.1891.

[19] R. Kouzmenko, Generalizations of the NTRU Cryptosystem, Master's thesis, Polytechnique Montreal, Canada, (2006).

[20] C. Karimianpour, Lattice-Based Cryptosystems, Master's thesis, University of Ottawa, Canada, (2007).

[21] M. Nevins, C. Karimianpour, and A. Miri, NTRU over rings beyond Z, Designs, Codes and Cryptography, (2010), vol. 56, no. 1, pages 65-78.

[22] E. Malekian, A. Zakerolhosseini, and A. Mashatan, QTRU: Quaternionic Version of the NTRU Public-Key Cryptosystems, The int'l Journal of information Security (ISeCure), (2011), vol. 3, no. 1, pages 29-42.

[23] A.H. Karbasi and R.E. Atani, ILTRU: An NTRU-Like Public Key Cryptosystem Over Ideal Lattices, The 7th International IEEE Symposium on Telecommunications (IST2014), Tehran, Iran, (2014).

[24] O. Goldreich, Sh. Goldwasser, and Sh. Halevi, Public-key cryptosystems from lattice reduction problems, In CRYPTO '97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, London, UK, (1997), pages 112-131.

[25] R.J. McEliece, A public-key cryptosystem based on algebraic coding theory, Deep Space Network Progress Report, (1978), No. 44, pages 114-116.

[26] P. Nguyen, Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto '97, Advances in Cryptology-Crypto '99, LNCS 1666, (1999), pages 288-304.

[27] D. Micciancio, Improving lattice based cryptosystems using the Hermite normal form, In Cryptography and Lattices Conference (CaLC), (2001), pages 126-145.

[28] M. Ajtai, and C. Dwork, A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence, In 29th ACM Symposium on Theory of Computing, (1997), pages 284-293.

[29] C.P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theor. Comput. Sci., (1987), No. 53(2-3), pages 201-224.

[30] S. Paeng, B. Jung, and K. Ha, A Lattice Based Public Key Cryptosystem Using Polynomial Representations, In Y.G. Desmedt (Ed.), PKC, (2003), Vol. 2567 of LNCS, Springer, pages 292-308.

[31] K. Jarvis, and M. Nevins, ETRU: NTRU over the Eisenstein Integers, Designs, Codes and Cryptography 74.1, (2015), pages 219-242.

[32] K. Ireland, and M. Rosen, A Classical Introduction to Modern Number Theory, Second Edition. New York: Springer-Verlag, (1990).

[33] J. Hoffstein, J. Pipher, and J.H. Silverman, An Introduction to Mathematical Cryptography, Springer-Verlag, 1st edition, (2008).

[34] J. Hoffstein, N. Howgrave-Graham, J. Pipher, J.H. Silverman, and W. Whyte, NTRU Sign: digital signatures using the NTRU lattice, In Topics in cryptology CT-RSA, (2003), Vol. 2612 of Lecture Notes in Comput. Sci., Springer, pages 122-140.

[35] J.H. Silverman, High-Speed Multiplication of (Truncated) Polynomial Rings, NTRU Cryptosystems Technical Report 11, (1999), Available from: http://www.ntru.com. Accessed: Dec 2010.

[36] G. Bourgeois, and J. Faugere, Algebraic attack on NTRU using Witt vectors and Grobner bases, In Journal of Math. Crypt., (2009), Vol. 3, pages 205-214.

[37] V. Shoup, NTL: A Library for doing Number Theory, http://www.shoup.net/ntl/. Accessed: Aug. (2010).

[38] J. Hoffstein, J. Pipher, and J. H. Silverman, NTRU: a ring-based public key cryptosystem, In Algorithmic Number Theory, Portland OR, (1998), Vol. 1423 of Lecture Notes in Comput. Sci., pages 267-288.

[39] A.H. Karbasi and R.E. Atani, "PSTRU: A provably secure variant of NTRU Encrypt over extended ideal lattices," The 2nd National Industrial Mathematics Conference, Tabriz, Iran, (2015).