Paper 2022/098
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? 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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- 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 - History
- 2022-10-19: last of 2 revisions
- 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},
url = {https://eprint.iacr.org/2022/098}
}