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 problemelliptic 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2017/1262}},
      url = {https://eprint.iacr.org/2017/1262}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.