# A New Password- and Position-Based Authenticated Key Exchange

Authors: Jia Fan; Lanfei Qiao; Yunfei Cao; Shanglin Liu; Wenke Zhang; Lin Tang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Password-based authenticated key exchange is a popular method for secure authentication and key exchange. With the wide application of unmanned aerial vehicles, position information has also become an important factor in authentication. In this paper, we present a new key exchange protocol, which firstly realizes dual authentication for both password and position, and we propose two applicable scenarios for the PPAKE mechanism: one is unmanned aerial vehicle authentication, and the other one is authentication in the military base. By adding position authentication, the reliability of authentication has improved, and the difficulty of adversarial attacks also increases. Any arbitrary adversary who can listen, tamper, and send messages can only perform an online attack for password guessing at a specified position. Finally, we provide security proofs under the defined model.


---

## Body

## 1. Introduction

Key exchange protocol is designed to allow two or more parties to negotiate and share session keys over insecure channels to establish an encrypted communication. To achieve secure communication in open and insecure communication channels, Diffie and Hellman [1] in 1976 introduced the concept of public key cryptography and the famous Diffie–Hellman key exchange protocol which establishes a shared session key between two communicating parties. However, the Diffie–Hellman protocol cannot resistant man-in-the-middle attacks or provide dual authentication.A large number of authentication key exchange protocols have been proposed subsequently [2–5], as well as corresponding applications [6–10]. According to different application scenarios and assumptions, the authentication key exchange protocols are broadly divided into the following two categories: one assumes that each interacting party has a high-entropy private key which can be used to generate a high-entropy session key; the other one assumes that each interacting party only shares a weak password and generates a high-entropy session key through interaction.Bellovin and Merritt [11] in 1992 first proposed the password-based authentication key exchange (PAKE) protocol, called the BM scheme. Subsequently, there were many improvements based on the BM scheme, but none of these had a security model. Until EUROCRYPT 2000, Boyko et al. [12] presented the first security model of PAKE. Under the random oracle model, the SPAKE scheme in [13] is an efficient provable secure scheme. Under the standard model, Goldreich and Lindell proposed a solution based on one-way functions and zero knowledge in EUROCRYPT 2001, but neither it nor the subsequent theoretical constructs based on it are practical. Katz et al. [14] proposed the first practical password-based solution for provable security with the help of public reference strings in EUROCRYPT 2001, called the KOY scheme. Gennaro and Lindell extended the KOY scheme to a general construction based on smooth projection hashing systems and the choice of secret security encryption schemes in EUROCRYPT 2003 [15]. There has have been much subsequent work based on this scheme [16–19], with [16, 17] being the most efficient.Xue et al. [20] found that the scheme in [16], requiring six group elements and a random string, is more efficient than other current schemes in the BPR [21] model while under the standard model. And they presented an improved PAKE protocol by replacing the CCA-secured encryption scheme in [16] with a CCA-secured key encapsulation mechanism (KEM). This protocol finally requires only 5 group elements and 2 short random strings. And the length of a random string is 1/3 log p bit (the size is equal to 1/6 of the length of a group element on an elliptic curve).In previous proposals, the form of password-based key exchange needs to face the challenge of generating high-entropy session keys from low-entropy keys. The current password-based key exchange protocol is mainly used in the scenario of the server-client, and the mainstream technology adopts a CCA2 secure encryption scheme and a smooth projective hash function.In many real applications, such as drone control stations and military base communications, the position information is also an important type of authentication information. The first position-based authentication protocol was presented by Chandran et al. [22], where a location can be verified in the 3D space using 4 verifiers. The protocol has many application scenarios, e.g., 4 aircrafts can verify the controller's position and communication between military bases. Followed by this work, a lot of schemes are proposed, such as blockchain-based positioning scheme [23], tracking cryptographic keys and encrypted data using position verification [24], and position-based encryption [25].


## 2. Motivation

