Paper 2017/304

Provably Secure NTRUEncrypt over More General Cyclotomic Rings

Yang Yu, Guangwu Xu, and Xiaoyun Wang

Abstract

NTRUEncrypt is a fast and standardized lattice-based public key encryption scheme, but it lacks a proof of security. Stehle and Steinfeld (EUROCRYPT 2011) first gave a variant of NTRUEncrypt, denoted by pNE, over power-of-2 cyclotomic rings. The pNE scheme is provably secure assuming the hardness of worst-case problems over ideal lattices. Recently, Yu, Xu and Wang (PKC 2017) proposed a pNE variant over prime cyclotomic rings, but it requires the parameters to be of rather larger sizes. In this paper, working with canonical embedding, we modify the key generation algorithm of pNE scheme to make it applicable to general cyclotomic rings. Through an improved analysis, we provide tighter parameters of pNE over prime power cyclotomic rings. To be more specific, even for the general case, our parameters are as good as that obtained by Stehle and Steinfeld for the case of power-of-2; compared to that of Yu, Xu and Wang (PKC 2017), the sizes of our parameters get significantly reduced. Thus our result not only applies to a larger class of rings but also enjoys greater efficiency. In proving our results, we have developed some technical tools which may be of general interest. Some remarks on further extension of the work (e.g., for more general polynomial rings) have also been made.