5
$\begingroup$

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}}$

$\endgroup$
9
  • $\begingroup$ Edited, thanks for the heads-up. $\endgroup$ Aug 23, 2011 at 15:25
  • 1
    $\begingroup$ I wonder what it is you call ln(g) in this context (where g is an element of an unsecified group G). $\endgroup$
    – Did
    Aug 23, 2011 at 15:25
  • $\begingroup$ I just read the informal description, I'm assuming that g is a value that is known. $\endgroup$ Aug 23, 2011 at 15:28
  • 1
    $\begingroup$ @Alexei, no it isn't. $\endgroup$
    – Did
    Aug 23, 2011 at 16:42
  • 1
    $\begingroup$ @Alexei: Even if you interpret it as conjugation, $g^{xy} = y^{-1}x^{-1}gxy$, and $g^xg^y = x^{-1}gxy^{-1}gy$; they need not be equal. $\endgroup$ Aug 23, 2011 at 17:04

2 Answers 2

6
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ Is there a not missing in your last sentence? ("that this is not the case") $\endgroup$ Aug 23, 2011 at 17:10
  • $\begingroup$ @Paŭlo: It's not well written now, for sure. Thanks. $\endgroup$ Aug 23, 2011 at 17:13
3
$\begingroup$

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.

$\endgroup$

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.