### 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 $$\mathcal{E} / \mathbb{F}_{q^{\ell}}$$ be a generalized Galbraith--Lin--Scott (GLS) binary curve, with $\ell \ge 2$ and $$(\ell, n) = 1$$. We show that the GLS endomorphism on $$\mathcal{E} / \mathbb{F}_{q^{\ell}}$$ induces an efficient endomorphism on the Jacobian $$\mathrm{Jac}_\mathcal{H}(\mathbb{F}_q)$$ of the genus-$$g$$ hyperelliptic curve $$\mathcal{H}$$ corresponding to the image of the GHS Weil-descent attack applied to $$\mathcal{E} / \mathbb{F}_{q^\ell}$$, and that this endomorphism yields a factor-$n$ speedup when using standard index-calculus procedures for solving the Discrete Logarithm Problem (DLP) on $$\mathrm{Jac}_\mathcal{H}(\mathbb{F}_q)$$. 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 $\mathbb{F}_{2^{5\cdot 31}}$. A Magma implementation of our algorithm finds the aforementioned discrete logarithm in about $1,035$ CPU-days.

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

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
GHS Weil descentextended GLS endomorphismindex-calculus algorithm
Contact author(s)
jesus dominguez @ tii ae
francisco @ cs cinvestav mx
smith @ lix polytechnique fr
History
2021-06-10: revised
See all versions
Short URL
https://ia.cr/2021/676

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},
note = {\url{https://eprint.iacr.org/2021/676}},
url = {https://eprint.iacr.org/2021/676}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.