Abstract
High-speed long polynomial multiplication is important for applications in homomorphic encryption (HE) and lattice-based cryptosystems. This paper addresses low-latency hardware architectures for long polynomial modular multiplication using the number-theoretic transform (NTT) and inverse NTT (iNTT). Chinese remainder theorem (CRT) is used to decompose the modulus into multiple smaller moduli. Our proposed architecture, namely PaReNTT, makes four novel contributions. First, parallel NTT and iNTT architectures are proposed to reduce the number of clock cycles to process the polynomials. Second, the proposed architecture eliminates the need for permuting the NTT outputs before their product is input to the iNTT, reducing latency and buffer requirements. Third, an approach to select special moduli expressed in terms of signed power-of-two terms is presented. Fourth, novel architectures for pre-processing and post-processing significantly reduce area consumption.
Introduction
Homomorphic Encryption (HE) is often described as the "holy grail" of data privacy, as it allows for the processing of data in its encrypted state. However, the computational cost of HE is a significant barrier to its widespread adoption. The primary bottleneck in HE schemes like BFV or CKKS is the modular multiplication of long polynomials, which can involve thousands of coefficients, each hundreds of bits long.
To manage this complexity, researchers typically employ the Number-Theoretic Transform (NTT)—an integer-based variant of the Fast Fourier Transform—and the Residue Number System (RNS) to parallelize computations. Despite these techniques, standard parallel hardware implementations face two major hurdles: the "shuffling bottleneck," where data must be reordered between transform stages, and the high hardware cost of modular reduction for large primes.
Proposed Architecture: PaReNTT
The PaReNTT architecture introduces several innovations to overcome these performance and area constraints.
Low-Complexity NTT and iNTT Architectures
PaReNTT utilizes highly optimized parallel NTT and iNTT units. By processing multiple coefficients simultaneously, the architecture reduces the total number of clock cycles required for polynomial multiplication. The signal flow is designed to be low-complexity, minimizing the hardware resources needed for each butterfly operation.
Eliminating the Shuffling Bottleneck
In traditional parallel NTT-iNTT pipelines, a shuffling circuit or large buffer is required to reorder the outputs of the forward NTT before they can be processed by the point-wise multiplier and subsequently the iNTT. PaReNTT eliminates this requirement by carefully aligning the scheduling patterns, or "folding sets," of the parallel units. This allows the output of the point-wise multiplication to be fed directly into the iNTT without intermediate reordering. This innovation reduces latency by $n/4$ clock cycles and eliminates a significant amount of buffer memory.
Special Moduli Selection and Shift-Add Units
Instead of using arbitrary primes, the authors selected "CRT-friendly" and "NTT-compatible" primes that can be represented as a small number of signed powers-of-two. This mathematical choice allows the replacement of area-intensive hardware multipliers in the pre-processing (CRT) and post-processing stages with simple bit-shifters and adders, known as Shift-Add Units (SAU). To maintain performance as the number of primes scales, a factorization approach is used to keep the depth of these units manageable.
Experimental Results
The PaReNTT architecture was implemented on a Xilinx Virtex Ultrascale+ FPGA and benchmarked against previous state-of-the-art designs. Operating at 240 MHz for a polynomial degree $n=4096$ and a 180-bit modulus, PaReNTT achieved the following:
- Latency Reduction: A staggering 49.2x reduction in latency compared to the benchmark architecture.
- Area Efficiency: The Area-Time Product (ATP) for Look-Up Tables (LUTs) was reduced by 89.2%, and for Digital Signal Processors (DSPs) by 92.5%.
- Power Consumption: The 2-parallel architecture consumes only 6.3 Watts, demonstrating high efficiency for high-throughput cloud applications.
Conclusion
PaReNTT represents a significant step forward in hardware acceleration for Homomorphic Encryption. By co-designing the hardware architecture with the underlying mathematical parameters, the authors successfully eliminated major bottlenecks in polynomial multiplication. The resulting feed-forward, pipelined architecture offers high throughput and extremely low latency, making it ideal for real-time privacy-preserving applications. Future work will focus on integrating this architecture into widely used HE libraries and evaluating its impact on complex tasks like private neural network inference.
Summary updated