Cryptology ePrint Archive: Report 2021/676

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

Short URL: ia.cr/2021/676

[ Cryptology ePrint archive ]