1
$\begingroup$

I've seen from the SafeCurve criteria that one should try to avoid small complex multiplication field discriminant as it can speedup the discret log computation via the Polard Rho method.

However, I cannot find any information about how this additional information can improve the rho method. Especially, the SafeCurve page seems quite vague, mentioning that we do not know for sure if a small Discriminant (even really tiny like 3 for example) can lead to disastrous consequences or not. May someone explain how this particular structure can (in some cases) improve the rho method?

| improve this question | | | | |
$\endgroup$
1
$\begingroup$

I first recall some basics on the discrete logarithm problem and the Pollard-rho algorithm before answering you question.

The discrete logarithm problem

Given a point $P$ of prime order $q$ on an elliptic curve, and $Q$ a point in the subgroup generated by $P$, then there exists $k$ such that $Q = kP$ where $0\leq k < q$.

The discrete logarithm of $Q$ in base $P$ is $k$, and the discrete logarithm problem is finding $k$ knowing $P$ and $Q$

The Pollard-rho algorithm

The Pollard-rho algorithm on a generic group of prime order $q$ has a complexity of $\sqrt{\pi q/2}$.

The principle of it is to construct a sequence of points by posing $R_0 = a_0P+b_0Q$ with random integers $a_0$ and $b_0$, then using a function $f$ that acts as a pseudo-random walk to obtain the sequence of points: $$ R_{i+1} = f(R_i) = a_{i+1} P + b_{i+1} Q. $$ Eventually, there will be will a point $R_j$ that is equal to a previous point $R_i$ in the sequence. Then, we deduce that: $$ k \equiv (a_i - a_j)(b_j-b_i)^{-1} \mod q, $$ if, of course, $(b_j-b_i)$ is invertible (but that will be the case with a high probability).

Now, the birthday paradox gives the aforementioned complexity.

Speeding-up rho

On elliptic curves, it is easy to compute $-P$ from $P=(x,y)$ since $-P=(x,-y)$. Then, we can regroup all the points of the curve by pairs $\{P,-P\}$.

Instead of looking for a collision between a point $R_i$ and $R_j$ in the sequence, we look for a collision on their $x$-coordinate. The discrete logarithm will be found if we have $R_i = \pm R_j$.

It is as if the search has not been done on all the points, but only on half of them. Then the value $q$ in the complexity is replaced by $q/2$, which gives the complexity of $\sqrt{q\pi/4}$ (which you will find the corresponding page on the website SafeCurves).

Speeding-up rho further

What we did above is possible because we have the map (called endomorphism) $[-1]$: $$ \begin{array}{rrcl} [-1]: & E & \longrightarrow & E \\ & (x,y) & \longmapsto & (x,-y) \end{array} $$ that sends a point of the elliptic curve $E$ to its opposite. We can see that if we apply it twice, we go back to the original point. We say this map has order $2$, and that is why we could grouped by pairs. And it is easy to compute.

Now the question is: does there exist other such maps easy to compute that could be used to speed-up rho by a greated factor?

The answer is yes. For instance, the curve secp256k1 has the following endomorphism: $$ \begin{array}{rrcl} \phi: & \texttt{secp256k1} & \longrightarrow & \texttt{secp256k1} \\ & (x,y) & \longmapsto & (\beta x,y) \end{array} $$ where $\beta$ is an element of order $3$ (it satisfies $\beta^3=1$ with $\beta \neq 1$) in the finite field of the curve. Then we have: $$ (x,y) \mapsto (\beta x, y) \mapsto (\beta^2 x, y) \mapsto (\beta^3 x, y) = (x,y), $$ which means the order of $\phi$ is $3$.

Then we can group the points of the curve by group of three: $\{ P, \phi(P), \phi^2(P)\}$. We choose one of three points as a representant (such as the point that has the smallest $x$-coordinate viewed as an integer). Instead of searching a collision in Pollard-rho on $q$ points, we search a collision on $q/3$ representants. From this, we deduce that on this curve we can divide by a factor $\sqrt 3$ the complexity of Pollard-rho. Combined with the previous speed-up, this gives a complexity of $\sqrt{q\pi/12}$.

Relation with the CM-field discriminant

The key is that we want an endomorphism easy to compute, otherwise it would not be useful to speed-up Pollard-rho. As we can see, those two examples given above are pretty simple. It is because their degree is $1$, which means the rational functions to compute the coordinates of $\phi(P)$ are polynomials of degree $1$.

There is a relation between the CM-field discriminant the existence of an endomorphism of small degree. In the case of the curve secp256k1, the fact that this discriminant is $-3$ is directly related to the endomorphism $\phi$ with this formula: $$ \left(\frac{1+i\sqrt 3}{2}\right)\left(\frac{1 - i\sqrt 3}{2}\right) = 1, $$ which means that there is a non-trivial endomorphism of degree $1$, that is the one given above.

I hope I gave some elements to answer your question. I will try to expand and correct some points later.

| improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Thank you for this detailed answer! Correct me if I am wrong, but then finding a non-trivial endomorphism does not imply a very efficient improvement. For instance here the speedup doesn't even remove one bit of security (i.e. we had 127 bits due to the original rho method, and the factor $\sqrt 3$ does not take us down to 126) which sounds quite ok for non standardized applications. $\endgroup$ – Binou Apr 7 at 0:21

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.