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

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

文章目录

• 加密方案（被动攻击）
  *
• 语义安全
• 不可区分安全
• 加密方案（主动攻击）
  *
• CPA
• CCA1
• CCA2
• Att
• 签名方案
• MAC

加密方案（被动攻击）

完美安全性：密文分布与明文分布相互独立，不同明文的密文是不可区分的，
{ 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}{E n c (k ,x ;r ):k ←G e n ,x ←X λ​}≡{E n c (k ,x ′;r ):k ←G e n ,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}{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 λ​}

语义安全

语义安全（私钥）：私钥方案 ( G e n , E n c , D e c ) (Gen,Enc,Dec)(G e n ,E n c ,D e c ) 称为语义安全的，如果对于现实世界中的任意 PPT 算法 A A A，总存在理想世界中的 PPT 算法 A ′ A’A ′，对于任意多项式有界的明文分布 { 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 ) \begin{aligned} &&\underset{X_\lambda,Gen,Enc,A}{Pr}\left[A\left(1^\lambda,\, Enc(Gen(1^\lambda),X_\lambda),\, 1^{|X_\lambda|},\, h_\lambda(1^\lambda,X_\lambda) \right) = f_\lambda(1^\lambda,X_\lambda) \right] \ \le &&\underset{X_\lambda,A’}{Pr}\left[A’\left(1^\lambda,\, 1^{|X_\lambda|},\, h_\lambda(1^\lambda,X_\lambda) \right) = f_\lambda(1^\lambda,X_\lambda) \right] + negl(n) \end{aligned}≤​​X λ​,G e n ,E n c ,A P r ​[A (1 λ,E n c (G e n (1 λ),X λ​),1 ∣X λ​∣,h λ​(1 λ,X λ​))=f λ​(1 λ,X λ​)]X λ​,A ′P r ​[A ′(1 λ,1 ∣X λ​∣,h λ​(1 λ,X λ​))=f λ​(1 λ,X λ​)]+n e g l (n )​

即，存在 PPT 模拟器 S S S，使得
( E n c ( G e n ( 1 λ ) , X λ ) , 1 ∣ X λ ∣ , h λ ( 1 λ , X λ ) ) ≡ c S ( 1 ∣ X λ ∣ , h λ ( 1 λ , X λ ) ) \left(Enc(Gen(1^\lambda),X_\lambda),\, 1^{|X_\lambda|},\, h_\lambda(1^\lambda,X_\lambda)\right) \overset{c}{\equiv} S\left(1^{|X_\lambda|},\, h_\lambda(1^\lambda,X_\lambda)\right)(E n c (G e n (1 λ),X λ​),1 ∣X λ​∣,h λ​(1 λ,X λ​))≡c S (1 ∣X λ​∣,h λ​(1 λ,X λ​))

语义安全（公钥）：公钥方案 ( G e n = ( G 1 , G 2 ) , E n c , D e c ) (Gen=(G_1,G_2),Enc,Dec)(G e n =(G 1 ​,G 2 ​),E n c ,D e c ) 称为语义安全的，如果对于现实世界中的任意 PPT 算法 A A A，总存在理想世界中的 PPT 算法 A ′ A’A ′，对于任意多项式有界的明文分布 { 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 ) \begin{aligned} &&\underset{X_\lambda,Gen,Enc,A}{Pr}\left[A\left(1^\lambda,\, G_1(1^\lambda),\, Enc(G_1(1^\lambda),X_\lambda),\, 1^{|X_\lambda|},\, h_\lambda(1^\lambda,X_\lambda) \right) = f_\lambda(1^\lambda,X_\lambda) \right] \ \le &&\underset{X_\lambda,A’}{Pr}\left[A’\left(1^\lambda,\, 1^{|X_\lambda|},\, h_\lambda(1^\lambda,X_\lambda) \right) = f_\lambda(1^\lambda,X_\lambda) \right] + negl(n) \end{aligned}≤​​X λ​,G e n ,E n c ,A P r ​[A (1 λ,G 1 ​(1 λ),E n c (G 1 ​(1 λ),X λ​),1 ∣X λ​∣,h λ​(1 λ,X λ​))=f λ​(1 λ,X λ​)]X λ​,A ′P r ​[A ′(1 λ,1 ∣X λ​∣,h λ​(1 λ,X λ​))=f λ​(1 λ,X λ​)]+n e g l (n )​

