Paper 2022/098

Orienteering with one endomorphism

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


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. Minor revision.
supersingularisogenyelliptic curvepath-findingorientation
Contact author(s)
kstange @ math colorado edu
klauter @ fb com
2022-03-10: revised
2022-01-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sarah Arpin and Mingjie Chen and Kristin E.  Lauter and Renate Scheidler and Katherine E.  Stange and Ha T.  N.  Tran},
      title = {Orienteering with one endomorphism},
      howpublished = {Cryptology ePrint Archive, Paper 2022/098},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.