Fujisaki - Okamoto Conversion（FO转换）

admin管理员组

文章数量:1530048

参考文献：

1. Fujisaki E, Okamoto T. Secure integration of asymmetric and symmetric encryption schemes[C]//Annual international cryptology conference. Springer, Berlin, Heidelberg, 1999: 537-554.

文章目录

• Hybrid Encryption
• • • 非对称加密
    • 对称加密
    • 混合使用
• Fujisaki- Okamoto Conversion
• • • 混合加密
    • FO转换
    • 安全性

令 s ← R S s \leftarrow_R S s←R​S定义为：从有限集合 S S S中均匀随机选择一个元素 s s s

令 a ← A ( ⋅ ) a \leftarrow A(\cdot) a←A(⋅)定义为：将算法 A A A的结果赋值给 a a a

Hybrid Encryption

非对称加密

非对称加密方案，定义为一个算法组：
Π a s y m = ( K a s y m , E a s y m , D a s y m , C O I N S a s y m , M S P C a s y m ) \Pi^{asym} = (K^{asym},E^{asym},D^{asym},COINS^{asym},MSPC^{asym}) Πasym=(Kasym,Easym,Dasym,COINSasym,MSPCasym)

K a s y m K^{asym} Kasym：密钥生成算法， ( p k , s k ) ← K a s y m ( 1 k ) (pk,sk) \leftarrow K^{asym}(1^k) (pk,sk)←Kasym(1k)，其中 k ∈ N k \in N k∈N

E a s y m E^{asym} Easym：加密算法， y ← E p k a s y m ( x , r ) y \leftarrow E_{pk}^{asym}(x,r) y←Epkasym​(x,r)，其中 r ← R C O I N S a s y m r \leftarrow_R COINS^{asym} r←R​COINSasym

D a s y m D^{asym} Dasym：解密算法， x ← D s k a s y m ( y ) x \leftarrow D_{sk}^{asym}(y) x←Dskasym​(y)

C O I N S a s y m COINS^{asym} COINSasym：随机数集合， C O I N S ( k ) ⊆ { 0 , 1 } ∗ COINS(k) \subseteq \{0,1\}^* COINS(k)⊆{0,1}∗

M S P C a s y m MSPC^{asym} MSPCasym：消息集合， M S P C ( k ) ⊆ { 0 , 1 } ∗ MSPC(k) \subseteq \{0,1\}^* MSPC(k)⊆{0,1}∗

对称加密

对称加密方案，定义为一个算法组：
Π s y m = ( E a s y m , D a s y m , K S P C a s y m , M S P C a s y m ) \Pi^{sym} = (E^{asym},D^{asym},KSPC^{asym},MSPC^{asym}) Πsym=(Easym,Dasym,KSPCasym,MSPCasym)
E s y m E^{sym} Esym：加密算法， y ← E k e y s y m ( x ) y \leftarrow E_{key}^{sym}(x) y←Ekeysym​(x)

D s y m D^{sym} Dsym：解密算法， x ← D k e y s y m ( y ) x \leftarrow D_{key}^{sym}(y) x←Dkeysym​(y)

K S P C s y m KSPC^{sym} KSPCsym：密钥集合， K S P C ( k ) ⊆ { 0 , 1 } ∗ KSPC(k) \subseteq \{0,1\}^* KSPC(k)⊆{0,1}∗

M S P C s y m MSPC^{sym} MSPCsym：消息集合， M S P C ( k ) ⊆ { 0 , 1 } ∗ MSPC(k) \subseteq \{0,1\}^* MSPC(k)⊆{0,1}∗

混合使用

给定一个非对称加密方案以及一个对称加密方案。一般的，非对称加密方案仅被用来传递对称加密方案的密钥，使用对称加密方案来传递消息。

然而，这种混合使用往往是不安全的，即使上述两种加密方案的安全性都非常高。

Fujisaki- Okamoto Conversion

混合加密

给定非对称加密方案 Π a s y m \Pi^{asym} Πasym以及对称加密方案 Π s y m \Pi^{sym} Πsym，混合加密定义为：
Π h y = ( K h y , E h y , D h y , C O I N S h y , M S P C h y ) \Pi^{hy} = (K^{hy},E^{hy},D^{hy},COINS^{hy},MSPC^{hy}) Πhy=(Khy,Ehy,Dhy,COINShy,MSPChy)
K h y K^{hy} Khy：密钥生成算法， ( p k , s k ) ← K h y ( 1 k ) (pk,sk) \leftarrow K^{hy}(1^k) (pk,sk)←Khy(1k)，其中 k ∈ N k \in N k∈N

