Method and device for proving his identity

The present application claims priority from U.S. provisional application U.S. 61/951,255 filed on Mar. 11, 2014, the entire contents of which is hereby incorporated by reference.

The present invention is related to a distance bounding methods and to devices allowing a user to prove his identity and proximity to a verifier.

Some important applications such as NFC-based payments or RFID access cards in our daily lives provide services according to the user's location. Relay attacks are serious threats against these applications. For instance, if someone make payment with a card on a malicious device then the device can relay to a fake card which is paying for something more expensive. As wireless technologies become more and more pervasive, being used daily in access control, remote unlocking credit-card payments and beyond, relay attacks also become a growing threat to the social acceptance of these techniques. It seems likely that nearly all wireless devices will eventually have to implement solutions to thwart these types of fraud.

To defeat relay attacks, Brands and Chaum introduced the notion of distance-bounding protocols in S. Brands, D. Chaum, “Distance-Bounding Protocols (Extended Abstract)”, Advances in Cryptology EUROCRYPT '93, Lofthus, Norway, Lecture Notes in Computer Science 765, pp. 344-359, Springer-Verlag, 1994.

Distance bounding is a special problem of position-based cryptography, as described by Chandran et al. in N. Chandran, V. Goyal, R. Moriarty, R. Ostrovsky, “Position Based Cryptography”, Advances in Cryptology CRYPTO '09, Santa Barbara, Calif., U.S.A., Lecture Notes in Computer Science 5677, pp. 391-407, Springer-Verlag, 2009.

Loana Boureanu and Serge Vaudenay describe an implementation in “Challenges in Distance-Bounding”, Security & Privacy, IEEE, 2015/1, Volume 12, Band 1, pages 41-48.

These distance-bounding protocols rely on information being local and incapable of travelling faster than the speed of light. So, in distance-bounding, an RFID reader can assess when participants are close enough because the round-trip communication time must have been short enough. The whole idea of distance-bounding is that a prover, holding a key x, demonstrates that he is close to a verifier (who also knows this key x).

The literature on distance-bounding considers several threat models:

Distance fraud (DF): a far-away malicious prover tries to illicitly pass the protocol. Mafia fraud (MF): a man-in-the-middle (MiM) adversary between a far-away honest prover and a verifier tries to exploit the prover's insights to make the verifier accept. (This generalizes relay attacks as not only does this adversary relay, but he may also modify the messages involved.). This attack is described in Y. Desmedt, “Major Security Problems with the “Unforgeable” (Feige-) Fiat-Shamir Proofs of Identity and How to Overcome Them”, Congress on Computer and Communication Security and Protection Securicom '88, Paris, France, pp. 147-159, SEDEP Paris France, 1988. Terrorist fraud (TF): a far-away malicious prover colludes with an adversary to make the verifier accept the adversary's rounds on behalf of this far-away prover, in such a way that the adversary gains no advantage to later pass the protocol on his own. This attack is described in the previously mentioned publication of Y. Desmedt. Impersonation fraud: An adversary tries to impersonate the prover to the verifier. This attack is described in G. Avoine, A. Tchamkerten, “An Efficient Distance Bounding RFID Authentication Protocol: Balancing False-Acceptance Rate and Memory Requirement”, In Information Security ISC '09, Pisa, Italy, Lecture Notes in ComputerScience 5735, pp. 250-261, Springer-Verlag, 2009. Distance hijacking [15]: A far-away prover takes advantage of some honest, active provers (of which one is close) to make the verifier grant privileges for the far-away prover. This attack is described in C. J. F. Cremers, K. B. Rasmussen, B. Schmidt, S. Capkun, “Distance Hijacking Attacks on Distance Bounding Protocols”, IEEE Symposium on Security and Privacy S&P '12, San Francisco, Calif., USA, pp. 113-127, IEEE Computer Society, 2012.

S. Vaudenay, “On Modeling Terrorist Frauds”, In Provable Security ProvSec '13, Melaka, Malaysia, Lecture Notes in Computer Science 8209, pp. 1-20, Springer-Verlag, 2013.17, proposed a formal model of the attacks and protocols (herein called the BMV model) including the notion of time. A more complete model is described in Ioana Boureanu, Aikaterini Mitrokotsa, Serge Vaudenay, “Practical and provably secure distance-bounding”, 2015, Journal of Computer Security, IOS Press, Available as IACR Eprint 2013/465 report, 2013, http://eprint.iacr.org/2013/465.pdf. Based on all these models, the paper factors all the previously enumerated common frauds into three possible threats:

Distance fraud. This is the classical notion, but concurrent runs with many participants is additionally considered. I.e., it includes other possible provers (with other secrets) and verifiers. Consequently, this generalized distance fraud also includes distance hijacking. Man-in-the-middle. This formalization considers an adversary working in two phases. During a learning phase, this adversary can interact with many honest provers and verifiers. Then, the attack phase contains a far away honest prover of given ID and possibly many other honest provers and other verifiers. The goal of the adversary is to make the verifier accept the proof with ID. Clearly, this generalizes mafia fraud (capturing relay attacks) and includes impersonation fraud. Collusion fraud. This formalization considers a far-away prover holding x who helps an adversary to make the verifier accept. This might be in the presence of many other honest participants. However, there should be no man-in-the-middle attack stemming from this malicious prover. I.e., one should not extract from this prover any advantage to (later) run a man-in-the-middle attack.

In S. Vaudenay, “On Modeling Terrorist Frauds”, Provable Security ProvSec '13, Melaka, Malaysia, Lecture Notes in Computer Science 8209, pp. 1-20, Springer-Verlag, 2013.17, the last threat model is replaced by a notion coming from interactive proofs:

Soundness. For all experiment with a verifier V, there exists an extractor such that the following holds: if this extractor is given as input several views of all participants which were close to V in several executions and which made him accept therein, then this extractor reconstructs the secret x. This was further shown to generalize collusion-fraud resistance.

There exist many distance-bounding protocols, but nearly all are broken in some way. For instance, the protocols from G. P. Hancke, M. G. Kuhn, “An RFID Distance Bounding Protocol” Conference on Security and Privacy for Emerging Areas in Communications Networks SecureComm '05, Athens, Greece, pp. 67-73, IEEE, 2005, as well as the protocol from C. H. Kim, G. Avoine, “RFID Distance Bounding Protocol with Mixed Challenges to Prevent Relay Attacks”, Cryptology and Network Security, 8th International Conference CANS 2009, Kanazawa, Japan, Lecture Notes in Computer Science 5888, pp. 119-133, Springer-Verlag, 2009, or the protocol from V. Nikov, M. Vauclair, “Yet Another Secure Distance-Bounding Protocol”, Proceedings of SECRYPT '08, Porto, Portugal, pp. 218-221, INSTICC Press, 2008, are vulnerable to Terrorist Fraud TF. Man-in-the middle attacks are also effective against many distance-bounding protocols, for example if a man-in-the-middle is placed at an authorised distance from the verifier.