即，存在 PPT 模拟器 S S S，使得
( G 1 ( 1 λ ) , E n c ( G 1 ( 1 λ ) , X λ ) , 1 ∣ X λ ∣ , h λ ( 1 λ , X λ ) ) ≡ c S ( 1 ∣ X λ ∣ , h λ ( 1 λ , X λ ) ) \left(G_1(1^\lambda),\, Enc(G_1(1^\lambda),X_\lambda),\, 1^{|X_\lambda|},\, h_\lambda(1^\lambda,X_\lambda)\right) \overset{c}{\equiv} S\left(1^{|X_\lambda|},\, h_\lambda(1^\lambda,X_\lambda)\right)(G 1 ​(1 λ),E n c (G 1 ​(1 λ),X λ​),1 ∣X λ​∣,h λ​(1 λ,X λ​))≡c S (1 ∣X λ​∣,h λ​(1 λ,X λ​))

多消息语义安全：设 { 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 ( λ ) ≤ p o l y ( λ ) t(\lambda) \le poly(\lambda)t (λ)≤p o l y (λ) 且 ∣ X λ ( i ) ∣ = p o l y ( λ ) |X\lambda^{(i)}| = poly(\lambda)∣X λ(i )​∣=p o l y (λ)（多项式有界的多消息联合分布，各分量无需相互独立）。方案 ( G e n , E n c , D e c ) (Gen,Enc,Dec)(G e n ,E n c ,D e c ) 称为多消息语义安全的，如果对于现实世界中的任意 PPT 算法 A A A，总存在理想世界中的 PPT 算法 A ′ A’A ′，对于多消息分布 { 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 ) \begin{aligned} &&\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’}{Pr}\left[A’\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{aligned}≤​​X λ​,G e n ,E n c ,A P r ​[A (1 λ,E n c (G e n (1 λ),X λ​),1 ∣X λ​∣,h λ​(1 λ,X λ​))=f λ​(1 λ,X λ​)]X λ​,A ′P r ​[A ′(1 λ,1 ∣X λ​∣,h λ​(1 λ,X λ​))=f λ​(1 λ,X λ​)]+n e g l (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 ) \begin{aligned} &&\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’}{Pr}\left[A’\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{aligned}≤​​X λ​,G e n ,E n c ,A P r ​[A (1 λ,G 1 ​(1 λ),E n c (G 1 ​(1 λ),X λ​),1 ∣X λ​∣,h λ​(1 λ,X λ​))=f λ​(1 λ,X λ​)]X λ​,A ′P r ​[A ′(1 λ,1 ∣X λ​∣,h λ​(1 λ,X λ​))=f λ​(1 λ,X λ​)]+n e g l (n )​

不可区分安全

密文不可区分（私钥）：私钥方案 ( G e n , E n c , D e c ) (Gen,Enc,Dec)(G e n ,E n c ,D e c ) 称为密文不可区分的（ 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，有
∣ P r G e n , E n c [ C λ ( E n c ( G e n ( 1 λ ) , x ) ) = 1 ] − P r G e n , E n c [ C λ ( E n c ( G e n ( 1 λ ) , y ) ) = 1 ] ∣ ≤ n e g l ( λ ) \left| \underset{Gen,Enc}{Pr}[C\lambda(Enc(Gen(1^\lambda),\, x))=1] – \underset{Gen,Enc}{Pr}[C_\lambda(Enc(Gen(1^\lambda),\, y))=1] \right| \le negl(\lambda)∣∣∣∣​G e n ,E n c P r ​[C λ​(E n c (G e n (1 λ),x ))=1 ]−G e n ,E n c P r ​[C λ​(E n c (G e n (1 λ),y ))=1 ]∣∣∣∣​≤n e g l (λ)

密文不可区分（公钥）：公钥方案 ( G e n = ( G 1 , G 2 ) , E n c , D e c ) (Gen=(G_1,G_2),Enc,Dec)(G e n =(G 1 ​,G 2 ​),E n c ,D e c ) 称为密文不可区分的（ 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，有
∣ P r G e n , E n c [ C λ ( G 1 ( 1 λ ) , E n c ( G 1 ( 1 λ ) , x ) ) = 1 ] − P r G e n , E n c [ C λ ( G 1 ( 1 λ ) , E n c ( G 1 ( 1 λ ) , y ) ) = 1 ] ∣ ≤ n e g l ( λ ) \left| \underset{Gen,Enc}{Pr}[C\lambda(G_1(1^\lambda),\, Enc(G_1(1^\lambda),\, x))=1] – \underset{Gen,Enc}{Pr}[C_\lambda(G_1(1^\lambda),\, Enc(G_1(1^\lambda),\, y))=1] \right| \le negl(\lambda)∣∣∣∣​G e n ,E n c P r ​[C λ​(G 1 ​(1 λ),E n c (G 1 ​(1 λ),x ))=1 ]−G e n ,E n c P r ​[C λ​(G 1 ​(1 λ),E n c (G 1 ​(1 λ),y ))=1 ]∣∣∣∣​≤n e g l (λ)

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

现实世界中敌手 A A A 相对于理想世界中模拟器 A ′ A’A ′ 的区分优势为：
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 ∣ \begin{aligned} Adv_{A,\Pi}^{IND}(\lambda) &:= \left| \underset{Gen,Enc,A}{Pr}\left[ Expt_{A,\Pi}^{IND}(1^\lambda,0)=0 \right] – \underset{Gen,Enc,A}{Pr}\left[ Expt_{A,\Pi}^{IND}(1^\lambda,1)=1 \right] \right| \ &:= 2\left| \underset{Gen,Enc,A}{Pr}\left[ Expt_{A,\Pi}^{IND}(1^\lambda,U_1)=1 \right] – \frac{1}{2} \right| \ \end{aligned}A d v A ,ΠI N D ​(λ)​:=∣∣∣∣​G e n ,E n c ,A P r ​[E x p t A ,ΠI N D ​(1 λ,0 )=0 ]−G e n ,E n c ,A P r ​[E x p t A ,ΠI N D ​(1 λ,1 )=1 ]∣∣∣∣​:=2 ∣∣∣∣​G e n ,E n c ,A P r ​[E x p t A ,ΠI N D ​(1 λ,U 1 ​)=1 ]−2 1 ​∣∣∣∣​​

其中 P r G e n , E n c , A ′ [ E x p t A ′ , Π , I d e a l I N D ( 1 λ , U 1 ) = 1 ] = 1 2 \underset{Gen,Enc,A’}{Pr}\left[ Expt_{A’,\Pi,Ideal}^{IND}(1^\lambda,U_1)=1 \right] = \dfrac{1}{2}G e n ,E n c ,A ′P r ​[E x p t A ′,Π,I d e a l I N D ​(1 λ,U 1 ​)=1 ]=2 1 ​

于是，我们说加密方案 Π \Pi Π 是 IND 安全的，如果对于任意的 PPT 敌手 A A A，有
A d v A , Π I N D ( λ ) ≤ n e g l ( λ ) Adv_{A,\Pi}^{IND}(\lambda) \le negl(\lambda)A d v A ,ΠI N D ​(λ)≤n e g l (λ)

多消息密文不可区分（私钥）：私钥方案 ( G e n , E n c , D e c ) (Gen,Enc,Dec)(G e n ,E n c ,D e c ) 称为 多消息 IND 安全的，如果对于任意非一致电路簇 { C λ } λ ∈ N {C_\lambda}{\lambda \in \mathbb N}{C λ​}λ∈N ​，以及任意的 x ‾ 0 , x ‾ 1 ∈ X ‾ λ \overline x_0,\overline x_1 \in \overline X\lambda x 0 ​,x 1 ​∈X λ​，有
∣ P r G e n , E n c [ C λ ( E n c ( G e n ( 1 λ ) , x ‾ 0 ) ) = 1 ] − P r G e n , E n c [ C λ ( E n c ( G e n ( 1 λ ) , x ‾ 1 ) ) = 1 ] ∣ ≤ n e g l ( λ ) \left| \underset{Gen,Enc}{Pr}[C_\lambda(Enc(Gen(1^\lambda),\, \overline x_0))=1] – \underset{Gen,Enc}{Pr}[C_\lambda(Enc(Gen(1^\lambda),\, \overline x_1))=1] \right| \le negl(\lambda)∣∣∣∣​G e n ,E n c P r ​[C λ​(E n c (G e n (1 λ),x 0 ​))=1 ]−G e n ,E n c P r ​[C λ​(E n c (G e n (1 λ),x 1 ​))=1 ]∣∣∣∣​≤n e g l (λ)

多消息密文不可区分（公钥）：公钥方案 ( G e n = ( G 1 , G 2 ) , E n c , D e c ) (Gen=(G_1,G_2),Enc,Dec)(G e n =(G 1 ​,G 2 ​),E n c ,D e c ) 称为称为 多消息 IND 安全的，如果对于任意非一致电路簇 { C λ } λ ∈ N {C_\lambda}{\lambda \in \mathbb N}{C λ​}λ∈N ​，以及任意的 x ‾ 0 , x ‾ 1 ∈ X ‾ λ \overline x_0,\overline x_1 \in \overline X\lambda x 0 ​,x 1 ​∈X λ​，有
∣ P r G e n , E n c [ C λ ( G 1 ( 1 λ ) , E n c ( G 1 ( 1 λ ) , x ‾ 0 ) ) = 1 ] − P r G e n , E n c [ C λ ( G 1 ( 1 λ ) , E n c ( G 1 ( 1 λ ) , x ‾ 1 ) ) = 1 ] ∣ ≤ n e g l ( λ ) \left| \underset{Gen,Enc}{Pr}[C_\lambda(G_1(1^\lambda),\, Enc(G_1(1^\lambda),\, \overline x_0))=1] – \underset{Gen,Enc}{Pr}[C_\lambda(G_1(1^\lambda),\, Enc(G_1(1^\lambda),\, \overline x_1))=1] \right| \le negl(\lambda)∣∣∣∣​G e n ,E n c P r ​[C λ​(G 1 ​(1 λ),E n c (G 1 ​(1 λ),x 0 ​))=1 ]−G e n ,E n c P r ​[C λ​(G 1 ​(1 λ),E n c (G 1 ​(1 λ),x 1 ​))=1 ]∣∣∣∣​≤n e g l (λ)

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

; 加密方案（主动攻击）

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

CPA

选择明文攻击下的语义安全：（公钥、私钥）加密方案 Π = ( G e n = ( G 1 , G 2 ) , E n c , D e c ) \Pi = (Gen=(G_1,G_2),Enc,Dec)Π=(G e n =(G 1 ​,G 2 ​),E n c ,D e c ) 称为称为 CPA 语义安全的，如果对于任意 PPT 的带加密 Oracle 的两阶段算法 A = ( A 1 , A 2 ) A = (A_1,A_2)A =(A 1 ​,A 2 ​)，存在 PPT算法 A ′ = ( A 1 ′ , A 2 ′ ) A’=(A_1′,A_2′)A ′=(A 1 ′​,A 2 ′​)，使得

1. 当 λ \lambda λ 充分大，对于任意的 z ∈ { 0 , 1 } p o l y ( λ ) z \in {0,1}^{poly(\lambda)}z ∈{0 ,1 }p o l y (λ)，有
   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}\right]\ &\le &\underset{A’,S}{Pr}\left[\begin{aligned} v=f(x): && ((S,h,f),\sigma) \leftarrow A_1′(1^\lambda,z)\ && c \leftarrow (1^{|x|},\, h(x)),\, x \leftarrow S(U_{poly(\lambda)})\ && v \leftarrow A_2′(\sigma,c) \end{aligned}\right] + negl(\lambda) \end{aligned}​≤​G e n ,E n c ,A ,S P r ​⎣⎢⎢⎢⎢⎢⎡​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 )​⎦⎥⎥⎥⎥⎥⎤​A ′,S P r ​⎣⎢⎡​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 (λ)​
