Provably Secure NTRUEncrypt over More General Cyclotomic Rings.
Yang Yu, Guangwu Xu, Xiao-Yun Wang · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 2017
NTRUEncrypt is a fast and standardized lattice-based public key encryption scheme, but it lacks a proof of security.Stehlé 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 Stehlé 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.