Isogenies and the discrete logarithm problem in Jacobians of genus 3 hyperelliptic curves
Let \(H\) be a hyperelliptic curve of genus \(3\) over a finite field \(\mathbb{F}_q\). The DLP in the Jacobian \(J_H\) of \(H\) can be solved in \(\tilde{O}(q^{4/3})\) group operations, using the index calculus algorithm of \textit{P. Gaudry}, \textit{E. Thomé}, \textit{N. Thériault} and \textit{C. Diem} [Math. Comput. 76, No. 257, 475--492 (2007; Zbl 1179.94062)]. The paper under review presents a procedure to compute a rational isogeny, \(\phi: J_H\longrightarrow J_X\), to the Jacobian of a non-hyperelliptic curve \(X\) of genus \(3\). This facilitates the translation of instances of the DLP from \(J_H\) to \(J_X\), where they can be solved in \(\tilde{O}(q)\) group operations, using the index calculus algorithm of \textit{C. Diem} [Lect. Notes Comput. Sci. 4076, 543--557 (2006; Zbl 1143.11361)]. Under reasonable assumptions, this procedure works with probability 0.1857. The initial curve \(H\) has to admit a Galois stable partition \(S\) of the set of Weierstrass points into four disjoint pairs. The curve \(X\) is obtained by Recilla's trigonal construction with respect to certain trigonal map \(g_S: \mathbb{P}^1 \to \mathbb{P}^1\) depending on \(S\). This determines an isogeny between \(J_H\) and \(J_X\), which is suitable to translate the DLP if \(X\) is non-hyperelliptic, the isogeny is rational, and a model of \(X\) as a plane quartic is available. The whole procedure has been implemented and seems to work very fast in practice.
scientific article; zbMATH DE number 5633136
scientific article