选择明文攻击下的不可区分性

公钥加密方案在选择明文攻击（Chosen Plaintext Attack，CPA）下的IDA（Indistinguishability）游戏称为IND-CPA游戏如下：

（1） 初始化。挑战者产生系统$\mathcal{\Pi}$，敌手$\mathcal {A}$获得系统的公开钥。

（2） 敌手产生明文消息，得到系统加密后的密文（可多项式有界次）。

（3） 挑战。敌手输出出两个长度相同的消息$M_0$和$M_1$。挑战者随机选择$\beta \larr _R\{0,1\}$，将$M_{\beta}$加密，并将密文$C^*$（称为目标密文）给敌手。

（4） 猜测。敌手输出$\beta^{\prime}$，如果$\beta=\beta^{\prime}$，则敌手攻击成功。

敌手的优势可定义为参数$\mathcal{K}$的函数：

$Adv_{\mathcal{\Pi},\mathcal{A}}^{CPA}(\mathcal{K})=|Pr[\beta^{\prime}=\beta]-\frac{1}{2}|$

其中，$\mathcal{K}$是安全参数，用来确定加密方案密钥的长度。因为任一个不作为（仅做监听）的敌手$\mathcal{A}$，都能通过对$\beta$做随即猜测，而以$\frac{1}{2}$的概率赢得IND-CPA游戏。而$|Pr[\beta^{\prime}=\beta]-\frac{1}{2}|$是敌手通过努力得到的，故称为敌手的优势。

因为

$|Pr[\beta^{\prime}=\beta]-\frac{1}{2}|\\ =|Pr[\beta=0]Pr[\beta^{\prime}=\beta|\beta=0]+Pr[\beta=1]Pr[\beta^{\prime}=\beta|\beta=1]-\frac{1}{2}|\\ =|Pr[\beta=0]Pr[\beta^{\prime}=0|\beta=0]+Pr[\beta=1]Pr[\beta^{\prime}=1|\beta=1]-\frac{1}{2}|\\ =|\frac{1}{2}[1-Pr[\beta^{\prime}=1|\beta=0]]+\frac{1}{2}Pr[\beta^{\prime}=1|\beta=1]-\frac{1}{2}|\\ =\frac{1}{2}|Pr[\beta^{\prime}=1|\beta=1]-Pr[\beta^{\prime}=1|\beta=0]|$

敌手的优势也可定义为

$Adv_{\mathcal{\Pi},\mathcal{A}}^{CPA}(\mathcal{K})=|Pr[\beta^{\prime}=1|\beta=1]-Pr[\beta^{\prime}=1|\beta=0]|$

只不过这种定义的优势是之前的2倍。

上述的IND-CPA游戏可形式化地描述如下，其中公钥加密方案是三元组$\mathcal{\Pi}=(KeyGen,\varepsilon,D)$，游戏的主体是挑战者。

$Exp_{\mathcal{\Pi},\mathcal{A}}^{CPA}(\mathcal{K}):\\ (pk,sk)\larr KeyGen(\mathcal K);\\ (M_0,M_1)\larr \mathcal{A}(pk)\ ,\ when |M_0|=|M_1|;\\ \beta \larr_R\{0,1\},C^*=\varepsilon_{pk}(M_{\beta});\\ \beta^{\prime}\larr\mathcal{A}(pk,C^*);\\ if\ \beta^{\prime}=\beta\ , \ return\ 1\ , \ else\ return\ 0;$

敌手的优势定义为

$Adv_{\mathcal{\Pi},\mathcal{A}}^{CPA}(\mathcal{K})=|Pr[Exp_{\mathcal{\Pi},\mathcal{A}}^{CPA}(\mathcal{K})=1]-\frac{1}{2}|$

如果在任何多项式时间的敌手$\mathcal{A}$，存在一个可忽略的函数$\epsilon(\mathcal K)$，使得$Adv_{\mathcal{\Pi},\mathcal{A}}^{CPA}(\mathcal{K}) \le \epsilon (\mathcal K)$，那么就称这个加密算法$\mathcal{\Pi}$是语义安全的，或者称为在选择明文攻击下具有不可区分性，简称为IND-CPA安全。

如果敌手通过$M_{\beta}$的密文能得到$M_{\beta}$的一个比特，就有可能区分$M_{\beta}$是$M_0$还是$M_1$，因此，IND游戏刻画了语义安全的概念。

定义中需要注意以下几点：

（1）定义中敌手是多项式时间的，否则因为它有系统的公开钥，可得到$M_0$和$M_1$的任意多个密文，再和目标密文逐一进行比较，即可赢得游戏。

（2）$M_0,M_1$应该是等长的，否则由密文，有可能区分$M_{\beta}$是$M_0$还是$M_1$。

（3）如果加密方案是确定的，每个明文对应的密文只有一个，敌手只需重新对$M_0$和$M_1$加密后与目标密文进行比较，即赢得游戏。因此，语义安全性不适用于确定性的加密方案。