2022/01/26 by Sarah Arpin, Arpin, Sarah, Mingjie Chen +9
Biochemistry, Genetics and Molecular Biology · Computer Science · #11-04 #11G05 #14K04 #94A60 #Coding theory and cryptography #Cryptography and Residue Arithmetic #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Microtubule and mitosis dynamics #Number Theory (math.NT) #Primary: 14G50 #Secondary: 11R52
paper · pdf · doi:10.48550/arxiv.2201.11079
openalex publication_date 2022/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.