Classical and Quantum Algorithms for Isogeny Problems

Explore classical and quantum algorithms for isogeny problems in this conference talk by Kirsten Eisentraeger at IPAM's Quantum Numerical Linear Algebra Workshop. Delve into the world of isogeny-based cryptography, a promising candidate for post-quantum security. Examine computational challenges in isogeny-based systems, including path finding in isogeny graphs and computing with isogenies. Discover how these problems can be reformulated in terms of quaternion algebras and group actions. Compare traditional elliptic curve cryptography with isogeny-based approaches, and learn about the current security status of isogeny-based crypto. Investigate potential quantum algorithm speedups and their implications for cryptographic security. Gain insights into commutative and non-commutative isogeny crypto, reductions to endomorphism ring problems, and the overall landscape of isogeny-based cryptographic systems.

Intro
POST-QUANTUM
ELLIPTIC CURVES AND
TRADITIONAL ELLIPTIC CURVE CRYPTOGRAPHY VERSUS ISOGENIES
WHY SUPERSINGULAR ISOGENY CRYPTO?
HARDNESS ASSUMPTIONS IN PUBLIC-KEY CRYPTOGRAPHY
ISOGENY-BASED SYSTEMS
STATUS OF SECURITY OF ISOGENY-BASED CRYPTO
COMPUTATIONAL CHALLENGES
PATH FINDING IN ISOGENY GRAPHS
COMPUTING WITH ISOGENIES
REDUCTIONS TO OTHER PROBLEMS
COMMUTATIVE ISOGENY SCHEMES
REDUCTIONS-COMMUTATIVE CASE
COMMUTATIVE VERSUS NON- COMMUTATIVE ISOGENY CRYPTO
REDUCTIONS TO ENDOMORPHISM RING PROBLEM
CONCLUSION
SUMMARY