安全性归约（安全性定义 - 2）

书接上回 ψ(*｀ー´)ψ

加密方案（被动攻击）

完美安全性：密文分布与明文分布相互独立，不同明文的密文是不可区分的，
{ E n c ( k , x ; r ) :   k ← G e n ,   x ← X λ } ≡ { E n c ( k , x ′ ; r ) :   k ← G e n ,   x ′ ← X λ } \{Enc(k,x;r):\, k \leftarrow Gen,\, x \leftarrow X_\lambda\} \equiv \{Enc(k,x';r):\, k \leftarrow Gen,\, x' \leftarrow X_\lambda\} {Enc(k,x;r):k←Gen,x←Xλ​}≡{Enc(k,x′;r):k←Gen,x′←Xλ​}

计算安全性：密文分布与明文分布在计算意义下相互独立，不同明文的密文是计算不可区分的，
{ E n c ( k , x ; r ) :   k ← G e n ,   x ← X λ } ≡ c { E n c ( k , x ′ ; r ) :   k ← G e n ,   x ′ ← X λ } \{Enc(k,x;r):\, k \leftarrow Gen,\, x \leftarrow X_\lambda\} \overset{c}{\equiv} \{Enc(k,x';r):\, k \leftarrow Gen,\, x' \leftarrow X_\lambda\} {Enc(k,x;r):k←Gen,x←Xλ​}≡c{Enc(k,x′;r):k←Gen,x′←Xλ​}

语义安全

语义安全（私钥）：私钥方案 $(Gen,Enc,Dec)$ 称为语义安全的，如果对于现实世界中的任意 PPT 算法 $A$，总存在理想世界中的 PPT 算法 $A^{\prime }$，对于任意多项式有界的明文分布 { X λ } λ ∈ N \{X_\lambda\}_{\lambda \in \mathbb N} {Xλ​}λ∈N​，任意的目标 f λ ( ⋅ ) : { 0 , 1 } ∗ → { 0 , 1 } ∗ f_\lambda(\cdot): \{0,1\}^* \to \{0,1\}^* fλ​(⋅):{0,1}∗→{0,1}∗，任意的辅助信息 h λ ( ⋅ ) : { 0 , 1 } ∗ → { 0 , 1 } ∗ h_\lambda(\cdot): \{0,1\}^* \to \{0,1\}^* hλ​(⋅):{0,1}∗→{0,1}∗，都有
P r X λ , G e n , E n c , A [ A ( 1 λ ,   E n c ( G e n ( 1 λ ) , X λ ) ,   1 ∣ X λ ∣ ,   h λ ( 1 λ , X λ ) ) = f λ ( 1 λ , X λ ) ] ≤ P r X λ , A ′ [ A ′ ( 1 λ ,   1 ∣ X λ ∣ ,   h λ ( 1 λ , X λ ) ) = f λ ( 1 λ , X λ ) ] + n e g l ( n )

≤​​Xλ​,Gen,Enc,APr​[A(1λ,Enc(Gen(1λ),Xλ​),1∣Xλ​∣,hλ​(1λ,Xλ​))=fλ​(1λ,Xλ​)]Xλ​,A′Pr​[A′(1λ,1∣Xλ​∣,hλ​(1λ,Xλ​))=fλ​(1λ,Xλ​)]+negl(n)​

即，存在 PPT 模拟器 $S$，使得
$$\left(Enc(Gen(1^{\lambda }),X_{\lambda }),1^{|X_{\lambda }|},h_{\lambda }(1^{\lambda },X_{\lambda })\right)\stackrel{c}{\equiv }S\left(1^{|X_{\lambda }|},h_{\lambda }(1^{\lambda },X_{\lambda })\right)$$

语义安全（公钥）：公钥方案 $(Gen=(G_1,G_2),Enc,Dec)$ 称为语义安全的，如果对于现实世界中的任意 PPT 算法 $A$，总存在理想世界中的 PPT 算法 $A^{\prime }$，对于任意多项式有界的明文分布 { X λ } λ ∈ N \{X_\lambda\}_{\lambda \in \mathbb N} {Xλ​}λ∈N​，任意的目标 f λ ( ⋅ ) : { 0 , 1 } ∗ → { 0 , 1 } ∗ f_\lambda(\cdot): \{0,1\}^* \to \{0,1\}^* fλ​(⋅):{0,1}∗→{0,1}∗，任意的辅助信息 h λ ( ⋅ ) : { 0 , 1 } ∗ → { 0 , 1 } ∗ h_\lambda(\cdot): \{0,1\}^* \to \{0,1\}^* hλ​(⋅):{0,1}∗→{0,1}∗，都有
P r X λ , G e n , E n c , A [ A ( 1 λ ,   G 1 ( 1 λ ) ,   E n c ( G 1 ( 1 λ ) , X λ ) ,   1 ∣ X λ ∣ ,   h λ ( 1 λ , X λ ) ) = f λ ( 1 λ , X λ ) ] ≤ P r X λ , A ′ [ A ′ ( 1 λ ,   1 ∣ X λ ∣ ,   h λ ( 1 λ , X λ ) ) = f λ ( 1 λ , X λ ) ] + n e g l ( n )

≤​​Xλ​,Gen,Enc,APr​[A(1λ,G1​(1λ),Enc(G1​(1λ),Xλ​),1∣Xλ​∣,hλ​(1λ,Xλ​))=fλ​(1λ,Xλ​)]Xλ​,A′Pr​[A′(1λ,1∣Xλ​∣,hλ​(1λ,Xλ​))=fλ​(1λ,Xλ​)]+negl(n)​

即，存在 PPT 模拟器 $S$，使得
$$\left(G_1(1^{\lambda }),Enc(G_1(1^{\lambda }),X_{\lambda }),1^{|X_{\lambda }|},h_{\lambda }(1^{\lambda },X_{\lambda })\right)\stackrel{c}{\equiv }S\left(1^{|X_{\lambda }|},h_{\lambda }(1^{\lambda },X_{\lambda })\right)$$

多消息语义安全：设 { X ‾ λ = ( X λ ( 1 ) , ⋯   , X λ ( t ) ) } λ ∈ N \{\overline X_\lambda = (X_\lambda^{(1)},\cdots,X_\lambda^{(t)})\}_{\lambda \in \mathbb N} {Xλ​=(Xλ(1)​,⋯,Xλ(t)​)}λ∈N​，其中 $t(\lambda )\le poly(\lambda )$ 且 $|X_{\lambda }^{(i)}|=poly(\lambda )$（多项式有界的多消息联合分布，各分量无需相互独立）。方案 $(Gen,Enc,Dec)$ 称为多消息语义安全的，如果对于现实世界中的任意 PPT 算法 $A$，总存在理想世界中的 PPT 算法 $A^{\prime }$，对于多消息分布 { X ‾ λ } λ ∈ N \{\overline X_\lambda\}_{\lambda \in \mathbb N} {Xλ​}λ∈N​，任意的目标 f λ ( ⋅ ) : { 0 , 1 } ∗ → { 0 , 1 } ∗ f_\lambda(\cdot): \{0,1\}^* \to \{0,1\}^* fλ​(⋅):{0,1}∗→{0,1}∗，任意的辅助信息 h λ ( ⋅ ) : { 0 , 1 } ∗ → { 0 , 1 } ∗ h_\lambda(\cdot): \{0,1\}^* \to \{0,1\}^* hλ​(⋅):{0,1}∗→{0,1}∗，都有

1. 私钥模型，
   P r X ‾ λ , G e n , E n c , A [ A ( 1 λ ,   E n c ( G e n ( 1 λ ) , X ‾ λ ) ,   1 ∣ X ‾ λ ∣ ,   h λ ( 1 λ , X ‾ λ ) ) = f λ ( 1 λ , X ‾ λ ) ] ≤ P r X ‾ λ , A ′ [ A ′ ( 1 λ ,   1 ∣ X ‾ λ ∣ ,   h λ ( 1 λ , X ‾ λ ) ) = f λ ( 1 λ , X ‾ λ ) ] + n e g l ( n )

   PrX¯λ,Gen,Enc,A[A(1λ,Enc(Gen(1λ),X¯λ),1|X¯λ|,hλ(1λ,X¯λ))=fλ(1λ,X¯λ)]≤PrX¯λ,A′[A′(1λ,1|X¯λ|,hλ(1λ,X¯λ))=fλ(1λ,X¯λ)]+negl(n)" role="presentation">≤PrX¯¯¯¯¯λ,Gen,Enc,A[A(1λ,Enc(Gen(1λ),X¯¯¯¯λ),1|X¯¯¯¯¯λ|,hλ(1λ,X¯¯¯¯λ))=fλ(1λ,X¯¯¯¯λ)]PrX¯¯¯¯¯λ,A′[A′(1λ,1|X¯¯¯¯¯λ|,hλ(1λ,X¯¯¯¯λ))=fλ(1λ,X¯¯¯¯λ)]+negl(n)$$\begin{array}{rlr}& & \underset{{\overline{X}}_{\lambda },Gen,Enc,A}{Pr}\left[A\left(1^{\lambda },Enc(Gen(1^{\lambda }),{\overline{X}}_{\lambda }),1^{|{\overline{X}}_{\lambda }|},h_{\lambda }(1^{\lambda },{\overline{X}}_{\lambda })\right)=f_{\lambda }(1^{\lambda },{\overline{X}}_{\lambda })\right]\\ \le & & \underset{{\overline{X}}_{\lambda },A^{\prime }}{Pr}\left[A^{\prime }\left(1^{\lambda },1^{|{\overline{X}}_{\lambda }|},h_{\lambda }(1^{\lambda },{\overline{X}}_{\lambda })\right)=f_{\lambda }(1^{\lambda },{\overline{X}}_{\lambda })\right]+negl(n)\end{array}$$
   ≤​​Xλ​,Gen,Enc,APr​[A(1λ,Enc(Gen(1λ),Xλ​),1∣Xλ​∣,hλ​(1λ,Xλ​))=fλ​(1λ,Xλ​)]Xλ​,A′Pr​[A′(1λ,1∣Xλ​∣,hλ​(1λ,Xλ​))=fλ​(1λ,Xλ​)]+negl(n)​

2. 公钥模型，
   P r X ‾ λ , G e n , E n c , A [ A ( 1 λ ,   G 1 ( 1 λ ) ,   E n c ( G 1 ( 1 λ ) , X ‾ λ ) ,   1 ∣ X ‾ λ ∣ ,   h λ ( 1 λ , X ‾ λ ) ) = f λ ( 1 λ , X ‾ λ ) ] ≤ P r X ‾ λ , A ′ [ A ′ ( 1 λ ,   1 ∣ X ‾ λ ∣ ,   h λ ( 1 λ , X ‾ λ ) ) = f λ ( 1 λ , X ‾ λ ) ] + n e g l ( n )

   PrX¯λ,Gen,Enc,A[A(1λ,G1(1λ),Enc(G1(1λ),X¯λ),1|X¯λ|,hλ(1λ,X¯λ))=fλ(1λ,X¯λ)]≤PrX¯λ,A′[A′(1λ,1|X¯λ|,hλ(1λ,X¯λ))=fλ(1λ,X¯λ)]+negl(n)" role="presentation">≤PrX¯¯¯¯¯λ,Gen,Enc,A[A(1λ,G1(1λ),Enc(G1(1λ),X¯¯¯¯λ),1|X¯¯¯¯¯λ|,hλ(1λ,X¯¯¯¯λ))=fλ(1λ,X¯¯¯¯λ)]PrX¯¯¯¯¯λ,A′[A′(1λ,1|X¯¯¯¯¯λ|,hλ(1λ,X¯¯¯¯λ))=fλ(1λ,X¯¯¯¯λ)]+negl(n)$$\begin{array}{rlr}& & \underset{{\overline{X}}_{\lambda },Gen,Enc,A}{Pr}\left[A\left(1^{\lambda },G_1(1^{\lambda }),Enc(G_1(1^{\lambda }),{\overline{X}}_{\lambda }),1^{|{\overline{X}}_{\lambda }|},h_{\lambda }(1^{\lambda },{\overline{X}}_{\lambda })\right)=f_{\lambda }(1^{\lambda },{\overline{X}}_{\lambda })\right]\\ \le & & \underset{{\overline{X}}_{\lambda },A^{\prime }}{Pr}\left[A^{\prime }\left(1^{\lambda },1^{|{\overline{X}}_{\lambda }|},h_{\lambda }(1^{\lambda },{\overline{X}}_{\lambda })\right)=f_{\lambda }(1^{\lambda },{\overline{X}}_{\lambda })\right]+negl(n)\end{array}$$
   ≤​​Xλ​,Gen,Enc,APr​[A(1λ,G1​(1λ),Enc(G1​(1λ),Xλ​),1∣Xλ​∣,hλ​(1λ,Xλ​))=fλ​(1λ,Xλ​)]Xλ​,A′Pr​[A′(1λ,1∣Xλ​∣,hλ​(1λ,Xλ​))=fλ​(1λ,Xλ​)]+negl(n)​

不可区分安全

密文不可区分（私钥）：私钥方案 $(Gen,Enc,Dec)$ 称为密文不可区分的（IND），如果对于任意非一致电路簇 { C λ } λ ∈ N \{C_\lambda\}_{\lambda \in \mathbb N} {Cλ​}λ∈N​，以及任意的 x , y ∈ { 0 , 1 } l ( λ ) = M x,y \in \{0,1\}^{l(\lambda)}=M x,y∈{0,1}l(λ)=M，有
$$\left|\underset{Gen,Enc}{\mathrm{Pr}}[C_{\lambda }(Enc(Gen(1^{\lambda }),x))=1]-\underset{Gen,Enc}{\mathrm{Pr}}[C_{\lambda }(Enc(Gen(1^{\lambda }),y))=1]\right|\le negl(\lambda )$$

密文不可区分（公钥）：公钥方案 $(Gen=(G_1,G_2),Enc,Dec)$ 称为密文不可区分的（IND），如果对于任意非一致电路簇 { C λ } λ ∈ N \{C_\lambda\}_{\lambda \in \mathbb N} {Cλ​}λ∈N​，以及任意的 x , y ∈ { 0 , 1 } l ( λ ) = M x,y \in \{0,1\}^{l(\lambda)}=M x,y∈{0,1}l(λ)=M，有
$$\left|\underset{Gen,Enc}{\mathrm{Pr}}[C_{\lambda }(G_1(1^{\lambda }),Enc(G_1(1^{\lambda }),x))=1]-\underset{Gen,Enc}{\mathrm{Pr}}[C_{\lambda }(G_1(1^{\lambda }),Enc(G_1(1^{\lambda }),y))=1]\right|\le negl(\lambda )$$

定义敌手和挑战者之间的判定实验，令 h ( X λ ) = { m 0 , m 1 } h(X_\lambda)=\{m_0,m_1\} h(Xλ​)={m0​,m1​}，$f(1^{\lambda },X_{\lambda })=b$，如图

现实世界中敌手 $A$ 相对于理想世界中模拟器 $A^{\prime }$ 的区分优势为：
A d v A , Π I N D ( λ ) : = ∣ P r G e n , E n c , A [ E x p t A , Π I N D ( 1 λ , 0 ) = 0 ] − P r G e n , E n c , A [ E x p t A , Π I N D ( 1 λ , 1 ) = 1 ] ∣ : = 2 ∣ P r G e n , E n c , A [ E x p t A , Π I N D ( 1 λ , U 1 ) = 1 ] − 1 2 ∣

AdvA,ΠIND​(λ)​:=∣∣∣∣​Gen,Enc,APr​[ExptA,ΠIND​(1λ,0)=0]−Gen,Enc,APr​[ExptA,ΠIND​(1λ,1)=1]∣∣∣∣​:=2∣∣∣∣​Gen,Enc,APr​[ExptA,ΠIND​(1λ,U1​)=1]−21​∣∣∣∣​​

其中 $\underset{Gen,Enc,A^{\prime }}{\mathrm{Pr}}\left[Exp{t}_{A^{\prime },\Pi ,Ideal}^{IND}(1^{\lambda },U_1)=1\right]=\frac{1}{2}$

于是，我们说加密方案 $\Pi$ 是 IND 安全的，如果对于任意的 PPT 敌手 $A$，有
$$Ad{v}_{A,\Pi }^{IND}(\lambda )\le negl(\lambda )$$

多消息密文不可区分（私钥）：私钥方案 $(Gen,Enc,Dec)$ 称为多消息 IND 安全的，如果对于任意非一致电路簇 { C λ } λ ∈ N \{C_\lambda\}_{\lambda \in \mathbb N} {Cλ​}λ∈N​，以及任意的 ${\overline{x}}_0,{\overline{x}}_1\in {\overline{X}}_{\lambda }$，有
$$\left|\underset{Gen,Enc}{\mathrm{Pr}}[C_{\lambda }(Enc(Gen(1^{\lambda }),{\overline{x}}_0))=1]-\underset{Gen,Enc}{\mathrm{Pr}}[C_{\lambda }(Enc(Gen(1^{\lambda }),{\overline{x}}_1))=1]\right|\le negl(\lambda )$$

多消息密文不可区分（公钥）：公钥方案 $(Gen=(G_1,G_2),Enc,Dec)$ 称为称为多消息 IND 安全的，如果对于任意非一致电路簇 { C λ } λ ∈ N \{C_\lambda\}_{\lambda \in \mathbb N} {Cλ​}λ∈N​，以及任意的 ${\overline{x}}_0,{\overline{x}}_1\in {\overline{X}}_{\lambda }$，有
$$\left|\underset{Gen,Enc}{\mathrm{Pr}}[C_{\lambda }(G_1(1^{\lambda }),Enc(G_1(1^{\lambda }),{\overline{x}}_0))=1]-\underset{Gen,Enc}{\mathrm{Pr}}[C_{\lambda }(G_1(1^{\lambda }),Enc(G_1(1^{\lambda }),{\overline{x}}_1))=1]\right|\le negl(\lambda )$$

各个安全性之间的关系为：

加密方案（主动攻击）

上述的语义安全和不可区分安全都是唯密文攻击（被动攻击）下的安全性。除此之外，还有更强的主动攻击下的安全性。

CPA

选择明文攻击下的语义安全：（公钥、私钥）加密方案 $\Pi =(Gen=(G_1,G_2),Enc,Dec)$ 称为称为 CPA 语义安全的，如果对于任意 PPT 的带加密 Oracle 的两阶段算法 $A=(A_1,A_2)$，存在 PPT算法 $A^{\prime }=(A_1^{\prime },A_2^{\prime })$，使得

1. 当 $\lambda$ 充分大，对于任意的 z ∈ { 0 , 1 } p o l y ( λ ) z \in \{0,1\}^{poly(\lambda)} z∈{0,1}poly(λ)，有
   P r G e n , E n c , A , S [ v = f ( x ) : ( e , d ) ← G e n ( 1 λ ) ( ( S , h , f ) , σ ) ← A 1 E n c e , d ( ⋅ ) ( 1 λ , e , z ) c ← ( E n c e , d ( x ) ,   h ( x ) ) ,   x ← S ( U p o l y ( λ ) ) v ← A 2 E n c e , d ( ⋅ ) ( σ , c ) ] ≤ P r A ′ , S [ v = f ( x ) : ( ( S , h , f ) , σ ) ← A 1 ′ ( 1 λ , z ) c ← ( 1 ∣ x ∣ ,   h ( x ) ) ,   x ← S ( U p o l y ( λ ) ) v ← A 2 ′ ( σ , c ) ] + n e g l ( λ )

   \begin{aligned} &&\underset{Gen,Enc,A,S}{Pr}\left[\begin{aligned} v=f(x): && (e,d) \leftarrow Gen(1^\lambda)\\ && ((S,h,f),\sigma) \leftarrow A_1^{Enc_{e,d}(\cdot)}(1^\lambda,e,z)\\ && c \leftarrow (Enc_{e,d}(x),\, h(x)),\, x \leftarrow S(U_{poly(\lambda)})\\ && v \leftarrow A_2^{Enc_{e,d}(\cdot)}(\sigma,c) \end{aligned}" role="presentation">\begin{aligned} &&\underset{Gen,Enc,A,S}{Pr}\left[\begin{aligned} v=f(x): && (e,d) \leftarrow Gen(1^\lambda)\\ && ((S,h,f),\sigma) \leftarrow A_1^{Enc_{e,d}(\cdot)}(1^\lambda,e,z)\\ && c \leftarrow (Enc_{e,d}(x),\, h(x)),\, x \leftarrow S(U_{poly(\lambda)})\\ && v \leftarrow A_2^{Enc_{e,d}(\cdot)}(\sigma,c) \end{aligned}$$\text{begin{aligned} \&\&underset{Gen,Enc,A,S}{Pr}left[begin{aligned} v=f(x): \&\& (e,d) leftarrow Gen(1^lambda) \&\& ((S,h,f),sigma) leftarrow A\_1^{Enc\_{e,d}(cdot)}(1^lambda,e,z) \&\& c leftarrow (Enc\_{e,d}(x),, h(x)),, x leftarrow S(U\_{poly(lambda)}) \&\& v leftarrow A\_2^{Enc\_{e,d}(cdot)}(sigma,c) end{aligned}}$$
   \right]\\ &\le &\underset{A',S}{Pr}\left[
   v=f(x):((S,h,f),σ)←A1′(1λ,z)c←(1|x|,h(x)),x←S(Upoly(λ))v←A2′(σ,c)" role="presentation">v=f(x):((S,h,f),σ)←A′1(1λ,z)c←(1|x|,h(x)),x←S(Upoly(λ))v←A′2(σ,c)$$\begin{array}{rlr}v=f(x):& & ((S,h,f),\sigma )\leftarrow A_1^{\prime }(1^{\lambda },z)\\ & & c\leftarrow (1^{|x|},h(x)),x\leftarrow S(U_{poly(\lambda )})\\ & & v\leftarrow A_2^{\prime }(\sigma ,c)\end{array}$$
   \right] + negl(\lambda) \end{aligned} ​≤​Gen,Enc,A,SPr​⎣⎢⎢⎢⎢⎢⎡​v=f(x):​​(e,d)←Gen(1λ)((S,h,f),σ)←A1Ence,d​(⋅)​(1λ,e,z)c←(Ence,d​(x),h(x)),x←S(Upoly(λ)​)v←A2Ence,d​(⋅)​(σ,c)​⎦⎥⎥⎥⎥⎥⎤​A′,SPr​⎣⎢⎡​v=f(x):​​((S,h,f),σ)←A1′​(1λ,z)c←(1∣x∣,h(x)),x←S(Upoly(λ)​)v←A2′​(σ,c)​⎦⎥⎤​+negl(λ)​

2. 对于任意的 $\lambda ,z$，$A_1^{\prime }(1^{\lambda },z)$ 与 $A_1^{En{c}_{e,d}(\cdot )}(1^{\lambda },e,z)$ 输出的 $(S,h,f)$ 计算不可区分（否则目标不一致，比较无意义）。

定义选择明文攻击（CPA）的实验 $Exp{t}_{A,\Pi ,z}^{IND-CPA}(1^{\lambda },b)$，如图：

区分优势定义为：
A d v A , Π I N D − C P A ( λ ) : = ∣ P r G e n , E n c , A [ E x p t A , Π , z I N D − C P A ( 1 λ , 0 ) = 0 ] − P r G e n , E n c , A [ E x p t A , Π , z I N D − C P A ( 1 λ , 1 ) = 1 ] ∣ : = 2 ∣ P r G e n , E n c , A [ E x p t A , Π , z I N D − C P A ( 1 λ , U 1 ) = 1 ] − 1 2 ∣

AdvA,ΠIND−CPA​(λ)​:=∣∣∣∣​Gen,Enc,APr​[ExptA,Π,zIND−CPA​(1λ,0)=0]−Gen,Enc,APr​[ExptA,Π,zIND−CPA​(1λ,1)=1]∣∣∣∣​:=2∣∣∣∣​Gen,Enc,APr​[ExptA,Π,zIND−CPA​(1λ,U1​)=1]−21​∣∣∣∣​​

选择明文攻击下的密文不可区分：（公钥、私钥）加密方案 $\Pi =(Gen=(G_1,G_2),Enc,Dec)$ 称为称为 IND-CPA 安全的，如果对于任意 PPT 的带加密 Oracle 的两阶段算法 $A=(A_1,A_2)$，使得区分优势为
$$Ad{v}_{A,\Pi }^{IND-CPA}(\lambda )\le negl(n)$$

由于 CPA 模型下算法 $A$ 可访问加密预言机 $En{c}_{e,d}(\cdot )$，因此有：

CCA1

定义第一类选择密文攻击（CCA1）的实验 $Exp{t}_{A,\Pi ,z}^{IND-CCA1}(1^{\lambda },b)$，如图：

CCA2

定义第二类选择密文攻击（CCA1）的实验 $Exp{t}_{A,\Pi ,z}^{IND-CCA2}(1^{\lambda },b)$，如图：

Att

为了统一表示 { C P A , C C A 1 , C C A 2 } \{CPA,CCA1,CCA2\} {CPA,CCA1,CCA2}，定义实验 $Exp{t}_{A,\Pi ,z}^{Att}(1^{\lambda },b)$ 如图：

区分优势定义为
A d v A , Π I N D − A t t ( λ ) : = ∣ P r Π , A [ E x p t A , Π , z I N D − A t t ( 1 λ , 0 ) = 0 ] − P r Π , A [ E x p t A , Π , z I N D − A t t ( 1 λ , 1 ) = 1 ] ∣ : = 2 ∣ P r Π , A , b [ E x p t A , Π , z I N D − A t t ( 1 λ , U 1 ) = 1 ] − 1 2 ∣

AdvA,ΠIND−Att​(λ)​:=∣∣∣∣​Π,APr​[ExptA,Π,zIND−Att​(1λ,0)=0]−Π,APr​[ExptA,Π,zIND−Att​(1λ,1)=1]∣∣∣∣​:=2∣∣∣∣​Π,A,bPr​[ExptA,Π,zIND−Att​(1λ,U1​)=1]−21​∣∣∣∣​​

Att-不可区分安全：（公钥、私钥）加密方案 $\Pi =(Gen,Enc,Dec)$ 称为 Att - 密文不可区分的，其中 A t t = { C P A , C C A 1 , C C A 2 } Att=\{CPA,CCA1,CCA2\} Att={CPA,CCA1,CCA2}，如果对于任意 PPT 的带 Oracles 的两阶段算法 $A=(A_1,A_2)$，以及任意的 z ∈ { 0 , 1 } p o l y ( ⋅ ) z \in \{0,1\}^{poly(\cdot)} z∈{0,1}poly(⋅)，有
$$Ad{v}_{A,\Pi }^{IND-Att}(\lambda )\le negl(\lambda )$$

Att-语义安全：（公钥、私钥）加密方案 $\Pi =(Gen,Enc,Dec)$ 称为 Att - 语义安全的，其中 A t t = { C P A , C C A 1 , C C A 2 } Att=\{CPA,CCA1,CCA2\} Att={CPA,CCA1,CCA2}，如果对于任意 PPT 的带 Oracles 的两阶段算法 $A=(A_1,A_2)$，存在 PPT 算法 $A^{\prime }=(A_1^{\prime },A_2^{\prime })$，使得

1. 当 $\lambda$ 充分大，对于任意的 z ∈ { 0 , 1 } p o l y ( λ ) z \in \{0,1\}^{poly(\lambda)} z∈{0,1}poly(λ)，有
   P r Π , A , S [ v = f ( x ) : ( e , d ) ← G e n ( 1 λ ) ( ( S , h , f ) , σ ) ← A 1 E n c e , d ( ⋅ ) , O A t t 1 ( 1 λ , e , z ) c ← ( E n c e , d ( x ) ,   h ( x ) ) ,   x ← S ( U p o l y ( λ ) ) v ← A 2 E n c e , d ( ⋅ ) , O A t t 2 ( σ , c ) ] ≤ P r A ′ , S [ v = f ( x ) : ( ( S , h , f ) , σ ) ← A 1 ′ ( 1 λ , z ) x ← S ( U p o l y ( λ ) ) v ← A 2 ′ ( σ , 1 ∣ x ∣ , h ( x ) ) ] + n e g l ( λ )

   \begin{aligned} &&\underset{\Pi,A,S}{Pr}\left[\begin{aligned} v=f(x): && (e,d) \leftarrow Gen(1^\lambda)\\ && ((S,h,f),\sigma) \leftarrow A_1^{Enc_{e,d}(\cdot),O_{Att}^1}(1^\lambda,e,z)\\ && c \leftarrow (Enc_{e,d}(x),\, h(x)),\, x \leftarrow S(U_{poly(\lambda)})\\ && v \leftarrow A_2^{Enc_{e,d}(\cdot),O_{Att}^2}(\sigma,c) \end{aligned}" role="presentation">\begin{aligned} &&\underset{\Pi,A,S}{Pr}\left[\begin{aligned} v=f(x): && (e,d) \leftarrow Gen(1^\lambda)\\ && ((S,h,f),\sigma) \leftarrow A_1^{Enc_{e,d}(\cdot),O_{Att}^1}(1^\lambda,e,z)\\ && c \leftarrow (Enc_{e,d}(x),\, h(x)),\, x \leftarrow S(U_{poly(\lambda)})\\ && v \leftarrow A_2^{Enc_{e,d}(\cdot),O_{Att}^2}(\sigma,c) \end{aligned}$$\text{begin{aligned} \&\&underset{Pi,A,S}{Pr}left[begin{aligned} v=f(x): \&\& (e,d) leftarrow Gen(1^lambda) \&\& ((S,h,f),sigma) leftarrow A\_1^{Enc\_{e,d}(cdot),O\_{Att}^1}(1^lambda,e,z) \&\& c leftarrow (Enc\_{e,d}(x),, h(x)),, x leftarrow S(U\_{poly(lambda)}) \&\& v leftarrow A\_2^{Enc\_{e,d}(cdot),O\_{Att}^2}(sigma,c) end{aligned}}$$
   \right]\\ &\le &\underset{A',S}{Pr}\left[
   v=f(x):((S,h,f),σ)←A1′(1λ,z)x←S(Upoly(λ))v←A2′(σ,1|x|,h(x))" role="presentation">v=f(x):((S,h,f),σ)←A′1(1λ,z)x←S(Upoly(λ))v←A′2(σ,1|x|,h(x))$$\begin{array}{rlr}v=f(x):& & ((S,h,f),\sigma )\leftarrow A_1^{\prime }(1^{\lambda },z)\\ & & x\leftarrow S(U_{poly(\lambda )})\\ & & v\leftarrow A_2^{\prime }(\sigma ,1^{|x|},h(x))\end{array}$$
   \right] + negl(\lambda) \end{aligned} ​≤​Π,A,SPr​⎣⎢⎢⎢⎢⎢⎡​v=f(x):​​(e,d)←Gen(1λ)((S,h,f),σ)←A1Ence,d​(⋅),OAtt1​​(1λ,e,z)c←(Ence,d​(x),h(x)),x←S(Upoly(λ)​)v←A2Ence,d​(⋅),OAtt2​​(σ,c)​⎦⎥⎥⎥⎥⎥⎤​A′,SPr​⎣⎢⎡​v=f(x):​​((S,h,f),σ)←A1′​(1λ,z)x←S(Upoly(λ)​)v←A2′​(σ,1∣x∣,h(x))​⎦⎥⎤​+negl(λ)​

2. 对于任意的 $\lambda ,z$，$A_1^{\prime }(1^{\lambda },z)$ 与 $A_1^{En{c}_{e,d}(\cdot ),O_{Att}^1}(1^{\lambda },e,z)$ 输出的 $(S,h,f)$ 计算不可区分（否则目标不一致，比较无意义）。

可以证明，

• （公钥、私钥）加密方案 $\Pi =(Gen,Enc,Dec)$ 是 Att - 语义安全的，当仅当 $\Pi$ 是 Att - 密文不可区分的。
• （公钥、私钥）加密方案 $\Pi =(Gen,Enc,Dec)$ 是单消息 Att - 语义安全的，当仅当 $\Pi$ 是多消息 Att - 语义安全的。
• （公钥、私钥）加密方案 $\Pi =(Gen,Enc,Dec)$ 是单消息 Att - 密文不可区分的，当仅当 $\Pi$ 是多消息 Att - 密文不可区分的。

签名方案

不可伪造性：签名方案 $\Pi =(Gen,Sign,Ver)$ 的选择消息攻击实验如下：

我们说 $\Pi$ 是选择消息攻击下的存在性不可伪造（EUF-CMA）的，如果对于任意 PPT 敌手 $A$，当 $\lambda$ 充分大，有
$$Ad{v}_{A,\Pi }^{EUF-CMA}(\lambda ):=Pr\left[Exp{t}_{A,\Pi }^{EUF-CMA}(1^{\lambda })=1\right]\le negl(\lambda )$$

强不可伪造性：签名方案 $\Pi =(Gen,Sign,Ver)$ 的（强）选择消息攻击实验如下：

我们说 $\Pi$ 是选择消息攻击下的（强）存在性不可伪造（EUF-CMA）的，如果对于任意 PPT 敌手 $A$，当 $\lambda$ 充分大，有
$$Ad{v}_{A,\Pi }^{EUF-CMA}(\lambda ):=Pr\left[Exp{t}_{A,\Pi }^{EUF-CMA}(1^{\lambda })=1\right]\le negl(\lambda )$$

MAC

不可伪造性：消息验证码 $\Pi =(Gen,MAC,Ver)$ 的选择消息攻击实验如下：

我们说 $\Pi$ 是选择消息攻击下的存在性不可伪造（EUF-CMA）的，如果对于任意 PPT 敌手 $A$，当 $\lambda$ 充分大，有
$$Ad{v}_{A,\Pi }^{EUF-CMA}(\lambda ):=Pr\left[Exp{t}_{A,\Pi }^{EUF-CMA}(1^{\lambda })=1\right]\le negl(\lambda )$$