### 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.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.FOCS 2021
Keywords
isogeny-based cryptographycryptanalysisendomorphism ringisogeny path
Contact author(s)
benjamin wesolowski @ math u-bordeaux fr
History
2021-09-10: revised
See all versions
Short URL
https://ia.cr/2021/919

CC BY

BibTeX

@misc{cryptoeprint:2021/919,
author = {Benjamin Wesolowski},
title = {The supersingular isogeny path and endomorphism ring problems are equivalent},
howpublished = {Cryptology ePrint Archive, Paper 2021/919},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/919}},
url = {https://eprint.iacr.org/2021/919}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.