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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
supersingularisogenyelliptic curvepath-findingorientation
Contact author(s)
kstange @ math colorado edu
klauter @ fb com
History
2022-03-10: revised
2022-01-31: received
See all versions
Short URL
https://ia.cr/2022/098
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/098,
      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{https://eprint.iacr.org/2022/098}},
      url = {https://eprint.iacr.org/2022/098}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.