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

*Jesús-Javier Chi-Domínguez and 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.

**Category / Keywords: **public-key cryptography / GHS Weil descent, extended GLS endomorphism, index-calculus algorithm

**Date: **received 24 May 2021, last revised 10 Jun 2021

**Contact author: **jesus dominguez at tii ae, francisco at cs cinvestav mx, smith at lix polytechnique fr

**Available format(s): **PDF | BibTeX Citation

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

**Version: **20210610:134407 (All versions of this report)

**Short URL: **ia.cr/2021/676

[ Cryptology ePrint archive ]