第三十一个知识点：Game Hopping证明

关于安全证明, 目前主流的方法有安全归约证明 (由 single game 实现) 和 Game Hopping (由 game sequence 实现) 两种。

注意这篇博客是基于Douglas Stebila的论文An Introduction to Provable Security的部分3.3中书写的，通过这个链接下载论文：https://www.douglas.stebila.ca/files/teaching/amsi-winter-school/Lecture-2-3-Provable-security.pdf。

回顾公钥密码学中IND-CCA安全定义。如果一个人从攻击者处移除了解密问询，那么我们就得到了CPA安全概念。注意：移除加密问询不能改变攻击者的能力，因为攻击者一开始就有公钥，所以他可以自己进行加密。

在早期的博客中，我们描述了一个DDH问题。在这篇博客中，我们继续讨论一个叫‘game hopping’的技术，来证明如果DDH是难的，那么ElGamal加密方案是IND-CPA安全的。从广义上讲，我们将对ElGamal的IND-CPA博弈转换成DDH的博弈来证明攻击者的在第一个游戏的概率不会超过第二个。因此如果第二个的概率是非常小的，那么第一个博弈获胜的概率也会是非常小的。（证明加密方案是IND-CPA安全的）

首先，让我们描述一下ElGamal加密方案。我们预先给定一个交换群G，G的阶是素数q，生成器是g。（这里隐式的选择了安全参数 \(\lambda\)。当我们说一个变量是可忽略的时候，我们指的是对安全参数的一个可忽略函数。我们不在这里讨论细节。）明文和密文都是群中的元素。私钥是一个秘密的指数\(x \in Z_q\)，公钥是\(X = g^x\)。加密消息\(M \in G\)，应该先随机的选择一个\(y \in Z_q\)，计算\(c_1 = g^y,c_2=MX^y\)。然后密文就是\((c_1,c_2)\) 。为了解密，我们知道\(c_2 = MX^y = M(g^x)^y = M(g^y)^x = Mc_1^x\)。因此使用私钥\(x\)，我们能计算\(M = c_2c_1^{-x}\)。

现在考虑下面的博弈，\(A\)是一个PPT（概率多项式时间）攻击者。

• \(x \overset{\$}{\leftarrow} \mathbb{Z}_q, X \leftarrow g^x\)，生成公私钥对。
• \((M_0,M_1) \overset{\$}{\leftarrow} \mathcal{A}(X)\)。攻击者产生两个消息。
• \(b \overset{\$}{\leftarrow} \{0,1\}\)。
• \(y \overset{\$}{\leftarrow} \mathbb{Z}_q, c_1 \leftarrow g^y, Z \leftarrow X^y, c_2 \leftarrow M_bZ\)
• \(b^{'} \overset{\$}{\leftarrow} \mathcal{A}(c_1,c_2)\)。
• 如果\(b = b^{'}\)，就返回1，否则返回0 。

如果上述博弈返回1，我们说\(\mathcal{A}\)获胜。从Ana的博客来看，如果\(\mathcal{A}\)的概率\(2|Pr[\mathcal{A} \space wins \space Game_0]-1/2|\)。

接下来，考虑一个新博弈\(Game_1\)。唯一和\(Game_0\)不同的是它把第四步替换了，从

\[Z \leftarrow X^y
\]

变成了

\[z \overset{\$}{\leftarrow} Z_q，Z \leftarrow g^z
\]

。

因此新的密码就变成了\((c_1, c_2) = (g^y, M_bg^z)\)。

我们观看第二个博弈，我们发现z是随机选择的，我们攻击者就不知道关于b的任何信息，于是他猜测成功的概率是1/2。

我们对比两个博弈，观察其中的不同。一个用的是\(g^{xy}\)，一个用的是\(g^z\)。很容易发现问题和DDH问题相关。攻击者必须分区\(g^x,g^y,g^{xy}\)和\(g^x,g^y,g^z\)。为了保证两个博弈的链接，我们使用\(\mathcal{A}\)来构造一个攻击者\(\mathcal{B}\)，来对抗DDH:

• 一旦输出\((X，Y，Z)\)，运行$\mathcal{A} \(输入\)X\(。接收到挑战对\)(M_0,M_1)$。
• 随机选择一个比特\(b\)。然后计算\(m_bZ\)。
• 给攻击者\(\mathcal{A}\)出密文\((Y,m_bZ)\)然后其输出一比特\(b^{'}\)。
• 如果\(b = b^{'}\)，攻击者就获胜了。

如果\(B\) 被给定的三元组是\((g^x,g^y,g^{xy})\)，那么上述就是一个\(A\) 的完美的模拟。因此之前两个博弈的差距完全在于B和DDH对抗的概率。

结合上面的分析，我们可以很容易地得到A对ElGamal的IND-CPA安全性的优势并不大于B对DDH的优势。因此，如果DDH对于所有多项式时间的对手都是困难的(这意味着它们的优势可以忽略不计)，那么ElGamal必须是IND-CPA安全的。