论文库

原文摘要

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. Although prior impossibility results apply, our information-theoretic QPV protocol achieves any desired polynomial gap between the honest parties' total resources (communication and storage) and the adversarial resource bound. To our knowledge, all prior constructions that do not rely on idealized oracles required resources of the honest parties to be at least as large as the proven adversarial entanglement bound. Interestingly, the resource gap depends on the precision in measuring time. As clock precision improves, the adversarial resource bound increases while honest resources remain largely unchanged. We call this the "I sleep, you work" paradigm. Finally, we show that our techniques extend to an information-theoretic, position-based message authentication protocol, which in turn extends to an information-theoretic, position-based quantum key exchange protocol with the same guarantees as our position-verification protocol in the continuous-time and discrete-time models.