Orienteering with One Endomorphism

La Matematica, vol. 2, pp. 523–582

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.

Authors 5

1. Mingjie Chen

   University of Birmingham

   Affiliation as printed

   School of Computer Science, University of Birmingham, University Road West, Birmingham, B15 2TT UK

   School of Computer Science, University of Birmingham, University Road West, Birmingham, B15 2TT, UK

2. Kristin Lauter

   Meta (United States)

   Affiliation as printed

   Facebook AI Research, Meta, Seattle, WA USA

   Facebook AI Research, Meta, Seattle, WA, USA

3. Renate Scheidler

   University of Calgary

   Affiliation as printed

   Department of Mathematics and Statistics, University of Calgary, 2500 University Drive NW, Calgary, Alberta T2N 1N4 Canada

   Department of Mathematics and Statistics, University of Calgary, 2500 University Drive NW, Calgary, Alberta, T2N 1N4, Canada

4. Katherine E. Stange

   University of Colorado Boulder · University of Colorado System

   Affiliation as printed

   Department of Mathematics, University of Colorado, Campus Box 395, Boulder, CO 80309-0395 USA

   Department of Mathematics, University of Colorado, Campus Box 395, Boulder, CO, 80309-0395, USA

5. Ha Thanh Nguyen Tran

   Concordia University of Edmonton

   Affiliation as printed

   Department of Mathematical and Physical Sciences, Concordia University of Edmonton, 7128 Ada Blvd NW, Edmonton, AB T5B 4E4 Canada

   Department of Mathematical and Physical Sciences, Concordia University of Edmonton, 7128 Ada Blvd NW, Edmonton, AB T5B 4E4, Canada