2
$\begingroup$

In a cyclic group with randomly looking behavior like the one used in secp256k1, is there any known efficient algorithm to compare the order of two randomly given elements $P_1$ and $P_2$ and find out which one will appear first starting from a known generator point of the cycle? If such algorithm exists, would that be considered a weakness?!

Consider that we have two known integers $a$ and $b$ so that $a>b$. Taking $P_1=a\times G$ and $P_2=b\times G$ we can say $P_2$ has a greater order in the cycle, meaning that starting from the generator point it will appear before than $P_1$.

By this definition is there any known algorithm based which one can compare the order of two random elements of the group $P_1$ and $P_2$?

$\endgroup$
  • 4
    $\begingroup$ You really shouldn't use the word "order" here. "Order" in group theory has a precise meaning, and using it to mean anything else creates confusion. $\endgroup$ – fkraiem Jan 6 at 13:04
  • $\begingroup$ What word do you suggest to use instead of "order"? $\endgroup$ – PouJa Jan 6 at 16:15
  • 1
    $\begingroup$ The integer $a$ such that $P_1 = a\cdot G$ is called the discrete logarithm of $P_1$ (relative to $G$), and similarly for $P_2$, so you could say that you wish to show that the discrete logarithm of $P_2$ is larger than that of $P_1$. $\endgroup$ – fkraiem Jan 6 at 16:21
2
$\begingroup$

By this definition is there any known algorithm based which one can compare the order of two random elements of the group $P_1$ and $P_2$?

No, such an algorithm would allow for an easy break of the elliptic curve discrete logarithm problem. But as this problem is assumed hard for secure curves like secp256k1 us knowing such an algorithm is impossible.

To see this fix the reference generator $G$ to the standard one for the curve with the generator having order $q$. Furthermore let $P=xG$ be the challenge point for which we want to recover $x$. Now define $a=1$ and $b=q-1$.

  1. Compute $m=\frac{a+b}{2}$ and $M=mG$.
  2. Check whether $M=P$ and if so, return $m$.
  3. Check whether $M<P$ using the conjectured algorithm. If this is true, set $a\gets m$, otherwise set $b\gets m$.
  4. Go to 1.

This is a standard binary search as you may have recognized and it will find the discrete logarithm in about $\log_2 q$ scalar point multiplications and algorithm evaluations which is quite efficient.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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