Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2023;2(3):523-582.
doi: 10.1007/s44007-023-00053-2. Epub 2023 Jun 20.

Orienteering with One Endomorphism

Sarah Arpin  1 , Mingjie Chen  2 , Kristin E Lauter  3 , Renate Scheidler  4 , Katherine E Stange  5 , Ha T N Tran  6
Affiliations

Orienteering with One Endomorphism

Sarah Arpin et al. Mathematica (N Y). 2023.

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 degree endomorphism enables polynomial-time path-finding and endomorphism ring computation (in: Love and Boneh, ANTS XIV-Proceedings of the Fourteenth Algorithmic Number Theory Symposium, volume 4 of Open Book Ser. Math. Sci. Publ., Berkeley, 2020). 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 (in: Wesolowski, Advances in cryptology-EUROCRYPT 2022, volume 13277 of Lecture Notes in Computer Science. Springer, Cham, 2022), 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.

Keywords: Elliptic curve; Endomorphism ring; Orientation; Path-finding; Supersingular isogeny graph; Vectorization.

PubMed Disclaimer

Conflict of interest statement

Conflict of interestOn behalf of all authors, the corresponding author states that there is no conflict of interest.

Figures

Fig. 1
Fig. 1
On the left hand side is a component of GK for p=179, ℓ=2 and K=Q(-47). On the right hand side is the supersingular 2-isogeny graph over Fp2. Here j1=64i+5,j2=99i+107,j3=5i+109, where i denotes a root of -1 in Fp2. Since the oriented graph is undirected while the supersingular isogeny graph is directed, we have undirected edges in the left graph and directed edges in the right graph. Note that the green 5-cycle represents the rim of the volcano
See this image and copyright information in PMC

References

    1. Apostol TM. Introduction to Analytic Number Theory. New York-Heidelberg: Springer-Verlag; 1976.
    1. Arpin, S., Chen, M., Lauter, K.E., Scheidler, R., Stange, K.E., Tran, H.T.N.: Orientations and cycles in supersingular isogeny graphs. arXiv:2205.03976 (2022)
    1. Arpin, S., Chen, M., Lauter, K.E., Scheidler, R., Stange, K.E., Tran, H.T.N.: WIN5 github repository. https://github.com/SarahArpin/WIN5 (2022)
    1. Bank E, Camacho-Navarro C, Eisenträger K, Morrison T, Park J. Research Directions in Number Theory. Berlin: Springer; 2019. Cycles in the supersingular l-isogeny graph and corresponding endomorphisms; pp. 41–66.
    1. Biasse J-F, Iezzi A, Jacobson MJ. A note on the security of csidh. In: Chakraborty D, Iwata T, editors. Progress in Cryptology - INDOCRYPT 2018. Cham: Springer International Publishing; 2018. pp. 153–168.

LinkOut - more resources