Quantum position-verification is a cryptographic task wherein a verifier attempts to establish the location in space of a prover. Recent experiments have implemented a well-studied class of position-verification schemes, known as the
f-BB84 scenario, but their security under realistic loss and imperfect state preparation remains incompletely understood. We give a new lower bound on any attack on this scheme, in particular proving nearly-linear quantum gate lower bounds on the attacker, even when allowing the attacker to declare a transmission loss of up to
50%, allowing for the challenges prepared by the referee to be imperfect, and allowing the quantum messages used in the protocol to be arbitrarily slow. Our results are applicable to recent and upcoming experimental implementations of
f-BB84, and in particular establish their security under a bounded quantum gate assumption on the attacker. The key ingredient is a tight analytic tradeoff for a lossy BB84 monogamy-of-entanglement game, valid without requiring the attackers' outputs to agree, which replaces observations previously made numerically.
The
f-routing protocol is a leading candidate for quantum position verification (Kent, Munro, and Spiller, Physical Review A, 2011), but security guarantees for explicit functions remain limited. We prove unconditional resource lower bounds for uniform attackers. Our techniques bypass communication-complexity bounds central to previous works, which are inherently at most linear in the input length.
We show that, for input length
n and a sufficiently small constant
ε>0, a uniform strategy running in time
T and succeeding with probability at least
1−ε on every input implies the following computational bounds on
f.
1. If the strategies are arbitrary quantum channels, then
f∈QSZK(poly(T)), where
QSZK(T) is the class of languages having quantum statistical zero-knowledge proofs in which the verifier runs in time
T and the simulator in time
poly(T).
2. If the strategies are Clifford+T circuits using at most
t magic gates, then
f∈DTIME(poly(T2t)).
3. If the strategies are explicit Pauli-sparse unitaries acting on at most
T qubits and having at most
s nonzero Pauli coefficients, then
f∈DTIME(poly(Ts)).
Time and space hierarchies then yield explicit functions secure against superlinear and even all polynomial-time adversaries under our computational restrictions. These bounds exceed the bounded-storage qubit bound
q≤logn of Bluhm, Christandl, and Speelman (Nature Physics, 2022) for the inner product function
f=IP, at the cost of restricting adversarial computation and increasing honest evaluation complexity.
Quantum position verification (QPV) aims to verify an untrusted prover's location by timing communication with them. To reduce uncertainty, it is desirable for this verification to occur in a single round. However, previous protocols achieving one-round secure QPV had critical drawbacks: attackers pre-sharing an EPR pair per qubit could perfectly break them, and their security depended on quantum information traveling at the speed of light in vacuum, a major experimental challenge in quantum networks. In this work, we prove that a single round of interaction suffices for secure position verification while overcoming these limitations. We show that security for a one-round protocol can rely only on the size of the classical information rather than quantum resources, making implementation more feasible, even with a qubit error tolerance of up to 3.6%, which is experimentally achievable with current technology -- and showing that the timing constraints have to apply only to classical communication. In short, we establish parallel repetition of the
f-BB84 and
f-routing QPV protocols. As a consequence of our techniques, we also demonstrate an order-of-magnitude improvement in the error tolerance for the sequential repetition version of these protocols, compared to the previous bounds of Nature Physics 18, 623-626 (2022).
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.
Secure position verification certifies that a remote prover occupies a claimed location, a task that is provably impossible with classical resources alone against colluding adversaries. Most existing quantum position verification schemes require transmitting quantum states between verifiers and provers, and the resulting photon loss makes long-distance verification impractical. Classical verifier position verification (CVPV) schemes with classical verifier-prover communication exist, but rely on complex quantum processes that generate certifiable randomness, placing them outside the reach of near-term hardware. Here we introduce a general compiler that maps any complete-support non-local game with the required quantum advantage into a multi-prover CVPV protocol. This addresses both limitations, with entirely classical verifier-prover communication and all quantum resources confined to shared entanglement and local measurements on the prover devices. Instantiating with the CHSH game enables near-term implementation on existing experimental platforms. We prove finite-size security in the quantum random oracle model for both simultaneous verification of multiple provers and verification of a single prover with multiple prover devices. Notably, security in the multi-prover setting is governed not by the certified randomness of the joint provers' outputs, but by certified blind local randomness that depends critically on the spatial arrangement of provers and verifiers.
The cryptographic task of position verification attempts to verify one party's location in spacetime by exploiting constraints on quantum information and relativistic causality. A popular verification scheme known as f -routing involves requiring the prover to redirect a quantum system based on the value of a Boolean function f . Cheating strategies for the f -routing scheme require the prover use pre-shared entanglement, and security of the scheme rests on assumptions about how much entanglement a prover can manipulate. Here, we give a new cheating strategy in which the quantum system is encoded into a secret-sharing scheme, and the authorization structure of the secret-sharing scheme is exploited to direct the system appropriately. This strategy completes the f -routing task using O(SPp(f)) EPR pairs, where SPp(f) is the minimal size of a span program over the field Zp computing f . This shows we can efficiently attack f -routing schemes whenever f is in the complexity class ModpL , after allowing for local pre-processing. The best earlier construction achieved the class L, which is believed to be strictly inside of ModpL . We also show that the size of a quantum secret sharing scheme with indicator function fI upper bounds entanglement cost of f -routing on the function fI .