# A Provably Secure and Lightweight Identity-Based Two-Party Authenticated Key Agreement Protocol for Vehicular Ad Hoc Networks

Authors: Quanrun Li; Ching-Fang Hsu; Kim-Kwang Raymond Choo; Debiao He
Journal: Security and Communication Networks
 (2019)

---

## Abstract

As an important part of smart cities, vehicle ad hoc networks (VANETs) have attracted much attention from both industry and academia. In a VANET, generating a secure session key to facilitate subsequent data-in-transit transfer between two or more vehicles is crucial, which can be achieved by using an authenticated key agreement protocol. However, most of the existing identity-based two-party authenticated key agreement protocols have significant computational requirements or are known to be insecure. Thus, in this paper, a secure and efficient identity-based two-party authenticated key agreement protocol is presented by us. This protocol does not involve complex bilinear pairing computations and can generate a valid session key in two rounds. The security of the proposed protocol is proved in the eCK model which has better capability to describe a protocol’s security than the famous CK model, and it has been widely used in the security proof of ID-based key agreement protocols currently. Additionally, we also evaluate its performance for potential utility in a VANET.


---

## Body

## 1. Introduction

As smart cities become a reality, vehicle ad hoc networks (VANETs) will become increasingly crucial. Therefore, data communications in a VANET are no longer restricted to a small number of vehicles, as such communications can occur among a wide range of vehicles (including driverless vehicles and unmanned aerial vehicles), roadside units (e.g., smart traffic lights), and other supporting infrastructure (e.g., IP-based CCTV). This allows the collection of traffic and other environmental information that can be analyzed to facilitate a smooth city operation. For example, information gathered from hurricane sensors and traffic monitoring devices can help to alert nearby vehicles to avoid a certain route.In general, a typical VANET setup comprises a trusted authority, some roadside infrastructures and some smart vehicles. VANETs can provide connectivity among vehicles and other Internet-connected entities and devices (e.g., via other local networks or the Internet). For instance, it can realize efficient vehicle-to-vehicle communications in the Internet Transportation System (ITS) [1], and so on.Two kinds of communication modes are included in a typical VANET (see also Figure1), namely, vehicle-to-vehicle (V2V) communication and vehicle-to-infrastructure (V2I) communication. Since the increasing devices and electronic products around us are digitalized and Internet-connected, vehicle to everything(V2X) security has been an essential security attribute in our daily life [2].Figure 1
A typical VANET setup.In VANETs, communication channels between vehicles and nearby roadside infrastructures are usually established using dedicated short-range communication (DSRC) protocols [3]. By using these channels, a vehicle can transmit messages, such as traffic information or conditions, to nearby vehicles and roadside infrastructures at a uniform time period. Such information can be used by drivers to plan, revise, and optimize their routes. Depending on a city’s connectivity level, local traffic control center (a trusted authority) may be able to reroute traffic, make certain adjustments to improve the traffic flow, and hence reduce traffic build up.As more vehicles and devices join the network, there are operational challenges, for example, to deal with latency (e.g., communication delay) and minimize computational costs. It is known that computing capability of smart vehicles and roadside units usually is limited in comparison to other computationally powerful devices such as a dedicated laptop or server. In time-critical application such as VANETs within a smart city, a large volume of traffic and other related information may need to be handled in time for making accurate traffic decision and timely instructions. In addition, messages exchanged between the different entities (e.g., vehicles and/or devices) in the VANETs can be sensitive and private. Hence, security and privacy are both two key properties. However, due to the open nature of VANETs, an adversary can easily obtain sensitive user messages through various attacks such as replay, masquerading, impersonation, and password guessing. The leakage of such messages may have real-world consequences, such as facilitating the planning and execution of a kidnapping or assassination attempt.Therefore, one fundamental design feature is to build a fast and secure communication channel between the different entities in a VANET, such as using two-party authenticated key agreement (2PAKA) protocols or group authenticated key agreement protocols. Specifically, in VANETs, a reliable 2PAKA protocol can help two communication entities to realize mutual authentication and get a valid session key. Unsurprisingly, a large number of 2PAKA protocols have been proposed to facilitate secure message exchange in VANETs. Simultaneously, such protocols are broadly divided into public key infrastructure (PKI)-based 2PAKA protocols, identity (ID)-based 2PAKA protocols, and certificateless 2PAKA protocols (i.e., based on how public keys are generated in these protocols). One limitation associated with PKI-based protocols is the surprising cost incurred in maintaining, issuing, and authenticating a large number of certificates. To mitigate such a limitation, we could use 2PAKA protocol based on identity-based cryptography (IBC) [4–11]. While ID-based 2PAKA protocols, such as those presented in [5–7], could overcome certain shortcomings associated with PKI-based 2PAKA protocols, bilinear pairing used in these protocols makes them unrealistic for deployment on lightweight devices. Hence, to overcome inefficiency caused by bilinear pairing, Zhu et al. [12] presented an ID-based 2PAKA protocol including no pairings in 2007. Nevertheless, the protocol suffers from limitations, such as the requirement for significant bandwidth. In recent times, we can find that a large number of similar protocols have been designed in the literature. However, most of these protocols provide no security proof, use a weak model to prove safety, take more than two communication rounds, or are found to be insecure. Based on gap Diffie–Hellman assumption, for example, Dang et al. [13] designed a two-round ID-based 2PAKA protocol in 2018, which has security proof in the eCK model. However, we reveal in this paper that their protocol could suffer from the man-in-the-middle attack, contrary to their claim. In our paper, we will build on their work and introduce a two-round ID-based 2PAKA protocol. We demonstrate that our protocol requires less computation and communication costs, in comparison to the protocol of Dang et al. [13].The key properties of our proposed protocol are summarized as below:(1)
Mutual authentication of the two parties and negotiation of the session key can be realized by our ID-based two-party AKA protocol.(2)
We show our protocol can get strong security in the eCK model, unlike most other existing protocols.(3)
The proposed protocol is two-round and pairing-free. Hence, it is more superior to other competing protocols in terms of performance.The rest of this paper is organized as follows. Some related works on ID-based 2PAKA protocol and background materials (i.e., mathematical assumptions and security attributes relating to ID-based AKA protocols) are introduced in Sections2 and 3, respectively. Our new ID-based 2PAKA protocol is shown in Section 4. In Sections 5 and 6, we demonstrate the security of the protocol in the eCK model and give out the corresponding performance analysis. A comparative summary of the performance between the proposed protocol and the ID-based 2PAKA protocols of [13, 14] is also presented in Section 6. In the end, the last section shows our paper’s conclusion.


## 2. Related Work

This section mainly shows some related works on the ID-based two-party AKA protocols. At first, we divide these protocols into two types: ID-based 2PAKA protocols with pairings and ID-based 2PAKA protocols without bilinear functions [15, 16]. Next, we respectively review the related works about the two different types of protocols:


### 2.1. ID-Based 2PAKA Protocols with Pairings

The first key agreement protocol employing pairings was presented by Joux [17] in 2000. Then Boneh and Franklin used bilinear pairing to construct the first ID-based encryption scheme in 2001 [18]. After Boneh and Franklin’s work, a lot of ID-based authenticated key agreement protocols with pairings have been presented. According to this ID-based encryption scheme, the first ID-based 2PAKA protocol with pairings was presented by Smart [4]. Unfortunately, Shim [19] found that the protocol presented by Smart [4] had some security flaws and constructed another one ID-based 2PAKA protocol with stronger security, which had lesser quantity of bilinear pairings. In Shim’s protocol [19], only one Weil pairing and scalar multiplication were used in the computation of session key. Meanwhile, Shim declared that his protocol could resist the general attacks. However, the protocol of Shim [20] was shown that it suffers from man-in-the-middle attack in the paper of Hsieh [19].


### 2.2. ID-Based 2PAKA Protocols without Bilinear Pairing Operations

To eliminate efficiency flaw in ID-based 2PAKA protocols with pairings, all kinds of ID-based 2PAKA protocols using no bilinear functions have been presented in the last decade. In 2007, the first ID-based 2PAKA protocol using no bilinear operations was presented by Zhu et al. [12] based on an ID-based signature scheme. Nevertheless, their protocol was still inefficient and needed three message exchanges. To reduce communication traffic, Fiore and Gennaro [21] used exponentiation operation to make an ID-based 2PAKA protocol in 2010. Besides, this protocol’s security was proved by them in the CK model. But this weak security model could not describe the ability of real adversary well. In the same year, Cao et al. [22] proposed a new ID-based 2PAKA protocol employing no pairings to reduce message exchange. Unfortunately, Cao et al.’s protocol was vulnerable to ephemeral key revealed attack. After Cao et al.’s work, lots of ID-based 2PAKA protocols using no bilinear functions were proposed, but these protocols still could not deal with the efficiency problem and security issue effectively.But because ID-based 2PAKA protocol without pairings can fit real-time application environment such as VANETs perfectly, cryptologists still put a lot of effort into improving these protocols’ performance and security. Until recently, some responding protocols with better properties have been presented. In 2015, Sun et al. [23] presented an improved 2PAKA protocol based on the identity with security proof in the eCK security model. But disadvantages were that this protocol used six scalar multiplications on elliptic curve and security proof was incomplete because only passive adversary was taken into consideration in the security model. After the Sun et al.’s work, Ni et al. [24] designed other new ID-based 2PAKA protocol that only needed five scalar multiplications in 2016. In addition, it was proved secure in the eCK security model completely. Although this protocol was far more efficient than previously proposed protocols, the communication traffic was still very large. Then, in 2017, an ID-based 2PAKA protocol including no pairings based on the BAN logic model was constructed by Islam and Biswas [25]. Sadly, their protocol was unsafe.


## 2.1. ID-Based 2PAKA Protocols with Pairings

The first key agreement protocol employing pairings was presented by Joux [17] in 2000. Then Boneh and Franklin used bilinear pairing to construct the first ID-based encryption scheme in 2001 [18]. After Boneh and Franklin’s work, a lot of ID-based authenticated key agreement protocols with pairings have been presented. According to this ID-based encryption scheme, the first ID-based 2PAKA protocol with pairings was presented by Smart [4]. Unfortunately, Shim [19] found that the protocol presented by Smart [4] had some security flaws and constructed another one ID-based 2PAKA protocol with stronger security, which had lesser quantity of bilinear pairings. In Shim’s protocol [19], only one Weil pairing and scalar multiplication were used in the computation of session key. Meanwhile, Shim declared that his protocol could resist the general attacks. However, the protocol of Shim [20] was shown that it suffers from man-in-the-middle attack in the paper of Hsieh [19].


## 2.2. ID-Based 2PAKA Protocols without Bilinear Pairing Operations

To eliminate efficiency flaw in ID-based 2PAKA protocols with pairings, all kinds of ID-based 2PAKA protocols using no bilinear functions have been presented in the last decade. In 2007, the first ID-based 2PAKA protocol using no bilinear operations was presented by Zhu et al. [12] based on an ID-based signature scheme. Nevertheless, their protocol was still inefficient and needed three message exchanges. To reduce communication traffic, Fiore and Gennaro [21] used exponentiation operation to make an ID-based 2PAKA protocol in 2010. Besides, this protocol’s security was proved by them in the CK model. But this weak security model could not describe the ability of real adversary well. In the same year, Cao et al. [22] proposed a new ID-based 2PAKA protocol employing no pairings to reduce message exchange. Unfortunately, Cao et al.’s protocol was vulnerable to ephemeral key revealed attack. After Cao et al.’s work, lots of ID-based 2PAKA protocols using no bilinear functions were proposed, but these protocols still could not deal with the efficiency problem and security issue effectively.But because ID-based 2PAKA protocol without pairings can fit real-time application environment such as VANETs perfectly, cryptologists still put a lot of effort into improving these protocols’ performance and security. Until recently, some responding protocols with better properties have been presented. In 2015, Sun et al. [23] presented an improved 2PAKA protocol based on the identity with security proof in the eCK security model. But disadvantages were that this protocol used six scalar multiplications on elliptic curve and security proof was incomplete because only passive adversary was taken into consideration in the security model. After the Sun et al.’s work, Ni et al. [24] designed other new ID-based 2PAKA protocol that only needed five scalar multiplications in 2016. In addition, it was proved secure in the eCK security model completely. Although this protocol was far more efficient than previously proposed protocols, the communication traffic was still very large. Then, in 2017, an ID-based 2PAKA protocol including no pairings based on the BAN logic model was constructed by Islam and Biswas [25]. Sadly, their protocol was unsafe.