In particular, G. P. Hancke, “Distance Bounding for RFID: Effectiveness of Terrorist Fraud”, Conference on RFID-Technologies and Applications RFID-TA '12, Nice, France, pp. 91-96, IEEE, 2012, observed that noisy-resilience in nearly all protocols allowed to mount a Terrorist Fraud Attack. This is also valid for the SwissKnife protocol described by C. H. Kim, G. Avoine, F. Koeune, F.-X. Standaert, O. Pereira. The Swiss-Knife RFID Distance Bounding Protocol. In Information Security and Cryptology ICISC '08, Seoul, Korea, Lecture Notes in Computer Science 5461, pp. 98-115, Springer-Verlag, 2009.

So, the problem of making provably secure distance bounding is of utmost importance.

We will now describe the SKI protocol and the Fischlin-Onete (FO) protocol of the prior art. Those two protocols provide an all-encompassing proven security, i.e., they protect against all the above threats.

The SKI Protocol

The SKI protocol is illustrated on FIG. 5 . It is described in Boureanu, A. Mitrokotsa, S. Vaudenay, “Secure & Lightweight Distance-Bounding”, Lightweight Cryptography for Security and Privacy LightSec '13, Gebze, Turkey, Lecture Notes in Computer Science 8162, pp. 97-113, Springer-Verlag, 2013; in I. Boureanu, A. Mitrokotsa, S. Vaudenay, “Practical & Provably Secure Distance-Bounding” available as IACR Eprint 2013/465 report, 2013. http://eprint.iacr.org/2013/465.pdf; in I. Boureanu, A. Mitrokotsa, S. Vaudenay, “Towards Secure Distance Bounding”, “Fast Software Encryption 13”, Singapore, Lecture Notes in Computer Science 8424, pp. 55-67, Springer-Verlag, 2013, among others.

In the SKI protocol, a secret xϵ{0,1} s is considered, given a security parameter s. The secret is shared between the prover p and the verifier v. The function f must be a PRF with circular-PRF security. It uses some other parameters based on s: the number of rounds n, a threshold τ, and the nonce length l nonce .

Given a vector μ, the linear function L μ is defined by

L μ ( x )=(μ· x, . . . , μ·x )

Namely, all bits are set to the dot product between μ and x. With x′=Lμ(x), Hancke's terrorist fraud [20] would reveal a majority of the bits of x′ thus leaking L μ (x). Since L μ is not chosen by the prover p, by repeating the attack, we can collect enough information about x to reconstruct x. So, Hancke's terrorist fraud is prevented.

There exists several variants of SKI with different properties. Namely, secret sharing schemes other than the one in FIG. 7 can be considered. Other leakage schemes L μ can also be considered.

The FO Protocol

The FO protocol is described in M. Fischlin, C. Onete, “Terrorism in Distance Bounding: Modelling Terrorist-Fraud Resistance”, Applied Cryptography and Network Security ACNS '13, Banff AB, Canada, Lecture Notes in Computer Science 7954, pp. 414-431, Springer-Verlag, 2013. It is also depicted The FO protocol is depicted on FIG. 6 .

The protocol builds up on the Swiss-Knife protocol and uses a special escape strategy b=1. Normal users shall only use b=0. For b=1, the verifier expect a simple echo on challenges (i.e., r i =c i ), does not verify the tag t, and has a probabilistic behavior: it accepts with probability p e where e is the Hamming distance between I and the secret y.

Theorem 19 DF-resistance of FO) The FO scheme α-resists to distance frauds, for

α = Tail ⁡ ( w , τ - n + w , 1 2 ) ,

where w is the Hamming weight of y. On average over y, this is

α = Tail ⁡ ( n , τ , 3 4 ) .

For

τ n > 3 4 + cte ,

this is negligible.

The FO protocol offers some form of terrorist-fraud, but, as the SKI protocol, requires a high number of rounds to be resistant.

It is an aim of the present invention to provide another method for offering provably secure distance bounding.

It is another aim of the present invention to provide a method offering provably secure distance bounding which is more efficient, i.e., which requires less rounds and/or less data to be exchanged for offering the same reliability at a given level of noise.

According to the invention, these aims are achieved by means of a method allowing a prover (p) holding a secret key (x) to prove its identity to a verifier (v) and to prove to this verifier that he is within a predetermined distance of this verifier, said method comprising an initialization phase and a distance bounding phase, said initialization phase comprising the following steps:

the prover (p) picks a first nonce (N p ) and communicates this first nonce to the verifier;

the verifier (v) picks a first random vector (a), a leak function (L μ ), and a second nonce (N v );

the verifier uses said leak function (L μ ) to compute a modified secret (x′) depending on the leak (L μ (x)) of said secret (x);

the verifier transmits to said prover said leak function (L μ ) and said second nonce (N v );

the prover retrieves said first random vector (a) and said modified secret (x′),

wherein said first random vector (a) and said modified secret (x′) are used by said prover during said distance bounding phase for computing responses (r i ) to challenges (c i ) sent by said verifier to said prover.

This method is a distance-bounding (DB) protocol. It behaves like a traditional interactive proof system as it really is a proof of proximity. In particular, it satisfies: 1. completeness (i.e., an honest prover close to the verifier will certainly pass the protocol); 2. soundness (i.e., if the verifier accepts the protocol, then we could extract from close-by participants the information to define a successful prover); 3. security (i.e., no participant shall be able to extract some information from the honest prover to make the verifier accept).

The different parameters (nonces, vectors, etc) are not necessarily transmitted in clear form; they may be transformed or embedded in matrices or vectors.

For example, in one embodiment, the verifier may further compute a computed vector (M) as a function of said first vector (a), said first nonce (N p ), said second nonce (N v ), and said leak function (L μ ), and transmit said computed vector (M) transmits to said prover. The prover then receives from said verifier the computed vector (M). The prover may use the computed vector to retrieve said random vector.

In a preferred embodiment, the method further comprises a challenge verification phase after said distance bounding phase,

wherein said prover sends to said verifier during said verification phase a parameter (t) that depends on challenges (c′ i ) received by said prover during said distance bounding phase,

wherein said verifier uses said parameter (t) to determine during said verification phase whether the challenges (c′ i ) received by said prover during said distance bounding phase correspond to the challenges (c i ) sent to said prover.

The challenges (c i ) may be non binary.

The method may comprise a step during said initialization phase during which said verifier picks a second random vector (b) with a Hamming weight of n/2, where n is the number of challenges sent during said distance bounding phase,

wherein said modified secret (x′) is the addition of the leak of said secret (L μ (x)) and of the second random vector (b);

wherein said verifier transmits said second random vector (b) to said prover.

The prover p may be a device or apparatus comprising software allowing him to prove its identity. For example, the prover may be embedded as a wireless smart card, or as a NFC device, or as an electronic access control device.

The verifier v may be a device or apparatus comprising software allowing him to verify a claimed identity and distance of a prover. For example, the verifier may be embedded as a computer, point-of-sale-equipment, server, smartphone etc.

As seen from a prover p, an embodiment of the method of the present invention comprises an initialization phase and a distance bounding phase, said initialization phase comprising the following steps:

the prover picks a first nonce (N p ) and communicates this first nonce to the verifier;

