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.

Finite Fields and Their Applications, Elsevier, In press, 75