面向CRYSTALS-Kyber的自适应FPGA混合基数NTT架构及其经典与量子评估

《Applied Sciences》：Adaptive FPGA-Based Mixed-Radix NTT Architectures with Classical and Quantum Evaluation for CRYSTALS-Kyber

　　

大规模量子计算机即将带来的威胁推动了后量子密码学（PQC）的部署。作为领先的基于格（lattice-based）密钥封装机制（KEM），CRYSTALS-Kyber高度依赖数论变换（NTT）运算，而这仍然是其性能与资源消耗方面的主要瓶颈。本文提出了一个面向CRYSTALS-Kyber的跨平台NTT评估框架，其核心是一种基于FPGA的自适应混合基数加速器，支持radix-2、radix-4和radix-8配置，同时结合了用于比较的经典实现以及探索性的量子电路原型。经典评估表明，迭代式Cooley–Tukey实现优于基于矩阵的基线实现（正向NTT约快3.6×，逆向NTT约快6.3×）。在Qiskit中实现的量子原型展示了基于量子傅里叶变换（QFT）的NTT构造概念验证，该结果强调了电路深度增长与噪声敏感性，而非实际硬件加速能力。所提出的FPGA设计基于Xilinx Virtex UltraScale+平台，采用自适应基数控制器、基于查找表的旋转因子（twiddle factor）管理以及Montgomery/Barrett模算术。Montgomery约简在时序与面积折衷方面表现更优，估计最大工作频率可达231.48 MHz，且在radix-2配置下仅使用5个数字信号处理器（DSP）。同时，radix-2在资源/性能平衡方面表现最佳，其时延约为32,804个时钟周期。该混合方法在保持Kyber基于模块学习带误差（MLWE）安全性的同时，兼顾了近期FPGA实现的实用性与长期量子潜力。实验结果与比较分析表明，与近期基于高层次综合（HLS）的NTT加速器相比，该自适应设计显著降低了资源使用与时序开销。

本文发表于《Applied Sciences》，围绕CRYSTALS-Kyber中数论变换（NTT）这一核心瓶颈，系统评估了经典软件、量子电路与FPGA硬件三类实现路径，重点提出了一种面向后量子密码学（PQC）的自适应FPGA混合基数NTT架构。研究背景在于：随着大规模量子计算的发展，传统公钥密码体制如RSA与椭圆曲线密码（ECC）面临Shor算法攻击风险，促使美国国家标准与技术研究院（NIST）推进后量子密码标准化。CRYSTALS-Kyber作为入选标准化的密钥封装机制（KEM），建立在模块学习带误差（MLWE）困难性之上，具有效率高、可扩展性好、抗量子攻击等优势。然而，Kyber中的多项式乘法严重依赖NTT，而NTT虽然可将复杂度由O(n²)降至O(n log n)，其实际部署仍受算法复杂度、FPGA资源消耗以及量子实现可行性不足等因素限制。现有研究多聚焦于单一基数结构、特定硬件优化或单一计算域，缺乏在统一框架下对多种NTT实现策略进行系统比较的工作。因此，开展这项研究的必要性在于建立统一的跨平台评估体系，明确不同实现路线在时延、资源利用率、扩展性与长期潜力上的权衡，为Kyber的工程化部署提供依据。

研究人员围绕这一问题构建了一个跨平台NTT评估框架，并将自适应FPGA混合基数架构作为主要贡献。该框架同时纳入经典实现与量子原型，用于对比分析不同范式下的NTT行为。研究结论表明：在经典域，迭代式Cooley–Tukey（CT）实现显著优于基于矩阵的直接变换；在量子域，基于量子傅里叶变换（QFT）的NTT电路可完成概念验证，但当前主要受制于电路深度、噪声与模拟开销，尚不具备Kyber规模部署条件；在硬件域，基于Xilinx Virtex UltraScale+的自适应混合基数FPGA设计，通过自适应基数控制、查找表（LUT）旋转因子管理以及Montgomery/Barrett模约简，实现了较优的时序—面积折衷，其中radix-2配合Montgomery约简表现最佳。论文的重要意义在于：该研究并非提出新的NTT算法，而是在统一评估框架中系统揭示不同实现策略的工程代价与优势，证明在当前阶段FPGA仍是Kyber中NTT加速的最现实路径，同时为未来量子可行性研究保留接口与比较基线。

在技术方法上，研究人员首先使用Python实现线性卷积、正包裹卷积与负包裹卷积，以验证多项式卷积及循环约简的数学正确性；随后构建经典NTT基线，包括基于模指数运算的矩阵法，以及采用CT蝴蝶实现正向NTT、采用Gentleman–Sande（GS）蝴蝶实现逆向NTT的迭代法，并利用扩展欧几里得算法求模逆。在量子部分，研究人员基于Qiskit搭建门级与QFT型加减乘算术模块，并在Qiskit Aer经典模拟后端与噪声模型下，对小规模参数进行QFT型NTT可行性验证。在硬件部分，研究人员面向Xilinx Virtex UltraScale+平台设计支持radix-2/radix-4/radix-8的自适应混合基数NTT架构，采用BRAM循环分区、LUT旋转因子存储、Barrett与Montgomery约简、HLS流水线与循环展开等策略进行综合评估。样本并非生物队列，而是以Kyber参数体系与缩减版量子玩具参数为测试对象。

在研究结果部分，论文依照不同模块展开分析。

