Quantum Proofs of Knowledge
summary
Classical sigma-protocol extractors fail against quantum provers because copying and rewinding break on quantum states; security uses Watrous-style quantum rewinding (uncompute instead of clone) plus a new canonical extractor that succeeds only when the protocol has special soundness and an extra strict soundness (at most one valid response per challenge). The extractor gives a weaker bound than classical extraction (requires more rounds; quadratic→worse dependence on challenge count), and several practical uses (GNI, composed protocols, signing-oracle games) remain open.
AI-written summary · about
chapters (17)
- 0:00Intro
- 1:03Post Quantum Crypto
- 3:24Zero Knowledge Proofs
- 8:34Zero-knowledge: how to show?
- 10:43Watrous' quantum rewinding
- 14:22Limitations of Watrous' rewinding
- 15:58Quantum ZK solved?
- 19:42Proofs of knowledge - definition
- 22:41Constructing extractors
- 28:11Quantum extractors?
- 34:26Canonical extractor (ctd.)
- 38:20Making extraction work (ctd.)
- 43:58Achieving strict soundness
- 46:17Plugging things together
- 48:06Using extractors (1)
- 52:04Using extractors (11)
- 56:20Conclusions
related talks
13mPost-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier
32mBeating Classical Impossibility of Position Verification
45mClassical Verification of Quantum Computational Advantage
58mClassical Zero Knowledge Arguments for Quantum Computing
01h 09mRecent Progress in Quantum Advantage
21mQuantum Proofs of Deletion for Learning with Errors
16mQuantum Information Meets Cryptography
01h 06mQuantum Advantage Without Structure