# Use ElGamal to solve Diffie-Hellman problem

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.

• AFAIK ElGamal only reduces to the decisional DH problem, not the the computational DH problem. So this proof shouldn't exist – CodesInChaos Jul 4 '14 at 15:05
• What's the difference between the decisional DH problem and the computational one? – CGFoX Jul 4 '14 at 15:33
• 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}$. – fkraiem Jul 4 '14 at 18:28
• Well, apparantly CodesInChaos was wrong (see answer below). – CGFoX Jul 4 '14 at 19:09

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)

• 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$? – CGFoX Jul 4 '14 at 15:53
• @CGFoX: stop at $(g^{xy})^{-1} \cdot z$; do you know the value $z$? – poncho Jul 4 '14 at 16:07
• Oh, of course. Since I know $c$ I also know $z$ and can easily calculate $z^{-1}$. Thank you! – CGFoX Jul 4 '14 at 18:32
• Could I just set $z$ to 1? – CGFoX Jul 5 '14 at 16:33
• @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) – poncho Jul 5 '14 at 17:11