Paper 2022/098

Orienteering with one endomorphism

Sarah Arpin, Universiteit Leiden
Mingjie Chen, University of Birmingham
Kristin E. Lauter, Facebook AI Research, Meta
Renate Scheidler, University of Calgary
Katherine E. Stange
Ha T. N. Tran, Concordia University of Edmonton

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]). An endomorphism gives an explicit orientation of a supersingular elliptic curve. In this paper, we use the volcano structure of the oriented supersingular isogeny graph to take ascending/descending/horizontal steps on the graph and deduce path-finding algorithms to an initial curve. Each altitude of the volcano corresponds to a unique quadratic order, called the primitive order. We introduce a new hard problem of computing the primitive order given an arbitrary endomorphism on the curve, and we also provide a sub-exponential quantum algorithm for solving it. In concurrent work (Wesolowski [54]), it was shown that the endomorphism ring problem in the presence of one endomorphism with known primitive order reduces to a vectorization problem, implying path-finding algorithms. Our path-finding algorithms are more general in the sense that we don't assume the knowledge of the primitive order associated with the endomorphism.

Available format(s)
Public-key cryptography
Publication info
supersingular isogeny elliptic curve path-finding orientation
Contact author(s)
Sarah Arpin @ colorado edu
m chen 1 @ bham ac uk
klauter @ fb com
rscheidl @ ucalgary ca
kstange @ math colorado edu
hatran1104 @ gmail com
2022-10-19: last of 2 revisions
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.