基于格的具有紧密安全性的短身份基签名

### 基于格的具有紧密安全性的短身份基签名 #### 1. 自适应安全身份基签名的通用构造 在这部分，我们将介绍两种把非自适应安全的身份基签名方案转换为自适应安全方案的方法。设 IBS′ = (Setup′, KeyExt′, Sig′, Ver′) 是一个身份空间为 ID、消息空间为 M 的身份基签名方案，CHF = (CHGen, CHash, CHColl) 是变色龙哈希函数，H1 : {0, 1}∗→ID，H2 : {0, 1}∗→M 是随机预言机，且 ℓ = ℓ(λ) ∈N。我们在图 2 中定义了新的身份基签名方案 IBS，在图 5 中定义了 IBSROM。 需要注意的是，第一种转换方法在标准模型下工作，而第二种使用了随机预言机。引入第二种转换方法的原因是，我们基于格的非自适应安全构造已经使用了随机预言机，所以可以采用第二种更高效且无需依赖额外原语（如变色龙哈希函数）的转换方法。 ##### 1.1 标准模型下的转换 若 IBS′ 是非自适应安全的，且 CHF 是抗碰撞的变色龙哈希函数，那么图 2 中定义的 IBS 就是自适应安全的。显然，如果 IBS′ 是 ρ - 完备的，那么 IBS 也是 ρ - 完备的。 **定理 1**：设 IBS′ 是一个身份基签名方案，CHF 是一个 εtrap - 变色龙哈希函数。若 IBS′ 是 UF - naCMA 安全的，且 CHF 是抗碰撞的，那么 IBS 是 UF - CMA 安全的。具体来说，对于每个最多进行 QS 次签名查询和 QC 次秘密密钥查询的算法 A，存在算法 B1 和 B2，使得： AdvUF - CMA A,IBS (λ) ≤Advcoll B1,CHF(λ) + AdvUF - naCMA B2,IBS′ (λ) + (QC + 2QS)εtrap 并且 T(B1) ≈T(A)，T(B2) ≈T(A)。 我们通过游戏 G0 和 G1 以及归约 B1 和 B2 来证明这个定理。游戏 G0 和 G1 正式展示在图 3 中。在每个游戏 i ∈{0, 1} 里，我们将敌手 A 的优势记为 Advi(A) := Pr { GA i ⇒1 } 。游戏 G0 是原始的 UF - CMA 游戏，所以我们的目标是界定 Adv0(A)。游戏 G1 会跟踪所有密钥和签名查询的哈希身份与消息。也就是说，它维护列表 Hm 和 Hid，若 (id′, id, r) ∈Hid，意味着敌手请求了身份 id 的秘密密钥，并且在回答查询时，游戏使用 r 将 id 哈希为 id′，即 id′ = CHash(hk, id; r)。类似地，若元组 ((id′, id, r), (μ′, μ, s)) 在 Hm 中，表明在某次签名查询中，分别使用随机性 r 和 s 将 id 哈希为 id′，将 μ 哈希为 μ′。在得到 A 的伪造签名 (id∗, μ∗, (r∗, s∗, σ∗)) 后，游戏会检查额外条件，若其中一个条件成立则返回 0。这些条件被建模为事件 bad1 和 bad2。设 bad := bad1 ∨ bad2，我们可以将两个游戏的差异界定为： |Adv0(A) − Adv1(A)| ≤ Pr [bad] 接下来，考虑 bad1 的定义： bad1 := (∃(id′, id, r) ∈Hid : CHash(hk, id∗; r∗) = id′) 这意味着存在一个碰撞： CHash(hk, id∗; r∗) = id′ = CHash(hk, id; r) 这个碰撞是非平凡的，因为 id∗∉Lid，所以 id∗≠ id。类似地，若 bad2 发生，也能找到一个非平凡的碰撞。在不知道哈希陷门 td 的情况下，我们可以高效地模拟 G1 并检查发生了哪种碰撞。因此，如果 bad 为真，我们有一个直接的归约 B1 能为给定的 hk 找到碰撞。显然，B1 的运行时间主要由运行一次 A 决定。我们可以得到： Pr [bad] ≤ Advcoll B1,CHF(λ) 最后，我们通过一个归约 B2 来界定敌手 A 在游戏 G1 中的优势，B2 参与 IBS′ 方案的 UF - naCMA 游戏。归约 B2 利用陷门 td，正式展示在图 4 中。归约 B2 选择一个变色龙哈希密钥及其陷门，然后使用随机性 ri 和 si 将 QS 个任意值（在我们的表述中为 0）哈希为哈希值 id′ i 和 μ′ i。这些哈希值随后会作为（非自适应）签名查询提供给 UF - naCMA 挑战者。B2 会得到一个公钥 mpk′ 和这些查询的签名 σ′ i。之后，当 A 发出第 i 个（自适应）签名查询 (id, μ) 时，归约使用其陷门找到随机性 r 和 s，使得 CHash(hk, id; r) = id′ i 且 CHash(hk, μ; s) = μ′ i，即： r ← CHColl(hk, td, 0, ri, id)，s ← CHColl(hk, td, 0, si, μ) 然后，根据方案的定义，归约可以直接返回 (r, s, σ′ i)，这是正确的。在非自适应地获取秘密密钥后，我们采用类似的碰撞策略来处理自适应秘密密钥查询。在得到 A 的伪造签名 (id∗, μ∗, (r∗, s∗, σ∗)) 后，B2 检查所有获胜条件并输出 (CHash(hk, id∗; r∗), CHash(hk, μ∗; s∗), σ∗)。根据变色龙哈希函数的性质，使用陷门进行的碰撞查找和诚实签名在统计上是接近的。具体来说，G1 和 B2 模拟的游戏之间的统计距离可以被 (QC + 2QS)εtrap 界定，因为 B2 在每次秘密密钥查询时应用一次 CHColl，在每次签名查询时应用两次。现在假设 A 获胜，我们来证明 B2 能赢得 UF - naCMA 游戏。根据方案验证算法的定义，如果 A 输出了消息 μ∗ 和身份 id∗ 的有效签名 (r∗, s∗, σ∗)，那么对于 IBS′ 来说，σ∗ 是身份 CHash(hk, id∗; r∗) 和消息 CHash(hk, μ∗; s∗) 的有效签名。所以我们只需检查新鲜性：为了推出矛盾，假设 CHash(hk, id∗; r∗) 的秘密密钥被 B2（非自适应地）查询过。那么存在某个 i ∈[QC]，使得 CHash(hk, id∗; r∗) = CHash(hk, 0; ¯ri)。B2 回答签名查询的方式表明，对于第 i 次密钥查询的身份 id 和某个随机性 r，有 (CHash(hk, 0; ¯ri), id, r) ∈Hid，这正是事件 bad1 的定义，而我们之前已经排除了这种情况。使用 bad2 进行类似的论证可以表明，(CHash(hk, id∗; r∗), CHash(hk, μ∗; s∗)) 没有被 B2 查询过。因此，我们有： Adv1(A) ≤ negl(λ) + AdvUF - naCMA B2,IBS′ (λ) 最后，B2 的运行时间主要由评估多项式时间的变色龙哈希和运行敌手 A 决定。 ##### 1.2 随机预言机模型下的转换 若 IBS′ 是非自适应安全的，且 ℓ∈ω(log λ)，那么图 5 中定义的 I