Summation polynomials and the discrete logarithm problem on elliptic curves

Igor Semaev

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 curves summation polynomials the 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: 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},
      url = {https://eprint.iacr.org/2004/031}
}