Isogenies and the discrete logarithm problem in Jacobians of genus 3 hyperelliptic curves
type: Item
instance of: scholarly article
title: Isogenies and the discrete logarithm problem in Jacobians of genus 3 hyperelliptic curves
zbMATH Open document ID: 1182.94047
author: J. Blot
published in: Journal of Cryptology
publication date: 2009-11-13T00:00:00Z
review text: 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.
reviewed by: Enric Nart
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 14G50
zbMATH DE Number: 5633136
zbMATH Keywords: discrete logarithm problem
zbMATH Keywords: genus 3
zbMATH Keywords: hyperelliptic curve
zbMATH Keywords: non-hyperelliptic curve
zbMATH Keywords: Jacobian
zbMATH Keywords: isogeny
zbMATH Keywords: trigonal construction
describes a project that uses: Magma
MaRDI profile type: Publication
full work available at URL: s00145-009-9038-1
OpenAlex ID: W2163037042
cites work: Q4830002
cites work: The Magma algebra system. I: The user language
cites work: Q4731294
cites work: Isogenies and duality of abelian varieties
cites work: Algorithmic Number Theory
cites work: The fibers of the Prym map
cites work: The arithmetic-geometric mean and isogenies for curves of higher genus
cites work: A double large prime variation for small genus hyperelliptic index calculus
cites work: Q4195061
cites work: Q4002797
cites work: Computing Riemann-Roch spaces in algebraic function fields and related topics.
cites work: Q4486426
cites work: Number of Points of Varieties in Finite Fields
cites work: An Explicit Formula for the Arithmetic–Geometric Mean in Genus 3
cites work: Q3741712
cites work: Tata lectures on theta. II: Jacobian theta functions and differential equations. With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman, and H. Umemura
cites work: Q3215074
cites work: An improved algorithm for computing logarithms over&lt;tex&gt;GF(p)&lt;/tex&gt;and its cryptographic significance (Corresp.)
cites work: Q4112043
cites work: Q2756583
cites work: Isogenies and the Discrete Logarithm Problem in Jacobians of Genus 3 Hyperelliptic Curves
cites work: Twelve points on the projective line, branched covers, and rational elliptic fibrations
cites work: Q5631239
DOI: 10.1007/S00145-009-9038-1
Recommended article: Translating the discrete logarithm problem on Jacobians of genus 3 hyperelliptic curves with \((\ell ,\ell ,\ell)\)-isogenies
Recommended article: Index calculus attack for Jacobian of hyperelliptic curves of small genus using two large primes
Recommended article: Time-memory trade-offs for index calculus in genus 3
Recommended article: Field extensions and index calculus on algebraic curves
Recommended article: Index calculus in class groups of non-hyperelliptic curves of genus three
Recommended article: Q3374896
Recommended article: Isogenies and the Discrete Logarithm Problem in Jacobians of Genus 3 Hyperelliptic Curves
Recommended article: Index calculus algorithm for non-planar curves
Recommended article: Fast Jacobian arithmetic for hyperelliptic curves of genus 3
Recommended article: Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields
description: scientific article; zbMATH DE number 5633136