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.