2. 对于任意的 λ , z \lambda,z λ,z，A 1 ′ ( 1 λ , z ) A_1′(1^\lambda,z)A 1 ′​(1 λ,z ) 与 A 1 E n c e , d ( ⋅ ) ( 1 λ , e , z ) A_1^{Enc_{e,d}(\cdot)}(1^\lambda,e,z)A 1 E n c e ,d ​(⋅)​(1 λ,e ,z ) 输出的 ( S , h , f ) (S,h,f)(S ,h ,f ) 计算不可区分（否则目标不一致，比较无意义）。

定义 选择明文攻击（CPA）的实验 E x p t A , Π , z I N D − C P A ( 1 λ , b ) Expt_{A,\Pi,z}^{IND-CPA}(1^\lambda,b)E x p t A ,Π,z I N D −C P A ​(1 λ,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 ∣ \begin{aligned} Adv_{A,\Pi}^{IND-CPA}(\lambda) &:= \left| \underset{Gen,Enc,A}{Pr}\left[ Expt_{A,\Pi,z}^{IND-CPA}(1^\lambda,0)=0 \right] – \underset{Gen,Enc,A}{Pr}\left[ Expt_{A,\Pi,z}^{IND-CPA}(1^\lambda,1)=1 \right] \right| \ &:= 2\left| \underset{Gen,Enc,A}{Pr}\left[ Expt_{A,\Pi,z}^{IND-CPA}(1^\lambda,U_1)=1 \right] – \frac{1}{2} \right| \end{aligned}A d v A ,ΠI N D −C P A ​(λ)​:=∣∣∣∣​G e n ,E n c ,A P r ​[E x p t A ,Π,z I N D −C P A ​(1 λ,0 )=0 ]−G e n ,E n c ,A P r ​[E x p t A ,Π,z I N D −C P A ​(1 λ,1 )=1 ]∣∣∣∣​:=2 ∣∣∣∣​G e n ,E n c ,A P r ​[E x p t A ,Π,z I N D −C P A ​(1 λ,U 1 ​)=1 ]−2 1 ​∣∣∣∣​​

选择明文攻击下的密文不可区分：（公钥、私钥）加密方案 Π = ( G e n = ( G 1 , G 2 ) , E n c , D e c ) \Pi = (Gen=(G_1,G_2),Enc,Dec)Π=(G e n =(G 1 ​,G 2 ​),E n c ,D e c ) 称为称为 IND-CPA 安全的，如果对于任意 PPT 的带加密 Oracle 的两阶段算法 A = ( A 1 , A 2 ) A = (A_1,A_2)A =(A 1 ​,A 2 ​)，使得区分优势为
A d v A , Π I N D − C P A ( λ ) ≤ n e g l ( n ) Adv_{A,\Pi}^{IND-CPA}(\lambda) \le negl(n)A d v A ,ΠI N D −C P A ​(λ)≤n e g l (n )

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

; CCA1

定义 第一类选择密文攻击（CCA1）的实验 E x p t A , Π , z I N D − C C A 1 ( 1 λ , b ) Expt_{A,\Pi,z}^{IND-CCA1}(1^\lambda,b)E x p t A ,Π,z I N D −C C A 1 ​(1 λ,b )，如图：

CCA2

定义 第二类选择密文攻击（CCA1）的实验 E x p t A , Π , z I N D − C C A 2 ( 1 λ , b ) Expt_{A,\Pi,z}^{IND-CCA2}(1^\lambda,b)E x p t A ,Π,z I N D −C C A 2 ​(1 λ,b )，如图：

; Att

为了统一表示 { C P A , C C A 1 , C C A 2 } {CPA,CCA1,CCA2}{C P A ,C C A 1 ,C C A 2 }，定义实验 E x p t A , Π , z A t t ( 1 λ , b ) Expt_{A,\Pi,z}^{Att}(1^\lambda,b)E x p t A ,Π,z A t t ​(1 λ,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 ∣ \begin{aligned} Adv_{A,\Pi}^{IND-Att}(\lambda) &:= \left| \underset{\Pi,A}{Pr}\left[ Expt_{A,\Pi,z}^{IND-Att}(1^\lambda,0)=0 \right] – \underset{\Pi,A}{Pr}\left[ Expt_{A,\Pi,z}^{IND-Att}(1^\lambda,1)=1 \right] \right| \ &:= 2\left| \underset{\Pi,A,b}{Pr}\left[ Expt_{A,\Pi,z}^{IND-Att}(1^\lambda,U_1)=1 \right] – \frac{1}{2} \right| \end{aligned}A d v A ,ΠI N D −A t t ​(λ)​:=∣∣∣∣​Π,A P r ​[E x p t A ,Π,z I N D −A t t ​(1 λ,0 )=0 ]−Π,A P r ​[E x p t A ,Π,z I N D −A t t ​(1 λ,1 )=1 ]∣∣∣∣​:=2 ∣∣∣∣​Π,A ,b P r ​[E x p t A ,Π,z I N D −A t t ​(1 λ,U 1 ​)=1 ]−2 1 ​∣∣∣∣​​

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

Att-语义安全：（公钥、私钥）加密方案 Π = ( G e n , E n c , D e c ) \Pi = (Gen,Enc,Dec)Π=(G e n ,E n c ,D e c ) 称为 Att – 语义安全的，其中 A t t = { C P A , C C A 1 , C C A 2 } Att={CPA,CCA1,CCA2}A t t ={C P A ,C C A 1 ,C C A 2 }，如果对于任意 PPT 的带 Oracles 的两阶段算法 A = ( A 1 , A 2 ) A = (A_1,A_2)A =(A 1 ​,A 2 ​)，存在 PPT 算法 A ′ = ( A 1 ′ , A 2 ′ ) A’=(A’_1,A’_2)A ′=(A 1 ′​,A 2 ′​)，使得

1. 当 λ \lambda λ 充分大，对于任意的 z ∈ { 0 , 1 } p o l y ( λ ) z \in {0,1}^{poly(\lambda)}z ∈{0 ,1 }p o l y (λ)，有
   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}\right]\ &\le &\underset{A’,S}{Pr}\left[\begin{aligned} v=f(x): && ((S,h,f),\sigma) \leftarrow A_1′(1^\lambda,z)\ && x \leftarrow S(U_{poly(\lambda)})\ && v \leftarrow A_2′(\sigma,1^{|x|},h(x)) \end{aligned}\right] + negl(\lambda) \end{aligned}​≤​Π,A ,S P r ​⎣⎢⎢⎢⎢⎢⎡​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 )​⎦⎥⎥⎥⎥⎥⎤​A ′,S P r ​⎣⎢⎡​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 (λ)​
