Welcome to the resource topic for 2019/1079
Title:
When NTT Meets Karatsuba: Preprocess-then-NTT Technique Revisited
Authors: Yiming Zhu, Zhen Liu, 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.
ePrint: https://eprint.iacr.org/2019/1079
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .