Unconditional foundations for supersingular isogeny-based cryptography
Isogeny-based cryptography relies on the assumption that the Isogeny Problem—finding an isogeny between two given elliptic curves—is a hard problem, even for quantum computers. In the security analysis of isogeny-based schemes, several related problems naturally arise, such as computing the endomorphism ring of an elliptic curve or determining a maximal quaternion order isomorphic to it. These problems have been shown to be equivalent to the Isogeny Problem, first under certain heuristics and later under the Generalized Riemann Hypothesis.
In this talk, we present ongoing joint work with Benjamin Wesolowski, in which we unconditionally prove these equivalences, notably using the new tools provided by isogenies in higher dimensions. We further demonstrate that these problems are also equivalent to finding the lattice of all isogenies between two elliptic curves. Finally, we show that if hard instances of the Isogeny problem exist, then all the previously mentioned problems are hard on average.