首先，之前的博文里面已经证明了ELGamal加密方案不是CCA安全的，可以发现CCA安全的方案其实并不是可以非常简单构造的，尤其是CCA安全的公钥加密方案。要想构造出CCA安全的公钥方案，就要借助一些性质更加特殊的密码原语才可以成功，比如摘要函数，摘要函数之前的博文也有总结过。公钥密码的课堂上老师证明了Cramer-Shoup加密方案是CCA安全的，但证明过程较为繁琐，首先来看Cramer-Shoup加密方案的具体流程。

Cramer-Shoup加密方案

    该方案使用了抗目标碰撞的摘要函数(弱$Hash$函数)$HASH=(HGen,T)$，假设$\mathcal{G}$是一个群生成算法，$\lambda$是安全参数。
Cramer-Shoup加密方案：$CS=(Gen,Enc,Dec)$
$\color{red}{Gen}$：输入$1^\lambda$，生成$(\mathbb{G},q,g_1) \leftarrow \mathcal{G}(1^\lambda)$，随机生成$\mathbb{Z}_q$中的元素$x_1,x_2,y_1,y_2,z_1,z_2$和$a\leftarrow \mathbb{Z}_q^*$，计算

$$g_2=g_1^a \quad X:=g_1^{x_1}g_2^{x_2} \quad Y:=g_1^{y_1}g_2^{y_2} \quad Z:=g_1^{z_1}g_2^{z_2} \quad s \leftarrow HGen(1^\lambda)$$

输出$pk=(g_1,g_2,X,Y,Z,T^s(\cdot))$和$sk=(x_1,x_2,y_1,y_2,z_1,z_2)$
$\color{red}{Enc}$：对于输入$pk$和消息$m \in \mathcal{G}$，随机选取$r \leftarrow \mathbb{Z}_q, r\neq 0$，计算

$$u_1:=g_1^r \quad u_2=g_2^r \quad c:=Z^r \cdot m \quad \alpha:=T^s(u_1,u_2,c) \quad v:=X^rY^{\alpha r}$$

输出密文$(u_1,u_2,v,c)$
$\color{red}{Dec}$：输入密文$(u_1,u_2,v,c)$和私钥$sk=(x_1,x_2,y_1,y_2,z_1,z_2)$，顺序计算

$$\alpha :=T^s(u_1,u_2,c) \quad v'=u_1^{x_1+\alpha y_1} u_2^{x_2+\alpha y_2} \quad m:=c \cdot (u_1^{z_1} u_2^{z_2})^{-1}$$

如果$v=v’$输出$m$，否则输出$\perp$

    这个方案的正确性是非常显然的，如果消息$m$诚如上述方式进行加密，则一定能够通过$v=v’$的检测且最后解密一定能成功解密出$m$。

Cramer-Shoup方案的CCA安全定理

    首先有如下定理：对于任何$PPT$敌手$\mathcal{A}$对于Cramer-Shoup方案进行的CCA选择密文攻击实验，一定存在对于$\mathcal{G}$进行$DH$组分辨的$PPT$敌手$\mathcal{A}_1$，以及对于摘要函数$HASH$进行第二原像攻击的$PPT$敌手$\mathcal{A}_2$，使得它们的优势满足：

$$\color{red}{Adv_{\mathcal{A},CS}^{cca}(\lambda) \leq 2\cdot Adv_{\mathcal{A}_1,\mathcal{G}}^{ddh}(\lambda)+Adv_{\mathcal{A}_2,HASH}^{tcr}(\lambda)+\frac{4+Q}{q} \tag{1}}$$

其中$Q$是敌手$\mathcal{A}$询问解密$oracle$的次数上界。
    这里的$q$是在生成群的描述时产生的，一般情况下$q$是安全参数的指数级大小，比如安全参数为$\lambda$，要想生成群，就要先生成模$q$的剩余类环，而这个$q$恰巧是$\lambda$比特长的，则显然可以认为$q=q(2^\lambda)$。所以如果$DDH$对于$\mathcal{G}$难解，摘要函数$HASH$是抗目标碰撞的，则必有$Adv_{\mathcal{A}_1,\mathcal{G}}^{ddh}(\lambda), Adv_{\mathcal{A}_2,HASH}^{tcr}(\lambda),\frac{4+Q}{q}$都是可忽略的函数，则有$Adv_{\mathcal{A},CS}^{cca}(\lambda)$是可忽略的函数，也就是说Cramer-Shoup方案的确是CCA安全的。
    一般情形下，$DDH$的难解性和$HASH=(HGen,T)$是抗目标碰撞$HASH$函数都是假设，所以我们只要证明$\color{red}{(1)}$式成立即可。

具体证明

    这个的证明非常繁琐，但难度并不是特别难，需要利用实验序列的思想，构造六个实验，首先来看$Expt_1$与$Expt_2$

$Expt_1$与$Expt_2$

$$Exp_1: input 1^\lambda\\ pk,sk \leftarrow CS \quad scheme\\ pk=(g_1,g_2,X,Y,Z,T^s(\cdot))\\ sk=(x_1,x_2,y_1,y_2,z_1,z_2)\\ \mathcal{A}(pk)\quad ask \quad Dec_{sk}(\cdot)\\ (m_0.m_1) \leftarrow \mathcal{A}(1^\lambda ,pk)\\ \delta \leftarrow \{0,1\} ,r^* \leftarrow \mathbb{Z}_q\\ u_1^*=g_1^{r^*}, u_2^*=g_2^{r^*}, c^*:=Z^{r^*} \cdot m_{\delta}\\ \alpha^*:=T^s(u_1^*,u_2^*,c^*)\\ v^*:=X^{r^*}Y^{\alpha^* r^*}\\ \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\quad ask \quad Dec_{sk}^*(\cdot)\\ \delta' \leftarrow \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\\ if \delta'=\delta \quad output \quad 1 \quad else \quad 0$$

