Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Communications Letters

Security Analysis of YKHL Distance Bounding Protocol with Adjustable False Acceptance Rate

Chong Hee Kim

Published Aug 25, 2011• 8 citations
Publisher

Abstract

A distance bounding protocol enables one entity to determine an upper bound on the physical distance to the other entity as well as to authenticate the other entity. It measures the round-trip time of exchanged messages that normally consist of n rounds of a single-bit challenge and a single-bit response. Let FARMand FARDbe the false acceptance rate against mafia fraud attack and distance fraud attack, respectively. Brands and Chaum designed the first distance bounding protocol that has (FARM, FARD) = ((½)n, (½)n). Recently Yum et al. proposed a flexible distance bounding protocol, in IEEE Communications Letters, asserting that its false acceptance rate (FARM, FARD) can be chosen from ((½)n, (½)n) to ((¼)n, (3/4)n). However, we introduce a new attack that achieves a higher false accep tance rate, where (FARM, FARD) varies from ((½)n, (½)n) to ((½)n, (½)n/2).

DOI
10.1109/lcomm.2011.080811.111299

Related papers

Security Analysis of the Distance Bounding Protocol Proposed by Jannati and Falahati

Fatemeh Baghernejad, Nasour Bagheri, Masoumeh Safkhani

In this paper, the security of a distance bounding protocol is analyzed which has been recently proposed by Jannati and Falahati (so-called JF). We prove that an adversary can recover key bits of JF protocol with probability of “1” while the complexity of attack is “2n” runs of protocol. In addition, we propose an improved protocol and prove that the improved protocol is resistant to mafia fraud attack, distance fraud attack and key recovery attack.

•Jul 1, 2014•5 citations

Security evaluation of quantum distance-bounding protocols via semidefinite programming

Kevin Bogner, Aysajan Abidin, Dave Singelee +1 more

Quantum distance-bounding (QDB) protocols let a verifier check that a prover is both genuine and physically nearby. During a timed fast phase of quantum communication, the verifier measures round-trip times to obtain an upper bound on the prover's distance. For a uniform comparison, we isolate the fast phase and study one-round distance-fraud (DF) and mafia-fraud (MF) games. For discrete-variable QDB, we show that these games reduce to convex optimization problems and can therefore be solved exactly with semidefinite programming; each MF value comes with an explicit attack achieving it and a matching certificate that no attack does better. This contrasts with quantum position verification, where an attack is split between two separated parties, so its optimization is nonconvex and analyses rely on relaxations. In our MF game, the cooperating pair collapses to a single sequential strategy, which keeps the game convex and its exact value computable. Across the discrete-variable protocols we examine, the best one-round DF attack succeeds with the same probability ($1/2$) for every protocol, whereas MF clearly separates the protocols. For continuous-variable QDB, we report estimated attack success probabilities from a calibrated Gaussian attack model. The benchmark covers protocols whose fast phase itself authenticates the prover; designs that follow Brands and Chaum and instead bind the fast phase with a final authenticated message, like the earliest QDB proposal, fall outside it and are treated separately. Of the four protocols studied, two had no previously known one-round attack values, and we report the first ones; for the other two, we find MF attacks with higher success probability than previously reported. Overall, one-round MF resistance depends on whether an attacker can use information revealed early by the prover to answer a fresh challenge from the verifier.

quant-pharXiv:2607.13464•Jul 16, 2026•0 citations

Mutual implementation of predefined and random challenges over RFID distance bounding protocol

Hoda Jannati, Abolfazl Falahati

Distance bounding protocols are launched based upon the round trip time measurements of the carried out messages to defend RFID systems against the relay attack. In such protocols, the reader authenticates tags and also estimates an upper bound for the physical distance between the tag and itself. Distance bounding protocols are vulnerable to mafia fraud and distance fraud attacks. In this paper, a new distance bounding protocol is proposed based on mutual utilization of binary predefined and random challenges. Moreover, this protocol is analyzed to compute the attacker's success probability due to mafia fraud and distance fraud attacks. In this case, the analysis and simulation results show that the proposed protocol obtains the desirable attackers' success probabilities, with minimum system memory requirement and minimum number of rounds compared with other distance bounding protocols employed by RFID systems.

International ISC Conference on Information Security and Cryptology (ISCISC)•Sep 1, 2012•14 citations

Security Framework for Quantum Distance-Bounding

Kevin Bogner, Aysajan Abidin, Dave Singelee +1 more

