《Sci》：Barrett Modular Multiplication Optimization for Accelerating Number Theoretic Transform
编辑推荐：
后量子格基方案的实际可行性对于其现实应用至关重要。集成这些方案需要通过硬件、软件和算法优化实现高效实施，以达到所需的速度和资源能力。本文旨在通过加速数论变换（NTT/INTT）来改进格基密码中的算术运算。研究人员通过将蝶形单元内的旋转因子模乘（该变换的主要瓶颈
后量子格基方案的实际可行性对于其现实应用至关重要。集成这些方案需要通过硬件、软件和算法优化实现高效实施，以达到所需的速度和资源能力。本文旨在通过加速数论变换（NTT/INTT）来改进格基密码中的算术运算。研究人员通过将蝶形单元内的旋转因子模乘（该变换的主要瓶颈）替换为源自Barrett约简的常量模乘，对此进行了优化。研究人员引入了两种常量乘法器：常量Barrett乘法器以及所提出的截断模长常量Barrett（TMSCB）变体，后者将每个旋转因子常数与其倒数一起预计算，消除了Barrett算法中的数据依赖性，并实现了面积-时间权衡。研究人员针对所提出的常量模乘，与经典Barrett乘法进行了全面评估，包括分析复杂度分析以及使用FPGA硬件设计的实验定量分析。所提出的优化技术被部署在针对ML-DSA和Falcon参数集的NTT/INTT硬件设计中，并实现了DSP核的最优利用。与最先进的ML-DSA NTT实现进行性能比较显示，采用单蝶形和双蝶形单元时，执行时间分别提升了46.73%和29.82%，面积资源分别减少了17%和35.4%。在Falcon上，研究人员的设计实现了至少27.6%的执行时间提升，并在多种蝶形配置下实现了面积节省。这些结果验证了常量Barrett优化技术在加速NTT/INTT方面的有效性，为其他应用中更高效的实现铺平了道路。
**论文解读：基于常量Barrett模乘优化的NTT加速研究**
**一、研究背景与动机**
1994年Shor算法的提出，证明了在足够大规模量子计算机问世的前提下，当前公钥密码体系所依赖的整数分解与离散对数难题可在多项式时间内求解，这给现有网络安全基础设施带来了根本性威胁。为应对这一量子计算时代的新兴威胁，美国国家标准与技术研究院(NIST)启动了后量子密码(PQC)标准化竞赛。在众多抗量子候选方案中，格基密码凭借其基于NP困难问题的安全性证明（既能抵抗经典计算机攻击，也能抵抗量子计算机攻击）以及基于整数上简单线性代数矩阵/向量运算所体现的高度实用性，成为了突出的选择。在NIST数字签名赛道中，CRYSTALS-Dilithium被选为主要候选方案，Falcon也在考量之列，两者均为格基方案。源自最新CRYSTALS-Dilithium规范的FIPS 204（ML-DSA）标准的发布，标志着格基密码正迅速成为广泛应用的核心数学框架。
然而，在现实应用中实现格基方案面临严峻挑战：其计算开销主要源于大量的多项式乘法运算。为提升效率，这些乘法通常利用数论变换(NTT)在频域中执行。因此，探索NTT在这些方案中的硬件设计空间，是实现格基密码实际部署的前提条件。在基于NTT的多项式乘法中，模乘运算可分为两类：一类是操作数为预计算常量旋转因子的旋转因子乘法，另一类是双操作数均为变量的点乘。由于旋转因子运算占据了绝大多数乘法操作，而点乘操作数量相对较少，因此针对旋转因子情况研究常量模乘是一种务实的优化途径。主流的模乘方法包括Montgomery、Barrett和特殊形式的K-RED，其中Barrett方法将乘法与约简分离。近年出现的常量Barrett方法在某一操作数固定时合并了乘法与约简过程，对NTT计算尤为适用。然而，如何将常量操作数的高效性与处理任意模数的灵活性相结合，仍是核心研究挑战。
**二、研究内容与结论**
针对上述挑战，本文开展了以下研究：首先，提出了两种用于旋转因子乘法的常量模乘算法——常量Barrett乘法器以及新提出的截断模长常量Barrett(TMSCB)变体。TMSCB算法将中间运算的位宽严格限制在模数位宽n比特以内，避免了常量Barrett所需的2n比特宽数据通路，同时至多保留一步最终校正。两种算法均通过将每个旋转因子与其预计算的倒数配对存储，消除了运算间的数据依赖性。其次，研究人员在三个层面进行了全面评估：算法运算复杂度的分析比较、统一框架下独立FPGA乘法器的对比实验，以及完整NTT/INTT实现的硬件性能验证。独立对比中，模数q被视为变量以避免特定模数的优化偏差；完整架构则采用固定的ML-DSA和Falcon参数集。实验结果表明，所提算法在面积-时间乘积指标上具有显著优势。在NTT/INTT硬件集成中，TMSCB算法被用于ML-DSA参数集（q=8,380,417，n=256），常量Barrett乘法器被用于Falcon参数集（q=12,289，n=512或1024），两者均部署在Xilinx UltraScale+ FPGA上并优化利用了DSP48E2片内资源。实验结果显示，与最先进的ML-DSA NTT实现相比，采用单蝶形和双蝶形单元时执行时间分别提升46.73%和29.82%，面积分别减少17%和35.4%；Falcon实现则至少获得27.6%的执行时间提升并在所有蝶形配置下实现面积节省。这些结果验证了常量Barrett优化技术对加速NTT/INTT的有效性。该研究成果发表于《Sci》期刊。
**三、主要关键技术方法**
研究人员采用了如下关键技术方法：（1）提出TMSCB算法，将模乘中间数据通路截断至模数位宽n比特，通过预计算常量b与模数q的合并倒数R，消除经典Barrett算法的数据依赖；（2）在Xilinx Artix-7 FPGA上建立统一组合逻辑评估框架，对不同位宽（含n=64）的三种算法进行对比分析；（3）在Xilinx UltraScale+ Kintex FPGA上实现完整NTT/INTT硬件架构，采用基于DSP48E2片内乘法器与后加法器的高效流水线设计，将旋转因子及其倒数拼接存储于同一ROM地址以消除额外存储访问周期；（4）利用ML-DSA（q=8,380,417处）和Falcon（q=12,289处，含Falcon-512 n=512与Falcon-1024 n=1024）两套参数集进行系统级验证。
**四、研究结果**
**（一）分析复杂度对比**：在离线预计算阶段，经典Barrett的倒数R仅依赖q，可重复使用；两种常量Barrett算法在b或q变化时均需重新计算R，其中常量Barrett需存储2n比特的R，而TMSCB仅需n比特。在整数乘法步骤中，经典与常量Barrett均需标准n比特乘法器产生2n比特乘积，而TMSCB采用截断乘法将结果限制在n比特，减少约一半的部分积操作。在乘以q的步骤中，TMSCB亦将其截断至n比特，减少了减法运算宽度，但新增了一个最多执行一次的条件减法步骤以保证结果落在[0,q)区间。
**（二）独立FPGA乘法器对比**：在Artix-7 FPGA上的均匀组合逻辑框架测试表明，TMSCB乘法器相比常量Barrett和经典Barrett方法持续使用更少的LUT；在寄存器用量上，TMSCB相比常量Barrett稳定改善了16.67%，这源于算法优化带来的存储需求减少。在速度方面，两种常量Barrett乘法器均优于经典方法，因为消除了数据依赖并支持前两步并行执行。当n较小时，常量Barrett快于TMSCB，但随着n增大，TMSCB反超——因为小位宽下条件语句成为关键路径瓶颈，而大位宽下乘法复杂度占据主导。面积-时间乘积指标显示，TMSCB的优势随输入位宽n增大而愈发显著。
**（三）NTT/INTT完整实现对比**：在ML-DSA参数集下，采用TMSCB的蝶形单元是NTT/INTT模块中资源最密集的部分，单蝶形设计可达533MHz。与Li等人（K-RED）、Derya等人（Montgomery）和Mert等人（Montgomery）等可扩展迭代架构相比，本设计在执行时间和面积上均实现大幅领先。例如，针对ML-DSA，本设计单蝶形配置执行时间为2.20μs、等效切片数(ENS)为568，而Derya等人为11.26μs/ENS 1429，Mert等人为8.77μs/ENS 1475。针对Falcon-512，本设计执行时间6.01μs、ENS 625，优于Derya等人的22.09μs/ENS 1429；针对Falcon-1024，本设计8蝶形配置达1.71μs/ENS 2938，而Mert等人为41.28μs/ENS 1654，Li等人虽以16蝶形实现1.72μs但ENS高达10511，本设计以3.6倍面积缩减实现相近延迟。
**五、总结讨论与结论**
**总结讨论**：研究结果表明，通过针对固定旋转因子操作数定制Barrett约简，能够有效加速NTT/INTT运算。将内部数据通路与模数字长对齐可带来面积-时间双重优势。独立乘法器实验证实，随着操作数位宽增大（包括64位情形），TMSCB的算术优势愈发明显。值得注意的是，将优化聚焦于旋转因子路径（而非同时优化点乘）即可在不同参数集上获得可观收益，这为设计高效变换引擎提供了新思路。与高度并行架构（如赵等人的32蝶形脉动阵列、Taghavi等人的128蝶形架构）相比，本设计以更合理的资源开销维持了高时钟频率。但本研究尚未评估完整大模数NTT/INTT架构或全同态加密(FHE)实现。
**结论翻译**：通过引入并全面评估截断模长常量Barrett(TMSCB)乘法器及常量Barrett变体，本工作证明了针对固定旋转因子操作数定制Barrett约简可加速NTT/INTT计算。针对ML-DSA和Falcon参数集的FPGA实现证实，聚焦于常量操作数模乘的优化策略是加速NTT计算的有效途径。特别是将内部数据通路与模数字长对齐可带来面积-时间优势。更大操作数位宽（包括64位）的独立乘法器结果表明，TMSCB的相对算术优势随模数位宽增长而增加。然而，当前工作未评估完整的大模数NTT/INTT架构或全同态加密实现。因此，使用代表性FHE参数集扩展和验证所提方法仍是未来工作的重要方向。未来研究还应考虑不同的NTT架构以及其他常量模乘方法，包括基于Montgomery和K-RED的途径。
