KyberMat: Efficient Accelerator for Matrix-Vector Polynomial Multiplication in CRYSTALS-Kyber Scheme via NTT and Polyphase Decomposition

Weihang Tan, Yingjie Lao, Keshab K. Parhi

TL;DR

KyberMat is a high-performance hardware accelerator designed to speed up CRYSTALS-Kyber, a leading post-quantum cryptography (PQC) standard. By applying a novel "sub-structure sharing" technique—borrowed from digital signal processing—to matrix-vector polynomial multiplications, the authors achieved a 90% reduction in execution time and a staggering 66x improvement in throughput compared to existing state-of-the-art FPGA implementations.

What Problem Does This Paper Address?

As we move toward the era of quantum computing, traditional encryption (like RSA) becomes vulnerable. CRYSTALS-Kyber is a lattice-based Key-Encapsulation Mechanism (KEM) selected by NIST to protect data in a post-quantum world. However, Kyber is computationally "heavy."

The primary bottleneck lies in matrix-vector polynomial multiplication. To make these operations efficient, researchers use the Number Theoretic Transform (NTT), which is similar to a Discrete Fourier Transform but for integers. Even with NTT, the latest version of Kyber requires a complex "polyphase decomposition" step. Previous hardware designs were often limited to simple parallel structures and failed to optimize the repetitive calculations that occur when a single vector is multiplied by an entire matrix. This leads to high latency and low throughput, making them less ideal for high-demand environments like cloud computing.

Methods

The authors propose an algorithm-hardware co-design called KyberMat. Their approach centers on three key innovations:

  1. FIR Filter Connection: They identified a mathematical link between fast parallel Finite Impulse Response (FIR) filters and point-wise multiplication in the NTT domain. This allowed them to adapt well-known signal processing optimizations to cryptography.
  2. Sub-structure Sharing: In a matrix-vector multiplication ($u = A^T r + e$), the same vector $r$ is multiplied by every row of the matrix $A$. KyberMat exploits this by calculating intermediate values once and reusing them across multiple multiplications. This significantly reduces the total number of modular multiplications and additions required.
  3. Scalable Parallelism: Unlike prior work restricted to "two-parallel" designs, KyberMat is built to support higher levels of parallelism (e.g., four-parallel or eight-parallel). The architecture is a fully pipelined, feed-forward design, ensuring that data moves through the system with minimal stalls.

Datasets

The researchers evaluated their design using the official parameters of the CRYSTALS-Kyber scheme (specifically Kyber-512, Kyber-768, and Kyber-1024).

  • Parameters: $n=256$ (polynomial degree) and $q=3329$ (prime modulus).
  • Hardware Platform: Evaluation was performed on a Xilinx Artix-7 FPGA (AC701 kit), which is the standard benchmark platform recommended by NIST for PQC hardware.

Key Insights and Ideas

  • The Power of Transposition: By leveraging the transposition property of fast filtering structures, the authors found they could relocate expensive point-wise multiplications to occur after certain summations. This "reordering" is the secret sauce that minimizes the total count of modular multiplications.
  • Breaking the 2-Parallel Ceiling: Most existing accelerators hit a wall at 2-parallel structures. By proving that the parallelism can be arbitrary (4, 8, etc.), the authors provide a clear path for scaling performance for high-end servers.
  • Efficiency over Compactness: While some prior works focused on making the smallest possible hardware (compact designs), KyberMat prioritizes throughput-per-area. It uses more hardware resources (LUTs and DSPs) but utilizes them so efficiently that the performance gains far outweigh the area costs.

Key Results

The KyberMat accelerator was compared against several recent high-performance designs (e.g., Xing et al., Zhao et al.). For the Kyber-512 security level:

  • Execution Time: Reduced from ~19.84 µs (Xing) to just 1.00 µs (KyberMat 2-parallel) and 0.67 µs (KyberMat 4-parallel).
  • Throughput: Jumped from 0.31 Gb/s to 21.31 Gb/s (2-parallel) and 42.62 Gb/s (4-parallel)—a 66x to 131x improvement.
  • Computational Savings: The sub-structure sharing technique reduced modular multiplications by approximately 22.4% and additions by 37.2% compared to a standard parallel implementation without sharing.
  • Clock Frequency: The design achieved a high operating frequency of 222 MHz on the Artix-7 FPGA.

Limitations and Future Work

  • Resource Consumption: The high performance comes at the cost of higher FPGA resource usage (LUTs and DSPs). While efficient, it may not be suitable for extremely resource-constrained IoT devices.
  • System Integration: The paper focuses specifically on the matrix-vector multiplication accelerator. A full Kyber implementation also requires modules for Keccak (hashing) and binomial sampling; while the authors mention these, the primary focus is the multiplier core.
  • Future Directions: The authors suggest that these sub-structure sharing techniques could be extended to other lattice-based PQC schemes beyond Kyber, such as Dilithium, to achieve similar efficiency gains.

Summary updated

Abstract

CRYSTAL-Kyber (Kyber) is one of the post-quantum cryptography (PQC) key-encapsulation mechanism (KEM) schemes selected during the standardization process. This paper addresses optimization for Kyber architecture with respect to latency and throughput constraints. Specifically, matrix-vector multiplication and number theoretic transform (NTT)-based polynomial multiplication are critical operations and bottle-necks that require optimization. To address this challenge, we propose an algorithm and hardware co-design approach to systematically optimize matrix-vector multiplication and NTT-based polynomial multiplication by employing a novel sub-structure sharing technique in order to reduce computational complexity, i.e., the number of modular multiplications and modular additions/subtractions consumed. The sub-structure sharing approach is inspired by prior fast parallel approaches based on polyphase decomposition. The proposed efficient feed-forward architecture achieves high speed, low latency, and full utilization of all hardware components, which can significantly enhance the overall efficiency of the Kyber scheme. The FPGA implementation results show that our proposed design, using the fast two-parallel structure, leads to an approximate reduction of 90% in execution time $(\mu s)$, along with a $66\times$ improvement in throughput performance.
BibTeX
@inproceedings{tan2023kybermat,
  author = {Weihang Tan and Yingjie Lao and Keshab K. Parhi},
  title = {{KyberMat: Efficient Accelerator for Matrix-Vector Polynomial Multiplication in CRYSTALS-Kyber Scheme via NTT and Polyphase Decomposition}},
  booktitle = {ICCAD},
  year = {2023},
  url = {https://openreview.net/forum?id=gxao6HInMr},
}

Loading related content...

Figure