Say we are able to decrypt a Elgamal ciphertext $c$ using only the public key. Apparantly it is now possible to solve the Diffie-Hellman problem (given $g^a, g^b$ calculate $g^{ab}$). How?

I know how it works the otherway. When I'm able to solve DH, I found a way to decrypt Elgamal ciphertext. But I can't come up with a good idea for this problem.

I figured since $c=(c_1,c_2)=(v,w)$ maybe $c_1=g^a, c_2=g^b$ such that the plaintext $p=g^{ab}$, but that doesn't work out.

I'm thankful for any tips.

  • $\begingroup$ AFAIK ElGamal only reduces to the decisional DH problem, not the the computational DH problem. So this proof shouldn't exist $\endgroup$ Commented Jul 4, 2014 at 15:05
  • $\begingroup$ What's the difference between the decisional DH problem and the computational one? $\endgroup$ Commented Jul 4, 2014 at 15:33
  • 2
    $\begingroup$ Decisional is: given $g, g^a, g^b, g^c$, decide whether $g^c = g^{ab}$. Computational is: given $g, g^a, g^b$, compute $g^{ab}$. $\endgroup$
    – fkraiem
    Commented Jul 4, 2014 at 18:28
  • $\begingroup$ Well, apparantly CodesInChaos was wrong (see answer below). $\endgroup$ Commented Jul 4, 2014 at 19:09

1 Answer 1


Since you're learning, I won't go ahead and give you the answer; I will try to point you in the right direction.

Consider what Elgamal decryption is: if the private key is $a$ (and hence the public key is $g^a$), and you're given a ciphertext $(b, c)$, the ElGamal decryption is $b^{-a} \cdot c$

Now, assume that we have an Oracle that, given an arbitrary public key $g^x$, and a ciphertext $(g^y, z)$, would return the ElGamal decryption. Can you see how you could use that by passing it a public key and ciphertext of your choosing (hint: write out what the decryption would look like in that case)?

(Further hint: given $g^x$, it is easy to compute $g^{-x}$, as that's just the multiplicative inverse)

  • $\begingroup$ Decryption: $b^{-x} \cdot z = (g^{xy})^{-1} \cdot z = (g^{xy})^{-1} \cdot h^r \cdot p$ with $h$ is public key, $r$ random number, $p$ plaintext. Is that correct? This looks good, but don't I just want $g^{xy}$ (or $(g^{xy})^{-1}$ for that matter)? How can I eleminate the other factors without knowing $r$ and $p$? $\endgroup$ Commented Jul 4, 2014 at 15:53
  • $\begingroup$ @CGFoX: stop at $(g^{xy})^{-1} \cdot z$; do you know the value $z$? $\endgroup$
    – poncho
    Commented Jul 4, 2014 at 16:07
  • $\begingroup$ Oh, of course. Since I know $c$ I also know $z$ and can easily calculate $z^{-1}$. Thank you! $\endgroup$ Commented Jul 4, 2014 at 18:32
  • $\begingroup$ Could I just set $z$ to 1? $\endgroup$ Commented Jul 5, 2014 at 16:33
  • 1
    $\begingroup$ @CGFoX: well, $z$ is from the ciphertext, and you get to pick that, so of course you can... (I almost mentioned that myself; I'm glad I didn't; it's better that you thought of it) $\endgroup$
    – poncho
    Commented Jul 5, 2014 at 17:11

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.