Paper 2021/676
Extending the GLS endomorphism to speed up GHS Weil descent using Magma
JesúsJavier ChiDomínguez, Francisco RodríguezHenríquez, and Benjamin Smith
Abstract
Let \(q~=~2^n\), and let \(\mathcal{E} / \mathbb{F}_{q^{\ell}}\) be a generalized GalbraithLinScott (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 Weildescent attack applied to \(\mathcal{E} / \mathbb{F}_{q^\ell}\), and that this endomorphism yields a factor$n$ speedup when using standard indexcalculus 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 primeorder 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$ CPUdays.
Note: Preprint accepted to journal Finite Field and their Applications. Acknowledgment extended
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. Minor revision.
 Keywords
 GHS Weil descentextended GLS endomorphismindexcalculus algorithm
 Contact author(s)

jesus dominguez @ tii ae
francisco @ cs cinvestav mx
smith @ lix polytechnique fr  History
 20210610: revised
 20210525: received
 See all versions
 Short URL
 https://ia.cr/2021/676
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/676, author = {JesúsJavier ChiDomínguez and Francisco RodríguezHenríquez and Benjamin Smith}, title = {Extending the GLS endomorphism to speed up GHS Weil descent using Magma}, howpublished = {Cryptology ePrint Archive, Paper 2021/676}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/676}}, url = {https://eprint.iacr.org/2021/676} }