Area-time efficient pipelined number theoretic transform for CRYSTALS-Kyber

Area of Science:

• Cryptography and Security
• Hardware Acceleration
• Post-Quantum Cryptography

Background:

• CRYSTALS-Kyber, a NIST-standardized quantum-resistant algorithm, faces performance bottlenecks in polynomial multiplication.
• Number Theoretic Transform (NTT) is crucial for Kyber's polynomial multiplication, necessitating efficient hardware implementations.

Purpose of the Study:

• To develop and evaluate novel parallel FPGA architectures for accelerating CRYSTALS-Kyber's NTT-based polynomial multiplication.
• To optimize resource utilization and enhance the performance of Kyber's core computational tasks.

Main Methods:

• Implementation of two parallel architectures using the Multi-Path Delay Commutator (MDC) approach on FPGAs.
• Adoption of resource sharing for Polynomial Multiplication (PWM) operations via MDC NTT/INTT architecture.
• Application of architectural optimizations including FIFO-based memory, LUT-based modular multipliers, and distributed-ROM for twiddle factors.

Main Results:

• Developed BRAM and DSP-free designs achieving a 68% improved area-time product for PWM operations.
• The two-parallel MDC architecture demonstrated superior performance compared to state-of-the-art designs, utilizing 29% fewer resources.
• Successful implementation on a Xilinx Artix-7 XC7A100T-3 device using Verilog HDL.

Conclusions:

• The proposed MDC-based parallel architectures offer significant improvements in area-time product and resource efficiency for CRYSTALS-Kyber.
• These optimized designs provide a viable solution for high-performance, resource-constrained implementations of post-quantum cryptography algorithms.
• The study highlights the effectiveness of architectural-level optimizations for accelerating cryptographic primitives on FPGAs.