A+ CATEGORY SCIENTIFIC UNIT

PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

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

Volume 187 / 2019

Dimitar Jetchev, Benjamin Wesolowski Acta Arithmetica 187 (2019), 381-404 MSC: Primary 11G15, 11G25, 11T24, 11T71, 11Y16; Secondary 14G50, 14H40, 14H45, 14K02, 14K22. DOI: 10.4064/aa180316-16-10 Published online: 11 February 2019

Abstract

Fix an ordinary abelian variety defined over a finite field. By complex multiplication, the ideal class group of its endomorphism ring acts freely on the set of isogenous varieties with the same endomorphism ring. 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, Robert and Vuille (2017) for computing explicit cyclic 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 the algorithm to a more general setting including genus 2.

Authors

  • Dimitar JetchevÉcole Polytechnique Fédérale de Lausanne
    EPFL SB GR-JET
    Lausanne, Switzerland
    e-mail
  • Benjamin WesolowskiÉcole Polytechnique Fédérale de Lausanne
    EPFL IC LACAL
    Lausanne, Switzerland
    e-mail

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image