Distance-bounding (DB) protocols let a verifier upper-bound a prover's physical distance by timing rapid challenge-response exchanges. Quantum communication promises simpler DB protocols with stronger security guarantees, yet existing quantum distance-bounding (QDB) proposals are analysed in ad-hoc models and, to the best of our knowledge, lack a common game-based treatment of standard fraud attacks. We contribute (i) a reusable security framework for QDB that fixes system and timing assumptions, specifies a quantum-capable adversary model, formalises distance-, mafia-, and terrorist-fraud experiments, and includes a simple i.i.d. depolarizing noise model; and (ii) an application of this framework to a published QDB protocol. For this protocol we characterise the honest per-round acceptance probability under noise and lift it to the multi-round setting, yielding explicit completeness guarantees as a function of the number of fast rounds, the acceptance threshold, and the noise parameter. For active adversaries we bound the per-round success probability of distance-fraud attacks and analyse the best known mafia-fraud strategy, deriving corresponding multi-round soundness bounds. We also show that the protocol is inherently insecure against terrorist-fraud in our model. The framework cleanly separates protocol-independent definitions from protocol-specific analysis and can be used to evaluate existing and future QDB protocols on a common basis.

quant-pharXiv:2604.16071•Quantum Information Processing•Apr 20, 2026•0 citations

Distance-bounding for RFID: Effectiveness of ‘terrorist fraud’ in the presence of bit errors

Gerhard Petrus Hancke

Time-of-flight distance-bounding protocols are potentially useful in RFID and NFC environments and are designed to discourage a number of attacks that take advantage of the inherent assumption that a token and reader that manages to communicate are located in close physical proximity to each other. These protocols are dependent on time measurements made at the physical layer of the communication channel, and thus require special high bandwidth channels with low latency. Executing a distance-bound protocol on a suitable channel in a constrained environment would potentially allow for bit errors during communication. Currently, terrorist fraud is discouraged in distance-bounding protocols by ensuring that a prover collaborating with an the attacker in this fraud has to make his secret key known to the attacker. We discuss the effect of making a protocol resistant to bit errors and show that the approach to design protocols against terrorist fraud is significantly weakened by error resistance, as a prover is potentially able to keep his key secret or hinder an attacker from learning his key.

IEEE International Conference on RFID Technology and Applications (RFID-TA)•Nov 1, 2012•51 citations

Distance Lower Bounding.

Xifan Zheng, Reihaneh Safavi–Naini, Hadi Ahmadi

Abstract. Distance (upper)-bounding (DUB) allows a verifier to know whether a proving party is located within a certain distance bound. DUB protocols have many applications in secure authentication and location based services. We consider the dual problem of distance lower bound-ing (DLB), where the prover proves it is outside a distance bound to the verifier. We motivate this problem through a number of application scenarios, and model security against distance fraud (DF), Man-in-the-Middle (MiM), and collusion fraud (CF) attacks. We prove impossibility of security against these attacks without making physical assumptions. We propose approaches to the construction of secure protocols under reasonable assumptions, and give detailed design of our DLB protocol and prove its security using the above model. This is the first treatment of the DLB problem in the untrusted prover setting, with a number of applications and raising new research questions. We discuss our results and propose directions for future research. 1