## 3. Preliminaries

In this section, we show several difficult mathematical problems and indispensable security attributes in the ID-based AKA protocol.


### 3.1. Mathematical Assumptions

The following difficult mathematical problems are some basic tools used to analyze the security of AKA protocol.We assume thatq is the order for a finite cyclic additive group G, where q is a big prime number. Meanwhile, G has a generator P.


#### 3.1.1. Elliptic Curve Discrete Logarithm (ECDL) Problem

Given two elementsP,Q∈G, it is hard to calculate a value a∈ℤp∗ such that Q=aP for any adversary in probability polynomial time.


#### 3.1.2. Gap Diffie–Hellman (GDH) Problem

Given three points (P,aP,bP) and a DDH oracle, for any probability polynomial time algorithm, the advantage of making the calculation of abP can be ignored, where a,b∈ℤp∗ are unknown.


#### 3.1.3. Decisional Diffie–Hellman (DDH) Problem

For unknowna,b,c∈ℤp∗, if an adversary is given P,aP,bP,cP∈G, it is still difficult to determine whether c=abmodq or not.


#### 3.1.4. Computational Diffie–Hellman (CDH) Problem

The numbersa,b∈ℤp∗ are unknown. Knowing three points P,aP,bP∈G, it is also impossible to compute abP by any PTT algorithm.


### 3.2. Essential Security Attributes

If an AKA protocol is safe and reliable, it must have some essential security attributes, because these security attributes show that the proposed protocol is capable of resisting corresponding attacks. So security attribute is an important index to measure quality of a protocol. The following security attributes are some basic conditions that a secure ID-based 2PAKA protocol needs to meet [26–28].


#### 3.2.1. Known-Key Security (K-SKS)

Even though the adversary has known a protocol’s all previous session keys, this protocol can still keep the current session key secure.


#### 3.2.2. Forward Secrecy (FS)

The leakage of users’ long-term private keys has no impact on the security of preceding session keys. Generally, forward secrecy mainly includes the following two different categories:(1)
Partial forward secrecy. Even though the adversary has known some users’ long-term secret keys, session keys made in preceding sessions still can keep safe.(2)
Perfect forward secrecy. For any probability polynomial time adversary, learning all long-term secrets has little help to make session keys known.


#### 3.2.3. Key Compromise Impersonation (KCI) Resistance

Even though an adversary knows entity A’s long-term private key, he still cannot masquerade as any other user to A.


#### 3.2.4. Unknown Key Share (UKS) Resistance

An adversary makes a group of users believe that they are sharing a secret with him. Actually, this secret should be shared by them and another user (e.g., B holds the viewpoint that a session key is established by itself and an adversary E. In fact, this key is generated by A and B together).


#### 3.2.5. No Key Control (NKC)

No entity can enforce a session key to be preselected or predetermined.


#### 3.2.6. Basic Impersonation (BI) Resistance

If a party A’s long-term secret key is leaked to an adversary, he can make full use of this key to disguise himself as A.


#### 3.2.7. Ephemeral Key Reveal (EKR) Resistance

Even if an adversary acquires the ephemeral private keys of all participants in a session, the session key is kept private as before.


## 3.1. Mathematical Assumptions

The following difficult mathematical problems are some basic tools used to analyze the security of AKA protocol.We assume thatq is the order for a finite cyclic additive group G, where q is a big prime number. Meanwhile, G has a generator P.


### 3.1.1. Elliptic Curve Discrete Logarithm (ECDL) Problem

Given two elementsP,Q∈G, it is hard to calculate a value a∈ℤp∗ such that Q=aP for any adversary in probability polynomial time.


### 3.1.2. Gap Diffie–Hellman (GDH) Problem

Given three points (P,aP,bP) and a DDH oracle, for any probability polynomial time algorithm, the advantage of making the calculation of abP can be ignored, where a,b∈ℤp∗ are unknown.


### 3.1.3. Decisional Diffie–Hellman (DDH) Problem

For unknowna,b,c∈ℤp∗, if an adversary is given P,aP,bP,cP∈G, it is still difficult to determine whether c=abmodq or not.


### 3.1.4. Computational Diffie–Hellman (CDH) Problem

The numbersa,b∈ℤp∗ are unknown. Knowing three points P,aP,bP∈G, it is also impossible to compute abP by any PTT algorithm.


## 3.1.1. Elliptic Curve Discrete Logarithm (ECDL) Problem

Given two elementsP,Q∈G, it is hard to calculate a value a∈ℤp∗ such that Q=aP for any adversary in probability polynomial time.


## 3.1.2. Gap Diffie–Hellman (GDH) Problem

Given three points (P,aP,bP) and a DDH oracle, for any probability polynomial time algorithm, the advantage of making the calculation of abP can be ignored, where a,b∈ℤp∗ are unknown.


## 3.1.3. Decisional Diffie–Hellman (DDH) Problem

For unknowna,b,c∈ℤp∗, if an adversary is given P,aP,bP,cP∈G, it is still difficult to determine whether c=abmodq or not.


## 3.1.4. Computational Diffie–Hellman (CDH) Problem

The numbersa,b∈ℤp∗ are unknown. Knowing three points P,aP,bP∈G, it is also impossible to compute abP by any PTT algorithm.


## 3.2. Essential Security Attributes

If an AKA protocol is safe and reliable, it must have some essential security attributes, because these security attributes show that the proposed protocol is capable of resisting corresponding attacks. So security attribute is an important index to measure quality of a protocol. The following security attributes are some basic conditions that a secure ID-based 2PAKA protocol needs to meet [26–28].


### 3.2.1. Known-Key Security (K-SKS)

Even though the adversary has known a protocol’s all previous session keys, this protocol can still keep the current session key secure.


### 3.2.2. Forward Secrecy (FS)

The leakage of users’ long-term private keys has no impact on the security of preceding session keys. Generally, forward secrecy mainly includes the following two different categories:(1)
Partial forward secrecy. Even though the adversary has known some users’ long-term secret keys, session keys made in preceding sessions still can keep safe.(2)
Perfect forward secrecy. For any probability polynomial time adversary, learning all long-term secrets has little help to make session keys known.


### 3.2.3. Key Compromise Impersonation (KCI) Resistance

Even though an adversary knows entity A’s long-term private key, he still cannot masquerade as any other user to A.


### 3.2.4. Unknown Key Share (UKS) Resistance

An adversary makes a group of users believe that they are sharing a secret with him. Actually, this secret should be shared by them and another user (e.g., B holds the viewpoint that a session key is established by itself and an adversary E. In fact, this key is generated by A and B together).


### 3.2.5. No Key Control (NKC)

No entity can enforce a session key to be preselected or predetermined.


### 3.2.6. Basic Impersonation (BI) Resistance

If a party A’s long-term secret key is leaked to an adversary, he can make full use of this key to disguise himself as A.


### 3.2.7. Ephemeral Key Reveal (EKR) Resistance

Even if an adversary acquires the ephemeral private keys of all participants in a session, the session key is kept private as before.


## 3.2.1. Known-Key Security (K-SKS)

Even though the adversary has known a protocol’s all previous session keys, this protocol can still keep the current session key secure.


## 3.2.2. Forward Secrecy (FS)

The leakage of users’ long-term private keys has no impact on the security of preceding session keys. Generally, forward secrecy mainly includes the following two different categories:(1)
Partial forward secrecy. Even though the adversary has known some users’ long-term secret keys, session keys made in preceding sessions still can keep safe.(2)
Perfect forward secrecy. For any probability polynomial time adversary, learning all long-term secrets has little help to make session keys known.


## 3.2.3. Key Compromise Impersonation (KCI) Resistance

Even though an adversary knows entity A’s long-term private key, he still cannot masquerade as any other user to A.


## 3.2.4. Unknown Key Share (UKS) Resistance

An adversary makes a group of users believe that they are sharing a secret with him. Actually, this secret should be shared by them and another user (e.g., B holds the viewpoint that a session key is established by itself and an adversary E. In fact, this key is generated by A and B together).


## 3.2.5. No Key Control (NKC)

No entity can enforce a session key to be preselected or predetermined.


## 3.2.6. Basic Impersonation (BI) Resistance

If a party A’s long-term secret key is leaked to an adversary, he can make full use of this key to disguise himself as A.


## 3.2.7. Ephemeral Key Reveal (EKR) Resistance

Even if an adversary acquires the ephemeral private keys of all participants in a session, the session key is kept private as before.


## 4. Our Presented Protocol

We describe our ID-based two-round 2PAKA protocolΠ without bilinear pairings in this section. There are three main algorithms included in this protocol Π, namely, setup algorithm, key generation algorithm, and key agreement algorithm. In our protocol, it is worth noting that the trusted authority plays the role of KGC.


### 4.1. Setup Phase

At this stage, all vital system parameters are generated by the trusted authority performing this setup algorithm with security parameterk. The specific implementation steps are as follows:(1)
Chooses one additive groupG with a generator P. Meanwhile, p is a prime order of G(2)
Selects randomly a numbers∈ℤp∗ as KGC’s private key, and then calculates Ppub=sP as its public key(3)
Picks three high-efficiency hash functions, whereh1:0,1∗×G⟶ℤp∗, h2:G⟶ℤp∗, and H3:0,1∗×0,1∗×G×G×G⟶0,1k(4)
Makesparams=G,p,P,Ppub,h1,h2,H3 public information and preserves the confidentiality of key s


### 4.2. Extract Key Phase

Here, we always suppose every vehicle has its ownIDi∈0,1∗. The trusted authority (acts as KGC) uses the Schnorr signature algorithm to compute these vehicles’ long-term private keys. Besides, the trusted authority distributes these key pairs to the corresponding vehicles. The trusted authority does as below:(1)
Picks randomly a numberri∈ℤp∗ for each vehicle, and then does calculations about Ri=riP and hi=h1IDi,Ri.(2)
Calculatessi=ri+hismodp and a vehicle’s long-term secret key actually is (si,Ri).(3)
The corresponding vehicle could receive this pair (si,Ri) sent by using a secure channel. Then, the vehicle can check the validity of its long-term private key after receiving the pair because they can verify whether the equation siP=Ri+h1IDi,RiPpub is satisfied or not. If it passes, the vehicle sets PKi=siP as its long-term public key.


### 4.3. Key Agreement Phase

After the extract key phase, two vehicles A and B have their own key pair (si,Ri) and relevant IDi. Now, A and B want to establish a session key through mutual communication, which is used to keep latter data secure. Our new protocol is displayed in Figure 2.(1)
Firstly, the ephemeral private keya∈ℤp∗ of vehicle A is randomly chosen, and its ephemeral public key is set as TA=aP. Then, A sends IDA,RA,andTA to vehicle B:(1)A⟶B:IDA,RA,TA.(2)
Meanwhile, a random valueb∈ℤp∗ is selected as vehicle B’s ephemeral private key, similarly. Then, B also computes TB=bP as the ephemeral public key. B transmits IDB,RB,andTB to A:(2)B⟶A:IDB,RB,TB.(3)
After receiving messages from B, A can calculatePKB=RB+h1IDB,RBPpub and SKA=h2sAPKBaTB. So, A can compute the session key skAB=H3IDA,IDB,SKA,aPKB,sATB.(4)
In the same way, when B gets data that A sends, vehicle B can computePKA=RA+h1IDA,RAPpub and SKB=h2sBPKAbTA. B can also calculate the session key skBA=H3IDA,IDB,SKB,bPKA,sBTA.Figure 2
The key agreement phase.Correctness. The correctness of our protocol is shown as below:(3)SKA=h2sAPKBaTB=h2sA⋅sB⋅Pa⋅b⋅P=h2sBPKAbTA=SKB,aPKB=a⋅sB⋅P=sBTA,sATB=sA⋅b⋅P=bPKA.