E h y E^{hy} Ehy：加密算法， y ← E p k h y ( x , r ) y \leftarrow E_{pk}^{hy}(x,r) y←Epkhy​(x,r)，其中 r ← R C O I N S h y r \leftarrow_R COINS^{hy} r←R​COINShy

D h y D^{hy} Dhy：解密算法， x ← D s k h y ( y ) x \leftarrow D_{sk}^{hy}(y) x←Dskhy​(y)

C O I N S h y COINS^{hy} COINShy：随机数集合， C O I N S h y = M S P C a s y m COINS^{hy}=MSPC^{asym} COINShy=MSPCasym

M S P C h y MSPC^{hy} MSPChy：消息集合， M S P C h y = M S P C s y m MSPC^{hy}=MSPC^{sym} MSPChy=MSPCsym

FO转换

ROM：random oracle model

H ( ⋅ ) H(\cdot) H(⋅)：ROM下的Hash函数，映射为
H : M S P C a s y m × M S P C s y m → C O I N S a s y m H: MSPC^{asym} \times MSPC^{sym} \rightarrow COINS^{asym} H:MSPCasym×MSPCsym→COINSasym
G ( ⋅ ) G(\cdot) G(⋅)：ROM下的Hash函数，映射为
G : M S P C a s y m → K S P C s y m G: MSPC^{asym} \rightarrow KSPC^{sym} G:MSPCasym→KSPCsym
加密算法：
E p k h y ( m , σ ) : = E p k a s y m ( σ , H ( σ , m ) ) ∥ E G ( σ ) s y m ( m ) E_{pk}^{hy}(m,\sigma) := E_{pk}^{asym}(\sigma,H(\sigma,m)) \| E_{G(\sigma)}^{sym}(m) Epkhy​(m,σ):=Epkasym​(σ,H(σ,m))∥EG(σ)sym​(m)
其中 σ ← R C O I N h y \sigma \leftarrow_R COIN^{hy} σ←R​COINhy， m ∈ M S P C h y m \in MSPC^{hy} m∈MSPChy