2. 对于任意的 λ , z \lambda,z λ,z，A 1 ′ ( 1 λ , z ) A_1′(1^\lambda,z)A 1 ′​(1 λ,z ) 与 A 1 E n c e , d ( ⋅ ) , O A t t 1 ( 1 λ , e , z ) A_1^{Enc_{e,d}(\cdot),O_{Att}^1}(1^\lambda,e,z)A 1 E n c e ,d ​(⋅),O A t t 1 ​​(1 λ,e ,z ) 输出的 ( S , h , f ) (S,h,f)(S ,h ,f ) 计算不可区分（否则目标不一致，比较无意义）。

可以证明，

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

签名方案

不可伪造性：签名方案 Π = ( G e n , S i g n , V e r ) \Pi = (Gen,Sign,Ver)Π=(G e n ,S i g n ,V e r ) 的选择消息攻击实验如下：

我们说 Π \Pi Π 是 选择消息攻击下的存在性不可伪造（ EUF-CMA）的，如果对于任意 PPT 敌手 A A A，当 λ \lambda λ 充分大，有
A d v A , Π E U F − C M A ( λ ) : = P r [ E x p t A , Π E U F − C M A ( 1 λ ) = 1 ] ≤ n e g l ( λ ) Adv_{A,\Pi}^{EUF-CMA}(\lambda) := Pr\left[ Expt_{A,\Pi}^{EUF-CMA}(1^\lambda) = 1 \right] \le negl(\lambda)A d v A ,ΠE U F −C M A ​(λ):=P r [E x p t A ,ΠE U F −C M A ​(1 λ)=1 ]≤n e g l (λ)

