Quantum and Classical Coin-flipping Protocols Based on Bit-commitment and their Point Games
summary
Defines a restricted family of coin‑flipping protocols by four probability vectors and shows the cheating SDPs collapse to an LP‑like polytope, enabling point‑game reductions that exactly characterize two cheating directions. Numerical search over ~10^16 parameter sets finds the best bias equals 3/4 so far, and a classical analogue proves classical protocols are insecure and at most one party can cheat perfectly. Saturating Kitaev’s bound forces the classical and quantum cheating values to coincide.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:34(Weak) Coin-Flipping
- 1:10(Strong) Coin-Flipping
- 3:06Bad Coin-Flipping
- 4:07Quantum Coin-Flipping Protocol Construction
- 8:20Calculating the cheating probabilities as SDPs
- 13:31Point Game Idea
- 15:44Another Easy Point Game
- 15:56Basic Point Game Moves
- 16:56Bob's Dual
- 19:14Quantum Point Game (1 of 3)
- 20:18Point Game Usefulness
- 25:32Classical Point Games!
- 26:21Favouring Cheating Alice
- 27:05Classical Point Game (Favouring Cheating Bob)
- 29:22Quantum security from studying classical protocols...
- 31:27Open questions
related talks
01h 06mCompiled Nonlocal Games: From CHSH to BQP Verification
52mGame-Theoretically Secure Protocols Inspired by Blockchains
32mBeating Classical Impossibility of Position Verification
33mHow Fair is your Protocol? A Utility-Based Approach to Protocol Optimality
35mMulti-Party Distributed Point Functions
01h 00mQuantum Commitments and Black Hole Radiation Decoding
01h 08mTutorial: Security
11mSecuring the Quantum Future: Exploiting Crosstalk and Controller Vulnerabilities