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?


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.

  • $\begingroup$ Actually, it's the Decisional DH problem, not Discrete. $\endgroup$
    – poncho
    Apr 28, 2017 at 22:30
  • $\begingroup$ It that their only mistake? $\endgroup$ Apr 28, 2017 at 22:32
  • $\begingroup$ "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$). $\endgroup$
    – fkraiem
    Apr 29, 2017 at 1:35
  • $\begingroup$ 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) $\endgroup$ Apr 29, 2017 at 7:49
  • 1
    $\begingroup$ If $z \ne xy$, then $(g^y, g^z \cdot m)$ is not a valid encryption of $m$ with the public key $g^x$. $\endgroup$
    – fkraiem
    Apr 29, 2017 at 8:53

1 Answer 1


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$.
This is because:
$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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.