Low-Latency VLSI Architectures for Modular Polynomial Multiplication via Fast Filtering and Applications to Lattice-Based Cryptography

Weihang Tan, Antian Wang, Yingjie Lao, Xinmiao Zhang, Keshab K. ParhiarXiv 2021 · arXiv · OpenReview

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 dependence graph (DG) for a degree-4 modular polynomial multiplication, mapped to a systolic array.

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.

The Fast M-parallel architecture for modular polynomial multiplication, featuring integrated modular reduction and pipelining.

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

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.
BibTeX
@misc{tan2021low,
  author = {Weihang Tan and Antian Wang and Yingjie Lao and Xinmiao Zhang and Keshab K. Parhi},
  title = {{Low-Latency VLSI Architectures for Modular Polynomial Multiplication via Fast Filtering and Applications to Lattice-Based Cryptography}},
  year = {2021},
  eprint = {2110.12127},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2110.12127},
}
Figure