Method of
proof uses “Isogeny Graphs”

•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).

•__Mixing Hypothesis:__
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).

Various Elliptic
Curves on the same level

Arrows represent equivalences between DLOG on different curves