Journal of Communications and Information Networks

Location information about wireless devices is valuable due to its crucial role in data collection, reliable communications, resource management, emergency services/maintenance, and other important functions of wireless systems^[1]. At the same time, security issues in location based systems have received increasing attention^[2]. Thus, the method of utilizing the location of a device to achieve security management in location based systems is becoming a focus nowadays.

It is well known that in classic cryptography a party holds some credentials so that its identity, access authority, etc. can be determined. Usually, the credentials consist of the following parts: a registered identity (e. g. , an email address), secret knowledge (e. g. , a pre-shared key or a password), authenticated information (e. g. , a certification issued by CA), a trusted computing base (e. g. , a TPM^[3]), biometric data (e. g. , a fingerprint) and so on. However, the location of a device or a user, which is an important piece of information, cannot be used as a credential and applied to realize cryptographic tasks in classic cryptography.

At CRYPTO 2009, Chandran, et al. ^[4]first introduced the notion of position based cryptography, in which the credential of a party comes from its geographic location. At the same time, the design of secure cryptographic protocols using location as a credential such as secure positioning and position based key exchange, was also investigated. Unfortunately, as a vital primitive in position based cryptography, secure positioning has been proven to have no secure position protocol under collusion attacks without set-up assumptions. As a result, none of the position based cryptographic tasks, including position based key exchange, can be carried out without setup assumptions. In the BRM (Bounded Retrieval Model), Chandran et al. propose secure positioning protocols resistant to collusion attacks. They also propose a secure position based key exchange protocol in the BRM^[4]. Subsequently, some position based cryptographic protocols have been proposed in the quantum model^[5,6,7]. Recently, the composition security of position based cryptography has also been investigated in universally composable security models^[8,9].

PbKE (Position based Key Exchange), which can establish a secret key between a prover located at a valid position and one verifier (or all of the verifiers), is one of the fundamental tasks in position based cryptography. The position based key exchange protocol proposed by Chandran^[4]can only realize key establishment between prover and verifier, which is called the p2v (Prover-to-Verifier) mode.

Besides the p2v mode, position based key exchange between two provers, called p2p (Prover-to Prover) mode, should also be considered one of the most important tasks in position based cryptography ^[10].

This paper investigates the security definitions and the implementations of position based key exchange in two modes. Our contributions are shown below. In particular.

1) To begin with, we distinguish between the two modes of position based key exchange in position based cryptography: the p2v mode and the p2p mode.

2) Then we present the security definitions of position based key exchange. The p2v mode guarantees that one prover (located at one valid position) can share a secret key with the verifiers against the colluding adversaries. In contrast, the p2p mode guarantees that one prover (located at one valid position) can share a secret key with another prover (located at another valid position), while colluding adversaries cannot access any information about the shared key.

3) Under the BRM, we discuss the implementation of position based key exchange, which includes p2v key exchange protocols and p2p key exchange protocols.

4) Finally, we compare existing position based key exchange protocols from both security and performance perspectives.

The organization of the rest paper is as follows: Section 2 introduces the p2v mode and the p2p model and gives their security definitions. In Section 3, we present the position based p2v key exchange protocols in one dimension, while Section 4 presents the position based p2p key exchange protocols. We also present extensions of the PbKE protocols in Section 5. Section 6 compares the above protocols in three dimensions. Section 7 concludes our results.

In this section, we introduce the adversary model, the assumptions used in this paper and the two modes of key exchange in position based cryptography.

The colluding adversaries in PbKE protocols have the following capabilities:

1) Adversaries can access all messages (except high min-entropy information in the BRM) when they pass through the wireless communication channel.

2) Adversaries can send any forged message in the wireless communication channel.

3) An adversary can be located at any position except the target position when the prover located in that target position runs a PbKE protocol.

Note that corruption of a prover or a verifier is not considered in position based cryptography. One hand, a prover has no pre-sharing of cryptographic keys, and the unique credential of the prover is its position. the other hand, a secure position based key exchange protocol could not be realized without trusted verifiers.