the prover receives from said verifier a leak function (L μ ) and a second nonce (N v );

the prover determines a first random vector (a) and a modified secret (x′) based on the received the first nonce, on the second nonce, on the leak function, and on the secret key (X);

said prover uses said first random vector (a) and said modified secret (x′) during a distance bounding phase for computing responses (r i ) to challenges (c i ) received from said verifier.

The method may further comprise a challenge verification phase after said distance bounding phase. The prover may send to said verifier during said verification phase a parameter (t) that depends on challenges (c′ i ) received by said prover during said distance bounding phase.

As seen from a verifier v, an embodiment of the method of the present invention that can be used by a verifier holding a secret key (x) to verify the identity of a prover and whether this prover is within a predetermined distance of this prover may comprise an initialization phase and a distance bounding phase, said initialization phase comprising the following steps:

the verifier receives a first nonce (N p ) transmitted by a prover;

the verifier picks a first random vector (a), a leak function (L μ ), and a second nonce (N v );

the verifier uses said leak function (L μ ) to compute a modified secret (x′) depending on the leak (L μ (x)) of said secret (x);

the verifier transmits to said prover said leak function (L μ ) and said second nonce (N v );

the verifier send challenges (c i ) to said prover;

the verifier verifies a response (r i ) to said challenge received from said prover;

the verifier verifies the delay (t i ) between a challenge and a response (r i ) to said challenge.

The method may further comprise a challenge verification phase after said distance bounding phase,

wherein said receiver receives from said verifier during said verification phase a parameter (t) that depends on challenges (c′ i ) received by said prover during said distance bounding phase,

wherein said verifier uses said parameter (t) to determine during said verification phase whether the challenges (c′ i ) received by said prover during said distance bounding phase correspond to the challenges (c i ) sent to said prover.

The method may further comprise a step during said initialization phase during which said verifier picks a second random vector (b) with a Hamming weight of n/2 where n is the number of challenges sent during said distance bounding phase, wherein said modified secret (x′) further depends on said second random vector (b);

wherein said verifier transmits said second random vector (b) to said prover.

In one aspect, the invention is also related to an electronic device which could be used as prover and comprising:

a storage for holding a secret key (x)

means for picking a first nonce (N p ) and for communicating this first nonce to a verifier;

means for receiving from said verifier a leak function (L μ ) and a second nonce (N v );

means for retrieving a first random vector (a) and a modified secret (x′) based on the first nonce, on the second nonce, on the leak function, and on the secret key (X); means for receiving from said verifier a sequence of challenges (c i );

means for determining responses (r i ) to said challenges based on said first nonce (a) and on said modified secret (x′ i ).

The device p may further comprise means for computing and transmitting to said verifier during a verification phase a parameter (t) that depends on challenges (c′ i ) received by said prover during said distance bounding phase.

The device p may be a smart card, a NFC device or an electronic access control device.

According to one aspect, the invention is related to an electronic device v which could be used as verifier and comprising:

means for receiving a first nonce from a verifier;

means for picking a first random vector (a), a leak function (L μ ), and a second nonce (N v );

means using said leak function (L μ ) to compute a modified secret (x′) depending on the leak (L μ (x)) of said secret (x);

means for transmitting to said prover said leak function (L μ ) and said second nonce (N v );

means for sending challenges (c i ) to said prover;

means for verifying responses (r i ) to said challenges from said prover;

means for verifying a delay (t i ) between a challenge and a corresponding response (r i ) received from the prover.

The device of may further comprise means using a parameter (t) received from said prover to determine during a verification phase whether the challenges (c′ i ) received by said prover during said distance bounding phase correspond to the challenges (c i ) sent to said prover.

The device may further comprising means for picking a second random vector (b) with a Hamming weight of n/2 where n is the number of challenges sent during said distance bounding phase,

wherein said modified secret (x′) is the addition of the leak of said secret (L μ (x)) and of the second random vector (b);

wherein said verifier transmits said second random vector (b) to said prover.

According to one aspect, the invention is also related to a system comprising a device p that can be used as a prover and a device v that can be used as a verifier.

According to one aspect, the invention is also related to a tangible computer-program product comprising a computer-readable medium comprising codes executable by at least one processing circuit for causing said processing circuit to carry out the above described method.

The invention will be better understood with the aid of the description of an embodiment given by way of example and illustrated by the figures, in which:

FIG. 1 illustrates the DBopt bounding protocol;

FIG. 2 illustrates the DB1 bounding protocol;

FIG. 3 illustrates the DB2 bounding protocol;

FIG. 4 illustrates the DBopt bounding protocol.

FIG. 5 illustrates the SKI protocol of the prior art.

FIG. 6 illustrates the FO protocol of the prior art.

For our security proofs, we will now first introduce a new complete set of security definitions for distance-bounding, capturing the previous notions, but being in line with the established theory behind interactive proofs. In particular, we will revisit the definition of mafia fraud/man-in-the-middle and the definition of terrorist fraud/collusion fraud.

Useful Bounds for Noisy Communications

To assert security in noisy communications, we will make use of the tail of the binomial distribution:

For any ϵ, n, τ, ρ such that

τ n < ρ - ɛ ,

we have Tail(n, τ, ρ)<1−e −2ϵ 2 n . For

τ n > ρ - ɛ ,

we have Tail(n, τ, ρ)<e −2ϵ 2 n .

Revised DB Security Model and Proofs

we now refine the security definitions and other tools from the above described BMV security model. In this section, we also discuss the links with the original notions.

