PaReNTT: Low-Latency Parallel Residue Number System and NTT-Based Long Polynomial Modular Multiplication for Homomorphic Encryption

Weihang Tan, Sin-Wei Chiu, Antian Wang, Yingjie Lao, Keshab K. Parhi

TL;DR

PaReNTT is a high-performance hardware architecture designed to accelerate the massive polynomial multiplications required for Homomorphic Encryption (HE). By eliminating intermediate data-shuffling buffers and using "shift-and-add" friendly prime numbers, the authors achieve a staggering 49.2x reduction in latency and over a 90% reduction in area-time complexity compared to previous state-of-the-art designs.

What Problem Does This Paper Address?

Homomorphic Encryption (HE) is the "holy grail" of privacy, allowing servers to process data without ever decrypting it. However, HE is notoriously slow. The primary bottleneck is long polynomial modular multiplication.

In HE schemes like BFV or CKKS, polynomials can have thousands of coefficients (e.g., $n=4096$), and each coefficient can be hundreds of bits long. To handle this, researchers use the Number-Theoretic Transform (NTT)—a version of the Fast Fourier Transform for integers—and the Residue Number System (RNS) to break large numbers into smaller, parallel chunks.

The "gap" addressed here is twofold:

  1. The Shuffling Bottleneck: Standard parallel NTT implementations require a "shuffling circuit" or buffer between the forward and inverse transforms to reorder data, which adds significant latency and consumes hardware area.
  2. The Complexity of Modular Reduction: Performing modular arithmetic on large primes usually requires expensive hardware multipliers.

Methods

The authors introduce PaReNTT, which utilizes three main innovations:

  • Buffer-less Cascaded NTT-iNTT: The team designed specific "folding sets" (scheduling patterns) for the parallel NTT and inverse NTT (iNTT). By carefully aligning these schedules, the output of the point-wise multiplication can be fed directly into the iNTT without any intermediate reordering or buffering.
  • Special Moduli Selection: Instead of random primes, they perform an exhaustive search for "CRT-friendly" and "NTT-compatible" primes that can be expressed as a few signed powers-of-two (e.g., $2^v - 2^{v1} \pm 1$).
  • Shift-Add Units (SAU): Because of the special primes chosen above, the authors replaced traditional, area-heavy hardware multipliers in the pre-processing (Chinese Remainder Theorem) stages with simple bit-shifters and adders. This significantly reduces the "Area-Time Product" (ATP).

Datasets

As this is a hardware architecture paper, it does not use traditional machine learning datasets. Instead, the design was evaluated using:

  • Target Platform: Xilinx Virtex Ultrascale+ FPGA.
  • Parameters: Polynomial degree $n=4096$ and a 180-bit coefficient modulus $q$.
  • Benchmarks: The design was compared against the previous benchmark architecture by Roy et al. (2019).

Key Insights and Ideas

  • The "Aha" Moment on Scheduling: The authors realized that bit-reversed scheduling, while well-known for eliminating buffers in single transforms, could be mathematically extended to a parallel NTT-iNTT cascade. This allows for a completely feed-forward, pipelined architecture.
  • Hardware-Math Co-design: By restricting the mathematical search space for primes to those with low Hamming weights, they effectively "offloaded" the computational complexity from the hardware (DSPs) to the logic (LUTs), which is much more efficient on FPGAs.
  • Factorization for Scaling: To prevent the "Shift-Add Units" from becoming too deep (and thus slow) as the number of primes increases, they proposed a factorization approach that breaks the computation into smaller, manageable blocks.

Key Results

The PaReNTT architecture was implemented and tested at 240 MHz. Compared to the prior state-of-the-art:

  • Latency: Reduced by a factor of 49.2.
  • Area-Time Product (ATP): The ATP for Look-Up Tables (LUTs) was reduced by 89.2%, and for Digital Signal Processors (DSPs) by 92.5%.
  • Efficiency: For a 180-bit coefficient and $n=4096$, the 2-parallel architecture consumes only 6.3 Watts, making it highly suitable for high-throughput cloud applications.

Limitations and Future Work

  • Parameter Specificity: The current optimization is highly tuned for specific polynomial degrees and bit-widths. While the method is generalized, the specific hardware "folding sets" must be re-calculated if the encryption parameters change significantly.
  • Future Directions: The authors suggest integrating this multiplier into full-scale HE libraries (like SEAL or Lattigo) to evaluate the system-level speedup for specific applications like private neural network inference or federated learning. They also aim to explore how this architecture handles different HE schemes like BGV and CKKS, which have slightly different modular requirements.

Summary updated

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). Parallel NTT and iNTT architectures are proposed to reduce the number of clock cycles to process the polynomials. Chinese remainder theorem (CRT) is used to decompose the modulus into multiple smaller moduli. Our proposed architecture, namely PaReNTT, makes three novel contributions. First, cascaded parallel NTT and iNTT architectures are proposed such that any buffer requirement for permuting the product of the NTTs before it is input to the iNTT is eliminated. This is achieved by using different folding sets for the NTTs and iNTT. Second, a novel approach to expand the set of feasible special moduli is presented where the moduli can be expressed in terms of a few signed power-of-two terms. Third, novel architectures for pre-processing for computing residual polynomials using the CRT and post-processing for combining the residual polynomials are proposed. These architectures significantly reduce the area consumption of the pre-processing and post-processing steps. The proposed long modular polynomial multiplications are ideal for applications that require low latency and high sample rate such as in the cloud, as these feed-forward architectures can be pipelined at arbitrary levels. Pipelining and latency tradeoffs are also investigated. Compared to a prior design, the proposed architecture reduces latency by a factor of 49.2, and the area-time products (ATP) for the lookup table and DSP, ATP(LUT) and ATP(DSP), respectively, by 89.2% and 92.5%. Specifically, we show that for $n=4096$ and a 180-bit coefficient, the proposed 2-parallel architecture requires 6.3 Watts of power while operating at 240 MHz, with 6 moduli, each of length 30 bits, using Xilinx Virtex Ultrascale+ FPGA.
BibTeX
@article{tan2024parentt,
  author = {Weihang Tan and Sin-Wei Chiu and Antian Wang and Yingjie Lao and Keshab K. Parhi},
  title = {{PaReNTT: Low-Latency Parallel Residue Number System and NTT-Based Long Polynomial Modular Multiplication for Homomorphic Encryption}},
  journal = {IEEE Trans. Inf. Forensics Secur.},
  year = {2024},
  url = {https://openreview.net/forum?id=SNSbyuYElj},
}

Loading related content...

Figure