In the p2v mode, a PbKE protocol in d-dimensions consists of a unique prover, some verifiers (at least d+1), and a group of colluding adversaries. At the end of a secure p2v key exchange protocol, the prover located at a valid position can securely share a key with verifiers against the colluding adversaries. For example, the p2v mode of key exchange in 2-dimensions is shown in Fig.1.

Formally, a position based p2v key exchange protocol π in d-dimensional space consists of two algorithms, i. e. π= (Init, Key): the position initialization algorithm Init(P) and the key exchange algorithm Key(V, P, p). There is a set of verifiers V={V ₀, V₁, …, V_D} at positions pos₀, pos₁, …, pos_D respectively (D ≤ d). At the same time, there are colluding probabilistic polynomial time adversaries A={A₁, A₂, …, A_K}at positions apos ₁, apos ₂, …, apos_K respectively. The Init(P) algorithm initializes the location of prover P, i. e. if Init(P)=p, this means that the location of P is position p where p is in the tetrahedron enclosed by pos₀, pos ₁, …, pos_D. The Key(V, P, p) algorithm against colluding PPT (Probabilistic Polynomial Time) adversaries A={A₁, A₂, …, A_K}establishes a shared secret key sk=Key(V, P, p)between uncorruptedPandVifPis located atp.

Definition 1 (Position based p2v key exchange) A position based p2v key exchange protocol π is called a secure position based p2v key exchange protocol in security parameter k if for all sets of A ={A₁, A ₂, …, A_K}, given(V, P, p=Init(P)), it is able to distinguish between sk=Key(V, P, p)and a uniform string U(where|U|=|sk|)with a negligible function ε(k). Formally,

As opposed to the p2v mode, the p2p mode deals with position based key exchange between two provers (with the help of verifiers). Fig.2 shows position based p2p key exchange in two dimensions.

Similar to the p2v mode, a position based p2p key exchange protocol π in d-dimensional space consists of two algorithms, i. e. π= (Init, Key): the position initialization algorithm Init(P) and the key exchange algorithm Key (V, P₁, p₁, P₂, p₂). A set of verifiers is denoted by V={V₀, V₁, …, V_D}at positions pos₀, pos₁, …, pos_D respectively(D≤d). The colluding probabilistic polynomial time adversaries are denoted by A={A₁, A₂, …, A_K}at positions apos ₁, apos₂, …, apos_K respectively. The Init(P)algorithm can set the location of a prover P as position p where p is in the tetrahedron enclosed by pos₀, pos₁, …, pos_D. The Key(V, P₁, p₁, P₂, p₂) algorithm against colluding PPT adversaries A={A₂, A₂, …, A_K}could establish a shared secret key sk=Key(V, P₁, p₁, P₂, p₂)between uncorrupted P ₁ and P₂ ifP₁ is located atp₁ andP₂ is located atp₂.

Definition 2 (position based p2p key exchange) A position based prover-to-prover key exchange protocol π is called a secure position based p2p key exchange protocol in security parameter k if for all sets of A={A ₁, A₂, …, A_K}, given (V, P ₁, P₂, p₁ = Init(P₁), p₂= Init(P₂)), it is able to distinguish between sk=Key(V, P ₁, p ₁, P₂, p ₂) and a uniform string U(where|U|=|sk|)with a negligible function ε(k). Formally,

In this subsection, we present the assumptions used in this paper.

Assumption 1 (The BRM) As in the underlying model in Ref. 4], the protocols in this paper are based on the BRM. The bounded retrieval model assumes that all adversaries can only retrieve part of high minentropy information. More specifically, we have:

1) Verifiers can generate n-bit string X, where X has high min-entropy (δ+β)n.

2) All adversaries can retrieve any part of X when X passes. However, the total retrieved information about X is no more than βn.

Assumption 2 (Private channel) We assume that there is a private channel among all of the verifiers in position based cryptography, i. e. that they can share any message securely.

