1、密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(1):4660密码学报编辑部版权所有.E-mail:http:/Tel/Fax:+86-10-82789618基于杂凑函数 SM3 的后量子数字签名*孙思维1,刘田雨1,关 志2,何逸飞2,荆继武1,胡 磊3,张振峰4,闫海伦11.中国科学院大学 密码学院,北京 1000492.北京大学 软件工程国家工程研究中心,北京 1008713.中国科学院大学 网络空间安全学院,北京 1000494.中国科学院 软件研究所,北京 100190通信作者:孙思维,E
2、-mail:摘要:基于杂凑函数的数字签名的安全性仅依赖于其所使用的杂凑函数的抗(第二)原像攻击的强度,可以抵抗量子计算攻击,是当前后量子签名研究的热点方向之一,各标准化组织也积极对基于杂凑函数的数字签名方案进行标准化.本文利用国产杂凑函数 SM3 替代 RFC 8554、RFC 8391 和 NIST SP 800-208中给出的 LMS、HSS、XMSS 和 XMSSMT数字签名方案所使用的杂凑函数,并给出了初步的实验结果.实验结果表明,使用 SM3 实例化 LMS 和 HSS 是完全可行的,为后续相关标准化工作的推进提供了支撑.关键词:杂凑函数;数字签名;后量子密码;LMS;HSS;XMS
3、S;XMSSMT;SM3中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000578中文引用格式:孙思维,刘田雨,关志,何逸飞,荆继武,胡磊,张振峰,闫海伦.基于杂凑函数 SM3 的后量子数字签名J.密码学报,2023,10(1):4660.DOI:10.13868/ki.jcr.000578英文引用格式:SUN S W,LIU T Y,GUAN Z,HE Y F,JING J W,HU L,ZHANG Z F,YAN H L.SM3-based post-quantum digital signature schemesJ.Journal of Cryptol
4、ogic Research,2023,10(1):4660.DOI:10.13868/ki.jcr.000578SM3-based Post-quantum Digital Signature SchemesSUN Si-Wei1,LIU Tian-Yu1,GUAN Zhi2,HE Yi-Fei2,JING Ji-Wu1,HU Lei3,ZHANG Zhen-Feng4,YAN Hai-Lun11.School of Cryptology,University of Chinese Academy of Sciences,Beijing 100049,China2.National Engin
5、eering Research Center For Software Engineering,Peking University,Beijing 100871,China3.School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100049,China4.Institute of Software,Chinese Academy of Sciences,Beijing 100190,ChinaCorresponding author:SUN Si-Wei,E-mail:Abstract:The s
6、ecurity of hash-based signatures relies solely on the(second)pre-image resistanceof the underlying hash functions and they are arguably the most conservative signature designs with*基金项目:国家重点研发计划(2022YFB2701900);国家自然科学基金(62032014,62202444);中央高校基本科研业务费专项资金Foundation:National Key Research and Developme
7、nt Program of China(2022YFB2701900);National NaturalScience Foundation of China(62032014,62202444);the Fundamental Research Funds for the Central Universities ofChina收稿日期:2022-10-31定稿日期:2022-11-24孙思维 等:基于杂凑函数 SM3 的后量子数字签名47respect to security.Therefore,hash-based signatures are actively standardized
8、 by the standard bodies.In this article,we instantiate the LMS,HSS,XMSS and XMSSMThash-based signature schemesstandardized in RFC 8554,RFC 8391 and NIST SP 800-208 with SM3 and report on the results ofpreliminary performance tests.Experimental results show that it is feasible to instantiate LMS andH
9、SS with SM3,which provides support for the subsequent standardization work of relevant algorithms.Key words:hash functions;digital signatures;post-quantum cryptography;LMS;HSS;XMSS;XMSSMT;SM31引言由于 Shor 算法可以在量子计算模型下以多项式时间复杂度分解大整数和求解离散对数,一旦大规模通用量子计算机问世,现行的基于大整数分解和离散对数求解困难性的数字签名体制(如 RSA、ECDSA 和 SM2 等)将
10、不再安全1.因此,学术界、产业界和各标准化组织都在积极研究后量子密码算法的设计与迁移.本文主要讨论基于杂凑函数设计的后量子签名体制.基于杂凑函数设计后量子签名体制主要有两类方法.第一类通过暴露某单向函数的原像进行签名24,第二类通过对一单向函数的原像进行零知识证明进行签名.其中后者是一种较新的技术路线,PICNIC5是典型代表,但此类方案还不够成熟稳定.因此,本文只关注第一种技术路线.基于杂凑函数的数字签名体制研究历史悠久,最早可以追溯到 1976 年.在密码学的新方向6这篇里程碑式的工作中,Diffie 和 Hellman 提出了一种利用单向函数对一比特数据进行签名的方法.该方案随机选择(x
11、0,x1)Fn2Fn2作为私钥,(F(x0),F(x1)Fn2Fn2则为相应的公钥,其中 F:Fn2 Fn2为一单向函数.那么,消息 b F2的签名为 F(xb)的原像 xb.经过四十余年的发展,基于杂凑函数的签名体制逐渐成熟.对比其他后量子签名体制的设计方法,基于杂凑函数的设计有很多优势.首先,它是目前所有后量子签名体制中安全性最可靠的方案,这类方案的安全性只依赖于底层杂凑函数的抗(第二)原像攻击的安全性,而不需要依赖其他结构性安全假设(注意,根据目前的研究,即使是被破解了的 MD5 算法也是具备抗原像攻击的性质的).并且,基于杂凑函数的签名体制的底层杂凑函数是可替换的,一但发现当前使用的杂
12、凑函数有安全问题,可以直接替换一个安全的杂凑函数.第二,基于杂凑函数的签名体制的签名和验签性能很好,部分参数设置下性能与 RSA 等传统签名算法相当.第三,基于杂凑函数的签名体制的参数选项丰富,针对具体应用场景有广泛的调整空间710.第四,基于杂凑函数的签名的公私钥尺寸较小.但基于杂凑函数的签名体制仍存在一些缺点.首先,性能和开销比较有优势的基于杂凑函数的签名体制是带状态的,这意味着每次签名后签名私钥都会改变状态.这种改变状态是为了确保同一个一次性签名实例不会进行多于一次签名以确保系统的安全性.2019 年,美国国家标准与技术研究院(NIST)对基于杂凑函数的带状态签名的抗误用进行了专门的讨论
13、11.其次,基于杂凑函数的签名体制的一个实例只能进行有限次签名(但一般都可通过参数调整达到具体应用所需要的签名次数).第三,基于杂凑函数的签名体制生成的签名尺寸较大.但总体来看,在部分应用场景下,上述局限性和开销并没有成为基于杂凑函数的签名体制应用的障碍.1.1应用情况来自 Cisco 和佛罗里达大学的研究人员指出12,签名时间和验签时间分别在 1 s 内和 10 ms 内的后量子签名方案完全可以应用于安全启动(secure boot)的应用场景.而基于杂凑函数的签名体制完全可以达到这个要求.文献 13 分析了在 TPM(trusted platform modules)中利用基于杂凑函数的签
14、名替换 RSA 签名的情况,并指出通过采用合适的 Merkle 树遍历算法,这种替换的开销是完全可以接受的.基于杂凑函数的签名在区块链领域也有所应用,QRL 利用 XMSS 结合 WOTS+实现了一个抗量子攻击分布式账本14.加拿大密码解决方案提供商在其产品 ISARA RadiateTM中实现了 XMSS 方案,该方案克服了基于 HSM 实现基于杂凑函数的签名的多个困难,并在 Utimaco Inc.SecurityServer 中进行了测试15.文献 16 提出了一种可以在无线传感器网络中传感器节点消息认证和广播认证中使用的基于杂凑函数的签名方案.Boneh 等人则考虑了在 SGX 应用基
15、于杂凑函数的签名方案17.最后,英飞凌在48Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023其 TPM 芯片产品 OPTIGATMTPM SLB 9672 中的固件更新功能中使用了基于杂凑函数的签名算法XMSS1.1.2基于杂凑函数的签名体制的标准化工作现状密码学界、工业界和各标准化组织都在积极推动后量子密码算法的标准化工作.因为其可靠的安全性和良好的性能,基于杂凑函数的签名体制成为第一批被标准化的后量子密码算法.早在 2013 年,IETF 就开始了对 Leighton-Micali 签名体制的标准化工作,最终在 2019 年
16、形成了 RFC 855418.对 XMSS 签名体制的标准化工作则开始于 2015 年,最终在 2018 年形成了 RFC 839119.NIST 则将 Leighton-Micali 签名体制(LMS)、XMSS 签名体制以及他们的变种 HSS 和 XMSSMT写入了 NIST SP 800-20820,用以补充 FIPS 186 的不足,并确保在更一般的后量子签名标准形成前有备选的后量子签名算法.当前,ISO 也在积极推动基于杂凑函数的签名体制的标准化工作,形成了 ISO/IEC CD 14888-4 等文件,目前正在讨论与修订中.同时,IETF 也考虑为 LMS 增加更多的参数选择21.我国有关部门对后量子密码的研究、标准化及迁移工作也极为重视.中国密码学会于 2018 年组织了全国密码算法设计竞赛,其中包括后量子公钥密码设计竞赛内容.然而,所提交的算法中并没有基于杂凑函数设计的签名算法.另外,2022 年,基于多变量和基于同源的两个重要后量子密码算法被破解,表明当前后量子密码算法设计的理论与方法在某些方面还不成熟、不可靠.这说明关于后量子密码算法的标准化工作必须谨慎推进.由于可
