🔬 physics

Security evaluation of quantum distance-bounding protocols via semidefinite programming

This paper evaluates the security of quantum distance-bounding protocols by isolating their fast phase and utilizing semidefinite programming to compute optimal one-round distance-fraud and mafia-fraud attack probabilities for discrete-variable systems, while also providing estimates for continuous-variable scenarios.

Original authors: Kevin Bogner, Aysajan Abidin, Dave Singelée, Bart Preneel

Published 2026-09-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kevin Bogner, Aysajan Abidin, Dave Singelée, Bart Preneel

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where your car unlocks only when your key fob is physically right next to you, and a thief cannot trick the system by relaying signals from a fob that is actually miles away. This is the promise of distance-bounding protocols: digital systems that verify not just that you have the right secret code, but that you are standing exactly where you claim to be. In the classical world, this relies on measuring how long a radio signal takes to bounce back. But as technology advances, scientists are moving these checks into the quantum realm, using particles of light to create unbreakable timing guarantees. The challenge, however, has been that every new quantum design behaves differently, making it nearly impossible to compare their security fairly. One design might be strong against a specific type of trick, while another fails against a different one, leaving researchers without a common yardstick to judge which systems are truly safe.

A team of researchers at KU Leuven in Belgium has now solved this comparison problem by creating a universal testing ground for these quantum distance checks. They focused on the most critical moment in these protocols: the "fast phase," a split-second exchange where the prover must answer a challenge before light could possibly travel from a distant location. By isolating this single round of communication, the team developed a mathematical method to calculate the absolute best possible success rate for an attacker trying to deceive. Instead of guessing or simulating specific tricks, they used a powerful optimization tool called semidefinite programming to map out every single strategy an attacker could possibly use, ensuring that no potential loophole was missed. This approach allowed them to determine the exact security limits for several leading quantum protocols, revealing which ones hold up and which ones are more vulnerable than previously thought.

The researchers applied this method to four distinct quantum protocols, three of which use individual particles of light and one that uses continuous waves of light. For the particle-based systems, the math provided exact, unshakeable answers. They found that for the most common type of deception, where a dishonest user tries to pretend they are closer than they are, the success rate is exactly fifty percent across all the particle-based protocols they studied. This means that in a single round, a distant cheater has no better chance than flipping a coin. However, the story changes for the protocol using continuous waves of light, where the success rate for this same type of deception drops significantly to about thirty-six percent. The story also changes when looking at a more complex attack, where a criminal team works together—one standing near the verifier and another near the honest user—to relay information. In this scenario, the protocols performed very differently. The team discovered that the most widely studied protocol, known as QDB 2019, is actually less secure than previously believed, with a new analysis showing an attacker could succeed about ninety percent of the time. Another protocol, called Mutual QDB, also proved weaker than earlier estimates, with a success rate for attackers rising to seventy-five percent.

Perhaps the most significant finding was for two protocols that had never been rigorously tested in this way before. For a protocol based on the famous E91 entanglement design, the researchers calculated the first-ever security numbers, finding that an attacker could succeed roughly ninety-three percent of the time in the mafia-style fraud scenario. Similarly, for a protocol using continuous waves of light, they provided the first estimates, showing a success rate of about ninety-one percent for the same type of attack. These numbers are not just theoretical guesses; for the particle-based protocols, the team generated mathematical certificates that prove no other strategy could possibly do better. It is a bit like finding the absolute highest peak in a mountain range: once you have the map and the proof, you know for certain that no one can climb higher.

The study also clarified why some older designs are not included in this comparison. One early protocol relied on a final digital signature to prove authenticity, but when the researchers stripped away that signature to test the timing mechanism alone, the system collapsed completely, allowing an attacker to succeed one hundred percent of the time. This confirmed a vital principle: the timing mechanism itself must be strong enough to authenticate the user, not just rely on a later check. The researchers emphasized that these results apply to a single round of communication. In a real-world system with many rounds, the security would be even higher, but knowing the exact limit of a single round is the essential first step to building a secure whole. By providing these precise, comparable numbers, the team has given engineers a clear way to choose the most robust protocols for the future of secure, location-aware technology.

Title: Security evaluation of quantum distance-bounding protocols via semidefinite programming

Problem Statement
Quantum distance-bounding (QDB) protocols aim to verify that a prover possesses a valid secret key and is physically located within a specific distance of a verifier. These protocols utilize a timed "fast phase" of quantum communication to enforce distance constraints. However, comparing the security of different QDB protocols is challenging because optimal attacks depend heavily on the specific structure of the protocol's fast phase. Existing literature often focuses on protocol-specific attacks, which lack a uniform basis for comparison across different QDB variants (e.g., prepare-and-measure vs. entanglement-based). Furthermore, while Quantum Position Verification (QPV) has been extensively studied, its attack models involve nonconvex optimization problems due to the separation of attackers, making exact solutions difficult. The paper addresses the need for a unified framework to evaluate and compare the security of QDB protocols against distance fraud (DF) and mafia fraud (MF) in a single-round setting.