Assumption 3 (Authenticated broadcast) In this paper, we assume that anyone of the verifiers has an authenticated broadcast channel in this paper. In other words, no adversary can modify or forge a message sent from a verifier in an authenticated channel.

It is also worth noting that there are some very efficient broadcast authentication protocols that can be used for position based cryptography, such as μTESLA^[11], one-time signature^[12]and so on.

Assumption 4 (DDH assumption) Consider a cyclic group G with prime order q and generator g. If a and b are chosen randomly from Z_q, then any PPT adversary A can distinguish between{g^a, g^b, g^ab}and{g^a, g^b, R}with only negligible probability, where R is a uniform string and|R|=|g^ab|.

In addition, we use BSM PRG (BSM pseudorandom generators)^[4]and PRF (pseudorandom function family)^[13]to construct the PbKE protocols. Due to space limitations, we omit detailed description of BRM, BSM PRG, PRF and other cryptographic operations.

In this section, we first present a position based p2v key exchange protocol in one dimension. Then, we present a generic version of the p2v key exchange protocol p2pKE^d in d-dimensions(d∈{1, 2, 3}).

The position based p2v key exchange protocol in one dimension, denoted by p2vKE ¹, is shown in Fig.3. For one dimension, we employ two verifiers, denoted by V₀ and V₁, which send messages at the speed of radio waves.

We assume that the position p being claimed by prover P is located between V₀and V₁.

Protocol p2vKE¹ is secure against an arbitrary number of adversaries colluding to establish a secret key between P and V={V₁, V₂} as long as the total information that these adversaries can retrieve during the protocol is bounded.

A detailed description of protocol p2vKE¹ in the BRM is as follows:

BSM PRG F: {0, 1}ⁿ×{0, 1}^m→{0, 1}^m.

Initialization: Prover P runs the algorithm Init(P) as follows:

(1)Set p=Init(P), i. e. P is located at p.

(2)Set s=(sid, p), where sid is session identity.

Let t(V_i, p)be the time taken for a message from verifier V_i to reach position p.

Let T be the time at which the message sent by V₀ arrives at p.

Key Exchange: Prover P runs the algorithm Key(V, P, p)as follows:

1) V₀generates X₀with min-entropy (δ+β)n and m-bit random string r, and V₁ generates X₁ with minentropy (δ+β)n. V₀and V₁can share X₀, X₁and r over a private channel.

2) V ₀ computes y₁ = F(X₁, r), sk = F(X ₀, y ₁). V ₀ sends (X₀, r, s) at time T-t(V₀, p) over an authenticated broadcast channel.

3)V₁ also computes y ₁=F(X ₁, r), s_k=F(X ₀, y ₁)and sends (X₁, s) at time T-t(V₁, p) over an authenticated broadcast channel.

4) Upon receiving (X₀, r, s) and (X₁, s) at time T, P first computes y₁=F(X₁, r). Then, P computes sk=F(X₀, y₁)as a shared key.

Theorem 1 If F is an ε-secure BSM PRG, X₀and X₁ have min-entropy (δ+β)n and βn is the total retrieval bound, then protocol p2vKE¹ is a secure position based p2v key exchange protocol in one dimension against an arbitrary number of colluding adversaries.

Outline of proof: Assuming that p2vKE ¹ is not secure, we have that adversary G could distinguish between sk generated by Key(V, P, p)and a random string U with a non-negligible probability.

Under the BRM, we know that the adversaries between V₁and P can compute only F(X₁, r), but that they does not have X₀ to compute sk. The adversaries between V₂and P cannot compute F(X₁, r), thus they cannot compute sk.

According to the Definition of BSM PRG, no adversary could distinguish between sk and U without adequate information. Thus, Theorem 1 holds.

Protocol p2vKE^d in d-dimensions requires at least(d+1) verifiers to carry out position based p2v key exchange in d-dimensions.

The detailed description of protocol p2vKE^d in the BRM is as follows:

BSM PRG F: {0, 1}ⁿ×{0, 1}^m→{0, 1}^m.

