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

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

更具体地说, 如公式 (11):

InSec PQ-EU-CMA (EQAS;ξ,q s ) ⩽ InSec PQ-PRF (PRF;ξ,q 1 )+InSec PQ-PRF (PRF msg ;ξ,q s )+InSec PQ-ITSR (H msg ;ξ,q s )
+InSec PQ-SM-TCR (T h ;ξ,q 2 )+3·InSec PQ-SM-TCR (F;ξ,q 3 )+InSec PQ-SM-DSPR (F;ξ,q 3 ) (11)
其中, PQ-PRF, PQ-ITSR 和 PQ-SM-TCR 的概念参考文献 [19]. 首先使用固定签名数量 (以及 Oracle 查询数量) 的
通用攻击来估计上述不安全级别. 然后, 计算对手的计算复杂度, 以获得在 EU-CMA 博弈中获胜的成功概率.
证明: 本节的安全证明借鉴了文献 [19] 中的证明方法, 为了证明 EQAS 方案的 EU-CMA 安全性, 我们通过引
入 5 个博弈 (GAME.0–GAME.4) 逐步构建敌手成功的概率界限. 每个博弈代表了签名方案的一个不同近似, 从而
使我们能够对签名方案的安全性进行详细分析. 在 GAME.0 中, 敌手面临的是一个真实的签名场景. 这里, 敌手可
以提出查询, 得到合法的签名, 试图找到漏洞以伪造签名. 在 GAME.1 中, 我们用随机数替换 PRF (伪随机函数) 的
输出, 用于生成 BW 和 DFORC 私钥. 我们需要在不让敌手察觉的情况下完成这一替换. 具体做法是将私钥生成的
每个秘密值随机替换为相同大小的随机值, 但保证这些随机值与公钥的计算保持一致, 即: 公钥根据这些随机值生

成, 使得签名过程看起来仍然有效. 为了使敌手无法察觉, 这里的“伪签名”设计仍然保证签名对消息 m 的验证通
过, 因为我们在使用随机值替换时, 确保这些值满足签名验证的结构. 敌手无法区分 GAME.1 与 GAME.0, 因为伪
签名的生成与真实签名生成无异, 唯一的不同在于使用了随机替代的密钥. 敌手在 GAME.0 和 GAME.1 之间成功
概率的差异如下:

|Succ GAME.1 (A)−Succ GAME.0 (A)| ⩽ InSec PQ-PRF (PRF;ξ,q 1 ) (12)
其中, InSec PQ-PRF 表示 PRF 的不安全性度量, ξ 表示敌手在博弈中的查询空间大小, q 1 为敌手的查询次数.
在 GAME.2 中, 我们将用于消息哈希的 PRF msg 替换为一个真正的随机函数. 在消息 m 通过的 PRF msg 后, 得到
一个随机值, 这个随机值用于生成签名, 要确保这个随机值与之前生成的私钥值对应. 伪签名的设计需要使得消息
哈希结果可验证. 具体方法是利用哈希值的随机性生成伪签名, 但这些伪签名在结构上与真实签名无异, 因此签名
验证算法对这些伪签名的验证仍然通过. 由于 PRF msg 的输出在 GAME.1 中已被替换为随机数, 因此敌手无法通过
多次查询来区分这些伪签名, 因为它们与真实签名完全一致. 敌手在 GAME.1 和 GAME.2 之间的成功概率差异为:

|Succ GAME.2 (A)−Succ GAME.1 (A)| ⩽ InSec PQ-PRF (PRF msg ;ξ,q s ) (13)
其中, InSec PQ-PRF 表示 PRF msg 的不安全性度量, q s 为消息查询次数.
在 GAME.3 中, 攻击者无法直接找到签名的第 2 原像, 而是试图找到签名结构中的弱点来伪造签名. 具体而
言, 攻击者利用签名 Oracle 查询到的合法签名, 尝试推断出签名中哈希函数的结构, 并找到一种方式生成一个有
效的伪造签名. 在这里, 我们确保签名对所有使用的密钥都是随机的. 这意味着签名的生成不仅依赖于随机密钥,
还涉及随机化的结构, 使得敌手无法利用之前的已知信息重现签名过程. 伪签名在此步骤中是通过随机化签名的
各个部分来完成的, 通过引入额外的随机值来扰乱签名结构, 使得敌手难以通过已知的签名信息推测签名的生成
过程. 这个阶段的伪造主要依赖于通过伪造签名本身的结构, 使得签名能够在验证中通过. 如果敌手能够在此阶段
识别出伪签名, 则说明我们的密钥随机化过程被破坏. 但在理想情况下, 伪签名与真实签名无法区分. 因此, 敌手在
GAME.3 和 GAME.2 之间的成功概率差异为:

|Succ GAME.3 (A)−Succ GAME.2 (A)| ⩽ InSec PQ-ITSR (H msg ;ξ,q s ) (14)
其中, InSec PQ-ITSR 表示哈希函数 H msg 的抗扰性度量.
在 GAME.4 中, 与 GAME.3 不同, 攻击者的目标是找到一个与已知签名结构相同的“第 2 原像”, 可以伪造出
一个新的消息-签名对, 使得该签名对通过验证. 通过将哈希函数替换为理想的随机函数 Oracle, 并在生成签名过
程中引入随机扰动, 使得攻击者难以找到第 2 原像. 具体来说, 生成伪签名时引入一个随机值 r, 将该随机值与消
m 结合生成一个伪秘密值, 然后使用伪秘密值通过哈希函数生成签名, 使得签名与公钥的关系保持一致. 通过确
息
保伪签名在验证过程中能够通过哈希和承诺机制的检验, 避免敌手发现伪造的过程. 此时的敌手可能会尝试通过
攻击树的构建算法来推测私钥, 但树结构的抗碰撞性 (TCR) 和抗冲突性确保了此类攻击难以成功. 敌手在 GAME.3
和 GAME.4 之间的成功概率差异: