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

Weihang Tan, Yingjie Lao, Keshab K. Parhi

Abstract

CRYSTALS-Kyber (Kyber) is a leading post-quantum cryptography (PQC) key-encapsulation mechanism (KEM) selected for standardization. This paper addresses the optimization of Kyber architecture to meet stringent latency and throughput constraints. The primary computational bottlenecks—matrix-vector multiplication and Number Theoretic Transform (NTT)-based polynomial multiplication—are optimized through a novel algorithm-hardware co-design. By employing a sub-structure sharing technique inspired by polyphase decomposition in digital signal processing, the proposed KyberMat architecture significantly reduces computational complexity. FPGA implementation results demonstrate that this approach achieves an approximate 90% reduction in execution time and a 66-fold improvement in throughput compared to existing state-of-the-art designs.

Introduction

As quantum computing capabilities advance, traditional public-key encryption schemes like RSA and ECC become increasingly vulnerable. In response, NIST has selected CRYSTALS-Kyber, a lattice-based KEM, as a primary standard for post-quantum security. While robust, Kyber is computationally intensive, particularly regarding matrix-vector polynomial multiplications. These operations are typically accelerated using the Number Theoretic Transform (NTT), yet existing hardware implementations often suffer from high latency and limited throughput, making them suboptimal for high-demand environments like cloud infrastructure.

Methodology

The KyberMat accelerator introduces an algorithm-hardware co-design that focuses on three primary innovations to overcome these bottlenecks:

1. FIR Filter Connection

The researchers identified a mathematical link between fast parallel Finite Impulse Response (FIR) filters and point-wise multiplication within the NTT domain. By adapting signal processing optimizations to the cryptographic context, the architecture leverages well-established fast filtering structures to streamline polynomial operations.

2. Sub-structure Sharing

In the Kyber scheme, the operation $u = A^T r + e$ requires multiplying the same vector $r$ by every row of the matrix $A$. KyberMat exploits this redundancy through "sub-structure sharing." By calculating intermediate values once and reusing them across multiple row multiplications, the design reduces the total number of modular multiplications by approximately 22.4% and modular additions/subtractions by 37.2% compared to standard parallel implementations.

3. Scalable Parallelism

While many prior accelerators are restricted to two-parallel structures, KyberMat is designed for arbitrary parallelism (e.g., 4-parallel or 8-parallel). The architecture utilizes a fully pipelined, feed-forward design that ensures high-speed data movement and full hardware utilization without the stalls common in more rigid designs.

Implementation and Results

The design was evaluated on a Xilinx Artix-7 FPGA (AC701 kit), the standard benchmark platform for PQC hardware evaluation. The researchers tested the core against Kyber-512, Kyber-768, and Kyber-1024 parameters ($n=256$, $q=3329$).

Performance Metrics

Compared to recent high-performance designs (e.g., Xing et al.), KyberMat demonstrated significant gains at the Kyber-512 security level:

  • Latency: Execution time dropped from ~19.84 µs to 1.00 µs (2-parallel) and 0.67 µs (4-parallel).
  • Throughput: Performance increased from 0.31 Gb/s to 21.31 Gb/s (2-parallel) and 42.62 Gb/s (4-parallel), representing a 66x to 131x improvement.
  • Frequency: The design maintained a high operating frequency of 222 MHz.

Discussion and Limitations

KyberMat prioritizes throughput-per-area efficiency. While it consumes more Look-Up Tables (LUTs) and Digital Signal Processors (DSPs) than compact, resource-constrained designs, the performance-to-area ratio is significantly higher. This makes it particularly suitable for server-side applications and high-speed network equipment. However, the increased resource footprint may limit its utility in extremely low-power IoT devices.

Furthermore, while KyberMat optimizes the multiplier core—the primary bottleneck—a complete Kyber implementation requires additional modules for Keccak-based hashing and binomial sampling. The authors suggest that the sub-structure sharing techniques presented here are extensible to other lattice-based schemes, such as the Dilithium digital signature algorithm.

Conclusion

KyberMat represents a significant advancement in PQC acceleration. By bridging the gap between digital signal processing techniques and lattice-based cryptography, the architecture achieves unprecedented throughput and latency reductions. These optimizations provide a scalable path for implementing CRYSTALS-Kyber in high-performance computing environments, ensuring data security in the post-quantum era.

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 bottlenecks 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, 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},
}
Figure