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$。

    之前的博文未解决的一个命题就是

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

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

$E_5$：敌手询问了被$Expt_3$中应答器回答但被$Expt_5$中应答器拒绝的密文 $E_6$：敌手询问了被$Expt_3$中应答器回答但被$Expt_6$中应答器拒绝的密文

讲义中的证明存在疑问

    首先给出实验的具体情况，即$Expt_3$，$Expt_5$，$Expt_6$的详细对比，这里$Expt_3$永远是最基础的实验，$Expt_5$，$Expt_6$均是在$Expt_3$基础上添加新的验证得来的。

$$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_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 \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\}\\ \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 \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_3$与$Expt_5$的区别是$Expt_5$两个阶段的解密应答器都多了一个条件，若$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$而已。

    我们要研究$E_6$这个事件，首先来看$Expt_3$与$Expt_6$的对比

$$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_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 \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^* \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$，结合$Expt_5$可知$Expt_3$与$Expt_6$的区别有两个，一是$Expt_6$的两个阶段的解密应答器都要验证$u_2=u_1^a$，不满足就直接输出$\perp$；二是$Expt_6$的第二阶段的解密应答器还要求若有敌手询问的密文$(u_1,u_2,v,c)$满足$(u_1,u_2,c) \neq (u_1^*,u_2^*,c^*)$但是$\alpha=\alpha^*$，则直接回答$\perp$并停机，故第一阶段多了一个规则，第二阶段多了两个规则。

    $Expt_3$与$Expt_6$就这两点区别， 但讲义里说$E_6$发生一定有$u_2 \neq u_1^a$且$v=u_{1}^{x_{1}+\alpha y_{1}} u_{2}^{x_{2}+\alpha y_{2}}$，这个我认为并不正确。首先$E_6$发生，则敌手构造的密文必通过$Expt_3$的验证，通不过$Expt_6$的验证，既然通过$Expt_3$的验证，则只需$v=u_{1}^{x_{1}+\alpha y_{1}} u_{2}^{x_{2}+\alpha y_{2}}$即可，$u_2$是否等于$u_1^a$对$Expt_3$来说是无所谓的，因为它只验证$v$；既然通不过$Expt_6$的验证，可以分别在第一阶段与第二阶段考虑，若在$Expt_6$的第一阶段无法通过验证，必有$u_2 \neq u_1^a$，可以发现此时敌手构造的密文满足$u_2 \neq u_1^a$且$v=u_{1}^{x_{1}+\alpha y_{1}} u_{2}^{x_{2}+\alpha y_{2}}$，此时讲义的断言就是正确的。

    但若敌手构造的密文在$Expt_6$的第二阶段无法通过验证，第二阶段是有两个规则的，如果$u_2 \neq u_1^a$，输出$\perp$；如果$(u_1,u_2,c) \neq (u_1^*,u_2^*,c^*)$但是$\alpha=\alpha^*$输出$\perp$。这两个规则只要满足一个就输出$\perp$，如果满足的是第二个，一定有$u_2 \neq u_1^a$吗？我觉得是不一定的，比如令$u_1=u_1^*$，$u_2=u_2^*$，$c\neq c^*$，此时必有$u_2 = u_1^a$，但此时只要控制$c\neq c^*$使得摘要函数$T^s$出现碰撞

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

即可使得敌手构造的密文满足第二个规则，应答器输出$\perp$，事件$E_6$发生，但此时$u_2 = u_1^a$。

    注意这里的碰撞，我们不关注于怎么找到具体的$\alpha$，我们只关注于这种碰撞出现的可能性，这种可能性现在当然不为0，也就是说有可能出现，那就足够了，所以我觉得讲义里说 $E_6$发生一定有$u_2 \neq u_1^a$且$v=u_{1}^{x_{1}+\alpha y_{1}} u_{2}^{x_{2}+\alpha y_{2}}$是存在疑问的。

个人感觉较为合理的证明

    这里给出一个我认为比较合理的证明，首先原命题是要证明$\color{red}{Pr[E_6] \leq \frac{Q}{q}}$，即事件$E_6$发生的概率是可忽略的，有了这个可忽略就可以利用其它一些命题证明Cramer-Shoup方案是CCA安全的，推导如下

$$\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}$$

但实际上，仔细观察这个推导过程，如果我们能够证明事件$E_5$发生的概率是可忽略的，就可以达到和事件$E_6$发生概率可忽略一样的效果，一样可以证明Cramer-Shoup方案是CCA安全的，所以这里我们转向推导事件$E_5$发生的概率是可忽略的，但实际上这个推导过程里依旧要用到事件$F_6$，其定义为

