HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

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

3 GRACE - Geometry, arithmetic, algorithms, codes and encryption
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
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.
Keywords :
Document type :
Journal articles

https://hal.inria.fr/hal-03233803
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

manuscript.pdf
Files produced by the author(s)

### Citation

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