ElGamal CPA secure

Question

I understand that if DDH (Decisional Diffie–Hellman) is hard then ElGamal is CPA secure. But I'm having confusion on what part the DDH applies to.

So, given $pk=(G, g, y), y=g^x$ and $sk=(pk,x), x \leftarrow Z_q$

Encryption: pick random $r \leftarrow Z_q$ then $(u,v)=(g^r, y^rm)$

Decryption: $m=u^{-x}v$ because $u^{-x}v=(g^r)^{-x}y^rm=(g^x)^{-r}y^rm=(y)^{-r}y^r=m$

From here, it says that:

Given some group $G$ and group elements $g$, and the elements $g^a$, $g^b$ and $g^c$, determine whether $g^c = g^{ab}$

I'm not understanding where this is applied to. I think it is at the decryption part but have more confusion of whether it is a DDH or CDH problem. Could someone highlight which part the $g^a$, $g^b$ and $g^c$?

Answer 1

So let's go through the IND-CPA game, shall we?

1. Pick two messages $m_0$ and $m_1$ arbitrarily.
2. Send them to the challenger who chooses $b\in\{0,1\}$ uniformly at random and returns you $c=E(m_b)$.
3. Output your guess for $b$ named $b'$. You "win" iff $b=b'$.

---

So you have two messages $m_0,m_1$, a ciphertext $c=(u,v)=(g^k,y^k\cdot m_b)=(g^k,g^{xk}\cdot m_b)$ and the public key $y=g^x$. Now note that you can calculate $c'=v\cdot m_0^{-1}$ which is $g^{xk}$ iff $b=0$. So what you now need to find out is whether $c'$ is the DH agreement of $u=g^k$ and $y=g^x$, which is precisely the DDH problem. If this is indeed this agreement then you know that $b=0$ and if not you know that $b=1$ and thus "win" the IND-CPA game.