Efficient Number Theoretic Transform Architecture for CRYSTALS-Kyber
Khalid Javeed, David P. Gregg · IEEE Transactions on Circuits & Systems II Express Briefs · 2024
The Number Theoretic Transform (NTT) is a central primitive to compute polynomial multiplication in a finite ring for both post-quantum cryptography (PQC) and fully homomorphic encryption (FHE) schemes. This brief presents a novel, efficient NTT hardware architecture suitable for CRYSTALS-Kyber, one of the NIST PQC standards. It is based on a new novel unified butterfly unit (UBU) developed by combining interleaved multiplication, radix-4, and resource-sharing strategies. This unit computes all butterfly operations for any generic prime modulus value and is re-configurable to any modulus length. In the proposed NTT architecture, multiple UBUs are deployed, demonstrating an area-time tradeoff. UBU and NTT architectures are synthesized and implemented over the Xilinix Artix-7 FPGA platform and results are shown for different performance evaluation metrics. The implementation results show our lightweight and high-speed designs achieve up to$5.6\times $and$7\times $improvements in resource consumption and efficiency, respectively. To the authors’ knowledge, it is the first generic NTT architecture based on interleaved multiplication approaches.