公钥密码算法可证明安全理论：第一讲

1 引入

1.1 柯克霍夫原则 Kerckhoffs’s Principle

def 即使密码系统的任何细节已为人悉知，只要密钥或未泄漏，它也应是安全的
加密系统的安全性不应依赖于算法的保密性，而应基于加密密钥的保密性

1.2 公钥密码学 Public-key Cryptography

def
- 每个用户都有一对密钥：私钥和公钥
- 公钥是公开已知的，但私钥是保密的
- 给定公钥，推断出私钥在计算上是不可行的
分类
- 公钥加密：允许双方通过不安全的通道交换消息，提供了保密性
- 数字签名：允许双方对电子文档进行签名，提供了不可伪造性

1.3 安全

过去的验证方式：搜索攻击（search for attacks），存在问题：
- 永远无法确定攻击不存在
- 安全性最多只能被视为启发式的，不能排除存在未知攻击方式的可能性

1.3.1 可证明安全

def 旨在将方案的安全性与困难问题联系起来，先指定攻击者能力和方案的安全目标，再将破坏方案安全目标的敌手转变为针对该方案所基于的困难问题的安全目标的敌手。
分类
- 基于游戏的证明 Game-based Proof
  - 安全规约：若存在敌手 $A$ 能破坏方案，则存在有效算法 $B$ 借助 $A$ 解决困难问题。
  - Game Hopping：在特定攻击环境中运行的攻击者具有未知的成功概率，改变攻击环境直到可以计算出攻击者的成功概率
- 基于模拟的证明 Simulation-based Proof

1.3.2 渐近安全与具体安全

渐近安全：使用多项式时间可归约性对计算问题的难度进行分类
具体安全：实际上由于需要实例化安全参数，需确切知道减少的效率，参数化敌手可用的所有资源
def 若对手可以在时间 $t$ 中以至少 $ε_Σ$ 的概率打破方案 $Σ$ ，则存在敌手可以在时间 $t'$ 内以至少 $ε_Π$ 的概率打破困难问题 $Π$ ，其中 $t≈t^′$ ， $ε_Σ ≈ε_Π$
安全参数 $λ$ 的选取： $ε_Π=2^{-λ}-γ$

2 概念、定义和模型

2.1 常用符号及定义

2.2 数字签名

2.2.1 数字签名的算法定义

$Setup(1^λ )→params$
$KeyGen(1^λ,params)→(SK,PK)$
$Sign(M,SK,params)→σ$
$Verify(M,σ,PK,params)→0/1$

2.2.2 数字签名的安全模型

def 安全模型：定义敌手所知道的内容，不同安全模型破坏方案的难度不同

1. 针对选择消息攻击的存在不可伪造性 EU-CMA

游戏在挑战者 $C$ 和敌手 $A$ 之间的执行过程：

$Setup$ ： $C$ 运行 $Setup(1^λ )→params$ ，并将 $params$ 返回给 $A$
$KeyGen$ ： $C$ 运行 $KeyGen(1^λ，params)→(SK，PK)$ ，并将 $PK$ 返回给 $A$
$Query$ ：
- 动态地提交消息 $M_i$
- $C$ $C$ 运行 $Sign(M_i，SK，params)→σ_i$ $S i g n (M_{i} ， S K ， p a r am s) \to σ_{i}$ ，并将 $σ_i$ $σ_{i}$ 返回给 $A$ $A$
  - 其中 $i=\{1,2，⋯, q_S\}$
  - 设消息 $M=\{M_1, ⋯, M_{q_S }\}$
  - 设 $Q=\{(M_1, σ_1 ), ⋯, (M_{q_s}, σ_{q_s } )\}$
$Forgery$ ： $A$ 在消息 $M^∗$ 上输出签名 $σ^∗$ 。满足下述情况则 $A$ 将赢得游戏：
- $Verify(M^∗, σ^∗, PK, params)→1$
- $M^∗∉M$