In this example, we concentrate on distance-bounding protocols based on symmetric cryptography (which is the overwhelmingly prevalent approach in DB. The method could also be applied to public-key distance-bounding, using asymmetric cryptography.

Definition 1. A (symmetric) distance-bounding protocol is a tuple ( ,P,V,B), constructed of the following: a key domain ; a two-party probabilistic polynomial-time (PPT) protocol (P(x),V(x)), where P is the proving algorithm, V is the verifying algorithm, and x is taken from ; a distance bound B. At the end of the protocol, the verifier V(x) sends a final message Out V . This output denotes that the verifier accepts (Out V =1) or (Out V =0).

In a DB protocol, apart from the participants prover and verifier, there may exist adversaries. Each participant has instances and each instance has its own location. P denotes the set of instances of the prover, V denotes the set of the instances of the verifier and A denotes the set of the instances of the other participants.

Informally, a distance-bounding protocol is complete if executing P(x) V(x) on locations within a distance bounded by B makes V(x) accept with overwhelming probability. The formalism is straightforward with the settings below.

We can compare the protocols of the invention to any DB protocol that follows what we call the common structure.

Definition 2. (Common structure) A DB protocol with the common structure based on parameters (n, τ, num c , num r ) has some initialization and verification phases which do not depend on communication times. The verification phase can be interactive or not. These phases are separated by n rounds of timed challenge/response exchanges. This is called the distance bounding phase. A response is on time if the elapsed time between sending the challenge and receiving the response is at most 2 B. Provers don't measure time Provers have no clock. They are in a waiting state to receive the challenge. Challenges and responses are in sets of cardinality num c and num r , respectively.

When the protocol follows the specified algorithms but messages during the distance bounding phase can be corrupted during transmission, we say that the protocol is τ-complete if the verifier accepts if and only if at least τ rounds have a correct and on-time response.

One can easily see that nearly all distance-bounding protocols in the literature fit this definition.

In practice, when the timed phase is subject to noise, we assume that there is a probability of p noise that one round of challenge/response is corrupted. The probability that an honest prover, close to the verifier, passes the protocol is thus Tail(n, τ, 1−P noise ). So, with

τ n < 1 - p noise

with a constant gap, the probability to fail is negligible, due to the Chernoff-Hoeffding bound.

Participants, Instances, Setup and Locations.

In a DB protocol, participants can be a prover p, a verifier v, or adversaries. The prover and the verifier receive a key x which is randomly selected from the key space. We adopt a static adversarial model: i.e., at the beginning of the experiment, it is decided whether the prover is malicious or not. Participants have several instances. An instance has a location. It corresponds to the execution of a protocol during one session.

A honest prover runs instances of the algorithm P denoted by P(x). An instance of a malicious prover runs an arbitrary algorithm denoted by P*(x). P denotes the set of instances of the prover.

The verifier is honest without loss of generality (A “malicious verifier” running an algorithm V*(x) can be seen as a malicious prover running V*(x)). He runs instances of the algorithm V denoted by V(x). V denotes the set of instances of the verifier. Other participants are (without loss of generality) malicious and may run whatever algorithm, but with no initialized key. The set of such malicious participants is denoted A. By contrast, a designated, one such instance is denoted . Locations are elements of a metric space.

Why a Single Identity?

We will use a definition using a single identity, without loss of generality. This is because provers or verifiers running the protocol with other identities (and keys independent of x) could be considered as elements of A.

Definition 3. (DB Experiment) An experiment exp for a distance-bounding protocol ( , P, V, B) is a setting (P, V, A) with several instances of participants, at some locations, set up as above, and running an overall PPT sequence.

In the above definition, the notion of experiment implies simultaneously several different entities: participants, physical locations, algorithms to be run by these participants and corruption states. As such, when used inside further definitions, the notion of experiment will implicitly or explicitly, upon the case, quantify over these entities.

We further assume that communicating from a location to another takes time equal to the distance. Indeed, no one can violate the fact that communication is limited by the speed of light. Adversaries can intercept some messages and replace them by others, but must adhere to the fact that computation is local.

Therefore, it could be accepted as a Lemma that a close-by participant cannot get online help from far away to answer correctly and in time to the challenge c.

Definition 5 Distinguished Experiment We denote by exp( ) an experiment in which we fix a verifier instance =V(x) from V, which we call distinguished verifier. Participants which are within a distance of at most B from a distinguished verifier are called close by participants. Others are called far-away participants.

Participants can move during the experiment, but not faster than the transmission of information. For simplicity, we assume that far-away participants remain far away during the experiment.

Definition 6 (α-resistance to distance fraud) We say that a distance-bounding protocol α-resists to distance fraud if for any distinguished experiment exp( ) where there is no participant close to , the probability that accepts is bounded by α.

This definition is simplified and does not capture the notion of distance hijacking; therein, a far-away malicious P*(x) can make accept by taking advantage of several honest provers which do not hold x but are close to . Nonetheless, distance hijacking and other extensions of classical frauds will be captured by the notion of soundness, which we introduce below.

Theorem 7. A DB protocol following the common structure with parameters (n, τ, num c , num r ) cannot α-resist to distance fraud for α lower than

Proof. We construct a DF following the early-reply strategy: a malicious prover guesses with probability

1 num c

the challenge c i before it is emitted, and then he sends the response so that it arrives on time. The rest of the protocol is correctly simulated (with delay) after receiving the challenges. An incorrect guess would look like a round which was the victim of noise. So, the attack succeeds with probability

Tail ⁡ ( n , τ , 1 num c ) .

We can have a similar attack guessing the response r and succeeding with probability

While the above definition protects verifiers against malicious provers, we need an extra notion to protect the honest prover against men-in-the-middle. This is as follows.

Definition 8 (β-secure distance-bounding protocol) We say that a distance-bounding protocol is if for any distinguished experiment exp( ) where the prover is honest, and the prover instances are all far-away from , the probability that accepts is bounded by β.

This definition formalizes security without a learning phase.

Intuitively, this notion protects honest provers from identity theft. It implies that x cannot be extracted by a malicious participant; this is along the same lines as in zero-knowledge interactive protocols. This notion of security also captures resistance to relay attacks, mafia fraud, and man-in-the-middle attacks. The advantage of Def. 8 over the resistance to man-in-the-middle attacks, as it was defined in [7, 9, Def. 4], is that we no longer need to formalize a learning phase, although we can easily show we capture these notions as well. Our definition is therefore simpler.

Theorem 9. A DB protocol following the common structure with parameters (n, τ, num c , num r ) cannot be β-secure for β lower than

Proof. We consider and a far-away instance of the prover P, and a close-by MiM . In the initialization phase and the verification phase, passively relays messages between and P. During the challenge phase, and in the pre-ask strategy, guesses the challenge before it is released and asks for the response to P on time so that he can later on answer to . Clearly, the attack succeeds with probability 1 Same remark about [33] as in Th. 7.

Tail ⁡ ( n , τ , 1 num c ) .

We can have a similar attack with a post-ask strategy where guesses the response at the same time he forwards the challenge to P. This succeeds with probability

Definition 10 ((γ, γ′, m)-soundnes) We say that a distance-bounding protocol is (γ, γ′, m)-sound if for any distinguished experiment exp( ) in which accepts with probability at least γ, there exists a PPT algorithm ϵ called extractor, with the following property. By ϵ running experiment exp( ) several times, in some executions denoted exp i ( ), i=1, . . . , M, for M of expected value bounded by m, we have that

Pr [Out V =1: (View I . . . View M ) V |Succ I . . . Succ M ]≥γ.

where View i denotes the view of all close-by participants (except ) and the transcript seen by in the run exp i ( ′), and Succ i is the event that accepts in the run exp i ( ).

Thus, in this approach, distance fraud does not capture distance hijacking anymore, distance hijacking being now captured by soundness. This makes proofs simpler. To this end, we extend the definition of soundness in such a way that the extraction of the secret is no longer necessary.

In other words, the extractor impersonates the prover to . In more details, this means that having accept in run exp i ( ) implies the following: a piece of x was given to the close-by participants and it is stored in View i , and that m such independent pieces, on average, could allow ϵ to impersonate P(x) to . This notion is pretty strong as it could offer a guaranty against distance hijacking: a prover making such attack would implicitly leak his credentials.

New Highly Efficient, Symmetric Distance-Bounding Protocols

We will now describe as non limitative examples three distance-bounding protocols or methods, called DBopt. It includes DB1, DB2, and DB3. Those embodiments of the invention are build up on the above described SKI and FO but outperform both the SKI and the FO protocols.

For instance, to offer a false acceptance rate of under 1 and false rejection rate of under 1%, at a noise level of 5% during the rapid bit-exchange, DB1 (with parameter q=3) requires 14/14/54 rounds for resistance to distance fraud/mafia fraud/terrorist fraud, respectively. For the same performance, SKI and FO require 84/48/181 and 84/84/? rounds, respectively. So, DB1 represents a substantial improvement in terms of efficiency, whilst maintaining provable security.

When considering optimality amongst protocols requiring at least τ out of n correct rounds, no clock for the prover p, and a challenge/response set of size q, we show security as follows:

Indeed, we will see herein that DB1 is in fact optimal in terms of distance-fraud resistance and security with non-binary challenges. The DB2 and DB3 variants are motivated by the use of binary challenges, which is customary in distance-bounding designs. Whilst DB2 is suboptimal, it still performs well, almost always, i.e., better than SKI and FO. DB3 is optimal but not TF-resistant.

DBopt

The DBopt protocol is illustrated on FIG. 1 .

We use a security parameter s (the length of the secret x, i.e., xϵK=Z 2 s ) and the following parameters based on s: the number of rounds n, the length l tag of tag, a threshold τ, the nonce length l nonce , and a constant q which is a prime power, e.g., q=2, q=3, or q=4. DBopt follows the common structure with parameters n, τ, and num c =num r =q.

We assume L μ (x)=(μ(x), . . . , μ(x)) for some function x μ(x), but μ is not necessarily linear. Concretely, μ is a vector in Z 2 s and map a fixed injection from Z 2 to GF(q). Hence, μ(x)=map(μ·x) maps a bitstring x to a GF(q)-representation of the bit obtained by the scalar product μ·x. We let denote the set of all such possible L μ mappings (map being fixed). The function f x maps to different codomains, depending on its inputs: given two nonces N P and N V , L μ ϵ , and b, cϵGF(q) n , f x (N P , N V , L μ , b)ϵGF(q) n and f x (N P , N V , L μ , b, c)ϵGF(q) l tag .

During the initialization, the prover p and the verifier v exchange some nonces N P , N V , some L μ ϵ , and a vector b. The vector b could be fixed in the protocol, but is subject to some constraints as detailed below. V and P compute a=f x (N P , N V , L μ , b) and x′=L μ (x). In the distance bounding phase, the response function is a linear function r i =φ c i (a i , x′ i , b i ) defined by the challenge c i . The verification checks that the participants have seen the same challenges (based on the tag computed by tag=f x (N P , N V , L μ , b, c)), counts the number of rounds with a correct and timely response, and accepts if there are at least τ of them.

Clearly, the DBopt family is quite open to specific choices for q, map, b, and φ c . We propose the instances DB1, DB2, and DB3. There are some specificities in each protocol which are summarized in the following table:

Other instances could be considered.

Specifically, DB3 is the simplest protocol and is optimal, but it offers no soundness. DB2 works with binary challenges and responses, but it is not optimal. DB1 is optimal but needs q≥3 since it requires that map is injective from Z 2 to GF(q)*. These protocols are depicted on FIG. 2-4 .

DB1 uses a security parameter s (the secret length) and the following parameters based on s: the number of rounds n, the bitlength n0 of the tag t, a threshold t, the nonce length k, and a constant q>2 which is a prime power, e.g. q=3 or q=4.

A set of parameters L μ , N v , a is picked by the verifier v during an initialization or distance bounding phase. Similarly, a parameter N p is picked by the prover p during the initialization phase. Both share a secret x. During the distance bounding phase, a set of values ci (challenges) is picked by the verifier. A timer is started and used by the verifier for measuring the time needed to receive a response r i to a challenge c i . A response is refused if it is not the expected one or if it received after a predetermined delay, corresponding to the predetermined distance bound.

As in SKI, we assume Lμ(x)=(μ(x); — — — ; μ(x)) for some function μ, but we now assume that μ maps a secret x to an element of GF(q)_. (We need at least two elements in this set, this is why we need q>2.)

Like in SKI, the leak vector x′ is fundamental for soundness: the vector x′ encodes μ·x, which leaks if the prover reveals his response function. The protocol DB1 adds a verification step, which allows to use better response functions: thanks to the above extra verification, the response function needs no longer resist men-in-the-middle playing with different challenges on the sides of P and V.

In one embodiment of the DB1, DB2 or DB3 protocol, the sending time of the challenges c i may be randomized, in order to prevent an attack by trying to guess replies and send them in advance. For example, each challenge ci may be sent at a random moment within a given interval of, for example, one microsecond.

The DB1 method thus includes an initialization phase comprising the following steps:

the prover p picks a first nonce (N p ) and communicates this first nonce to the verifier;

the verifier v picks a first random vector (a), a leak function (L μ ), and a second nonce (N v );

the verifier transmits to said prover said leak function (L μ ), and said second nonce (N v );

the verifier uses said leak function (L μ ) to compute a modified secret (x′) depending on the leak (L μ (x)) of said secret (x);

the prover retrieves said first random vector (a) and said modified secret (x′).

During a distance bounding phase, the first random vector (a) and the modified secret (x′) are used by the prover for computing a response (r i ) to each of the i challenges (c i ) sent by said verifier to said prover.

During a verification phase, the verifier verifies whether the reply r i to each of the i challenges c i correspond to this challenge, taking into account the first random vector a and the modified vector. The verifier also verifies if the delay timer i for receiving each reply is correct, i.e. under a predefined threshold. In a preferred embodiment, a value t is computed by the prover p as a function fx of N P , N V , L μ and of the received vector c′, and sent to the verifier; this value is compared with a value t computed on the verifier side. The prover is identified if t is correct and if all or at least a sufficient number of r i and t i are correct.

One particularity is that DB1 mandates x′ i ≠0 so cannot accommodate q=2. If we want q=2, we need for DF-resistance to make sure that r i really depends on c i , by introducing the vector b in which exactly half of the coordinates are 0. DB2 can be optimized into DB3 by using r i =a i +c i (so x′ is unused and b i =1 for all i) by sacrificing soundness.

DB1 is optimal in terms of distance-fraud resistance and security with non-binary challenges. A variant to DB1, called DB2, is illustrated on FIG. 3 . This variant is motivated in following a trend in distance-bounding: that of using binary challenges. Whilst DB2 is not as efficient as DB1, it is performs well, almost always, better than SKI and FO.

DB2 still uses a security parameter s (the secret length) and the following parameters based on s: the number of rounds n, the bitlength n0 of the tag t, a threshold t, and the nonce length k. The function μ now maps {0;1} s to {0;1}. It is required that the random vector b in the DB2 protocol has a Hamming weight of n/2 to protect against distance fraud. The other setps are described and illustrated on FIG. 3 .

In the DB1 to DB3 methods, the prover and the verifier are typically electronic devices or equipments. For example, the prover and the verifier could be any electronic equipment with a wireless interface for establishing a wireless communication with a wireless equipment in the vicinity.

The method of the present invention may be used to secure communications between various devices and equipments, including short distance communications between a prover p and a verifier v close to each other. For example, the method is suitable for securing communications over a distance of less than 10 meters, without limitation. The prover and verifier may communicate with each other via one or more wireless communication links that are based on or otherwise support any suitable wireless communication technology, including for example radio communication or optical communication.

For example, in some aspects the prover p and/or the verifier v may be associated within a network. In some aspects the network may comprise a body area network or a personal area network (e.g., an ultra-wideband network). In some aspects the network may comprise a local area network or a wide area network. A wireless device may support or otherwise use one or more of a variety of wireless communication technologies, protocols, or standards such as, for example, any RFID protocol, Bluetooth, NFC, Zigbee, WiMAX, and Wi-Fi. A wireless device may thus include appropriate components (e.g., air interfaces) to establish and communicate via one or more wireless communication links using the above or other wireless communication technologies.

Therefore, the communication between the prover and the verifier could be a wireless communication between two wireless equipments or devices.

DF-Resistance of DB1, DB2, and DB3

Theorem 11 (DF-resistance) The DBopt protocols α-resists to distance fraud for

(DB1 and DB3)

Due to Th. 7 , DB1 and DB3 are optimal for DF-resistance. DB2 is clearly not optimal (as DB3 is better with the same q=2). However, the bound is tight for DB2 as the DF guessing the response matches the α bound: the malicious prover always wins the rounds for which x′=b i (that is: exactly half of the rounds due to the Hamming weight of b) by sending the response in advance and passes with probability

Proof. We consider a distinguished experiment exp( ) with no close-by participant. Due to the distance, the answer r i to comes from far away. Thanks to Lemma 4, r i is independent from c i . Since c i is randomly selected when it is sent, r i is statistically independent from c i . For DB1, since x′ i ≠0 by construction, r i equals a i +c i x′ i with probability

1 q .

The same goes for DB3. For DB2, thanks to the selection of b, this holds for exactly half of the rounds: those such that x′ i +b i ≠0. So, the probability to succeed in the experiment is bounded as stated.

Security of DB1, DB2, and DB3

We cannot rely on the PRF assumption alone for DB1 or DB2, since the secret is used as a key of f x and also outside f x in x′. The circular-PRF assumption guarantees the PRF-ness of f, even when we encrypt a function L μ (x) of the key. We new recall and extend the notion, to accommodate DB1 and DB2.

Definition 12 (Circular PRF) We consider some parameters s, n 1 , n 2 , and q. Given ϵ{0,1} s , a function L from {0,1} s to GF(q) n 1 , and a function F from {0,1}* to GF(q) n 2 , we define an oracle by (y,L,A,B)=A·L( )+B·F(y), using the dot product over GF(q). We assume that L is taken from a set of functions with polynomially bounded representation. Let (f x ) xϵ{0,1} s be a family of functions from {0,1}* to {0,1} n 2 . We say that the family f is a (ϵ, T)-circular-PRF if for any distinguisher limited to a complexity T, the advantage for distinguishing f x , xϵ u {0,1} s , from , ϵ υ {0,1} s , where F is uniformly distributed, is bounded by ϵ. We require two conditions on the list of queries:

for any pair of queries (y,L,A,B) and (y′,L′,A′,B′), if y=y′, then L=L′; for any yϵ{0,1}), if (y, L, A i , B i ), i=1, . . . , l is the list of queries using this value y, then

