Quantum position verification secured against large entanglement attacks
Breaking the Bounded Entanglement Barrier for Quantum Position Verification
Cryptography and Security
Summary
Position verification lets others check where you claim to be, but classical versions can be tricked. Quantum Position Verification tried to fix this, but attackers with lots of shared quantum entanglement could still cheat. The authors show that by carefully measuring time in a continuous way, they can create a quantum protocol that remains secure even against attackers with huge entanglement and resources. This method lets honest parties use much fewer resources than attackers, improving security as clock precision improves.
What this means in practice
- •For quantum network engineers: Securely verify the physical location of network nodes using a quantum protocol resistant to large entanglement-based attacks.
- •For cybersecurity system designers: Design position-based authentication methods that require fewer resources while maintaining security even against powerful quantum adversaries.
Authors
Amit Behera, Vipul Goyal
Abstract
Position verification, introduced by Chandran et al. (SIAM J. Computing 2014), allows verifiers to test a prover's claimed position by an interactive protocol. Classical position verification is impossible. Even for Quantum Position Verification (QPV), there always exists an LOCC (Local Operations and Classical Communication) attack if the adversary can hold an exponentially large amount of preshared entanglement. Somewhat surprisingly, we show that we can circumvent this barrier in the idealized continuous-time model, where time is represented by a real-valued parameter and challenge messages can be sent at a time sampled uniformly from a real interval. In this model, we give a BB84-based protocol that remains secure against any finite coalition of LOCC adversaries with arbitrary finite (possibly exponential) quantum storage and entanglement. Our construction can also be instantiated in the discrete-time model. Even though the previous impossibility results apply, we are able to obtain an information-theoretic QPV protocol in which the honest parties' total resources (communication and storage) can be significantly smaller than the adversarial resource bound. In fact, we can achieve any desired polynomial gap between honest parties and adversarial resources. To our knowledge, all previous protocols in the literature required resources of the honest parties to be at least as large as the adversarial entanglement. Interestingly, the resource gap between the honest and adversarial party resources in our protocol depends on how precisely time can be measured. As the precision of the best-known clock improves with further research, the resource gap in our protocol keeps increasing. In particular, the adversarial resource bound keeps increasing while the honest parties' resources remain largely the same. We call this the "I sleep, you work" paradigm.