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

https://hal.archives-ouvertes.fr/hal-03340899
Contributor : Benjamin Wesolowski Connect in order to contact the contributor
Submitted on : Friday, September 10, 2021 - 2:09:17 PM
Last modification on : Saturday, December 4, 2021 - 3:42:54 AM

File

paper.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03340899, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

38

Files downloads

69