Technical Summary: Arbitrarily Loss-Tolerant Quantum Position Verification in a Single Execution

1. Problem Statement

Quantum Position Verification (QPV) aims to certify the spatial location of an untrusted prover using relativistic signaling constraints and quantum information. While the no-cloning theorem prevents classical copying attacks, unconditional security is impossible against adversaries sharing arbitrarily large entanglement. Consequently, research focuses on the bounded-entanglement (BE) model, where adversaries share a limited number of entangled qubits.

A critical practical obstacle for QPV is photon loss. In optical fibers, transmission loss increases exponentially with distance. Standard QPV protocols (e.g., $QPV_{BB84}$, $QPV^f_{BB84}$, and the parallel $QPV^{f:n\to m}_{BB84}$) assume ideal transmission. This assumption creates a fundamental vulnerability: an adversary can intercept qubits, measure them in random bases, and only report outcomes when the basis guess is correct, declaring "loss" otherwise. This strategy breaks security whenever the transmission rate drops below 50%.

Previous works addressed loss and entanglement separately or simultaneously only in sequential settings. Specifically, [ABB+23] introduced a commitment-based modification ($c-QPV^f_{BB84}$) that tolerates arbitrary loss by requiring the prover to commit to received qubits before learning the measurement basis. However, this technique relied on the sequential structure of the protocol, where repeated rounds allow verifiers to detect inconsistent commitments. These techniques do not extend to single-execution (parallel) protocols, which are preferable for practical implementation and use as subroutines in larger cryptographic schemes. Existing single-execution protocols either lack loss tolerance or require quantum communication at the speed of light, limiting their applicability.

2. Methodology

The authors propose a commitment-based modification to the parallel, single-execution protocol $QPV^{f:n\to m}_{BB84}$, denoted as $c-QPV^{f:n\to m}_{BB84}$.

Protocol Structure

The protocol involves two verifiers ($V_0, V_1$) and a prover ($P$):

1. Preparation: Verifiers generate classical inputs $x, y \in \{0,1\}^n$ and quantum states (BB84 qubits) based on a function $z = f(x,y)$.
2. Distribution: Quantum states are sent to $P$, followed by classical strings $x$ and $y$ timed to arrive simultaneously at the claimed position.
3. Commitment (New Step): Upon receiving the quantum systems but before learning $x$ and $y$, the prover broadcasts a commitment string $c \in \{0,1\}^m$, indicating which qubits were successfully received ($c_i=1$) and which were lost ($c_i=0$).
4. Verification Condition: The protocol proceeds only if the number of committed qubits $|c| \geq k$, where $k$ is a pre-defined threshold.
5. Measurement: Once $x$ and $y$ arrive, $P$ computes $z = f(x,y)$ and measures only the qubits in the committed set $C = \{i \mid c_i=1\}$ in the bases specified by $z_C$.
6. Verification: Verifiers accept if the reported outcomes match the expected values within an error margin $\gamma$ for the subset $C$.

Security Analysis Techniques

The security proof addresses the challenge that, unlike sequential repetition, a single execution provides only one commitment string, preventing the detection of inconsistencies across rounds. The authors employ the following techniques:

• No-Signalling Constraints: The analysis leverages the fact that adversaries (Alice and Bob) are spatially separated. Their joint commitment distribution must satisfy no-signalling conditions; specifically, Alice's commitment cannot depend on Bob's input $y$, and vice versa.
• Decomposition of Acceptance Probability: The authors decompose the total acceptance probability into a sum over possible commitment strings $c$. They bound the conditional acceptance probability $Pr[\text{accept } w_C \mid c]$ for a fixed $c$ by relating it to the security of the original $QPV^{f:n\to m}_{BB84}$ protocol restricted to the subset $C$.
• Exponential Decay: By combining the no-signalling constraints with the exponential decay of the original protocol's soundness (governed by the parameter $\lambda_\gamma$), they derive a global bound that decays exponentially with the threshold $k$.
• Refined Sequential Analysis: The authors also revisit the sequential protocol from [ABB+23]. They replace the stochastic stopping time (waiting for a polynomial number of successful rounds) with a fixed number of rounds $m$ and a fixed threshold $k$. This allows for a direct bound on the acceptance probability without relying on "either-or" statements regarding inconsistent commitments.

