Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Edited, thanks for the heads-up. –  Chris Smith Aug 23 '11 at 15:25
1  
I wonder what it is you call ln(g) in this context (where g is an element of an unsecified group G). –  Did Aug 23 '11 at 15:25
    
I just read the informal description, I'm assuming that g is a value that is known. –  Chris Smith Aug 23 '11 at 15:28
1  
@Alexei, no it isn't. –  Did Aug 23 '11 at 16:42
1  
@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. –  Arturo Magidin Aug 23 '11 at 17:04

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

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

share|improve this answer
    
Is there a not missing in your last sentence? ("that this is not the case") –  Paŭlo Ebermann Aug 23 '11 at 17:10
    
@Paŭlo: It's not well written now, for sure. Thanks. –  Arturo Magidin Aug 23 '11 at 17:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.