Abstract
This paper presents a low-latency hardware accelerator for modular polynomial multiplication for lattice-based post-quantum cryptography and homomorphic encryption applications. The proposed novel modular polynomial multiplier exploits the fast finite impulse response (FIR) filter architecture to reduce the computational complexity for the schoolbook modular polynomial multiplication. We also extend this structure to fast M-parallel architectures while achieving low-latency, high-speed, and full hardware utilization. We comprehensively evaluate the performance of the proposed architectures under various polynomial settings as well as in the Saber scheme for post-quantum cryptography as a case study. The experimental results show that our design reduces the computational time and area-time product by 61% and 32%, respectively, compared to the state-of-the-art designs.
Introduction
As we transition toward a post-quantum computing era, traditional encryption methods like RSA and Elliptic Curve Cryptography (ECC) are becoming increasingly vulnerable. Lattice-based cryptography has emerged as a leading candidate for future-proof security. However, these schemes rely heavily on modular polynomial multiplication, a computationally expensive operation that often becomes the primary bottleneck in hardware implementations.
While techniques like the Number Theoretic Transform (NTT) are frequently used for acceleration, they are not universally optimal. For instance, the Saber post-quantum cryptography (PQC) scheme uses moduli that are powers-of-two, making NTT-based acceleration difficult without complex and costly transformations. This paper addresses these challenges by introducing novel hardware architectures that treat modular polynomial multiplication as a fast Finite Impulse Response (FIR) filtering problem, leveraging decades of optimization in Digital Signal Processing (DSP).
Methodology
Systolic Array Foundation
The authors first derive a weight-stationary systolic array for polynomial multiplication. By mapping the dependence graph (DG) of the multiplication operation to a systolic array, they establish a structured datapath ideal for high-performance hardware.
The researchers specifically chose a transpose-form FIR filter structure. Unlike direct-form architectures, the transpose-form offers a feed-forward datapath with a very short critical path. This architectural choice is crucial for high-speed pipelining, allowing the system to operate at higher clock frequencies without excessive hardware overhead.
Fast Parallel Filtering and Integrated Modular Reduction
To achieve even higher throughput, the authors utilize polyphase decomposition to create "Fast M-parallel" architectures. This "divide and conquer" approach significantly reduces the total number of required multiplications. For instance, their "Fast 2-parallel" algorithm reduces the complexity of a length-$n$ multiplication into three multiplications of length $n/2$, rather than the four required by standard schoolbook methods.
A key innovation in these parallel structures is the handling of modular reduction. The authors cleverly integrate the reduction process directly into the "merging" phase of the parallel filter. This eliminates the need for extra clock cycles in a separate post-processing step, ensuring that the hardware remains fully utilized throughout the operation.
Key Results and Insights
The proposed architectures were evaluated using the Saber PQC scheme as a primary benchmark on Xilinx Artix-7 and UltraScale+ FPGAs. The experimental results demonstrate significant improvements over previous high-performance designs:
- Latency Reduction: For a degree-256 modular polynomial multiplication, the Fast 4-parallel design achieved a latency of only 127 clock cycles, a 50% improvement over standard high-speed designs.
- Area-Time Efficiency: Compared to common baselines like the "Roy" design, the proposed Fast 2-parallel architecture reduced Look-Up Table (LUT) usage by 18.9% and improved the overall Area-Time Product (ATP) by nearly 40%.
- System-Level Impact: When applied to the full Saber scheme, the design reduced the total latency for Key Generation, Encapsulation, and Decapsulation by over 50%.
Conclusion and Future Work
By recognizing the mathematical symmetry between modular polynomial multiplication and discrete convolution, the authors have unlocked a suite of DSP-inspired optimizations for cryptographic hardware. The resulting architectures are not only high-performing but also highly scalable; a 2-parallel block can serve as a building block for 4-parallel or 8-parallel systems, allowing for flexible performance tuning.
Looking forward, these low-latency techniques hold great promise for Fully Homomorphic Encryption (FHE). FHE enables computation on encrypted data but is currently limited by extreme computational overhead. The efficient multiplication methods proposed here could be a vital step toward making FHE practical for real-world applications.
Summary updated