Computing the Endomorphism Ring of a Supersingular Elliptic Curve from a Full Rank Suborder

In this paper, we study the problem of computing the endomorphism ring of a supersingular elliptic curve given the knowledge of a full rank suborder. We provide a polynomial time quantum algorithm to solve this problem in full generality. This result enhances our understanding of the endomorphism ring problem, which is at the core of isogeny-based cryptography. As part of our approach, we also present a polynomial time quantum algorithm to solve the problem of computing the endomorphism ring of the codomain curve of an isogeny from a curve with known endomorphism ring. This extends the work of [CII + 23a] by lifting their restrictions on the number of factors of the isogeny degree. As an application, we present quantum reductions between key hard problems in isogeny-based cryptography. We show that some of our quantum reductions are tighter than the classical ones, while all reductions are of polynomial time complexity. In particular, we improve the query complexity of the reduction of the EndRing problem to the OneEnd problem from poly(log p) (classically) to O(1) (quantumly), strengthening the hardness assumption of the OneEnd problem in the post-quantum setting. This reduction underlies the 2-special soundness proof of SQIsign identification protocols.