Paper 2017/609

On the discrete logarithm problem for prime-field elliptic curves

Alessandro Amadori, Federico Pintore, and Massimiliano Sala

Abstract

In recent years several papers have appeared investigating the classical discrete logarithm problem for elliptic curves by means of the multivariate polynomial approach based on the celebrated summation polynomials, introduced by Semaev in 2004. However, with a notable exception by Petit et al. in 2016, all numerous papers have investigated only the composite-field case, leaving apart the laborious prime-field case. In this paper we propose a variation of Semaev's original approach for the prime-field case. Our proposal outperforms both the original Semaev's method and Petit et al. specialized algorithm. The improvement is reached by reducing the necessary Groebner basis computations to only one basis calculation.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
elliptic curvediscrete logarithm problemprime fieldsummation polynomialsgroebner basis
Contact author(s)
federico pintore @ unitn it
History
2017-06-26: received
Short URL
https://ia.cr/2017/609
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/609,
      author = {Alessandro Amadori and Federico Pintore and Massimiliano Sala},
      title = {On the discrete logarithm problem for prime-field elliptic curves},
      howpublished = {Cryptology ePrint Archive, Paper 2017/609},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/609}},
      url = {https://eprint.iacr.org/2017/609}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.