5.1. Classical NTT Evaluation
该部分通过Python平台比较了迭代式CT实现与矩阵式NTT实现。研究人员指出，矩阵法中每个输出系数依赖全部输入系数，计算代价为O(n²)；而迭代式CT NTT通过递归蝴蝶分解将复杂度降至O(n log n)。实验结果表明，CT方法在正向NTT中的执行时间为752.8 μs，而矩阵法为2728.5 μs；在逆向NTT中，CT方法为432.2 μs，而矩阵法为2723.4 μs。通过对16至200阶多项式的缩放实验，研究人员进一步说明CT实现的时间增长趋势接近线性，而矩阵法呈二次增长。该结果证明了结构化迭代NTT相对直接矩阵构造的算法效率优势。作者同时强调，这些Python实验主要用于正确性验证、复杂度说明与基线比较，并非面向实际Kyber部署的软件性能基准。

5.2. Quantum NTT Evaluation
该部分基于Qiskit qasm simulator对QFT型NTT电路进行可行性评估。研究人员由于受限于量子比特数量、电路深度、相干时间与模拟器扩展性，只在小规模多项式向量与简化模参数下进行实验，例如对小型输入向量执行QFT型模算术与递归蝴蝶构造。结果显示，量子NTT在经典模拟环境中明显慢于经典CT实现，且内存消耗更高。其主要开销来自递归蝴蝶带来的高电路深度、多量子比特门的保真度问题、量子态表示的指数增长以及辅助寄存器需求。引入噪声模型后，研究人员观察到随着电路深度增加，尤其在模指数运算阶段，退相干显著降低电路精度。该部分结论是：量子NTT目前并不适用于大规模密码负载，但可作为QFT型NTT构造的概念验证，为未来硬件成熟后的量子并行实现提供方法学基础。

5.3. FPGA-Based Adaptive Radix NTT
这是全文核心结果。研究人员在Amazon AWS云平台上的Xilinx Virtex UltraScale+ FPGA（xcvu9p-fsgd2104-3-e）上，利用Vivado Design Suite 2020.2与HLS优化，对自适应混合基数NTT进行综合与评估。结果表明，Montgomery约简在所有基数配置下都优于Barrett约简，其时钟周期为4.32–5.55 ns，而Barrett约简为6.83–8.64 ns，对应的最大工作频率最高可达231.48 MHz。时延方面，radix-2结合Montgomery约简的结果为32,804个周期，而Barrett约简下为65,571个周期。资源利用方面，Montgomery方案在DSP、LUT和触发器（FF）占用上均低于Barrett，而BRAM使用量保持为4个块。虽然从理论上更高基数可减少变换级数，例如N = 256时radix-2需要8级、radix-4需要4级、radix-8约需3级，但在该HLS实现中，radix-4与radix-8由于蝴蝶单元更复杂、资源共享更强、旋转因子调度更困难、启动间隔（initiation interval）更高，反而带来更高的周期时延。其中启动间隔从radix-2的1增加到radix-4的3和radix-8的6，抵消了理论级数减少的优势。因此，研究人员得出结论：在面向Kyber的该实现框架下，radix-2配合Montgomery约简提供了最佳资源—时延折衷。

5.4. Comparative Analysis
该部分将所提架构与已有NTT加速器进行比较。研究人员指出，所提设计仅需5个DSP，显著低于文献中36个DSP与26个DSP的报告值，LUT与FF占用也明显低于部分已有方案。在时钟性能上，该设计实现了4.322 ns时钟周期与231.48 MHz估计频率，优于多项当代FPGA NTT加速器。研究人员还总结了与既有工作的结构差异：不同于固定基数架构，本文方案支持radix-2、radix-4、radix-8可配置运行；不同于仅采用单一模约简策略的实现，本文在统一框架中同时评估Barrett与Montgomery方法；此外，通过LUT型旋转因子管理和资源感知调度，方案在保持竞争性频率的同时显著降低DSP使用。该部分结论说明，该设计的优势主要体现在资源效率和可配置性，而非单纯追求最高吞吐率。

5.5. Discussion
讨论部分综合了三类实现路径的意义与限制。研究人员认为，经典CT实现提供了成熟高效的算法基线，FPGA加速代表当前最实际的部署方案，而量子电路则为长期发展提供前瞻性探索，因此该混合框架兼顾了现实需求与未来潜力。与此同时，量子NTT在当前仍受限于量子比特数量、电路深度、误差传播与模拟器复杂度，尚不具备Kyber规模实用性。安全性方面，研究人员明确指出，所提出的自适应基数与混合实现策略并未改变Kyber底层的MLWE困难性，也未破坏其IND-CPA与IND-CCA2安全性质。论文也指出当前工作的边界：radix-4与radix-8在资源共享约束下未能充分发挥高基数理论优势；研究未包含针对时序、功耗与电磁泄露等侧信道攻击的专门评估；功耗及Power–Area–Timing（PAT）分析也未纳入当前范围。该讨论强调，本文更适合作为架构评估与设计空间探索，而非直接替代高度专用化的Kyber加速器。

研究结论部分指出，本文提出了一个面向CRYSTALS-Kyber的混合NTT框架，将优化后的经典算法、基于Qiskit的量子原型与自适应混合基数FPGA加速器整合于统一评估体系中。实验表明，经典迭代式CT NTT在概念性Python比较中优于朴素矩阵实现；FPGA综合结果显示，自适应基数架构在时序与面积之间实现了良好折衷，其中采用Montgomery约简的radix-2实现达到231.48 MHz估计最大频率、4.32 ns时钟周期、约32,804周期低时延以及仅5个DSP的资源消耗。量子原型则证明了基于QFT的NTT电路构建在方法上可行，但在当前硬件与模拟环境下仍受到电路深度、退相干和资源规模的严格限制。总体而言，该研究在不改变Kyber数学结构及安全保证的前提下，提出了一种兼顾资源效率、高性能与未来可拓展性的NTT解决方案，为后量子密码硬件实现与跨平台比较研究提供了系统性参考。