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
-
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} }