Paper 2004/031

Summation polynomials and the discrete logarithm problem on elliptic curves

Igor Semaev

Abstract

The aim of the paper is the construction of the index calculus algorithm for the discrete logarithm problem on elliptic curves. The construction presented here is based on the problem of finding bounded solutions to some explicit modular multivariate polynomial equations. These equations arise from the elliptic curve summation polynomials introduced here and may be computed easily. Roughly speaking, we show that given the algorithm for solving such equations, which works in polynomial or low exponential time in the size of the input, one finds discrete logarithms faster than by means of Pollard's methods.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. submitted to Crypto 2004
Keywords
elliptic curvessummation polynomialsthe discrete logarithm problem
Contact author(s)
Igor Semaev @ wis kuleuven ac be
History
2004-02-05: received
Short URL
https://ia.cr/2004/031
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/031,
      author = {Igor Semaev},
      title = {Summation polynomials and the discrete logarithm problem on elliptic curves},
      howpublished = {Cryptology ePrint Archive, Paper 2004/031},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/031}},
      url = {https://eprint.iacr.org/2004/031}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.