3.安全分析

通过将 H 建模为随机 oracle，我们可以证明我们在通用组模型中构造的强不可伪造性（以及基本不可伪造性）。

依赖于 q 型假设，就像在中对 PS 签名所做的那样，在这里似乎非常困难，因为使用秘密值 y 的多个幂会阻止使用中的策略。幸运的是，证明我们方案的不可链接性不需要这样的假设，因为我们证明了这个属性无条件地成立。这由以下定理正式陈述，证明如下：

在这个证明中，我们将使用寄存器 L 来处理随机 oracle 查询，对于在yi · m,i) β5,,3 ·β1,i ·做 α1,i · yi 每个查询 x，我们首先检查 L[x] 是否已经包含一个标量 y ∈ Z，在这种情况下我们返回后者。否则，我们生成一个随机的 y 返回给 A，然后存储在 L[x] 中。

[σ2]中 x 的任务 1 次单项式也包含一些rk或 r 。然后我们必须有α1,0 = 0，这意味着左侧的任何单项式也包含一些rk或 r 。这使我们能够得出结论β1,i = 0∀i 和β5,,3 = 0∀∈[1, qD]。

最后，前面关系中的因子 (x yi · mi)表示[σ2]中的任何单项式在 x 或 y 中至少有 1 次。这意味着β4,k,1 = β5,,1 = 0,∀k ∈ [1, qR]和 ∈ [1, qD]。然后我们还可以简化[σ2]。

我们证明中涉及的多项式数量为 3n 2 2qR 4qD qG，每个多项式的次数至多为 2n。使用 Schwartz‑Zippel 引理，我们可以将此类事件的概率限制为2n·(3n 2 2qR 4qD qG)2 2p，这是微不足道的。

不可链接性证明。我们在此证明， {mi}i∈I上的派生签名σI独立于原始签名 σ = (σ1, σ2, σ3, σ) 和编辑消息集{mi}i∈I 分布。