On the discrete logarithm problem for prime-field elliptic curves

A.G. Amadori, F. Pintore, M. Sala

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
128 Downloads (Pure)

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.

Original languageEnglish
Article number2017/609
Pages (from-to)168-182
Number of pages15
JournalFinite Fields and their Applications
Volume51
DOIs
Publication statusPublished - 1 May 2018

Fingerprint

Discrete Logarithm Problem
Elliptic Curves
Polynomials
Groebner Basis
Multivariate Polynomials
Summation
Exception
Galois field
Composite materials
Composite
Polynomial
Necessary

Keywords

  • Discrete logarithm problem (DLP)
  • Elliptic curve
  • Groebner basis
  • Prime field
  • Summation polynomials

Cite this

@article{3fc32d51a08d4589b923a4619ca167d0,
title = "On the discrete logarithm problem for prime-field elliptic curves",
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.",
keywords = "Discrete logarithm problem (DLP), Elliptic curve, Groebner basis, Prime field, Summation polynomials",
author = "A.G. Amadori and F. Pintore and M. Sala",
year = "2018",
month = "5",
day = "1",
doi = "10.1016/j.ffa.2018.01.009",
language = "English",
volume = "51",
pages = "168--182",
journal = "Finite Fields and their Applications",
issn = "1071-5797",
publisher = "Academic Press Inc.",

}

On the discrete logarithm problem for prime-field elliptic curves. / Amadori, A.G.; Pintore, F.; Sala, M.

In: Finite Fields and their Applications, Vol. 51, 2017/609, 01.05.2018, p. 168-182.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - On the discrete logarithm problem for prime-field elliptic curves

AU - Amadori, A.G.

AU - Pintore, F.

AU - Sala, M.

PY - 2018/5/1

Y1 - 2018/5/1

N2 - 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.

AB - 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.

KW - Discrete logarithm problem (DLP)

KW - Elliptic curve

KW - Groebner basis

KW - Prime field

KW - Summation polynomials

UR - http://www.scopus.com/inward/record.url?scp=85041446194&partnerID=8YFLogxK

U2 - 10.1016/j.ffa.2018.01.009

DO - 10.1016/j.ffa.2018.01.009

M3 - Article

AN - SCOPUS:85041446194

VL - 51

SP - 168

EP - 182

JO - Finite Fields and their Applications

JF - Finite Fields and their Applications

SN - 1071-5797

M1 - 2017/609

ER -