$$Exp_1: input 1^\lambda\\ pk,sk \leftarrow CS \quad scheme\\ pk=(g_1,g_2,X,Y,Z,T^s(\cdot))\\ sk=(x_1,x_2,y_1,y_2,z_1,z_2)\\ \mathcal{A}(pk)\quad ask \quad Dec_{sk}(\cdot)\\ (m_0.m_1) \leftarrow \mathcal{A}(1^\lambda ,pk)\\ \delta \leftarrow \{0,1\} ,r^* \leftarrow \mathbb{Z}_q\\ u_1^*=g_1^{r^*}, u_2^*=g_2^{r^*}, \color{red}{c^*:=(u_1^*)^{z_1}(u_2^*)^{z_2} \cdot m_{\delta}}\\ \alpha^*:=T^s(u_1^*,u_2^*,c^*)\\ \color{red}{v^*:=(u_1^*)^{x_1+\alpha^* y_1} (u_2^*)^{x_2+\alpha^* y_2}}\\ \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\quad ask \quad Dec_{sk}^*(\cdot)\\ \delta' \leftarrow \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\\ if \delta'=\delta \quad output \quad 1 \quad else \quad 0$$

非常显然的，$Expt_1$就是敌手$\mathcal{A}$对$CS$进行CCA攻击的分辨实验，所以必有下式成立：

$$\color{red}{Adv_{\mathcal{A},CS}^{cca}(\lambda)=|Pr[Expt_1 \quad success]-\frac{1}{2}| \tag{2}}$$

这就将我们想要证明的$\color{red}{(1)}$式的左边和实验序列的第一个实验$Expt_1$联系了起来。

    另外，可以直观的发现$Expt_1$与$Expt_2$其实没有区别，尽管实验里标红的地方有些区别，但根据$CS$方案的结构，那只是同一个量不同的表示方式而已，所以必有：

$$\color{red}{Pr[Expt_1 \quad success]=Pr[Expt_2 \quad success] \tag{3}}$$

$Expt_2$与$Expt_3$

    再考虑$Expt_2$与$Expt_3$如下：

$$Exp_2: input 1^\lambda\\ pk,sk \leftarrow CS \quad scheme\\ pk=(g_1,g_2,X,Y,Z,T^s(\cdot))\\ sk=(x_1,x_2,y_1,y_2,z_1,z_2)\\ \mathcal{A}(pk)\quad ask \quad Dec_{sk}(\cdot)\\ (m_0.m_1) \leftarrow \mathcal{A}(1^\lambda ,pk)\\ \delta \leftarrow \{0,1\} ,r^* \leftarrow \mathbb{Z}_q\\ u_1^*=g_1^{r^*}, u_2^*=g_2^{r^*}, c^*:=(u_1^*)^{z_1}(u_2^*)^{z_2} \cdot m_{\delta}\\ \alpha^*:=T^s(u_1^*,u_2^*,c^*)\\ v^*:=(u_1^*)^{x_1+\alpha^* y_1} (u_2^*)^{x_2+\alpha^* y_2}\\ \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\quad ask \quad Dec_{sk}^*(\cdot)\\ \delta' \leftarrow \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\\ if \delta'=\delta \quad output \quad 1 \quad else \quad 0$$

$$Exp_3: input 1^\lambda\\ pk,sk \leftarrow CS \quad scheme\\ pk=(g_1,g_2,X,Y,Z,T^s(\cdot))\\ sk=(x_1,x_2,y_1,y_2,z_1,z_2)\\ \mathcal{A}(pk)\quad ask \quad Dec_{sk}(\cdot)\\ (m_0.m_1) \leftarrow \mathcal{A}(1^\lambda ,pk)\\ \color{red}{r_1^*,r_2^* \leftarrow \mathbb{Z}_q,r_1^* \neq r_2^*}\\ \color{red}{u_1^*=g_1^{r_1^*}, u_2^*=g_2^{r_2^*}}\\ \delta \leftarrow \{0,1\}, c^*:=(u_1^*)^{z_1}(u_2^*)^{z_2} \cdot m_{\delta}\\ \alpha^*:=T^s(u_1^*,u_2^*,c^*)\\ v^*:=(u_1^*)^{x_1+\alpha^* y_1} (u_2^*)^{x_2+\alpha^* y_2}\\ \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\quad ask \quad Dec_{sk}^*(\cdot)\\ \delta' \leftarrow \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\\ if \delta'=\delta \quad output \quad 1 \quad else \quad 0$$

可以发现仅仅一处有变动，就是$Expt_2$是$r^* \leftarrow \mathbb{Z}_q, u_1^*=g_1^{r^*}, u_2^*=g_2^{r^*}$，这里都是$g_1$或$g_2$的$r^*$次幂，但$Expt_3$中变成了$\color{red}{r_1^*,r_2^* \leftarrow \mathbb{Z}_q,r_1^* \neq r_2^* ,u_1^*=g_1^{r_1^*}, u_2^*=g_2^{r_2^*}}$，也就是说他们的幂次不是相等的，而是完全随机的。

    我们要考虑$Expt_2$与$Expt_3$成功概率之间的联系，就要找到一些可联系的点，首先考虑每个实验中的$(g_1,g_2,u_1^*,u_2^*)$这个四元组，$Expt_2$中有:

$$(g_1,g_2,u_1^*,u_2^*)=(g_1,g_1^a,g_1^{r^*},g_2^{r^*})=(g_1,g_1^a,g_1^{r^*},g_1^{ar^*})$$

而在$Expt_3$中有$(g_1,g_2,u_1^*,u_2^*)=(g_1,g_1^a,g_1^{r_1^*},g_1^{ar_2^*})$，也就是说$Expt_2$中的$(g_1,g_2,u_1^*,u_2^*)$一定是一个$DH$组，但$Expt_3$中的$(g_1,g_2,u_1^*,u_2^*)$与$DH$组有非常大的区别，由此可以利用$DDH$假设进行成功概率的分析。

    标准的$DH$组的形式是$(g,g^x,g^y,g^{xy})$，这里的$x,y$都没有取值的限制，也就是说$x,y \leftarrow \mathbb{Z}_q$，但$Expt_2$中的$(g_1,g_2,u_1^*,u_2^*)$是要求$g_2=g_1^a$，而且根据$CS$方案，这里的$a\leftarrow \mathbb{Z}_q^*$，这是非常显然的，出于加密的一些考虑，如果$a=0$，方案的安全性会不完美，此时的$g_2$就是单位元，也就违背了引入$g_2$的初衷。由于$q$是素数，所以$Expt_2$中的$(g_1,g_2,u_1^*,u_2^*)$与标准的$DH$组只差了一个$a=0$，那这样的$(g_1,g_2,u_1^*,u_2^*)$还满足$DDH$的假设吗？实际上依旧是满足的，这个称为是$DDH$假设的改进。

