Last week Igor Semaev distributed a paper which seems to give a new, more efficient, algorithm to solve the Elliptic Curve Discrete Logarithm Problem (ECDLP) on curves defined over fields of small characteristic. This is important as such curves are used in a number of protocols and products. Whilst not devastating (yet), the algorithm does vindicate the communities preference for curves defined over large prime fields.
Recall the ECDLP is to solve the following equation for z,
$$ Q = [z] P $$
where $P$ and $Q$ are given points on the curve $E({\mathbb F}_q)$ over the field ${\mathbb F}_q$.
Like many modern algorithms for the ECDLP over curves of small characteristic the algorithm makes use of the "summation polynomial". In particular it makes use of the third summation polynomial $S_3(x_1,x_2,x_3)$. This polynomial has a zero $(x_1,x_2,x_3)$ if and only if there exists $y$-coordinates $y_1,y_2$ and $y_3$ such that $P_i=(x_i,y_i)$ is a point on the curve and
$$ P_1+P_2+P_3 = {\mathcal O}$$.
The algorithm is very very simply, and is given by the following steps, (see page 4 of Semaev's paper).
- Pick an integer value $m$ and a subset $V$ of ${\mathbb F}_q$ of size $q^{1/m}$.
- Generate a set of "relations" as follows:
- Pick random integers $u$ and $v$ and compute the point $R= [u] P + [v] Q$. If $R={\mathcal O}$ then we immediately solve the ECDLP, so assume $R \ne {\mathcal O}$. Write $R$ as $(R_X,R_Y)$
- If $R_X \in V$ then we have a relation $[u] P + [v] Q - R = {\mathcal O}$.
- For $t=2,\ldots,m$ try to solve the following system \begin{align*} S_3(u_1,x_1,x_2) &= 0 \\ S_3(u_i,u_{i+1},x_{i+2}) &=0 \mbox{ for } 1 \le i \le t-3 \\ S_3(u_{t-2},x_t,R_X)&=0 \end{align*} for $x_1,\ldots,x_t \in V$ and $u_1,\ldots,u_{t-2} \in {\mathbb F}_q$.
- If successful we can find $y_1,\ldots,y_t \in {\mathbb F}_q$ such that $$(x_1,y_1) + (x_2,y_2) + \ldots + (x_t,y_t) + [u] P + [v] Q = {\mathcal O}$$.
- As soon as we have enough relations we can solve for $z$ using linear algebra.
The last step is standard in so called "index calculus" algorithms. The key innovation is in the second step. The idea is that we try to solve the system defined by the $S_3$ summation polynomials; which have low degree; rather than attack the $S_m$ polynomial in one go. Semaev provides strong evidence that this step will be amenable to so called Grobner Basis algorithms; by analysing the "first fall degree" assumption for such a system.
The expectation is that this method will be able to "break" various curves in small characteristic currently defined in cryptographic standards. I expect experimental validation of this expectation, or a reason why such experiments fail, to come in the next few months.
UPDATE (23/04/2015):
More updates on this potential algorithm:
UPDATE (23/04/2015):
More updates on this potential algorithm:
No comments:
Post a Comment