Quantum 2

on YouTube ↗58m

" summary

Explains why lattice problems (SVP/CVP and LWE-style matrices) are the leading post-quantum tools, proves simple PRG composition still holds against QPT adversaries, and shows classical rewinding breaks because of no-cloning and measurement disturbance so coin‑tossing proofs fail. Replaces binding with the collapsing commitment experiment, gives constructions from lossy functions and ROM reductions, proves rewinding fixes under collapsing, and catalogues open questions about quantum hardness, group actions, and collision time/space tradeoffs.

AI-written summary · about

" chapters (7)

1. 0:00Post-quantum cryptography intro
2. 6:30Lattices and security
3. 10:27Security proofs in quantum
4. 27:06Rewinding challenges
5. 30:59Quantum-secure commitments
6. 49:43Fixing rewinding with commitments
7. 57:14Open questions

" related talks

• 01h 12mQuantum Rewinding Tutorial, Part 1: Motivation and Early Rewinding TechniquesAlex Lombardi, Fermi Ma · Quantum and Lattices Joint Reunion Workshop
• 40mPost-QuantumJames Howe, Thomas Prest, Thijs Laarhoven, Corentin Jeudy · RSAC 2021
• 13mPost-Quantum Succinct Arguments: Breaking the Quantum Rewinding BarrierFermi Ma · Meet the Fellows Welcome Event
• 49mQuantum CryptanalysisRen Taguchi, Jiayu Xu · RSA Conference 2023
• 01h 11mQuantum Rewinding Tutorial, Part 2: How to Run a Quantum Attacker Many TimesAlex Lombardi, Fermi Ma · Quantum and Lattices Joint Reunion Workshop
• 01h 06mAn introduction to lattice-based folding schemesBinyi Chen · Proofs (Simons Institute)
• 01h 36mAlgorithms for Algebraic Lattices: Classical and QuantumLéo Ducas · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 49mPanel Discussion: Computational AssumptionsYael Tauman Kalai, Chris Peikert, Benny Applebaum · Simons Institute Workshop: New Developments in Obfuscation