The supersingular isogeny path and endomorphism ring problems are equivalent
This addresses the security foundations for isogeny-based cryptography, providing a rigorous equivalence between key computational problems, which is incremental but essential for the field.
The paper proves that the path-finding problem in ℓ-isogeny graphs and the endomorphism ring problem for supersingular elliptic curves are equivalent under polynomial-time reductions, assuming the generalised Riemann hypothesis, establishing a foundational link for isogeny-based cryptography.
We prove that the path-finding problem in $\ell$-isogeny graphs and the endomorphism ring problem for supersingular elliptic curves are equivalent under reductions of polynomial expected time, assuming the generalised Riemann hypothesis. The presumed hardness of these problems is foundational for isogeny-based cryptography. As an essential tool, we develop a rigorous algorithm for the quaternion analog of the path-finding problem, building upon the heuristic method of Kohel, Lauter, Petit and Tignol. This problem, and its (previously heuristic) resolution, are both a powerful cryptanalytic tool and a building-block for cryptosystems.