Position and password are all important information in wireless communication. Our basic idea is to combine the result of PAKE in [20] with the secure position-based protocol in [22] to obtain a secure key exchange protocol for dual authentication of position and password (called PPAKE). Dual authentication based on the password and position can improve the reliability of authentication and increase the difficulty of adversarial attacks. To propose a secure PPAKE protocol, we solved the following issues:(1)
How do the four verifiers determine the position information of the participant and verify it simultaneously?(2)
How does the participant verify the password information of the four verifiers and generate a high-entropy session key at the same time?(3)
How do four verifiers generate the same high-entropy session key while verifying the position and password information of the participant?By applying our PPAKE protocol, four verifiers use a common reference string to authenticate the participant and initiate encrypted communication by sharing the password and position information. The PPAKE protocol includes ElGamal ciphertext, universal projective hash function, key encapsulation mechanism, 4-wise independent hash function, and pseudo-random generator.The proposed PPAKE protocol can realize the synchronization authentication of password and position information. The prior art authenticates participants unilaterally, but the present technique uses the password and position information to authenticate the joining party and negotiate a common session key to prepare for the next step of private communication. Specifically, the adversary cannot pretend to be the joining party to verify from a location that is inconsistent with its declared location. Any location and password forged by the adversary cannot be authenticated.Our PPAKE can be widely applied in many scenarios, for example, (1) the communication base station that needs to verify the position and password of the user and authorizes networking and (2) real-life logistics distribution scenarios require password and location information verification to negotiate important content. Other applications, such as unmanned aerial vehicle authentication and military base authentication, will be described in the later section. From what has been discussed above, it is very meaningful to present a key exchange protocol for dual authentication of password and position.


## 3. Applications of PPAKE

Next, we propose two applicable scenarios for the PPAKE mechanism: one is unmanned aerial vehicle authentication, and the other one is authentication in military base.


### 3.1. Unmanned Aerial Vehicle Authentication

The unmanned aerial vehicle (UAV) is a kind of unmanned aircraft that uses wireless remote control or flight planning. Due to a series of advantages such as low cost, easy operation, fast image acquisition speed, high ground resolution, not restricted by a fixed environment, and no need to worry about accidental crashes that may cause casualties on board, UAVs have been widely used in map surveying and mapping update, geological survey, natural disaster monitoring, agricultural remote sensing monitoring, and other fields.Control technology of the UAV refers to the technology of remote control, telemetry, tracking, positioning, and information transmission to the UAV. The corresponding technical facilities consist of a data chain and ground control station. The data chain realizes data transmission and delivery, tracking, and positioning between the ground control station and the UAV. The ground control station is used to realize such functions as mission planning, link control, flight control, load control, flight track display, and parameter and image display, as well as recording and distribution.To ensure the authenticity of the information content and its source transmitted between the subjects, dual authentication and key exchange should be carried out before information exchange between the UAV and the ground control station. Our PPAKE adopts dual authentication based on the position and password to complete the identity authentication and key exchange between the two parties. When a UAV holding a legal identity and password granted by the ground control station sends a request to the ground control station for authentication and information transmission, it should also submit the encrypted identity, password, and position information.Then, the ground control station authenticates the information separately. When the ground control station confirms the information, if it matches the prestored information, the session key is generated, and the message is transmitted; otherwise, the request for authentication and message transmission is aborted.


### 3.2. Military Base

In recent years, several local wars in the world have shown the wide application of information technology in the military field, which has brought about comprehensive and profound changes to the war pattern. With the increasing use of modern communication and computer network technology, the situation of military information carriers has undergone great changes. The hidden danger of information security also spreads from simple document management in the past to information systems, equipment, places, and various links in information operation.Modern communication technology in the army can be divided into three categories, namely, wired communication, wireless communication, and network communication, which all exist in different ways and have different degrees of security risk. In the process of wireless communication, to remote access system resources or data transmission, the user must obtain appropriate permissions. Dual identity authentication gives a simple and effective security solution to the problem.Specifically, the PPAKE adopts the form of dual authentication based on the password and position to authenticate a wireless user who has registered with the base and obtained his or her identity ID and password and generate a session key. For a user who holds an ID and password, when sending an access and authentication request to the base station, the user needs to submit the encrypted ID, password, and location information. Then, the base station will authenticate each message separately.


## 3.1. Unmanned Aerial Vehicle Authentication

