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

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

com_ver(SIG_ht,PK.seed,root,ADRS,idx_tree,idx_leaf,md ) → (True/False) : 算法用于验证 HT 的根节点是否
′

与提供的承诺一致. 首先, 算法通过索引 idx_leaf 找到消息对应的叶子节点, 并开始使用 ht_sig 中提供的签名值和
认证路径中的哈希值, 逐层重构 HT. 通过对 SIG ht .getsig() 返回的签名值进行递归哈希计算, 算法逐层构建出树的
′ root 一致, 则返回 True, 表明承诺验证成功; 否
内部节点, 最终得到树的根节点. 若计算出的根节点 root 与提供的
则, 返回 False, 表示验证失败. 具体流程见算法 9, 有关 ADRS 的操作参考文献 [30].
算法 9. com_ver.

输入: SIG_ht,PK.seed,root,ADRS,idx_tree,idx_leaf,md ;
′
输出: True/False.
1. ADRS.setLayerAddr(0);
2. ADRS.setTreeAddr(idx_tree);
3. for j = 0 to d −1 do
4. idx_lea f 为 idx_tree 中前 ⌊h/d⌋ bits;
5. idx_tree 为 idx_tree 中后 ⌊h−( j+1)×(h/d)⌋ bits;
′
6. tmp = SIG ht .getsig(j);
7. ADRS.setLayerAddr( j);
8. 根据算法 7 的第 1–14 行生成 root ;
′
9. endfor
′
10. if root == root then
11. return True;
12. else
13. return False;
14. endif

4.6 承诺和证明更新

当有键值对加入时, 首先查询该键值对是否存在于元组 KV 中. 现在我们来讨论两种情况.
情况 1: 若不存在, 承诺值保持不变, 但证明改变. 换言之, 每当验证新的键值对时, 承诺值与前一个相同, 但生
成的证明不同, 因为键值对选择的 DFORC 节点发生了变化. 随后, 根据算法 1–9 来进行验证.
情况 2: 若存在, 则修改承诺值和证明, 并将来自元组 VM 对应的版本号增加 1. 根据元组 ID 中对应的索引, 对

应的叶子节点进行 VM[k] 次哈希, 并根据 Merkle 树调整从叶子节点到根节点的路径, 生成新的承诺值和证明. 接
下来, 根据算法 1–算法 9 对进行重新认证. 请注意, 当验证证明的正确性时, 还需要对 ID[key] 进行 VM[k] 次哈希,
以获得重建 DFORC 的新叶子节点.

5 安全性分析

在本节中, 我们通过以下定理来证明方案的量子安全. 需要注意的是, F 和 H 只是 Th 的替代哈希, 其中 F 对
应于消息长度 , 2n.
n H 对应于消息长度
定理 1. 对于方案中的参数 n、w、h、d、m、t、k, 如果满足以下条件, 那么 EQAS 是 PQ-EU-CMA 安全.
● Th (也是 F 和 H) 针对不同的调整, 具有后量子单函数多目标碰撞抗性.
● F 针对不同的调整, 具有后量子单函数多目标决策第 2 原像抗性.
● PRF 和 PRF msg 是后量子伪随机函数族.
● H msg 具有后量子交错目标子集抗性.