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

An isogeny graph is a graph whose vertices are abelian varieties (typically elliptic curves, or Jacobians of genus 2 hyperelliptic curves) and whose edges are isogenies between them. Such a graph is "horizontal" if all the abelian varieties have the same endomorphism ring. We study the connectivity and the expander properties of these graphs. We use these results, together with a recent algorithm for computing explicit isogenies in genus 2, to prove random self-reducibility of the discrete logarithm problem for Jacobians of genus 2 hyperelliptic curves 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.