Beating Classical Impossibility of Position Verification
summary
Constructs a position‑verification protocol where verifiers are entirely classical verifiers and all messages are classical, but the prover must be quantum; security assumes LWE hardness against quantum attacks and uses trapdoor claw-free functions as the computationally unclonable resource. The basic protocol has soundness 3/4 against efficient quantum colluders and achieves negligible soundness via parallel repetition, can be strengthened to bounded‑entanglement security under subexponential quantum LWE or to unbounded entanglement in the quantum random oracle model, and requires the honest prover to maintain quantum memory.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:36Position verification via distance bounding
- 1:31Attack with colluding adversaries
- 5:04State of the art for position verification (PV)
- 5:48In this talk...
- 9:44Practical advantages, cont'd
- 10:53Quantum position verification with BB84
- 12:27BB84 position verification security TEKW13
- 13:23Position verification impossibility
- 15:05Trapdoor claw-free functions Goldwasser, Micali, Rivest '84
- 16:10Proof of quantumness [Brakerski, Christiano, Mahadev, Vazirani, Vidick; 2018]
- 22:05First attempt, cont'd
- 22:49First attempt, attack
- 24:29Second attempt
- 25:52Computational non-local game of TCFS
- 28:14Other results
- 30:00Future directions
related talks
45mClassical Verification of Quantum Computational Advantage
16mQuantum Information Meets Cryptography
58mClassical Zero Knowledge Arguments for Quantum Computing
23mA Unified Assertion-Based Framework for Classical-Quantum Program Verification
21mAnalyzing quantum programs using the power of interaction
22mEfficient Formal Verification of Quantum Error Correcting Programs
01h 03mQuantum Proofs of Knowledge
01h 03mA Survey on the Complexity of Entangled Provers