The unmanned aerial vehicle (UAV) is a kind of unmanned aircraft that uses wireless remote control or flight planning. Due to a series of advantages such as low cost, easy operation, fast image acquisition speed, high ground resolution, not restricted by a fixed environment, and no need to worry about accidental crashes that may cause casualties on board, UAVs have been widely used in map surveying and mapping update, geological survey, natural disaster monitoring, agricultural remote sensing monitoring, and other fields.Control technology of the UAV refers to the technology of remote control, telemetry, tracking, positioning, and information transmission to the UAV. The corresponding technical facilities consist of a data chain and ground control station. The data chain realizes data transmission and delivery, tracking, and positioning between the ground control station and the UAV. The ground control station is used to realize such functions as mission planning, link control, flight control, load control, flight track display, and parameter and image display, as well as recording and distribution.To ensure the authenticity of the information content and its source transmitted between the subjects, dual authentication and key exchange should be carried out before information exchange between the UAV and the ground control station. Our PPAKE adopts dual authentication based on the position and password to complete the identity authentication and key exchange between the two parties. When a UAV holding a legal identity and password granted by the ground control station sends a request to the ground control station for authentication and information transmission, it should also submit the encrypted identity, password, and position information.Then, the ground control station authenticates the information separately. When the ground control station confirms the information, if it matches the prestored information, the session key is generated, and the message is transmitted; otherwise, the request for authentication and message transmission is aborted.


## 3.2. Military Base

In recent years, several local wars in the world have shown the wide application of information technology in the military field, which has brought about comprehensive and profound changes to the war pattern. With the increasing use of modern communication and computer network technology, the situation of military information carriers has undergone great changes. The hidden danger of information security also spreads from simple document management in the past to information systems, equipment, places, and various links in information operation.Modern communication technology in the army can be divided into three categories, namely, wired communication, wireless communication, and network communication, which all exist in different ways and have different degrees of security risk. In the process of wireless communication, to remote access system resources or data transmission, the user must obtain appropriate permissions. Dual identity authentication gives a simple and effective security solution to the problem.Specifically, the PPAKE adopts the form of dual authentication based on the password and position to authenticate a wireless user who has registered with the base and obtained his or her identity ID and password and generate a session key. For a user who holds an ID and password, when sending an access and authentication request to the base station, the user needs to submit the encrypted ID, password, and location information. Then, the base station will authenticate each message separately.


## 4. Security Model

In this model, we assume that (1) the clocks of all verifiers are synchronized. We require that the pace between verifiers and the participants be the same. (2) The protocol has a fixed set of protocol users. (3) Messages travel at a speed equal to that of radio waves. (4) Each principal can execute the protocol multiple times with different partners. As described above, the PPAKE protocol concludes two phases, namely, the initialization phase and the execution phase.Initialization phase: in this phase, public parameters are established, each user’s position is given, and the unique identifiers of all the verifiers are given to all protocol users. Each participant shares a password with all verifiers. Each password is uniformly chosen from the set1,…,Dn for some integer Dn depending on n.Execution phase: in this phase, we separately define how the verifiers, participants, and adversaries execute in these following two security definitions according to [16, 22].Position-based authentication [22]: in the execution phase, any verifier and adversary can send all the following three types of messages: broadcast messages, directional messages, and private multicast messages. Any participant can send broadcast messages and directional messages. The detailed description of all types of messages is as follows:(1)
Broadcast messages: a broadcast message travels with equal speed in all directions, in concentric hyperspheres centered at the sender’s positionP, which arrives at a position P′ after time t (t is the time the radio waves travel from P to P′)(2)
Directional messages: a directional message travels in a region of concentric hyperspheres centered at the sender’s positionP and arrives at position P′ after time t (t is the time the radio waves travel from P to P′)(3)
Private multicast messages: a verifier (or an adversary) talks to other verifiers (or other adversaries) via a private channelA PPAKE protocol in the 3-dimensional space is described as a set of verifiersVer=V1,V2,…,Vn at positions pos1,pos2,…,posn, respectively, which take as input a claimed position P′ of a participant at position P and jointly return “accept” after interacting with the honest participant (if P′ = P) and in the absence of any adversarial parties.Definition 1.
A protocol PPAKE satisfies position-based authentication if for any positionP (in the tetrahedron enclosed by pos1,pos2,…,posn) and for any adversary Ai at position aposi with P≠aposi, verifiers V1,V2,…,Vn at positions pos1,pos2,…,posn jointly return “accept” with a negligible probability ε in the defined security parameter.Password-based authenticated key exchange [16]: in the execution phase, the adversary is given oracle access to these different instances. All the oracles are described as follows:(1)
Send: this oracle sends message M to instance ΠUi (denote instance i of user U as ΠUi) and outputs the message sent by the instance of ΠUi to the adversary(2)
Execute: if ΠUi and ΠU'j have not yet been used, this oracle executes the protocol between these instances and outputs the resulting transcript to the adversary(3)
Reveal: this oracle outputs the session key skUi to the adversaryFinally, adversaryA makes a single query Test to a fresh instance ΠUi and outputs a bit b′. In the Test oracle, a random bit b is chosen; if b = 1, the adversary is given skUi, and if b = 0, the adversary is given a session key chosen uniformly from the appropriate space. A succeeds if either b′=b or at the end of the experiment, there is an instance ΠUi that accepts but is not semipartnered with any other instance (semipartnering is defined as follows: instances ΠUi and ΠU′j are partners, or session ids sidUi and sidU′j agree, except possibly for the final message, and partner ids pidUi=U′ and pidU′j=U.)Definition 2.
A PPAKE protocol Π achieves password-based authenticated key exchange if for all dictionary sizesDn and for all PPT adversaries A making at most Qn online attacks, A succeeds with advantage AdvA,Π=def2⋅PrSucc−1≤Qn/Dn+εn, where Succ is the event that the adversary succeeds and ε is negligible in the defined security parameter.
We claim that if protocol Π satisfies both position-based authentication and password-based authenticated key exchange, then protocol Π is a secure PPAKE protocol.