Theorem 13 (Security) The DBopt protocols are β-secure for

(DB1 and DB2)

There, r is the number of honest instances (of P or V) and T is a complexity bound on the experiment. β is negligible for

τ n > 1 q + cte ,

r and T polynomially bounded, and ϵ negligible.

Based on that

r 2 2 ⁢ 2 - ℓ nonce + ( r + 1 ) ⁢ ɛ + r ⁢ ⁢ 2 - ℓ tag

(or the similar term for DB3) can be made negligible against β, DB1, DB2, and DB3 are optimal for security due to Theorem 9.

Proof. We consider a distinguished experiment exp( ) with no close-by P(x), no P*(x), and where accepts with probability p. We consider a game Γ 0 in which we simulate the execution of exp( ) and succeed if and only if Out V by is an acceptance message. Γ 0 succeeds with probability p.

First of all, we reduce to the same game Γ 1 whose success additionally requires that for every (N P , N V , L μ ) triplet, there is no more than one instance P(x) and one instance V(x) using this triplet. Since P(x) is honest and selecting the l nonce -bit nonce N P at random and the same for V(x) selecting N V , by looking at the up to r 2 /2 pairs of P(x)'s or of V(x)'s and the probability that one selection of a nonce repeats, this new game succeeds with probability at least

Then, for DB1 and DB2, we outsource the computation of every a i +cx′ i to the oracle