定义
如果不存在任何敌手 $A$ 在进行 $𝑞_𝑠$ 次签名查询后，能在时间 $𝑇$ 内以至少 $ϵ(λ)$ 的优势赢得上述游戏，则签名方案在 EU-CMA 安全模型中是 $(𝑇,𝑞_𝑠,ϵ(λ))$ - 安全的，即

$Pr[Verify(M^∗,\sigma ^∗,PK,params) \to 1 | M^∗ \notin M)]<\epsilon(λ)$

2. 针对选择消息攻击的强不可伪造性 SU-CMA

游戏在挑战者 $C$ 和敌手 $A$ 之间的执行过程：

$Setup$ ： $C$ 运行 $Setup(1^λ )→params$ ，并将 $params$ 返回给 $A$
$KeyGen$ ： $C$ 运行 $KeyGen(1^λ，params)→(SK，PK)$ ，并将 $PK$ 返回给 $A$
$Query$ ：
- 动态地提交消息 $M_i$
- $C$ $C$ 运行 $Sign(M_i，SK，params)→σ_i$ $S i g n (M_{i} ， S K ， p a r am s) \to σ_{i}$ ，并将 $σ_i$ $σ_{i}$ 返回给 $A$ $A$
  - 其中 $i=\{1,2，⋯, q_S\}$
  - 设消息 $M=\{M_1, ⋯, M_{q_S }\}$
  - 设 $Q=\{(M_1, σ_1 ), ⋯, (M_{q_s}, σ_{q_s } )\}$
$Forgery$ ： $A$ 在消息 $M^∗$ 上输出签名 $σ^∗$ 。满足下述情况则 $A$ 将赢得游戏：
- $Verify(M^∗, σ^∗, PK, params)→1$
- $(M^∗, σ^∗)∉Q$ ： $A$ 可以询问关于 $M^∗$ 的签名，但输出一个不同的签名即可

定义

如果不存在任何敌手 $A$ 在进行 $𝑞_𝑠$ 次签名查询后，能在时间 $𝑇$ 内以至少 $ϵ(λ)$ 的优势赢得上述游戏，则签名方案在 SU-CMA 安全模型中是 $(𝑇,𝑞_S,ϵ(λ))$ - 安全的，即

$Pr[Verify(M^∗,\sigma ^∗,PK,params) \to 1 | (M^∗, \sigma ^∗)\notin Q)]<\epsilon(λ)$

2.3 公钥加密

2.3.1 公钥加密的算法定义

$Setup(1^λ )→params$
$KeyGen(1^λ,params)→(SK,PK)$
$Enc(M,PK,params)→CT$
$Dec(CT,SK,params)→M/⊥$

2.3.2 公钥加密的安全模型

1. 针对选择明文攻击的不可区分性 IND-CPA

游戏在挑战者 $C$ 和敌手 $A$ 之间的执行过程：

$Setup$ ： $C$ 运行 $Setup(1^λ )→params$ ，并将 $params$ 返回给 $A$
$KeyGen$ ： $C$ 运行 $KeyGen(1^λ，params)→(SK，PK)$ ，并将 $PK$ 返回给 $A$
$Challenge$ ：
- $A$ 提交两条消息 $M_0$ 和 $M_1$
- $C$ 掷出一枚无偏硬币，得到比特 $b∈ \{0,1\}$
- $C$ 运行 $Enc(M_b, PK, params)→CT^∗$ ，并返回 $CT^∗$ 给 $A$
$Output$ ： $A$ 在 $b$ 上输出其猜测 $b'$ ，如果 $b^′=b$ ，则 $A$ 赢得游戏

定义

如果不存在可以赢得上述游戏的敌手 $A$ ，则公钥加密方案在 IND-CPA 安全模型中是 $(𝑇,ϵ(λ))$ - 安全的，即

$|Pr[b^′=b]-\frac{1}{2}|<\epsilon(λ)$

