On the discrete logarithm problem for prime-field elliptic curves
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, a...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Elsevier
2018
|
| _version_ | 1826296457544597504 |
|---|---|
| author | Amadori, A Pintore, F Sala, M |
| author_facet | Amadori, A Pintore, F Sala, M |
| author_sort | Amadori, A |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T04:16:37Z |
| format | Journal article |
| id | oxford-uuid:c99fdb39-f5b1-428d-999c-770b63363e25 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T04:16:37Z |
| publishDate | 2018 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:c99fdb39-f5b1-428d-999c-770b63363e252022-03-27T07:00:41ZOn the discrete logarithm problem for prime-field elliptic curvesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:c99fdb39-f5b1-428d-999c-770b63363e25Symplectic Elements at OxfordElsevier2018Amadori, APintore, FSala, MIn 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. |
| spellingShingle | Amadori, A Pintore, F Sala, M On the discrete logarithm problem for prime-field elliptic curves |
| title | On the discrete logarithm problem for prime-field elliptic curves |
| title_full | On the discrete logarithm problem for prime-field elliptic curves |
| title_fullStr | On the discrete logarithm problem for prime-field elliptic curves |
| title_full_unstemmed | On the discrete logarithm problem for prime-field elliptic curves |
| title_short | On the discrete logarithm problem for prime-field elliptic curves |
| title_sort | on the discrete logarithm problem for prime field elliptic curves |
| work_keys_str_mv | AT amadoria onthediscretelogarithmproblemforprimefieldellipticcurves AT pintoref onthediscretelogarithmproblemforprimefieldellipticcurves AT salam onthediscretelogarithmproblemforprimefieldellipticcurves |