1
$\begingroup$

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.

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

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)

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

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.