The ECDH problem defined that given $g,ag,bg$ it is difficult to calculate $abg$. But it is also difficult to calculate $bg$ given $ag,g,abg$. where $g$ is generator and a,b are elements of group.

  • $\begingroup$ Can you explain the specific relationship to cryptography? Otherwise this should be on a different site. Likely Math or Computer Science. $\endgroup$ – mikeazo Feb 23 '15 at 13:19
  • 1
    $\begingroup$ Note that $a$ and $b$ are normally not elements of the group, they are integers (modulo the order of $g$ if one wants to be pedantic). $\endgroup$ – fkraiem Feb 23 '15 at 15:19
  • $\begingroup$ @fkraiem: Exactly, this is what I was just observing. $\endgroup$ – Robert NACIRI Feb 23 '15 at 15:20
  • $\begingroup$ yes you are correct a,b are integers not element of group. $\endgroup$ – Aria Feb 24 '15 at 5:12

Yes, it is equally as difficult; if we assign:

$$g' = ag$$ $$a' = a^{-1}$$ $$b' = b$$

Then the restatement of your problem is: given $g' = ag$, $a'g' = g$ and $b'g' = abg$, compute $a'b'g' = bg$, which is exactly the ECDH problem.

Now, this assumes that $a$ has an inverse; this is not a problem if the curve order is a prime, and is easy to work around if the curve order is a prime times a small cofactor.

  • $\begingroup$ I think that the problem can't be solved in a general way. Assume if we can define on this group a pairing e. then chosing $x_0$ in such a way that $e(g,x_0)=\alpha$ then if the DLP is easy in this group, then we can solve for any integer a (modulo the order) $e(a.g, x_0)=\alpha^a$. It depend on the nature of the group. $\endgroup$ – Robert NACIRI Feb 23 '15 at 20:45

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.