[论文阅读] 算法 | 抗量子+紧凑！SM3-OTS：基于国产哈希算法的一次签名新方案

抗量子+紧凑！SM3-OTS：基于国产哈希算法的一次签名新方案

论文信息

一段话总结

面对量子计算对传统密码的威胁，后量子签名方案SPHINCS+因核心组件WOTS+签名值过长限制应用，研究团队设计了基于国密算法SM3的紧凑型一次签名方案SM3-OTS：通过消息摘要的二进制信息索引前32条哈希链、十六进制信息索引后16条哈希链，大幅缩短密钥与签名长度；相较于WOTS+、Balanced WOTS+、WOTS+C，签名值分别缩短29%、27%、26%，密钥生成、签名生成、验证时间较WOTS+分别减少27.2%、18.7%、25.3%，同时依托SM3具备抗量子能力，适用于存储/带宽受限场景（如物联网）。

四、思维导图

研究背景

咱们先从“为什么要做这个研究”说起——毕竟任何技术方案，都是为了解决实际问题而生的。

首先，量子计算是传统密码的“天敌”。以前我们常用的密码（比如银行转账用的RSA、手机支付用的ECC），都依赖“大整数分解”“离散对数”这些数学难题——就像用一把复杂的锁把数据锁起来，传统计算机要解开得花几百年。但1994年Shor算法出现后，量子计算机能“秒解”这些难题；1996年Grover算法更狠，能把对称密码的破解时间砍半。这就好比，量子计算机手里有一把“万能钥匙”，传统密码的锁很快就不管用了。

为了应对这个危机，后量子密码（PQC） 应运而生——目标是设计“量子计算机也解不开”的密码。2022年NIST（美国国家标准与技术研究院）选出了4种首批标准化PQC方案，其中SPHINCS+ 很特别：它是唯一基于“哈希函数”的方案（其他3种基于格理论）。哈希函数就像“单向榨汁机”——把水果（输入）榨成汁（哈希值）容易，但想从汁还原出水果几乎不可能，这种特性让SPHINCS+的签名/验证速度快、安全性可靠，很适合物联网、嵌入式设备。

但问题来了：SPHINCS+的核心组件WOTS+（一次签名方案）有个大缺点——签名值太长。比如安全参数n=32时，WOTS+的签名要2144字节（差不多2KB）。这对手机、传感器这些“小身板”设备很不友好：想象一下，一个物联网传感器只有几KB存储，存一个签名就占了一半空间；或者偏远地区的设备靠窄带宽传输，一个2KB的签名要传半天——就像快递包装比里面的物品还大，小快递柜根本放不下，运输也费时间。

除此之外，国内场景还关注**“国产自主可控”**：很多现有方案用的是国外哈希函数（比如SHA-256），而国密算法SM3是我国自主设计的，安全性经过验证，更符合国内合规要求。但当时还没有基于SM3的“紧凑后量子签名方案”——这就是论文要填补的空白：用SM3做一个“又小又快、抗量子、国产化”的一次签名方案，解决WOTS+的“大体积”痛点。

创新点

这篇论文的核心亮点，简单说就是“用对方法，解决了老问题”，具体有三个关键创新：

1. 双信息维度索引哈希链，从根源缩短签名长度
   传统OTS方案（比如WOTS+）只用消息摘要的“单一格式”（比如二进制）索引哈希链，需要更多哈希链或更长节点才能覆盖安全需求。SM3-OTS则“一鱼两吃”：把32字节的消息摘要拆成两种格式——二进制（m_bin）和十六进制（m_hex），分别对应前32条、后16条哈希链的节点索引。这样既保证了安全覆盖，又减少了冗余，最终签名长度从WOTS+的2144字节压缩到1536字节，缩短了29%。

2. 深度结合国密SM3，兼顾合规与抗量子
   很多后量子方案依赖国外哈希函数，而SM3-OTS全程用国密算法SM3：私钥生成、公钥推导、签名计算、验证都基于SM3。这不仅符合国内“自主可控”的合规要求，还利用了SM3的抗量子特性——哈希函数的“单向性”“无碰撞性”在量子环境下仅受Grover算法轻微影响（安全级别从128位降至85位，可通过扩展输出弥补），比基于数论的密码抗量子能力更稳定。

