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
-
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},
url = {https://eprint.iacr.org/2017/609}
}
