Skip to Main content Skip to Navigation
Conference papers

The supersingular isogeny path and endomorphism ring problems are equivalent

Benjamin Wesolowski 1, 2
1 LFANT - Lithe and fast algorithmic number theory
IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : We prove that the path-finding problem in 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.
Complete list of metadata
Contributor : Benjamin Wesolowski Connect in order to contact the contributor
Submitted on : Friday, September 10, 2021 - 2:09:17 PM
Last modification on : Thursday, January 20, 2022 - 4:20:52 PM


Files produced by the author(s)


  • HAL Id : hal-03340899, version 1



Benjamin Wesolowski. The supersingular isogeny path and endomorphism ring problems are equivalent. FOCS 2021 - 62nd Annual IEEE Symposium on Foundations of Computer Science, Feb 2022, Denver, Colorado, United States. ⟨hal-03340899⟩



Les métriques sont temporairement indisponibles