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.

I know that there are elliptic curve groups, used in pairing-based cryptography, where the decisional Diffie Hellman problem (ie. given $g$, $g^a$, $g^b$ and $c$, determine if $c = g^{ab}$ is easy but the computational Diffie Hellman problem (given $g$, $g^a$ and $g^b$, find $g^{ab}$) is hard, and I know that if you can solve the discrete log problem (given $g$ and $g^a$ find $a$) you can do both.

But are there groups where you can fairly easily do the Computational Diffie Hellman problem but it's hard to find a discrete log?

share|improve this question
1  
Welcome to CSE! Notice that formulas can be written in (La)Tex, e.g. $g^{ab}$ renders as $g^{ab}$. –  fgrieu Jan 20 at 11:13
2  
AFAIK there are no know groups where this is the case, but we know no proof that shows they don't exist either. –  CodesInChaos Jan 20 at 14:23
add comment

1 Answer

There are some known groups in which computational Diffie-Hellman assumption is equivalent to discrete logarithm problem. Besides, It has been shown that the equivalence holds "when a small amount of extra information depending on the group order is provided". Furthermore, those extra informations has been computed for certain elliptic curve groups used in real cryptographic applications. Later the reduction has been tightened.

The whole progress in researches shows that although there is no full proof for the equivalence but there are some evidences which lead to the believe that there might not be any groups in which computational Diffie-Hellman is easy but discrete logarithm problem is hard.

share|improve this answer
add comment

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.