EMINEM: E fficient FPGA Implementation of M ixed-RadIx N TT Hardware Acc E lerators for NIST Post-Quantu M Cryptography Falcon, Dilithium, and HAWK

The advent of quantum computing poses a significant threat to modern cryptography. To address this challenge, the National Institute of Standards and Technology (NIST) has initiated the PQC standardization process, and several algorithms have been selected (a few are still under consideration in the additional standardization process). Among these schemes, lattice-based post-quantum cryptography (PQC) has emerged as a promising approach and garnered substantial attention from the implementation community, especially on the hardware platforms. Notably, the field-programmable gate array (FPGA) has gained considerable attention as a convenient platform for hardware implementation, not only from NIST but also from the research community, as reflected by the related recommendations from NIST and the number of works reported recently. This work follows the existing trend of developing novel FPGA implementations for PQC. It is worth mentioning that the polynomial multiplication in these NIST lattice-based PQC algorithms can be implemented with Number Theoretic Transform (NTT) for efficiency. Nevertheless, there remains a lack of novel and universal NTT methods for polynomial multiplication at different sizes. For instance, for \(n=512\) (F alcon and HAWK), the existing works are mostly limited to the Radix-2 NTT (other methods like Radix-4 or Radix-8 cannot be directly applied). To fill the research gap, this paper presents a novel design framework, i.e., E fficient M ixed-Rad I x N TT hardware acc E lerators for NIST post-quantu M cryptography (EMINEM, specially tailored for targeted schemes). Our design leverages Radix-4 for polynomial sizes of 256 and 1,024, while introducing a hybrid Radix-2/4 strategy for NTT of length 512 and achieving comparable performance to pure Radix-4 at other lengths. In total, our contributions include: (i) a generic Radix-4/Mixed-Radix NTT algorithm is proposed for \(n=256\) , 512, and 1,024; (ii) an efficient NTT hardware accelerator is designed with the help of a new memory access pattern and some optimization techniques; (iii) two types of butterfly architectures are developed to obtain pure Radix-4 time complexity and low resource usage, respectively; (iv) a detailed implementation and comparison showcase the superior performance of the proposed design strategy. Overall, the proposed strategy enables the efficient deployment of Mixed-Radix NTT in targeted NIST schemes, surpassing the limitations of the conventional Radix-2 approach for 512-length NTT designs. The proposed design offers a significant advancement in the field, facilitating efficient FPGA acceleration of PQC standards.