f x ( y, L μ , A, B )=( A·L μ ( x ))+( B·f x ( y ))

as in Def. 12, with y=(N P , N V , L μ , b), A·L μ (x)=c(L μ (x)) i , and B·f x (y)=(f x (y)) i . I.e., A i =ce i and B i =e i , where e i is the vector having a 1 on its ith component and 0 elsewhere. This can be used with c=c′ i by P(x) (for computing r′ i ) or with c=c i by V(x) (for verifying r i ). Similarly, the computation (by P(x) or V(x)) of tag=f x (y) can be made by several calls of form f x (y, L μ , 0, B). (We note that the y in this case has incompatible form with the y in the r i computation.) So, every computation requiring x is outsourced. Note that queries to the same y must use the same L μ since this is part of y. So, the first condition in Def. 12 to apply the circular-PRF assumption is satisfied. We consider the event E that there exists in the game some sequence (y, L μ , A j , B j ) of queries to f x sharing the same (y, L μ ) and some λ j 's such that Σ j λ j B j =0 and Σ j λ j A j =0. We need to restrict to the event E to apply Definition 12. We consider the event E′ that one instance in V receives a valid tag which was not computed by the prover P (i.e., it was forged).

Let c″ i be the value received by V(x) in the verification phase. We assume that V checks that tag is correct, timer i is correct, and c i =c″ i , then queries f x (y, L μ , c i , e i , e i ) only if these are correct. If E happens for some (y, L μ ), due to the property of Γ 1 , each i has at most two queries. Since B j =e i j , Σ j λ j B j =0 yields pairs of values j and j′ such that i j =i j′ =i, A j =c i e i , A j′ =c′ i e i , B j =B j′ =e i , and λ j +λ j′ =0. The event E implies that there exists one such pair such that λ j A j +λ j′ A j′ ≠0. So, c i ≠c′ i . But since V only queries if c″ i and tag are correct, we have c i =c″ i ≠c′ i and tag correct. So, must have accepted some tag which was not computed by P(x). So, E implies E′. We now show that Pr[E′] is negligible.

We define Γ 2 , the variant of Γ 1 , which in turn requires that E′ does not occur as an extra condition for success. We let E′ j be the event that tag j , the jth value tag received by any V(x) in V is forged. Let Γ 1,j be the hybrid of Γ 1 stopping right after tag j is received and succeeding if E′ j occurs but not E′ 1 , . . . , E′ j−1 .