## 4.1. Setup Phase

At this stage, all vital system parameters are generated by the trusted authority performing this setup algorithm with security parameterk. The specific implementation steps are as follows:(1)
Chooses one additive groupG with a generator P. Meanwhile, p is a prime order of G(2)
Selects randomly a numbers∈ℤp∗ as KGC’s private key, and then calculates Ppub=sP as its public key(3)
Picks three high-efficiency hash functions, whereh1:0,1∗×G⟶ℤp∗, h2:G⟶ℤp∗, and H3:0,1∗×0,1∗×G×G×G⟶0,1k(4)
Makesparams=G,p,P,Ppub,h1,h2,H3 public information and preserves the confidentiality of key s


## 4.2. Extract Key Phase

Here, we always suppose every vehicle has its ownIDi∈0,1∗. The trusted authority (acts as KGC) uses the Schnorr signature algorithm to compute these vehicles’ long-term private keys. Besides, the trusted authority distributes these key pairs to the corresponding vehicles. The trusted authority does as below:(1)
Picks randomly a numberri∈ℤp∗ for each vehicle, and then does calculations about Ri=riP and hi=h1IDi,Ri.(2)
Calculatessi=ri+hismodp and a vehicle’s long-term secret key actually is (si,Ri).(3)
The corresponding vehicle could receive this pair (si,Ri) sent by using a secure channel. Then, the vehicle can check the validity of its long-term private key after receiving the pair because they can verify whether the equation siP=Ri+h1IDi,RiPpub is satisfied or not. If it passes, the vehicle sets PKi=siP as its long-term public key.


## 4.3. Key Agreement Phase

After the extract key phase, two vehicles A and B have their own key pair (si,Ri) and relevant IDi. Now, A and B want to establish a session key through mutual communication, which is used to keep latter data secure. Our new protocol is displayed in Figure 2.(1)
Firstly, the ephemeral private keya∈ℤp∗ of vehicle A is randomly chosen, and its ephemeral public key is set as TA=aP. Then, A sends IDA,RA,andTA to vehicle B:(1)A⟶B:IDA,RA,TA.(2)
Meanwhile, a random valueb∈ℤp∗ is selected as vehicle B’s ephemeral private key, similarly. Then, B also computes TB=bP as the ephemeral public key. B transmits IDB,RB,andTB to A:(2)B⟶A:IDB,RB,TB.(3)
After receiving messages from B, A can calculatePKB=RB+h1IDB,RBPpub and SKA=h2sAPKBaTB. So, A can compute the session key skAB=H3IDA,IDB,SKA,aPKB,sATB.(4)
In the same way, when B gets data that A sends, vehicle B can computePKA=RA+h1IDA,RAPpub and SKB=h2sBPKAbTA. B can also calculate the session key skBA=H3IDA,IDB,SKB,bPKA,sBTA.Figure 2
The key agreement phase.Correctness. The correctness of our protocol is shown as below:(3)SKA=h2sAPKBaTB=h2sA⋅sB⋅Pa⋅b⋅P=h2sBPKAbTA=SKB,aPKB=a⋅sB⋅P=sBTA,sATB=sA⋅b⋅P=bPKA.


## 5. Security Analysis

In the following content, the security of our protocolΠ is displayed in detail. Firstly, it is necessary to give out the eCK security model that we use in our protocol. After that, we give the security proof and some security attributes of our protocol in detail.


### 5.1. Protocol Participants

There is a setU that is composed of all protocol participants. Every party in set U has a unique IDi and corresponding private and public key pair (si,PKi). Besides, PKi is relative with its IDi and si always is generated by the trusted authority (acts as KGC). In security proof, the ability of each participant is usually described by a probability polynomial time (PPT) algorithm. We consider that a polynomial number of sessions are the maximum value that every participant can take part in at the same time. Furthermore, the sth session of party IDA is denoted as ΠA,Bs that is established by party IDA and party IDB. If A finally gets a valid session key by communicating with B, we think participant A completes the session ΠA,Bs.


### 5.2. eCK Model

Without loss of generality, an adversary C always is deemed as a PPT algorithm in the security model. Moreover, C is considered to have the ability to control the whole communication network. It means messages may be arbitrarily replayed, eavesdropped, modified, suspended, and injected by the adversary. The ability of an adversary C always is described through a series of queries. Here, we only give out the simple information about the eCK model, and more details can be found in the literature of Huang and Cao [29].(i)
EphemeraKeyReveal(ΠA,Bs). Adversary C can get the ephemeral private key of protocol participant IDA in session ΠA,Bs.(ii)
SessionKeyReveal(ΠA,Bs). If session ΠA,Bs is completed, adversary C can obtain the session key. Otherwise, a null value will be returned to C.(iii)
StaticKeyReveal(IDA). Adversary C could obtain IDA’s long-term private key sent by this query. But C cannot control IDA completely.(iv)
PKGstaticKeyReveal. The adversary can know PKG’s master private key by this query. This query usually simulates PKG-FS.(v)
EstablishParty(IDA). After requesting this query, a legitimate user IDA can be registered. But the adversary can acquire IDA’s private key. In addition, party IDA is considered to be dishonest.(vi)
Send(ΠA,Bs,M). A message M is transmitted to ΠA,Bs by adversary C. After receiving this message, ΠA,Bs responds to the message according to the protocol regulation. If M is null, this session ΠA,Bs will initiate a session as an initiator. Otherwise, it will be a responder.(vii)
Test(ΠA,Bs). This query usually takes place during the experiment. The adversary C can make this query to a finished fresh session ΠA,Bs only once. The session picks a random value b∈0,1 when getting a test query from the adversary C. If b=1, this session ΠA,Bs returns session key to C. Otherwise, a random number that is indistinguishable from the session key will be given to adversary C.Definition 1 (matching session).
If the sessionsΠA,Bs and ΠB,At have the same session identifier SID, they will be each other’s matching session. SID is a series connection of a session participant’s messages in the order of initiator or responder.Definition 2 (fresh session).
TheΠA,Bs is a fresh session executed by two honest parties IDA and IDB, if none of the following conditions is satisfied.(1)
The sessionΠA,Bs has a matching session ΠB,At. Additionally, a session key of ΠA,Bs or ΠB,At is leaked to adversary C.(2)
Assume that sessionΠA,Bs has a matching session ΠB,At. Besides, all of IDA’s secret keys in ΠA,Bs or the long-term and temporary secret keys of IDB in ΠB,At are revealed to adversary C.(3)
There is no matching session aboutΠA,Bs, but an adversary knows the long-term and ephemeral private keys of IDA in ΠA,Bs or the long-term secret key of IDB.Definition 3 (ID-eCK security).
For adversary C,succ denotes the event that adversary C can know b’s correct value in the manner of sending a Test query to some fresh instances. Therefore, the advantage of adversary C is advAKEC=2Prsucc−1. If a 2PAKA protocol can satisfy the following conditions, this protocol is considered to be ID-eCK security.(1)
For any PPT adversary, the success probability of knowing the rightb is negligible. It means that advAKEC=2Prsucc−1 is a negligible value.(2)
After two honest parties complete a session, they can get the same session key.


### 5.3. Formal Proof

