Paper 2015/986

Bit Coincidence Mining Algorithm

Koh-ichi Nagao

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
ECDLPsubexponential algorithmxL algorithm
Contact author(s)
nagao @ kanto-gakuin ac jp
History
2015-10-12: received
Short URL
https://ia.cr/2015/986
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/986,
      author = {Koh-ichi Nagao},
      title = {Bit Coincidence Mining Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2015/986},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/986}},
      url = {https://eprint.iacr.org/2015/986}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.