Paper 2018/995

Preprocess-then-NTT Technique and Its Applications to KYBER and NEWHOPE

Shuai Zhou, Haiyang Xue, Daode Zhang, Kunpeng Wang, Xianhui Lu, Bao Li, and Jingnan He


The Number Theoretic Transform (NTT) provides efficient algorithm for multiplying large degree polynomials. It is commonly used in cryptographic schemes that are based on the hardness of the Ring Learning With Errors problem (RLWE), which is a popular basis for post-quantum key exchange, encryption and digital signature. To apply NTT, modulus q should satisfy that q = 1 mod 2n, RLWE-based schemes have to choose an oversized modulus, which leads to excessive bandwidth. In this work, we present “Preprocess-then-NTT (PtNTT)” technique which weakens the limitation of modulus q, i.e., we only require q = 1 mod n or q = 1 mod n/2. Based on this technique, we provide new parameter settings for KYBER and NEWHOPE (two NIST candidates). In these new schemes, we can reduce public key size and ciphertext size at a cost of very little efficiency loss.

Note: Revise the references.

Available format(s)
Publication info
Published elsewhere. Inscrypt 2018
NTTPreprocess-then-NTTKyberNewHopeRing LWEModule LWE
Contact author(s)
zhoushuai @ iie ac cn
haiyangxc @ gmail com
2020-08-01: last of 2 revisions
2018-10-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shuai Zhou and Haiyang Xue and Daode Zhang and Kunpeng Wang and Xianhui Lu and Bao Li and Jingnan He},
      title = {Preprocess-then-NTT Technique and Its Applications to KYBER and NEWHOPE},
      howpublished = {Cryptology ePrint Archive, Paper 2018/995},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.