Firstly, our protocol will be proved to have strong enough security in this section. Then, we will show some security attributes that our protocol has.Theorem 1.
AssumeH1, H2, and H3 are three random oracles in the eCK model. According to the difficult GDH problem, no adversary can break the security of protocol Π in polynomial time.Proof.
On the basis of ID-eCK security, we know the two properties inDefinition3 are the basic conditions that a secure AKA protocol should satisfy. We can know the second condition is met in the correctness of our protocol. Next, we show that the first condition also can be met in the following content. In the eCK security model, our protocol Π’s security parameter is specified as k. Meanwhile, the maximum value of truthful users activated by an adversary is nk. The symbol qsk is the maximum number of sessions that each party can take part in. Besides, it is also an assumed condition that the test session selected by adversary C is ΠA,Bs, which is established by IDA and IDB together. Adversary C can only use the following three methods to get the correct value of test session key.(1)
Guessing directly attack. Adversary C can know test session key in a guessing way.(2)
Key replication attack. Adversary C constructs another session that is not a matching session of the test session. But its session key is same with the test session. Hence, adversary C can make the use of a nonmatching session to acquire the test session key. Namely, it means that this protocol cannot stand up to adversary C’s attack.(3)
Forging attack. Adversary C can query H3 random oracle with the input IDA,IDB,TA,TB,SKA,aPKB,andsATB. Obviously, the adversary C calculates the value SKA,aPKB,andsATB by itself.
Becausek is security parameter, it indicates that the size of session key is k bit. Therefore, the guessing directly attack is successful with probability O1/2k. Besides, the role of H3 is the same as a random oracle in the security model. If this random oracle produces no collisions, the event that a session key is jointly owned by two nonmatching sessions occurs with a negligible probability because two nonmatching sessions cannot have the same SID under the definition of matching session. Namely, key replication attack’s successful probability is negligible. Consequently, we only need to consider about the successful probability of the forging attack.
Before we analyze a forging attack in detail, we firstly review the GDH problem. This mathematical assumption is that the valueX=xP,Y=yP is given, where x,y∈Rℤp∗ is unknown, the aim of challenger S is to get the result of GDHX,Y=xyP by using a DDH oracle. Then, a challenger S plays the ID-eCK game with the adversary C who can break the protocol Π. During the game, S must make responses to all kinds of queries of the adversary C. If the adversary C can make a successful forging attack with non-negligible probability, the challenger S can construct a gap Diffie–Hellman solver by using C as a subroutine. As fresh definition shown in the eCK model, we need to consider about two special cases:(1)
The sessionΠB,At is the matching session of the test session ΠA,Bs(2)
There is no corresponding session matching with the sessionΠA,Bs
In the first scenario, we only consider about passive adversary who cannot change messages transmitted among all parties. Contrary to the first scenario, challenger S has an active adversary that could modify the partyIDB’s long-term secret key element RB in the second scenario. Above analysis results show that the adversary can adopt different attack strategies. So before the challenger S plays game with the adversary C, S can ensure C’s test session is ΠA,Bs with probability 1/nk2qsk. In addition, S must guess the attack way that the adversary could choose from the following six strategies:(i)
Case 1. IDB’s long-term secret key and IDA’s temporary private key are not leaked to adversary C. Meanwhile, C transmits RB correctly.(ii)
Case 2. The long-term secret keys of IDA and IDB are not known by C. The value of RB still is not modified by C.(iii)
Case 3. The temporary private keys of IDA and IDB are not revealed to adversary C.(iv)
Case 4. IDB’s temporary private key and the long-term secret key of IDA are not acquired by adversary C.(v)
Case 5. Adversary C does not get the long-term secret key of IDB and IDA’s temporary private key. But the value of RB is changed by C.(vi)
Case 6. Adversary C knows nothing about long-term secret keys of IDA and IDB. But C alters RB’s real value.
Obviously, the six cases above cover all attack manners of different adversaries, including the passive adversary and the active adversary. On the basis of the above result, the correct test session and strategy are chosen by challenger S with the probability1/6nk2qsk.Case 1.
ID
B’s long-term secret key and IDA’s temporary private key are not leaked to adversary C. Meanwhile, C correctly transmits RB.(i) Setup.
The challenger S initializes the long-term keys of all parties and KGC’s public key as follows:(1)
The challenger S chooses the valuePpub∈G at random as the KGC’s public key.(2)
Challenger S randomly chooseshB∈ℤp∗ as H1IDB,RB and calculates RB=Y−hBPpub. So we can know PKB=RB+hBPpub=Y is the long-term public key of IDB. IDB can get its long-term secret key’s value Δ,RB.(3)
For other partiesIDi, the challenger S randomly selects hi,si∈ℤp∗ as H1IDi,Ri and long-term private key. Similarly, the challenger can compute Ri=siP−hiPpub. Therefore, PKi=Ri+hiPpub=siP is IDi’s long-term public key.After the above process, for eachIDi, the challenger passes IDi,Ri to the adversary C and this new entry IDi,Ri,hi is added to H1list.(ii) Queries.
In order to deal withH1, H2, H3, and SessionKeyReveal queries from C, the challenger first maintains the corresponding empty lists H1list, H2list, H3list, and Rlist. Then, the challenger S responds to all queries from C as below:(1)
H1IDi,Ri. In the setup phase, when the long-term secret key of each party IDi is set, S inserts the entry IDi,Ri,hi to H1list. When a query about H1 sent by adversary C already exists in H1list, S returns the corresponding entry to C. Otherwise, S selects randomly hi∈ℤp∗ and adds the new entry IDi,Ri,hi to the list H1list. Then, S returns the random value hi.(2)
H2siPKj. When C launches an H2 query, S first searches for the relevant entry in the whole list H2list. If S finds the entry out, S transmits h2 to C. Conversely, S computes si∗PKj and checks whether this value is already in H2list or not. If the H2list has the corresponding value, the challenger gives h2 to C. Otherwise, S chooses h2∈ℤp∗ at random. Then, S inserts the entry si,PKj,siPKj,h2 to H2list and returns h2 to the adversary C.(3)
H3IDi,IDj,Ti,Tj,SK,aiPKj,siTj. Before this query, S keeps an empty table H3list whose entries are the form of IDi,IDj,Ti,Tj,SK,aiPKj,siTj,h3.(i)
If the corresponding entry is found inH3list, the challenger S responds to the query with h3.(ii)
Otherwise, S checks the whole listRlist. If i has a correct value B and target item is stored, S uses the DDH oracle to verify whether DDHH2sjPKiTj,Ti,SK=DDHh2Tj,Ti,SK=1, DDHTi,PKj,aiPKj=1, and DDHPKi,Tj,siTj=1. If all of them are right, S sets h3=skij and stores the entry IDi,IDj,Ti,Tj,SK,aiPKj,siTj,h3 to H3list. If the entry is found in the list and i≠B, the equation h3=skij is made by challenger S and the relevant item is added to H3list. But if the list H3list has not the corresponding entry or the verifications of DDH oracle are wrong, S randomly selects h3∈0,1k and writes these new data into the list H3list. In final, S returns the corresponding h3 to the adversary C.(4)
EphemeralKeyReveal(Πi,js). If the session Πi,js is ΠA,Bs, the challenger S aborts. Otherwise, the temporary private key of IDi is sent to S by adversary C.(5)
StaticKeyReveal(IDi). If i = B, S aborts. Otherwise, the challenger provides C with si,Ri.(6)
MasterPrivateKeyReveal(). The challenger S aborts.(7)
EstablishParty(IDi). For this query, the challenger S chooses si,hi∈ℤp∗ at random. Then S assigns the value of H1IDi,Ri to hi and calculates Ri=siP−hiPpub. Finally, S sends si,Ri to C as its long-term secret key. Therefore, the adversary C can control IDi completely, it is because the long-term secret key of IDi is known by C.(8)
SessionKeyReveal(Πi,js). If the session Πi,js is ΠA,Bs or ΠB,At, S aborts. Otherwise, S searches for the value sij in the whole list Rlist and sends it to C.(9)
Send(Πi,js, M). A blank table Rlist is held by S whose element is IDi,IDj,Ti,Tj,skij for the Send query.(i)
IfΠi,js is ΠA,Bs and M=Δ, adversary C receives X returned by challenger S.(ii)
If the value ofi is B and M=W, S selects b∈ℤp∗ at random and returns the bP to C. Besides, S verifies whether DDHH2sjPKiTj,Ti,SK=DDHh2Tj,bP,SK=1, DDHTi,PKj,aiPKj=1, and DDHPKi,Tj,siTj=1. If SK, aiPKj, and siTj are correct, S sets skij=h3 and inserts the entry IDi,IDj,Ti,Tj,skij to the list Rlist. But if the list H3list does not have the entry or one of SK, aiPKj, and siTj is wrong, S chooses randomly skij∈0,1k and writes new information to Rlist.(iii)
If B is not the correct value fori, S answers this Send query according to protocol rule.(10)
Test(Πi,js). If the session Πi,js is ΠA,Bs, S chooses randomly β∈0,1k and this data is returned to adversary C. On the contrary, S is not playing this game.(iii) Analysis.
If a forgery attack is successfully launched by adversary C with great probability, C must have usedSK=H2sAYDLOGXbP, aiPKB=DLOGXY, and sATB=sAbP to query H3 random oracle. To cope with the GDHX,Y difficult problem, challenger S checks whether the value of an H3 query from C is IDi,IDj,Ti,Tj,SK,aiPKj,siTj such that DDHH2sjPKiTj,Ti,SK=DDHh2Tj,bP,SK=1, DDHTi,PKj,aiPKj=1, and DDHPKi,Tj,siTj=1. If this H3 query is found, S computes GDHX,Y=DLOGXY=aAPKB using this query. Assume that the probability of the event that a forgery attack is made by adversary C is AdvCΠk, so S successfully deals with the GDH problems with the advantage(4)AdvSGDHk≥AdvCΠk6nk2qsk.Case 2.
The long-term secret keys ofIDA and IDB are not known by C. The value of RB still is not modified by C.(i) Setup.
All parties’ long-term secret keys and KGC’s public key are given by challenger C as follows:(1)
Ppub∈G selected by the challenger S is assigned to KGC’s public key.(2)
As forIDA, a random value hA∈ℤp∗ is selected by S as the value of H1IDA,RA. Then, S does the calculation on RA=X−hAPpub and IDA’s long-term secret key is given the value Δ,RA. Thus, X is relevant public key of IDA.(3)
Using the same method, S selectshB∈ℤp∗ at random as H1IDB,RB for the party IDB and calculates RB=Y−hBPpub. So IDB’s long-term secret key can be assigned to the value Δ,RB. Additionally, IDB’s corresponding public key is PKB=RB+hBPpub=Y.(4)
Considering about other partiesIDi, where i≠A and i≠B, challenger S randomly chooses hi,si∈ℤp∗. Similarly, S sets hi=H1IDi,Ri and computes the relevant value of Ri=siP−hiPpub. Thus, the long-term secret key of entry IDi is si,Ri. Its public key is PKi=Ri+hiPpub. S sends IDi,Ri to the adversary C, and this new entry IDi,Ri,hi is inserted into the table H1list.(ii) Queries.
To deal with the query about SessionKeyReveal and three hash queriesH1, H2, and H3, challenger S stores four tables Rlist and H1list, H2list, H3list. And S uses the following ways to answer those queries asked by C.(1)
H3IDi,IDj,Ti,Tj,SK,aiPKj,siTj. S has an empty list H3list in the form of IDi,IDj,Ti,Tj,SK,aiPKj,siTj,h3.(i)
IfH3list already has the relevant entry IDi,IDj,Ti,Tj,SK,aiPKj,siTj,h3, S returns h3 to the adversary C.(ii)
If not, S looks up target item in the whole tableRlist. If the item is found and the value of i is A or B, challenger S verifies whether DDHh2Ti,Tj,SK=DDHH2DLOGXYTi,Tj,SK=1, DDHTi,PKj,aiPKj=1, and DDHPKi,Tj,siTj=1. If all of them are correct, S sets h3=skij and stores the new entry into the list H3list. If Rlist has the goal entry (A and B are both not the right value of i), S assigns h3 to skij. Then, S adds the new entry to the list H3list. Otherwise, If the corresponding entry does not exist in the list Rlist or SK, aiPKj and siTj are not right, S chooses h3∈0,1k and inserts IDi,IDj,Ti,Tj,SK,aiPKj,siTj,h3 into the list H3list.(2)
EphemeralKeyReveal(Πi,js). Adversary C acquires temporary secret key of entry IDi returned by S.(3)
StaticKeyReveal(IDi). If A or B is the correct value of i, challenger S terminates this program. Otherwise, si,Ri is transmitted to C.(4)
Send(Πi,js, M). As before, a blank table Rlist is held by S, the form of which is IDi,IDj,Ti,Tj,skij.(i)
Ifi is equal to A, its temporary secret key is a∈ℤp∗ picked up by challenger S at random and the value aP is given to C. Next, S seeks the relevant item in the table H3list. If the entry exists, S checks whether DDHh2Ti,Tj,SK=DDHH2DLOGXYTi,Tj,SK=1, DDHTi,PKj,aiPKj=1, and DDHPKi,Tj,siTj=1. If all of them are right, S sets skij=h3 and stores the new entry to Rlist. But if this corresponding item is not found or three values verified by DDH oracle are not correct, S randomly selects skij∈0,1k and writes new data to Rlist.(ii)
Ifi is equal to B, S uses a similar way in the simulation.(iii)
For other conditions, the challenger S responds according to the protocol specification.It is worth noting that S responds to theH1IDi,Ri, H2siPKj, EstablishParty(IDi), MasterPrivateKey, Session KeyReveal(Πi,js), and Test(Πi,js) in the manner of case 1.(iii) Analysis.
Similarly, if the adversary C makes a successful forging attack with non-negligible probabilityAdvCΠ, C must make the use of SK=H2DLOGXYabP, aAPKB=aY, and sATB=bX to query H3. To deal with GDHX,Y, S checks whether the content of an H3 query from C is IDA,IDB,TA,TB,SK,aY,bX such that DDHh2Ti,Tj,SK=DDHH2DLOGXYTi,Tj,SK=1, DDHTi,PKj,aiPKj=1, and DDHPKi,Tj,siTj=1. If S can find such an H3 query, it computes GDHX,Y=DLOGXY. Therefore, GDH difficult problem can be solved by S successfully with the advantage(5)AdvSGDHk≥AdvCΠk6nk2qsk.Case 3.
The temporary private keys ofIDA and IDB are not revealed to adversary C.(i) Setup.
S assigns the values to all parties’ long-term secret keys and KGC’s master keys as follows.(1)
s∈ℤp∗ is chosen by S as KGC’s master secret key and the challenger S also calculates Ppub=sP. Thus, Ppub is its public key. In fact, case 3 simulates MFS.(2)
For each party, S selectssi,hi∈ℤp∗ at random. S sets hi = H1IDi,Ri and calculates Ri=siP−hiPpub. So IDi’s long-term secret key is si,Ri. Then, S computes PKi=Ri+hiPpub = siP. In the end, S sends IDi,Ri to the adversary C. In addition, IDi,Ri,hi is inserted to the table H1list.(ii) Queries.
As before, S holds four blank tablesH1list, H2list, H3list, and Rlist to cope with corresponding queries. Those queries from C are responded by S in the following ways.(1)
H3IDi,IDj,Ti,Tj,SK,aiPKj,siTj. The challenger S has an empty list H3list in the form of IDi,IDj,Ti,Tj,SK,aiPKj,siTj,h3.(i)
If the listH3list already has the matching entry, S returns h3 to C.(ii)
Otherwise, S checks the whole tableRlist. If the item is found out, S sets h3=skij and puts the new entry into the list H3list. If not, h3∈0,1k is randomly chosen by S and the corresponding data is written into H3list.(2)
StaticKeyReveal(IDi). si,Ri is revealed by S to C.(3)
MasterPrivateKeyReveal. The challenger S responds to this query with s.(4)
EphemeralKeyReveal(Πi,js). If Πi,js is ΠA,Bs or ΠB,At, S aborts. Otherwise, S returns the ephemeral key of IDi to C.(5)
Send(Πi,js, M). S maintains an empty list Rlist in the form of IDi,IDj,Ti,Tj,skij.(i)
IfΠi,js = ΠA,Bs, S returns X to C.(ii)
IfΠi,js = ΠB,At, S returns Y to C. Then, S searches for the relevant entry in H3list. If the item is gotten by S, challenger S sets skij=h3 and the table Rlist is added with this new entry. Conversely, skij∈0,1k is randomly selected by S and the corresponding item is inserted into table Rlist.(iii)
For other conditions, S responds to the C according to the protocol specification.(iii) Analysis.
Assume that adversary C can make a successful forging attack with non-negligible probabilityAdvCΠ, C must make a query to H3 with the input SK=h2DLOGXY and aAPKB=sBX and sAY. To solve the GDHX,Y, S checks whether the value of an H3 query from C is IDA,IDB,TA,TB,h2DLOGXY,sBX,sAY such that DDHh2X,Y,SK=1, DDHX,PKB,sBX=1, and DDHPKA,Y,sAY=1. If such an H3 query is found, S can correctly calculate GDHX,Y=DLOGXY=h2−1SK. Therefore, the GDH problem is solved by S with an advantage(6)AdvSGDHk≥AdvCΠk6nk2qsk.Case 4.
ID
B’s temporary private key and the long-term secret key of IDA are not acquired by adversary C. For case 4, we can consider this case as case 1. Thus, S can use the similar way used in case 1 to make this simulation. Therefore, GDH problem is dealt by S successfully with great advantage(7)AdvSGDHk≥AdvCΠk6nk2qsk.Case 5.
Adversary C does not get long-term secret key ofIDB and IDA’s temporary private key. But the value of RB is changed by C.
Firstly, KGC’s master public key is selected asX∈G. For all participants, S randomly chooses hi,si∈ℤp∗. Next, S makes the equation hi = H1IDi,Ri and gets the value of Ri=siP−hiPpub. So si,Ri is IDi’s long-term secret key. Meanwhile, PKi=Ri+hiPpub = siP is its long-term public key. Then, for every IDi, challenger S returns IDi,Ri to the adversary C and adds IDi,Ri,hi to the table H1list. Besides, S sets Y as the ephemeral public key of IDA. The answers to all kinds of queries from C are easy, because all participants’ long-term secret keys are known by S.
Secondly, we assume that C neither queries EphemeralKeyReveal(ΠA,Bs) nor StaticKeyReveal(IDB). A message IDB,RB,C,bP made by adversary C is sent to the session ΠA,Bs. Here, the adversary C selects b∈ℤp∗ at random and may change RB of IDB to RB,C. For participant IDB, h˜B∈ℤp∗ is chosen by the challenger S and H1IDB,RB,C=h˜B is also assigned by S. Finally, we make an assumption that the successful probability of a forgery attack made by C is AdvCΠ. So C must make a query to H3 with the input SK=H2sAPKBbY = h2bY, aPKB=DLOGYRB+h˜BX, and sATB=sAbP. S checks whether C makes an H3 query on the value IDA,IDB,TA,TB,SK,DLOGYRB+h˜BX,sAbP such that DDHh2Y,TB,SK=1, DDHY,PKB,DLOGYPKB=1, and DDHPKA,TB,sATB=1.
On the basis of forking lemma, S restarts the game with adversary C using the same data. Similarly,h˜B′ is randomly selected and assigned to H1IDB,RB,C by S, and h˜B′ is not equal to h˜B. Assume that the probability of a forgery attack launched successfully can not be ignored. An H3 query must be requested by C with the input SK=h2bY, aPKB=DLOGYRB+h˜B′X, and sATB=sAbP. Then, S does as above.
In order to cope with theGDH, challenger S does a simple calculation on K = DLOGYRB+h˜BX − DLOGYRB+h˜B′X = DLOGYh˜B−h˜B′X. So the right value GDHX,Y=DLOGYX=h˜B−h˜B′−1K can be acquired by S. If λ is forking lemma’s utilization parameter, GDH difficult problem can be successfully dealt by S with the advantage(8)AdvSGDHk≥λAdvCΠk6nk2qsk.Case 6.
Adversary C knows nothing about long-term secret keys ofIDA and IDB. But C alters RB’s real value.
At first, KGC’s public key is assigned by S using a random numberX∈G. Considering about IDi, where A is not the right value of i, hi,si∈ℤp∗ is selected and Ri = siP − hiPpub is calculated by S. Then, S makes the equation hi = H1IDi,Ri true and gives IDi the long-term secret key si,Ri. Thus, relevant public key of IDi gets the value PKi = Ri+hiPpub = siP. Particularly, for IDA, H1IDA,RA is assigned to hA∈ℤp∗ picked by S at random and RA = Y−hAPpub can be worked out. Then, the long-term secret key of IDA gets the value Δ,RA. So its long-term public key is PKA = RA+hAPpub=Y. Besides, S sends IDi,Ri of all parties to the adversary C and stores IDi,Ri,hi to the table H1list. Particularly, the temporary secret key of IDA is given the value a∈ℤp∗ selected by S randomly.
Secondly, it is an assumption that C does not request queries about StaticKeyReveal(IDA) and StaticKeyReveal(IDB). Moreover, the simulation does not abort. A message IDB,RB,C,bP made by C is sent to the session ΠA,Bs. b∈ℤp∗ is randomly selected by the adversary and C can also change RB. Assume that S chooses h¯B∈ℤP∗ at randomly as H1IDB,RB,C. If the probability of a successful forgery attack maked by C cannot be ignored, the adversary must launch an H3 asking with the input sATB = DLOGYbP, aAPKB = aRB+h¯BX, and SK=H2DLOGYPKBabP = H2DLOGYRB+h¯BXabP. Next, S checks whether there is an H3 query from the adversary C on the value IDA,IDB,TA,TB,SK,DLOGYbP,aPKB such that DDHh2TA,TB,SK=1, DDHTA,PKB,aPKB=1, and DDHY,TB,sATB=1.
Similarly, based on forking lemma, S replays the game with adversary C using the same data. S getsh¯B′∈ℤP∗ as H1IDB,RB,C. We should note that h¯B′≠h¯B. As above, if the probability of a forgery attack cannot be ignored, adversary C must make an H3 query with the input sATB = DLOGYbP, aAPKB = aRB+h¯B′X, and SK′=H2DLOGYPKBabP = H2DLOGYRB+h¯B′XabP. Then, S verifies whether such an H3 query from the adversary C exists on the value IDA,IDB,TA,TB,SK,DLOGYbP,aPKB such that DDHh2TA,TB,SK′=1, DDHTA,PKB,aPKB=1, and DDHY,TB,sATB=1.
In order to deal with theGDH problem, S calculates K = DLOGYRB+h¯BX − DLOGYRB+h¯B′X = DLOGYXh¯B−h¯B′. Therefore, S can compute GDHX,Y = h¯B−h¯B′−1K. If λ is forking lemma’s utilization parameter, GDH difficult problem can be successfully dealt by S with an advantage(9)AdvSGDHk≥λAdvCΠk6nk2qsk.
All in all, becauseAdvCΠk is considered to be non-negligible, AdvSGDHk also cannot be ignored. But it is contradictory to the GDH assumption.


