Recorded 26 January 2022. Kirsten Eisentraeger of Pennsylvania State University presents “Classical and quantum algorithms for isogeny problems” at IPAM’s Quantum Numerical Linear Algebra Workshop.
Isogeny-based cryptography is one of a few candidates for post-quantum cryptography. The computational problems relevant for isogeny-based cryptography are usually stated in terms of computing isogenies between elliptic curves, but they have other equivalent formulations. Many can be stated as path finding problems in the supersingular isogeny graph, as a problem in quaternion algebras or as a problem involving group actions. We will discuss known algorithms and where quantum algorithms might provide a speedup.