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 Nov 23 '20 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$ – user10216038 Nov 23 '20 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 Nov 24 '20 at 2:24
  • $\begingroup$ @poncho I actually meant "at least as hard". Thanks, I'll update. $\endgroup$ – Weier Nov 24 '20 at 19:49
  • 1
    $\begingroup$ @kodlu - Apparently I failed the "Chicago Manual of Style". $\endgroup$ – user10216038 Nov 24 '20 at 21:15

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, privacy policy and cookie policy

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