NTRU over rings beyond \(\mathbb{Z}\) (Q977194)

NTRU is a public-key cryptosystem introduced by [\textit{J. Hoffstein, J. Pipher} and \textit{J. H. Silverman}, NTRU: A ring-based public key cryptosystem. Algorithmic number theory. 3rd international symposium, ANTS-III, Portland, OR, USA, June 21--25, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1423, 267--288 (1998; Zbl 1067.94538)] based on \(A[x]\) with \(A=\mathbb Z\). Its decryption algorithm has a non-zero probability of failure. Analogues of NTRU with \(A=\mathbb Z_2[x]\) and \(A=\mathbb Z[i]\) have been studied. Here the authors present criteria for the suitability of a ring \(A\) as a base for NTRU. They show the Eisenstein integers \(A=\mathbb Z[\zeta_3]\) satisfy the criteria and yield better security than previous bases \(A\). Assuming a simple probabilistic model, they show the decryption failure probability for the Eisenstein integers is comparable to that of \(A=\mathbb Z\) or \(\mathbb Z[i]\).