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 '17 at 22:30
  • $\begingroup$ It that their only mistake? $\endgroup$ – Antonis Paragas Apr 28 '17 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 '17 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$ – Antonis Paragas Apr 29 '17 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 '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$.
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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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