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 web-site 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)
PDF
Publication info
Preprint. MINOR revision.
Keywords
discrete logarithm problemelliptic curve cryptosystem
Contact author(s)
igor @ ii uib no
History
2015-04-10: revised
2015-04-06: received
See all versions
Short URL
https://ia.cr/2015/310
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.