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 \(\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
Metadata
- Available format(s)
-
PDF
- 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
- 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}
}