$F_6$：应答器$\color{red}{\widehat{Dec_{sk}^*(\cdot)}}$使用规则"$(u_1,u_2,c) \neq (u_1^*,u_2^*,c^*)$但是$\alpha=\alpha^*$，则回答$\perp$并停机"拒绝了一个密文

但由于$Expt_5$第二阶段的应答器并不是$\color{red}{\widehat{Dec_{sk}^*(\cdot)}}$，故需要对$F_6$做一些修改，具体如下

$F_6$：$Expt_5$第二阶段的敌手询问了某个密文$(u_1,u_2,v,c)$满足"$(u_1,u_2,c) \neq (u_1^*,u_2^*,c^*)$但是$\alpha=\alpha^*$"

实际上这个$F_6$发生的概率也是可忽略的，证明方法与原来的证明一模一样，只需要将构造的寻找第二原像的敌手中的$Expt_6$换成$Expt_5$即可。

    首先对事件$E_5$发生的概率进行分析

$E_5$：敌手询问了被$Expt_3$中应答器回答但被$Expt_5$中应答器拒绝的密文

$$Pr[E_5]=Pr[F_6]Pr[E_5|F_6]+Pr[\neg F_6]Pr[E_5|\neg F_6]\leq Pr[F_6]+Pr[E_5|\neg F_6]$$

首先$F_6$发生的概率是可忽略的，故只要证明$Pr[E_5|\neg F_6]$是可忽略的即可，实际上这也是后面的主要工作。

    $Expt_5$的解密应答器拒绝解密有两种情况，一是在第一阶段不满足某个规则而拒绝，二是在第二阶段不满足某个规则而拒绝，只要我们能证明在$\neg F_6$的条件下无论是第一阶段还是第二阶段拒绝的概率都是可忽略的即可。

第一阶段

    首先来看第一阶段，注意$F_6$是对第二阶段的应答器做出的限制，所以$\neg F_6$对第一阶段完全没有影响，故此时的$E_5$出现意味着敌手提供的密文$(u_1,u_2,v,c)$满足$u_2 \neq u_1^a$且$v=u_{1}^{x_{1}+\alpha y_{1}} u_{2}^{x_{2}+\alpha y_{2}}$，分别用指数形式表示有

$$r_1:=\log _{g_1} u_1, \quad r_2:=\log _{g_2} u_2, \quad \alpha:=T^s\left(u_1, u_2, c\right), \quad \beta:=\log _{g_1} v$$ $$\gamma:=x_1 r_1+\alpha r_1 y_1+a r_2 x_2+a \alpha r_2 y_2$$

则$u_2 \neq u_1^a$等价于$r_1 \neq r_2$，$v=u_{1}^{x_{1}+\alpha y_{1}} u_{2}^{x_{2}+\alpha y_{2}}$等价于$\gamma = \beta$。注意$(u_1,u_2,v,c)$是敌手构造的密文，所以$u_2 \neq u_1^a$是完全可能的，则此时有

$$\begin{aligned} Pr[E_5|\neg F_6]=Pr[E_5] &\leq Pr[u_2 \neq u_1^a \land v=u_{1}^{x_{1}+\alpha y_{1}} u_{2}^{x_{2}+\alpha y_{2}}] \\ &=Pr[r_1 \neq r_2 \land \gamma = \beta]\\ &=Pr[r_1 \neq r_2 ]Pr[\gamma = \beta|r_1 \neq r_2]\\ &\leq Pr[\gamma = \beta|r_1 \neq r_2] \end{aligned}$$

    接下来就要考虑$r_1 \neq r_2$的情况下，$\gamma = \beta$的概率，首先对$\gamma = \beta$的意义做一下分析，$\gamma = \beta$等价于$v=u_{1}^{x_{1}+\alpha y_{1}} u_{2}^{x_{2}+\alpha y_{2}}$，实际上对于敌手而言，如果敌手使用标准的加密生成$(u_1,u_2,v,c)$，则$v=u_{1}^{x_{1}+\alpha y_{1}} u_{2}^{x_{2}+\alpha y_{2}}$是显然成立的，但注意这里要求$r_1 \neq r_2$，也就是$u_2 \neq u_1^a$，这与标准的加密是相背离的，所以就相当于敌手在规则之外构造了一个密文，然后交给解密应答器，解密应答器再验证$v$等不等于$u_{1}^{x_{1}+\alpha y_{1}} u_{2}^{x_{2}+\alpha y_{2}}$，也就是$\gamma$是不是等于$\beta$，那这是就不一定成功了，这里$\beta$可以理解为敌手生成的，$\gamma$是解密应答器根据私钥生成的。

    下面考虑$x_1,x_2,y_1,y_2$与$\gamma$的关系，可以得到如下线性方程组