Methodology
The authors utilize the QDB security framework established by [BASP26] to formalize the capabilities of adversaries in DF and MF scenarios. They isolate the fast phase of the protocol into one-round games and model the optimal attack strategies using Semidefinite Programming (SDP).

Discrete-Variable (DV) QDB: For DV-QDB protocols, the authors demonstrate that the strategy sets for both DF and MF admit exact SDP representations.
- Distance Fraud: The distant prover must prepare a quantum state without knowledge of the verifier's challenge. This reduces to a "state SDP," where the adversary optimizes a density matrix to maximize acceptance probability.
- Mafia Fraud: The adversary acts as a cooperating pair (near the verifier and near the prover) but is modeled as a single sequential strategy in the one-round game. The adversary performs a "pre-ask" (querying the honest prover) before the timed challenge arrives, stores the quantum system, and then processes it with the verifier's challenge. This two-step strategy is represented as a "two-slot comb," leading to a "comb SDP."
- Exact Solvability: Unlike QPV, where the split nature of attackers leads to nonconvex optimization, the QDB MF adversary in the one-round game collapses into a sequential strategy. This allows the SDP optimum to equal the exact game value rather than a relaxation bound. The authors verify these values using matching primal (attack) and dual (certificate) witnesses in exact arithmetic.
Continuous-Variable (CV) QDB: For CV-QDB, the infinite-dimensional state space prevents exact SDP formulation. Instead, the authors employ a calibrated Gaussian attack model. They report success probability estimates derived from a finite-grid search over Gaussian parameters (probe amplitude, measurement angles) under a zero-added-response-noise assumption to maximize the attacker's potential.

Key Contributions

Unified Framework: The paper establishes a uniform method to compare QDB protocols by reducing their fast phases to one-round DF and MF games solvable via SDP.
Exact SDP Formulations: It provides the first exact SDP representations for the full strategy space of one-round DV-QDB attacks, distinguishing them from the relaxation-based approaches common in QPV.
New Security Bounds:
- QDB 2019: The study finds a stronger MF attack ( $p^*_{MF} \approx 0.9045$ ) than previously reported ($0.875$), achieved by keeping the quantum state intact during the pre-ask rather than collapsing it to a classical estimate.
- Mutual QDB: The study reports a new MF value of $0.75$, improving upon the previously reported $0.625$.
- E91 QDB: The paper provides the first reported one-round DF ($0.5$) and MF ( $\approx 0.9332$ ) values for this protocol.
- CV-QDB: It offers the first per-round DF ( $\approx 0.3592$ ) and MF ( $\approx 0.9138$ ) estimates for a Gaussian CV-QDB protocol.
Certification: For all DV results, the authors provide explicit primal and dual witnesses verified in exact arithmetic, ensuring the reported values are rigorous upper and lower bounds.

Results

Distance Fraud (DF): For all discrete-variable protocols analyzed, the optimal one-round DF success probability is exactly $0.5$. This indicates that DF does not distinguish between the security of these specific DV-QDB designs.
Mafia Fraud (MF): MF values vary significantly across protocols, ranging from $0.75$ (Mutual QDB) to $0.9332$ (E91 QDB). The variation depends on how effectively an adversary can convert information gained from a pre-ask into a valid response for a fresh challenge.
CV-QDB Estimates: The CV-QDB protocol shows a lower DF probability ( $\approx 0.36$ ) compared to DV protocols due to the continuous nature of the acceptance threshold, but a high MF probability ( $\approx 0.91$ ). These values are estimates dependent on specific calibration parameters (squeezing, threshold, energy bounds).
QDB 2017: The paper notes that QDB 2017, which relies on a final MAC for authentication rather than the fast phase itself, yields an MF value of $1$ in the one-round game (as the MAC is stripped). This highlights that ranging and authentication cannot be separated; the fast phase alone must provide MF resistance.

Significance and Claims
The paper claims that its primary contribution is the ability to compare QDB protocols on a common ground using exact convex formulations (SDPs) for discrete-variable systems. This contrasts with QPV, where attack optimization is generally nonconvex. The authors emphasize that these results are for reduced one-round fast-phase games and do not directly equate to full-protocol fraud probabilities, which involve multi-round correlations and adaptive strategies. However, the reported one-round values serve as the necessary constants for multi-round security analyses (e.g., via concentration bounds). The work updates the security understanding of existing protocols (QDB 2019, Mutual QDB) by identifying stronger attacks and provides the first quantitative security metrics for E91 QDB and CV-QDB. The authors explicitly state that Terrorist Fraud (TF) is outside the scope of this one-round analysis.

More like this