3. 算法流程优化，效率与紧凑性双赢
   传统方案为了缩短签名，常牺牲效率（比如增加复杂计算），但SM3-OTS在紧凑的同时还提升了效率：密钥生成时，48个私钥块仅需各做255次SM3哈希就得公钥；签名/验证时，通过“索引直接定位哈希链节点”减少无效计算。实验显示，它比WOTS+的密钥生成快27.2%、签名快18.7%、验证快25.3%——相当于“包装变小了，快递速度还变快了”。

研究方法和思路、实验方法

（一）核心研究思路

论文的整体思路很清晰：“发现痛点→针对性设计方案→验证安全性→测试性能”，具体路径是：

1. 痛点：SPHINCS+的WOTS+签名过长，缺乏国产方案；
2. 方向：基于SM3设计紧凑型OTS，用双信息索引优化哈希链；
3. 验证：从理论证明方案安全（归约到SM3特性），从实验验证性能（对比主流方案）。

（二）SM3-OTS方案的具体实现步骤

1. 密钥生成算法（KeyGen）：“造钥匙”的过程

目标：生成一对“私钥（自己用）+公钥（别人验证用）”
步骤：
① 确定安全参数：默认n=256bits（行业常用安全级别）；
② 生成私钥块：用伪随机数生成函数（PRNF），以“秘密种子（Seed）”为基础，生成48个32字节的私钥块（sk₀~sk₄₇），私钥sk就是这48个块的集合（1536Bytes）；
③ 生成公钥块：对每个私钥块skᵢ，用SM3哈希255次（记为H²⁵⁵(skᵢ)），得到48个32字节的公钥块（pk₀~pk₄₇），公钥pk就是这48个块的集合（1536Bytes）；
④ 形成哈希链：每个skᵢ到pkᵢ的过程就是一条“哈希链”（共48条），链上有256个节点（首节点=skᵢ，尾节点=pkᵢ）。

2. 签名生成算法（Sign）：“签名字”的过程

目标：给明文消息M生成唯一签名σ
步骤：
① 算消息摘要：用SM3对M哈希，得到32字节的摘要m=H(M)；
② 处理摘要格式：

• 二进制格式（m_bin）：把m转成二进制，每8位分成一组，共32组，每组转成0-255的十进制数（作为前32条哈希链的“节点索引”）；
• 十六进制格式（m_hex）：把m转成十六进制（含0-F共16个字符），统计每个字符在64位十六进制串中的位置和，再对255取模（作为后16条哈希链的“节点索引”）；
  ③ 生成签名块：对每条哈希链，根据索引找到对应的节点——比如前32条的第1条索引是10，就取sk₀哈希10次的结果（H¹⁰(sk₀)）作为签名块σ₀；
  ④ 组合签名：48个签名块（σ₀~σ₄₇）组合成最终签名σ（1536Bytes）。

3. 签名验证算法（Verify）：“验真假”的过程

目标：确认签名σ是不是“真的”（没被篡改）
步骤：
① 重复签名生成的①-②：对收到的M重新算摘要m，再得到m_bin和m_hex的索引；
② 推导验证公钥：对每个签名块σᵢ，用SM3哈希“255-索引值”次（比如σ₀索引是10，就哈希255-10=245次，记为H²⁴⁵(σ₀)），得到验证公钥块pk’ᵢ；
③ 对比验证：把48个pk’ᵢ组合成验证公钥pk’，如果pk’和原公钥pk完全一致，说明签名有效（输出true），否则无效（输出false）。

（三）实验方法：怎么证明方案“好用”

1. 实验环境（保证结果可信）

• 硬件：AMD Ryzen 7840S CPU（3.3 GHz）、4GB RAM（模拟嵌入式/物联网设备的中等配置）；
• 软件：Ubuntu 22.04 LTS操作系统（Linux环境，常见服务器/设备系统）。

2. 对比对象（选行业主流方案）

• WOTS+（SPHINCS+核心组件）；
• Balanced WOTS+（SPHINCS-α优化方案）；
• WOTS+C（SPHINCS+C优化方案）；
• LMOTS（经典哈希基OTS方案）。

3. 测试指标（关键性能维度）

• 尺寸指标：私钥长度、公钥长度、签名值长度（单位：Bytes）；
• 效率指标：密钥生成时间、签名生成时间、签名验证时间（单位：ms）。

主要成果和贡献

（一）核心成果总结（用表格更清晰）

（二）领域贡献（实实在在的价值）

1. 解决“签名过长”痛点，拓展后量子签名的应用场景
   以前WOTS+签名太长，物联网传感器、智能卡等资源受限设备用不了；SM3-OTS的1536字节签名能轻松适配这些设备，让后量子密码从“实验室”走进“实际产品”。

