HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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

Abstract : Let $q = 2^n$, and let $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 $E / \mathbb{F}_{q^{\ell}}$ induces an efficient endomorphism on the Jacobian $J_H(\mathbb{F}_q)$ of the genus-$g$ hyperelliptic curve $H$ corresponding to the image of the GHS Weil-descent attack applied to $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 $J_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.
Document type :
Journal articles
Complete list of metadata

Contributor : Benjamin Smith Connect in order to contact the contributor
Submitted on : Thursday, June 17, 2021 - 10:19:08 AM
Last modification on : Friday, April 1, 2022 - 3:56:15 AM
Long-term archiving on: : Saturday, September 18, 2021 - 6:04:28 PM


Files produced by the author(s)



Jesús-Javier Chi-Domínguez, Francisco Rodríguez-Henríquez, Benjamin Smith. Extending the GLS endomorphism to speed up GHS Weil descent using Magma. Finite Fields and Their Applications, Elsevier, inPress, 75, ⟨10.1016/j.ffa.2021.101891⟩. ⟨hal-03233803⟩



Record views


Files downloads