If Eve intercepts all the values communicated between Alice and Bob in a Diffie–Hellman key exchange, and applies the hill-climbing algorithm to reverse the modulo function, how will the algorithm know whether it is following the right path?


NO, we can't apply an hill-climbing algorithm to Diffie–Hellman.

In order to break Diffie-Hellman key exchange, it is enough for Eve to reverse exponentiation modulo the public prime $p$; that is, given $g^x\bmod p$, find $x$. That's the Discrete Logarithm Problem.

We do not know that hill-climbing can help for that (or the slightly less general DH problem). One reason is that in the DLP, we have no known way to estimate if a guess of $x$ is close or far from the solution (contrary to what happens for the continuous logarithm problem). Hill-climbing is nice when it works; but in crypto, it tends to work only against weak/broken systems.

  • $\begingroup$ Well, you're not saying a complete no, it's just "We do not know". antilogs can be estimated by trial and error and maybe even hill climb. Isn't it a similar situation? $\endgroup$ – Faraaz Ahmad Oct 5 '15 at 14:07
  • $\begingroup$ @Faraaz Ahmad: I've revised the answer towards a square NO, with as justification that we know no mean. Definitely, the situation is very different from that of the continuous case. $\endgroup$ – fgrieu Oct 5 '15 at 15:13

Because groups used for Diffie-Hellman cannot be given a non-trivial, efficiently calculable metric, you cannot define such things like a "local maximum" or "local minimum". You also cannot say if you are climbing or diving.

  • 3
    $\begingroup$ Actually, it's quite easy to give them a metric with the actual solution as a local maximum. What's difficult is to give a metric that gives a useful indication of "you're close" $\endgroup$ – poncho Oct 5 '15 at 16:17
  • 2
    $\begingroup$ @poncho: it's easy to define a metric that tells you when you're close, it's just that evaluating the metric is as hard as solving the discrete logarithm, so you don't get any benefit. $\endgroup$ – Dietrich Epp Oct 5 '15 at 17:01
  • $\begingroup$ Corrected the aanswer. Thank you for making this precise. $\endgroup$ – user27950 Oct 5 '15 at 17:04

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.