### 5.4. Other Discussions

We will show some essential security attributes that our pairing-free 2PAKA protocol holds in the following content.(i)
Mutual authentication. The security proof shows that a useful message cannot be successfully made by any adversary in polynomial time because authentications among users can be achieved by verifying whether those messages that they get are valid or not. Therefore, our protocol has the hidden function of mutual authentication.(ii)
Session Key Agreement. According to our protocol shown in the Key Agreement phase, one session key skij = H3IDi,IDj,SK,aiPKj,siTj = H3IDi,IDj,SK,bjPKi,sjTi can be obtained by two users after communication. Thus, our protocol can complete the negotiation process of a session key.(iii)
Known Session Key Security (KSKS) Resistance. Our protocol can achieve KSKS security property because Session Key Reveal is allowed in the eCK strong security model. Namely, any other session’ key could be revealed to an adversary excluding the goal session and its matching session’s keys. Meanwhile, the probability of the event that C can successfully distinguish goal session key from a random number can be ignored. So C cannot use other session keys to know test session key.(iv)
Forward Secrecy (FS). As it shows in our security proof, it is forbidden that both a user’s long-term and temporary secret keys are known by an adversary. In other words, our protocol can get wPFS. Besides, the case 3 simulates MFS.(v)
Key Compromise imPersonation (KCI) Resistance. In case 1, 3, and 5, the adversary C cannot generate the goal key acquired by IDA and any other user when C knows IDA’s the long-term secret key and even changes those messages sent to IDA.(vi)
Unknown Key Share (UKS) Resistance. Because identity is the core foundation of our protocol, it indicates that one user’s public key is generated depending on its ID. Obviously, the UKS attack can be resisted by our protocol.(vii)
No Key Control (NKC) Resistance. Because H3 hash function does not have the same result with different input, the session key cannot be determined by one party or the adversary. Thus, our protocol can catch NKC resistance.(viii)
BI Resistance: If the long-term secret key of IDA is not obtained by adversary C, C cannot successfully calculate the correct input to H3. So C cannot get the session key generated by IDA and any other party.(ix)
Ephemeral Key Reveal (EKR) Resistance: In case 1, 4, and 5, the security still can be held by our protocol while its temporary secret keys are leaked partially. In case 2 and 6, when the ephemeral keys are compromised completely, this protocol also keeps safe.


## 5.1. Protocol Participants

There is a setU that is composed of all protocol participants. Every party in set U has a unique IDi and corresponding private and public key pair (si,PKi). Besides, PKi is relative with its IDi and si always is generated by the trusted authority (acts as KGC). In security proof, the ability of each participant is usually described by a probability polynomial time (PPT) algorithm. We consider that a polynomial number of sessions are the maximum value that every participant can take part in at the same time. Furthermore, the sth session of party IDA is denoted as ΠA,Bs that is established by party IDA and party IDB. If A finally gets a valid session key by communicating with B, we think participant A completes the session ΠA,Bs.


## 5.2. eCK Model

