In recent years several papers have appeared that investigate 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. With a notable exception by Petit et al. in 2016, all numerous papers on the subject 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 that reduces to only one the relations to be found among points of the factor base, thus decreasing drastically the necessary Groebner basis computations. Our proposal holds for any finite field but it is particularly suitable for the prime-field case, where it outperforms both the original Semaev’s method and the specialised algorithm by Petit et al..

On the discrete logarithm problem for prime-field elliptic curves / Amadori, Alessandro; Pintore, Federico; Sala, Massimiliano. - In: FINITE FIELDS AND THEIR APPLICATIONS. - ISSN 1071-5797. - STAMPA. - 2018/51:(2018), pp. 168-182. [10.1016/j.ffa.2018.01.009]

On the discrete logarithm problem for prime-field elliptic curves

Pintore, Federico;Sala, Massimiliano
2018-01-01

Abstract

In recent years several papers have appeared that investigate 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. With a notable exception by Petit et al. in 2016, all numerous papers on the subject 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 that reduces to only one the relations to be found among points of the factor base, thus decreasing drastically the necessary Groebner basis computations. Our proposal holds for any finite field but it is particularly suitable for the prime-field case, where it outperforms both the original Semaev’s method and the specialised algorithm by Petit et al..
2018
Amadori, Alessandro; Pintore, Federico; Sala, Massimiliano
On the discrete logarithm problem for prime-field elliptic curves / Amadori, Alessandro; Pintore, Federico; Sala, Massimiliano. - In: FINITE FIELDS AND THEIR APPLICATIONS. - ISSN 1071-5797. - STAMPA. - 2018/51:(2018), pp. 168-182. [10.1016/j.ffa.2018.01.009]
File in questo prodotto:
File Dimensione Formato  
Amadori, Pintore, Sala - On DLP for prime-field EC (rev).pdf

Open Access dal 02/06/2020

Descrizione: Articolo Principale
Tipologia: Post-print referato (Refereed author’s manuscript)
Licenza: Creative commons
Dimensione 287.62 kB
Formato Adobe PDF
287.62 kB Adobe PDF Visualizza/Apri
1-s2.0-S1071579718300091-main.pdf

Solo gestori archivio

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 356.55 kB
Formato Adobe PDF
356.55 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/202653
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 7
social impact