Paper 2022/098

Orienteering with one endomorphism

Sarah Arpin, Mingjie Chen, Kristin E. Lauter, Renate Scheidler, Katherine E. Stange, and Ha T. N. Tran

Abstract

In supersingular isogeny-based cryptography, the path-finding problem reduces to the endomorphism ring problem. Can path-finding be reduced to knowing just one endomorphism? It is known that a small endomorphism enables polynomial-time path-finding and endomorphism ring computation (Love-Boneh [36]). As this paper neared completion, it was shown that the endomorphism ring problem in the presence of one known endomorphism reduces to a vectorization problem (Wesolowski [54]). In this paper, we give explicit classical and quantum algorithms for path-finding to an initial curve using the knowledge of one endomorphism. An endomorphism gives an explicit orientation of a supersingular elliptic curve. We use the theory of oriented supersingular isogeny graphs and algorithms for taking ascending/descending/horizontal steps on such graphs. Although the most general runtimes are subexponential, we demonstrate a class of (potentially large) endomorphisms, for any supersingular elliptic curve, for which the classical runtime is polynomial.