实用前向安全双环签名方案解析

### 实用前向安全双环签名方案解析 #### 1. 前向安全环签名方案的定义与模型 前向安全环签名（FS - RS）方案由以下算法组成： - **Setup(1λ)**：以安全参数 λ 为输入，输出包含最大周期数 T 的公共参数 PP。 - **KeyGen(PP)**：以公共参数 PP 为输入，为任意用户输出初始密钥对 (pki, sk(i,0))，用 pki 代表该用户。 - **KeyUp(PP, sk(i,t), t′)**：以用户 pki 的密钥 sk(i,t) 和周期 t′ 为输入，输出更新后的密钥 sk(i,t′)，其中 t ≤ t′。 - **Sign(PP, sk(i,t), m, PK, t)**：以用户 pki 的密钥 sk(i,t)、消息 m、公钥集合 PK = (pk1, · · ·, pkn) 和周期 t 为输入，输出签名 σ。 - **Verify(PP, PK, m, σ, t)**：以消息 - 签名对 (m, σ)、公钥集合 PK 和周期 t 为输入，若签名有效输出 1，否则输出 0。 正确性方面，若对于所有安全参数 λ、所有公共参数 PP ← Setup(1λ)、所有密钥 (pki, sk(i,0)) ← KeyGen(PP)、所有 t ≤ t′，sk(i,t′) ← KeyUp(PP, sk(i,t), t′)、所有 m 和 PK = (pk1, · · ·, pkn)，σ ← Sign(PP, sk(i,t), m, PK, t)，都有 1 = Verify(PP, PK, m, σ, t)，则该 FS - RS 方案正确。 #### 2. 安全模型 ##### 2.1 前向安全不可伪造性 非正式地说，即使攻击者可以自适应地破坏一些诚实参与者并获取他们基于周期的秘密密钥，也无法伪造消息 - 签名对。概率多项式时间（PPT）对手 A 和模拟器 S 之间的正式安全游戏定义如下： - **游戏设置**：S 创建 n 个用户及其对应的密钥对 {(pki, sk(i,0))} ← KeyGen(PP)，其中 PP ← Setup(1λ)，{sk(i,0)} 表示用户 i 的初始秘密密钥。对于每个用户 pki，S 可以将基于周期的秘密密钥更新为 {sk(i,t)}T t = 1。最后，S 将所有公钥返回给 A，并维护一个集合 Q 来记录被破坏的用户。 - **查询操作**：在游戏期间，A 可以向 S 进行以下查询： - **密钥更新**：若 A 在周期 t 对用户 pki 发出密钥更新查询，S 将密钥 sk(i,t) 更新为 sk(i,t + 1) 并增加 t，其中 t ≤ T。 - **签名**：若 A 在周期 t 对消息 m 和公钥集合 PK = {pki, · · · } 发出签名查询，S 使用秘密密钥 sk(i,t) 计算签名 σ 并返回给 A。 - **入侵**：若 A 在周期 ¯t 对用户 pki 发出入侵查询，S 将相应的秘密密钥 sk(i,¯t) 返回给 A。每个用户只能发出一次此查询，之后 A 不能再对该用户进行密钥更新或签名查询。此外，允许 A 对不同用户发出不同的入侵查询。 - **破坏**：若 A 对用户 pki 发出破坏查询，S 将用户的初始秘密密钥 sk(i,0) 返回给 A，并通过包含被破坏的公钥 pki 来更新集合 Q。 - **获胜条件**：在某个时刻，A 输出伪造 (PK∗, t∗, m∗, σ∗)。若满足以下条件，A 赢得游戏： 1. 消息 - 签名对 (m∗, σ∗) 在 PK∗ 和 t∗ 下有效。 2. 对于 PK∗ 中的任何用户 pk∗，但 pk∗ ∉ Q。 3. 伪造 (PK∗, t∗, m∗, ·) 之前未向签名预言机查询过。 4. 若对 PK∗ 中的任何用户在周期 ¯t 进行了入侵查询，入侵周期必须满足 ¯t > t∗。 我们将 A 在上述游戏中的优势定义为 AdvA(λ) = |Pr[A 获胜]|。若对于任何 PPT A，AdvA(λ) 是 λ 的可忽略函数，则前向安全环签名方案是不可伪造的。 ##### 2.2 全密钥暴露下的匿名性 非正式地说，即使攻击者可以访问生成每个用户秘密密钥时使用的所有随机性，给定有效签名和一组公钥，攻击者也无法识别特定签名者。PPT 对手 A 和模拟器 S 之间的正式匿名性游戏定义如下： - **游戏设置**：S 使用与上述不可伪造性游戏相同的方法设置游戏，但有以下差异。首先，S 生成用户的密钥对为 (pki, ski) ← KeyGen(PP; wi)，其中 wi 表示生成用户秘密密钥时使用的随机性。其次，S 将所有用户的公钥返回给 A，并抛掷一枚随机硬币 b 供后续游戏使用。 - **训练阶段**：A 可以在训练阶段向 S 进行签名查询。最后，A 输出两个索引 i0, i1 ∉ Q，其中 Q 表示对破坏预言机的查询集合。 - **挑战阶段**：A 可以在周期 t∗ 对消息 m∗ 和公钥集合 PK∗ = {pki0, pki1, · · · } 发出签名查询，S 使用秘密密钥 sk(ib,t∗) 计算签名 σ 并将其和所有见证 {wi} 返回给 A。最后，A 输出 b′ 作为对 b 的猜测。若 b′ = b，S 输出 1；否则，S 输出 0。我们将 A 在上述游戏中的优势定义为 AdvA(λ) = |Pr[S → 1] - 1/2|。若对于任何 PPT A，AdvA(λ) 是 λ 的可忽略函数，则前向安全环签名方案是匿名的。 需要注意的是，对于（前向安全）T 型环签名，有两种随机性：一种是用于生成/更新用户秘密密钥的随机性 {wi}，另一种是用于生成环签名的随机性 Rands。即使攻击者可以访问所有 {wi} 并在挑战阶段破坏环中的所有用户，我们的匿名性仍然成立。然而，如果攻击者可以访问与环签名相关的随机性 Rands，该环签名的匿名性将丢失。我们的匿名性模型不允许攻击者在整个游戏中访问任何 Rands。 #### 3. 方案构造 我们将基于周期的函数表示为 F(t) = h0  hti i，其中 t = t1||t2|| · · · ||ti = {1, 2}i。设 H :