Horizontal isogeny graphs of ordinary abelian varieties and the discrete logarithm problem

DOI10.4064/AA180316-16-10MaRDI QIDQ5376571zbMATH OpenOpenAlexWikidataFDO

Authors Dimitar Jetchev, Benjamin Wesolowski

Publication date 13 May 2019

Published in Acta Arithmetica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.00522

zbMATH Keywords

discrete logarithmisogenyhyperelliptic curve cryptographyexpander graphrandom self-reducibility

Mathematics Subject Classification ID

Complex multiplication and moduli of abelian varieties (11G15) Varieties over finite and local fields (11G25) Jacobians, Prym varieties (14H40) Other character sums and Gauss sums (11T24) Applications to coding theory and cryptography of arithmetic geometry (14G50) Isogeny (14K02) Complex multiplication and abelian varieties (14K22)

Abstract: Fix an ordinary abelian variety defined over a finite field. The ideal class group of its endomorphism ring acts freely on the set of isogenous varieties with same endomorphism ring, by complex multiplication. Any subgroup of the class group, and generating set thereof, induces an isogeny graph on the orbit of the variety for this subgroup. We compute (under the Generalized Riemann Hypothesis) some bounds on the norms of prime ideals generating it, such that the associated graph has good expansion properties. We use these graphs, together with a recent algorithm of Dudeanu, Jetchev and Robert for computing explicit isogenies in genus 2, to prove random self-reducibility of the discrete logarithm problem within the subclasses of principally polarizable ordinary abelian surfaces with fixed endomorphism ring. In addition, we remove the heuristics in the complexity analysis of an algorithm of Galbraith for explicitly computing isogenies between two elliptic curves in the same isogeny class, and extend it to a more general setting including genus 2.

Recommendations

• Isogeny graphs of ordinary abelian varieties
• Automorphisms and isogeny graphs of abelian varieties, with applications to the superspecial Richelot isogeny graph
• Cyclic isogenies for abelian varieties with real multiplication
• Isogeny graphs with maximal real multiplication
• Isogenies and the Discrete Logarithm Problem in Jacobians of Genus 3 Hyperelliptic Curves

Cites work

• scientific article; zbMATH DE number 3181290 (Why is no real title available?)
• Computing $(\ell ,\ell )$-isogenies in polynomial time on Jacobians of genus $2$ curves
• Endomorphisms of Abelian varieties over finite fields

Cited in

(6)

• Isogeny graphs with maximal real multiplication
• Explicit Isogenies of Prime Degree Over Quadratic Fields
• Isogeny graphs of ordinary abelian varieties
• Computing the endomorphism ring of an ordinary abelian surface over a finite field
• Isogenous hyperelliptic and non-hyperelliptic Jacobians with maximal complex multiplication
• Cyclic isogenies for abelian varieties with real multiplication

This page was built for publication: Horizontal isogeny graphs of ordinary abelian varieties and the discrete logarithm problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5376571)