Orienteering with One Endomorphism.

Area of Science:

• Number Theory
• Cryptography
• Post-Quantum Cryptography

Background:

• Supersingular isogeny-based cryptography relies on solving the path-finding problem, often linked to the endomorphism ring problem.
• A known endomorphism can simplify path-finding and endomorphism ring computation in supersingular elliptic curves.

Purpose of the Study:

• To investigate if path-finding can be achieved using a single endomorphism.
• To develop general path-finding algorithms for supersingular isogeny graphs without assuming knowledge of the primitive order.

Main Methods:

• Utilizing the volcano structure of oriented supersingular isogeny graphs to perform graph traversal (ascending/descending/horizontal steps).
• Introducing and solving a new hard problem: computing the primitive order from an endomorphism.
• Developing a sub-exponential quantum algorithm for the new primitive order computation problem.

Main Results:

• Path-finding algorithms are deduced by navigating the volcano structure of supersingular isogeny graphs.
• A new computationally hard problem related to primitive orders and endomorphisms is introduced.
• A quantum algorithm with sub-exponential complexity is presented for solving this new problem.

Conclusions:

• The proposed path-finding algorithms are more general than prior methods as they do not require prior knowledge of the primitive order.
• The research contributes to understanding the relationship between endomorphisms, primitive orders, and path-finding in supersingular isogeny cryptography.
• The introduction of a new hard problem and a quantum algorithm advances the study of isogeny-based cryptosystems.