2. 针对（两阶段）选择密文攻击的不可区分性 IND-CCA2

游戏在挑战者 $C$ 和敌手 $A$ 之间的执行过程：

$Setup$ ： $C$ 运行 $Setup(1^λ )→params$ ，并将 $params$ 返回给 $A$
$KeyGen$ ： $C$ 运行 $KeyGen(1^λ，params)→(SK，PK)$ ，并将 $PK$ 返回给 $A$
$Phase$ I：
- $A$ 动态地提交密文 $CT_i$ ，其中 $i=1, 2, ⋯, q_1$
- $C$ 运行 $Dec(CT_i,SK,params)→M_i$ ，并将 $M_i$ 返回给 $A$
$Challenge$ ：
- $A$ 提交两条消息 $M_0$ 和 $M_1$
- $C$ 掷出一枚无偏硬币，得到比特 $b∈ \{0,1\}$
- $C$ 运行 $Enc(M_b, PK, params)→CT^∗$ ，并返回 $CT^∗$ 给 $A$
$Phase$ II：
- $A$ $A$ 动态地提交密文 $CT_j$ $C T_{j}$ ，但有以下限制条件：
  - $CT^∗ ≠ CT_j$ ，其中 $j=1,2,⋯,q_2$
  - $C$ 运行 $Dec(CT_j,SK,params)→M_j$ , 并将 $M_j$ 返回给 $A$
  - $q_D=q_1+q_2$
$Output$ ： $A$ 在 $b$ 上输出其猜测 $b'$ ，如果 $b^′=b$ ，则 $A$ 赢得游戏

定义

如果不存在可以赢得上述游戏的敌手 $A$ ，则公钥加密方案在 IND-CCA2 安全模型中是 $(𝑇,ϵ(λ))$ - 安全的，即

$|Pr[b^′=b]-\frac{1}{2}|<\epsilon(λ)$

2.4 基于身份加密

2.4.1 基于身份加密的算法定义

$Setup(1^λ )→(MSK,params)$ ：多输出一个主私钥 $MSK$
$KeyGen(ID,MSK,params)→SK_{ID}$ ：输入身份标识 $ID∈\{0,1\}^∗$ 而非安全参数 $1^λ$
$Enc(M,ID,params)→CT$
$Dec(CT,SK_{ID},params)→M/⊥$

2.4.2 基于身份加密的安全模型

1. 针对（两阶段）选择明文攻击的不可区分性 IND-ID-CPA

游戏在挑战者 $C$ 和敌手 $A$ 之间的执行过程：

$Setup$ ： $C$ 运行 $Setup(1^λ )→(MSK,params)$ ，并将 $params$ 返回给 $A$
$Phase$ I：
- $A$ 动态地提交身份标识 $ID∈\{0,1\} ^∗$ ，其中 $i=1, 2, ⋯, q_1$
- $C$ 运行 $KeyGen(ID_i,MSK,params)→SK_{ID_i}$ ，并将 $SK_{ID_i}$ 返回给 $A$
$Challenge$ ：
- $A$ 提交一个身份标识 $ID^∗∈\{0,1\}^∗$ （ $ID^∗∉\{ID_1,ID_2,⋯,ID_{q_1 }\}$ ）和两条长度相等的消息 $M_0$ 和 $M_1$
- $C$ 掷出一枚无偏硬币，得到比特 $b∈ \{0,1\}$
- $C$ 运行 $Enc(M_b, ID^*, params)→CT^∗$ ，并返回 $CT^∗$ 给 $A$
$Phase$ II：
- $A$ 动态地提交身份标识 $ID_j$ ，限制 $ID_j≠ID^∗$ ，其中 $j=1,2,⋯,q_2$
- $C$ 运行 $KeyGen(ID_j,MSK,params)→SK_{ID_j}$ ，并将 $SK_{ID_j}$ 返回给 $A$
- $q_K=q_1+q_2$
$Output$ ： $A$ 在 $b$ 上输出其猜测 $b'$ ，如果 $b^′=b$ ，则 $A$ 赢得游戏

