Cryptology ePrint Archive: Report 2021/919

The supersingular isogeny path and endomorphism ring problems are equivalent

Benjamin Wesolowski

Abstract: 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.

Category / Keywords: public-key cryptography / isogeny-based cryptography, cryptanalysis, endomorphism ring, isogeny path

Original Publication (with minor differences): FOCS 2021

Date: received 7 Jul 2021, last revised 10 Sep 2021

Contact author: benjamin wesolowski at math u-bordeaux fr

Available format(s): PDF | BibTeX Citation

Version: 20210910:121141 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]