素阶数域上的高效格基数字签名方案  

Efficient Lattice-based Digital Signature Scheme in Large-Galois-group Prime-degree Prime-ideal Field

作　　者：董怡帆 方博越 梁志闯 赵运磊 DONG Yi-Fan;FANG Bo-Yue;LIANG Zhi-Chuang;ZHAO Yun-Lei(School of Computer Science,Fudan University,Shanghai 200433,China;State Key Laboratory of Cryptology,Beijing 100878,China)

机构地区：[1]复旦大学计算机科学技术学院,上海200433 [2]密码科学技术全国重点实验室,北京100878

出　　处：《软件学报》2025年第2期776-804,共29页Journal of Software

基　　金：国家自然科学基金(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倍,实现兼顾高效性和安全性的素阶数域签名算法.With the rapid development of quantum computing,especially the optimization and progress of the Shor quantum algorithm and its variants,the current classical public-key cryptography based on factoring large integers and discrete logarithm problems is facing serious security threats.To cope with quantum attacks,post-quantum cryptography has been proposed,among which lattice-based cryptography is commonly viewed as the most promising one due to its outstanding performance in security,bandwidth,and efficiency.Most of the existing lattice-based post-quantum cryptographic schemes use cyclotomic rings,especially power-of-two cyclotomic rings,as their underlying algebraic structures.However,targeted attacks against cyclotomic rings have been proposed,exploiting subfields,small Galois groups,and ring homomorphisms in these rings.This study uses the large-Galois-group prime-degree prime-ideal field as the new underlying algebraic structure,which has characteristics of high security,prime order,large Galois group,and inert modulus.First,this study proposes a post-quantum digital signature scheme based on the large-Galois-group prime-degree prime-ideal field,which is named Dilithium-Prime,and the recommended parameter sets are provided.Next,considering that the traditional number theory transform(NTT)algorithm cannot be used to multiply polynomials efficiently in the large-Galois-group prime-degree prime-ideal field,this study designs efficient polynomial multiplication strategies for Dilithium-Prime,including NTT for the large-Galois-group prime-degree prime-ideal field and small polynomial multiplication.Finally,this study provides a portable C language implementation of Dilithium-Prime,along with the implementation details and constant-time implementation skills,and compares Dilithium-Prime with other lattice-based digital signature schemes.The experimental results show that the public key size,secret key size,and signature size of Dilithium-Prime are reduced by 1.8%,10.2%,and 1.8%,respectively,compared to CRYSTALS-Dilit

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

分 类 号：TP309[自动化与计算机技术—计算机系统结构]