Clearly, since E′ 1 ∪ . . . ∪E′ j-1 does not occur and we stop right after reception of tag j , E cannot occur. (Remember that for E to occur for the first time upon a query to f x , there must be a prior tag which was forged.) So, the conditions to apply the circular-PRF security reduction in Def. 12 is satisfied in Γ 1,j . We apply the circular-PRF assumption and replace f x , by , loosing some probability ϵ. We obtain a game Γ 2,j . Clearly, Γ 2,j succeeds with probability bounded by 2 −l tag because F is random. So, Pr Γ 1,j [success]≤ϵ+2 −l tag in Γ i,j .

So, Pr[E′] is bounded by the sum of all Pr Γ 1,j [success], i.e. Pr Γ 1 [E′]≤rϵ+r2 −l tag since the number of hybrids is bounded by r. Hence,

Now, in the whole game Γ 2 where E′ does not occur, we replace f x by and obtain the simplified game Γ 3 . We have

It is now possible to analyze the protocol Γ 3 . Thanks to Lemma 4, the response is computed based on information from P(x) (w in Lemma 4) which is independent (in the sense of Lemma 4) from the challenge. Either P(x) was queried with a challenge before, but this could only match the correct one with probability

1 q

and the adversary would fail with tag otherwise. Or, P(x) leaked nothing about the response to this challenge, and the answer by the adversary can only be correct with probability

1 q .

In any case, his answer is correct with probability

1 q .

So, Γ 3 succeeds with probability up to

To sum up, we have

p ≤ Tail ⁡ ( n , τ , 1 q ) + r 2 2 ⁢ 2 - ℓ nonce + ( r + 1 ) ⁢ ɛ + r ⁢ ⁢ 2 - ℓ tag

for DB1 and DB2.

For DB3, we loose

r 2 2 ⁢ 2 - ℓ nonce

from Γ 0 to Γ 1 . In Γ 1 , we apply the full PRF reduction and loose ϵ to obtain Γ 2 with a random function. We loose 2 −l tag more to assume that tag received by V was not forged in some Γ 3 . Then, it is easy to see that either the prover was queried before c i was known, but this will only succeed if c i was correctly guessed, or it was queries after, but this will only succeed if the answer r i was correctly guessed. So, Γ 3 succeeds with a probability bounded by

Tail ⁡ ( n , τ , 1 q ) .

(Note that DB3 is insecure without the authenticating tag: the man-in-the-middle can just run the DB phase with the prover, deduce a, then answer all challenges from the verifier.)

Soundness of DB1 and DB2

Theorem 14 (soundness of DB1) The DB1 scheme is (γ, γ′, s+2)-sound for any

γ ≥ q q - 1 ⁢ p B

and γ′ such that γ′=(1−γ −1 P B ) s , where p B =max a+b≤n p B (a,b) and

More precisely, any collusin fraud with a success probability

γ ≥ p B 1 - 1 q - ɛ

leaks one random (μ,μ·x) pair with probability at least

1 q + ɛ .

Assuming p B =p B (0,0), this compares γ to

For instance, for γ=sp B and

τ n > q q - 1 + cte ,

γ is negligible and γ′ is greater than a constant.

If we applied the same proof as for SKI from [30, Th. 14], we would not get such a good result. We would rather obtain

Tail ⁡ ( n 2 , τ - n 2 , q - 1 q ) .

So, our proof of Th-14 is substantially improved.

Proof. We consider a distinguished experiment exp( ) where accepts with probability p≥γ.

The verifier has computed some a and x′. We apply Lemma 4. We let Resp i (c) be the value of the response r i arriving to when c i is replaced to c in the simulation. We show below that we can always compute Resp i (c)−Resp i (c′) for any (c,c′) pair from a straightline simulation (i.e., without rewinding). Let View i be the view of close-by participants until the time before c i arrives, and w i be the extra information (independent from c i , in the sense of Lemma 4) arriving from far-away. Due to Lemma 4, we have Resp i (c)=Algo(View i ,c,w i ). So, we can easily compute Resp i (c)−Resp i (c′) without rewinding. The answer by a far-away participant is independent from c i , so Resp i (c)−Resp i (c′)=0: we can compute Resp i (c)−Resp i (c′) as well.

We say that c is correct in the ith round if Resp i (c)=a i +cx′ i . We let C i be the set of correct c's for the ith round. We let S be the set of all i's such that c i ϵC i . Finally, we let R (resp. R′) be the set of all i's for which #C i =q (resp. #C i ≤1). I.e., all c's are correct in the ith round for iϵR and at most one is correct for iϵR′.

By definition, the probability that #S≥τ is p≥γ. We see that

Resp i ⁡ ( c ) - Resp i ⁡ ( c ′ ) c - c ′ = x i ′

if iϵR, for any c≠c′. If the left-hand side leads to the same value ξ i for each c≠c′, we say that the round i votes for x′ i =ξ i . If the (c,c′) pairs do not lead to the same value in GF(q), we say that the round i does not vote. So, we can always compute the vote ξ i from the views of close-by participants. The majority of the available map −1 (ξ i ) shall decode μ·x.

For DB1, we can prove that if the round i votes for some ξ i such that ξ i ≠x′ i , then we must have iϵR′. Indeed, if round i votes for some ξ i and #C i ≥2, it means that there exist two different challenges c and c′ such that the responses Resp i (c) and Resp i (c′) are correct. So, Resp i (c)=a i +cx′ i and Resp i (c′)=a i +c′x′ i . The vote ξ i is

Resp i ⁡ ( c ) - Resp i ⁡ ( c ′ ) c - c ′

which is thus equal to x′ i . So, an incorrect vote cannot have two correct challenges: it must be for iϵR′. The majority of the votes does not give x′ i only when #R≤#R′. So, we shall bound Pr[#R≤#R′].

Let I, I′⊂(1, . . . , n) such that #I≤#I′ and I∩I′ is empty. Let p B (a,b) be the probability that at least τ rounds succeed, when we know that a rounds succeed with probability 1, b rounds succeed with probability

1 q ,

and the other succeed with probability

1 - 1 q .

