NETRU: A Non-commutative and Secure Variant of CTRU Cryptosystem

Document Type: ORIGINAL RESEARCH PAPER

Authors

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

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

Abstract

In this paper we present a new finite field-based public key cryptosystem(NETRU) which is a non-commutative variant of CTRU. The original CTRU is defined by the ring of polynomials in one variable over a finite field F2. This system works in the ring R = F2[x]=hxN 􀀀 1i and is already broken by some attacks such as linear algebra attack. We extend this system over finite fields Zp, where p is a prime (or prime power) and it operates over the non-commutative ring M = Mk(Zp)[T; x]=hXn 􀀀 Ikki, where M is a matrix ring of k by k matrices of polynomials in R = Zp[T; x]=hxn 􀀀1i. In the proposed NETRU, the encryption and decryption computations are non-commutative and hence the system is secure against linear algebra attack as lattice-based attacks. NETRU is designed based on the CTRU core and exhibits high levels of security with two-sided matrix multiplication.

Keywords


[1] W. Diffie, and M.E. Hellman, New directions in cryptography, In IEEE Trans. On Information Theory, (1976), Vol. 22, pages 644-654.
[2] N. Koblitz, and A.J. Menezes, A Survey of Public Key Cryptosystems, SIAM Review, (2004), Vol.46, No. 4, pages 599-634.
[3] R.J. McEliece, A public key cryptosystem based on algebraic coding theory, JPL DSN Progress Report, (1978), No. 42-44, pages 114-116.
[4] T. Matsumoto, and H. Imai, Public quadratic polynomial-tuples for efficient signatureverification and message-encryption, In Proceeding of Eurocrypt ’88, (1988), LNCS of vol. 330,Springer-Verlag, pages 419-453.
[5] J. Ding, A new variant of the Matsumoto-Imaicryptosystem through perturbation, In Proceeding of PKC ’04, (2004), LNCS of vol. 2947, Springer-Verlag, pages 305-318.
[6] O. Regev, Lattice-based cryptography, In Advances in cryptology-CRYPTO, (2006), pages131–141.
[7] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, J. ACM,(2005), Vol. 56, No. 6, pages 1–40. Preliminary version in STOC 2005.
[8] C. Peikert, V. Vaikuntanathan, and B. Waters, A framework for efficient and composable oblivious transfer, In CRYPTO, (2008), pages 554–571.
[9] X. Boyen, Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more, In Public Key Cryptography,(2010), pages 499–517.
[10] C. Gentry, C. Peikert, and V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, In STOC, (2008), pages 197–206.
[11] V. Lyubashevsky, Lattice signatures without trapdoors, In EUROCRYPT, (2012), pages 738–755.
[12] D. Cash, D. Hofheinz, E. Kiltz, and C. Peikert, Bonsai trees, or how to delegate a lattice basis, In EUROCRYPT, (2010), pages 523–552.
[13] S. Agrawal, D. Boneh, and X. Boyen, Lattice basis delegation in fixed dimension and shorter ciphertext hierarchical IBE, In CRYPTO, (2010), pages 98–115.
[14] Z. Brakerski and V. Vaikuntanathan, Efficient  fully homomorphic encryption from (standard) LWE, In FOCS, (2011), pages 97–106.

[15] J. Hoffstein, J. Pipher, and J.H. Silverman, NTRU: A Ring-Based Public Key Cryptosystem, In Proceedings of the 3rd International Symposium on Algorithmic Number Theory (ANTS-III), (1998), pages 267-288.
[16] D. Coppersmith, and A. Shamir, Lattice attacks on NTRU, in EUROCRYPT, (1997), pages 52–61.
[17] C. Gentry, Key recovery and message attacks on NTRU-composite, Eurocrypt 01, (2001), Springer LNCS 2045, pages 182-194.
[18] Standard Specifications for Public Key Cryptographic Techniques Based on Hard Problems over Lattices. IEEE P1363, 2008. Available at http://grouper.ieee.org/groups/1363/.
[19] D. Han, J. Hong, J.W. Han, and D. Kwon, Key recovery attacks on NTRU without ciphertext validation routine, In Proceeding of ACISP ’03, (2003), LNCS of vol. 2727, Springer-Verlag, pages 274-284.
[20] M. Coglianese, and B. M. Go, MaTRU: A New NTRU-Based Cryptosystem, INDOCRYPT, Lecture Notes in Computer Science, (2005), No. 3797 pages 232-243.
[21] 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.
[22] P. Gaborit, J. Ohler, and P. Sole, CTRU, a polynomial analogue of NTRU, Technical report, INRIA, (2002).
[23] R. Kouzmenko, Generalizations of the NTRU Cryptosystem, Master’s thesis, Polytechnique Montreal, Canada, (2006).
[24] M. O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comp., (1980), No. 9, pages 273-280.
[25] M. Butler, On the reducibility of polynomials over a finite field, Quart. J. Math. Oxford 5(1954), pages 102-107.
[26] J. von zur Gathen, and V. Shoup, Computing Frobenius maps and factoring polynomials, Comput complexity, (1992), No. 2, pages 187-224.
[27] V. Shoup, Fast construction of irreducible polynomials over finite fields, J. Symb. Comp., (1995), No. 17, pages 371-391.
[28] M. Ben-Or, Probabilistic algorithms in finite fields, In Proc. 22nd IEEE Symp. Foundations Computer Science, (1981), pages 394-398.
[29] N. Howgrave-Graham, J.H. Silverman, and W.Whyte, A Meet-In-The-Middle Attack on an NTRU Private Key, Technical report, Security Innovation Inc., Boston, MA, USA, (2002). Available at http://securityinnovation.com/ cryptolab/pdf/NTRUTech004v2.pdf.
[30] E. Jaulmes, and A. Joux, A Chosen Ciphertext Attack against NTRU, In Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology-CRYPTO, (2000), pages 20-36.
[31] J. Hoffstein, and J. Silverman, Optimizations for NTRU, Technical Report 015, NTRU Cryptosystems, (2000). Available
at http://www.sisecure.com/cryptolab/pdf/ TECH_ARTICLE_OPT.pdf.
[32] P.Q. Nguyen, and D. Stehle, LLL on the Average, In Proceedings of the 7th International Symposium on Algorithmic Number Theory (ANTSVII), (2006), pages 238-256.
[33] P.Q. Nguyen, and D. Stehle, Low Dimensional Lattice Basis Reduction Revisited, ACM Transactions on Algorithms, (2009), Vol. 5, No. 4, pages 1-48.
[34] R.E. Atani, S.E. Atani, and A.H. Karbasi, EEH: A GGH-Like Public Key Cryptosystem Over The Eisenstein Integers Using Polynomial Representation, The ISC International Journal of Information Security, (2015), Vol. 7, No. 2, pages 115-126.
[35] A.H. Karbasi, and R.E. Atani, ILTRU: An NTRU-Like Public Key Cryptosystem Over Ideal Lattices, IACR Cryptology ePrint Archive 2015: 549, (2015).
[36] A.H. Karbasi, R.E. Atani, and S.E. Atani, A New Ring-Based SPHF and PAKE Protocol On Ideal Lattices, Submitted.
[37] S.E. Atani, R.E. Atani, and A.H.Karbasi, PairTRU: Pairwise Non-commutative Extension of The NTRU Public key Cryptosystem, Submitted