Paper 2024/1569

The Supersingular Isogeny Path and Endomorphism Ring Problems: Unconditional Reductions

Abstract

In this paper we study several computational problems related to current post-quantum cryptosystems based on isogenies between supersingular elliptic curves. In particular we prove that the supersingular isogeny path and endomorphism ring problems are unconditionally equivalent under polynomial time reductions. We show that access to a factoring oracle is sufficient to solve the Quaternion path problem of KLPT and prove that these problems are equivalent, where previous results either assumed heuristics or the generalised Riemann Hypothesis (GRH). Consequently, given Shor’s quantum algorithm for factorisation, our results yield unconditional quantum polynomial reductions between the isogeny path and EndRing problems. Recently these reductions have become foundational for the security of isogeny-based cryptography

Note: Benjamin Wesolowski along with another reviewer spotted a mistake in the proof of theorem 5.1. The ratio of sampling the correct solution is not precisely stated and needs some revision. For the problem of using Cornacchia's algorithm for highly composite integers, this can be easily solved in our particular case by computing the ideal class group and the group of particular S-units or alternatively by an instance of the subset sum problem. As the discriminant of our binary quadratic form is O(log^2 p), this can be done efficiently. The author sincerely thanks Benjamin Wesolowski for his valuable feedback.