计算机研究与发展

作者：郑婕妤,宋振宇,朱浩亮,赵运磊,林璟锵,范晶,

关键词：后量子密码, NTRU格, 密钥封装机制, AVX2并行优化, 软件实现,

NTRU格是构建实用后量子格基密钥封装机制的重要选择.格密码的软件优化工程实现对于后量子密码后续的应用部署具有重要意义.CTRU是中国学者提出的基于NTRU格的格密码密钥封装机制.目前CTRU方案只有CTRU-768完成了C和AVX2实现，且有进一步的优化空间，并且CTRU-768的实现无法直接扩展到CTRU-512和CTRU-1024方案上.完成了CTRU-512和CTRU-1024及其变体CNTR-512和CNTR-1024的优化参考C实现和对应AVX2并行优化实现，并对已有的CTRU-768方案的参考实现和AVX2实现进行优化.采用混合基数论变换（NTT）加速多项式环乘法，并使用Karatsuba算法加速分解后的小度数多项式环乘法.此外，结合中心Barrett约减，提出在逆向NTT中进行基于索引的延迟约减.对于CTRU-1024下较为耗时的多项式求逆，引入了Bernstein快速求逆算法.进一步地，提供了更加高效的AVX2优化实现方案，利用Intel提出的单指令多数据（SIMD）指令集AVX2，加速了CTRU中的性能瓶颈.采用层融合和系数置乱技术减少实现过程中的存取指令.此外，对Bernstein快速多项式求逆算法进行了向量化优化实现.对耗时SHA-3哈希模块进行AVX2汇编实现.相较于最新的CTRU-768AVX2实现，AVX2优化实现性能提升了8%～11%.对于CTRU方案，与参考实现相比，AVX2优化实现在3个方案上的性能提升均非常显著.对于CTRU方案，与参考实现相比，提出的AVX2优化实现在CTRU-512，CTRU-768，CTRU-1024这3个方案上的性能提升均十分显著，密钥生成、密钥封装、密钥解封装的性能提升幅度分别为56%～91%，74%～90%，70%～83%.

来源：2025年第9期

《计算机研究与发展》期刊编辑部

查看计算机研究与发展杂志2025年第9期