[cryptography] New algorithm for the discrete logarithm problem on elliptic curves

Alexander Klimov alserkli at inbox.ru
Tue Apr 7 07:31:43 EDT 2015


Although calculating the exact time/memory complexity of algorithms 
based on the Grobner basis is not easy, the new approach is 
interesting:

  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. 

<http://eprint.iacr.org/2015/310.pdf> or
<http://arxiv.org/pdf/1504.01175v1>

-- 
Regards,
ASK


More information about the cryptography mailing list