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

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 − Ik∗ki, 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.