Paper 2019/1079

When NTT Meets Karatsuba: Preprocess-then-NTT Technique Revisited

Yiming Zhu, Zhen Liu, and Yanbin Pan


The Number Theoretic Transform (NTT) technique is widely used in the implementation of the cryptographic schemes based on the Ring Learning With Errors problem(RLWE), since it provides efficient algorithm for multiplication of polynomials over the finite field. However, to employ NTT, the finite field is required to have some special root of unity, such as $n$-th root, which makes the module $q$ in RLWE big since we need $q\equiv 1\mod 2n$ to ensure such root exits. At Inscrypt 2018, Zhou et al. proposed a technique called preprocess-then-NTT to reduce the value of modulus $q$ while the NTT still works, and the time complexity is just a constant ($>1$) multiple of the original NTT algorithm asymptotically. In this paper, we revisit the preprocess-then-NTT technique and point out it can be improved such that its time complexity is as the same as the original NTT algorithm asymptotically. What's more, through experiments we find that even compared with the original NTT our improved algorithm may have some advantages in efficiency.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
NTTRing Learning With Errorspreprocess-then-NTT
Contact author(s)
panyanbin @ amss ac cn
zhuyiming17 @ mails ucas ac cn
liuzhen16 @ mails ucas ac cn
2019-10-05: revised
2019-09-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yiming Zhu and Zhen Liu and Yanbin Pan},
      title = {When {NTT} Meets Karatsuba: Preprocess-then-{NTT} Technique Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1079},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.