Number Theoretic Transform Accelerates Lattice-based Encryption Via Quasilinear Polynomial Multiplication

The discrete Fourier Transform decomposes signals into their constituent frequencies, and a related mathematical tool, the Number Theoretic Transform, offers powerful advantages for modern cryptography. Banhirup Sengupta from the Tata Institute of Fundamental Research, Peenal Gupta from PinakashieldTech OÜ, and Souvik Sengupta from IONOS SE, demonstrate how this transform operates on groups and finite fields, using polynomials in place of traditional sine waves. Their work introduces fast versions of cyclic and negacyclic convolutions based on the Number Theoretic Transform, significantly reducing the complexity of polynomial multiplication, and paving the way for more efficient lattice-based encryption schemes and potentially, homomorphic encryption. This advance addresses a critical need for faster and more secure cryptographic methods in an increasingly data-driven world.

Fast NTT significantly reduces the complexity of polynomial multiplication, improving efficiency from quadratic to quasilinear time. This advancement is crucial for lattice-based cryptography, a promising approach to post-quantum cryptographic schemes offering resilience against attacks from both classical and quantum computers.

This field depends on the mathematical properties of lattices, regular arrangements of points in space, to build cryptographic tools. The speed of polynomial multiplication directly impacts the efficiency of many lattice-based schemes, making NTT a vital component. Traditional polynomial multiplication has a time complexity of O(n²), becoming inefficient for large polynomials. NTT offers a solution by transforming polynomials from a coefficient representation to a frequency representation over a finite field, leveraging the properties of finite fields to perform multiplication in the frequency domain as a much faster operation. An inverse NTT then transforms the result back to the coefficient domain, reducing the time complexity to O(n log n) through a divide-and-conquer approach.

NTT relies on carefully chosen finite fields to ensure efficient transforms and inverse transforms, utilizing primitive roots of unity within the finite field. Algorithms like Cooley-Tukey and Gentleman-Sande are optimized for different orderings, utilizing the divide-and-conquer strategy and employing ‘butterflies’ to combine partial results. NTT is crucial for the efficiency of lattice-based cryptographic schemes, such as Kyber, Falcon, and Dilithium, which rely heavily on polynomial arithmetic and the Module Learning With Errors (Module-LWE) problem. The NTT, analogous to the Discrete Fourier Transform but operating on polynomials over finite fields, enables efficient polynomial multiplication by reducing its complexity from quadratic to quasilinear time. Researchers introduced concepts of cyclic and negacyclic convolutions, developing both NTT and its inverse, alongside fast algorithms to accelerate these processes. Calculations with NTT require specific properties of the modulus, ‘q’, the number used for the remainder after division.

For NTT to function, an n-th root of unity must exist within the integer ring modulo q. Furthermore, for negacyclic convolution, essential for certain cryptographic applications, both an n-th and a 2n-th root of unity must exist within the same ring. Theorems were established defining the conditions for the existence of these roots of unity, ensuring successful NTT implementation. Utilizing the periodicity and symmetry properties of the 2n-th root of unity, scientists developed algorithms like the Cooley-Tukey and Gentleman-Sande methods, which decompose the NTT calculation into smaller, manageable steps, significantly speeding up the process. By leveraging techniques similar to the Discrete Fourier Transform but adapted for finite fields, NTT achieves a significant reduction in computational complexity, moving from quadratic time to quasilinear time complexity through a divide-and-conquer approach. The practical implications of this work are considerable, particularly within the field of lattice-based cryptography. NTTs are already widely implemented in prominent post-quantum cryptography (PQC) algorithms like Kyber and Falcon, and the research highlights further potential for optimization. For example, the authors demonstrate how direct sampling in the NTT representation can substantially reduce the number of required transforms in signature schemes, such as Dilithium. While the specific gains achieved depend on the parameters of the cryptographic scheme being used, future research could explore further optimizations tailored to specific applications and investigate the potential for NTTs in other areas beyond cryptography where efficient polynomial multiplication is crucial.