Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.16495

Quantum gate lower bounds for loss-tolerant position verification

Alex May, Philip Verduyn Lunel

quant-phSubmitted Aug 17, 2026• Announced Aug 18, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
23 pages, 4 figures

Related papers

Arbitrarily Loss-Tolerant Quantum Position Verification in a Single Execution

Llorenç Escolà-Farràs, Boris Škorić, Florian Speelman

Quantum position verification (QPV) aims to certify the location of an untrusted prover, but faces two major obstacles: fundamentally, entanglement-based attacks and, experimentally, photon loss. A commitment-based modification introduced in Phys. Rev. Lett. 135, 260801 addresses both in sequentially repeated protocols. Its security analysis, however, relies on the sequential structure and does not extend to parallel repetition. We use a different proof approach to establish security of the commitment modification for a parallel BB84-based QPV protocol. Against bounded-entanglement adversaries, the acceptance probability decays exponentially in the minimum number $k$ of successfully committed qubits. The protocol tolerates arbitrary transmission loss and noise rates up to 3.7%, while allowing arbitrarily slow quantum communication. This yields a fully loss-tolerant, single-execution QPV protocol secure against bounded-entanglement attacks, removing transmission loss as a fundamental limitation on verification distance. We also revisit sequential repetition, correcting the treatment of conditioning on commitment and replacing the earlier conditional guarantee with an unconditional security bound, without the finite-size correction to the correctness gap. The resulting bound provides improved quantitative security parameters for experimental implementations.

quant-pharXiv:2606.25037•Jun 25, 2026•0 citations

Linear gate bounds against natural functions for position-verification

Vahid R. Asadi, Richard Cleve, Eric Culf +1 more

A quantum position-verification scheme attempts to verify the spatial location of a prover. The prover is issued a challenge with quantum and classical inputs and must respond with appropriate timings. We consider two well-studied position-verification schemes known as f -routing and f -BB84. Both schemes require an honest prover to locally compute a classical function f of inputs of length n , and manipulate O(1) size quantum systems. We prove the number of quantum gates plus single qubit measurements needed to implement a function f is lower bounded linearly by the communication complexity of f in the simultaneous message passing model with shared entanglement. Taking f(x,y)=∑ixiyi to be the inner product function, we obtain a Ω(n) lower bound on quantum gates plus single qubit measurements. The scheme is feasible for a prover with linear classical resources and O(1) quantum resources, and secure against sub-linear quantum resources.

arXiv:2402.18648•Quantum•Jan 21, 2025•3 citations

Single-Qubit Loss-Tolerant Quantum Position Verification Protocol Secure against Entangled Attackers

Llorenç Escolà-Farràs, Florian Speelman

We give a tight characterization of the relation between loss tolerance and error rate of the most popular protocol for quantum position verification, which is based on BB84 states. Combining it with classical information, we show, using semidefinite programming, for the first time a fault-tolerant protocol that is secure against attackers who preshare a linear amount of entanglement (in the classical information), arbitrarily slow quantum information and that tolerates a certain amount of photon loss. We also extend this analysis to the case of more than two bases, showing even stronger loss tolerance for that case. Finally, we show that our techniques can be applied to improve the analysis of one-sided device-independent quantum key distribution protocols.

arXiv:2212.03674•Physical Review Letters•Oct 6, 2023•7 citations

Quantum position verification: loss-tolerant protocols and fundamental limits

Philip Verduyn Lunel

