Cryptology ePrint Archive: Report 2017/609

On the discrete logarithm problem for prime-field elliptic curves

Alessandro Amadori and 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.

Category / Keywords: public-key cryptography / elliptic curve, discrete logarithm problem, prime field, summation polynomials, groebner basis

Date: received 23 Jun 2017

Contact author: federico pintore at unitn it

Available format(s): PDF | BibTeX Citation

Version: 20170626:154915 (All versions of this report)

Short URL: ia.cr/2017/609

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]