International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 06 April 2015

Igor Semaev
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.