第1章引言
数字签名可以确保数据的完整性（Integrity）和来源真实性（Authenticity）.在数字签名方案中，签名方拥有一个公私钥对（pk，sk），其中sk是私钥（签名方需对其保密），pk是公钥（可以公开签名者可以使用私钥sk对消息msg进行签名，任何知道公钥pk的实体都可以验证这个签名的真伪.可以公开验证真伪，是数字签名的一个重要性质，这意味着一个消息的签名可以出示给第三方，知道正确公钥的第三方可以正确地验证该签名的真伪.另外，由于只有知道私钥的实体才能进行签名，因此当一个实体给一个消息签名后，它也很难对其签名行为进行抵赖.这些特点与同样可以提供完整性和真实性保护的对称密码方案消息认证码（Message Authentication Code，MAC）有显著区别.消息认证码只能由私钥拥有者进行验证，且知道私钥的双方都可以计算任意消息的认证码，因此MAC也无法提供抗抵赖性.同时，数字签名也在一定程度上避免了消息认证码中密钥分配和管理的复杂性.但要注意，如何可靠地公布（和签名实体绑定的）公钥并不是一个平凡问题，错误的公钥信息可能带来灾难性的安全问题，公钥基础设施（PublicKey Infrastructure，PKI）体系就是一种系统地解决安全发布公钥的方案.
数字签名的应用极为广泛，在TLS协议、PKI、软件更新、操作系统安全启动、区块链等系统中发挥了重要作用.当前大规模部署和应用的数字签名包括国际标准RSA、ECDSA和我国商用密码标准SM2等.然而，由于Shor算法可以在量子计算模型下以多项式时间复杂度分解大整数和求解离散对数，一旦大规模通用量子计算机问世，现行的基于大整数分解和离散对数求解困难性的数字签名算法（如RSA、ECDSA和SM2等）的安全性将受到严重威胁W.尽管目前学术界和产业界对是否可以成功制造出大规模通用量子计算机还存在争议，但该领域的研究进展迅速，全球主要国家对向抗量子计算攻击密码算法迁移的必要性已达成广泛的共识.实际上，只要无法证明通用量子计算机不可实现，向抗量子计算攻击算法的迁移就是必要甚至紧迫的.其一，技术突破无法被预测，各国政府在量子计算领域投入了大量资源，由于量子计算的颠覆性，率先取得突破的国家有较高可能不会公布其相关成果.其二，密码算法的迁移需要较长的时间周期，向后量子密码算法的迁移必须远远早于量子计算机成功制造的时间.其三，将基于传统密码体系保护的加密流量保存起来并等待量子计算机成功制造后再解密的囤积攻击（Store Now Decrypt Later）进一步加剧了向后量子密码迁移的迫切性.*后，越来越多的企业将支持后量子算法作为可以进行大力宣传的产品优势，不具备抗量子计算攻击能力的产品将在未来产业竞争中处于劣势地位.
由于量子计算对对称密码的影响有限，我们目前所说的后量子密码主要是指抗量子计算攻击公钥密码.更具体地，主要是指密钥封装（KEM）/公钥加密（PKE）和数字签名（DSA）.本书主要关注数字签名算法.目前构造抗量子计算攻击数字签名的技术路线主要包括基于格的设计、基于编码的设计、基于同源的设计、基于多变量的设计、基于MPC-in-the-Head的设计和基于杂凑函数的设计.由于基于杂凑函数的数字签名算法不依赖于任何“结构化”的困难问题，其安全性是*保守的.
1.1基于杂凑函数的数字签名
基于杂凑函数的数字签名算法（Hash-Based Digital Signature Schemes，简称HBS）的研究历史悠久，*早可以追溯到1976年.在《密码学的新方向》M这篇里程碑式的论文中，Diffie和Heilman提出了一种利用单向函数对一比特数据进行签名的方案.在该方案中，我们随机选择一对n比特串Gx作为私钥，并令为相应的公钥，其中哎—哎为一个单向函数.那么，消息6G的签名为的原像xb.后来，Lamport对这一方案进行了推广，给出了一个适用于任意长度消息的一次性数字签名算法队一次性数字签名算法的一个公私钥对只能对一个消息进行签名，多次签名会破坏算法的安全性.通过将N个一次性数字签名的实例作为叶子节点组织在一个Merkle树中，可以构造一个N次签名算法.经过40余年的发展，这种设计数字签名的技术路线逐渐成熟.基于杂凑函数的数字签名包括带状态的数字签名和无状态数字签名两类，其中带状态的数字签名在每次签名后都需要对私钥状态进行更新，且确保正确的私钥状态更新对保证算法的安全性至关重要.
对比其他后量子签名体制的设计方法，基于杂凑函数的设计有很多优势.**，它是目前所有后量子签名体制中安全性*可靠的方案，这类方案的安全性本质上只依赖于底层杂凑函数的抗（第二）原像攻击的安全性（注意，根据目前的研究，即使是被破解了的MD5算法也是具备抗原像攻击的性质的），而不依赖其他结构性安全假设.并且，基于杂凑函数的签名体制的底层杂凑函数是可替换的，一旦发现当前使用的杂凑函数有安全问题，可以直接替换一个安全的杂凑函数.第二，基于杂凑函数的数字签名算法的公私钥尺寸较小，验签性能高.第三，基于杂凑函数的数字签名算法的参数选项丰富，可以根据应用场景灵活调整.基于杂凑函数的数字签名也存在一些缺点.*先，性能和开销比较有优势的基于杂凑函数的数字签名算法是带状态的，这意味着每次签名后私钥都会改变状态.这种状态更新
是为了确保同一个一次性数字签名实例不会进行多于一次签名以确保系统的安全性.如何进行安全可靠的私钥更新并不是一个平凡的问题.在2019年，美国国家标准与技术研究院（NIST）对基于杂凑函数的带状态签名的抗误用进行了专门的讨论W.在部分应用场景下，安全可靠地管理私钥状态是困难的，这限制了这类签名算法的实际应用.其次，一个基于杂凑函数的数字签名算法实例（对应一个公私钥对）只能进行有限次签名丨但一般都可通过参数调整达到具体应用所需要的签名次数*后，基于杂凑函数的数字签名算法生成的签名尺寸较大.但总体来看，在部分应用场景下，上述局限性和开销并没有成为基于杂凑函数的数字签名体制应用的障碍.
在文献中，来自思科和佛罗里达大学的研究人员指出，基于杂凑函数的数字签名算法的性能完全满足安全启动（Secure Boot）的应用场景.文献[6]分析了在可信平台模块（Trusted Platform Modules，TPM）中利用基于杂凑函数的签名替换RSA签名的情况，并指出通过采用合适的Merkle树遍历算法，这种替换的开销是完全可以接受的.基于杂凑函数的签名在区块链领域也有所应用，qRL利用XMSS结合W0TS+实现了一个抗量子攻击分布式账本[7].加拿大密码解决方案提供商在其产品ISARA Radiate中实现了XMSS方案，该方案克服了基于HSM实现基于杂凑函数的数字签名的多个困难，并在Utimaco SecurityServer中进行了测试文献[9]提出了一种可以在无线传感器网络节点消息认证和广播认证中使用的基于杂凑函数的签名方案.Boneh等则考虑了在SGX应用基于杂凑函数的签名方案*后，英飞凌在其TPM芯片产品OPTIGA TPM SLB9672中的固件更新功能中使用了基于杂凑函数的签名算法XMSS.系统级芯片（System on Chip，SoC）信任根（Trust of Root）开源项目OpenTitan[12]和Caliptra实现了基于杂凑函数的数字签名的安全启动机制.
1.2基于杂凑函数的数字签名的标准化现状
各国政府和相关组织都在积极推动后量子密码算法的标准化工作.因为其可靠的安全性和在特定应用场景下的适用性，基于杂凑函数的带状态数字签名体制成为*早一批被标准化的后量子密码算法.早在2013年，IETF就开始了对Leighton-Micali签名体制的标准化工作，*终在2019年形成了RFC8554[14].另外，IETF也考虑为LMS增加更多的参数选择[151对XMSS签名体制的标准化工作则开始于2015年，*终在2018年形成了RFC8391[16].美国国家标准与技术研究院（NIST）则将LMS、XMSS签名体制以及它们的超树版本HSS和XMSS-MT写入了NISTSP800-208.当前，国际标准化组织（International Organization for Standardization，ISO）也在积极推动基于杂凑函数的带状态数字签名的标准化工作，形成了ISO/IEC 14888-4:2024标准.由于带状态的数字签名在每次签名后需要可靠地进行状态更新才能保证其安全性，IETF也在考虑为安全的状态管理制定专门的标准[19].2022年9月，美国国家安全局发布了《商业国家安全算法套件2.0》（CNSA2.0）I20!，建议在软件和固件丨更新）签名应用场景下立即向NISTSP800-208中给出的基于杂凑函数的数字签名迁移，并在2030年完成这一迁移过程.德国联邦信息安全局（BSI）也在BSITR-02102-1中给出了类似的建议[21].
2016年，NIST发起了后量子密码算法标准征集竞赛该竞赛共收到来自全球的82套算法设计，其中有69套满足*低要求的算法进入了**轮的评估，包括49套公钥加密算法（PKE）或密钥封装算法（KEM），以及20套数字签名算法.经过三轮的评估，NIST于2022年宣布了4套正式进入标准化程序的算法，包括密钥封装算法CHYSTALS-Kyber（基于格）、数字签名算法CRYSTALS-Dilithium（基于格）、数字签名算法Falcon（基于格）和基于杂凑函数的无状态数字签名算法SPHINCS+.2023年11月，NIST发布了关于无状态数字签名算法SPHINCS+的FIPS205草案.2024年8月13日，NIST正式发布了基于杂凑函数的无状态数字签名标准FIPS205.*后，在NIST新一轮抗量子计算攻击数字签名的征集活动中，我国学者也提交了一套基于杂凑函数的无状态数字签名算法SPHINCS-a，目前正在评估阶段.
我国有关部门对后量子密码的研究、标准化及迁移工作也极为重视.中国密码学会于2018年组织了全国密码算法设计竞赛，其中就包括后量子公钥密码的设计竞赛.然而，在提交的算法中，并没有基于杂凑函数设计的数字签名算法.另外，2022年基于多变量和基于同源的两个重要后量子密码算法被破解，在一定程度上说明了当前后量子密码算法设计的理论与方法在某些方面还不成熟.因此，后量子密码算法的标准化工作必须谨慎推进.由于其可靠的安全性以及国际标准化组织已有相关可借鉴的经验，我国密码行业标准化技术委员会于2023年启动了基于我国商用密码杂凑函数SM3的带状态数字签名％的标准化制定项目，并于2024年前启动了基于我国商用密码杂凑函数的无状态数字签名[25，271的研究工作.目前，基于SM3的带状态数字签名算法密码行业标准已进入全国征求意见阶段.基于杂凑函数的后量子签名体制也许可以成为我国后量子公钥密码算法标准化的起点，并以此为基础形成后量子算法部署、迀移等工作的实践阵地.
1.3章节安排和阅读建议
本书共9章.第2章介绍了两种典型的杂凑函数结构和一些后续章节将要用到的标准杂凑函数、消息认证码和掩码生成函数.第3章介绍了数字签名的
基本定义并给出了两种可以将只支持固定长度消息的签名算法转化为支持任意长度消息的签名算法的范式.第4章介绍了一次性数字签名的基本原理和典型算法.在一次性签名算法中使用了一种抗伪造攻击的编码方法，第5章对这种编码方案进行了细致的分析.第6章介绍了可以对少量消息进行签名的FTS（Few-Time Signature）数字签名算法.第7章介绍带状态数字签名的基本原理和典型算法.第8章介绍了Meride树遍历算法，Merkle树遍历算法可以按一定顺序生成带状态数字签名算法输出的数字签名中所需的认证路径；由于本章涉及的算法细节过多且跳过本章不会影响后续章节的阅读，因此我们建议读者先跳过此
展开