Without loss of generality, an adversary C always is deemed as a PPT algorithm in the security model. Moreover, C is considered to have the ability to control the whole communication network. It means messages may be arbitrarily replayed, eavesdropped, modified, suspended, and injected by the adversary. The ability of an adversary C always is described through a series of queries. Here, we only give out the simple information about the eCK model, and more details can be found in the literature of Huang and Cao [29].(i)
EphemeraKeyReveal(ΠA,Bs). Adversary C can get the ephemeral private key of protocol participant IDA in session ΠA,Bs.(ii)
SessionKeyReveal(ΠA,Bs). If session ΠA,Bs is completed, adversary C can obtain the session key. Otherwise, a null value will be returned to C.(iii)
StaticKeyReveal(IDA). Adversary C could obtain IDA’s long-term private key sent by this query. But C cannot control IDA completely.(iv)
PKGstaticKeyReveal. The adversary can know PKG’s master private key by this query. This query usually simulates PKG-FS.(v)
EstablishParty(IDA). After requesting this query, a legitimate user IDA can be registered. But the adversary can acquire IDA’s private key. In addition, party IDA is considered to be dishonest.(vi)
Send(ΠA,Bs,M). A message M is transmitted to ΠA,Bs by adversary C. After receiving this message, ΠA,Bs responds to the message according to the protocol regulation. If M is null, this session ΠA,Bs will initiate a session as an initiator. Otherwise, it will be a responder.(vii)
Test(ΠA,Bs). This query usually takes place during the experiment. The adversary C can make this query to a finished fresh session ΠA,Bs only once. The session picks a random value b∈0,1 when getting a test query from the adversary C. If b=1, this session ΠA,Bs returns session key to C. Otherwise, a random number that is indistinguishable from the session key will be given to adversary C.Definition 1 (matching session).
If the sessionsΠA,Bs and ΠB,At have the same session identifier SID, they will be each other’s matching session. SID is a series connection of a session participant’s messages in the order of initiator or responder.Definition 2 (fresh session).
TheΠA,Bs is a fresh session executed by two honest parties IDA and IDB, if none of the following conditions is satisfied.(1)
The sessionΠA,Bs has a matching session ΠB,At. Additionally, a session key of ΠA,Bs or ΠB,At is leaked to adversary C.(2)
Assume that sessionΠA,Bs has a matching session ΠB,At. Besides, all of IDA’s secret keys in ΠA,Bs or the long-term and temporary secret keys of IDB in ΠB,At are revealed to adversary C.(3)
There is no matching session aboutΠA,Bs, but an adversary knows the long-term and ephemeral private keys of IDA in ΠA,Bs or the long-term secret key of IDB.Definition 3 (ID-eCK security).
For adversary C,succ denotes the event that adversary C can know b’s correct value in the manner of sending a Test query to some fresh instances. Therefore, the advantage of adversary C is advAKEC=2Prsucc−1. If a 2PAKA protocol can satisfy the following conditions, this protocol is considered to be ID-eCK security.(1)
For any PPT adversary, the success probability of knowing the rightb is negligible. It means that advAKEC=2Prsucc−1 is a negligible value.(2)
After two honest parties complete a session, they can get the same session key.


## 5.3. Formal Proof