## 5. Description of PPAKE

In the PPAKE protocol, we assume that (1) all participants of the system have a synchronized clock, and all users have access to the public reference string CRS; (2) all verifiers share the private random number string VRS; (3) the calculation time is negligible relative to the transmission time of the information; and (4) computation for the Diffie–Hellman problem on a group with prime orderp is difficult.The main process of our PPAKE protocol is described in Figure1, and the details are as follows.Figure 1
Main process of the PPAKE.


### 5.1. Initialize Phase

In this phase, all users share a common reference stringCRS=G,p,g,h,H,Hcr,PRG,d,e and maintain a common clock. In CRS,G is a cyclic group of order p, and generally, the length of p is greater than 160 bits. g and h are random elements on group G. H is a 4-wise independent hash function. Hcr is a collision-resistant hash function. PRG is a pseudo-random generator. d and e are elements on group G; specifically, d=ga1hb1 and e=ga2hb2 are the public keys for the key encapsulation mechanism (KEM), where a1,a2,b1,andb2 are random numbers generated when the system is established.Assume that all verifiersVi (i = 1, ..., 4) share a random number string VRS=K1,K2,K3,K4,r through a secure communication channel. Generally, the length of all K1,K2,K3,andK4 is greater than 80 bits. The length of r is greater than 160 bits, and t1,…,t4, respectively, represent the time in which the radio waves were transmitted from the verifiers V1,…,V4 to the position of the participant (write as P for short).


### 5.2. Execution Phase

Now, we introduce the execution phase, which is described from phase 1 to phase 4.


#### 5.2.1. Phase 1

In this phase, all verifiers send authentication information toP, in which the content of the message sent by the prime verifier is slightly different from those sent by other nonprime verifiers. Figure 2 illustrates the calculation process of the prime verifier V1. V1 sends the calculated results, that is, encrypted password and position authentication information, to P. Figure 3 illustrates the calculation process of nonprime verifiers Vii=2,3,4. Nonprime verifiers calculate and send the position authentication information, which reaches P at the same time. The computation details are described as follows:(1)
V1 selects r from VRS and calculates A=grandc′=hrgπ, where π represents the password previously shared between all verifiers and P. Then, V1 broadcasts (K1,A∥c′) at time T−t1, as shown in Figures 1 and 2.(2)
V2 randomly selects X1, calculates K2′=PRGX1,K1⊕K2, and broadcasts X1,K2′ at time T−t2, as shown in Figures 1 and 3.(3)
V3 randomly selects X2, calculates K3′=PRGX2,K2⊕K3, and broadcasts X2,K3′ at time T−t3, as shown in Figures 1 and 3.(4)
V4 randomly selects X3, calculates K4′=PRGX3,K3⊕K4, and broadcasts (X3K4′) at time T−t4, as shown in Figures 1 and 3.Figure 2
Prime verifier’s algorithm for generating the sent message in phase 1.Figure 3
Nonprime verifier’s algorithm for generating sent messages in phase 1.


#### 5.2.2. Phase 2