In this thesis we explore position-based quantum cryptography zooming in on the task of position verification. In position verification, the idea is to use an individual's geographical location as a cryptographic credential. In practice, such protocols can authenticate that a message originated from a specific location or ensure that messages can only be read at a certain location. In a position-verification protocol, the limitations imposed by the speed of light, as described by special relativity, are used to verify that a party is at their claimed location. It has been shown that any QPV protocol can be broken by attackers that use an amount of entanglement exponential in the input size. However, from a practical point of view, not all is lost. We can still hope for QPV protocols that are secure in practice. This raises the problem of designing protocols that are secure in a practical setting. An important problem that arises is that of signal loss. Signal loss can be detrimental as it allows attackers to only answer on a subset of rounds. We investigate several questions related to the practical implementation of such protocols. We propose a new experimentally feasible protocol, which is fully loss-tolerant against attackers restricted to classical communication. Furthermore, we consider the role of allowing quantum communication with no pre-shared entanglement for attackers and show that this setting is strictly stronger than the classical one, indicating that allowing for quantum communication may break security. Conversely, we then show that any protocol secure against classical communication can be transformed into a protocol secure against quantum communication. Finally, we invert the picture, and consider the task of non-local quantum computation (NLQC), which corresponds to the operations of the attackers in a QPV protocol. We connect NLQC to the wider context of information-theoretic cryptography by relating it to a number of other cryptographic primitives.

•Jan 1, 2024•0 citations

Making Existing Quantum Position Verification Protocols Secure Against Arbitrary Transmission Loss

Rene Allerstorfer, Andreas Blühm, Harry Buhrman +4 more

Signal loss threatens the security of quantum cryptography, especially in quantum position verification (QPV) protocols, where even small losses can compromise security. This Letter modifies traditional QPV to make high transmission loss between verifiers and the prover irrelevant for a class of protocols, including a practically interesting one based on BB84 states (QPV_{BB84}^{f}). Using photon presence detection and a small time delay, as well as a commitment before proceeding, the protocol's relevant loss rate is reduced to only that of the prover's lab, and the modified protocol has essentially the same security guarantees as the original one. The adapted protocol c-QPV_{BB84}^{f} thus offers strong security guarantees and feasibility over longer distances. We also discuss the practical implementation of the protocol and parameter estimates.

arXiv:2312.12614•Physical Review Letters•Nov 13, 2025•5 citations

On the Role of Quantum Communication and Loss in Attacks on Quantum Position Verification

Rene Allerstorfer, Harry Buhrman, Florian Speelman +1 more

We study the role of quantum communication in attacks on quantum position verification. In this work, we construct the first known example of a QPV protocol that is provably secure against unentangled attackers restricted to classical communication, but can be perfectly attacked by local operations and a single round of simultaneous quantum communication indicating that allowing for quantum communication may break security. We also show that any protocol secure against classical communication can be transformed into a protocol secure against quantum communication. We further show, using arguments based on the monogamy of entanglement, that the task of Bell state discrimination cannot be done locally with a single round of quantum communication, not even probabilistically (when we allow attackers to say loss sometimes), making this the first fully loss-tolerant QPV task secure against quantum communication attacks. Finally, we observe that any multi-round QPV protocol can be attacked with a linear amount of entanglement if the loss is high enough.

