Provably Secure NTRU Instances over Prime Cyclotomic Rings

Due to its remarkable performance and potential resistance to quantum attacks, \(\mathsf {NTRUEncrypt}\) has drawn much attention recently; it also has been standardized by IEEE. However, classical \(\mathsf {NTRUEncrypt}\) lacks a strong security guarantee and its security still relies on heuristic arguments. At Eurocrypt 2011, Stehlé and Steinfeld first proposed a variant of \(\mathsf {NTRUEncrypt}\) with a security reduction from standard problems on ideal lattices. This variant is restricted to the family of rings \(\mathbb {Z}[X]/(X^n+1)\) with n a power of 2 and its private keys are sampled by rejection from certain discrete Gaussian so that the public key is shown to be almost uniform. Despite the fact that partial operations, especially for \(\mathsf {RLWE} \), over \(\mathbb {Z}[X]/(X^n+1)\) are simple and efficient, these rings are quite scarce and different from the classical \(\mathsf {NTRU}\) setting. In this work, we consider a variant of \(\mathsf {NTRUEncrypt}\) over prime cyclotomic rings, i.e. \(\mathbb {Z}[X]/(X^{n-1}+\cdots +X+1)\) with n an odd prime, and obtain \(\mathsf {IND\text {-}CPA}\) secure results in the standard model assuming the hardness of worst-case problems on ideal lattices. In our setting, the choice of the rings is much more flexible and the scheme is closer to the original \(\mathsf {NTRU}\), as \(\mathbb {Z}[X]/(X^{n-1}+\cdots +X+1)\) is a large subring of the \(\mathsf {NTRU}\) ring \(\mathbb {Z}[X]/(X^{n}-1)\). Some tools for prime cyclotomic rings are also developed.