Paper 2024/1569 Original: eprint.iacr.org/2024/1569 ↗

The Supersingular ℓ-Isogeny Path and Endomorphism Ring Problems: Tighter Unconditional Reductions

Abstract

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.