Séminaire de Théorie Algorithmique des Nombres

Isogeny-based cryptography is founded 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, various 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 some heuristics and subsequently under the Generalized Riemann Hypothesis.

In this talk, we present ongoing joint work with Benjamin Wesolowski, where we unconditionally prove these equivalences, notably using the new tools provided by isogenies in higher dimensions.

Additionally, we show that these problems are also equivalent to finding the lattice of all isogenies between two elliptic curves.

Finally, we demonstrate that if there exist hard instances of the Isogeny problem then all the previously mentioned problems are hard on average.