52 Things: Number 31: Game Hopping Proof

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this post we give an example of a proof that uses the 'game hopping' technique.

Note, this blog post is based on Section 3.3 of 'An Introduction to Provable Security' by Douglas Stebila, downloadable via this link.

Recall the definition of IND-CCA security for a public key encryption scheme, described by Ana here. If one removes the decryption oracle from the adversary, we obtain the IND-CPA (indistinguishability under chosen-plaintext attacks) security notion. Note that removing the encryption oracle does not change the adversary's view since it holds the public key and can therefore produce its own encryptions.

In an earlier blog post, we described the Decisional Diffie-Hellman (DDH) problem. In this post, we are going to use a technique called 'game hopping' to show that the ElGamal encryption scheme is IND-CPA secure if DDH is hard. Loosely speaking, we will transform the IND-CPA game against ElGamal into a game against DDH and show that an adversary's advantage in the first game cannot be more than their advantage in the second. So if their advantage in the second game is negligible (which is the assumption that DDH is hard), the advantage in the first game must also be negligible (showing that the encryption scheme is IND-CPA secure).

Firstly, let's describe the ElGamal scheme. We work in a cyclic group $G$ of prime order $q$ with generator $g$. (Implicitly the selection of the group depends on a security parameter $\lambda$ and when we say that a quantity is negligible, we mean a negligible function of $\lambda$, but we'll omit those details here.) Plaintexts and ciphertexts are group elements. The private key is a secret exponent $x \in \mathbb{Z}_q$ and the public key is $X = g^x$. To encrypt a message $M \in G$, one selects an exponent $y \in \mathbb{Z}_q$ uniformly at random, computes $c_1 = g^y$, $c_2 = MX^y$ and the ciphertext is the pair $(c_1, c_2)$. To decrypt, notice that $c_2 = MX^y = M(g^x)^y = M(g^y)^x = Mc_1^x$ so, with the private key $x$ we just compute $M = c_2c_1^{-x}$.

Now consider the following game $\mathrm{Game}_0$ played by a PPT adversary $\mathcal{A}$.

1. $x \overset{\$}{\leftarrow} \mathbb{Z}_q, X \leftarrow g^x$ (generate the public, private key pair)
2. $(M_0, M_1) \overset{\$}{\leftarrow} \mathcal{A}(X)$ (the adversary, in possession of the public key, produces a pair of challenge messages, possibly using a randomised process)
3. $b \overset{\$}{\leftarrow} \{0,1\}$ (a random bit is chosen)
4. $y \overset{\$}{\leftarrow} \mathbb{Z}_q, c_1 \leftarrow g^y, Z \leftarrow X^y, c_2 \leftarrow M_bZ $ (an encryption of message $b$ is produced)
5. $b' \overset{\$}{\leftarrow} \mathcal{A}(c_1, c_2)$ (the adversary, in possession of the ciphertext, produces a bit, possibly using a randomised process)
6. if $b = b'$ then return 1, else return 0.

We say $\mathcal{A}$ wins $\mathrm{Game}_0$ if the game returns 1. From the definition in Ana's blog, it should be clear that the advantage of $\mathcal{A}$ against the IND-CPA security of ElGamal (with parameters $G$, $q$ and $g$) is $2|\mathrm{Pr}[\mathcal{A} \: \mathrm{wins \: Game}_0] - 1/2|$ (1).

Next, consider a new game $\mathrm{Game}_1$. This game is exactly as above, except that in Step 4, we replace the command 

$Z \leftarrow X^y$

by 

$z \overset{\$}{\leftarrow} \mathbb{Z}_q, Z \leftarrow g^z$.

So the new ciphertext is $(c_1, c_2) = (g^y, M_bg^z)$ instead of $(c_1, c_2) = (g^y, M_bg^{xy})$. 

Again we say $\mathcal{A}$ wins this game if it returns 1. What is the probability that this happens? Note that $Z$ is now a totally random group element by the randomness of $z \in \mathbb{Z}_q$. So $c_2$ is also a random group element, independent of $X$, $c_1$ and $b$. So the adversary gains no information about $b$ from $(c_1, c_2)$, meaning it outputs the correct bit and wins the game with probability exactly 1/2 (2).

Now we bound the difference in probability for an adversary to win each of the games. Since the only difference in the two games is that the group element $g^{xy}$ is replaced by a random group element $g^z$, it is easy to see how this relates to the DDH problem, where an adversary must distinguish between the triples $(g^x, g^y, g^{xy})$ and $(g^x, g^y, g^z)$ for a random exponent $z \in \mathbb{Z}_q$. To make the link between the games precise, we use the adversary $\mathcal{A}$ to build an adversary $\mathcal{B}$ against DDH as follows:

1. On input $(X, Y, Z)$, run $\mathcal{A}$ on input $X$ to receive a challenge pair $(M_0, M_1)$
2. Select a bit $b$ uniformly at random and compute $m_bZ$
3. Give the 'ciphertext' $(Y, m_bZ)$ to the $\mathcal{A}$ and receive a bit $b'$
4. If $b = b'$, guess that $Z = g^{xy}$ and return 1, else guess $Z$ is random so return 0.

If $\mathcal{B}$ is given a real Diffie-Hellman triple $(g^x, g^y, g^{xy})$ then the above is a perfect simulation of $\mathcal{A}$ playing $\mathrm{Game}_0$, and if $\mathcal{B}$ is given a fake triple $(g^x, g^y, g^z)$ then it is a perfect simulation of $\mathcal{A}$ playing $\mathrm{Game}_1$. Therefore, the difference between the probability of $\mathcal{A}$ winning $\mathrm{Game}_0$ and $\mathcal{A}$ winning $\mathrm{Game}_1$ is precisely the difference between the probability that $\mathcal{B}$ outputs 1 on input $(g^x, g^y, g^{xy})$ and outputs 1 on input $(g^x, g^y, g^z)$, which is exactly the advantage of $\mathcal{B}$ against DDH.

Combining the above with facts (1) and (2) (and using the triangle inequality to take care of the modulus signs), we can easily obtain that the advantage of $\mathcal{A}$ against the IND-CPA security of ElGamal is no greater than the advantage of $\mathcal{B}$ against DDH. So if DDH is hard for all polynomial time adversaries (meaning their advantage is negligible), ElGamal must be IND-CPA secure.