I'm wondering what is the current knowledge regarding the difficulty of solving the Diffie-Hellman problem (DHP).

Obvisously solving the DLP (discrete log) is at least as hard as solving the DH problem.

What about the converse :

  • In a general setting (cyclic group, no other assumption) ?
  • With specific groups (multiplicative groups of finite fields, various EC, ...) ?

I found ftp://ftp.inf.ethz.ch/pub/crypto/publications/MauWol00c.pdf discussing the matter but this paper is more than 20 years old so I guess it might be outdated...

  • $\begingroup$ Are you executing a research project? $\endgroup$
    – kelalaka
    Commented Nov 23, 2020 at 20:59
  • $\begingroup$ By amazing coincidence, many years ago I actually asked that question of "Whitfield Diffie". Paraphrased, his answer was that the difference in difficulty was essentially trivial compared to the whole problem. $\endgroup$ Commented Nov 23, 2020 at 21:21
  • 3
    $\begingroup$ "Obvisously solving the DLP (discrete log) is harder than solving DHP"; actually, that is not obvious at all. It is obviously at least as hard as solving CDH (the computational Diffie-Hellman problem), but whether it is harder is still an open question. Off the top, I can't think of any group for when the DLP is believed hard but the CDH problem is known to be easy. $\endgroup$
    – poncho
    Commented Nov 24, 2020 at 2:24
  • $\begingroup$ @poncho I actually meant "at least as hard". Thanks, I'll update. $\endgroup$
    – Weier
    Commented Nov 24, 2020 at 19:49
  • 1
    $\begingroup$ @kodlu - Apparently I failed the "Chicago Manual of Style". $\endgroup$ Commented Nov 24, 2020 at 21:15

1 Answer 1


According to Wikipedia (with two articles sourced):

Computing the discrete logarithm is the only known method for solving the CDH problem. But there is no proof that it is, in fact, the only method. It is an open problem to determine whether the discrete log assumption is equivalent to the CDH assumption, though in certain special cases this can be shown to be the case.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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