强不可伪造性：签名方案 Π = ( G e n , S i g n , V e r ) \Pi = (Gen,Sign,Ver)Π=(G e n ,S i g n ,V e r ) 的（强）选择消息攻击实验如下：

我们说 Π \Pi Π 是 选择消息攻击下的（强）存在性不可伪造（ EUF-CMA）的，如果对于任意 PPT 敌手 A A A，当 λ \lambda λ 充分大，有
A d v A , Π E U F − C M A ( λ ) : = P r [ E x p t A , Π E U F − C M A ( 1 λ ) = 1 ] ≤ n e g l ( λ ) Adv_{A,\Pi}^{EUF-CMA}(\lambda) := Pr\left[ Expt_{A,\Pi}^{EUF-CMA}(1^\lambda) = 1 \right] \le negl(\lambda)A d v A ,ΠE U F −C M A ​(λ):=P r [E x p t A ,ΠE U F −C M A ​(1 λ)=1 ]≤n e g l (λ)

; MAC

不可伪造性：消息验证码 Π = ( G e n , M A C , V e r ) \Pi = (Gen,MAC,Ver)Π=(G e n ,M A C ,V e r ) 的选择消息攻击实验如下：

我们说 Π \Pi Π 是 选择消息攻击下的存在性不可伪造（ EUF-CMA）的，如果对于任意 PPT 敌手 A A A，当 λ \lambda λ 充分大，有
A d v A , Π E U F − C M A ( λ ) : = P r [ E x p t A , Π E U F − C M A ( 1 λ ) = 1 ] ≤ n e g l ( λ ) Adv_{A,\Pi}^{EUF-CMA}(\lambda) := Pr\left[ Expt_{A,\Pi}^{EUF-CMA}(1^\lambda) = 1 \right] \le negl(\lambda)A d v A ,ΠE U F −C M A ​(λ):=P r [E x p t A ,ΠE U F −C M A ​(1 λ)=1 ]≤n e g l (λ)

Original: https://blog.csdn.net/weixin_44885334/article/details/127814873
Author: 山登绝顶我为峰 3(
Title: 安全性归约（安全性定义 – 2）