Paper 2017/304

Provably Secure NTRUEncrypt over More General Cyclotomic Rings

Yang Yu and Guangwu Xu and Xiaoyun Wang

Abstract

NTRUEncrypt is a fast and standardized lattice-based public key encryption scheme, but it lacks a solid security guarantee. In 2011, Stehlé and Steinfeld first proposed a provably secure variant of NTRUEncrypt, denoted by pNE, over power-of-2 cyclotomic rings. The IND-CPA security of pNE is based on the quantum worst-case hardness of classical problems over ideal lattices. Recently, Yu, Xu and Wang constructed pNE variants over prime cyclotomic rings. In this paper, we further extend the previous results to the case of general prime power cyclotomic rings, which allows a more flexible choice of parameters. We discover a potential trade-off between the power exponent of the ring order and the minimal magnitude of modulus. Moreover, we discuss the case of pNE over general rings assuming the hardness of corresponding RLWE, and propose three attributes of the ring mattering to parameter selection.