Security evaluation of quantum distance-bounding protocols via semidefinite programming

Source: arXiv:2607.13464 · Published 2026-07-15 · By Kevin Bogner, Aysajan Abidin, Dave Singelee, Bart Preneel

TL;DR

This paper addresses the challenge of uniformly evaluating the security of quantum distance-bounding (QDB) protocols against distance-fraud (DF) and mafia-fraud (MF) attacks in their critical fast phase. Unlike quantum position verification (QPV) where attacker optimization problems are nonconvex and only relaxation bounds are available, the authors show that for discrete-variable QDB protocols the DF and MF attack games can be exactly reduced to convex semidefinite programs (SDPs). This exact reduction enables precise computation of the optimal one-round attack success probabilities, and yields explicit attack strategies along with matching certificates proving optimality. The paper also estimates attack success probabilities for continuous-variable QDB using a calibrated Gaussian attack model. Their analysis covers four representative QDB protocols, including two previously lacking known one-round attack values. The results demonstrate that while distance fraud attacks achieve a uniform success probability of 1/2 across protocols, mafia fraud distinguishes protocols with success probabilities ranging from 0.75 to 0.93 for discrete-variable ones, exceeding prior state-of-the-art attacks. The paper concludes that one-round mafia fraud resistance crucially depends on whether attackers can leverage information revealed early by the prover to answer fresh challenges.

Key findings

• One-round distance-fraud (DF) attacks succeed with probability exactly 0.5 for all discrete-variable QDB protocols evaluated.
• One-round mafia-fraud (MF) success probabilities vary significantly across discrete-variable QDB protocols, ranging from 0.75 (Mutual QDB) up to 0.9332 (E91 QDB), exceeding all prior results.
• The MF games reduce to convex semidefinite programs whose optima are computed exactly, providing explicit attack strategies and matching dual certificates proving no better attack exists (Appendix A).
• Continuous-variable QDB MF attacks are estimated under a restrictive Gaussian model, reporting success around 0.9138 without noise, but these estimates are not certified optima.
• The classical and quantum information timing constraints imply that MF adversaries collapse to single sequential strategies modeled as two-slot combs, enabling convex SDP formulation unlike bipartite nonconvex QPV attacks.
• QDB 2017 protocol, which separates proximity check and final authentication, falls outside this analysis scope due to its fast phase being unauthenticated.
• Previously unknown one-round MF values are reported for the E91 QDB and the continuous-variable QDB protocols for the first time.
• MF resistance hinges on whether the attacker can exploit early revealed prover information before answering fresh verifier challenges.

Threat model

The adversary is a quantum polynomial-time attacker operating under strict timing and distance constraints of the QDB security framework. In distance fraud, the adversary is a dishonest prover located beyond the allowed distance bound, who must respond before receiving the verifier's challenge in the fast phase. In mafia fraud, the adversary consists of two cooperating quantum attackers positioned near the verifier and honest prover, respectively, able to pre-ask the prover and relay or manipulate messages under timing constraints, but restricted from violating physical causality or breaking ideal cryptographic primitives. Terrorist fraud and multi-round colluding adversaries are out of scope.

Methodology — deep read

The core methodological contribution is reducing quantum distance-bounding one-round fast-phase DF and MF attack games to semidefinite programs (SDPs) that optimize over quantum strategies. The authors begin by fixing the threat model and adversarial capabilities under the QDB security framework [BASP26]. The adversary is limited by physical time bounds and distance constraints: in DF, the dishonest prover outside range must prepare a response state independent of the verifier's fresh challenge; in MF, attackers form a cooperating pair positioned near verifier and honest prover, allowed to pre-ask the prover before the verifier's challenge but must respond within fast timing constraints.

Data provenance comprises classical-quantum protocol branches, representing secret keys, basis choices, and measurement outcomes. The discrete-variable QDB protocols handle finite-dimensional qubit states, enabling a finite-dimensional SDP formulation. Continuous-variable QDB is modeled under calibrated Gaussian attacks with finite grids.

For DF, the adversary strategy is a state preparation mapping the prover's response-time view (containing slow-phase secrets but not the fast challenge) to a density operator, constrained by positivity and unit trace. The verifier has a set of accept operators corresponding to each protocol branch. The DF success probability is maximized over these response states, forming a convex SDP (Equation 3).

The MF adversary is modeled as a two-step sequential quantum comb acting on registers Q (probe sent to honest prover), R (prover response), C (verifier challenge), and O (attacker output). The comb is a positive semidefinite operator subject to normalization constraints ensuring physical realizability. The honest prover channel and verifier's acceptance operator are combined into a tester operator per branch. The MF success probability is the expectation over branches of the trace between the comb and tester operators. Maximizing over the comb subject to the SDP constraints yields the exact MF attack value (Equation 4).

