Orienteering with one endomorphism

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? Our Women in Numbers 5 (WIN5) working group investigated these questions in our study of oriented supersingular elliptic curves. An endomorphism gives an explicit orientation of a supersingular elliptic curve. It is known that a small endomorphism enables polynomial-time path-finding and endomorphism ring computation (Love-Boneh 2019). As our paper neared completion, it was shown that the endomorphism ring problem in the presence of one known endomorphism reduces to a vectorization problem (Wesolowski 2021). In our paper, we give explicit classical and quantum algorithms for path-finding to an initial curve using the knowledge of one endomorphism. 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.

Back to Search Research Symposium Abstracts