定义

如果不存在任何敌手 $A$ 在进行 $𝑞_k$ 次密钥查询后，能在时间 $𝑇$ 内以至少 $ϵ(λ)$ 的优势赢得上述游戏，则基于身份加密方案在 IND-ID-CPA 安全模型中是 $(𝑇,𝑞_k,ϵ(λ))$ - 安全的，即

$|Pr[b^′=b]-\frac{1}{2}|<\epsilon(λ)$

2. 针对两阶段选择性 ID 的选择明文攻击的不可区分性 IND-sID-CPA

游戏在挑战者 $C$ 和敌手 $A$ 之间的执行过程：

$Inititialization$ ： $A$ 提前提交一个身份标识 $ID^∗∈\{0,1\}^∗$
$Setup$ ： $C$ 运行 $Setup(1^λ )→(MSK,params)$ ，并将 $params$ 返回给 $A$
$Phase$ I：
- $A$ 动态地提交身份标识 $ID_i∈\{0,1\}^∗$ ，其中 $i=1, 2, ⋯, q_1$
- $C$ 运行 $KeyGen(ID_i,MSK,params)→SK_{ID_i}$ ，并将 $SK_{ID_i}$ 返回给 $A$
$Challenge$ ：
- $A$ 提交两条长度相等的消息 $M_0$ 和 $M_1$
- $C$ 掷出一枚无偏硬币，得到比特 $b∈ \{0,1\}$
- $C$ 运行 $Enc(M_b, ID^*, params)→CT^∗$ ，并返回 $CT^∗$ 给 $A$
$Phase$ II：
- $A$ 动态地提交身份标识 $ID_j$ ，限制 $ID_j≠ID^∗$ ，其中 $j=1,2,⋯,q_2$
- $C$ 运行 $KeyGen(ID_j,MSK,params)→SK_{ID_j}$ ，并将 $SK_{ID_j}$ 返回给 $A$
- 令 $q_K=q_1+q_2$
$Output$ ： $A$ 在 $b$ 上输出其猜测 $b'$ ，如果 $b^′=b$ ，则 $A$ 赢得游戏

定义

如果不存在任何敌手 $A$ 在进行 $𝑞_k$ 次密钥查询后，能在时间 $𝑇$ 内以至少 $ϵ(λ)$ 的优势赢得上述游戏，则基于身份加密方案在 IND-sID-CPA 安全模型中是 $(𝑇,𝑞_k,ϵ(λ))$ - 安全的，即

$|Pr[b^′=b]-\frac{1}{2}|<\epsilon(λ)$

3. 针对（两阶段）选择密文攻击的不可区分性 IND-ID-CCA2

游戏在挑战者 $C$ 和敌手 $A$ 之间的执行过程：

$Setup$ ： $C$ 运行 $Setup(1^λ )→(MSK,params)$ ，并将 $params$ 返回给 $A$
$Phase$ I：
- $KeyGen$ $Key G e n$ $Query$ $Q u ery$ ：
  - $A$ 动态地提交身份标识 $ID_i∈\{0,1\}^∗$ ，其中 $i=1, 2, ⋯, q_1$
  - $C$ 运行 $KeyGen(ID_i,MSK,params)→SK_{ID_i}$ ，并将 $SK_{ID_i}$ 返回给 $A$
- $Decryption$ $Decry pt i o n$ $Query$ $Q u ery$ ：
  - $A$ 动态地提交密文 $(ID_k, CT_k)$ ，其中 $k=1, 2, ⋯, q_1'$
  - $C$ 运行 $KeyGen(ID_k,MSK,params)→SK_{ID_k}$ 和 $Dec(CT_k,SK_{ID_k},params)→M_k$ ，并将 $M_k$ 返回给 $A$