3. Key Contributions

1. First Loss-Tolerant Single-Shot QPV: The paper presents $c-QPV^{f:n\to m}_{BB84}$, the first protocol that simultaneously achieves:
   • Negligible soundness in a single execution.
   • Security against adversaries sharing a linear amount of entanglement (in the size of classical inputs).
   • No requirement for quantum communication at the speed of light.
   • Tolerance to arbitrarily large transmission losses.
2. Generalization of Commitment Paradigm: The work successfully lifts the commitment modification from sequential to parallel settings using no-signalling correlations, overcoming the reliance on sequential structure that previously prevented this extension.
3. Improved Sequential Parameters: The paper refines the analysis of sequential commitment protocols, replacing stochastic stopping times with fixed parameters. This yields improved quantitative bounds where the adversarial acceptance probability decays exponentially in the threshold $k$, with a correction term scaling as $O(k^{-1/3})$ (improved from $O(r^{-1/4})$ in prior work).
4. Robustness: The resulting protocol maintains robustness to noise levels up to 3.7% per qubit, matching the noise tolerance of the original underlying protocol.

4. Results

The main theoretical result (Theorem 1.1 and Theorem 4.1) establishes that for a suitable function $f$, the probability of an adversary being accepted in the BE($O(n)$) model is bounded by:
$$Pr[\text{accept } c-QPV^{f:n\to m}_{BB84}] \lesssim 2(\lambda_\gamma)^{k/2}$$
where $\lambda_\gamma = 2^{h(\gamma)}(\frac{1}{2} + \frac{1}{2}\sqrt{2})$ and $h(\cdot)$ is the binary entropy function.

• Loss Tolerance: Security depends on $k$ (the number of successfully received qubits), not the total number of transmitted qubits $m$. Thus, the protocol remains secure even if the transmission rate is arbitrarily low, provided enough qubits are eventually received to meet the threshold $k$.
• Noise Tolerance: The protocol remains secure for error rates $\gamma < 0.037$ (3.7%), as this ensures $\lambda_\gamma < 1$.
• Parallel Repetition: For protocols constructed by parallel repetition of a single Boolean function $g$ (i.e., $f = g^{\otimes m}$), the security of the commitment-based version reduces to the security of the non-commitment version with $k$ repetitions: $Pr[\text{accept } c-QPV^{g^{\otimes m}}_{BB84}] \leq 2\sqrt{Pr[\text{accept } QPV^{g^{\otimes k}}_{BB84}]}$.

5. Significance and Claims

The authors claim that this work bridges a critical gap between theoretical security and practical implementation of QPV.

• Feasibility over Arbitrary Distances: By making the protocol arbitrarily loss-tolerant, the work makes QPV feasible over long distances where photon loss is significant, a prerequisite for real-world deployment.
• Practical Utility: The single-execution nature of the protocol is highlighted as particularly attractive for near-term implementations and for use as a subroutine in larger cryptographic constructions (e.g., Quantum Key Distribution, message authentication), where sequential repetition is often impractical.
• Theoretical Advancement: The work demonstrates that commitment-based security can be achieved in parallel settings without sacrificing the security guarantees of the underlying protocol against bounded-entanglement adversaries.
• Experimental Relevance: The paper provides improved quantitative parameters for experimental implementations, specifically by fixing the number of rounds and the acceptance threshold, which eliminates the uncertainty of execution duration inherent in previous sequential approaches.

The paper concludes that $c-QPV^{f:n\to m}_{BB84}$ represents the first fully loss-tolerant single-shot QPV protocol secure against entangled attackers, effectively removing the transmission rate barrier that previously limited QPV to short distances or idealized conditions.