Page 21 - 《软件学报》2025年第10期

4418 软件学报 2025 年第 36 卷第 10 期

while maintaining well-balanced overall performance.
+
Key words: hash function; SPHINCS ; digital signature; one-time signature (OTS); post-quantum cryptography (PQC)
1 引 言

随着量子计算技术 [1,2] 的飞速发展, 传统基于椭圆曲线、离散对数、大整数分解等数学困难问题的密码方案
[4]
将面临量子计算攻击 [3] . 1994 年, Shor 提出的 Shor 算法是一种能够高效地解决大整数分解问题的量子算法;
[5]
1996 年, Grover 提出了量子搜索 Grover 算法, 通过暴力破解的方式将破解对称密码算法密钥的时间复杂度从
n/2
n O(2 ), 量子计算机通过使用 Shor 算法和 Grover 算法, 对传统的公钥密码算法和对称密码算法构成
O(2 ) 降低到
了严重威胁, 为应对这些威胁, 具有抵抗量子攻击能力的后量子密码算法 (post-quantum cryptography, PQC) 的研
[6]
究与优化工作迫在眉睫. 2016 年 12 月, 美国国家标准与技术研究院 (National Institute of Standards and Technology,
NIST) 正式面向全世界征集具备抵抗量子计算机攻击能力的后量子密码算法, 以在量子时代逐步取代传统公钥密
码算法.
2022 年 7 月, NIST 从第 3 轮后量子密码算法提交的方案中, 初步选定 4 种算法作为标准化算法, 包括 1 种公
钥加密算法和 3 种数字签名算法, 分别是公钥加密算法 CRYSTALS-Kyber 、数字签名算法 CRYSTALS-Dilithium 、
[7]
[8]
[9]
FALCON 以及 SPHINCS +[10] . 其中, Kyber、Dilithium、FALCON 是基于格理论问题构建的. 2022 年, 杨亚涛等人 [11]
基于 CRYSTALS-Kyber 密码方案设计了一套抗量子计算攻击的 VPN 软件系统, 展现了后量子密码方案在网络安
全中的工程应用. 区别于上述 3 种密码方案, SPHINCS 是其中唯一基于哈希函数构建的密码方案. 且后续 NIST
+
也会陆续征集并标准化其他安全性及性能更加优秀的密码算法.
目前后量子密码方案大致可以分为基于编码、基于格、基于多变量以及基于哈希函数 [12] 等类型的密码方
案 [13] . 基于哈希函数设计的数字签名方案的签名生成和验证时间最短, 且安全性更可靠, 所以基于哈希函数的
数字签名方案被认为是量子时代十分具有研究价值的后量子密码方案. SPHINCS +[10] 是一种基于哈希函数设计
+
的无状态数字签名方案, SPHINCS 是利用一次签名方案 (one-time signature, OTS)、少次签名方案 (few-time
signature, FTS) 和 Merkle Tree [14] 构建的. 一次签名方案为 SPHINCS 方案的核心, 一般基于哈希函数设计的一次
+
+
签名方案存在生成的签名值长度较大问题, 造成了 SPHINCS 等基于哈希函数的无状态数字签名方案在实际应
用中的困难.
本文贡献如下.
(1) 设计了一种新的基于国密算法 SM3 的后量子一次签名方案 SM3-OTS: 本方案通过利用消息摘要值的二
进制信息 (binary) 和十六进制信息 (hexadecimal) 分别作为前 32 条哈希链和后 16 条哈希链节点位置的索引, 从而
有效地缩短了传统基于哈希函数的一次签名方案的密钥长度和生成的签名值长度.
(2) 测试了新的基于国密算法 SM3 的一次签名方案 SM3-OTS 性能: 通过实验测试, SM3-OTS 相较于 SPHINCS +[10]
+
中使用的 WOTS+、SPHINCS-α [15] 中使用的 Balanced WOTS+以及 SPHINCS C [16] 中使用的 WOTS+C, SM3-OTS
方案所生成的签名值长度大约缩短了 29%、27%、26%, 签名性能得到明显提升.
2 国内外研究现状

利用哈希函数的抗原像攻击特性 (单向性) 构造数字签名方案是一个众多密码研究者关注并认可的研究思路.
Suhail 等人 [17] 和 Kumar 等人 [18] 分别于 2020 年和 2021 年针对量子计算技术成熟后的基于哈希函数的数字签名方
案在物联网设备安全中的重要性、部署时需要考虑的各种因素和各种挑战进行了分析, 并对物联网设备网络环境
中应用后量子密码技术给出了相应建议和展望.
1979 年, Lamport [19] 首次提出了基于哈希函数的一次签名方案 Lamport-OTS (LOTS). LOTS 方案签名时对消
息逐位进行签名. LOTS 方案有两个缺陷, 其一是方案的每对密钥只能使用一次, 否则敌手可以利用前一条消息的
签名值伪造签名, 为避免伪造攻击, LOTS 方案的每对密钥只能使用一次; 其二是方案使用的公私钥长度以及生成