参考文献：

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

令$s{\leftarrow }_{R}S$定义为：从有限集合$S$中均匀随机选择一个元素$s$

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

Hybrid Encryption

非对称加密

非对称加密方案，定义为一个算法组：
$${\Pi }^{asym}=(K^{asym},E^{asym},D^{asym},COIN{S}^{asym},MSP{C}^{asym})$$

$K^{asym}$：密钥生成算法，$(pk,sk)\leftarrow K^{asym}(1^k)$，其中$k\in N$

$E^{asym}$：加密算法，$y\leftarrow E_{pk}^{asym}(x,r)$，其中$r{\leftarrow }_{R}COIN{S}^{asym}$

$D^{asym}$：解密算法，$x\leftarrow D_{sk}^{asym}(y)$

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

$MSP{C}^{asym}$：消息集合， M S P C ( k ) ⊆ { 0 , 1 } ∗ MSPC(k) \subseteq \{0,1\}^* MSPC(k)⊆{0,1}∗

对称加密

对称加密方案，定义为一个算法组：
$${\Pi }^{sym}=(E^{asym},D^{asym},KSP{C}^{asym},MSP{C}^{asym})$$
$E^{sym}$：加密算法，$y\leftarrow E_{key}^{sym}(x)$

$D^{sym}$：解密算法，$x\leftarrow D_{key}^{sym}(y)$

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

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

混合使用

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

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

Fujisaki- Okamoto Conversion

混合加密

给定非对称加密方案${\Pi }^{asym}$以及对称加密方案${\Pi }^{sym}$，混合加密定义为：
$${\Pi }^{hy}=(K^{hy},E^{hy},D^{hy},COIN{S}^{hy},MSP{C}^{hy})$$
$K^{hy}$：密钥生成算法，$(pk,sk)\leftarrow K^{hy}(1^k)$，其中$k\in N$

$E^{hy}$：加密算法，$y\leftarrow E_{pk}^{hy}(x,r)$，其中$r{\leftarrow }_{R}COIN{S}^{hy}$

$D^{hy}$：解密算法，$x\leftarrow D_{sk}^{hy}(y)$

$COIN{S}^{hy}$：随机数集合，$COIN{S}^{hy}=MSP{C}^{asym}$

$MSP{C}^{hy}$：消息集合，$MSP{C}^{hy}=MSP{C}^{sym}$

FO转换

ROM：random oracle model

$H(\cdot )$：ROM下的Hash函数，映射为
$$H:MSP{C}^{asym}\times MSP{C}^{sym}\to COIN{S}^{asym}$$
$G(\cdot )$：ROM下的Hash函数，映射为
$$G:MSP{C}^{asym}\to KSP{C}^{sym}$$
加密算法：
$$E_{pk}^{hy}(m,\sigma ):=E_{pk}^{asym}(\sigma ,H(\sigma ,m))\Vert E_{G(\sigma )}^{sym}(m)$$
其中$\sigma {\leftarrow }_{R}COI{N}^{hy}$，$m\in MSP{C}^{hy}$

解密算法：
$$D_{sk}^{hy}(c_1\Vert c_2)=\{\begin{array}{rlr}{D}_{G(\hat{\sigma })}^{sym}(c_2),& & c_1=E_{pk}^{asym}(\hat{\sigma },H(\hat{\sigma },\hat{m}))\\ \perp ,& & otherwise\end{array}$$
其中$\hat{\sigma }:=D_{sk}^{asym}(c1)$，$\hat{m}:=D_{G(\hat{\sigma })}^{sym}(c_2)$

安全性

• One-way Encryption (OWE)：非对称加密方案${\Pi }^{asym}=(K^{asym},E^{asym},D^{asym},COIN{S}^{asym},MSP{C}^{asym})$，$A$是敌手，其优势定义为

$$Ad{v}_{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)]$$

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

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

• Find-Guess (FG)：对称加密方案${\Pi }^{sym}=(K^{sym},E^{sym},D^{sym},KSP{C}^{sym},MSP{C}^{sym})$，$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$运行时间至多为$t$，优势至少为$ϵ$，那么说：adversary $A$ $(t,ϵ)-$breaks ${\Pi }^{sym}$ in the sense of FG in the ROM

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

• 定理：If ${\Pi }^{asym}$ is $(t_1,{ϵ}_1)-$ secure in the sense of OWE，${\Pi }^{sym}$ is $(t_2,{ϵ}_2)-$ secure in the sense of FG，then ${\Pi }^{hy}$ is $(t,q_G,q_H,q_D,ϵ)-$secure in the sense of IND-CCA in the ROM.

  这里$q_G,q_H,q_D$是查询$G(\cdot ),H(\cdot ),D_{sk}(\cdot )$预言机的次数，$t$是执行时间，$ϵ$是优势上界。

  优势定义为：
  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​

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