Efficient Number Theoretic Transform Architecture for CRYSTALS-Kyber

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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$5.6\times $ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$7\times $ </tex-math></inline-formula> improvements in resource consumption and efficiency, respectively. To the authors’ knowledge, it is the first generic NTT architecture based on interleaved multiplication approaches.