Welcome to the resource topic for 2016/924
Title:
Bit Coincidence Mining Algorithm II
Authors: 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.
ePrint: https://eprint.iacr.org/2016/924
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .