PaperlayerView exact revision on arXiv

Source-linked AI summary

Breaking the Bounded Entanglement Barrier for Quantum Position Verification

Amit Behera, Vipul Goyal

arXiv:2609.39234v1quant-phcs.CR

TL;DR

Classical position verification is impossible, and finite-slot teleportation attacks challenge quantum schemes. This paper presents continuous- and discrete-time QPV constructions; the latter achieves polynomial honest–adversary resource gaps.

  • Problem

    Classical position verification is impossible, while teleportation-based attacks in possible challenge time slots pose a security challenge for quantum position verification.

    Source: §1 · p. 3, §1.1 · p. 4

  • Method

    The authors construct a 1-D QPV protocol secure in the ideal continuous-time model and carry its ideas into a BB84-based discrete-time protocol.

    Source: §1.1 · pp. 4–6

  • Results

    Finite LOCC coalitions with finite registers and entanglement have negligible success in ideal continuous time, while discrete-time protocols can achieve any desired polynomial resource gap.

    Source: §1.1 · pp. 4–5

  • Takeaways & Limitations

    The discrete-time construction allows honest parties’ total communication and storage to be significantly smaller than the adversarial resource bound.

    Source: §1.1 · p. 5

    The paper leaves open whether a single protocol can achieve arbitrary polynomial or fixed exponential resource gaps.

    Source: §1.3 · p. 8

Abstract

from arXiv · show

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.

1 Introduction

Position verification tests a prover’s claimed location, but classical protocols are impossible and quantum protocols remain vulnerable to LOCC adversaries with enough preshared entanglement. This paper presents BB84-based protocols that bypass the continuous-time barrier and, in discrete time, separate honest-party resources from adversarial quantum storage.

1.1 Our Results

  • In the idealized continuous-time model, a 1-D QPV protocol gives every finite LOCC coalition with finite quantum storage and preshared entanglement negligible success probability.Randomizing the challenge time creates infinitely many possible slots, preventing any finite entanglement supply from supporting teleportation in every slot; sequential repetition amplifies security.Source: §1.1 · p. 4
  • The “I sleep, you work” design keeps honest-party resources independent of slot count s, while adversaries must remain prepared across slots and consume entanglement proportional to s.The verifiers hide the real challenge slot among s possibilities; the honest parties operate only in that slot.Source: §1.1 · p. 5
  • In discrete time, the protocol achieves any desired polynomial resource gap, with honest-party resources eO(RH + m) and adversarial quantum-register size eΩ(sRHm).The construction uses m rounds, s slots per round, and RH stored qubits; its security is stated for adversaries with non-negligible success probability.Source: §1.1 · pp. 5–6

1.2 Discussion on Our Model

  • Security is measured by adversarial quantum-register size because a rare branch can retain non-negligible attack success while a convex entanglement measure of the initial mixture is only O(1).The register-size measure captures the worst-case space needed to hold the entangled state, unlike average-case convex entanglement measures.Source: §1.2 · p. 7
  • The protocol extends to higher dimensions without loss in its security bounds when verifiers are mobile and can move according to the claimed location.The paper gives a reduction for both continuous-time and discrete-time models.Source: §1.2 · p. 8

1.3 Open Questions

  • The discrete-time results give a family of protocols with any chosen polynomial resource gap, but leave open whether one protocol can achieve arbitrary polynomial or fixed exponential gap.Source: §1.3 · p. 8

1.4 Related Works

  • Earlier QPV results include adversarial lower bounds linear in n, of the same asymptotic order as honest-party communication and storage.Ribeiro and Grosshans obtain a nearly tight local-register lower bound of n − O(log n) qubits for adversaries limited to classical communication.Source: §1.4 · p. 8

2 Technical Overview

The overview presents a repeated BB84 position-verification protocol and develops an entanglement-consumption argument to lower-bound adversarial registers. It applies the argument to post-selected high-success rounds, idle and overlapping slots, and higher-dimensional mobile verifiers, using classically flagged pure-state mixtures, including the multiple-reference-qubit case.

2 Technical Overview

  • The protocol uses RH live BB84 states over m rounds of s slots, with a uniformly chosen challenge slot, verifier, and state; all rounds must be accepted.Honest parties use eO(RH + m) total resources, while idle slots let them sleep and adversaries may need Ω(msRH) Bell pairs to teleport stored states.Source: §2 · p. 11, A Natural Attack · p. 11

A Natural Attack

  • High average Bell-pair fidelity recoverability by opposite sides before and after an LOCC evolution forces their entanglement to decrease by Ω(RH).The proof uses squashed entanglement, which satisfies the needed monogamy and LOCC-monotonicity properties.Source: A Natural Attack · pp. 13–14

2.1 Using the Entanglement-Consumption Theorem in the Protocol

  • Because local recoverability may fail on one side or both sides within a slot, the proof reorders adversarial evolutions and applies the consumption theorem across consecutive good slots.A high-success round contains at least 0.98s good slots; reordered timestamps establish average Bell-pair fidelity of at least 1 − 4γ for the recoverable side.Source: §2.1 · pp. 14–16
  • Every high-success round incurs an Ω(sRH) decrease in squashed entanglement across its slots, even after accounting for verifier actions between rounds.The argument aggregates consumption across consecutive good slots and allows an additive O(RH) loss from verifier actions.Source: §2.1 · p. 17
  • Non-negligible overall success does not guarantee a high-success round, since a rare highly entangled initial component may win rounds reliably while unconditional success remains low.Thus the high-success-round argument cannot be applied directly to every execution.Source: §2.1 · p. 17
  • Post-selecting a block of consecutive high-success rounds forces adversarial quantum registers of size Ω(smRH / log2 2(λ)) = eΩ(smRH).The argument uses the per-round squashed-entanglement decrease and its non-negativity; post-selection does not change the number or dimensions of the coalition’s registers.Source: §2.1 · pp. 17–18
  • The overlapping-slot argument reschedules the attack into a non-overlapping execution that reproduces accepted responses and uses the same quantum registers, with success probability at least as high.The reduction delays operations until the needed information and registers are available while preserving the original strategy’s register use and response deadlines.Source: §2.1 · pp. 18–19

2.2 Proving the Entanglement-Consumption Theorem

  • An initial-state upper bound, LOCC monotonicity, and a final-state lower bound together imply an Ω(1) decrease in squashed entanglement when a qubit is approximately recovered as a Bell-pair half.The final lower bound uses monogamy and the recovered qubit’s high fidelity with a Bell pair.Source: §2.2 · p. 19
  • Because locking prevents a dimension-independent upper bound for arbitrary mixed states, the proof uses classically flagged pure-state mixtures and applies the pure-state bound to each classical record.Squashed entanglement’s direct-sum identity lets the proof average the resulting inequalities over classical records.Source: §2.2 · pp. 20–21
  • For multiple reference qubits with recovery guaranteed only on average over indices, generalized additivity of mutual information handles inter-qubit correlations, whose contribution cancels against pure-state entropy terms.The proof averages and sums over indices; the continuity-bound errors are small because each comparison involves only two qubits.Source: §2.2 · p. 21

2.3 Lifting the Protocol from 1-D Static Verifiers to Higher-Dimensional Mobile Verifiers

  • A perturbed projection maps finite higher-dimensional adversarial coalitions to a one-dimensional coalition that preserves register use and response timing, yielding the same Ω(smRH / log2 2(λ)) = eΩ(smRH) lower bound.The mapping avoids placing an adversary at the claimed location while ensuring simulated distances do not increase.Source: §2.3 · pp. 21–22

3 Preliminaries: Quantum Information

The preliminaries establish quantum-information tools used in the proof, then connect classical-record accounting to bounds on quantum-register size.

3 Preliminaries: Quantum Information

  • Squashed entanglement is defined through conditional mutual information and has standard pure-state and LOCC-monotonicity properties.The section also lists monogamy, a coherent-information lower bound, and a continuity bound.Source: §3 · pp. 22–23
  • A register is classical in a joint state only when it is not entangled with the other registers, though it may be classically correlated with them.The section also defines classically flagged mixtures of pure states and notes operations that preserve this form.Source: §3 · p. 23

3.1 Classical records and quantum-register size

  • A classical record held on one side lets squashed entanglement be averaged over its values, while quantum-register size bounds that entanglement by the number of qubits.For Q qubits, the stated upper bound is Q, even when the classical record is arbitrarily large.Source: §3.1 · p. 23

4 Definitions of Quantum Position Verification

The section formalizes QPV correctness and bounded-register LOCC security, specifies the adversary model, and defines resource gaps and protocol transformations.

4 Definitions of Quantum Position Verification

  • A QPV protocol involves QPT verifiers, a QPT prover, and a relocation algorithm; an admissible claimed location lies in the verifiers’ convex hull but is not a verifier location.An honest prover at an admissible location must succeed with certainty.Source: §4 · p. 24
  • Static- and mobile-verifier security require negligible acceptance probability against finite LOCC coalitions within a stated quantum-register bound.The adversaries exchange only classical messages internally; the resource accounting excludes classical registers.Source: §4 · pp. 24–25
  • A t-vs-r resource gap bounds honest peak quantum storage plus communication by t(λ), while requiring security against coalitions with up to r(λ) qubits.The definition applies to either static- or mobile-verifier security.Source: §4 · p. 24
  • The adversary coalition is finite, uses fixed-location local hardware and finite circuits, and cannot exchange quantum messages or exceed the model’s speed limit.Its circuits have fixed quantum-register sets; classical computation, communication, and storage are unrestricted and uncounted.Source: §4 · pp. 24–25
  • Slot-based protocols use fixed spacing between logical times, and inter-slot-delay independence preserves the same security bound when that spacing is scaled by any constant.The mobile-verifier generalization translates and rotates the one-dimensional configuration while preserving verifier-input paths, logical times, and deadlines.Source: §4 · pp. 25–26

5 QPV Protocol

The protocol amplifies a one-round base protocol by repetition and enforces synchronized delivery and response rules. Its stated security result gives a lower bound on adversarial quantum registers alongside the honest parties’ resource use.

5 QPV Protocol

  • The amplified protocol repeats the base protocol m times to make the probability of a successful attack negligible.The base protocol is described as a simplified one-round protocol.Source: §5 · p. 26
  • With perfect quantum communication, the protocol in Figure 3 is correct for polynomial-time-computable, polynomially bounded integer-valued RH, s, and m.Source: §5 · p. 26, Figure 3 · p. 27
  • The verifiers keep BB84-state descriptions hidden, send initialization or replacement qubits along a fixed path, and abort on missed deadlines or unwarranted responses.Each slot’s logical time is when the selected verifier’s instruction reaches the claimed location; the honest response is due when it reaches that verifier.Source: §5 · pp. 26, 28
  • Ω(smRH / log2 λ) adversarial quantum-register size is required for non-negligible success, while the honest prover uses RH qubits and the protocol sends RH + 2m honest quantum messages.The security is independent of delays between slots and extends from one-dimensional static verifiers to higher-dimensional mobile verifiers.Source: Figure 3 · p. 27, §5 · p. 28

6 Lower Bound on Entanglement Consumption

This section develops an entanglement-consumption lower bound for LOCC that transfers the ability to recover Bell-pair halves. It connects recovery fidelity to squashed entanglement and handles imperfect recovery and classical records.

Bell closeness and entanglement

  • Bell-pair closeness gives a dimension-independent lower bound on squashed entanglement.The stated lemma applies when the two-qubit state is within trace distance ϵ′ of a Bell state.Source: §6 · p. 28

From test success to fidelity

  • Random two-qubit BB84 test success is converted into a lower bound on average fidelity to a maximally entangled Bell pair.The test measures both qubits in a randomly chosen XX or ZZ basis.Source: §6 · pp. 28–29

Correlated reference qubits

  • For several reference qubits, mutual-information additivity accounts for correlations through ΔO, a penalty that vanishes when O is a tensor product state.The lemma’s correlation term is used to combine the one-qubit estimates.Source: §6 · p. 29

Initial recovery bound

  • The initial recovery bound applies to flagged mixtures with a classical flag held on A1 and recovery operations whose conditional recovered states are close to Bell pairs.The bound combines preceding estimates to provide the initial recovery endpoint needed for the main entanglement-loss theorem.Source: §6 · p. 29

Entanglement-consumption bound

  • Theorem 5 lower-bounds entanglement consumed across A1 : A2 when LOCC transfers the ability to recover k Bell-pair halves from one side of the cut to the other.The theorem’s setup uses classically flagged mixtures and recovery operations at the two endpoints.Source: §6 · p. 30

General recovery operations

  • The lower-bound framework extends from locally controlled unitaries to arbitrary quantum-channel recovery operations using Stinespring dilation.The corollary states the result for local CPTP recovery maps.Source: §6 · pp. 30–31

Classical records on both sides

  • The framework also allows endpoint recovery maps to depend on classical records held on both sides and reference-qubit labels to vary with those records.For the analysis, maps may use the complete value of both records.Source: §6 · p. 31

7 Security Proof of the Protocol

The proof establishes security by reducing overlapping-slot attacks to nonoverlapping ones and applying timing and entanglement bounds, then bounding successful LOCC coalitions through decreases in squashed entanglement and extending one-dimensional security to mobile verifiers in every fixed dimension.

Notations for the Proof

  • The proof places the claimed location at 0, sets verifier positions to −L and R, and uses D = max{L, R} to define each slot’s full interval.It groups adversary registers by side and keeps outgoing registers on the sender’s side until receipt or discard.Source: Notations for the Proof · p. 32

Analysis Conventions

  • For any original slot spacing, an attack with register size Q and success probability p yields one at spacing ∆⋆ > max{∆, 2D} with size Q and success at least p, and disjoint slot intervals.The reduction also applies to slot-based protocols satisfying rules 2–5 and the stated single-return-instruction conditions.Source: Analysis Conventions · p. 33
  • Under Theorem 6’s conditions, for any admissible claimed location and coalition with no adversaries there, success probability at least (1 − 10^-7)^⌈log_2^2 λ⌉ implies total quantum-register size strictly exceeds the stated bound for large enough λ.The parameters satisfy s ≥ 9, RH ≥ 1, and m = ω(log_2^2 λ).Source: Analysis Conventions · p. 34
  • The analysis represents a round’s response as pre-slot LOCC, commuting local maps, classical communication, and final local response maps; current-instruction information can cross the claimed location at most once before a timely response.It alternates the side whose local response maps are defined across consecutive good slots.Source: Analysis Conventions · pp. 35, 36, 38

Steps 3–4

Step 5

  • Conditioning on a block jointly won with high probability makes every round in that block high-success without changing adversarial register dimensions.The conditioned execution has round success probability at least 1 − 10^-7; summing the entanglement decreases and using nonnegativity yields the register-size lower bound.Source: Analysis Conventions · p. 41

Remark 3 (Concrete security)

  • For integers m, s, RH with s ≥ 9 and 1 ≤ k < m, the proof gives a finite-parameter register-size bound for coalitions succeeding with probability at least (1 − 10^-7)^k.The proof obtains this version by partitioning the m rounds into k consecutive blocks of lengths differing by at most one.Source: Analysis Conventions · p. 42

Theorem 7

  • Under the stated protocol conditions, one-dimensional static-verifier security with bound B(λ) lifts to d-dimensional mobile-verifier security with the same register bound for every fixed d ≥ 2.The reduction maps the coalition to the verifier line and reproduces its execution using the same quantum-register size and at least the same success probability.Source: Analysis Conventions · pp. 43, 45

A Proof of basic quantum information lemmas

The lemmas relate squashed entanglement of classically flagged states to flag-wise terms and bound those terms using local subsystem dimensions. The proof obtains the identity through matching extension-based upper and dephasing-based lower bounds.

A Proof of basic quantum information lemmas

  • The upper-bound proof embeds extensions into a common environment and records x there, while the lower bound dephases X, a local operation that cannot increase conditional mutual information.Source: A Proof of basic quantum information… · p. 48
  • For classically flagged states with orthogonal flags, Lemma 1 gives an exact decomposition of total squashed entanglement into flag-conditioned terms.The lower-bound argument identifies the weighted flag-wise terms as a lower bound, matching the extension-based upper bound.Source: A Proof of basic quantum information… · pp. 48–49
  • Each flag’s squashed entanglement is bounded by local subsystem entropy and therefore by the logarithm of the subsystem’s dimension.This bounds the entanglement in terms of the size of the corresponding quantum register.Source: A Proof of basic quantum information… · p. 49

B.1 Entanglement estimates

These estimates relate squashed entanglement to coherent information and bound how recovery fidelity constrains entanglement. They also show that a BB84 test’s average acceptance probability yields a lower bound on average Bell-state fidelity.

B.1 Entanglement estimates

  • Squashed entanglement upper-bounds one-way distillable entanglement, which upper-bounds coherent information [CW04].The proof invokes these known bounds to obtain its coherent-information estimate.Source: §B.1 · p. 49
  • F_avg ≥ 2p − 1: the ensemble’s average Bell-state fidelity is at least twice its average BB84-test success probability minus one.The bound follows by averaging the state-indexed fidelity bound F_x ≥ 2p_x − 1.Source: §B.1 · p. 50
  • For a pure state, the proof uses an arbitrary extension and data processing to lower-bound its squashed entanglement by S(A2) − I(O : A2).Since S(A2) = Esq(OA1 : A2), this yields the corresponding entanglement inequality after rearrangement.Source: §B.1 · p. 50

B.2 Proofs of the entanglement-loss theorem and its corollaries

The proofs bound entanglement loss using monogamy, fidelity, and concavity, then extend the argument to local recovery channels and classical records. The resulting estimate for classical-record recovery subtracts a penalty proportional to the number of target pairs and g(ϵ).

