arXiv:2609.39234
Breaking the Bounded Entanglement Barrier for Quantum Position Verification
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.
AI Summary
Quantum position verification (QPV) admits generic attacks with sufficiently large preshared entanglement. This paper asks whether hiding the challenge time can yield security when adversarial quantum resources exceed honest communication and storage. The protocol gives the prover $R_H$ random BB84 qubits to store. In each of $m$ rounds, one of two verifiers requests a uniformly selected stored qubit at a uniformly selected slot among $s$ possibilities, checks its timely return, and replenishes it. Honest communication and storage total $\widetilde O(R_H+m)$. For polynomially bounded parameters with $s\geq9$ and $m=\omega(\log^2\lambda)$, any finite LOCC coalition succeeding with non-negligible probability requires $\Omega(sR_Hm/\log^2\lambda)$ quantum-register qubits. Parameter choices give any prescribed polynomial resource gap. An ideal continuous-time version claims negligible cheating probability against arbitrary finite quantum storage and entanglement, bypassing the finite-slot premise of generic attacks. The proof bounds squashed-entanglement consumption when local recoverability of a random reference-entangled qubit transfers between adversarial sides. Reordered executions establish recovery guarantees during idle slots; post-selection identifies a block of high-success rounds. Reductions handle overlapping slots and higher-dimensional configurations with mobile verifiers. Security assumes fixed-location adversaries communicating only classically, instantaneous local operations, perfect quantum communication, and exact deadlines. The resource bound concerns worst-case quantum-register size, not an average entanglement measure. Continuous-time implementation is acknowledged as impossible; discrete performance depends on timing precision and response latency. A single protocol tolerating every polynomial resource gap, or a fixed exponential gap, remains open.
ChatGPT 5.5 Pro, 5.6 Sol, and 6 Astra were used for proofreading, editorial changes, as well as literature review
Central claim may not hold: The supplied text omits the promised continuous-time model and proof needed to establish the abstract's security claim against every finite LOCC coalition with arbitrary finite quantum storage.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.