Quantum Rewinding Tutorial, Part 1: Motivation and Early Rewinding Techniques
summary
Proves that Blum’s Hamiltonian-cycle protocol achieves post-quantum soundness and zero knowledge assuming collapse-binding commitments (instantiable from LWE or a collapsed random oracle) and quantum-hiding, and gives concrete techniques: replace full runs with a lazy one-bit measurement projector, apply a gentle-measurement style bound (Unruh) to extract two transcripts (leading to the known 1/√2 soundness bound), and use alternating projectors plus Jordan’s Lemma to build an efficient simulator; shows the methods work but also highlights limits (need collapsing properties and special protocol structure).
AI-written summary · about
chapters (11)
- 0:00Introduction to the workshop
- 2:00Quantum rewinding challenges
- 5:26Counterexamples to rewinding
- 11:43Quantum rewinding and security
- 17:06Interactive protocol model
- 20:35The Blum protocol
- 23:21Classical soundness proof
- 28:35Computational binding
- 35:16Collapse binding definition
- 42:54Soundness via lazy execution
- 50:34Zero knowledge simulation
