A Generalized Number-Theoretic Transform for Efficient Multiplication in Lattice Cryptography

Abstract

The Number Theoretic Transform (NTT) has emerged as a powerful tool for efficiently computing convolutions of digital signals, due to its inherent advantages such as numerical stability, reliance on simple integer operations, and proven efficiency. Its applications have extended to accelerating polynomial multiplication in lattice-based cryptography. However, existing NTT multiplication algorithms impose restrictions on the underlying moduli, potentially affecting key and ciphertext sizes as well as computational overhead. Therefore, enabling NTT with small moduli holds significant potential for enhancing the overall system performance. This study introduces a novel reduction framework for NTT computation in cyclotomic rings employing field extensions. Our approach replaces the underlying polynomial ring with a two-dimensional isomorphic ring, effectively relaxing the restrictions imposed on the NTT moduli. The proposed framework is evaluated through two case studies relevant to the LAC and NTTRU lattice-based cryptographic schemes. Comprehensive theoretical analysis is provided, demonstrating the effectiveness of our approach in enabling NTT with small moduli and its potential to improve the efficiency of lattice-based cryptography.