Quantum Rewinding Tutorial, Part 3: Zero Knowledge Simulation Beyond Watrous
summary
Claims a constructive simulator that achieves guaranteed extraction of witnesses for three‑message proofs against quantum verifiers and then preserves the verifier state, by abandoning Marriott‑Watrous and using singular value transform / singular‑vector algorithms plus a pseudo‑inverse lemma. Built a rewind/repair procedure that only does K repairs (not K/P) and replaces costly amplitude estimation with gap/phase methods to get the expected‑polynomial runtime. Works under collapsing assumptions and a new coherent expected‑polynomial‑time model so the extraction composes into full zero‑knowledge.
AI-written summary · about
chapters (9)
- 0:00Introduction and overview
- 6:18Zero knowledge protocols
- 12:27Graph non-isomorphism
- 21:13Extracting transcripts
- 27:41Quantum rewinding procedure
- 34:08Maintaining state invariants
- 40:08Analyzing runtime complexity
- 49:20Optimizing for polynomial time
- 55:46Conclusion and future outlook
related talks
13mPost-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier
58mQuantum 2
33mAn Introduction to Zero Knowledge Proofs
01h 13mQuantum 3
38mNew Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, ...
17mProofs of Quantumness from Trapdoor Permutations
48mCommitments to Quantum States
49mLattice-Based Zero Knowledge and Applications