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

张川 等: 抗量子的高效区块链认证存储方案 4487

其中, D n,m 表示前 n 个码字的总和为 m 的大小, 定义初始值为:


 D 1,m = 1, m ∈ {0,1,...,w−1}

 (2)

D n,m = 0, 2 ⩽ n ∈ Z,m ∈ Z

 −
递归关系为:

∑ w−1
D n,m = D n−1,m−i , 2 ⩽ n ∈ Z,m ∈ {0,1,...,l(w−1)} (3)
i=0
接下来解释一下公式 (3) 的递归关系. 要计算 D n,m , 首先考虑最后一个求和的值, 可以是 {0,1,...,w−1} 中的任
意值. 假设将该值设为 i, 则前 n−1 个元素的和必须为 m−i. 因此, 可以将问题“ n 个元素的和为 m ”变成“ n−1 个元
素的和为 m−i ”. 通过这种推导, 我们可以简单地累加 D n−1,m−i 来计算 D n,m . 根据这种方法, 具体的平衡 WOTS+签名
算法如算法 1.
算法 1. bw_sig.

输入: l,w;
输出: SIG bw .

1. 设 d 是大小为 l 的数组;
2. m = ⌊l(w−1)/2⌋;
3. for i = l to 1 do
4. for j = 0 to min{w−1,m} do
5. if x ⩾ D i−1,s− j then
6. x = x− D i−1,s− j ;
7. else
8. d[i] = j;
9. break;
10. endif
11. endfor
12. m = m−d[i];
13. endfor
d[i]
14. SIG bw [i] = F (sk i );
15. return SIG bw

λ
算法 1 中, 私钥 sk 由 个随机数据块组成, 即 sk = (sk 1 , sk 2 ,..., sk l ), sk i ∈ {0,1} . 公钥 {pk i } l i=1 是通过对私钥中的
l
每个块迭代应用哈希函数 w−1 次而生成的, 即 pk i = F w−1 (sk i ). 最后, 通过可调整的哈希函数 Th l (详见第 2.2 节) 将
l
这些块合并为公钥 pk, 即 pk = Th l (pk 1 , pk 2 ,..., pk l ). 对于包含 个块的签名 SIG bw , 验证者将哈希函数应用于每个块
′
′
′
′
′
′
w−1−d[i] 次, 即 pk = F w−1−d[i] (SIG bw [i]). 最后, 再次使用 Th l 将这些块合并为 pk , 即 pk = Th l (pk , pk ,..., pk ). 如
i 1 2 l
′
果 pk = pk , 验证者接受此签名.
2.4 超 树
引入超树前, 先介绍 Merkle 树. 为了对 2 h ′ 条消息进行签名, 签名者生成 2 h ′ 个 WOTS+密钥对, 并将这 2 h ′ 个公
钥作为叶子节点构建二叉树. 具体而言, 对于每对叶子节点, 签名者重复应用哈希函数生成对应的父节点, 直到到
达树的根节点, 即这个树的公钥. 在进行签名时, 签名者选择一个 WOTS+叶子节点, 并发布 WOTS+签名以及从叶
子节点到根节点的路径上所有节点的兄弟节点, 这就构成了“认证路径” (详见图 1). 验证者首先从签名中获得
WOTS+公钥, 然后使用认证路径上的节点及其兄弟节点来重建根节点.