Cryptology ePrint Archive: Report 2015/986
Bit Coincidence Mining Algorithm
Abstract: Here, we propose new algorithm for solving ECDLP named "Bit Coincidence Mining Algorithm!", from which ECDLP is reduced to solving some quadratic equations system.
In this algorithm, ECDLP of an elliptic curve $E$ defined over $\bF_q$ ($q$ is prime or power of primes) reduces to solving quadratic equations system of $d-1$ variables and $d+C_0-1$ equations where $C_0$ is small natural number and $d \sim C_0 \, \log_2 q$.
This equations system is too large and it can not be solved by computer.
However, we can show theoritically the cost for solving this equations system by xL algorithm is subexponential under the reasonable assumption of xL algorithm.
Category / Keywords: foundations / ECDLP, subexponential algorithm, xL algorithm
Date: received 11 Oct 2015
Contact author: nagao at kanto-gakuin ac jp
Available format(s): PDF | BibTeX Citation
Version: 20151012:211752 (All versions of this report)
Short URL: ia.cr/2015/986
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]