We have Pr[#S≥τ, R=I, R′=I′]=Pr[#S≥τ|R=I, R′=I′]Pr[R=I, R′=I′] and Pr[#S≥τ|R=I, R′=I′]≤p B (#I, #I′)≤p B since we have #I correct rounds for sure and it remains to pick u correct challenges (out of at most q−1) among the i∉I∪I′ rounds, and v correct challenges (out of at most 1) among the iϵI′ rounds, for all u and v such that u+v≥τ−#I. By summing over all choices for I and I′, we obtain that Pr[#S≥τ, #R≤#R′]≤p B So, Pr[#R>#R′|#S≥τ]≥1−γ −1 p B . So, when the experiment succeeds, the extracting algorithm gets a random pair (μ,μ·x) with probability at least 1−γ −1 p B . This is better than just guessing μ·x when

We can do M many such accepting experiments, collect some (μ, μ·x) until we have s vector μspanning GF(q) s , and reconstruct x with probability at least γ′=(1−γ −1 p B ) s . The probability that m samples in GF(q) s do not generate this space is p m ≤q s-m (the number of hyperplane, q s −1 times the probability that the m samples are all in this hyperplane, which is q −1 to the power m). So, the expected M until we generate the space is bounded by s+Σ m≥s q s-m ≤s+2. Hence, after at most s+2 iterations on average, we can recover x by solving a linear system. This defines the extractor.

We can also push the extraction further when

1 - γ - 1 ⁢ p B > 1 q

by solving an instance of the Learning Parity with Noise problem (LPN), which would still be feasible by the practical parameters s.

Extraction can also work with a complexity overhead bounded by (s j ) and a probability of at least γ′=Tail(s, s−j, 1−γ −1 p B ), by finding at most J errors by exhaustive search or LPN solving algorithms.

The maximum p B =p B (a, b) is always reached for a=b.

Below, we prove that the result is tight for DB1 using q=3. Whether this it tight for other q is an open question. Whether it is optimal for protocols following the common structure is also open.

DB1's Tightness of the Soundness Proof.

To show that the result is tight for DB1 with q=3, we mount a (non-leaking) terrorist fraud succeeding with probability

γ = Tail ⁡ ( n , τ , q - 1 q ) :

let the malicious prover give to the adversary the tables for c i r i +e i (c i ) for every round i. For each such i, randomly pick one entry for which e i (c i ) is a random nonzero value and let it be 0 for other, two entries. With such tables as a response function, the adversary passes the DB phase with probability γ. (Other phases are done by relaying messages.) Since the verifier accepts with negligible probability γ, the adversary learns as much as if Out V was always set to 0.

For q=3 and each i, based on random a i ϵGF(q), x′ i ϵGF(q)*, and c e i (c) as distributed above, we can easily see that the distribution of the transmitted table is independent from x′ i : for x′ i =1, the table of c a i +cx′ i defined by a random a i is randomly picked from

When adding the random table e i (c), it becomes a uniformly distributed random table among those with an output set of cardinality 2. For x′ i =2, the table of a i +cx′ i is randomly picked from

( 0 ⁢ ⁢ … ⁢ ⁢ 0 1 ⁢ ⁢ … ⁢ ⁢ 2 2 ⁢ ⁢ … ⁢ ⁢ 1 ) · ( 0 ⁢ ⁢ … ⁢ ⁢ 2 1 ⁢ ⁢ … ⁢ ⁢ 1 2 ⁢ ⁢ … ⁢ ⁢ 0 ) · ( 0 ⁢ ⁢ … ⁢ ⁢ 1 1 ⁢ ⁢ … ⁢ ⁢ 0 2 ⁢ ⁢ … ⁢ ⁢ 2 ) .

but adding e i (c) leads to the same distribution as for x′ i =1. So, the above attack does not leak and is a valid terrorist fraud. Th. 14 essentially says that there is no valid terrorist fraud with a larger γ. So, the result is tight for DB1 with q=3.

The same proof technique leads to the following result for DB2.

Theorem 15 (thDB2sound) For

τ n > 3 4 ,

the DB2 scheme is (γ, γ′, s+2)-sound for any

Again, it is open whether this is optimal for a protocol with binary challenges. The bound is pretty tight for DB2: a malicious adversary could leak the c i r i tables for a random selection of half of the rounds, and leak the table with one bit flipped for the others. This will not leak x′ i and will pass with probability

γ = Tail ⁡ ( n 2 , τ - n 2 , 1 2 ) .

Performance Comparisons

Tests with a noise level of p noise =5% have shown that the DB1, DB2 and DB3 protocols are more resistant than SKI and FO. Moreover, a lower number of rounds is required to attain such security.

We provided the provably secure symmetric protocols DB1, DB2, and DB3 which require fewer rounds than the only two existing, provably secure protocols, SKI and FO. Prior to this, we have revised the formal model for distance-bounding protocols in a way which is closer to (the state of the art of) interactive proofs. We also studied optimality of all provably secure DB protocols, existing and advanced herein.

Implementations

The prover and verifier of the present invention may be incorporated into (e.g., implemented within or performed by) a variety of apparatuses (e.g., devices). For example, one or more aspects taught herein may be incorporated into a phone (e.g., a cellular phone), a computer, a tablet, a personal data assistant (“PDA”), a smart card, a RFID device or transponder, an electronic access key, a dongle, an entertainment device (e.g., a music or video device), a headset (e.g., headphones, an earpiece, etc.), a medical sensing device (e.g., a biometric sensor, a heart rate monitor, a pedometer, an EKG device, etc.), a user I/O device (e.g., a watch, a remote control, a light switch, a keyboard, a mouse, etc.), an environment sensing device (e.g., a tire pressure monitor), a computer, a point-of-sale device, an entertainment device, a hearing aid, a set-top box, or any other suitable device.

Those of skill would further appreciate that any of the various protocols, methods or method steps described or claimed in the present application may be implemented as electronic hardware (e.g., a digital implementation, an analog implementation, or a combination of the two, which may be designed using source coding or some other technique), various forms of program or design code incorporating instructions (which may be referred to herein, for convenience, as “software” or a “software module”), or combinations of both. To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present disclosure.

The various illustrative devices and further means described in connection with the aspects disclosed herein may be implemented within or performed by an integrated circuit (“IC”), an access terminal, or an access point. The IC may comprise a general purpose processor, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, electrical components, optical components, mechanical components, or any combination thereof designed to perform the functions described herein, and may execute codes or instructions that reside within the IC, outside of the IC, or both. A general purpose processor may be a microprocessor, but in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, e.g., a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration.

Various electronic systems may be used by the verifier v as timer for verifying the delays t i between each challenge c i and the corresponding reply r i . In one example, a time of flight measuring system based for example on avalanche diodes may be used.

It is understood that any specific order or hierarchy of steps in any disclosed process is an example of a sample approach. Based upon design preferences, it is understood that the specific order or hierarchy of steps in the processes may be rearranged while remaining within the scope of the present disclosure. The accompanying method claims present elements of the various steps in a sample order, and are not meant to be limited to the specific order or hierarchy presented.

The steps of a method or algorithm described in connection with the aspects disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module (e.g., including executable instructions and related data) and other data may reside in a data memory such as RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, a hard disk, a removable disk, a CD-ROM, or any other form of computer-readable storage medium known in the art. A sample storage medium may be coupled to a machine such as, for example, a computer/processor (which may be referred to herein, for convenience, as a “processor”) such the processor can read information (e.g., code) from and write information to the storage medium. A sample storage medium may be integral to the processor. The processor and the storage medium may reside in an ASIC. The ASIC may reside in user equipment. In the alternative, the processor and the storage medium may reside as discrete components in user equipment. Moreover, in some aspects any suitable computer-program product may comprise a computer-readable medium comprising codes (e.g., executable by at least one processor) relating to one or more of the aspects of the disclosure.

The previous description of the disclosed aspects is provided to enable any person skilled in the art to make or use the present disclosure. Various modifications to these aspects will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other aspects without departing from the scope of the disclosure. Thus, the present disclosure is not intended to be limited to the aspects shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.