Diffie–Hellman Problem

Question

I've been reading the Wikipedia Article on the Diffie–Hellman Problem and I've been wondering whether I understood it correctly, because if I did it seems fairly easy to solve.

The Diffie–Hellman problem is stated informally as follows:

Given an element $g$ and the values of $g^x$ and $g^y$, what is the value of $g^{x\cdot y}$?

We know: $g$, $m = g^x$ and $l = g^y$. Couldn't we simply solve the last two equations for x and y respectively and in a few more steps come up with the following result?

$g^{x\cdot y}=g^{\frac{\ln(m)\cdot \ln(l)}{\ln(g)^2}}$

Answer 1

True, if you can calculate the discrete logarithm, then it would be easy. But that's hard too, e.g. see Wikipedia for more details.

Answer 2

The issue of the Diffie-Hellman problem is the following:

• We know that if we can solve the Discrete Logarithm problem, then we can solve the Diffie-Hellman problem. Thus, the Diffie-Hellman problem is no harder than the discrete logarithm problem. So far as we know, the discrete logarithm problem is hard.

• However, we don't know whether solving the Diffie-Hellman problem is at least as hard as solving the discrete logarithm problem. In other words, is there some easier way of figuring out $g^{xy}$ given $g$, $g^x$, and $g^y$ that does not involve finding $x$ or $y$? Or will solving the Diffie-Hellman problem also allow you to find an easy solution to the corresponding discrete logarithm problem (thus showing the discrete logarithm problem is no harder than Diffie-Hellman)?

To give you an analogy, consider the problem of finding the greatest common divisor of two positive integer $n$ and $m$. If we can factor $n$ and $m$ into primes, $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ and $m=q_1^{\beta_1}\cdots q_r^{\beta_r}$, then we can find the greatest common divisor by finding all primes that appear in both factorizations, and taking the smallest of the two exponents. Thus, finding the gcd is no harder than factoring; and so far as we know, factoring is hard. Does that mean that finding the gcd is hard?

No! Because it turns out that there is a method for computing the gcd that does not rely on finding the prime factorizations of $n$ and $m$ (the Euclidean algorithm), and this algorithm turns out to be "easy" (computationally speaking).

The issue with the Diffie-Hellman problem is that we don't know whether the same thing happens. Could there be some other, clever way of figuring out $g^{xy}$ without having to go through the discrete logarithm problem? Generally it is believed that the Diffie-Hellman is at least as hard as the discrete log problem, so it is believed that there is no such clever way, but there is no proof (in so far as I know).