$Challenge$ ：
- $A$ 提交一个身份标识 $ID^∗∈\{0,1\}^∗$ （ $ID^∗∉\{ID_1,ID_2,⋯,ID_{q_1 }\}$ ）和提交两条长度相等的消息 $M_0$ 和 $M_1$
- $C$ 掷出一枚无偏硬币，得到比特 $b∈ \{0,1\}$
- $C$ 运行 $Enc(M_b, PK, params)→CT^∗$ ，并返回 $CT^∗$ 给 $A$
$Phase$ II：
- $KeyGen$ $Key G e n$ $Query$ $Q u ery$ ：
  - $A$ 动态地提交身份标识 $ID_j$ ，限制 $ID_j≠ID^∗$ ，其中 $j=1,2,⋯,q_2$
  - $C$ 运行 $KeyGen(ID_j,MSK,params)→SK_{ID_j}$ ，并将 $SK_{ID_j}$ 返回给 $A$
- $Decryption$ $Decry pt i o n$ $Query$ $Q u ery$ ：
  - $A$ 动态地提交密文 $(ID_l, CT_l)$ ，限制 $(ID_l, CT_l)≠(ID^∗, CT^∗)$ ，其中 $l=1, 2, ⋯, q_2'$
  - $C$ 运行 $KeyGen(ID_l,MSK,params)→SK_{ID_l}$ 和 $Dec(CT_l,SK_{ID_l},params)→M_l$ ，并将 $M_l$ 返回给 $A$
  - 令 $q_K=q_1+q_2$ ， $q_D'=q_1'+q_2'$
$Output$ ： $A$ 在 $b$ 上输出其猜测 $b'$ ，如果 $b^′=b$ ，则 $A$ 赢得游戏

定义

如果不存在任何敌手 $A$ 在进行 $q_K$ 密钥生成查询和 $q_D$ 次解密查询后，能在时间 $𝑇$ 内以至少 $ϵ(λ)$ 的优势赢得上述游戏，则基于身份加密方案在 IND-ID-CCA2 安全模型中是 $(𝑇,𝑞_K, q_D, ϵ(λ))$ - 安全的，即

$|Pr[b^′=b]-\frac{1}{2}|<\epsilon(λ)$

4. 针对两阶段选择性 ID 的选择密文攻击的不可区分性 IND-sID-CCA2

游戏在挑战者 $C$ 和敌手 $A$ 之间的执行过程：

$Inititialization$ ： $A$ 提前提交一个身份标识 $ID^∗∈\{0,1\}^∗$
$Setup$ ： $C$ 运行 $Setup(1^λ )→(MSK,params)$ ，并将 $params$ 返回给 $A$
$Phase$ I：
- $KeyGen$ $Key G e n$ $Query$ $Q u ery$ ：
  - $A$ 动态地提交身份标识 $ID_i∈\{0,1\}^∗$ ，其中 $i=1, 2, ⋯, q_1$
  - $C$ 运行 $KeyGen(ID_i,MSK,params)→SK_{ID_i}$ ，并将 $SK_{ID_i}$ 返回给 $A$
- $Decryption$ $Decry pt i o n$ $Query$ $Q u ery$ ：
  - $A$ 动态地提交密文 $(ID_k, CT_k)$ ，其中 $k=1, 2, ⋯, q_1'$
  - $C$ 运行 $KeyGen(ID_k,MSK,params)→SK_{ID_k}$ 和 $Dec(CT_k,SK_{ID_k},params)→M_k$ ，并将 $M_k$ 返回给 $A$