2. 填补国产紧凑型后量子签名的空白
   之前国内多是“用SM3替换国外方案的哈希函数”，而SM3-OTS是从算法设计层面深度结合SM3，首次实现“国产算法+紧凑结构+后量子安全”的结合，为国内行业提供了自主可控的选择。

3. 提供“效率+安全”平衡的参考方案
   很多方案要么追求紧凑牺牲效率，要么追求效率牺牲紧凑；SM3-OTS证明了“两者可以兼得”，为后续哈希基后量子签名的优化提供了思路（比如双信息索引的设计）。

（三）开源代码/数据集说明

论文中未提及开源代码或公开数据集，推测目前处于理论验证与实验阶段，后续可能在相关学术平台（如GitHub、IEEE Xplore）发布。

关键问题

1. 问：SM3-OTS是怎么解决传统OTS方案（比如WOTS+）签名过长的问题？

答：核心是“双信息维度索引哈希链”：传统方案只用消息摘要的单一格式（如二进制）索引哈希链，需要更多链或更长节点；SM3-OTS把32字节摘要拆成二进制（m_bin）和十六进制（m_hex），分别索引前32条、后16条哈希链，既覆盖安全需求，又减少冗余——比如WOTS+需要更多哈希链节点才能保证安全，而SM3-OTS通过“精准索引”直接定位节点，最终签名从2144Bytes缩到1536Bytes，缩短29%。

2. 问：SM3-OTS的抗量子能力从哪里来？和传统密码（如RSA）比有什么优势？

答：抗量子能力来自国密算法SM3的特性：哈希函数的“单向性”（从哈希值反推输入难）和“无碰撞性”（找两个不同输入得相同哈希值难），在量子环境下仅受Grover算法影响（安全级别从128位降至85位，可通过扩展SM3输出弥补）；而RSA依赖大整数分解，会被Shor算法“秒破”。优势在于：SM3-OTS的抗量子能力更稳定，不会被量子算法完全破解。

3. 问：SM3-OTS的“国密属性”有什么实际意义？国内企业为什么要关注？

答：国密属性的核心意义是“自主可控+合规”：① 避免依赖国外算法的“卡脖子”风险（比如国外算法升级或限制使用）；② 符合国内《网络安全法》《密码法》对“关键信息基础设施用国产密码”的要求。国内企业（尤其是金融、政务、物联网领域）用SM3-OTS，既能满足后量子安全需求，又不用为合规额外改造，降低成本。

4. 问：SM3-OTS是“一次签名方案”，这意味着什么？怎么扩展到“多次签名”场景？

答：“一次签名”是指一对私钥/公钥只能给一条消息签名（重复用会被伪造）；论文提到未来可通过“二叉哈希树（Merkle Tree）”扩展：把多个SM3-OTS的公钥作为哈希树的“叶子节点”，树的“根节点”作为总公钥——用户每次签名用一个叶子节点的SM3-OTS密钥，就能实现“多次签名”，同时保持无状态（不用记录已签名次数）。

5. 问：和SPHINCS+的其他优化方案（如Balanced WOTS+、WOTS+C）比，SM3-OTS的核心优势是什么？

答：核心优势是“综合性能最优”：① 签名更短：比Balanced WOTS+短27%、比WOTS+C短26%；② 效率更高：密钥生成、签名、验证时间均优于这两种方案；③ 国密兼容：后两者基于国外哈希函数，SM3-OTS基于SM3，更适合国内场景。简单说，SM3-OTS在“短、快、合规”三个维度上都做到了更好。

总结

论文针对后量子签名方案SPHINCS+中WOTS+签名过长的痛点，设计了基于国密算法SM3的紧凑型一次签名方案SM3-OTS。该方案通过消息摘要的二进制与十六进制信息双维度索引哈希链，有效缩短了密钥与签名长度（较WOTS+缩短29%）；同时依托SM3的抗量子特性，从理论上证明了方案的安全性（归约到SM3的单向性与抗碰撞性）；实验验证显示，方案在密钥生成、签名生成、验证效率上均优于主流OTS方案（较WOTS+效率提升18.7%-27.2%）。

SM3-OTS的价值在于：既解决了传统OTS方案“大体积”的应用瓶颈，又填补了国产紧凑型后量子签名的空白，为物联网、嵌入式设备等资源受限场景提供了“安全、紧凑、高效、合规”的后量子签名选择。未来通过二叉哈希树扩展为无状态方案后，其应用范围还将进一步扩大。