Paper 2024/1569
The Supersingular ℓ-Isogeny Path and Endomorphism Ring Problems: Tighter Unconditional Reductions
, University of WaterlooAbstract
In this paper we show that the supersingular ℓ-isogeny path problem and the endomorphism ring problem are unconditionally equivalent under polynomial-time reductions given access to a factoring oracle. We show access to such oracle is sufficient to solve the Quaternion Path Problem of [KLPT14], removing the heuristic and GRH-based assumptions of previous work. Using Shor’s factorization algorithm, this implies unconditional quantum polynomial-time equivalences between the ℓ-Isogeny Path and Endomorphism Ring problems. Our result strengthens a previous work of Wesolowski’s reduction by removing the Generalized Riemann Hypothesis assumption and achieving polynomial-time equivalences with significantly lower polynomial degree, whereas the original reduction incurs a polynomial overhead of impractically high degree.
Note: A mistake in an earlier version of Theorem 4.1 has been corrected. The author thanks Benjamin Wesolowski for pointing out the error.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- isogeny-based cryptographyendomorphism ring problemisogeny path problemFoundations
- Contact author(s)
- mmamah @ uwaterloo ca
- History
- 2026-01-07: last of 9 revisions
- 2024-10-05: received
- See all versions
- Short URL
- https://ia.cr/2024/1569
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1569,
author = {Maher Mamah},
title = {The Supersingular ℓ-Isogeny Path and Endomorphism Ring Problems: Tighter Unconditional Reductions},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1569},
year = {2024},
url = {https://eprint.iacr.org/2024/1569}
}
