Lazy Modular Reduction for NTT

Abstract

The number theoretic transform (NTT) is a fundamental operation in cryptography, especially for lattice-based cryptographic schemes. This paper introduces LazyNTT, a novel method that reduces the number of Montgomery multiplications required in the NTT computation by replacing some of them with standard multiplication without modular reduction. This approach enhances the performance of the NTT computation and modular polynomial multiplication in lattice-based cryptographic schemes. The proposed LazyNTT can be generalized by increasing the number of standard multiplications. The experimental results show that the proposed LazyNTT improves the cycle counts of the NTT by up to (Formula presented.) and (Formula presented.), respectively, by allowing two and one standard multiplications. © 2024 by the authors.