arXiv:2208.04341•Aug 8, 2022•4 citations
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 fff-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%50\%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 fff-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.
Quantum position verification (QPV) aims to certify the location of an untrusted prover, but faces two major obstacles: fundamentally, entanglement-based attacks and, experimentally, photon loss. A commitment-based modification introduced in Phys. Rev. Lett. 135, 260801 addresses both in sequentially repeated protocols. Its security analysis, however, relies on the sequential structure and does not extend to parallel repetition. We use a different proof approach to establish security of the commitment modification for a parallel BB84-based QPV protocol. Against bounded-entanglement adversaries, the acceptance probability decays exponentially in the minimum number kkk of successfully committed qubits. The protocol tolerates arbitrary transmission loss and noise rates up to 3.7%, while allowing arbitrarily slow quantum communication. This yields a fully loss-tolerant, single-execution QPV protocol secure against bounded-entanglement attacks, removing transmission loss as a fundamental limitation on verification distance. We also revisit sequential repetition, correcting the treatment of conditioning on commitment and replacing the earlier conditional guarantee with an unconditional security bound, without the finite-size correction to the correctness gap. The resulting bound provides improved quantitative security parameters for experimental implementations.
A quantum position-verification scheme attempts to verify the spatial location of a prover. The prover is issued a challenge with quantum and classical inputs and must respond with appropriate timings. We consider two well-studied position-verification schemes known as f -routing and f -BB84. Both schemes require an honest prover to locally compute a classical function f of inputs of length n , and manipulate O(1) size quantum systems. We prove the number of quantum gates plus single qubit measurements needed to implement a function f is lower bounded linearly by the communication complexity of f in the simultaneous message passing model with shared entanglement. Taking f(x,y)=∑ixiyi to be the inner product function, we obtain a Ω(n) lower bound on quantum gates plus single qubit measurements. The scheme is feasible for a prover with linear classical resources and O(1) quantum resources, and secure against sub-linear quantum resources.
We give a tight characterization of the relation between loss tolerance and error rate of the most popular protocol for quantum position verification, which is based on BB84 states. Combining it with classical information, we show, using semidefinite programming, for the first time a fault-tolerant protocol that is secure against attackers who preshare a linear amount of entanglement (in the classical information), arbitrarily slow quantum information and that tolerates a certain amount of photon loss. We also extend this analysis to the case of more than two bases, showing even stronger loss tolerance for that case. Finally, we show that our techniques can be applied to improve the analysis of one-sided device-independent quantum key distribution protocols.
In this thesis we explore position-based quantum cryptography zooming in on the task of position verification. In position verification, the idea is to use an individual's geographical location as a cryptographic credential. In practice, such protocols can authenticate that a message originated from a specific location or ensure that messages can only be read at a certain location. In a position-verification protocol, the limitations imposed by the speed of light, as described by special relativity, are used to verify that a party is at their claimed location. It has been shown that any QPV protocol can be broken by attackers that use an amount of entanglement exponential in the input size. However, from a practical point of view, not all is lost. We can still hope for QPV protocols that are secure in practice. This raises the problem of designing protocols that are secure in a practical setting. An important problem that arises is that of signal loss. Signal loss can be detrimental as it allows attackers to only answer on a subset of rounds. We investigate several questions related to the practical implementation of such protocols. We propose a new experimentally feasible protocol, which is fully loss-tolerant against attackers restricted to classical communication. Furthermore, we consider the role of allowing quantum communication with no pre-shared entanglement for attackers and show that this setting is strictly stronger than the classical one, indicating that allowing for quantum communication may break security. Conversely, we then show that any protocol secure against classical communication can be transformed into a protocol secure against quantum communication. Finally, we invert the picture, and consider the task of non-local quantum computation (NLQC), which corresponds to the operations of the attackers in a QPV protocol. We connect NLQC to the wider context of information-theoretic cryptography by relating it to a number of other cryptographic primitives.
Signal loss threatens the security of quantum cryptography, especially in quantum position verification (QPV) protocols, where even small losses can compromise security. This Letter modifies traditional QPV to make high transmission loss between verifiers and the prover irrelevant for a class of protocols, including a practically interesting one based on BB84 states (QPV_{BB84}^{f}). Using photon presence detection and a small time delay, as well as a commitment before proceeding, the protocol's relevant loss rate is reduced to only that of the prover's lab, and the modified protocol has essentially the same security guarantees as the original one. The adapted protocol c-QPV_{BB84}^{f} thus offers strong security guarantees and feasibility over longer distances. We also discuss the practical implementation of the protocol and parameter estimates.
We study the role of quantum communication in attacks on quantum position verification. In this work, we construct the first known example of a QPV protocol that is provably secure against unentangled attackers restricted to classical communication, but can be perfectly attacked by local operations and a single round of simultaneous quantum communication indicating that allowing for quantum communication may break security. We also show that any protocol secure against classical communication can be transformed into a protocol secure against quantum communication. We further show, using arguments based on the monogamy of entanglement, that the task of Bell state discrimination cannot be done locally with a single round of quantum communication, not even probabilistically (when we allow attackers to say loss sometimes), making this the first fully loss-tolerant QPV task secure against quantum communication attacks. Finally, we observe that any multi-round QPV protocol can be attacked with a linear amount of entanglement if the loss is high enough.