Provably secure NTRU instances over prime cyclotomic rings

Due to its remarkable performance and potential resistance to quantum attacks, NTRUEncrypt has drawn much attention recently; it also has been standardized by IEEE. However, classical 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 NTRUEncrypt with a security reduction from standard problems on ideal lattices. This variant is restricted to the family of rings ℤ[X]/(Xn + 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 RLWE, over ℤ[X]/(Xn + 1) are simple and efficient, these rings are quite scarce and different from the classical NTRU setting. In this work, we consider a variant of NTRUEncrypt over prime cyclotomic rings, i.e. ℤ[X]/(Xn-1 +…+ X + 1) with n an odd prime, and obtain IND-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 NTRU, as ℤ[X]/(Xn-1+…+X+1) is a large subring of the NTRU ring ℤ[X]/(Xn-1). Some tools for prime cyclotomic rings are also developed.

• View at Publisher

Full Text ( Final Version , 568kb )