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

We prove that the supersingular <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℓ</mml:mi> </mml:mrow> </mml:math> -isogeny path problem and the endomorphism ring problem are equivalent via polynomial-time reductions given access to a factoring oracle. Prior work related the endomorphism ring problem to the general isogeny path problem, but the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℓ</mml:mi> </mml:mrow> </mml:math> -isogeny path case remained open unconditionally. We show that a factoring oracle suffices to solve the quaternion path problem of Kohel, Lauter, Petit, and Tignol, replacing previous heuristic or GRH-based assumptions in the core reduction. Combined with Shor's factoring algorithm, this gives quantum polynomial-time equivalences between <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℓ</mml:mi> </mml:mrow> </mml:math> -isogeny path and endomorphism ring, with substantially lower polynomial degree, whereas the original reduction incurs a polynomial overhead of impractically high degree.