Paper 2014/806

Summation polynomial algorithms for elliptic curves in characteristic two

Steven D. Galbraith and Shishay W. Gebregiyorgis

Abstract

The paper is about the discrete logarithm problem for elliptic curves over characteristic 2 finite fields F_2^n of prime degree n. We consider practical issues about index calculus attacks using summation polynomials in this setting. The contributions of the paper include: a choice of variables for binary Edwards curves (invariant under the action of a relatively large group) to lower the degree of the summation polynomials; a choice of factor base that “breaks symmetry” and increases the probability of finding a relation; an experimental investigation of the use of SAT solvers rather than Gröbner basis methods for solving multivariate polynomial equations over F2. We show that our choice of variables gives a significant improvement to previous work in this case. The symmetry breaking factor base and use of SAT solvers seem to give some benefits in practice, but our experimental results are not conclusive. Our work indicates that Pollard rho is still much faster than index calculus algorithms for the ECDLP (and even for variants such as the oracle-assisted static Diffie-Hellman problem of Granger and Joux-Vitse) over prime extension fields F_2^n of reasonable size.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. INDOCRYPT 2014
Contact author(s)
bonjour mit @ gmail com
History
2014-10-15: revised
2014-10-11: received
See all versions
Short URL
https://ia.cr/2014/806
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/806,
      author = {Steven D.  Galbraith and Shishay W.  Gebregiyorgis},
      title = {Summation polynomial algorithms for elliptic curves in characteristic two},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/806},
      year = {2014},
      url = {https://eprint.iacr.org/2014/806}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.