$$\left(\begin{array}{l} x \\ y \\ \gamma \end{array}\right)=\left(\begin{array}{cccc} 1 & a & 0 & 0 \\ 0 & 0 & 1 & a \\ r_1 & a r_2 & \alpha r_1 & a \alpha r_2 \end{array}\right) \left(\begin{array}{l} x_1 \\ x_2 \\ y_1 \\ y_2 \end{array}\right)$$

注意$r_1 \neq r_2$，$a\neq 0$，故此方程系数矩阵的秩一定为3，可对其进行初等行变换得到如下结果

$$\left(\begin{array}{l} x \\ y \\ \gamma-r_1x-r_1y \end{array}\right)=\left(\begin{array}{cccc} 1 & a & 0 & 0 \\ 0 & 0 & 1 & a \\ 0 & a(r_2-r_1)& 0 & a\alpha (r_2-r_1) \end{array}\right) \left(\begin{array}{l} x_1 \\ x_2 \\ y_1 \\ y_2 \end{array}\right)$$

上面方程中的$r_1,r_2$是敌手给的，$\alpha$也相当于是敌手给的，至于$a$，解密应答器在生成公私钥对时可以将$a$固定，故一旦敌手给出密文，上述方程的系数矩阵就是确定的，另外对一个解密应答器而言，一旦公钥确定，那么$x=x_1+ax_2,y=y_1+ay_2$就是确定的，但即便如此，我们也可以合理假设$x_2,y_2$是$\mathbb{Z}_q$中的随机元素。

    在这样的情况下，考虑上述方程组的第三个等式

$$\gamma-r_1x-r_1y=a(r_2-r_1)x_2+a\alpha (r_2-r_1)y_2$$ $$\gamma=r_1x+r_1y+a(r_2-r_1)x_2+a\alpha (r_2-r_1)y_2$$

显然在敌手给出密文后，上面的式子只有$x_2,y_2$是$\mathbb{Z}_q$中的随机元素，其余都是确定的值，故对任一个$\gamma \in \mathbb{Z}_q$，可以固定$y_2$的值，由于$a\neq 0$，$r_1\neq r_2$，故一定存在唯一的一个$x_2 \in \mathbb{Z}_q$使得上式成立，故$x_2,y_2$随机取时，$\gamma$也一定随机选取，故在这样的情况下，$\gamma$等于$\beta$这个定值的概率就是$\frac{1}{q}$，显然为可忽略的。

第二阶段

    再来看第二阶段，第二阶段敌手得到了挑战密文$(u_1^*,u_2^*,v^*,c^*)$，下设

$$r_{1}^{*}:=\log _{g_{1}} u_{1}^{*}, \quad r_{2}^{*}:=\log _{g_{2}} u_{2}^{*}, \quad \beta^{*}:=\log _{g_{1}} v^{*}, \quad r^{*}:=\log _{g_{1}} c^{*}$$

然后敌手以密文$(u_1,u_2,v,c)$向第二阶段的解密应答器进行询问，实际敌手此时给出的$u_1,u_2,c$必满足

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

这是非常显然的，分析如下

1，若$\alpha=\alpha^*$且$(u_1,u_2,c)=(u_1^*,u_2^*,c^*)$成立，则由$v^*$计算的形式$v=u_{1}^{x_{1}+\alpha y_{1}} u_{2}^{x_{2}+\alpha y_{2}}=(u_1^*)^{x_{1}+\alpha^* y_{1}} (u_2^*)^{x_{2}+\alpha^* y_{2}}=v^*$，则$(u_1,u_2,v,c)=(u_1^*,u_2^*,v^*,c^*)$，此时$Expt_3$不可能验证通过，故此事件不可能出现。

2，若$\alpha=\alpha^*$且$(u_1,u_2,c)\neq (u_1^*,u_2^*,c^*)$成立，非常显然这就是事件$F_6$发生，但前面已经提过，我们的分析都是在$\neg F_6$条件下的，所以这种情况不会出现。

    所以可以认为$\alpha \neq \alpha^*$，则有下面方程组成立

$$\left(\begin{array}{c} x \\ y \\ \beta^{*} \\ \gamma \end{array}\right)=\left(\begin{array}{cccc} 1 & a & 0 & 0 \\ 0 & 0 & 1 & a \\ r_{1}^{*} & a r_{2}^{*} & \alpha^{*} r_{1}^{*} & a \alpha^{*} r_{2}^{*} \\ r_{1} & a r_{2} & \alpha r_{1} & a \alpha r_{2} \end{array}\right) \cdot\left(\begin{array}{c} x_{1} \\ x_{2} \\ y_{1} \\ y_{2} \end{array}\right)$$

