# Proof that in El Gamal DDH implies CPA

I am refering to the theorem:

If the Discrete Diffie-Hellman problem is hard (i.e. if the DDH assumption holds), El Gamal is IND-CPA secure."

which is stated here along with the proof.

So we have adversary A that has a non-negligible advantage with CPA and we are trying to build adversary B that can break DDH. B is given $a$,$b$,$c$ which could be $g^x$, $g^y$ and $g^{xy}$ or $g^z$. Then A outputs $m_0$,$m_1$ to B which encrypts by picking random $b$ and returning to A: $c_0=b$, $c_1=c*m_b$

Now if $c=g^{xy}$ then A will be like interacting with real encryption oracle. Otherwise they say it will be like receiving random values

What I couldn't understand, is that since $c=g^z$ where $z$ is randomly chosen, assuming order of group $q$ which is prime, then there is always $k$ such that $z=k*y\ (mod\ q)$. So even when the B is given $g^z$ the encryption of the message could be a valid el gamal encryption, so it shouldn't look that random to the adversary A.

Is that right?

EDIT:

So apparently, as pointed out by fkraiem, since the adversary is given the public key $g^x$, when $c_0=b$ he expects the encrypted message to be: $c_1=g^{x\cdot y}\cdot m$ not just a random $k$. The probability of $k=x$ is negligible.

• Actually, it's the Decisional DH problem, not Discrete. – poncho Apr 28 '17 at 22:30
• It that their only mistake? – Antonis Paragas Apr 28 '17 at 22:32
• "So even when the $B$ is given $g^z$ the encryption of the message could be a valid el gamal encryption," It could be, but only with negligible probability (if $z = xy$). – fkraiem Apr 29 '17 at 1:35
• but why negligible, as i have shown, z can always break to $z=ky$ for some $k$. It doesn't have to be $xy$ right? (I have edited the original post to explicitly state the always) – Antonis Paragas Apr 29 '17 at 7:49
• If $z \ne xy$, then $(g^y, g^z \cdot m)$ is not a valid encryption of $m$ with the public key $g^x$. – fkraiem Apr 29 '17 at 8:53

A key point is that for group $G$ and any arbitrary $m \in G$, choosing a uniform $k \in G$ and setting $\hat{k} = k \cdot m$ gives the same distribution for $\hat{k}$ as just choosing it uniformly from $G$.
$Pr[\hat{k}=k \cdot m] =Pr[k=\hat{k} \cdot m^{-1}] = {1 \over {|G|}}$
So in the reduction, when $A$ interacts with the challenge $<u=g^y,v=g^z \cdot m>$ for random $z$, $u$ is completely independent of $v$, and so they reveal no information over each other. Notice that even though it's not a valid encryption scheme (because it's impossible to decrypt), the experiment is still well defined.