Firstly, our protocol will be proved to have strong enough security in this section. Then, we will show some security attributes that our protocol has.Theorem 1.
AssumeH1, H2, and H3 are three random oracles in the eCK model. According to the difficult GDH problem, no adversary can break the security of protocol Π in polynomial time.Proof.
On the basis of ID-eCK security, we know the two properties inDefinition3 are the basic conditions that a secure AKA protocol should satisfy. We can know the second condition is met in the correctness of our protocol. Next, we show that the first condition also can be met in the following content. In the eCK security model, our protocol Π’s security parameter is specified as k. Meanwhile, the maximum value of truthful users activated by an adversary is nk. The symbol qsk is the maximum number of sessions that each party can take part in. Besides, it is also an assumed condition that the test session selected by adversary C is ΠA,Bs, which is established by IDA and IDB together. Adversary C can only use the following three methods to get the correct value of test session key.(1)
Guessing directly attack. Adversary C can know test session key in a guessing way.(2)
Key replication attack. Adversary C constructs another session that is not a matching session of the test session. But its session key is same with the test session. Hence, adversary C can make the use of a nonmatching session to acquire the test session key. Namely, it means that this protocol cannot stand up to adversary C’s attack.(3)
Forging attack. Adversary C can query H3 random oracle with the input IDA,IDB,TA,TB,SKA,aPKB,andsATB. Obviously, the adversary C calculates the value SKA,aPKB,andsATB by itself.
Becausek is security parameter, it indicates that the size of session key is k bit. Therefore, the guessing directly attack is successful with probability O1/2k. Besides, the role of H3 is the same as a random oracle in the security model. If this random oracle produces no collisions, the event that a session key is jointly owned by two nonmatching sessions occurs with a negligible probability because two nonmatching sessions cannot have the same SID under the definition of matching session. Namely, key replication attack’s successful probability is negligible. Consequently, we only need to consider about the successful probability of the forging attack.
Before we analyze a forging attack in detail, we firstly review the GDH problem. This mathematical assumption is that the valueX=xP,Y=yP is given, where x,y∈Rℤp∗ is unknown, the aim of challenger S is to get the result of GDHX,Y=xyP by using a DDH oracle. Then, a challenger S plays the ID-eCK game with the adversary C who can break the protocol Π. During the game, S must make responses to all kinds of queries of the adversary C. If the adversary C can make a successful forging attack with non-negligible probability, the challenger S can construct a gap Diffie–Hellman solver by using C as a subroutine. As fresh definition shown in the eCK model, we need to consider about two special cases:(1)
The sessionΠB,At is the matching session of the test session ΠA,Bs(2)
There is no corresponding session matching with the sessionΠA,Bs
In the first scenario, we only consider about passive adversary who cannot change messages transmitted among all parties. Contrary to the first scenario, challenger S has an active adversary that could modify the partyIDB’s long-term secret key element RB in the second scenario. Above analysis results show that the adversary can adopt different attack strategies. So before the challenger S plays game with the adversary C, S can ensure C’s test session is ΠA,Bs with probability 1/nk2qsk. In addition, S must guess the attack way that the adversary could choose from the following six strategies:(i)
Case 1. IDB’s long-term secret key and IDA’s temporary private key are not leaked to adversary C. Meanwhile, C transmits RB correctly.(ii)
Case 2. The long-term secret keys of IDA and IDB are not known by C. The value of RB still is not modified by C.(iii)
Case 3. The temporary private keys of IDA and IDB are not revealed to adversary C.(iv)
Case 4. IDB’s temporary private key and the long-term secret key of IDA are not acquired by adversary C.(v)
Case 5. Adversary C does not get the long-term secret key of IDB and IDA’s temporary private key. But the value of RB is changed by C.(vi)
Case 6. Adversary C knows nothing about long-term secret keys of IDA and IDB. But C alters RB’s real value.
Obviously, the six cases above cover all attack manners of different adversaries, including the passive adversary and the active adversary. On the basis of the above result, the correct test session and strategy are chosen by challenger S with the probability1/6nk2qsk.Case 1.
ID
B’s long-term secret key and IDA’s temporary private key are not leaked to adversary C. Meanwhile, C correctly transmits RB.(i) Setup.
The challenger S initializes the long-term keys of all parties and KGC’s public key as follows:(1)
The challenger S chooses the valuePpub∈G at random as the KGC’s public key.(2)
Challenger S randomly chooseshB∈ℤp∗ as H1IDB,RB and calculates RB=Y−hBPpub. So we can know PKB=RB+hBPpub=Y is the long-term public key of IDB. IDB can get its long-term secret key’s value Δ,RB.(3)
For other partiesIDi, the challenger S randomly selects hi,si∈ℤp∗ as H1IDi,Ri and long-term private key. Similarly, the challenger can compute Ri=siP−hiPpub. Therefore, PKi=Ri+hiPpub=siP is IDi’s long-term public key.After the above process, for eachIDi, the challenger passes IDi,Ri to the adversary C and this new entry IDi,Ri,hi is added to H1list.(ii) Queries.
In order to deal withH1, H2, H3, and SessionKeyReveal queries from C, the challenger first maintains the corresponding empty lists H1list, H2list, H3list, and Rlist. Then, the challenger S responds to all queries from C as below:(1)
H1IDi,Ri. In the setup phase, when the long-term secret key of each party IDi is set, S inserts the entry IDi,Ri,hi to H1list. When a query about H1 sent by adversary C already exists in H1list, S returns the corresponding entry to C. Otherwise, S selects randomly hi∈ℤp∗ and adds the new entry IDi,Ri,hi to the list H1list. Then, S returns the random value hi.(2)
H2siPKj. When C launches an H2 query, S first searches for the relevant entry in the whole list H2list. If S finds the entry out, S transmits h2 to C. Conversely, S computes si∗PKj and checks whether this value is already in H2list or not. If the H2list has the corresponding value, the challenger gives h2 to C. Otherwise, S chooses h2∈ℤp∗ at random. Then, S inserts the entry si,PKj,siPKj,h2 to H2list and returns h2 to the adversary C.(3)
H3IDi,IDj,Ti,Tj,SK,aiPKj,siTj. Before this query, S keeps an empty table H3list whose entries are the form of IDi,IDj,Ti,Tj,SK,aiPKj,siTj,h3.(i)
If the corresponding entry is found inH3list, the challenger S responds to the query with h3.(ii)
Otherwise, S checks the whole listRlist. If i has a correct value B and target item is stored, S uses the DDH oracle to verify whether DDHH2sjPKiTj,Ti,SK=DDHh2Tj,Ti,SK=1, DDHTi,PKj,aiPKj=1, and DDHPKi,Tj,siTj=1. If all of them are right, S sets h3=skij and stores the entry IDi,IDj,Ti,Tj,SK,aiPKj,siTj,h3 to H3list. If the entry is found in the list and i≠B, the equation h3=skij is made by challenger S and the relevant item is added to H3list. But if the list H3list has not the corresponding entry or the verifications of DDH oracle are wrong, S randomly selects h3∈0,1k and writes these new data into the list H3list. In final, S returns the corresponding h3 to the adversary C.(4)
EphemeralKeyReveal(Πi,js). If the session Πi,js is ΠA,Bs, the challenger S aborts. Otherwise, the temporary private key of IDi is sent to S by adversary C.(5)
StaticKeyReveal(IDi). If i = B, S aborts. Otherwise, the challenger provides C with si,Ri.(6)
MasterPrivateKeyReveal(). The challenger S aborts.(7)
EstablishParty(IDi). For this query, the challenger S chooses si,hi∈ℤp∗ at random. Then S assigns the value of H1IDi,Ri to hi and calculates Ri=siP−hiPpub. Finally, S sends si,Ri to C as its long-term secret key. Therefore, the adversary C can control IDi completely, it is because the long-term secret key of IDi is known by C.(8)
SessionKeyReveal(Πi,js). If the session Πi,js is ΠA,Bs or ΠB,At, S aborts. Otherwise, S searches for the value sij in the whole list Rlist and sends it to C.(9)
Send(Πi,js, M). A blank table Rlist is held by S whose element is IDi,IDj,Ti,Tj,skij for the Send query.(i)
IfΠi,js is ΠA,Bs and M=Δ, adversary C receives X returned by challenger S.(ii)
If the value ofi is B and M=W, S selects b∈ℤp∗ at random and returns the bP to C. Besides, S verifies whether DDHH2sjPKiTj,Ti,SK=DDHh2Tj,bP,SK=1, DDHTi,PKj,aiPKj=1, and DDHPKi,Tj,siTj=1. If SK, aiPKj, and siTj are correct, S sets skij=h3 and inserts the entry IDi,IDj,Ti,Tj,skij to the list Rlist. But if the list H3list does not have the entry or one of SK, aiPKj, and siTj is wrong, S chooses randomly skij∈0,1k and writes new information to Rlist.(iii)
If B is not the correct value fori, S answers this Send query according to protocol rule.(10)
Test(Πi,js). If the session Πi,js is ΠA,Bs, S chooses randomly β∈0,1k and this data is returned to adversary C. On the contrary, S is not playing this game.(iii) Analysis.
If a forgery attack is successfully launched by adversary C with great probability, C must have usedSK=H2sAYDLOGXbP, aiPKB=DLOGXY, and sATB=sAbP to query H3 random oracle. To cope with the GDHX,Y difficult problem, challenger S checks whether the value of an H3 query from C is IDi,IDj,Ti,Tj,SK,aiPKj,siTj such that DDHH2sjPKiTj,Ti,SK=DDHh2Tj,bP,SK=1, DDHTi,PKj,aiPKj=1, and DDHPKi,Tj,siTj=1. If this H3 query is found, S computes GDHX,Y=DLOGXY=aAPKB using this query. Assume that the probability of the event that a forgery attack is made by adversary C is AdvCΠk, so S successfully deals with the GDH problems with the advantage(4)AdvSGDHk≥AdvCΠk6nk2qsk.Case 2.
The long-term secret keys ofIDA and IDB are not known by C. The value of RB still is not modified by C.(i) Setup.
All parties’ long-term secret keys and KGC’s public key are given by challenger C as follows:(1)
Ppub∈G selected by the challenger S is assigned to KGC’s public key.(2)
As forIDA, a random value hA∈ℤp∗ is selected by S as the value of H1IDA,RA. Then, S does the calculation on RA=X−hAPpub and IDA’s long-term secret key is given the value Δ,RA. Thus, X is relevant public key of IDA.(3)
Using the same method, S selectshB∈ℤp∗ at random as H1IDB,RB for the party IDB and calculates RB=Y−hBPpub. So IDB’s long-term secret key can be assigned to the value Δ,RB. Additionally, IDB’s corresponding public key is PKB=RB+hBPpub=Y.(4)
Considering about other partiesIDi, where i≠A and i≠B, challenger S randomly chooses hi,si∈ℤp∗. Similarly, S sets hi=H1IDi,Ri and computes the relevant value of Ri=siP−hiPpub. Thus, the long-term secret key of entry IDi is si,Ri. Its public key is PKi=Ri+hiPpub. S sends IDi,Ri to the adversary C, and this new entry IDi,Ri,hi is inserted into the table H1list.(ii) Queries.
To deal with the query about SessionKeyReveal and three hash queriesH1, H2, and H3, challenger S stores four tables Rlist and H1list, H2list, H3list. And S uses the following ways to answer those queries asked by C.(1)
H3IDi,IDj,Ti,Tj,SK,aiPKj,siTj. S has an empty list H3list in the form of IDi,IDj,Ti,Tj,SK,aiPKj,siTj,h3.(i)
IfH3list already has the relevant entry IDi,IDj,Ti,Tj,SK,aiPKj,siTj,h3, S returns h3 to the adversary C.(ii)
If not, S looks up target item in the whole tableRlist. If the item is found and the value of i is A or B, challenger S verifies whether DDHh2Ti,Tj,SK=DDHH2DLOGXYTi,Tj,SK=1, DDHTi,PKj,aiPKj=1, and DDHPKi,Tj,siTj=1. If all of them are correct, S sets h3=skij and stores the new entry into the list H3list. If Rlist has the goal entry (A and B are both not the right value of i), S assigns h3 to skij. Then, S adds the new entry to the list H3list. Otherwise, If the corresponding entry does not exist in the list Rlist or SK, aiPKj and siTj are not right, S chooses h3∈0,1k and inserts IDi,IDj,Ti,Tj,SK,aiPKj,siTj,h3 into the list H3list.(2)
EphemeralKeyReveal(Πi,js). Adversary C acquires temporary secret key of entry IDi returned by S.(3)
StaticKeyReveal(IDi). If A or B is the correct value of i, challenger S terminates this program. Otherwise, si,Ri is transmitted to C.(4)
Send(Πi,js, M). As before, a blank table Rlist is held by S, the form of which is IDi,IDj,Ti,Tj,skij.(i)
Ifi is equal to A, its temporary secret key is a∈ℤp∗ picked up by challenger S at random and the value aP is given to C. Next, S seeks the relevant item in the table H3list. If the entry exists, S checks whether DDHh2Ti,Tj,SK=DDHH2DLOGXYTi,Tj,SK=1, DDHTi,PKj,aiPKj=1, and DDHPKi,Tj,siTj=1. If all of them are right, S sets skij=h3 and stores the new entry to Rlist. But if this corresponding item is not found or three values verified by DDH oracle are not correct, S randomly selects skij∈0,1k and writes new data to Rlist.(ii)
Ifi is equal to B, S uses a similar way in the simulation.(iii)
For other conditions, the challenger S responds according to the protocol specification.It is worth noting that S responds to theH1IDi,Ri, H2siPKj, EstablishParty(IDi), MasterPrivateKey, Session KeyReveal(Πi,js), and Test(Πi,js) in the manner of case 1.(iii) Analysis.
Similarly, if the adversary C makes a successful forging attack with non-negligible probabilityAdvCΠ, C must make the use of SK=H2DLOGXYabP, aAPKB=aY, and sATB=bX to query H3. To deal with GDHX,Y, S checks whether the content of an H3 query from C is IDA,IDB,TA,TB,SK,aY,bX such that DDHh2Ti,Tj,SK=DDHH2DLOGXYTi,Tj,SK=1, DDHTi,PKj,aiPKj=1, and DDHPKi,Tj,siTj=1. If S can find such an H3 query, it computes GDHX,Y=DLOGXY. Therefore, GDH difficult problem can be solved by S successfully with the advantage(5)AdvSGDHk≥AdvCΠk6nk2qsk.Case 3.
The temporary private keys ofIDA and IDB are not revealed to adversary C.(i) Setup.
S assigns the values to all parties’ long-term secret keys and KGC’s master keys as follows.(1)
s∈ℤp∗ is chosen by S as KGC’s master secret key and the challenger S also calculates Ppub=sP. Thus, Ppub is its public key. In fact, case 3 simulates MFS.(2)
For each party, S selectssi,hi∈ℤp∗ at random. S sets hi = H1IDi,Ri and calculates Ri=siP−hiPpub. So IDi’s long-term secret key is si,Ri. Then, S computes PKi=Ri+hiPpub = siP. In the end, S sends IDi,Ri to the adversary C. In addition, IDi,Ri,hi is inserted to the table H1list.(ii) Queries.
As before, S holds four blank tablesH1list, H2list, H3list, and Rlist to cope with corresponding queries. Those queries from C are responded by S in the following ways.(1)
H3IDi,IDj,Ti,Tj,SK,aiPKj,siTj. The challenger S has an empty list H3list in the form of IDi,IDj,Ti,Tj,SK,aiPKj,siTj,h3.(i)
If the listH3list already has the matching entry, S returns h3 to C.(ii)
Otherwise, S checks the whole tableRlist. If the item is found out, S sets h3=skij and puts the new entry into the list H3list. If not, h3∈0,1k is randomly chosen by S and the corresponding data is written into H3list.(2)
StaticKeyReveal(IDi). si,Ri is revealed by S to C.(3)
MasterPrivateKeyReveal. The challenger S responds to this query with s.(4)
EphemeralKeyReveal(Πi,js). If Πi,js is ΠA,Bs or ΠB,At, S aborts. Otherwise, S returns the ephemeral key of IDi to C.(5)
Send(Πi,js, M). S maintains an empty list Rlist in the form of IDi,IDj,Ti,Tj,skij.(i)
IfΠi,js = ΠA,Bs, S returns X to C.(ii)
IfΠi,js = ΠB,At, S returns Y to C. Then, S searches for the relevant entry in H3list. If the item is gotten by S, challenger S sets skij=h3 and the table Rlist is added with this new entry. Conversely, skij∈0,1k is randomly selected by S and the corresponding item is inserted into table Rlist.(iii)
For other conditions, S responds to the C according to the protocol specification.(iii) Analysis.
Assume that adversary C can make a successful forging attack with non-negligible probabilityAdvCΠ, C must make a query to H3 with the input SK=h2DLOGXY and aAPKB=sBX and sAY. To solve the GDHX,Y, S checks whether the value of an H3 query from C is IDA,IDB,TA,TB,h2DLOGXY,sBX,sAY such that DDHh2X,Y,SK=1, DDHX,PKB,sBX=1, and DDHPKA,Y,sAY=1. If such an H3 query is found, S can correctly calculate GDHX,Y=DLOGXY=h2−1SK. Therefore, the GDH problem is solved by S with an advantage(6)AdvSGDHk≥AdvCΠk6nk2qsk.Case 4.
ID
B’s temporary private key and the long-term secret key of IDA are not acquired by adversary C. For case 4, we can consider this case as case 1. Thus, S can use the similar way used in case 1 to make this simulation. Therefore, GDH problem is dealt by S successfully with great advantage(7)AdvSGDHk≥AdvCΠk6nk2qsk.Case 5.
Adversary C does not get long-term secret key ofIDB and IDA’s temporary private key. But the value of RB is changed by C.
Firstly, KGC’s master public key is selected asX∈G. For all participants, S randomly chooses hi,si∈ℤp∗. Next, S makes the equation hi = H1IDi,Ri and gets the value of Ri=siP−hiPpub. So si,Ri is IDi’s long-term secret key. Meanwhile, PKi=Ri+hiPpub = siP is its long-term public key. Then, for every IDi, challenger S returns IDi,Ri to the adversary C and adds IDi,Ri,hi to the table H1list. Besides, S sets Y as the ephemeral public key of IDA. The answers to all kinds of queries from C are easy, because all participants’ long-term secret keys are known by S.
Secondly, we assume that C neither queries EphemeralKeyReveal(ΠA,Bs) nor StaticKeyReveal(IDB). A message IDB,RB,C,bP made by adversary C is sent to the session ΠA,Bs. Here, the adversary C selects b∈ℤp∗ at random and may change RB of IDB to RB,C. For participant IDB, h˜B∈ℤp∗ is chosen by the challenger S and H1IDB,RB,C=h˜B is also assigned by S. Finally, we make an assumption that the successful probability of a forgery attack made by C is AdvCΠ. So C must make a query to H3 with the input SK=H2sAPKBbY = h2bY, aPKB=DLOGYRB+h˜BX, and sATB=sAbP. S checks whether C makes an H3 query on the value IDA,IDB,TA,TB,SK,DLOGYRB+h˜BX,sAbP such that DDHh2Y,TB,SK=1, DDHY,PKB,DLOGYPKB=1, and DDHPKA,TB,sATB=1.
On the basis of forking lemma, S restarts the game with adversary C using the same data. Similarly,h˜B′ is randomly selected and assigned to H1IDB,RB,C by S, and h˜B′ is not equal to h˜B. Assume that the probability of a forgery attack launched successfully can not be ignored. An H3 query must be requested by C with the input SK=h2bY, aPKB=DLOGYRB+h˜B′X, and sATB=sAbP. Then, S does as above.
In order to cope with theGDH, challenger S does a simple calculation on K = DLOGYRB+h˜BX − DLOGYRB+h˜B′X = DLOGYh˜B−h˜B′X. So the right value GDHX,Y=DLOGYX=h˜B−h˜B′−1K can be acquired by S. If λ is forking lemma’s utilization parameter, GDH difficult problem can be successfully dealt by S with the advantage(8)AdvSGDHk≥λAdvCΠk6nk2qsk.Case 6.
Adversary C knows nothing about long-term secret keys ofIDA and IDB. But C alters RB’s real value.
At first, KGC’s public key is assigned by S using a random numberX∈G. Considering about IDi, where A is not the right value of i, hi,si∈ℤp∗ is selected and Ri = siP − hiPpub is calculated by S. Then, S makes the equation hi = H1IDi,Ri true and gives IDi the long-term secret key si,Ri. Thus, relevant public key of IDi gets the value PKi = Ri+hiPpub = siP. Particularly, for IDA, H1IDA,RA is assigned to hA∈ℤp∗ picked by S at random and RA = Y−hAPpub can be worked out. Then, the long-term secret key of IDA gets the value Δ,RA. So its long-term public key is PKA = RA+hAPpub=Y. Besides, S sends IDi,Ri of all parties to the adversary C and stores IDi,Ri,hi to the table H1list. Particularly, the temporary secret key of IDA is given the value a∈ℤp∗ selected by S randomly.
Secondly, it is an assumption that C does not request queries about StaticKeyReveal(IDA) and StaticKeyReveal(IDB). Moreover, the simulation does not abort. A message IDB,RB,C,bP made by C is sent to the session ΠA,Bs. b∈ℤp∗ is randomly selected by the adversary and C can also change RB. Assume that S chooses h¯B∈ℤP∗ at randomly as H1IDB,RB,C. If the probability of a successful forgery attack maked by C cannot be ignored, the adversary must launch an H3 asking with the input sATB = DLOGYbP, aAPKB = aRB+h¯BX, and SK=H2DLOGYPKBabP = H2DLOGYRB+h¯BXabP. Next, S checks whether there is an H3 query from the adversary C on the value IDA,IDB,TA,TB,SK,DLOGYbP,aPKB such that DDHh2TA,TB,SK=1, DDHTA,PKB,aPKB=1, and DDHY,TB,sATB=1.
Similarly, based on forking lemma, S replays the game with adversary C using the same data. S getsh¯B′∈ℤP∗ as H1IDB,RB,C. We should note that h¯B′≠h¯B. As above, if the probability of a forgery attack cannot be ignored, adversary C must make an H3 query with the input sATB = DLOGYbP, aAPKB = aRB+h¯B′X, and SK′=H2DLOGYPKBabP = H2DLOGYRB+h¯B′XabP. Then, S verifies whether such an H3 query from the adversary C exists on the value IDA,IDB,TA,TB,SK,DLOGYbP,aPKB such that DDHh2TA,TB,SK′=1, DDHTA,PKB,aPKB=1, and DDHY,TB,sATB=1.
In order to deal with theGDH problem, S calculates K = DLOGYRB+h¯BX − DLOGYRB+h¯B′X = DLOGYXh¯B−h¯B′. Therefore, S can compute GDHX,Y = h¯B−h¯B′−1K. If λ is forking lemma’s utilization parameter, GDH difficult problem can be successfully dealt by S with an advantage(9)AdvSGDHk≥λAdvCΠk6nk2qsk.
All in all, becauseAdvCΠk is considered to be non-negligible, AdvSGDHk also cannot be ignored. But it is contradictory to the GDH assumption.


