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

DOI10.4064/AA180316-16-10zbMATH Open1441.11160arXiv1506.00522OpenAlexW2963817850WikidataQ128420296 ScholiaQ128420296MaRDI QIDQ5376571FDOQ5376571

Authors: Dimitar Jetchev, Benjamin Wesolowski 

Publication date: 13 May 2019

Published in: Acta Arithmetica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Computing $(\ell ,\ell )$-isogenies in polynomial time on Jacobians of genus $2$ curves
• Endomorphisms of Abelian varieties over finite fields
• Title not available (Why is that?)

Cited In (6)

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

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)