The evaluation protocols use this SDP formulation to find optimal one-round attack values. For discrete-variable protocols (QDB 2019, Mutual QDB, E91 QDB), exact primal and dual SDP solutions are computed. Dual solutions certify the optimum by bounding the success probability from above. These certificates are verified in exact arithmetic beyond floating-point solver accuracy. For continuous-variable QDB, SDPs are infeasible, so the authors use a calibrated Gaussian finite-grid attack estimator to report approximate attack success probabilities.

This approach enables uniform comparisons of DF and MF attack values across four major QDB protocols, revealing previously unknown values and improvements over prior results. The authors clarify that their one-round fast-phase analysis excludes correlations across multiple protocol rounds and terrorist fraud attacks, which require different models.

Finally, the paper provides detailed SDP formulations, proofs of correctness for the reductions, and verification procedures for the primal-dual witnesses assuring reproducibility. However, full code or frozen weights are not released, and the continuous-variable results are approximate rather than certified.

Technical innovations

• Reduction of one-round DF and MF attack games for discrete-variable QDB protocols to exact convex semidefinite programs, enabling computation of definitive success probabilities.
• Proof that in one-round MF games the cooperating attacker pair collapses to a single sequential strategy modeled as a two-slot comb, resulting in convex optimization unlike nonconvex QPV attacks.
• Certification of optimal MF attack values via construction of matching primal and dual SDP solutions verified in exact arithmetic, not depending on solver floating-point precision.
• Application of a calibrated Gaussian attack estimation method to continuous-variable QDB, providing first approximate one-round DF and MF values under realistic noise assumptions.

Baselines vs proposed

• QDB 2019: prior MF attack success = 0.875 vs proposed MF = 0.9045
• Mutual QDB: prior MF attack success = 0.625 vs proposed MF = 0.75
• E91 QDB: prior MF attack success unknown vs proposed MF = 0.9332
• CV-QDB: prior MF attack unknown vs proposed MF estimate = 0.9138
• For all discrete-variable QDB protocols, DF success probability = 0.5 matches theoretical limit.

Limitations

• Analysis is limited to one-round fast-phase attack games; multi-round or full-protocol security is not directly addressed.
• The continuous-variable QDB results are estimated via a finite-grid Gaussian model and are not certified optimal values.
• Terrorist fraud resistance is not considered because it inherently involves multiple protocol runs.
• Some protocols, like QDB 2017, with separate final MAC authentication fall outside the benchmark scope.
• The SDP formulations assume ideal randomness with perfect quantum-secure pseudorandom functions and noiseless channels for discrete protocols.
• No explicit modeling of implementation-level or side-channel attacks that could affect practical security.

Open questions / follow-ons

• How do the one-round exact attack values compose or degrade over multiple rounds in real QDB protocols to influence full-protocol security?
• Can the SDP framework be extended or adapted to analyze terrorist fraud attacks involving multiple protocol executions and prover accomplices?
• What are the effects of realistic noise, loss, and imperfect quantum hardware on the estimated MF and DF success probabilities, especially for continuous-variable QDB?
• Can the SDP approach be generalized to other position-verification or proximity-authentication protocols involving higher-dimensional quantum systems or multipartite settings?

Why it matters for bot defense

For bot-defense and CAPTCHA practitioners, this work sheds light on foundational quantum protocols aimed at verifying physical proximity using quantum communication. While not directly applicable to classical CAPTCHA challenges or typical web bot defenses, the methodology exemplifies how advanced convex optimization tools like semidefinite programming enable exact security analyses of complex quantum authentication systems. Practitioners interested in future-proofing authentication mechanisms against quantum adversaries can draw on this approach to understand the limits of proximity-based quantum authentication designs and their precise vulnerabilities. The collapse of multiparty adversaries to convex models hints at potential simplifications in analyzing complex attacker strategies in other authentication contexts. However, adopting these quantum protocols would require addressing multi-round and side-channel considerations absent here.

Cite

@article{arxiv2607_13464,
  title={ Security evaluation of quantum distance-bounding protocols via semidefinite programming },
  author={ Kevin Bogner and Aysajan Abidin and Dave Singelee and Bart Preneel },
  journal={arXiv preprint arXiv:2607.13464},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.13464}
}

Read the full paper

• arXiv:2607.13464 (abstract)
• arXiv:2607.13464 (PDF)