# 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? – Faraaz Ahmad Oct 5 '15 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 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.

• 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" – poncho Oct 5 '15 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. – Dietrich Epp Oct 5 '15 at 17:01
• Corrected the aanswer. Thank you for making this precise. – user27950 Oct 5 '15 at 17:04