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

Let \({\mathcal E}/\mathbb F_{q^{\ell}}\) be an elliptic curve over a binary field \(\mathbb F_{q^{\ell}}\) with \(q=2^n\), \(\ell\geq 2\) and \((\ell,n)=1\). The Weil descent attack, introduced first by G. Frey and refined by \textit{S. D. Galbraith} and \textit{N. P. Smart} [Lect. Notes Comput. Sci. 1746, 191--200 (1999; Zbl 0981.94025)], transfers the ECDLP on \({\mathcal E}(\mathbb F_{q^{\ell}})\) to the DLP on the Jacobian of a genus-\(g\) hyperelliptic curve \(\mathcal H\) defined over \(\mathbb F_q\). This transfer is useful when the DLP on the Jacobian is easier to solve than the ECDLP on \({\mathcal E}(\mathbb F_{q^{\ell}}),\) which happens when \(g\geq \ell\) and \(g \approx \ell\). \textit{P. Gaudry} et al. [J. Cryptology 15, No. 1, 19--46 (2001; Zbl 0996.94036)] presented an efficient version of this attack, known as GHS Weil descent. Improvements of this method as well as extensions to larger classes of curves have been proposed. In this paper, the authors show that if \(\mathcal E/\mathbb F_{q^{\ell}}\) has a suitable endomorphism \(\psi\) for the Gallant-Lambert-Vanstone (GLV) scalar multiplication technique, then it induces an efficiently computable endomorphism \(\psi^*\) of \(\mbox{Jac}_{\mathcal H}(\mathbb F_q)\). They give an explicit description of this endomorphism, proving it can provide a factor \(n\)-speedup when using index-calculus algorithm for solving the DLP on \(\mbox{Jac}_{\mathcal H}(\mathbb F_q)\). To illustrate this procedure, the authors present an explicit computation of a DLP. They consider a binary GLS elliptic curve introduced by \textit{S. D. Galbraith} et al. [J. Cryptology 24, No. 3, 446--469 (2011; Zbl 1258.94036)], which is equipped with an efficiently computable endomorphism \(\psi\). More precisely, they take the curve over the field \(\mathbb F_{2^{5\cdot 31}}\) given by the equation \[ {\mathcal E}/\mathbb F_{q^{\ell}}: y^2+xy=x^3+x^2+(v^{18}+v^{17}+v^{12}+v^8 +v^5+v^4+1), \] with \(\mathbb F_q=\mathbb F_2[u]/\langle u^5+u^2+1\rangle\) and \(\mathbb F_{q^{\ell}}=\mathbb F_q[v]/\langle v^{31}+v^3+1\rangle\), and consider a discrete logarithm challenge on its group of points. Using the function WeilDescent() of Magma, the authors reduce the problem into a hyperelliptic genus-32 curve of the form \[ {\mathcal H}/\mathbb F_{q}: y^2+h(x)y=f(x). \] To solve the DLP in \(\mbox{Jac}_{\mathcal H}(\mathbb F_{2^5})\), they implemented a parallel version of the Enge-Gaudry algorithm accelerated by means of the endomorphism \(\psi^*\) over \(\mbox{Jac}_{\mathcal H}(\mathbb F_{2^5})\).