Efficient Multi-basis Quantum Position Verification Secure against Generalized Adversaries

Technical Summary: Efficient Multi-basis Quantum Position Verification Secure against Generalized Adversaries

Problem Statement
Quantum Position Verification (QPV) aims to certify that a prover is located at a specific physical position using quantum communication and physical assumptions. While classical position verification requires strong assumptions (e.g., bounded classical memory or pre-shared keys), QPV relies on weaker physical assumptions, such as the inability to clone quantum information. However, existing QPV protocols face significant practical challenges:

1. Loss Sensitivity: Protocols based on BB84 states typically tolerate at most 50% channel loss.
2. Experimental Complexity: Protocols requiring matching preparation and measurement bases often necessitate complex state preparation or secure communication of basis choices between verifiers.
3. Security Gaps: Existing security analyses often rely on implicit assumptions, such as adversaries using only pure states, lacking unbounded shared randomness, or having transmission rates independent of inputs.

Methodology
The authors propose a comprehensive framework addressing protocol design, security analysis refinement, and adversary model generalization.

1. Protocol Design (Multi-basis QPV):
   The paper introduces a protocol (Protocol 1) where verifiers prepare one of six states ($|0\rangle, |1\rangle, |+\rangle, |-\rangle, |+i\rangle, |-i\rangle$) but the prover measures in multiple bases ($m$ bases) on the Bloch sphere. Crucially, the preparation basis and measurement basis need not match. To evaluate performance without matching bases, the authors utilize the Asymmetric Bell Expectation (ABE) score ($C$), generalized for six-state preparation. The normalized score $\hat{C} = C/\eta$ is monitored alongside transmission $\eta$. This decoupling allows for third-party state preparation and eliminates the need for verifiers to securely communicate basis choices.

2. Security Analysis Refinement:
   To prove security against entangled adversaries, the authors adapt and refine techniques from prior work (specifically Ref. [3]). Key methodological improvements include:

   • Trace Distance Tightening: Instead of using Fano's inequality or reduction to simpler games, the authors formulate the lower bound on the trace distance between state sets as a Semidefinite Program (SDP) using the Navascués-Pironio-Acín (NPA) hierarchy and linear approximation.
   • Classical Rounding: A modified classical rounding argument is introduced where the output set size is fixed to $m-1$ (rather than $m$), tightening the analysis.
   • Score-based Analysis: The analysis shifts from error-rate monitoring to score-based monitoring to accommodate mismatched bases.

3. Generalized Adversary Model:
   The authors identify and remove three implicit assumptions from previous security proofs:

   • Mixed States: Adversaries may pre-share mixed quantum states (bounded dimension) rather than just pure states.
   • Unbounded Shared Randomness: Adversaries may share unbounded classical randomness.
   • Input-Dependent Transmission: The transmission rate $\eta$ may depend on the inputs $(x, y)$ and the shared randomness $r$.
     To handle these, the authors employ partial purification (converting mixed states and general CPTP maps into pure states and unitaries with auxiliary systems) and a partitioning strategy that categorizes attack rounds based on both high/low error and high/low transmission.

Key Contributions

1. Protocol-Level Novelty: Introduction of a multi-basis QPV protocol using six prepared states and multiple measurement bases. This reduces experimental complexity (fewer prepared states), enhances flexibility (decoupled preparation/measurement), and removes the need for secure basis-communication channels between verifiers, all without compromising security performance compared to previous proposals.
2. Proof-Level Novelty: Development of a refined security analysis featuring tightened trace-distance bounds via SDP and a modified classical rounding argument. These improvements increase the protocol's error and loss tolerance under restricted adversary models.
3. Model-Level Novelty: Generalization of the adversary model to include mixed states, unbounded shared randomness, and input-dependent transmission. This exposes limitations in prior analyses and clarifies the scope of rigorous security guarantees.
4. Application: Illustration of QPV as an authentication mechanism for Quantum Key Distribution (QKD), specifically to bootstrap key exchange when standard Wegman-Carter authentication fails or when location-based credentials are required.

Results

• Unentangled Adversaries: Numerical simulations using the new SDP formulation (Eq. 6) show that the simple multi-basis QPV matches the performance of the original multi-basis QPV (Ref. [3]) but with improved error tolerance compared to the analysis in Ref. [3]. The ABE score is validated as a robust substitute for error rates.
• Entangled Adversaries (Restricted): For $q$-qubit restricted strategies (pure states, unitary operations), the tightened analysis (solid lines in Fig. 5) demonstrates higher error tolerance than previous methods (dotted lines) for fixed quantum memory sizes ($q_0$). The asymptotic limit shows the error rate against entangled adversaries is at most half that against unentangled adversaries.
• Entangled Adversaries (Generalized): When generalizing to mixed states, unbounded randomness, and input-dependent transmission, the security requirements become significantly more demanding. The analysis (Fig. 6) reveals a severe degradation in performance: loss tolerance drops to $\eta > 75\%$ for 2 bases and $\eta > 90.6\%$ for 3 bases. This indicates that while the framework provides rigorous security, the current generalized model imposes strict experimental constraints.
• Feasibility: The paper estimates that against restricted entangled adversaries, secure implementation is possible up to $\approx 6.8$ km (assuming $q_0=5.5$), an improvement over the $2.8$ km limit of previous analyses. However, against generalized adversaries, current setups fall below the required transmission thresholds.

Significance and Claims
The paper claims to advance the practicality of QPV by reducing experimental complexity through the multi-basis protocol and by providing a more rigorous, albeit more restrictive, security framework.

• Practicality: The proposed protocol simplifies verifier hardware and communication requirements, making QPV more adaptable to real-world networks.
• Rigor: By generalizing the adversary model, the authors provide a "worst-case" security guarantee that accounts for realistic imperfections like input-dependent loss and shared randomness.
• Trade-off: The paper explicitly acknowledges a tension: the improved security analysis against generalized adversaries significantly degrades loss tolerance compared to restricted models. The authors state that this highlights the need for further improved security analysis techniques to bridge this gap.
• Application: The work positions QPV not just as a location verifier but as a viable, albeit complex, component for position-based cryptography and QKD authentication, offering a solution for scenarios where pre-shared keys are unavailable or compromised.

The authors conclude that while their improvements relax experimental requirements under restricted models, the degradation observed under generalized models underscores the difficulty of achieving practical QPV against the most powerful adversaries without further theoretical breakthroughs.