Initialization: The Initialization phase is as same as that of protocol p2vKE ¹.

Key Exchange:

1) V₀generates X₀with min-entropy (δ+β)n and m-bit random string r, and V_i generates X _i with minentropy(δ+β)n(1≤i≤d). V_i can share X ₀, {X _i}(1≤i≤d)androver a private channel.

2) V₀ computes the shared key sk = F(X₀, r₀), w h e r e r_i-1=F(X_i, r_i), r_d=r(1≤i≤d). V₀ sends(X₀, r, s)at time T-t(V₀, p) over an authenticated channel, where s=(sid, p).

3) V_i computes the shared key s k and sends (X _i, s) at time T-t(V_i, p) over an authenticated channel. (1≤i≤d)

4)Upon receiving(X ₀, r, s)and{X₁, …, X_d}at time T, P computes the shared key sk=F(X ₀, r ₀), where r_i-1=F(X_i, r_i), r_d= r (1≤i≤d).

Theorem 2 If F is ε-secure BSM PRG, {X_i} have min-entropy(δ+β)n and βn is the total retrieval bound (0≤i≤d), then protocol p2vKE^d is a secure position based p2v key exchange protocol in d-dimensions.

The proof of Theorem 2 is similar to that of Theorem 1. Hence, it will not be discussed in this paper.

With regard to the region available for PbKE in two dimensions or three dimensions, Chandran et al. show that only a very small region near a verifier could not be used to realize secure PbKE, whether it be the p2v mode or the p2p mode^[4].

In this section, we begin by presenting a position based p2p key exchange protocol in one dimension. Then, we show a generic version of the p2p key exchange protocol p2pKE^d in d-dimensions(d∈{1, 2, 3}).

Intuitively, a prover P₁could share a key k₁with a verifier, and another prover P₂could also share a key k₂with a verifier using position based p2v key exchange. Then, prover P₁and prover P₂run a key exchange protocol, such as the Needham-Schroeder protocol^[14], involving a trusted third party (i. e. the above verifier) to carry out position based key exchange between prover P₁and prover P₂. However, a fatal shortcoming of this construction is that the verifier must maintain the correlation between a prover’s current position and its key generated by the p2v mode. Otherwise, a prover may question that whether the position of the other prover during the p2v position based key exchange protocol is its current position or not. Obviously, maintaining this correlation is the construction′s vulnerability and is too costly from the verifiers perspective. Furthermore, this construction demonstrates worse performance in terms of both efficiency and scalability.

Therefore, a construction based on the p2v mode would not be an effective way to realize p2p key exchange. In the following section, we discuss how to realize the position based p2p key exchange protocols.

The position based p2p key exchange protocol in one dimension, denoted by p 2pKE ¹, is shown in Fig.4. For one dimension, we employ two verifiers, denoted by V₀ and V₁(which send messages at the speed of radio waves).

We assume that both position p₁and position p₂ being claimed by prover P₁and prover P₂respectively are located between V₀and V₁.

Protocol p2pKE ¹ is secure against an arbitrary number of adversaries, colluding to establish a secret key between P₁and P₂, as long as the total information that these adversaries can retrieve during the protocol is bounded.

A detailed description of protocol p2pKE¹ in the BRM is as follows:

BSM PRG F: {0, 1}ⁿ×{0, 1}^m→{0, 1}^m.

PRF f: {0, 1}^2m×{0, 1}^l→{0, 1}^k.

Initialization: P ₁ and P₂ run the algorithm Init(P₁) and Init(P₂)as follows:

1) Set p ₁ = Init(P₁) and p ₂ = Init(P₂), i. e. P ₁ is located at p₁, and P₂is located at p₂.

2) Set s = (sid, p ₁, p ₂) where sid is the session identity.

Let t(V_i, p)be the time taken for a message from verifier V_i to reach position p. Let T ₁ and T ₂ be the times at which the message sent by V₀arrive p₁and p₂respectively. Then, we have that T₁-T₂=t(V₀, p₁)-t(V₀, p₂).

