Cryptology ePrint Archive: Report 2019/1079

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

Yiming Zhu and Zhen Liu and Yanbin Pan

Abstract: 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.

Category / Keywords: public-key cryptography / NTT, Ring Learning With Errors, preprocess-then-NTT

Date: received 21 Sep 2019, last revised 5 Oct 2019

Contact author: panyanbin at amss ac cn,zhuyiming17@mails ucas ac cn,liuzhen16@mails ucas ac cn

Available format(s): PDF | BibTeX Citation

Version: 20191005:063222 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]