Extending the GLS endomorphism to speed up GHS Weil descent using Magma

Jesús-Javier Chi-Domínguez; Francisco Rodríguez-Henríquez; Benjamin Smith

Paper 2021/676

Extending the GLS endomorphism to speed up GHS Weil descent using Magma

Jesús-Javier Chi-Domínguez, Francisco Rodríguez-Henríquez, and Benjamin Smith

Abstract

Let $q = 2^{n}$ , and let $E / F_{q^{ℓ}}$ be a generalized Galbraith--Lin--Scott (GLS) binary curve, with $ℓ \geq 2$ and $(ℓ, n) = 1$ . We show that the GLS endomorphism on $E / F_{q^{ℓ}}$ induces an efficient endomorphism on the Jacobian ${Jac}_{H} (F_{q})$ of the genus- $g$ hyperelliptic curve $H$ corresponding to the image of the GHS Weil-descent attack applied to , and that this endomorphism yields a factor- speedup when using standard index-calculus procedures for solving the Discrete Logarithm Problem (DLP) on . Our analysis is backed up by the explicit computation of a discrete logarithm defined on a prime-order subgroup of a GLS elliptic curve over the field . A Magma implementation of our algorithm finds the aforementioned discrete logarithm in about CPU-days.

Note: Preprint accepted to journal Finite Field and their Applications. Acknowledgment extended

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: GHS Weil descent extended GLS endomorphism index-calculus algorithm
Contact author(s): jesus dominguez @ tii ae
francisco @ cs cinvestav mx
smith @ lix polytechnique fr
History: 2021-06-10: revised; 2021-05-25: received; See all versions
Short URL: https://ia.cr/2021/676
License: CC BY

BibTeX

@misc{cryptoeprint:2021/676,
      author = {Jesús-Javier Chi-Domínguez and Francisco Rodríguez-Henríquez and Benjamin Smith},
      title = {Extending the {GLS} endomorphism to speed up {GHS} Weil descent using Magma},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/676},
      year = {2021},
      url = {https://eprint.iacr.org/2021/676}
}