## 5.4. Other Discussions

We will show some essential security attributes that our pairing-free 2PAKA protocol holds in the following content.(i)
Mutual authentication. The security proof shows that a useful message cannot be successfully made by any adversary in polynomial time because authentications among users can be achieved by verifying whether those messages that they get are valid or not. Therefore, our protocol has the hidden function of mutual authentication.(ii)
Session Key Agreement. According to our protocol shown in the Key Agreement phase, one session key skij = H3IDi,IDj,SK,aiPKj,siTj = H3IDi,IDj,SK,bjPKi,sjTi can be obtained by two users after communication. Thus, our protocol can complete the negotiation process of a session key.(iii)
Known Session Key Security (KSKS) Resistance. Our protocol can achieve KSKS security property because Session Key Reveal is allowed in the eCK strong security model. Namely, any other session’ key could be revealed to an adversary excluding the goal session and its matching session’s keys. Meanwhile, the probability of the event that C can successfully distinguish goal session key from a random number can be ignored. So C cannot use other session keys to know test session key.(iv)
Forward Secrecy (FS). As it shows in our security proof, it is forbidden that both a user’s long-term and temporary secret keys are known by an adversary. In other words, our protocol can get wPFS. Besides, the case 3 simulates MFS.(v)
Key Compromise imPersonation (KCI) Resistance. In case 1, 3, and 5, the adversary C cannot generate the goal key acquired by IDA and any other user when C knows IDA’s the long-term secret key and even changes those messages sent to IDA.(vi)
Unknown Key Share (UKS) Resistance. Because identity is the core foundation of our protocol, it indicates that one user’s public key is generated depending on its ID. Obviously, the UKS attack can be resisted by our protocol.(vii)
No Key Control (NKC) Resistance. Because H3 hash function does not have the same result with different input, the session key cannot be determined by one party or the adversary. Thus, our protocol can catch NKC resistance.(viii)
BI Resistance: If the long-term secret key of IDA is not obtained by adversary C, C cannot successfully calculate the correct input to H3. So C cannot get the session key generated by IDA and any other party.(ix)
Ephemeral Key Reveal (EKR) Resistance: In case 1, 4, and 5, the security still can be held by our protocol while its temporary secret keys are leaked partially. In case 2 and 6, when the ephemeral keys are compromised completely, this protocol also keeps safe.


## 6. Performance Analysis

Within this module, our protocol’s performance is analyzed from computational cost and running time. Besides, we display that our protocol is compared with other related protocols [13, 14] in terms of efficiency.In our experiment, an additive groupG is selected by us, where q is its order. This group has a generator P. The order q is a big prime number with 160-bits and P is a point chosen from a common elliptic curve E/Fp: y2=x3+1. Here, the number of bits of prime number p is 512.


### 6.1. Analysis of Computational Cost

For better computational cost analysis, we firstly give out the comparison results between our protocol and some valuable protocols [13, 14] in terms of message size in the Table 1. Then, on the basis of message size, we analyze their computational cost and give the results in Figure 3.Table 1
Message size of ID-based 2PAKA protocols.
Protocol
Message content
Message size (bytes)
Bala et al.
One ID, two points
42
Dang et al.
One ID, three points
62
Our protocol
One ID, two points
42Figure 3
Comparison of computational cost.Assume that the ID of one party is 2 bytes long. In addition, messages exchanged between two parties in our protocol areIDi,Ri,Ti. Here, Ri and Ti belong to G. So the messages are one ID and two points, whose total size is 2∗8+160∗2/8=42bytes. Similarly, the size of exchanged messages in the Bala et al.’s protocol is also 42 bytes. However, in Dang et al.’s protocol, the messages’ size is 62 bytes.Next, we present the executing time of some basic operations in Table2.Table 2
Executing time of basic operations (ms).
Operation
Description
Personal computer
T
sm
Scalar multiplication
2.165
T
hf
Hash function
0.007
T
bp
Bilinear pairing
5.427We have achieved these basic operations in the MIRACL library [30]. The implementations were deployed in a personal computer and the platform’s parameters are displayed in the following Table 3.Table 3
Simulation platform.
Device
Dell
Operating system
Windows 8
CPU
15-4460S 2.90 GHz
Memory
4 GB RAM
Program language
CWhat deserves our attention is that our protocol is a symmetrical structure. In other words, the partyIDA and IDB are making the computational operations at the same time. Thus, we only need to consider about the computational cost of one party. In our protocol, the computational operation only includes Ti=aiP. Fortunately, this operation is only a simple scalar multiplication. But among the other two protocols being compared, we can find the computational operations are both four scalar multiplications. When precomputation is considered, there are still three scalar multiplications in the Bala et al.’s protocol and two scalar multiplications in the Dang et al.’s protocol. The result of computational cost is shown in the following figure.Now, we know the computational operations in the three protocols. Moreover, we can find that most of these computational operations can be completed offline. We can know that a scalar multiplication needs 2.165 ms in the personal computer according to Table2. Therefore, we can get the respective computational time of the three protocols. In general, we take the precomputation into consideration. So the computational time of Bala et al.’s protocol is 3∗2.165ms=6.495ms. In the Dang et al.’s protocol, it needs 2∗2.156ms=4.33ms. But in our protocol, we only need 1∗2.165ms=2.165ms to achieve the required operation. Therefore, our protocol has better performance.


### 6.2. Analysis of Running Time

Generally, the running time of an AKA protocol is approximately made up of computational time and transmission time. Here, we can only consider the transmission time, because we already know the corresponding computational time of each protocol. As for the transmission time, we think the transmission time is mainly related to message size and hardware performance. We assume that these hardware equipments have similar performance. Hence, if the message size is longer, more time is needed to transmit it. Fortunately, we have analyzed these protocols’ message size in the analysis of computational cost.Table1 shows that our protocol has smaller message size than Dang’s protocol and the same size as Bala’s protocol. Therefore, compared with other ID-based protocols, our protocol can get stronger or be at the same level of security with less running time.In conclusion, the performance of our protocol is better than that of the other two protocols. Besides, our protocol is superior to the Dang’s protocol in resisting attacks. Therefore, our protocol has better performance in VANETs environment compared with previous ID-based 2PAKA protocols.


## 6.1. Analysis of Computational Cost

For better computational cost analysis, we firstly give out the comparison results between our protocol and some valuable protocols [13, 14] in terms of message size in the Table 1. Then, on the basis of message size, we analyze their computational cost and give the results in Figure 3.Table 1
Message size of ID-based 2PAKA protocols.
Protocol
Message content
Message size (bytes)
Bala et al.
One ID, two points
42
Dang et al.
One ID, three points
62
Our protocol
One ID, two points
42Figure 3
Comparison of computational cost.Assume that the ID of one party is 2 bytes long. In addition, messages exchanged between two parties in our protocol areIDi,Ri,Ti. Here, Ri and Ti belong to G. So the messages are one ID and two points, whose total size is 2∗8+160∗2/8=42bytes. Similarly, the size of exchanged messages in the Bala et al.’s protocol is also 42 bytes. However, in Dang et al.’s protocol, the messages’ size is 62 bytes.Next, we present the executing time of some basic operations in Table2.Table 2
Executing time of basic operations (ms).
Operation
Description
Personal computer
T
sm
Scalar multiplication
2.165
T
hf
Hash function
0.007
T
bp
Bilinear pairing
5.427We have achieved these basic operations in the MIRACL library [30]. The implementations were deployed in a personal computer and the platform’s parameters are displayed in the following Table 3.Table 3
Simulation platform.
Device
Dell
Operating system
Windows 8
CPU
15-4460S 2.90 GHz
Memory
4 GB RAM
Program language
CWhat deserves our attention is that our protocol is a symmetrical structure. In other words, the partyIDA and IDB are making the computational operations at the same time. Thus, we only need to consider about the computational cost of one party. In our protocol, the computational operation only includes Ti=aiP. Fortunately, this operation is only a simple scalar multiplication. But among the other two protocols being compared, we can find the computational operations are both four scalar multiplications. When precomputation is considered, there are still three scalar multiplications in the Bala et al.’s protocol and two scalar multiplications in the Dang et al.’s protocol. The result of computational cost is shown in the following figure.Now, we know the computational operations in the three protocols. Moreover, we can find that most of these computational operations can be completed offline. We can know that a scalar multiplication needs 2.165 ms in the personal computer according to Table2. Therefore, we can get the respective computational time of the three protocols. In general, we take the precomputation into consideration. So the computational time of Bala et al.’s protocol is 3∗2.165ms=6.495ms. In the Dang et al.’s protocol, it needs 2∗2.156ms=4.33ms. But in our protocol, we only need 1∗2.165ms=2.165ms to achieve the required operation. Therefore, our protocol has better performance.


## 6.2. Analysis of Running Time

Generally, the running time of an AKA protocol is approximately made up of computational time and transmission time. Here, we can only consider the transmission time, because we already know the corresponding computational time of each protocol. As for the transmission time, we think the transmission time is mainly related to message size and hardware performance. We assume that these hardware equipments have similar performance. Hence, if the message size is longer, more time is needed to transmit it. Fortunately, we have analyzed these protocols’ message size in the analysis of computational cost.Table1 shows that our protocol has smaller message size than Dang’s protocol and the same size as Bala’s protocol. Therefore, compared with other ID-based protocols, our protocol can get stronger or be at the same level of security with less running time.In conclusion, the performance of our protocol is better than that of the other two protocols. Besides, our protocol is superior to the Dang’s protocol in resisting attacks. Therefore, our protocol has better performance in VANETs environment compared with previous ID-based 2PAKA protocols.


## 7. Conclusion

To be able to deal with the increasing demands of VANETs (e.g., due to the increasing number of connected vehicles and devices), we constructed a new efficient 2PAKA protocol based on the identity in this paper. This protocol was designed to provide an authentication function and a session key to two users in an efficient way. Besides, we showed that our protocol has strong security in the eCK model, and it outperforms two other recently proposed 2PAKA protocols [13, 14].Future research includes extending the protocol to achieve other desirable properties, as well as implementing an initial model of the extended protocol for evaluation in a practical application.



---

*Source: 7871067-2019-12-04.xml*