Paper 2017/304

Provably Secure NTRUEncrypt over More General Cyclotomic Rings

Yang Yu, Guangwu Xu, and Xiaoyun Wang


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.

Available format(s)
Publication info
Preprint. MINOR revision.
Lattice-based cryptographyNTRULearning With ErrorsProvable security.
Contact author(s)
y-y13 @ mails tsinghua edu cn
2018-07-25: last of 3 revisions
2017-04-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yang Yu and Guangwu Xu and Xiaoyun Wang},
      title = {Provably Secure NTRUEncrypt over More General Cyclotomic Rings},
      howpublished = {Cryptology ePrint Archive, Paper 2017/304},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.