Welcome to the resource topic for 2015/310
Title:
New algorithm for the discrete logarithm problem on elliptic curves
Authors: 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.
ePrint: https://eprint.iacr.org/2015/310
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 .