A New  Index Calculus Algorithm for the Elliptic Curve Discrete Logarithm Problem and Summation Polynomial Evaluation

Gary McGuire; Daniela Mueller

Paper 2017/1262

A New Index Calculus Algorithm for the Elliptic Curve Discrete Logarithm Problem and Summation Polynomial Evaluation

Gary McGuire and Daniela Mueller

Abstract

The introduction of summation polynomials for elliptic curves by Semaev has opened up new avenues of investigation in index calculus type algorithms for the elliptic curve discrete logarithm problem, and several recent papers have explored their use. We propose an index calculus algorithm to solve the Elliptic Curve Discrete Logarithm Problem that makes use of a technique for fast evaluation of the summation polynomials, and unlike all other algorithms using summation polynomials, does not involve a Gröbner basis computation. We further propose another algorithm that does not involve Gröbner basis computations or summation polynomials. We give a complexity estimate of our algorithms and provide extensive computational data.

Note: Presentation improved and Lemma 5.10 added.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Keywords: discrete logarithm problem elliptic curve cryptosystem
Contact author(s): gary mcguire @ ucd ie
History: 2018-08-08: last of 2 revisions; 2017-12-31: received; See all versions
Short URL: https://ia.cr/2017/1262
License: CC BY

BibTeX

@misc{cryptoeprint:2017/1262,
      author = {Gary McGuire and Daniela Mueller},
      title = {A New  Index Calculus Algorithm for the Elliptic Curve Discrete Logarithm Problem and Summation Polynomial Evaluation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/1262},
      year = {2017},
      url = {https://eprint.iacr.org/2017/1262}
}