As shown in Figure4, phase 2 can be divided into three steps, as detailed from Figures 5 to 7. The computation details are described as follows.Figure 4
The participant’s algorithm for generating the authentication information in phase 2.Figure 5
The participant’s algorithm for calculating the password-based authentication information.Figure 6
The participant’s algorithm for calculating position-based authentication information.Figure 7
The participant’s algorithm for generating password and position authentication information.Figure5 illustrates the process of calculating the password-based authentication information. When calculating the password information, P randomly calculates μ, the public key of the hash proof function, and the hash value σ, according to the password-encrypted ElGamal secret message. σ is divided into three parts, which can be written as τp‖ skp‖rp←σ, where τp is used to verify the identity of the verifier, skp is used to generate the session key, and rp is used to encapsulate the key and dissimulate the password and location information.The specific calculation steps are as follows:P randomly selects λ1andλ2 from ℤq (the value of q is related to the safety parameters), computes μ=gλ1hλ2,c=c′g−π, and σ=Aλ1cλ2, where σ is divided into three equal pieces by bit value τp‖ skp‖rp←σ, then computes ckem=grP,hrP and kkem=HdterP, where t=HcrgrP,hrP,A‖c′,V1,P; and finally, it outputs μ‖ckemandkkem as (2 − P − 1).Figure6 illustrates the process of calculating position-based authentication information K4 by the information received in phase 1. P computes the position information Ki+1=PRGXi,Ki⊕Ki+1'i=1,2,3 and outputs K4 as (2 − P − 2).Figure7 illustrates how to compute password and position authentication information (2 − P − 3) from (2 − P − 1) and (2 − P − 2). P computes δ=kkemπ‖K4 and broadcasts μ‖ckem‖δ to Vi (i = 1, 2, 3, and 4).


#### 5.2.3. Phase 3