Key exchange: P ₁ and P₂ run the algorithm Key(V={V₁, V₂}, P₁, p₁, P₂, p₂) as follows:

1) V₀generates X₀with min-entropy (δ+β)n and m-bit random string r, and V₁ generates X₁ and X₂ with min-entropy (δ+β)n. V₀and V₁can share X₀, X₁, X₂ androver a private channel.

2) V₀computes y₁= F(X₁, r), z₁= F(X₀, y₁), y₂= F(X₂, r) and z₂= F(X₀, y₂), and sets $z=z_1\oplus z_2$. V₀ sends (X₀, r, z, s) at time T₁-t(V₀, p₁) over an authenticated broadcast channel.

3) V₁sends (X₁, s) and (X₂, s) at time T₁-t(V₁, p₁) and T₂-t(V₁, p₂) respectively over an authenticated broadcast channel.

4) Upon receiving (X₀, r, z, s) and (X₁, s) at time T₁, P₁ computes y₁=F(X₁, r), z₁=F(X₀, y₁)and $z_2=z\oplus z_1$ . Then, P₁ computes sk=f(z ₁, z ₂)as a shared key.

5) Upon receiving (X₀, r, z, s) and (X₂, s) at time T₂, P₂ computes y₂=F(X₂, r), z₂=F(X₀, y₂)and $z_1=z\oplus z_2$. Then, P₂ computes sk=f(z₁, z ₂)as a shared key.

Theorem 3 If F is an ε-secure BSM PRG, f is PRF, X_i has min-entropy (δ+β)n and βn is the total retrieval bound(0≤i≤2), then protocol p2pKE¹ is a secure position based p2p key exchange protocol in one dimension against an arbitrary number of colluding adversaries.

Outline of proof: Assuming that p2pKE ¹ is not secure, an adversary G can distinguish between sk generated by Key(V, P ₁, p ₁, P ₂, p ₂) and a random string U with a non-negligible probability.

Because the messages from the verifiers are broadcasted in an authenticated channel, no adversary can successfully launch an attack on the integrity of those messages. According to the protocol p2pKE¹, the session key sk should be equal to f(z ₁, z ₂). If an adversary G were able to successfully attack the protocol p2pKE¹, there are two possible events:

Event 1 Adversary G could distinguish between sk and U without z₁and z₂. According to the Definition of PRF, Event 1 occurs with only a negligible probability.

Event 2 Adversary G could obtain the value of z₁ and z₂. According to the BRM, Event 2 occurs with only a negligible probability. We know that the adversaries between V₁and P₁can compute F(X₁, r) and F(X₂, r) but do not have X₀to compute z₁and z₂. The adversaries between P₁and P₂can only compute F(X₂, r) but do not have X₀ to compute z₁. The adversaries between V₂and P₂cannot compute F(X₁, r) and F(X₂, r), thus they cannot obtain z₁and z₂.

Therefore, if f is a PRF and F is an ε-secure BSM PRG, then ε_f, ε_F1, ε_F2, ε_F3, and ε_F4 are negligible, and ε_G is also negligible. Theorem 3 holds.

Protocol p2pKE^d in d dimensions requires at least (d+1) verifiers to realize position based p2p key exchange in d-dimensions.

A detailed description of protocol p2pKE^d in the BRM is as follows:

BSM PRG F: {0, 1}ⁿ×{0, 1}^m→{0, 1}^m.

PRF f: {0, 1}^2m×{0, 1}^l→{0, 1}^k.

Initialization is the same as that of protocol p 2 pKE ¹. Key exchange:

1) V₀generates X₀with min-entropy (δ+β)n and m-bit random string r, and V_i generates X_{(i, 1)}and X_{(i, 2)} with min-entropy(δ+β)n(1≤i≤d). V_i can share X ₀, {X_{(i, j)}} (1≤i≤d, 1≤j≤2) and r over a private channel.

