软件学报

作者：董怡帆，方博越，梁志闯，赵运磊

单位：董怡帆，复旦大学 计算机科学技术学院, 上海 20043311,方博越，复旦大学 计算机科学技术学院, 上海 20043302,梁志闯，复旦大学 计算机科学技术学院, 上海 20043303,赵运磊，复旦大学 计算机科学技术学院, 上海 200433;密码科学技术全国重点实验室, 北京10087804

关键词：后量子密码;格密码;素阶数域;数字签名方案;快速数论变换;小多项式乘法

基金：国家自然科学基金(61877011); 国家重点研发计划(2022YFB2701600); 上海科技创新行动计划技术标准项目(21DZ2200500)

随着量子计算的快速发展, 特别是Shor量子算法及其变体的优化进步, 当前基于大整数分解和离散对数问题的经典公钥密码体制将面临颠覆性的影响. 为了应对量子攻击, 学界开始对后量子密码学的研究, 其中基于格的后量子密码方案因其在安全、效率、带宽等方面的均衡表现和良好的可扩展性而成为后量子密码的主流技术路线. 目前, 基于格的后量子密码方案大多使用分圆环, 尤其是二次幂分圆环作为底层代数结构. 但分圆环中具有丰富的子域、自同构、环同态等代数结构, 容易遭受针对性攻击. 基于具有“高安全性、素数阶、大Galois群和惰性模数”特点的素阶数域, 设计出后量子数字签名方案Dilithium-Prime, 并给出推荐参数集. 然而, 素阶数域的一个显著缺点是无法直接使用快速数论变换(NTT)算法进行高效的多项式乘法, 导致素阶数域上的密码方案性能较差. 为此, 设计素阶数域上的NTT算法和小多项式乘法, 实现素阶数域上高效的多项式乘法. 最后, 为方案的关键算法设计常数时间无分支实现方法, 给出方案的C语言实现, 并与其他方案进行对比. 实验结果表明, 在同一安全等级下, 与分圆环上的数字签名方案CRYSTALS-Dilithium推荐参数相比, Dilithium-Prime方案的公钥尺寸、私钥尺寸、签名尺寸分别降低1.8%、10.2%、1.8%, 签名算法效率提高11.9%, 密钥生成算法、验证算法所需时间分别为CRYSTALS-Dilithium方案的2.0倍和2.5倍, 但不同于CRYSTALS-Dilithium, Dilithium-Prime方案具有抵抗针对分圆环的密码攻击的优越特性; 与2023年韩国后量子密码算法竞赛中提出的基于素阶数域的签名方案NCC-Sign推荐参数相比, 在相同的安全等级和带宽条件下, Dilithium-Prime方案的密钥生成算法、签名算法、验证算法的速度分别提升至4.2倍、35.3倍、7.2倍, 实现兼顾高效性和安全性的素阶数域签名算法.

来源：2025年第2期

《软件学报》期刊编辑部

查看软件学报杂志2025年第2期