Quantum Algorithms and Post-Quantum Cryptography

Explore quantum algorithms and post-quantum cryptography in this 49-minute lecture by Sean Hallgren from Pennsylvania State University, part of the Quantum Wave in Computing Boot Camp at the Simons Institute. Delve into exponential speedups for oracle problems, NIST's post-quantum cryptography standardization efforts, and the development of new cryptographic systems. Examine the search for hard problems in cryptography, focusing on lattices and quantum algorithms. Investigate the quantum algorithm for the unit group, special cases of lattices, and the challenges of finding short generators. Consider alternative bases for post-quantum cryptography, including the hard isogeny problem and its related graph structures. Analyze the security of isogeny-based cryptography, computational challenges, and hardness assumptions. Conclude with an exploration of finding cycles in the isogeny graph using structure and a comprehensive summary of key concepts.

Intro
Exponential Speedups for Oracle Problems
NIST Post-Quantum Cryptography Standardization
Developing New Systems
Looking for Hard Problems for Crypto
Back to Lattices and Quantum Algorithms
What Makes Good Crypto?
Lattices, Cryptography, and Quantum Algorithms
Quantum Algorithm for the Unit Group
Special Cases of Lattices
The Unit Group and Finding Short Generators
Computing the Short Generator
Quantum Algorithm for Lattices?
What Else Can be used for Post-Quantum Crypto?
Crypto and Algorithms
Hard Isogeny Problem
The isogeny problem
The supersingular -isogeny graph
Two types of isogeny graphs
More Assumptions for Efficiency
How Secure is Isogeny-Based Crypto?
Computational Challenges
Three hardness assumptions
Finding Cycles in the Isogeny Graph using Structure
Summary