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

Protocolo de acotamiento de distancias basado en canales con ruido

Kirill Morozov, Valeri Korjik, Guillermo B. Morales-Luna

Published Jan 1, 2000• 0 citations
OpenAlex

Abstract

We consider a distance bounding protocol that enables the verifying party to determine a practical upperbound on the physical distance to a proving party. This protocol can protect against so called “mafia frauds” in which a party identifies himself to a verifying party using the third party being aware of it. Another attack on distance bounding protocol is a falsification of real distance between parties by dishonest prover. To prevent both types of frauds the distance bounding protocol should contain Bit Commitment primitive. In this paper we develop the idea to achieve this primitive and hence a distance bounding protocol based on making noisy channels connecting parties. To solve this problem we derive the formulas to estimate security and reliability of bit commitment protocol and present an algorithm that optimizes the main parameters provided minimal complexity. An example is given to show that this protocol is indeed reliable and informationtheoretically secure. We also discuss the problem on how to establish a noisy channel connecting parties. Palabras claves: Fraudes mafiosos, protocolo de acotamiento de distancias, primitiva de compromiso por bits, canales con ruido, ampliacion de privacidad, codigos de correccion de errores.

Related papers

Secure Distance Bounding Verification using Physical-Channel Properties

Hadi Ahmadi, Reihaneh Safavi–Naini

We consider the problem of distance bounding verification (DBV), where a proving party claims a distance and a verifying party ensures that the prover is within the claimed distance. Current approaches to "secure" distance estimation use signal's time of flight, which requires the verifier to have an accurate clock. We study secure DBV using physical channel properties as an alternative to time measurement. We consider a signal propagation environment that attenuates signal as a function of distance, and then corrupts it by an additive noise. We consider three attacking scenarios against DBV, namely distance fraud (DFA), mafia fraud (MFA) and terrorist fraud (TFA) attacks. We show it is possible to construct efficient DBV protocols with DFA and MFA security, even against an unbounded adversary; on the other hand, it is impossible to design TFA-secure protocols without time measurement, even with a computationally-bounded adversary. We however provide a TFA-secure construction under the condition that the adversary's communication capability is limited to the bounded retrieval model (BRM). We use numerical analysis to examine the communication complexity of the introduced DBV protocols. We discuss our results and give directions for future research.

arXiv:1303.0346•Mar 2, 2013•2 citations

Secure Distance Bounding

Xifan Zheng

Location (or distance) information of a device plays a significant role in current location-based systems. How to determine the location of a device or verify the location claims made by a device is challenging, as devices are untrusted and may have an incentive to claim a false location. In secure localization and positioning system, the trusted verifier(s) interact with the untrusted prover to determine its location or validate its location claim. In this thesis, we mainly focus on one of the prominent areas of such systems: distance bounding. Distance (upper) bounding (DUB) allows a verifier to verify whether a proving party is located within a certain distance bound. DUB protocols have many applications in secure authentication and location-based services. This thesis has two main contributions. The first is that we consider the dual problem of distance lower bounding (DLB), where the prover proves it is outside a distance bound from 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 physical assumptions and give detailed design of a DLB protocol with security analysis using our proposed model. This is the first treatment of the DLB problem in the untrusted prover setting with a number of applications, raising new research directions and opportunities in location based services. We discuss our results and propose directions for future research. One of the main assumptions which DUB protocols rely on is that the time that the prover spends in receiving the challenge, processing, and sending the response is negligible compared to the propagation time of the signal between the prover and verifier. This strict requirement poses difficulties on the implementation of DUB protocols and limits the possible development of applications for distance bounding as well. The second contribution in this thesis is that we design a novel one-round DUB protocol that uses one-way transmission time to estimate the distance instead of round-trip time, so that the assumption of negligible processing time is not required any longer. In order to prove the security, we formalize the notion of time in a distributed environment with adversarial users. In this model, time is implemented by a trusted party broadcasting unpredictable timestamps at a high frequency. We show that the timestamp is proved to be fresh and unpredictable. We then extend the time model to formalize DUB protocols and define corresponding attacks. Finally, we prove the security of our proposed distance bounding protocol and discuss potential issues when implementing such protocol. Besides these two main contributions, we also have the following two contributions: (1) we identify and analyze a new attack: false rejection attack, which poses serious threat to proximity-based authentications that uses distance bounding protocol for proximity evaluation; (2) We investigate the feasibility of replay attack in context-based proximity authentication using real-world data.