$DDH$假设的改进

    标准的$DDH$假设区分的是：

$$D_1:=\{(g,g^x,g^y,g^{xy})|x,y \in \mathbb{Z}_q\} \quad T_1:=\{(g,g^x,g^y,g^z)|x,y ,z\in \mathbb{Z}_q\}$$

改进的$DDH$假设区分的是：

$$D_2:=\{(g,g^x,g^y,g^{xy})|x \neq 0\} \quad T_2:=\{(g,g^x,g^y,g^z)|x \neq 0 ,z\neq xy\}$$

其实这个改进是根据$Expt_3$来的，首先根据$CS$方案的设计，$x \neq 0$是$D_2,T_2$的基础，但为什么$T_2$还要要求$z\neq xy$，这是因为$Expt_3$标红的地方要求$r_1^* \neq r_2^*$，则有$a r_1^* \neq ar_2^*$，这也就是$z\neq xy$。其实如果这条不满足，$Expt_3$与$Expt_2$也是完全没有区别的。
    接下来我们考虑两个分辨$DH$组的实验$Expt_{\mathcal{A},\mathcal{G}}^{ddh}(\cdot)$和$Expt_{\mathcal{A},\mathcal{G}}^{ddh'}(\cdot)$如下：

$$Expt_{\mathcal{A},\mathcal{G}}^{ddh}(\cdot): input 1^\lambda\\ (\mathbb{G},q,g) \leftarrow \mathcal{G}(1^\lambda)\\ b \leftarrow \{0,1\},X,Y,Z \leftarrow \mathbb{G}\\ if b=1,\hat{Z}=dh_g(X,Y)\\ if b=0,\hat{Z}=Z\\ b' \leftarrow \mathcal{A}(\mathbb{G},q,g,X,Y,\hat{Z}), b' \in \{0,1\}\\ output \quad b'\\ $$

$$Expt_{\mathcal{A},\mathcal{G}}^{ddh'}(\cdot): input 1^\lambda\\ (\mathbb{G},q,g) \leftarrow \mathcal{G}(1^\lambda)\\ b \leftarrow \{0,1\},X,Y,Z \leftarrow \mathbb{G}, \color{red}{x \neq 0 ,z\neq xy}\\ if b=1,\hat{Z}=dh_g(X,Y)\\ if b=0,\hat{Z}=Z\\ b' \leftarrow \mathcal{A}(\mathbb{G},q,g,X,Y,\hat{Z}), b' \in \{0,1\}\\ output \quad b'\\ $$

其中$dh_g(X,Y)$表示由$X,Y$生成一个$DH$组，我们接下来就要考虑这两个实验的优势

$$Adv_{\mathcal{A},\mathcal{G}}^{ddh-01}(\cdot) \quad Adv_{\mathcal{A},\mathcal{G}}^{ddh'-01}(\cdot)$$

有什么联系。

    要整理出这两个实验的优势有点繁琐，我们一步一步得来写，首先定义两个集合：

$$S_{1}^{\prime}:=\{(g^{x}, g^{y}, g^{x y}) | y \in \mathbb{Z}_{q}, x=0\} \\ S_{2}^{\prime}:=\{(g^{x}, g^{y}, g^{z}) | x, y, z \in \mathbb{Z}_{q},(x=0 \vee z=x y)\}$$

可以发现有$D_1=D_2 \cup S_{1}^{\prime},T_1=T_2 \cup S_{2}^{\prime}$。
    我们考虑集合$S_{1}^{\prime},S_{2}^{\prime}$中元素的个数，非常显然的有$|S_{1}^{\prime}|=q$，至于$|S_{2}^{\prime}|$，必有:

$$|S_{2}^{\prime}|=|T_1|-|T_2|=q^3-q(q-1)^2$$

首先设$X_{D_1}$为集合$D_1$里的一个随机元素，$X_{D_2}$为集合$D_2$里的一个随机元素，则对任意的集合$M \subset D_1$，必有:

$$\begin{aligned} |Pr[X_{D_1} \in M]-Pr[X_{D_2} \in M]|&=|Pr[X_{D_1} \in M]-Pr[X_{D_2} \in M \cap D_2]| \\ &=|Pr[X_{D_1} \in M \cap \overline{D_2}]+\color{red}{Pr[X_{D_1} \in M \cap D_2]-Pr[X_{D_2} \in M \cap D_2]}| \\ & \leq |Pr[X_{D_1} \in M \cap \overline{D_2}]| \\ & \leq |Pr[X_{D_1} \in D_1 \cap \overline{D_2}]|= |Pr[X_{D_1} \in S_{1}^{\prime}]|\\ &= |Pr[X_{D_1} \in S_{1}^{\prime}]-0|\\ &= |Pr[X_{D_1} \in S_{1}^{\prime}]-Pr[X_{D_2} \in S_{1}^{\prime}]|=\frac{1}{q} \end{aligned}$$

上面等式成立的一个重要条件就是标红的式子$\color{red}{Pr[X_{D_1} \in M \cap D_2]-Pr[X_{D_2} \in M \cap D_2]}$一定为负值，这是非常显然的，因为集合$D_1$里的元素个数比集合$D_2$里的元素个数要多。
    同理，设$Y_{T_1}$为集合$T_1$里的一个随机元素，$Y_{T_2}$为集合$T_2$里的一个随机元素，则对任意的集合$M \subset T_1$，必有:

$$\begin{aligned} |Pr[Y_{T_1} \in M]-Pr[Y_{T_2} \in M]|&=|Pr[Y_{T_1} \in M]-Pr[Y_{T_2} \in M \cap T_2]| \\ &=|Pr[Y_{T_1} \in M \cap \overline{T_2}]+\color{red}{Pr[Y_{T_1} \in M \cap T_2]-Pr[Y_{T_2} \in M \cap T_2]}| \\ & \leq |Pr[Y_{T_1} \in M \cap \overline{T_2}]| \\ & \leq |Pr[Y_{T_1} \in T_1 \cap \overline{T_2}]|= |Pr[Y_{T_1} \in S_{2}^{\prime}]|\\ &= |Pr[Y_{T_1} \in S_{2}^{\prime}]-0|\\ &= |Pr[Y_{T_1} \in S_{2}^{\prime}]-Pr[Y_{T_2} \in S_{2}^{\prime}]|=\frac{q^3-q(q-1)^2}{q^3} \leq \frac{2q-1}{q^2} \leq \frac{2}{q} \end{aligned}$$

    有了这两个不等式，我们现在终于可以讨论$Adv_{\mathcal{A},\mathcal{G}}^{ddh-01}(\cdot)$与$Adv_{\mathcal{A},\mathcal{G}}^{ddh'-01}(\cdot)$这两个优势之间有什么关系了，首先$Expt_{\mathcal{A},\mathcal{G}}^{ddh}(\cdot)$和$Expt_{\mathcal{A},\mathcal{G}}^{ddh'}(\cdot)$这两个实验对$\mathcal{A}$的输入$X,Y,\hat{Z}$要么是$D_1,T_1$，要么是$D_2,T_2$，$D_1,D_2$中的元素我们和前面一样，都记做$X_{D_1},X_{D_2}$，$T_1,T_2$中的元素都记做$Y_{T_1},Y_{T_2}$，则有：

$$\begin{aligned} Adv_{\mathcal{A},\mathcal{G}}^{ddh'-01}(\lambda)&=|Pr[X_{D_2}:\mathcal{A}(1^\lambda, X_{D_2})=1]-Pr[Y_{T_2}:\mathcal{A}(1^\lambda, Y_{T_2})=1]|\\ &=|Pr[X_{D_2}:\mathcal{A}(1^\lambda, X_{D_2})=1]-Pr[X_{D_1}:\mathcal{A}(1^\lambda, X_{D_1})=1]+Pr[X_{D_1}:\mathcal{A}(1^\lambda, X_{D_1})=1]\\ &\quad -Pr[Y_{T_1}:\mathcal{A}(1^\lambda, Y_{T_1})=1]+Pr[Y_{T_1}:\mathcal{A}(1^\lambda, Y_{T_1})=1]-Pr[Y_{T_2}:\mathcal{A}(1^\lambda, Y_{T_2})=1]| \\ &\leq |Pr[X_{D_2}:\mathcal{A}(1^\lambda, X_{D_2})=1]-Pr[X_{D_1}:\mathcal{A}(1^\lambda, X_{D_1})=1]|+|Pr[X_{D_1}:\mathcal{A}(1^\lambda, X_{D_1})=1]\\ &\quad -Pr[Y_{T_1}:\mathcal{A}(1^\lambda, Y_{T_1})=1]|+|Pr[Y_{T_1}:\mathcal{A}(1^\lambda, Y_{T_1})=1]-Pr[Y_{T_2}:\mathcal{A}(1^\lambda, Y_{T_2})=1]| \\ & \color{red}{\leq} \frac{1}{q}+Adv_{\mathcal{A},\mathcal{G}}^{ddh-01}(\lambda)+\frac{2}{q}\\ &=\frac{3}{q}+Adv_{\mathcal{A},\mathcal{G}}^{ddh-01}(\lambda) \end{aligned}$$

为什么标红的$\color{red}{\leq}$是成立的呢？实际上$\mathcal{A}(1^\lambda, X)=1$就是对$X$做出了限制，这个等式实际上就相当于规定了一个概率总体上的子集$M$，再由前面的两个不等式，这个标红的$\color{red}{\leq}$是必然成立的，所以有：

$$Adv_{\mathcal{A},\mathcal{G}}^{ddh'}(\lambda)=\frac{1}{2}Adv_{\mathcal{A},\mathcal{G}}^{ddh'-01}(\lambda) \leq \frac{3}{2q}+\frac{1}{2}Adv_{\mathcal{A},\mathcal{G}}^{ddh-01}(\lambda)=\frac{3}{2q}+Adv_{\mathcal{A},\mathcal{G}}^{ddh}(\lambda)$$

这样就证明了我们非常需要的一个不等式:

$$\color{red}{Adv_{\mathcal{A},\mathcal{G}}^{ddh'}(\lambda) \leq \frac{3}{2q}+Adv_{\mathcal{A},\mathcal{G}}^{ddh}(\lambda) \tag{4}}$$

    因为$Expt_2$与$Expt_3$的具体形式已经给出来了，为了利用上面的不等式，我们可以构造一个区分$D_2,T_2$的$PPT$算法$\mathcal{A}_1$如下:
$\mathcal{A}_1$的构造：输入$1^\lambda$
1，$b\leftarrow {0,1}$，如果$b=1$，则选取$(g_1,g_2,u_1^*,u_2^*) \in D_2$，如果$b=0$，则选取$(g_1,g_2,u_1^*,u_2^*) \in T_2$
2，随机选择$x_1,x_2,y_1,y_2,z_1,z_2 \leftarrow \mathbb{Z}_q^*$，令

$$X:=g_1^{x_1}g_2^{x_2} \quad Y:=g_1^{y_1}g_2^{y_2} \quad Z:=g_1^{z_1}g_2^{z_2} \quad s \leftarrow HGen(1^\lambda)$$

输出公钥$pk=(g_1,g_2,X,Y,Z,T^s(\cdot))$，私钥$sk=(x_1,x_2,y_1,y_2,z_1,z_2)$
3，$\mathcal{A}(pk)$询问时，$\mathcal{A}_1$用密钥$sk$解密回答，然后$\mathcal{A}$输出$(m_0.m_1) \leftarrow \mathcal{A}(1^\lambda ,pk)$
4，随机选取$ \delta \leftarrow {0,1}$，如下计算并输出$(u_1^*,u_2^*,v^*,c^*)$给$\mathcal{A}$

$$c^*:=(u_1^*)^{z_1}(u_2^*)^{z_2} \cdot m_{\delta} \quad \alpha^*:=T^s(u_1^*,u_1^*,c^*) \quad v^*:=(u_1^*)^{x_1+\alpha^* y_1} (u_2^*)^{x_2+\alpha^* y_2}$$

5，$\mathcal{A}(u_1^*,u_2^*,v^*,c^*)$可以解密询问，$\mathcal{A}_1$使用$sk$解密回答
6，算法$\mathcal{A}$输出$\delta’$
7，如果$\delta=\delta’$，则输出1，否则输出0
    这个算法的构造真的是非常巧妙，首先在$CS$加密方案里，$(g_1,g_2,u_1^*,u_2^*)$这个组完全不涉及到密钥，它最多只是涉及到加密时的一些随机数，所以算法$\mathcal{A}_1$完全可以自己生成公钥私钥，然后利用$(g_1,g_2,u_1^*,u_2^*)$这个组回复算法$\mathcal{A}$的解密询问，实际上如果算法$\mathcal{A}$是$PPT$算法，则$\mathcal{A}_1$也必为$PPT$算法。另外这个$\mathcal{A}_1$也和$Expt_2$与$Expt_3$产生了联系，实际上如果$b=1$，那$\mathcal{A}_1$和$Expt_2$就是一模一样的，如果$b=0$，那$\mathcal{A}_1$和$Expt_3$就是一模一样，的非常直观的可以看到：

$$Pr[Expt_2 \quad success]=Pr[\mathcal{A}_1^{b=1}(1^\lambda)=1 ] \\ Pr[Expt_3 \quad success]=Pr[\mathcal{A}_1^{b=0}(1^\lambda)=1 ]$$

所以有：

$$\begin{aligned} |Pr[Expt_2 \quad success]-Pr[Expt_3 \quad success]|&=|Pr[\mathcal{A}_1^{b=1}(1^\lambda)=1 ]-Pr[\mathcal{A}_1^{b=0}(1^\lambda)=1 ]|\\ &=2Adv_{\mathcal{A}_1,\mathcal{G}}^{ddh'}(\lambda)\\ &\leq 2(\frac{3}{2q}+Adv_{\mathcal{A}_1,\mathcal{G}}^{ddh}(\lambda))\\ &=\frac{3}{q}+2Adv_{\mathcal{A}_1,\mathcal{G}}^{ddh}(\lambda) \end{aligned}$$

由此我们终于证明了$Expt_2$与$Expt_3$之间的概率关系：、

$$\color{red}{|Pr[Expt_2 \quad success]-Pr[Expt_3 \quad success]| \leq \frac{3}{q}+2Adv_{\mathcal{A}_1,\mathcal{G}}^{ddh}(\lambda) \tag{5}}$$

非常的不容易。

$Expt_3$与$Expt_4$

    接下来再看$Expt_3$与$Expt_4$，具体结构如下：

$$Exp_3: input 1^\lambda\\ pk,sk \leftarrow CS \quad scheme\\ pk=(g_1,g_2,X,Y,Z,T^s(\cdot))\\ sk=(x_1,x_2,y_1,y_2,z_1,z_2)\\ \mathcal{A}(pk)\quad ask \quad Dec_{sk}(\cdot)\\ (m_0.m_1) \leftarrow \mathcal{A}(1^\lambda ,pk)\\ r_1^*,r_2^* \leftarrow \mathbb{Z}_q,r_1^* \neq r_2^*\\ u_1^*=g_1^{r_1^*}, u_2^*=g_2^{r_2^*}\\ \delta \leftarrow \{0,1\}, c^*:=(u_1^*)^{z_1}(u_2^*)^{z_2} \cdot m_{\delta}\\ \alpha^*:=T^s(u_1^*,u_2^*,c^*)\\ v^*:=(u_1^*)^{x_1+\alpha^* y_1} (u_2^*)^{x_2+\alpha^* y_2}\\ \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\quad ask \quad Dec_{sk}^*(\cdot)\\ \delta' \leftarrow \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\\ if \delta'=\delta \quad output \quad 1 \quad else \quad 0$$

$$Exp_4: input 1^\lambda\\ pk,sk \leftarrow CS \quad scheme\\ pk=(g_1,g_2,X,Y,Z,T^s(\cdot))\\ sk=(x_1,x_2,y_1,y_2,z_1,z_2)\\ \mathcal{A}(pk)\quad ask \quad \color{red}{\overline{Dec_{sk}(\cdot)}}\\ (m_0.m_1) \leftarrow \mathcal{A}(1^\lambda ,pk)\\ r_1^*,r_2^* \leftarrow \mathbb{Z}_q,r_1^* \neq r_2^*\\ u_1^*=g_1^{r_1^*}, u_2^*=g_2^{r_2^*}\\ \delta \leftarrow \{0,1\}, c^*:=(u_1^*)^{z_1}(u_2^*)^{z_2} \cdot m_{\delta}\\ \alpha^*:=T^s(u_1^*,u_2^*,c^*)\\ v^*:=(u_1^*)^{x_1+\alpha^* y_1} (u_2^*)^{x_2+\alpha^* y_2}\\ \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\quad ask \quad \color{red}{\overline{Dec_{sk}^*(\cdot)}}\\ \delta' \leftarrow \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\\ if \delta'=\delta \quad output \quad 1 \quad else \quad 0$$

    $Expt_4$与$Expt_3$不同的地方在于$Expt_4$的解密检验步骤更加丰富，要求更多，每当有解密询问$(u_1,u_2,v,c)$时，则对$\alpha =T^s(u_1,u_2,c)$做如下检查：若有$u_2=u_1^a \land v=u_1^{x+\alpha}$，则输出$c(u_1^z)^{-1}$，否则输出$\perp$，其中

$$g_2=g_1^a \quad x:=x_1+ax_2 \quad y:=y_1+ay_2 \quad z:=z_1+az_2$$

通过简单的计算之后可以发现，这里的检验和$Expt_3$中的检验仅仅是多了一个$u_2=u_1^a$，实际上这也是比较稳妥的，对于攻击者，$(u_1,u_2,v,c)$它都可以进行修改，也许会有某一组$(u_1,u_2,v,c)$使得通过$Expt_3$的验证且$u_2\neq u_1^a$，这种可能性不是没有。
    由此我们定义事件$E_4$，表示敌手询问了能被$Expt_3$中应答器回答但$Expt_4$中应答器拒绝的密文。可以发现，如果事件$E_4$不出现，那实验$Expt_4$与$Expt_3$是完全相同的实验，所以根据概率差引理有：

$$\color{red}{|Pr[Expt_3 \quad success]-Pr[Expt_4 \quad success]| \leq Pr[E_4 ] \tag{6}}$$

$Expt_4$与$Expt_5$

    接下来再看$Expt_4$与$Expt_5$，具体结构如下：

$$Exp_4: input 1^\lambda\\ pk,sk \leftarrow CS \quad scheme\\ pk=(g_1,g_2,X,Y,Z,T^s(\cdot))\\ sk=(x_1,x_2,y_1,y_2,z_1,z_2)\\ \mathcal{A}(pk)\quad ask \quad \overline{Dec_{sk}(\cdot)}\\ (m_0.m_1) \leftarrow \mathcal{A}(1^\lambda ,pk)\\ r_1^*,r_2^* \leftarrow \mathbb{Z}_q,r_1^* \neq r_2^*\\ u_1^*=g_1^{r_1^*}, u_2^*=g_2^{r_2^*}\\ \delta \leftarrow \{0,1\}, c^*:=(u_1^*)^{z_1}(u_2^*)^{z_2} \cdot m_{\delta}\\ \alpha^*:=T^s(u_1^*,u_2^*,c^*)\\ v^*:=(u_1^*)^{x_1+\alpha^* y_1} (u_2^*)^{x_2+\alpha^* y_2}\\ \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\quad ask \quad \overline{Dec_{sk}^*(\cdot)}\\ \delta' \leftarrow \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\\ if \delta'=\delta \quad output \quad 1 \quad else \quad 0$$

$$Exp_5: input 1^\lambda\\ pk,sk \leftarrow CS \quad scheme\\ pk=(g_1,g_2,X,Y,Z,T^s(\cdot))\\ sk=(x_1,x_2,y_1,y_2,z_1,z_2)\\ \mathcal{A}(pk)\quad ask \quad \overline{Dec_{sk}(\cdot)}\\ (m_0.m_1) \leftarrow \mathcal{A}(1^\lambda ,pk)\\ r_1^*,r_2^* \leftarrow \mathbb{Z}_q,r_1^* \neq r_2^*\\ u_1^*=g_1^{r_1^*}, u_2^*=g_2^{r_2^*}\\ \delta \leftarrow \{0,1\}\\ \color{red}{c^* \leftarrow \mathbb{G}} ,\alpha^*:=T^s(u_1^*,u_2^*,c^*)\\ v^*:=(u_1^*)^{x_1+\alpha^* y_1} (u_2^*)^{x_2+\alpha^* y_2}\\ \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\quad ask \quad \overline{Dec_{sk}^*(\cdot)}\\ \delta' \leftarrow \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\\ if \delta'=\delta \quad output \quad 1 \quad else \quad 0$$

    它们的区别非常显然$Expt_4$中的挑战密文是$c^*:=(u_1^*)^{z_1}(u_2^*)^{z_2} \cdot m_{\delta}$，但$Expt_5$中的挑战密文是$c^* \leftarrow \mathbb{G}$，我们接下来就要考虑这两个实验成功概率之间的关系。由于$c^*$永远是群$\mathbb{G}$的一个元素，必然有$r=log_{g_1}c^*$，根据$c^*:=(u_1^*)^{z_1}(u_2^*)^{z_2} \cdot m_{\delta}$可以得到：

$$r=r^*z_1+ar_2^*z_2+log_{g_1}m_{\delta}$$

根据$z=z_1+az_2$可知，有如下关系：

$$\left(\begin{array}{l} z \\ r \end{array}\right)=\left(\begin{array}{cc} 1 & a \\ r_1^* & a r_2^* \end{array}\right) \cdot\left(\begin{array}{l} z_1 \\ z_2 \end{array}\right)+\left(\begin{array}{c} 0 \\ \log _{g_1} m_\delta \end{array}\right)$$

另外$Expt_4$和$Expt_5$中解密应答器的解密过程中，密文为$(u_1,u_2,v,c)$，如果我们不考虑验证过程，解密过程为$c/u_1^z$，显然仅仅使用了$z=z_1+az_2$这个密钥，我们现在考虑$r$和$z_1,z_2$的关系，在上面那个矩阵等式里，在计算$c^*$，也就是计算$r$时，$z,a,r_1^*,r_2^*,\delta$都是已经确定好的量，而且那个二阶矩阵还显然是可逆的，所以一个$r$就与一个$z_1,z_2$唯一对应。

    但$z_1,z_2$是怎么确定的？实际上，即使敌手知道$z$的值，敌手也不会有任何优势地知道$z_1,z_2$是多少，就像敌手拿到一个数100，那敌手就不会有任何优势去判断我给100的加法分解是什么，因为关于这些我完全没有和敌手交互，另外由于$a \in \mathbb{Z}_q^*$，那$z_1,z_2$就一共有$q$对，且每一个都是等概率出现，则对应的$r$也是有$q$个，每一个的概率都是相等的。
    所以我们实际上发现$Expt_4$和$Expt_5$中的挑战密文$c^*$都是随机的，那$Expt_4$和$Expt_5$里这些需要挑选的随机变量都是同分布的，那$Expt_4$和$Expt_5$就完全是相同的实验，如果我们假设事件$E_5$是敌手询问了被$Expt_3$中应答器回答但被$Expt_5$中应答器拒绝的密文，则必有：

$$\color{red}{Pr[Expt_4 \quad success]=Pr[Expt_5 \quad success] \tag{7}}$$ $$\color{red}{Pr[E_4]=Pr[E_5] \tag{8}}$$

因为$Expt_5$中的$c^*$完全是随机选取的，所以$c^*$中不含$m_{\delta}$的信息，所以有：

$$\color{red}{Pr[Expt_5 \quad success] =\frac{1}{2} }$$

$Expt_5$与$Expt_6$

    接下来再看$Expt_5$与$Expt_6$，具体结构如下：

$$Exp_5: input 1^\lambda\\ pk,sk \leftarrow CS \quad scheme\\ pk=(g_1,g_2,X,Y,Z,T^s(\cdot))\\ sk=(x_1,x_2,y_1,y_2,z_1,z_2)\\ \mathcal{A}(pk)\quad ask \quad \overline{Dec_{sk}(\cdot)}\\ (m_0.m_1) \leftarrow \mathcal{A}(1^\lambda ,pk)\\ r_1^*,r_2^* \leftarrow \mathbb{Z}_q,r_1^* \neq r_2^*\\ u_1^*=g_1^{r_1^*}, u_2^*=g_2^{r_2^*}\\ \delta \leftarrow \{0,1\}\\ c^* \leftarrow \mathbb{G} ,\alpha^*:=T^s(u_1^*,u_2^*,c^*)\\ v^*:=(u_1^*)^{x_1+\alpha^* y_1} (u_2^*)^{x_2+\alpha^* y_2}\\ \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\quad ask \quad \overline{Dec_{sk}^*(\cdot)}\\ \delta' \leftarrow \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\\ if \delta'=\delta \quad output \quad 1 \quad else \quad 0$$

$$Exp_6: input 1^\lambda\\ pk,sk \leftarrow CS \quad scheme\\ pk=(g_1,g_2,X,Y,Z,T^s(\cdot))\\ sk=(x_1,x_2,y_1,y_2,z_1,z_2)\\ \mathcal{A}(pk)\quad ask \quad \overline{Dec_{sk}(\cdot)}\\ (m_0.m_1) \leftarrow \mathcal{A}(1^\lambda ,pk)\\ r_1^*,r_2^* \leftarrow \mathbb{Z}_q,r_1^* \neq r_2^*\\ u_1^*=g_1^{r_1^*}, u_2^*=g_2^{r_2^*}\\ \delta \leftarrow \{0,1\}\\ c^* \leftarrow \mathbb{G} ,\alpha^*:=T^s(u_1^*,u_2^*,c^*)\\ v^*:=(u_1^*)^{x_1+\alpha^* y_1} (u_2^*)^{x_2+\alpha^* y_2}\\ \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\quad ask \quad \color{red}{\widehat{Dec_{sk}^*(\cdot)}}\\ \delta' \leftarrow \mathcal{A}(pk,u_1^*,u_1^*,v^*,c^*)\\ if \delta'=\delta \quad output \quad 1 \quad else \quad 0$$

    $Expt_6$中猜测阶段的应答器与$Expt_5$中猜测阶段的应答器存在一些区别，如果敌手询问的密文$(u_1,u_2,v,c)$满足$(u_1,u_2,c) \neq (u_1^*,u_2^*,c^*)$但是$\alpha=\alpha^*$，则回答$\perp$并停机，否则一切和$Expt_5$中猜测阶段的应答器完全一样。

    这里需要定义两个事件，一个事件$E_6$：敌手询问了被$Expt_3$中应答器回答但被$Expt_6$中应答器拒绝的密文，另外一个事件$F_6$：新的应答器$\color{red}{\widehat{Dec_{sk}^*(\cdot)}}$使用上述新的规则拒绝了一个密文。显然的是如果$F_6$不发生，就是说这个新设的限制完全没用，那$Expt_5$与$Expt_6$完全一样，则事件$E_6$和事件$E_5$也是一样的，因为他们所依赖的实验基础都是相同的，即$E_5\land \neg F_6=E_6 \land \neg F_6$，根据概率差引理有：

$$\color{red}{|Pr[E_5]-Pr[E_6]| \leq Pr[F_6] \tag{9}}$$

    我们接下来要去考虑$Pr[F_6]$的大小，$F_6$这个事件与碰撞有关，我们利用$\mathcal{A}$构建一个对于$HASH$寻找第二原像攻击的敌手$\mathcal{A}_2$：
$\mathcal{A}_2$的构造：输入$s,(u_1^*,u_2^*,c^*)$
1，随机选择$x_1,x_2,y_1,y_2,z_1,z_2 \leftarrow \mathbb{Z}_q^*$，令

$$X:=g_1^{x_1}g_2^{x_2} \quad Y:=g_1^{y_1}g_2^{y_2} \quad Z:=g_1^{z_1}g_2^{z_2}$$

输出公钥$pk=(g_1,g_2,X,Y,Z,T^s(\cdot))$，私钥$sk=(x_1,x_2,y_1,y_2,z_1,z_2)$
2，$\mathcal{A}(pk)$询问$\overline{Dec_{sk}(\cdot)}$时，$\mathcal{A}_2$用密钥$sk$解密回答，然后$\mathcal{A}$输出$(m_0.m_1) \leftarrow \mathcal{A}(1^\lambda ,pk)$
3，$\mathcal{A}_2$如下计算挑战密文$(u_1^*,u_2^*,v^*,c^*)$给$\mathcal{A}$

$$c^* \leftarrow \mathbb{G} \quad \alpha^*:=T^s(u_1^*,u_2^*,c^*) \quad v^*:=(u_1^*)^{x_1+\alpha^* y_1} (u_2^*)^{x_2+\alpha^* y_2}$$

4，$\mathcal{A}(u_1^*,u_2^*,v^*,c^*)$可以询问$\color{red}{\widehat{Dec_{sk}^*(\cdot)}}$，如果敌手询问某个密文$(u_1,u_2,v,c)$满足

$$T^s(u_1,u_2,c)=\alpha^* \quad (u_1,u_2,c) \neq (u_1^*,u_2^*,c^*)$$

则回答$perp$并输出$(u_1,u_2,c)$，停机

    分析上述实验的成功优势我们有如下等式：

$$\begin{aligned} Adv_{\mathcal{A}_2,HASH}^{crt}&=Pr[\mathcal{A}_2 success]\\ &=Pr[log_{g_1}u_1^* \neq log_{g_2}u_2^*]Pr[\mathcal{A}_2 success|log_{g_1}u_1^* \neq log_{g_2}u_2^*]\\ &\quad +Pr[log_{g_1}u_1^* = log_{g_2}u_2^*]Pr[\mathcal{A}_2 success|log_{g_1}u_1^* = log_{g_2}u_2^*] \\ &\color{red}{=}Pr[log_{g_1}u_1^* = log_{g_2}u_2^*]Pr[\mathcal{A}_2 success|log_{g_1}u_1^* = log_{g_2}u_2^*]+Pr[log_{g_1}u_1^* \neq log_{g_2}u_2^*]Pr[F_6] \end{aligned}$$

为什么最后一个标红的等号成立？实际上因为$\mathcal{A}_2$这个算法完全就是套在$Expt_6$这个壳子里运行的，如果$log_{g_1}u_1^* \neq log_{g_2}u_2^*$，则此时的$\mathcal{A}_2$与$Expt_6$根本就没区别，当然若此时$\mathcal{A}_2$成功，就等价于事件$F_6$出现，所以上面标红的等号必然成立。

    因为$(u_1^*,u_2^*,c^*)$这个组显然只有$q^3$个，所以有：

$$Pr[log_{g_1}u_1^* = log_{g_2}u_2^*] =\frac{q^2}{q^3}=\frac{1}{q}\\ Pr[log_{g_1}u_1^* \neq log_{g_2}u_2^*] =1-\frac{1}{q}\\ Adv_{\mathcal{A}_2,HASH}^{crt}=\frac{1}{q}Pr[\mathcal{A}_2 success|log_{g_1}u_1^* = log_{g_2}u_2^*]+(1-\frac{1}{q})Pr[F_6]$$

所以有

$$\begin{aligned} Pr[F_6]&=\frac{Adv_{\mathcal{A}_2,HASH}^{crt}-\frac{1}{q}Pr[\mathcal{A}_2 success|log_{g_1}u_1^* = log_{g_2}u_2^*]}{1-\frac{1}{q}}\\ &=\frac{q}{q-1}Adv_{\mathcal{A}_2,HASH}^{crt}-\frac{1}{q-1}Pr[\mathcal{A}_2 success|log_{g_1}u_1^* = log_{g_2}u_2^*]\\ &\leq \frac{q}{q-1}Adv_{\mathcal{A}_2,HASH}^{crt}\\ & \leq 2Adv_{\mathcal{A}_2,HASH}^{crt} \end{aligned}$$

由此我们证明了：

$$\color{red}{Pr[F_6] \leq 2Adv_{\mathcal{A}_2,HASH}^{tcr} \tag{10}}$$

    接下来就剩了最后一个概率不等式没有解决，由于篇幅的原因，此概率不等式放到另外的博文里解决，其具体形式如下：

$$\color{red}{Pr[E_6] \leq \frac{Q}{q} \tag{11}}$$

其中$Q$表示敌手$\mathcal{A}$询问应答器的次数，当然为多项式次。

总结

    到现在就可以总结公式了，真的非常不容易，公式有：

$$\color{red}{Adv_{\mathcal{A},CS}^{cca}(\lambda)=|Pr[Expt_1 \quad success]-\frac{1}{2}| }\\ \color{red}{Pr[Expt_1 \quad success]=Pr[Expt_2 \quad success] }\\ \color{red}{|Pr[Expt_2 \quad success]-Pr[Expt_3 \quad success]| \leq \frac{3}{q}+2Adv_{\mathcal{A}_1,\mathcal{G}}^{ddh}(\lambda)}\\ \color{red}{|Pr[Expt_3 \quad success]-Pr[Expt_4 \quad success]| \leq Pr[E_4 ] }\\ \color{red}{Pr[Expt_4 \quad success]=Pr[Expt_5 \quad success] }\\ \color{red}{Pr[E_4]=Pr[E_5] }\\ \color{red}{Pr[Expt_5 \quad success] =\frac{1}{2} }\\ \color{red}{|Pr[E_5]-Pr[E_6]| \leq Pr[F_6] }\\ \color{red}{Pr[F_6] \leq 2Adv_{\mathcal{A}_2,HASH}^{tcr} }\\ \color{red}{Pr[E_6] \leq \frac{Q}{q} }$$

下面的公式推导里，为了简便形式，将$Pr[Expt_i \quad success]$记为$Pr[E_i s]$，由此我们得到了：

$$\begin{aligned} Adv_{\mathcal{A},CS}^{cca}(\lambda)&=|Pr[E_1 s]-\frac{1}{2}|=|Pr[E_2 s]-\frac{1}{2}| \\ &=|Pr[E_2 s]-Pr[E_3 s]+Pr[E_3 s]-Pr[E_4 s]+Pr[E_4 s]-\frac{1}{2}| \\ & \leq |Pr[E_2 s]-Pr[E_3 s]|+|Pr[E_3 s]-Pr[E_4 s]|+|Pr[E_4 s]-\frac{1}{2}| \\ & \leq \frac{3}{q}+2Adv_{\mathcal{A}_1,\mathcal{G} }^{ddh}(\lambda)+Pr[E_4 ] \\ &=\frac{3}{q}+2Adv_{\mathcal{A}_1,\mathcal{G}}^{ddh}(\lambda)+Pr[E_5 ]\\ &=\frac{3}{q}+2Adv_{\mathcal{A}_1,\mathcal{G}}^{ddh}(\lambda)+|Pr[E_5 ]-Pr[E_6 ]+Pr[E_6 ]| \\ &\leq \frac{3}{q}+2Adv_{\mathcal{A}_1,\mathcal{G}}^{ddh}(\lambda)+|Pr[E_5 ]-Pr[E_6 ]|+Pr[E_6 ] \\ &\leq \frac{3}{q}+2Adv_{\mathcal{A}_1,\mathcal{G}}^{ddh}(\lambda)+Pr[ F_6]+\frac{Q}{q} \\ &\leq 2Adv_{\mathcal{A}_1,\mathcal{G}}^{ddh}(\lambda)+2Adv_{\mathcal{A}_2,HASH}^{tcr}+\frac{3+Q}{q} \end{aligned}$$

也就证明了最终的结论，分辨的优势是可忽略的。

再次总结

    真的好繁琐，好在是弄完了，部分证明和老师讲的有出入，但我觉得应该是对的，问题不大。