$Challenge$ ：
- $A$ 提交两条长度相等的消息 $M_0$ 和 $M_1$
- $C$ 掷出一枚无偏硬币，得到比特 $b∈ \{0,1\}$
- $C$ 运行 $Enc(M_b, PK, params)→CT^∗$ ，并返回 $CT^∗$ 给 $A$
$Phase$ II：
- $KeyGen$ $Key G e n$ $Query$ $Q u ery$ ：
  - $A$ 动态地提交身份标识 $ID_j$ ，限制 $ID_j≠ID^∗$ ，其中 $j=1,2,⋯,q_2$
  - $C$ 运行 $KeyGen(ID_j,MSK,params)→SK_{ID_j}$ ，并将 $SK_{ID_j}$ 返回给 $A$
- $Decryption$ $Decry pt i o n$ $Query$ $Q u ery$ ：
  - $A$ 动态地提交密文 $(ID_l, CT_l)$ ，限制 $(ID_l, CT_l)≠(ID^∗, CT^∗)$ ，其中 $l=1, 2, ⋯, q_2'$
  - $C$ 运行 $KeyGen(ID_l,MSK,params)→SK_{ID_l}$ 和 $Dec(CT_l,SK_{ID_l},params)→M_l$ ，并将 $M_l$ 返回给 $A$
  - 令 $q_K=q_1+q_2$ ， $q_D'=q_1'+q_2'$
$Output$ ： $A$ 在 $b$ 上输出其猜测 $b'$ ，如果 $b^′=b$ ，则 $A$ 赢得游戏

定义

如果不存在任何敌手 $A$ 在进行 $q_K$ 密钥生成查询和 $q_D$ 次解密查询后，能在时间 $𝑇$ 内以至少 $ϵ(λ)$ 的优势赢得上述游戏，则基于身份加密方案在 IND-sID-CCA2 安全模型中是 $(𝑇,𝑞_K, q_D, ϵ(λ))$ - 安全的，即

$|Pr[b^′=b]-\frac{1}{2}|<\epsilon(λ)$

2.5 基于身份签名

2.5.1 基于身份签名的算法定义

$Setup(1^λ )→(MSK,params)$ ：多输出一个主私钥 $MSK$
$KeyGen(ID, MSK, params)→SK_{ID}$ ：输入身份标识 $ID∈\{0,1\}^∗$ 而非安全参数 $1^λ$
$Sign(M,SK_{ID},params)→σ$
$Verify(M,σ,ID,params)→0/1$

2.5.2 基于身份签名的安全模型

1. 针对选择消息攻击的存在不可伪造性 EU-ID-CMA

游戏在挑战者 $C$ 和敌手 $A$ 之间的执行过程：

