Quantum Commitments and Black Hole Radiation Decoding
summary
A reformulation of Harlow–Hayden’s decoding task as a radiation distinguishing game shows a concrete equivalence: distinguishing whether register B is entangled with R or replaced by a maximally mixed qubit is exactly the hiding test for an EPR commitment. Brakerski proves this is necessary and sufficient for commitment-based quantum cryptography; hardness reductions use polynomial‑size random circuits, teleportation to turn an EPR commit into a commit‑any‑state routine, and complexity assumptions (e.g. SZK v. BQP, one‑way functions); the trivial win rate is 1/4 trivial win.
AI-written summary · about
chapters (20)
- 0:00Introduction
- 2:30Warning Slide
- 3:12Black Hole Radiation
- 8:08Amps Experiment
- 10:46Computational Complexity
- 12:26Radiation
- 13:04Amp Experiment
- 16:29Why would the black hole evaporate
- 24:34Statistical Zero Knowledge
- 25:10What is Hard
- 25:57Weak Assumptions
- 33:41Hardness
- 34:39Natural Crypto Assumption
- 35:46Quantum State Commitment
- 38:56Binding and Hiding
- 40:25Epr Commitments
- 41:37Summary
- 44:04Commitments
- 46:11Conclusion
- 48:31Discussion
related talks
34mQuantum and Classical Coin-flipping Protocols Based on Bit-commitment and their Point Games
38mQuantum Technologies: Quantum Computing & Secure Quantum Communication
13mQuantum Computing Encryption
59mCommit-and-Prove Zero-Knowledge Proof Systems and Extensions
35mQuantum Cryptography: From Theory to Practice
43mWhen the Internet Is Ruled by Schrödinger's Cats
40mPost-quantum Key Exchange—A New Hope
57mThe Cryptographic Lens: Visions of our Past and Future