素阶数域上的高效格基数字签名方案
CSTR:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

TP309

基金项目:

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


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

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    随着量子计算的快速发展, 特别是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倍, 实现兼顾高效性和安全性的素阶数域签名算法.

    Abstract:

    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-Dilithium. The efficiency of the signature algorithm is improved by 11.9%, and the key generation algorithm and the verification algorithm are 2.0× and 2.5× slower than those of CRYSTALS-Dilithium, respectively. However, Dilithium-Prime can withstand the cryptographic attack against cyclotomic rings, which is exactly what CRYSTALS Dilithium lacks. Compared to NCC-Sign, Dilithium-Prime's key generation algorithm, signature algorithm, and verification algorithm are 4.2×, 35.3×, and 7.2× faster, respectively, than those of NCC-Sign under the same security level and bandwidth.

    参考文献
    相似文献
    引证文献
引用本文

董怡帆,方博越,梁志闯,赵运磊.素阶数域上的高效格基数字签名方案.软件学报,,():1-29

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2023-10-19
  • 最后修改日期:2024-01-03
  • 录用日期:
  • 在线发布日期: 2024-10-30
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号