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?

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

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.


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.