$Setup$ ： $C$ 运行 $Setup(1^λ )→(MSK,params)$ ，并将 $params$ 返回给 $A$
$KeyGen$ $Query$ ：
- $A$ 动态地提交身份标识 $ID_i∈\{0,1\}^∗$ ，其中 $i=1, 2, ⋯, q_1$
- $C$ 运行 $KeyGen(ID_i,MSK,params)→SK_{ID_i}$ ，并将 $SK_{ID_i}$ 返回给 $A$
- 令 $Q_K=\{ID_1, ⋯, ID_{q_1}\}$
$Signing$ $Query$ ：
- $A$ 提交身份标识 $ID_j'∈\{0,1\}^∗$ 和消息 $M_j∈\{0,1\}^∗$ ，其中 $j=1,2,⋯,q_2$
- $C$ 运行 $KeyGen(ID_j',MSK,params)→SK_{ID_j'}$ 和 $Sign(M_j', SK, params)→σ_j'$ ，
- 将 $σ_j'$ 返回给 $A$ ，令 $Q_S={(ID_1^′,M_1 ),⋯(ID_{q_2}^′,M_{q_2})}$
$Forgery$ ： $A$ 输出 $(ID^∗, M^∗,σ^∗)$ 。下述情况 $A$ 将赢得游戏：
- $Verify(M^∗, σ^∗, ID^∗, params)→1$
- $ID^∗∉Q_K$
- $(ID^∗,M^∗)∉Q_S$

定义

如果不存在任何敌手 $A$ 在进行 $𝑞_1$ 次密钥查询和 $q_2$ 次签名查询后，能在时间 $𝑇$ 内以至少 $ϵ(λ)$ 的优势赢得上述游戏，则基于身份签名方案在 EU-ID-CMA 安全模型中是 $(𝑇,𝑞_1,q_2,ϵ(λ))$ - 安全的，即

$Pr[Verify(M^∗,\sigma ^∗,ID ^∗,params) \to 1 ]< \epsilon(λ)$

2. 针对选择性 ID 的选择消息攻击的存在不可伪造性 EU-sID-CMA

游戏在挑战者 $C$ 和敌手 $A$ 之间的执行过程：

$Inititialization$ ： $A$ 提前提交一个身份标识 $ID^∗∈\{0,1\}^∗$
$Setup$ ： $C$ 运行 $Setup(1^λ )→(MSK,params)$ ，并将 $params$ 返回给 $A$
$KeyGen$ $Query$ ：
- $A$ 动态地提交身份标识 $ID_i∈\{0,1\}^∗$ ，限制为 $ID_i≠ID^∗$ ，其中 $i=1, 2, ⋯, q_1$
- $C$ 运行 $KeyGen(ID_i,MSK,params)→SK_{ID_i}$ ，并将 $SK_{ID_i}$ 返回给 $A$
- 令 $Q_K=\{ID_1, ⋯, ID_{q_1}\}$
$Signing$ $Query$ ：
- $A$ 提交身份标识 $ID_j'∈\{0,1\}^∗$ 和消息 $M_j∈\{0,1\}^∗$ ， $ID_j≠ID^∗$ ，其中 $j=1,2,⋯,q_2$
- $C$ 运行 $KeyGen(ID_j',MSK,params)→SK_{ID_j'}$ 和 $Sign(M_j', SK, params)→σ_j'$ ，
- 将 $σ_j'$ 返回给 $A$ ，令 $Q_S={(ID_1^′,M_1 ),⋯(ID_{q_2}^′,M_{q_2})}$
$Forgery$ ： $A$ 输出 $(ID^∗, M^∗,σ^∗)$ 。下述情况 $A$ 将赢得游戏：
- $Verify(M^∗, σ^∗, ID^∗, params)→1$

定义

如果不存在任何敌手 $A$ 在进行 $𝑞_1$ 次密钥查询和 $q_2$ 次签名查询后，能在时间 $𝑇$ 内以至少 $ϵ(λ)$ 的优势赢得上述游戏，则基于身份签名方案在 EU-sID-CMA 安全模型中是 $(𝑇,𝑞_1,q_2,ϵ(λ))$ - 安全的，即

$Pr[Verify(M^∗,\sigma ^∗,ID ^∗,params) \to 1 ]< \epsilon (λ)$

3. 针对选择消息攻击的强不可伪造性 SEU-ID-CMA

游戏在挑战者 $C$ 和敌手 $A$ 之间的执行过程：

$Setup$ ： $C$ 运行 $Setup(1^λ )→(MSK,params)$ ，并将 $params$ 返回给 $A$
$KeyGen$ $Query$ ：
- $A$ 动态地提交身份标识 $ID_i∈\{0,1\}^∗$ ，其中 $i=1, 2, ⋯, q_1$
- $C$ 运行 $KeyGen(ID_i,MSK,params)→SK_{ID_i}$ ，并将 $SK_{ID_i}$ 返回给 $A$
- 令 $Q_K=\{ID_1, ⋯, ID_{q_1}\}$
$Signing$ $Query$ ：
- $A$ 提交身份标识 $ID_j'∈\{0,1\}^∗$ 和消息 $M_j∈\{0,1\}^∗$ ，其中 $j=1,2,⋯,q_2$
- $C$ 运行 $KeyGen(ID_j',MSK,params)→SK_{ID_j'}$ 和 $Sign(M_j', SK, params)→σ_j'$ ，
- 将 $σ_j'$ 返回给 $A$ ，令 $Q_S={(ID_1^′,M_1 ),⋯(ID_{q_2}^′,M_{q_2})}$ ， $Q_σ=\{σ_1,⋯,σ_{q_2 }\}$
$Forgery$ ： $A$ 输出 $(ID^∗, M^∗,σ^∗)$ 。下述情况 $A$ 将赢得游戏：
- $Verify(M^∗, σ^∗, ID^∗, params)→1$
- $ID^∗∉Q_K$
- $(ID^∗,M^∗)∉Q_S$ 或 $(ID^∗,M^∗)∈Q_S (σ^∗ ∉Q_σ)$

定义

如果不存在任何敌手 $A$ 在进行 $𝑞_1$ 次密钥查询和 $q_2$ 次签名查询后，能在时间 $𝑇$ 内以至少 $ϵ(λ)$ 的优势赢得上述游戏，则基于身份签名方案在 SEU-ID-CMA 安全模型中是 $(𝑇,𝑞_1,q_2,ϵ(λ))$ - 安全的，即

$Pr[Verify(M^∗,\sigma ^∗,ID ^∗,params) \to 1 ]< \epsilon (λ)$

4. 针对选择性 ID 的选择消息攻击的强不可伪造性 SEU-sID-CMA

游戏在挑战者 $C$ 和敌手 $A$ 之间的执行过程：

$Inititialization$ ： $A$ 提前提交一个身份标识 $ID^∗∈\{0,1\}^∗$
$Setup$ ： $C$ 运行 $Setup(1^λ )→(MSK,params)$ ，并将 $params$ 返回给 $A$
$KeyGen$ $Query$ ：
- $A$ 动态地提交身份标识 $ID_i∈\{0,1\}^∗$ ，限制为 $ID_i≠ID^∗$ ，其中 $i=1, 2, ⋯, q_1$
- $C$ 运行 $KeyGen(ID_i,MSK,params)→SK_{ID_i}$ ，并将 $SK_{ID_i}$ 返回给 $A$
- 令 $Q_K=\{ID_1, ⋯, ID_{q_1}\}$
$Signing$ $Query$ ：
- $A$ 提交身份标识 $ID_j'∈\{0,1\}^∗$ 和消息 $M_j∈\{0,1\}^∗$ ， $ID_j≠ID^∗$ ，其中 $j=1,2,⋯,q_2$
- $C$ 运行 $KeyGen(ID_j',MSK,params)→SK_{ID_j'}$ 和 $Sign(M_j', SK, params)→σ_j'$ ，
- 将 $σ_j'$ 返回给 $A$ ，令 $Q_S={(ID_1^′,M_1 ),⋯(ID_{q_2}^′,M_{q_2})}$ ， $Q_σ=\{σ_1,⋯,σ_{q_2 }\}$
$Forgery$ ： $A$ 输出 $(ID^∗, M^∗,σ^∗)$ 。下述情况 $A$ 将赢得游戏：
- $Verify(M^∗, σ^∗, ID^∗, params)→1$
- $ID^∗∉Q_K$
- $(ID^∗,M^∗)∉Q_S$ 或 $(ID^∗,M^∗)∈Q_S (σ^∗ ∉Q_σ)$

定义

如果不存在任何敌手 $A$ 在进行 $𝑞_1$ 次密钥查询和 $q_2$ 次签名查询后，能在时间 $𝑇$ 内以至少 $ϵ(λ)$ 的优势赢得上述游戏，则基于身份签名方案在 SEU-sID-CMA 安全模型中是 $(𝑇,𝑞_1,q_2,ϵ(λ))$ - 安全的，即

$Pr[Verify(M^∗,\sigma ^∗,ID ^∗,params) \to 1 ]<ϵ \epsilon (λ)$

参考资料：

[1] 安全规约导论，郭富春