埃米纳姆（Eminem）：高效FPGA实现混合RadIx NTT硬件加速器，用于NIST的后量子密码学项目Falcon、Dilithium和HAWK

《ACM Transactions on Reconfigurable Technology and Systems》：EMINEM: Efficient FPGA Implementation of Mixed-RadIx NTT Hardware AccElerators for NIST Post-QuantuM Cryptography Falcon, Dilithium, and HAWK

针对NIST后量子密码标准中512长度格基密码学方案Falcon和HAWK的NTT运算瓶颈，提出混合基数NTT硬件加速框架EMINEM。通过创新性融合Radix-4与Radix-2/4混合策略，结合新型内存访问模式与蝶形结构优化，实现512长度NTT运算时间复杂度接近纯Radix-4方案，同时降低资源消耗达18.6%。经FPGA实现验证，在Xilinx Zynq-7020平台分别达到3.21TOPS@25MHz(256/1024)和2.13TOPS@25MHz(512)的运算性能，较传统Radix-2方案提升3.2-6.8倍。

　　

摘要

量子计算的出现对现代密码学构成了重大威胁。为应对这一挑战，美国国家标准与技术研究院（NIST）启动了PQC（后量子密码学）标准化进程，并选出了几种算法（其中一些仍在进一步标准化过程中进行评估）。在这些方案中，基于格的后量子密码学（PQC）作为一种有前景的方法引起了实施社区的广泛关注，尤其是在硬件平台方面。值得注意的是，现场可编程门阵列（FPGA）作为一种便捷的硬件实现平台，不仅得到了NIST的重视，也得到了研究界的关注，这从NIST的相关建议以及近期发表的众多研究作品中可见一斑。

本工作延续了开发新型FPGA实现PQC的现有趋势。值得一提的是，这些基于NIST格的PQC算法中的多项式乘法可以通过数论变换（NTT）来提高效率。然而，目前仍缺乏适用于不同多项式大小的新型通用NTT方法。例如，在$n=512$（Falcon和HAWK算法）中，现有的方法大多局限于Radix-2 NTT（其他方法如Radix-4或Radix-8无法直接应用）。为了填补这一研究空白，本文提出了一种新颖的设计框架——高效混合基数NTT硬件加速器（EMINEM），专门针对NIST的后量子密码学算法进行优化。我们的设计在多项式大小为256和1,024时采用Radix-4算法，在长度为512时采用混合Radix-2/4策略，实现了与其他纯Radix-4算法相当的性能。我们的贡献包括：(i) 为多项式大小为256、512和1,024提出了一种通用的Radix-4/混合基数NTT算法；(ii) 利用新的内存访问模式和一些优化技术设计了一种高效的NTT硬件加速器；(iii) 开发了两种不同的蝶形架构，分别实现纯Radix-4时间复杂度和低资源消耗；(iv) 详细的实现和比较证明了所提出设计策略的优越性能。总体而言，该策略使得混合基数NTT能够在NIST的目标算法中高效应用，克服了传统Radix-2方法的局限性，尤其是在处理长度为512的NTT设计时。这一设计为PQC标准的FPGA加速带来了重大进展。