B.2 Proofs of the entanglement-loss theorem and its corollaries

  • When ϵ ≤ 3/4, the initial state satisfies Esq(A1 : A2)ρ ≥ Esq(OA1 : A2)ρ − 2k · g(ϵ), since gsafe(ϵ) equals g(ϵ) under this condition.Source: §B.2 · p. 55
  • The entanglement-loss proof combines LOCC monotonicity and monogamy with a fidelity-based bound on final target entanglement.Its fidelity hypothesis is an average final fidelity of at least 1 − (ϵ′)^2, with ϵ′ ≤ 1/2.Source: §B.2 · pp. 55–56
  • Local CPTP recovery maps are handled by adjoining local pure Stinespring environments and applying the unitary-recovery result on the extended bipartition.The extensions preserve the initial and final average-fidelity conditions and the entanglement difference.Source: §B.2 · pp. 56–57
  • Classical records can be copied across the cut by LOCC and locally discarded, enabling record-conditioned recovery maps to use the corollary’s bound.The proof applies the result to the enlarged state and a channel acting trivially on the copied records.Source: §B.2 · p. 57

C.1 From Overlapping to Nonoverlapping Slots

The proposition transforms overlapping response slots into nonoverlapping ones by delaying operations according to their information and register dependencies. This preserves accepted executions without increasing the coalition’s quantum-register size.

C.1 From Overlapping to Nonoverlapping Slots

  • Each circuit event is scheduled only after its shifted time, required information arrivals, and release of every needed register.The schedule derives event delays from dependencies, including message values, waits, timeouts, and register use.Source: §C.1 · p. 58
  • Every accepted execution remains accepted because each response reaches the verifier at its shifted deadline in the same state.The argument applies across rounds, including responses prepared before the round in which they are received.Source: §C.1 · p. 59
  • The transformed coalition has the same quantum-register size Q and success probability at least p.Delayed responses reuse the same counted outgoing registers; only classical information may need to be stored longer.Source: §C.1 · p. 59

C.2 Loss Due to the Verifiers’ Messages

The proof bounds the coalition’s entanglement using the verifier’s response, or a trivial register when no response is present. The same bound applies regardless of which side responds, and removing analysis-only outcomes cannot increase squashed entanglement.

C.2 Loss Due to the Verifiers’ Messages

  • For a timely response, the proof uses the sender’s outgoing register; without one, it substitutes a one-dimensional trivial register.For the resulting pure conditional state, the proof lower-bounds squashed entanglement by S(Y) − RH.Source: §C.2 · p. 59
  • The same squashed-entanglement bound holds whether either side sends the response or no response is sent.The proof uses symmetry to express the bound across the original A0 : A1 bipartition.Source: §C.2 · p. 60
  • Averaging over the complete analysis record proves the result, and deleting analysis-only outcomes cannot increase squashed entanglement.Source: §C.2 · p. 60

D Security in the Ideal Continuous-Time Model

The ideal continuous-time protocol is secure against any finite-circuit LOCC coalition with finite quantum-register size. Its guarantee depends on exact real-valued challenge times, which place it outside the finite-input setting of the general impossibility result.

Security in the ideal continuous-time model

  • Each unit-length round window has infinitely many possible real-valued slots, but the verifiers select one uniformly and allow its response to finish after the window.A slot is defined by when the instruction reaches the claimed location; transmission-response intervals for different slots may overlap.Source: D Security in the Ideal… · p. 60
  • For every finite s ≥9, equally spaced slots force any coalition succeeding with probability at least ν(λ) to use more than Bs quantum-register size.The bound applies to every finite s, not only polynomially bounded s.Source: D Security in the Ideal… · p. 61
  • For every λ ≥λ0, the continuous-time protocol has success probability below ν(λ) against any finite-circuit LOCC coalition, regardless of its finite quantum-register size.This covers any finite amount of preshared entanglement without fixing a bound in advance.Source: D Security in the Ideal… · p. 61
  • An attack with success probability at least ν(λ) would require register size Q > Bs for every finite s ≥9, contradicting fixed finite Q as Bs grows without bound.The proof transfers a continuous-time attack to a suitable finite set of challenge times with at least the same success probability.Source: D Security in the Ideal… · pp. 60, 62
  • For every fixed dimension d ≥2, the mobile-verifier generalization has the same security guarantee as the one-dimensional protocol.The reduction preserves the adversaries' register size and gives at least the same success probability.Source: D Security in the Ideal… · p. 62
  • The theorem requires exact real-valued slot sampling and excludes infinite-dimensional states and strategies performing infinitely many operations before a deadline.It does not contradict Buhrman et al., whose impossibility result concerns finite-dimensional protocols with inputs from fixed finite sets.Source: D Security in the Ideal… · pp. 60, 62
Loading 2609.39234v1…