Paper 2019/1079

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

Yiming Zhu, 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.