Paper 2016/924

Bit Coincidence Mining Algorithm II

Koh-ichi Nagao

Abstract

In 2012, Petit et al. shows that under the algebraic geometrical assumption named "First Fall degree Assumption", the complexity of ECDLP over binary extension field ${\bf F}_{2^n}$ is in $O(exp(n^{2/3+o(1)}))$ where $\lim_{n \to \infty} o(1)=0$ and there are many generalizations and improvements for the complexity of ECDLP under this assumption. In 2015, the author proposes the bit coincidence mining algorithm, which states that under the heuristic assumption of the complexity of xL algorithm, the complexity of ECDLP $E/{\bf F}_q$ over arbitrary finite field including prime field, is in $O(exp(n^{1/2+o(1)}))$ where $n \sim \log_2 \#E({\bf F}_q) \sim \log_2 q$. It is the first (heuristic) algorithm for solving ECDLP over prime field in subexponential complexity. In both researches, ECDLP reduces to solving large equations system and from each assumption, the complexity for solving reduced equations system is subexponential (or polynomial) complexity. However, the obtained equations system is too large for solving in practical time and space, they are only the results for the complexity. xL algorithm, is the algorithm for solving quadratic equations system, which consists of $n$ variables and $m$ equations. Here, $n$ and $m$ are considered as parameters. Put $D=D(n,m)$ by the maximal degree of the polynomials, which appears in the computation of solving equations system by xL. Courtois et al. observe and assume the following assumption; 1) There are small integer $C_0$, such that $D(n,n+C_0)$ is usually in $O(\sqrt{n})$, and the cost for solving equations system is in $O(exp(n^{1/2+0(1)}))$. However, this observation is optimistic and it must have the following assumption 2) The equations system have small number of the solutions over algebraic closure. (In this draft we assume the number of the solutions is 0 or 1) In the previous version's bit coincidence mining algorithm (in 2015), the number of the solutions of the desired equations system over algebraic closure is small and it can be probabilistically controlled to be 1 and the assumption 2) is indirectly true. For my sense, the reason that xL algorithm, which is the beautiful heuristic, is not widely used is that the general equations system over finite field does not satisfy the assumption 2) (there are many solutions over algebraic closure) and is complexity is much larger. In the previous draft, I show that the ECDLP of $E({\bf F}_q)$ reduces to solving equations system consists of $d-1$ variables and $d+C_0-1$ equations where $C_0$ is an arbitrary positive integer and $d \sim C_0 \times \log_2 q$. So, the complexity for solving ECDLP is in subexponential under the following assumption a) There are some positive integer $C_0$ independent from $n$, such that solving quadratic equations system consists of $n$ variables and $m=n+C_0$ equations (and we must assume the assumption 2)) by xL algorithm, the maximum degree of the polynomials $D=D(n,m)$, appears in this routine is in $O(\sqrt{n})$ in high probability. Here, we propose the new algorithm that ECDLP of $E({\bf F}_q)$ is essentially reducing to solving equations system consists of $d-1$ variables and $\frac{b_0}{2}d$ equations where $b_0(\ge 2)$ is an arbitrary positive integer named block size and $d \sim (b_0-1)\log_{b_0} q$. Here, we mainly treat the case block size $b_0=3$. In this case, ECDLP is essentially reducing to solving equations system consists of about $2 \log_3 q$ variables and $3 \log_3 q$ equations. So that the desired assumption 1) is always true. Moreover, the number of the solutions (over algebraic closure) of this equations system can be probabilistically controlled to be 1 and the desired assumption 2) is also true. In the former part of this manuscript, the author states the algorithm for the construction of equations system that ECDLP is reduced and in the latter part of this manuscript, the author state the ideas and devices in order for increasing the number of the equations, which means the obtained equations system is easily solved by xL algorithm.