•Low degree isogenies
between elliptic curves
provide explicit polynomial time reductions
between the curves they connect.
•An “isogeny graph” is a graph whose vertices represent all the elliptic curves on a given level, and whose edges represent low degree isogenies (of degree (log
q)2+e, e > 0).
suppose that the random walk
on this graph mixes rapidly
(i.e. after polylog(q) steps one reaches
any vertex with uniform probability
up to a small error). This is proven using GRH.
•Then by computing
random low degree isogenies, DLOG can be explicitly reduced between any two curves on that level.
•Therefore DLOG has uniform difficulty on this level (assuming the Mixing Hypothesis).
Curves on the same level
Arrows represent equivalences between DLOG on different curves