•Jan 1, 2014•0 citations
A distance bounding protocol enables one entity to determine an upper bound on the physical distance to the other entity as well as to authenticate the other entity. It measures the round-trip time of exchanged messages that normally consist of n rounds of a single-bit challenge and a single-bit response. Let FARMand FARDbe the false acceptance rate against mafia fraud attack and distance fraud attack, respectively. Brands and Chaum designed the first distance bounding protocol that has (FARM, FARD) = ((½)n, (½)n). Recently Yum et al. proposed a flexible distance bounding protocol, in IEEE Communications Letters, asserting that its false acceptance rate (FARM, FARD) can be chosen from ((½)n, (½)n) to ((¼)n, (3/4)n). However, we introduce a new attack that achieves a higher false accep tance rate, where (FARM, FARD) varies from ((½)n, (½)n) to ((½)n, (½)n/2).
Quantum distance-bounding (QDB) protocols let a verifier check that a prover is both genuine and physically nearby. During a timed fast phase of quantum communication, the verifier measures round-trip times to obtain an upper bound on the prover's distance. For a uniform comparison, we isolate the fast phase and study one-round distance-fraud (DF) and mafia-fraud (MF) games. For discrete-variable QDB, we show that these games reduce to convex optimization problems and can therefore be solved exactly with semidefinite programming; each MF value comes with an explicit attack achieving it and a matching certificate that no attack does better. This contrasts with quantum position verification, where an attack is split between two separated parties, so its optimization is nonconvex and analyses rely on relaxations. In our MF game, the cooperating pair collapses to a single sequential strategy, which keeps the game convex and its exact value computable. Across the discrete-variable protocols we examine, the best one-round DF attack succeeds with the same probability (1/21/21/2) for every protocol, whereas MF clearly separates the protocols. For continuous-variable QDB, we report estimated attack success probabilities from a calibrated Gaussian attack model. The benchmark covers protocols whose fast phase itself authenticates the prover; designs that follow Brands and Chaum and instead bind the fast phase with a final authenticated message, like the earliest QDB proposal, fall outside it and are treated separately. Of the four protocols studied, two had no previously known one-round attack values, and we report the first ones; for the other two, we find MF attacks with higher success probability than previously reported. Overall, one-round MF resistance depends on whether an attacker can use information revealed early by the prover to answer a fresh challenge from the verifier.
Distance bounding protocols are launched based upon the round trip time measurements of the carried out messages to defend RFID systems against the relay attack. In such protocols, the reader authenticates tags and also estimates an upper bound for the physical distance between the tag and itself. Distance bounding protocols are vulnerable to mafia fraud and distance fraud attacks. In this paper, a new distance bounding protocol is proposed based on mutual utilization of binary predefined and random challenges. Moreover, this protocol is analyzed to compute the attacker's success probability due to mafia fraud and distance fraud attacks. In this case, the analysis and simulation results show that the proposed protocol obtains the desirable attackers' success probabilities, with minimum system memory requirement and minimum number of rounds compared with other distance bounding protocols employed by RFID systems.
Distance-bounding (DB) protocols let a verifier upper-bound a prover's physical distance by timing rapid challenge-response exchanges. Quantum communication promises simpler DB protocols with stronger security guarantees, yet existing quantum distance-bounding (QDB) proposals are analysed in ad-hoc models and, to the best of our knowledge, lack a common game-based treatment of standard fraud attacks. We contribute (i) a reusable security framework for QDB that fixes system and timing assumptions, specifies a quantum-capable adversary model, formalises distance-, mafia-, and terrorist-fraud experiments, and includes a simple i.i.d. depolarizing noise model; and (ii) an application of this framework to a published QDB protocol. For this protocol we characterise the honest per-round acceptance probability under noise and lift it to the multi-round setting, yielding explicit completeness guarantees as a function of the number of fast rounds, the acceptance threshold, and the noise parameter. For active adversaries we bound the per-round success probability of distance-fraud attacks and analyse the best known mafia-fraud strategy, deriving corresponding multi-round soundness bounds. We also show that the protocol is inherently insecure against terrorist-fraud in our model. The framework cleanly separates protocol-independent definitions from protocol-specific analysis and can be used to evaluate existing and future QDB protocols on a common basis.
Time-of-flight distance-bounding protocols are potentially useful in RFID and NFC environments and are designed to discourage a number of attacks that take advantage of the inherent assumption that a token and reader that manages to communicate are located in close physical proximity to each other. These protocols are dependent on time measurements made at the physical layer of the communication channel, and thus require special high bandwidth channels with low latency. Executing a distance-bound protocol on a suitable channel in a constrained environment would potentially allow for bit errors during communication. Currently, terrorist fraud is discouraged in distance-bounding protocols by ensuring that a prover collaborating with an the attacker in this fraud has to make his secret key known to the attacker. We discuss the effect of making a protocol resistant to bit errors and show that the approach to design protocols against terrorist fraud is significantly weakened by error resistance, as a prover is potentially able to keep his key secret or hinder an attacker from learning his key.
Abstract. Distance (upper)-bounding (DUB) allows a verifier to know whether a proving party is located within a certain distance bound. DUB protocols have many applications in secure authentication and location based services. We consider the dual problem of distance lower bound-ing (DLB), where the prover proves it is outside a distance bound to the verifier. We motivate this problem through a number of application scenarios, and model security against distance fraud (DF), Man-in-the-Middle (MiM), and collusion fraud (CF) attacks. We prove impossibility of security against these attacks without making physical assumptions. We propose approaches to the construction of secure protocols under reasonable assumptions, and give detailed design of our DLB protocol and prove its security using the above model. This is the first treatment of the DLB problem in the untrusted prover setting, with a number of applications and raising new research questions. We discuss our results and propose directions for future research. 1