2) V₀computes z₁= F(X₀, r_{(0, 1)}) and z₂=F(X₀, r_{(0, 2)}), where r_{(i-1, j)}= F(X_{(i, j)}, r_{(i, j)}), r_{(d, j)}= r (1≤i≤d, 1≤j ≤ 2), and sets $z_1=z_1\oplus z_2$. V₀ sends(X₀, r, z, s)at time T₁-t(V₀, p₁) over an authenticated channel, where s = (sid, p₁, p₂).

3) V_i sends (X_{(i, 1)}, s) and (X_{(i, 2)}, s) at time T ₁-t(V_i, p ₁)and T ₂-t(V_i, p ₂)respectively over an authenticated channel. (1≤i≤d)

4) Upon receiving (X₀, r, z, s) and {X_{(1, 1)}, … , X_{(d, 1)}}at time T₁, P₁computes z₁= F(X₀, r_{(0, 1)}) where r_{(i-1, 1)}=F(X_{(i, 1)}, r_{(i, 1)}), r_{(d, 1)}=r(1≤i≤d)and$z_2=z\oplus z_1$. Then, P ₁ computes sk=f(z₁, z ₂)as a shared key.

5) Upon receiving (X₀, r, z, s) and {X_{(1, 2)}, …, X_{(d, 2)}}at time T₂, P₂computes z₂= F(X₀, r_{(0, 2)}) where r_{(i-1, 2)}=F(X_{(i, 2)}, r_{(i, 2)}), r_{(d, 2)}=r(1≤i≤d)and $z_1=z\oplus z_2$. Then, P₂ computes sk=f(z₁, z ₂)as a shared key.

Theorem 4 If F is an ε-secure BSM PRG, f is a PRF, X₀ and {X_{(i, j)}} have min-entropy (δ+β)n andβn is the total retrieval bound (1≤i≤d, 1≤j≤2), then protocol p2 pKE^d is a secure p2p position based key exchange protocol in d-dimensions.

The proof of Theorem 4 is omitted due to space limitations.

In this section, we extend the above protocols in order to establish some useful properties of key exchange, including key confirmation and without key escrow. Due to space limitations, we omit the detailed descriptions and security proofs of the extended protocols.

A key exchange protocol between parties A and B satisfies mutual key confirmation if both of them are assured that the other party possesses the secret key. Obviously, protocol p2vKE^d and p2pKE^d do not have the key confirmation property. That is, a prover has no assurance that whether the verifiers (in the p2v mode) or the other prover (in the p2p mode) can obtain the shared key or not.

We can use message authentication code (MAC) to extend PbKE protocols for the key confirmation property as follows.

Assuming that g is a secure MAC algorithm, and f is a secure PRF, the prover P and the verifier V_i(in the p2v mode) or the other prover P′(in the p2p mode) have shared the secret key sk. First, the prover P and the verifier V_i(in the p2v mode)or the other prover P′(in the p2p mode)can compute the encryption key ek=f(sk, 0)and the authentication key ak=f(sk, 1) as a MAC key. Second, the prover P can compute c₁=g(a k, (P, s, r)), and either the verifier V_i(in the p2v mode)can compute c ₂=g(a k, (V_i, s, r))or the other prover P′(in the p2p mode) can compute c₂ = g(ak, (P′, s, r)). Finally, they exchange the MAC values c₁ and c₂, and verify the validity of the MAC value from the other party. If both of the MAC values pass the verification, they can confirm that the other party must hold the same key.

In the above protocols, we assume that all of the verifiers are trusted. According to the logic of p2 pKE^d (or p2pKE_C^d), all verifiers can compute the shared key between provers P₁and prover P₂in the p2p mode, which implies the problem of key escrow^[15].

However, in some applications, there are only semi-trusted verifiers that provide the positionrelated services. Therefore, prover P₁and prover P₂ maybe wish to keep their communication confidential from the semi-trusted verifiers in the p2p mode. In fact, a semi-trusted verifier can be treated as a passive attacker in the p2p mode.

Based on the DDH (Decision Diffie-Hellman) assumption^[16], we construct a position based p2p key exchange protocol p 2pKE_E^d without key escrow by adding a DH Exchange phase.