当敌手得到挑战密文后，$a,r_1^*,r_2^*,r^*,\alpha^*$也就确定了，当敌手以$(u_1,u_2,v,c)$询问解密应答器时，$r_1,r_2$也就确定了，故此时系数矩阵完全确定，矩阵的行列式为

$$\operatorname{det}(M)=a^{2}\left(r_{2}-r_{1}\right)\left(r_{2}^{*}-r_{1}^{*}\right)\left(\alpha^{*}-\alpha\right) \neq 0$$

显然系数矩阵是可逆矩阵，则设$s=-a(r_2-r_1)[a(r_2^*-r_1^*)]^{-1},t=(\alpha r_{1} +\alpha^{*}r_1^{*}s)y$，对上述方程组进行初等行变换可得

$$\left(\begin{array}{c} x \\ y \\ \beta^{*}-r_1^* x \\ \gamma-r_1 x+s(\beta^{*}-r_1^* x)-t \end{array}\right)=\left(\begin{array}{cccc} 1 & a & 0 & 0 \\ 0 & 0 & 1 & a \\ 0 & a (r_{2}^{*}-r_1^{*}) & \alpha^{*} r_{1}^{*} & a \alpha^{*} r_{2}^{*} \\ 0 & 0 & 0 & -a(\alpha r_{1} +\alpha^{*}r_1^{*}s)+a \alpha r_{2}+sa\alpha^*r_{2}^{*} \end{array}\right) \cdot\left(\begin{array}{c} x_{1} \\ x_{2} \\ y_{1} \\ y_{2} \end{array}\right)$$

    考虑第四个等式，则有

$$\gamma=-s(\beta^{*}-r_1^* x)+r_1 x+t+y_{2}(-a(\alpha r_{1} +\alpha^{*}r_1^{*}s)+a \alpha r_{2}+sa\alpha^*r_{2}^{*})$$

非常显然的是上式$y_2$的系数$-a(\alpha r_{1} +\alpha^{*}r_1^{*}s)+a \alpha r_{2}+sa\alpha^*r_{2}^{*}$必不为0，否则根据上面化简的矩阵可知，此矩阵不可逆，与原矩阵可逆矛盾。接下来的分析就与阶段一的分析类似，当敌手以$(u_1,u_2,v,c)$询问第二阶段的解密应答器后，上式的右边只有$y_2$是$\mathbb{Z}_q$上的随机元素，其余均为定值，且由于$y_2$的系数不为0，则$\gamma$也一定是$\mathbb{Z}_q$上的随机元素，则此时的$\gamma$等于一个确定的$\beta$的概率就是$\frac{1}{q}$，显然为可忽略的。

两个阶段的合并

    综上，我们证明了两个阶段都成立$Pr[E_5| \neg F_6]=\frac{1}{q}$，故整体的一次实验中当然有$Pr[E_5| \neg F_6]=\frac{1}{q}$，当然这是单次询问下的概率，$E_5$发生是指总共$Q$次询问中，只要有某一次询问时发生即可认为$E_5$在整体上发生，则可知在总共$Q$次询问中$Pr[E_5| \neg F_6]=\frac{Q}{q}$，由此有

$$Pr[E_5]=Pr[F_6]Pr[E_5|F_6]+Pr[\neg F_6]Pr[E_5|\neg F_6]\leq Pr[F_6]+Pr[E_5|\neg F_6]\leq 2Adv_{\mathcal{A}_2,HASH}^{tcr}+\frac{Q}{q}$$

显然$E_5$发生的概率可忽略，则原来博文里最后Cramer-Shoup方案CCA实验总的区分优势$Adv_{\mathcal{A},CS}^{cca}(\lambda)$可以改写为

$$\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 ]\\ &\leq \frac{3}{q}+2Adv_{\mathcal{A}_1,\mathcal{G}}^{ddh}(\lambda)+2Adv_{\mathcal{A}_2,HASH}^{tcr}+\frac{Q}{q}\\ &= 2Adv_{\mathcal{A}_1,\mathcal{G}}^{ddh}(\lambda)+2Adv_{\mathcal{A}_2,HASH}^{tcr}+\frac{3+Q}{q} \end{aligned}$$

这也就证明了最后的结论。

总结

    至此，Cramer-Shoup方案的CCA安全性就完全证明了，这个证明非常的繁琐，但非常的有规律，一步一步往下走即可，从中也能体会到原作者为什么要在加密方案里设置一些特殊的步骤。其实最有意思的部分还是这篇博文给出的证明，利用一些代数的性质，也巧妙利用了私钥的不同形式，居然真的完成了证明。