Paper 2015/310
New algorithm for the discrete logarithm problem on elliptic curves
Igor Semaev
Abstract
A new algorithms for computing discrete logarithms on elliptic curves defined over finite fields is suggested. It is based on a new method to find zeroes of summation polynomials. In binary elliptic curves one is to solve a cubic system of Boolean equations. Under a first fall degree assumption the regularity degree of the system is at most $4$. Extensive experimental data which supports the assumption is provided. An heuristic analysis suggests a new asymptotical complexity bound $2^{c\sqrt{n\ln n}}, c\approx 1.69$ for computing discrete logarithms on an elliptic curve over a field of size $2^n$. For several binary elliptic curves recommended by FIPS the new method performs better than Pollard's. The asymptotical bound is correct under a weaker assumption that the regularity degree is bounded by $o(\sqrt{\frac{n}{\ln n}})$ though the conclusion on the security of FIPS curves does not generally hold in this case.
Note: A new section is added, it is shown that the asymptotical bound for ECDLP in binary elliptic curves depends on a much weaker assumption not related to any first fall degree assumptions. Since the first version appeared on the IACR website several people sent me their unpublished works which exploit similar ideas though without asymptotical analysis of the ECDLP. I have now acknowledged this.
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 discrete logarithm problemelliptic curve cryptosystem
 Contact author(s)
 igor @ ii uib no
 History
 20150410: revised
 20150406: received
 See all versions
 Short URL
 https://ia.cr/2015/310
 License

CC BY
BibTeX
@misc{cryptoeprint:2015/310, author = {Igor Semaev}, title = {New algorithm for the discrete logarithm problem on elliptic curves}, howpublished = {Cryptology ePrint Archive, Paper 2015/310}, year = {2015}, note = {\url{https://eprint.iacr.org/2015/310}}, url = {https://eprint.iacr.org/2015/310} }