The protocol p2pKE_E^d is shown as follows:

BSM PRG F: {0, 1}ⁿ×{0, 1}^m→{0, 1}^m.

PRF f: {0, 1}^2m×{0, 1}^l→{0, 1}^k.

MAC g : {0, 1}^l×{0, 1}^2m→{0, 1}^k.

G: a cyclic group with prime orderqand generatorg. Initialization & Key Exchange: Prover P₁and prover P₂run the Initialization and Key Exchange phases as in protocol p2pKE^d and share a secret sk.

DH Exchange:

1)P ₁ selects a random a from Z_q, and sends(P₁, s, g^a)to P₂.

2)Upon receiving(P₁, s, g^a), P₂ selects a random b from Z_q, computes key=(g^a)^b and the authentication tag c₂=g(sk, (P₂, s, g^b, g^a)), then it sends(P₂, s, g^b, c₂) to P₁.

3)Upon receiving(P₂, s, g^b, c ₂), P ₁ first verifies the validity of the authentication tag c₂, and if successful computes key=(g^b)^a and the authentication tag c₁=g(sk, (P₁, s, g^a, g^b)). Then, P₁ sends(P ₁, s, c ₁)to P₂ and outputs key as a shared key.

4) Upon receiving (P₁, s, c₁), P₂verifies the validity of c₁. If successful, P₂outputs key as a shared key.

Obviously, protocol p2 pKE_E^d, like protocol p2pKE_C^d, has the property of key confirmation when using the message authentication code g(sk, •). At the same time, p2pKE_E^d is also a secure position based p2p key exchange protocol if the DDH assumption holds.

In this section, we compare the PbKE protocols in three dimensions. Table1 shows the comparison results.

Security: It is obvious that all of the position based key exchange protocols in this paper satisfy the Definition of a secure position based key exchange under Assumption 1, Assumption 2 and Assumption 3.

In addition, protocol p2vKE_C³ and p2pKE_C³ have the property of key confirmation, while protocol p2pKE_E³ has the properties of key confirmation and being without key escrow by using Assumption 4 (i. e. the DDH assumption).

Performance: From the viewpoint of the verifiers in the p2p mode, the communication overhead and computation cost are the same. In other words, protocol p2pKE_C³ and protocol p2pKE_E³ would not generate additional cost for the verifiers, which helps the verifiers to provide reliable position-related services.

Protocols p 2vKE³ and p2 pKE³ are suitable for energy-limited applications, since the provers in protocol p2vKE³ and p2pKE ³ have no communication overhead.

Compared to protocol p2vKE³ and p2pKE³, protocol p2vKE_C³ and p2pKE_C³ incur extra communication overhead and computational cost to the prover for the key confirmation property. We note that the added operation cost of PRF or MAC is acceptable since there are some very efficient implementations of PRF and MAC for lowpower devices.

Note that position based cryptographic protocols using the TOA technique have a disadvantage in that they are not robust to round trip delays, which include propagation delays and processing delays. Therefore, the PbKE protocols in this paper as well as the protocols in Ref. [4] are all based on an assumption that there is no round trip delay: that is that all the participants can immediately send, receive and process data without delay.

Position based key exchange is a basic primitive in position based cryptography. This paper distinguishes the prover-to-verifier mode and the prover-toprover mode of position based key exchange. According to the different requirements of the two modes, this paper discusses the security definitions and the implementation of position based key exchange. Moreover, this paper extends position based key exchange protocols in order to capture two meaningful properties of key exchange: key confirmation and without key escrow. Finally, this paper compares the position based key exchange protocols in two modes from both security and performance perspectives.

The next step will be to find new assumptions for position based cryptography and to construct new position based key exchange protocols that are more robust to round trip delays.

In Tab.1, f denotes the cost of one operation of PRF; g denotes the cost of one computation or verification of MAC; F denotes the cost of one operation of BSM PRG; E denotes the cost of one exponential operation in the DH exchange.