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