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.
While it is known that unconditionally secure position-based cryptography is impossible both in the classical and the quantum setting, it has been shown that some quantum protocols for position verification are secure against attackers which share a quantum state of bounded dimension. In this work, we consider the security of two protocols for quantum position verification that combine a single qubit with classical strings of total length
2n: The qubit routing protocol, where the classical information prescribes the qubit's destination, and a variant of the BB84-protocol for position verification, where the classical information prescribes in which basis the qubit should be measured. We show that either protocol is secure for a randomly chosen function if each of the attackers holds at most
n/2−5 qubits. With this, we show for the first time that there exists a quantum position verification protocol where the ratio between the quantum resources an honest prover needs and the quantum resources the attackers need to break the protocol is unbounded. The verifiers need only increase the amount of classical resources to force the attackers to use more quantum resources. Concrete efficient functions for both protocols are also given -- at the expense of a weaker but still unbounded ratio of quantum resources for successful attackers. Finally, we show that both protocols are robust with respect to noise, making them appealing for applications.
The
f-routing protocol is a leading candidate for quantum position verification (Kent, Munro, and Spiller, 2011), but security guarantees for explicit functions remain limited. We prove unconditional resource lower bounds for uniform attackers; our new 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 sufficiently small constant
ε>0, a uniformly generated strategy using
q qubits and having description length
poly(q), with success 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(nq)), 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 explicit Pauli-sparse unitaries on
q qubits that have at most
s nonzero Pauli coefficients, then
f∈DTIME(poly(nqs)).
3. If the strategies are Clifford+T circuits using at most
t magic gates, then
f∈DTIME(poly(nq2t)).
Time and space hierarchies then yield explicit functions secure against polynomial and even quasipolynomial qubits
q under our computational restrictions. These bounds exceed the
q≤logn bound of Bluhm, Christandl, and Speelman (2022) for inner product function
f=IP, at the cost of restricting adversarial computation and increasing honest evaluation complexity.
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 .
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.
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).