# Is it possible to apply hill-climbing algorithm to Diffie–Hellman?

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.

• 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? Commented Oct 5, 2015 at 14:07
• @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.
– fgrieu
Commented Oct 5, 2015 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.

• 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" Commented Oct 5, 2015 at 16:17
• @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. Commented Oct 5, 2015 at 17:01
• Corrected the aanswer. Thank you for making this precise.
– user27950
Commented Oct 5, 2015 at 17:04