QTRU: quaternionic version of the NTRU public-key cryptosystems

Abstract

In this paper we will construct a lattice-based public-key cryptosystem using non-commutative quaternion algebra, and since its lattice does not fully fit within Circular and Convolutional Modular Lattice (<em>CCML</em>), we prove it is arguably more secure than the existing lattice-based cryptosystems such as NTRU. As in NTRU, the proposed public-key cryptosystem relies for its inherent security on the intractability of finding the shortest vector in a certain non-convolutional modular lattice, yet it is efficient and cost effective, contrary to cryptosystems such as RSA or ECC. The detailed specification of the proposed cryptosystem, including the underlying algebraic structure, key generation, encryption and decryption process and also the issues regarding key security, message security, and probability of successful decryption are explained. We will further show, based on the existing results for lattice-reduction algorithms, that the proposed cryptosystem with a dimension of 41 will have a security equal to NTRU-167.