解密算法：
D s k h y ( c 1 ∥ c 2 ) = { D G ( σ ^ ) s y m ( c 2 ) , c 1 = E p k a s y m ( σ ^ , H ( σ ^ , m ^ ) ) ⊥ , o t h e r w i s e D_{sk}^{hy}(c_1\|c_2) = \left\{ \begin{aligned} D_{G(\hat\sigma)}^{sym}(c_2) ,&& c_1 = E_{pk}^{asym}(\hat\sigma,H(\hat\sigma,\hat m))\\ \perp ,&& otherwise\\ \end{aligned} \right. Dskhy​(c1​∥c2​)={DG(σ^)sym​(c2​),⊥,​​c1​=Epkasym​(σ^,H(σ^,m^))otherwise​
其中 σ ^ : = D s k a s y m ( c 1 ) \hat\sigma:=D_{sk}^{asym}(c1) σ^:=Dskasym​(c1)， m ^ : = D G ( σ ^ ) s y m ( c 2 ) \hat m := D_{G(\hat\sigma)}^{sym}(c_2) m^:=DG(σ^)sym​(c2​)

安全性

• One-way Encryption (OWE)：非对称加密方案 Π a s y m = ( K a s y m , E a s y m , D a s y m , C O I N S a s y m , M S P C a s y m ) \Pi^{asym} = (K^{asym},E^{asym},D^{asym},COINS^{asym},MSPC^{asym}) Πasym=(Kasym,Easym,Dasym,COINSasym,MSPCasym)， A A A是敌手，其优势定义为

A d v A , Π , M S P C O W E ( k ) : = P r [ ( p k , s k ) ← K ( 1 k ) , x ← M S P C ( k ) , y ← E p k ( x ) : A ( p k , y ) = D s k ( y ) ] Adv_{A,\Pi,MSPC}^{OWE}(k) := Pr[(pk,sk)\leftarrow K(1^k), x \leftarrow MSPC(k), y \leftarrow E_{pk}(x): A(pk,y)=D_{sk}(y)] AdvA,Π,MSPCOWE​(k):=Pr[(pk,sk)←K(1k),x←MSPC(k),y←Epk​(x):A(pk,y)=Dsk​(y)]

如果敌手 A A A运行时间至多为 t t t，优势至少为 ϵ \epsilon ϵ，那么说：adversary A A A ( t , ϵ ) − (t,\epsilon)- (t,ϵ)−breaks Π a s y m \Pi^{asym} Πasym in the sense of OWE

如果不存在这样的敌手，那么说： Π a s y m \Pi^{asym} Πasym is ( t , ϵ ) − (t,\epsilon)- (t,ϵ)− secure in the sense of OWE

• Find-Guess (FG)：对称加密方案 Π s y m = ( K s y m , E s y m , D s y m , K S P C s y m , M S P C s y m ) \Pi^{sym} = (K^{sym},E^{sym},D^{sym},KSPC^{sym},MSPC^{sym}) Πsym=(Ksym,Esym,Dsym,KSPCsym,MSPCsym)， A A A是敌手，其优势定义为

A d v A , Π F G ( k ) : = 2 ⋅ P r [ k e y ← K S P C ( k ) , ( x 0 , x 1 , s ) ← A ( f i n d ) , b ← R { 0 , 1 } , y ← E k e y ( x b ) : A ( g u e s s , s , y ) = b ] − 1 Adv_{A,\Pi}^{FG}(k) := 2\cdot Pr[key\leftarrow KSPC(k), (x_0,x_1,s) \leftarrow A(find), b \leftarrow_R \{0,1\},y \leftarrow E_{key}(x_b): A(guess,s,y)=b] - 1 AdvA,ΠFG​(k):=2⋅Pr[key←KSPC(k),(x0​,x1​,s)←A(find),b←R​{0,1},y←Ekey​(xb​):A(guess,s,y)=b]−1

如果敌手 A A A运行时间至多为 t t t，优势至少为 ϵ \epsilon ϵ，那么说：adversary A A A ( t , ϵ ) − (t,\epsilon)- (t,ϵ)−breaks Π s y m \Pi^{sym} Πsym in the sense of FG in the ROM

如果不存在这样的敌手，那么说： Π s y m \Pi^{sym} Πsym is ( t , ϵ ) − (t,\epsilon)- (t,ϵ)− secure in the sense of FG

• 定理：If Π a s y m \Pi^{asym} Πasym is ( t 1 , ϵ 1 ) − (t_1,\epsilon_1)- (t1​,ϵ1​)− secure in the sense of OWE， Π s y m \Pi^{sym} Πsym is ( t 2 , ϵ 2 ) − (t_2,\epsilon_2)- (t2​,ϵ2​)− secure in the sense of FG，then Π h y \Pi^{hy} Πhy is ( t , q G , q H , q D , ϵ ) − (t,q_G,q_H,q_D,\epsilon)- (t,qG​,qH​,qD​,ϵ)−secure in the sense of IND-CCA in the ROM.

  这里 q G , q H , q D q_G,q_H,q_D qG​,qH​,qD​是查询 G ( ⋅ ) , H ( ⋅ ) , D s k ( ⋅ ) G(\cdot),H(\cdot),D_{sk}(\cdot) G(⋅),H(⋅),Dsk​(⋅)预言机的次数， t t t是执行时间， ϵ \epsilon ϵ是优势上界。

  优势定义为：
  A d v A , Π I N D − C C A ( k ) : = 2 ⋅ P r [ G , H ← Ω ; ( s k , p k ) ← K ( 1 k ) ; ( x 0 , x 1 , s ) ← A G , H , D s k ( f i n d , p k ) ; b ← R { 0 , 1 } ; y ← E p k G , H ( x b ) : A G , H , D s k ( g u e s s , s , y ) = b ] − 1 \begin{aligned} Adv_{A,\Pi}^{IND-CCA}(k) := 2\cdot Pr[G,H\leftarrow \Omega; (sk,pk) \leftarrow K(1^k); (x_0,x_1,s) \leftarrow A^{G,H,D_{sk}}(find,pk); \\b \leftarrow_R \{0,1\}; y \leftarrow E_{pk}^{G,H}(x_b): A^{G,H,D_{sk}}(guess,s,y)=b] - 1 \end{aligned} AdvA,ΠIND−CCA​(k):=2⋅Pr[G,H←Ω;(sk,pk)←K(1k);(x0​,x1​,s)←AG,H,Dsk​(find,pk);b←R​{0,1};y←EpkG,H​(xb​):AG,H,Dsk​(guess,s,y)=b]−1​

一般的，对称加密方案 Π s y m \Pi^{sym} Πsym可以选择为一次一密， E s k ( m ) = s k ⊕ m E_{sk}(m) = sk \oplus m Esk​(m)=sk⊕m
给定任意CPA安全的非对称加密方案，都可以利用FO转换，得到IND-CCA安全的非对称加密方案！

本文标签： OkamotoFujisakiFOconversion