CCA安全定义

    对公钥方案来说，CCA安全是比CPA安全还要复杂的，CCA安全一定是CPA安全，但CPA安全不一定是CCA安全，CCA的全称是Chosen-ciphertext attack，也就是选择密文攻击，攻击者可以随便选择一个密文，访问解密应答器并得到对应的明文，这对攻击者的能力是很大的提高。如果一个方案能抵抗选择密文攻击就称为是CCA安全的，但和以前一样，仅仅是文字上的描述是不准确的，要用标准的密码学语言和数学语言进行描述才行，其实还是用到了分辨实验的思想，固定攻击者使用解密应答器的方式，具体定义如下：

CCA安全-不可分辨实验

实验$Pubk_{\mathcal{A},\Pi}^{cca}(\lambda)$定义如下：
1，$(pk,sk) \leftarrow Gen(1^\lambda)$
2，$\mathcal{A}$得到$pk$和应答器$Dec_{sk}(\cdot)$，输出一对等长的消息$m_0,m_1$
3，选择$b \leftarrow \{ 0,1 \}$，计算$c^*=Enc_{pk}(m_b)$，发送给$\mathcal{A}$
4，$\mathcal{A}$继续与应答器$Dec_{sk}^*(\cdot)$交互，但是不允许向应答器询问$c^*$的对应明文
5，$\mathcal{A}$最终输出一个比特$b’$
5，如果$b’=b$则实验输出1，否则输出0.实验结束
    注意第四步的应答器$Dec_{sk}^*(\cdot)$是带有$*$号的，意思是不允许向应答器询问$c^*$的对应明文，这是非常显然的，不然这个分辨实验没有意义。
    如果$Pubk_{\mathcal{A},\Pi}^{cca}(\lambda)=1$，则说$\mathcal{A}$成功，$\mathcal{A}$成功的优势定义为：

$$Adv_{\mathcal{A},\prod}(\lambda):=|Pr[ Pubk_{\mathcal{A},\Pi}^{cca}(\lambda)=1]-\frac{1}{2}|$$

由此就可以给出现在公认的CCA安全的定义如下：

CCA安全定义

    如果下列条件满足，则说公钥加密方案$\Pi$具有在选择密文攻击下不可分辨加密(CCA-安全)：对于任意$PPT$敌手$\mathcal{A}$，存在可忽略函数$negl$，使得

$$Pr[ Pubk_{\mathcal{A},\Pi}^{cca}(\lambda)=1] \leq \frac{1}{2}+negl(\lambda)$$

即$Adv_{\mathcal{A},\Pi}^{cca}(\lambda) \leq negl(\lambda)$。

ELGamal加密方案的CCA安全

    ELGamal加密方案在之前的博文里已经讨论过了，并证明了ELGamal加密方案是CPA安全的，但ELGamal加密方案在上面CCA安全的分辨实验定义下不是安全的。首先回忆一下ELGamal加密方案：

ELGamal加密方案

    ELGamal加密方案的结构并不复杂，设$\mathcal{G}$是一个多项式时间算法，输入$1^\lambda$，输出一个循环群$\mathbb{G}$，此群的阶数为长度为$\lambda$比特的素数$q$，设$g$是此群的一个生成元。对应的ELGamal加密方案主要结构如下：
Gen：输入$1^\lambda$，运行$\mathcal{G}$得到$(\mathbb{G},q,g)$，选择$x\leftarrow \mathbb{Z}_q$，计算$h:=g^x$。公钥为$pk=(\mathcal{G},q,g,h)$，私钥为$sk=(\mathcal{G},q,g,x)$
Enc：输入公钥$pk=(\mathcal{G},q,g,h)$，消息$m \in \mathbb{G}$，随机选择$y\leftarrow \mathbb{Z}_q$，输出密文$(c_1,c_2)=(g^y,h^y \cdot m)$
Dec：输入私钥$sk=(\mathcal{G},q,g,x)$，密文$(c_1,c_2)$，计算消息：$m:=\frac{c_2}{c_1^x}=c_2 \cdot (c_1^x)^{-1}=c_2 \cdot (c_1^{-1})^x$

ELGamal加密方案不是CCA安全

    这个其实非常好理解，只要我们能找到一个$PPT$的敌手$\mathcal{A}$使得$Adv_{\mathcal{A},\Pi}^{cca}(\lambda)$不是可忽略的即可，实际上这个$\mathcal{A}$的构造可以非常简单。
    首先$\mathcal{A}$随机生成两个等长的明文$m_0,m_1$，之后得到密文$c^*=(g^r,h^r \cdot m_b)$，CCA分辨实验里要求不能直接用$c^*$去询问解密应答器，但可以对$c^*$进行简单的修改如下：

$$c=(g\cdot g^r,h\cdot h^r \cdot m_b)=(g^{r+1},h^{r+1}\cdot m_b)$$

显然$(g^{r+1},h^{r+1}\cdot m_b)$仍然是一个合法的密文，且不等于$c^*$(虽然可能不太准确，但这样的$c$肯定可以构造出来)，这样的$c^*$解密之后，$\mathcal{A}$就得到了$m_b$，也就是成功破解了算法，分辨实验成功的优势必为$\frac{1}{2}$。

    所以ELGamal加密方案的确不是CCA安全的