•Jan 1, 2015•0 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

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

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•50 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
We consider a distance bounding protocol that enables the verifying party to determine a practical upperbound on the physical distance to a proving party. This protocol can protect against so called “mafia frauds” in which a party identifies himself to a verifying party using the third party being aware of it. Another attack on distance bounding protocol is a falsification of real distance between parties by dishonest prover. To prevent both types of frauds the distance bounding protocol should contain Bit Commitment primitive. In this paper we develop the idea to achieve this primitive and hence a distance bounding protocol based on making noisy channels connecting parties. To solve this problem we derive the formulas to estimate security and reliability of bit commitment protocol and present an algorithm that optimizes the main parameters provided minimal complexity. An example is given to show that this protocol is indeed reliable and informationtheoretically secure. We also discuss the problem on how to establish a noisy channel connecting parties. Palabras claves: Fraudes mafiosos, protocolo de acotamiento de distancias, primitiva de compromiso por bits, canales con ruido, ampliacion de privacidad, codigos de correccion de errores.
We consider the problem of distance bounding verification (DBV), where a proving party claims a distance and a verifying party ensures that the prover is within the claimed distance. Current approaches to "secure" distance estimation use signal's time of flight, which requires the verifier to have an accurate clock. We study secure DBV using physical channel properties as an alternative to time measurement. We consider a signal propagation environment that attenuates signal as a function of distance, and then corrupts it by an additive noise. We consider three attacking scenarios against DBV, namely distance fraud (DFA), mafia fraud (MFA) and terrorist fraud (TFA) attacks. We show it is possible to construct efficient DBV protocols with DFA and MFA security, even against an unbounded adversary; on the other hand, it is impossible to design TFA-secure protocols without time measurement, even with a computationally-bounded adversary. We however provide a TFA-secure construction under the condition that the adversary's communication capability is limited to the bounded retrieval model (BRM). We use numerical analysis to examine the communication complexity of the introduced DBV protocols. We discuss our results and give directions for future research.
Location (or distance) information of a device plays a significant role in current location-based systems. How to determine the location of a device or verify the location claims made by a device is challenging, as devices are untrusted and may have an incentive to claim a false location. In secure localization and positioning system, the trusted verifier(s) interact with the untrusted prover to determine its location or validate its location claim. In this thesis, we mainly focus on one of the prominent areas of such systems: distance bounding. Distance (upper) bounding (DUB) allows a verifier to verify whether a proving party is located within a certain distance bound. DUB protocols have many applications in secure authentication and location-based services. This thesis has two main contributions. The first is that we consider the dual problem of distance lower bounding (DLB), where the prover proves it is outside a distance bound from 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 physical assumptions and give detailed design of a DLB protocol with security analysis using our proposed model. This is the first treatment of the DLB problem in the untrusted prover setting with a number of applications, raising new research directions and opportunities in location based services. We discuss our results and propose directions for future research. One of the main assumptions which DUB protocols rely on is that the time that the prover spends in receiving the challenge, processing, and sending the response is negligible compared to the propagation time of the signal between the prover and verifier. This strict requirement poses difficulties on the implementation of DUB protocols and limits the possible development of applications for distance bounding as well. The second contribution in this thesis is that we design a novel one-round DUB protocol that uses one-way transmission time to estimate the distance instead of round-trip time, so that the assumption of negligible processing time is not required any longer. In order to prove the security, we formalize the notion of time in a distributed environment with adversarial users. In this model, time is implemented by a trusted party broadcasting unpredictable timestamps at a high frequency. We show that the timestamp is proved to be fresh and unpredictable. We then extend the time model to formalize DUB protocols and define corresponding attacks. Finally, we prove the security of our proposed distance bounding protocol and discuss potential issues when implementing such protocol. Besides these two main contributions, we also have the following two contributions: (1) we identify and analyze a new attack: false rejection attack, which poses serious threat to proximity-based authentications that uses distance bounding protocol for proximity evaluation; (2) We investigate the feasibility of replay attack in context-based proximity authentication using real-world data.
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
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.
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.