Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

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

1 Answer 1

up vote 0 down vote accepted

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)

share|improve this answer
    
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 at 15:53
    
@CGFoX: stop at $(g^{xy})^{-1} \cdot z$; do you know the value $z$? –  poncho Jul 4 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 at 18:32
    
Could I just set $z$ to 1? –  CGFoX Jul 5 at 16:33
1  
@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 at 17:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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