Cryptology ePrint Archive: Report 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{\" o}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.

Category / Keywords: public-key cryptography /

Original Publication (with major differences): INDOCRYPT 2014

Date: received 6 Oct 2014, last revised 15 Oct 2014

Contact author: bonjour mit at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20141015:225227 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]