2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Can you explain the specific relationship to cryptography? Otherwise this should be on a different site. Likely Math or Computer Science. $\endgroup$
    – mikeazo
    Commented Feb 23, 2015 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
    Commented Feb 23, 2015 at 15:19
  • $\begingroup$ @fkraiem: Exactly, this is what I was just observing. $\endgroup$ Commented Feb 23, 2015 at 15:20
  • $\begingroup$ yes you are correct a,b are integers not element of group. $\endgroup$
    – Aria
    Commented Feb 24, 2015 at 5:12

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\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$ Commented Feb 23, 2015 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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