In this phase, all verifiersVi (i = 1, 2, 3, and 4) verify P’s password and position authentication information, calculate the session key, and reply the authentication information to P.As shown in Figure8, all verifiers receive the information from P, calculate the hash value σ, verify the password, and check the consistency of the receiving time and location. After passing all the authentication checks, all verifiers send the first block of σ back to P. The detailed computation process is as follows: when Vi (i = 1, 2, 3, and 4) receives μ‖ckem‖δ, it calculates the hash value σ=μr and sets τVskvrV←σ. Then, Vi verifies ckem, δ, and the receiving time. Only if ckem is equal to grV,hrV, δ is equal to HdterV⊕π∥K4, where t=HcrgrV,hrV,A‖c′,V1,P, and the receiving time is equal to T+ti, then Vi sends τV as the message of (3−Vi to P; otherwise, Vi aborts the progress of phase 3. At the end of this phase, Vi sets the negotiated session key as skv.Figure 8
Verification algorithm of the verifiers in phase 3.


#### 5.2.4. Phase 4

As shown in Figure9, P determines whether the authentication message τV sent by Vi is equal to τp. If they are equal, P sets skp as the communication key with verifiers; otherwise, P aborts the progress of phase 4.Figure 9
Protocol execution process of the participant in phase 4.


## 5.1. Initialize Phase

In this phase, all users share a common reference stringCRS=G,p,g,h,H,Hcr,PRG,d,e and maintain a common clock. In CRS,G is a cyclic group of order p, and generally, the length of p is greater than 160 bits. g and h are random elements on group G. H is a 4-wise independent hash function. Hcr is a collision-resistant hash function. PRG is a pseudo-random generator. d and e are elements on group G; specifically, d=ga1hb1 and e=ga2hb2 are the public keys for the key encapsulation mechanism (KEM), where a1,a2,b1,andb2 are random numbers generated when the system is established.Assume that all verifiersVi (i = 1, ..., 4) share a random number string VRS=K1,K2,K3,K4,r through a secure communication channel. Generally, the length of all K1,K2,K3,andK4 is greater than 80 bits. The length of r is greater than 160 bits, and t1,…,t4, respectively, represent the time in which the radio waves were transmitted from the verifiers V1,…,V4 to the position of the participant (write as P for short).


## 5.2. Execution Phase

Now, we introduce the execution phase, which is described from phase 1 to phase 4.


### 5.2.1. Phase 1

In this phase, all verifiers send authentication information toP, in which the content of the message sent by the prime verifier is slightly different from those sent by other nonprime verifiers. Figure 2 illustrates the calculation process of the prime verifier V1. V1 sends the calculated results, that is, encrypted password and position authentication information, to P. Figure 3 illustrates the calculation process of nonprime verifiers Vii=2,3,4. Nonprime verifiers calculate and send the position authentication information, which reaches P at the same time. The computation details are described as follows:(1)
V1 selects r from VRS and calculates A=grandc′=hrgπ, where π represents the password previously shared between all verifiers and P. Then, V1 broadcasts (K1,A∥c′) at time T−t1, as shown in Figures 1 and 2.(2)
V2 randomly selects X1, calculates K2′=PRGX1,K1⊕K2, and broadcasts X1,K2′ at time T−t2, as shown in Figures 1 and 3.(3)
V3 randomly selects X2, calculates K3′=PRGX2,K2⊕K3, and broadcasts X2,K3′ at time T−t3, as shown in Figures 1 and 3.(4)
V4 randomly selects X3, calculates K4′=PRGX3,K3⊕K4, and broadcasts (X3K4′) at time T−t4, as shown in Figures 1 and 3.Figure 2
Prime verifier’s algorithm for generating the sent message in phase 1.Figure 3
Nonprime verifier’s algorithm for generating sent messages in phase 1.


### 5.2.2. Phase 2

As shown in Figure4, phase 2 can be divided into three steps, as detailed from Figures 5 to 7. The computation details are described as follows.Figure 4
The participant’s algorithm for generating the authentication information in phase 2.Figure 5
The participant’s algorithm for calculating the password-based authentication information.Figure 6
The participant’s algorithm for calculating position-based authentication information.Figure 7
The participant’s algorithm for generating password and position authentication information.Figure5 illustrates the process of calculating the password-based authentication information. When calculating the password information, P randomly calculates μ, the public key of the hash proof function, and the hash value σ, according to the password-encrypted ElGamal secret message. σ is divided into three parts, which can be written as τp‖ skp‖rp←σ, where τp is used to verify the identity of the verifier, skp is used to generate the session key, and rp is used to encapsulate the key and dissimulate the password and location information.The specific calculation steps are as follows:P randomly selects λ1andλ2 from ℤq (the value of q is related to the safety parameters), computes μ=gλ1hλ2,c=c′g−π, and σ=Aλ1cλ2, where σ is divided into three equal pieces by bit value τp‖ skp‖rp←σ, then computes ckem=grP,hrP and kkem=HdterP, where t=HcrgrP,hrP,A‖c′,V1,P; and finally, it outputs μ‖ckemandkkem as (2 − P − 1).Figure6 illustrates the process of calculating position-based authentication information K4 by the information received in phase 1. P computes the position information Ki+1=PRGXi,Ki⊕Ki+1'i=1,2,3 and outputs K4 as (2 − P − 2).Figure7 illustrates how to compute password and position authentication information (2 − P − 3) from (2 − P − 1) and (2 − P − 2). P computes δ=kkemπ‖K4 and broadcasts μ‖ckem‖δ to Vi (i = 1, 2, 3, and 4).


### 5.2.3. Phase 3

In this phase, all verifiersVi (i = 1, 2, 3, and 4) verify P’s password and position authentication information, calculate the session key, and reply the authentication information to P.As shown in Figure8, all verifiers receive the information from P, calculate the hash value σ, verify the password, and check the consistency of the receiving time and location. After passing all the authentication checks, all verifiers send the first block of σ back to P. The detailed computation process is as follows: when Vi (i = 1, 2, 3, and 4) receives μ‖ckem‖δ, it calculates the hash value σ=μr and sets τVskvrV←σ. Then, Vi verifies ckem, δ, and the receiving time. Only if ckem is equal to grV,hrV, δ is equal to HdterV⊕π∥K4, where t=HcrgrV,hrV,A‖c′,V1,P, and the receiving time is equal to T+ti, then Vi sends τV as the message of (3−Vi to P; otherwise, Vi aborts the progress of phase 3. At the end of this phase, Vi sets the negotiated session key as skv.Figure 8
Verification algorithm of the verifiers in phase 3.


### 5.2.4. Phase 4

As shown in Figure9, P determines whether the authentication message τV sent by Vi is equal to τp. If they are equal, P sets skp as the communication key with verifiers; otherwise, P aborts the progress of phase 4.Figure 9
Protocol execution process of the participant in phase 4.


## 5.2.1. Phase 1

In this phase, all verifiers send authentication information toP, in which the content of the message sent by the prime verifier is slightly different from those sent by other nonprime verifiers. Figure 2 illustrates the calculation process of the prime verifier V1. V1 sends the calculated results, that is, encrypted password and position authentication information, to P. Figure 3 illustrates the calculation process of nonprime verifiers Vii=2,3,4. Nonprime verifiers calculate and send the position authentication information, which reaches P at the same time. The computation details are described as follows:(1)
V1 selects r from VRS and calculates A=grandc′=hrgπ, where π represents the password previously shared between all verifiers and P. Then, V1 broadcasts (K1,A∥c′) at time T−t1, as shown in Figures 1 and 2.(2)
V2 randomly selects X1, calculates K2′=PRGX1,K1⊕K2, and broadcasts X1,K2′ at time T−t2, as shown in Figures 1 and 3.(3)
V3 randomly selects X2, calculates K3′=PRGX2,K2⊕K3, and broadcasts X2,K3′ at time T−t3, as shown in Figures 1 and 3.(4)
V4 randomly selects X3, calculates K4′=PRGX3,K3⊕K4, and broadcasts (X3K4′) at time T−t4, as shown in Figures 1 and 3.Figure 2
Prime verifier’s algorithm for generating the sent message in phase 1.Figure 3
Nonprime verifier’s algorithm for generating sent messages in phase 1.


## 5.2.2. Phase 2

As shown in Figure4, phase 2 can be divided into three steps, as detailed from Figures 5 to 7. The computation details are described as follows.Figure 4
The participant’s algorithm for generating the authentication information in phase 2.Figure 5
The participant’s algorithm for calculating the password-based authentication information.Figure 6
The participant’s algorithm for calculating position-based authentication information.Figure 7
The participant’s algorithm for generating password and position authentication information.Figure5 illustrates the process of calculating the password-based authentication information. When calculating the password information, P randomly calculates μ, the public key of the hash proof function, and the hash value σ, according to the password-encrypted ElGamal secret message. σ is divided into three parts, which can be written as τp‖ skp‖rp←σ, where τp is used to verify the identity of the verifier, skp is used to generate the session key, and rp is used to encapsulate the key and dissimulate the password and location information.The specific calculation steps are as follows:P randomly selects λ1andλ2 from ℤq (the value of q is related to the safety parameters), computes μ=gλ1hλ2,c=c′g−π, and σ=Aλ1cλ2, where σ is divided into three equal pieces by bit value τp‖ skp‖rp←σ, then computes ckem=grP,hrP and kkem=HdterP, where t=HcrgrP,hrP,A‖c′,V1,P; and finally, it outputs μ‖ckemandkkem as (2 − P − 1).Figure6 illustrates the process of calculating position-based authentication information K4 by the information received in phase 1. P computes the position information Ki+1=PRGXi,Ki⊕Ki+1'i=1,2,3 and outputs K4 as (2 − P − 2).Figure7 illustrates how to compute password and position authentication information (2 − P − 3) from (2 − P − 1) and (2 − P − 2). P computes δ=kkemπ‖K4 and broadcasts μ‖ckem‖δ to Vi (i = 1, 2, 3, and 4).


## 5.2.3. Phase 3

In this phase, all verifiersVi (i = 1, 2, 3, and 4) verify P’s password and position authentication information, calculate the session key, and reply the authentication information to P.As shown in Figure8, all verifiers receive the information from P, calculate the hash value σ, verify the password, and check the consistency of the receiving time and location. After passing all the authentication checks, all verifiers send the first block of σ back to P. The detailed computation process is as follows: when Vi (i = 1, 2, 3, and 4) receives μ‖ckem‖δ, it calculates the hash value σ=μr and sets τVskvrV←σ. Then, Vi verifies ckem, δ, and the receiving time. Only if ckem is equal to grV,hrV, δ is equal to HdterV⊕π∥K4, where t=HcrgrV,hrV,A‖c′,V1,P, and the receiving time is equal to T+ti, then Vi sends τV as the message of (3−Vi to P; otherwise, Vi aborts the progress of phase 3. At the end of this phase, Vi sets the negotiated session key as skv.Figure 8
Verification algorithm of the verifiers in phase 3.


## 5.2.4. Phase 4

As shown in Figure9, P determines whether the authentication message τV sent by Vi is equal to τp. If they are equal, P sets skp as the communication key with verifiers; otherwise, P aborts the progress of phase 4.Figure 9
Protocol execution process of the participant in phase 4.


## 6. Security Analysis of PPAKE

Our PPAKE protocol dual authenticates the participant by password and position and negotiates a session key for the next step of private communication. In particular, the prime verifierV1 is responsible for both password-based authenticated key exchange as well as position-based authentication with participant P, while V2,V3,andV4 are mainly responsible for position-based authentication. Our protocol is resistant to an active adversary under the standard model. Firstly, we prove that our PPAKE protocol is secure on password-based authenticated key exchange.Theorem 1.
Assume PKE in [16, 17] is an IND-CPA secure encryption scheme, SPHF (smooth projective hash function) is a ε-smooth SPHF over PKE, and KEM in [26] is an IND-PCA secure KEM, and the PPAKE is secure in the BPR model. In particular, let qe be the number of execute queries, qs be the number of send queries, and qe+qs≤t; we have(1)AdvA,Πn≤1D+tAdvB,EncCPA+tϵsmooth+tAdvEkem−pca.Proof of Theorem 1.In our PPAKE, we use a weak secure notion of KEM, namely, security against plaintext-checkable attack (PCA). Let PKE = (KGen, Enc, Dec) be an IND-CPA secure encryption. Let KEM = (KGenkem, Enckem, Deckem) be an IND-PCA secure KEM with KeySp=D. Let PRG be a pseudo-random generator.We redescribe our PPAKE as follows, in which the position-based authentication part is omitted: in phase 1,V1 sends (A‖c′) to P; in phase 2, P broadcasts μ‖ckem; in phase 3, every verifier computes the negotiated key as skv and sends τV to P; and finally, in phase 4, P checks the value of τV and computes similarly as in [20]. PAKE protocol assumes that, in phase 3, only V1 will compute the negotiated key. In PPAKE, we assume that V2,V3,andV4 can get the value of r from VRS, so they have the ability to compute the negotiated key. At the end of the protocol, all verifiers and the participant share the same session key. People without r cannot compute the shared key. Therefore, the security proof of our PPAKE can also follow the security proof in [20]. Xue et al. proved that their PAKE is secure in the BPR model; the security proof sketch is as follows.The proof proceeds via a sequence of experiments. Let “Gi” denote the sequence of experiments and denote the advantage of adversary A in “Gi” as AdvA,Gin=2PrΑsucceeds  inGi−1. Let G0 be the experiment of BPR challenge. The proof is separated into two phases: the first phase (from G1 to G5) bounds out the advantage of execute queries, and the second phase (from G6 to G10) bounds out the advantage of sendqueries. The detailed descriptions of G1 to G10 are the same as Theorem 2 in [20]. Finally, summing up all the gap advantages, we finally have AdvA,Πn≤1/D+tAdvB,EncCPA+tϵsmooth+tAdvEkem−pca.In the following, we analyze the security of position-based authentication. The completeness follows from the fact that verifiers can computeK4 from the stored Xi values, and the participant can also compute K4 since all the information required is gathered at time T at P. Now, we prove that our PPAKE protocol is secure on position-based authentication.We redescribe the position-based authentication part in our PPAKE as follows: in phase 1,V1 broadcasts A‖c′,K1 at time T−t1, and Vi (i=2,3,4) broadcasts Xi−1,Ki′at timeT−ti; in phase 2, P calculates Ki+1=PRGXi,Ki⊕Ki+1'i=1,2,3 and broadcasts δ, where δ=kkem⊕π‖K4, kkem=HdterP, and t=HcrgrP,hrP,A‖c′,V1,P; and in phase 3, all verifiers verify δ and the receiving time. If the verification passed, then Vi’s authentication on P is successful. There are some differences between the secure positioning protocol proposed by Chandran et al. [22] and our PPAKE, that is, in phase 2, P broadcasts K4, instead of δ.In our protocol, to cooperate with password-based authenticated key exchange, we enhanced the protocol in [22] by encrypting K4. We compute δ=kkem⊕π‖K4, where kkem=HdterP, t=HcrgrP,hrP,A‖c′,V1,P. Therefore, our PPAKE protocol at least satisfies the security of position-based authentication in [22]. For more details of this proof, please refer to Section 7 in [22].From the above analysis, we can claim that our proposed protocol is a secure authenticated key exchange, which provides both password- and position-based authentication.


## 7. Conclusion

In summary, the PPAKE protocol dual authenticates the participant through the password and position and negotiates a common session key to prepare for the next step of private communication. The proposed protocol can resist the attack of the active adversary under the standard model. Specifically, an arbitrary adversary who can listen, tamper, and send messages can only perform an online attack for password guessing at a specified position. The impersonation of any of the position and password by the adversary cannot be authenticated.



---

*Source: 6613392-2021-02-24.xml*