# A Novel ID-Based Authentication and Key Exchange Protocol Resistant to Ephemeral-Secret-Leakage Attacks for Mobile Devices

Authors: Yuh-Min Tseng; Sen-Shan Huang; Tung-Tso Tsai; Li Tseng
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

With the rapid development in wireless communications and cloud computing technologies, clients (users) often use handheld mobile	 devices to access remote servers via open network channels. To provide authentication and confidentiality between clients and servers, a large number of ID-based authentication and key exchange (ID-AKE) protocols have been proposed for mobile client-server environments. However, most of the existing ID-AKE protocols adopt the precomputation technique so that they become vulnerable to the ephemeral-secret-leakage (ESL) attacks, in the sense that an adversary could use the ephemeral secrets to reveal the private keys of clients from the corresponding exchange messages. In the paper, we propose a new ESL-secure ID-AKE protocol for mobile client-server environments. We formally prove that the proposed protocol satisfies the security requirements of both mutual authentication and key exchange while resisting the ESL attacks. When compared with previously proposed ID-AKE protocols, our protocol has higher security and retains computational performance, since it requires no bilinear pairing operation for mobile clients. Finally, we mention the possibility of adopting our protocol as an authentication method of the extensible authentication protocol (EAP) for wireless networks.


---

## Body

## 1. Introduction

A key exchange protocol allows two parties to construct a session key. A symmetric encryption scheme with the session key is used to achieve confidentiality between the two parties. However, key exchange protocols without authentication are not secure against impersonation and intruder-in-the-middle attacks. An authentication and key exchange (AKE) protocol is a key exchange protocol under which the established session key of two parties remains secret to other parties. Several famous AKE protocols [1–3] based on the traditional public-key systems [4, 5] have been proposed to provide confidentiality and mutual authentication.In 1985, Shamir [6] proposed an identity- (ID-) based public-key system that eliminates the certificate management in conventional public-key systems. In an ID-based public-key system, a user’s public key is derived from the user’s identity information, such as name, social security number, and e-mail address. However, Shamir’s system is not practical. In 2001, Boneh and Franklin [7] followed Shamir’s idea to propose a practical ID-based encryption scheme based on the Weil pairing. Afterwards, the ID-based cryptography received significant attention. A large number of ID-based cryptographic schemes and protocols have appeared in the literatures, such as ID-based encryption schemes [8–11], ID-based signature schemes [12–14], ID-based group key exchange protocols [15–18], and ID-based AKE protocols [19–23].


### 1.1. Motivation

With rapid growth of wireless communications, clients usually employ mobile devices (e.g., smart card) to obtain services from remote servers via open network channels. In a mobile client-server environment, these mobile devices are generally resource-constrained because they possess only low-power energy and limited computing capability. In this case, cryptographic operations with expensive computations would become heavy load for mobile devices. Hence, it is a critical issue to diminish the computational load of mobile devices in AKE or ID-based AKE protocols.To overcome the resource-constrained situation on the client side, several AKE protocols [24–26] for mobile devices have been proposed for conventional public-key systems. Also, based on Boneh and Franklin’s ID-based public-key setting, a number of ID-based AKE protocols for mobile devices [27–33] have been proposed to focus on the computation issue for mobile devices. These protocols above adopted an imbalanced computation technique to reduce the client’s computational cost by shifting computational burden to a powerful server.On the other hand, the offline precomputation technique is employed to lighten the online computational load of mobile devices. In the offline precomputation phase, ephemeral secrets (or random values) are required to generate some values in advance. In the meantime, the ephemeral secrets and these precomputed values are stored in the memory of mobile devices for the usage in the online phase. As a result, a new type of attacks would occur, called ephemeral-secret-leakage (ESL) attacks [34–36], in the sense that an adversary can reveal the private keys of clients from those precomputed values or the corresponding exchange messages if the ephemeral secrets are compromised. To our knowledge, the existing ID-based AKE protocols [27–33] did not address the ESL attacks at all. In the paper, we will construct an ID-based AKE protocol which is resistant to the ESL attacks under mobile client-server environments.


### 1.2. Related Work

In 2002, Smart [19] proposed the first ID-based AKE (ID-AKE) protocol based on the Weil pairing. However, Shim [20] pointed out that Smart’s protocol does not offer forward secrecy. Shim also presented a new ID-AKE protocol with the optimal number of Weil pairing operations. Afterwards, several ID-AKE protocols [21–23] were proposed to improve performance and achieve more security properties. However, the protocols mentioned above require bilinear pairing operations on both ends and are consequently not suited for low-power computing devices.In 2005, Choi et al. [27] proposed an ID-AKE protocol for mobile client-server environments. They adopted an imbalanced computation technique which shifts the client’s computational burden to a powerful server. In 2010, Wu and Tseng [28, 29] also proposed two efficient ID-AKE protocols which do not require any bilinear pairing operations on the client side under mobile client-server environments. Their protocols are proved to be secure against ID attack, impersonation attack, and passive attack and offer mutual authentication, implicit key confirmation, and partial forward secrecy. In 2012, He [30] presented a new ID-AKE protocol to improve the performance of Wu and Tseng’s protocol on client side. In addition, Islam and Biswas [31] and He et al. [32], independently, proposed ID-AKE protocols based on elliptic curve cryptography (ECC) without using bilinear pairings. Chuang and Tseng [33] proposed a generalized ID-based AKA protocol for mobile multiserver environments which is suitable for both general users with a long validity period and anonymous users with a short validity period. Chuang and Tseng’s protocol is secure against all known attacks and provides forward secrecy. Indeed, all the mentioned ID-AKE protocols [27–33] adopted the precomputation technique to reduce the computational load of the mobile client. In such a case, as mentioned earlier, those ID-AKE protocols would be vulnerable to ESL attacks under mobile client-server environments.In 2007, LaMacchia et al. [34] presented a strong security model for AKE protocols, which is concerned with the ESL attacks. They proposed a concrete AKE protocol resistant to ESL attacks. In their protocol, the leakage of ephemeral secrets would not damage the security of session keys and private keys of parties. In 2011, Ni et al. [35] proposed a strongly secure ID-AKE protocol which captures all basic security properties including the ESL resistance. Although Ni et al.’s protocol requires six bilinear pairing operations, one can employ the precomputation technique to reduce the computation cost if it knows the identity of the other party in communication beforehand. However, they did not address the scenarios for applications to mobile client-server environments. In 2014, Islam [36] also proposed a provably secure ID-AKE protocol resistant to ESL attack. Islam’s protocol still requires two bilinear pairing operations for a client.


### 1.3. Contribution and Organization

In the paper, we propose a new ID-AKE protocol resistant to ESL attacks in mobile client-server environments, called ESL-secure ID-AKE protocol. In the proposed protocol, we also adopt the techniques of imbalanced computation and offline precomputation to reduce the computational cost required by a mobile client. Indeed, our protocol requires no bilinear pairing for mobile clients. Our protocol employs Tseng et al.’s ESL-secure signature scheme [37] to achieve the client-to-server authentication. Also, the offline precomputation is carried out prior to the execution of our protocol to achieve better performance. As compared with previously proposed protocols, our protocol is secure against the ESL attacks while retaining the computational performance. For security analysis, we first formalize the adversary’s capabilities by redefining the adversarial model of ESL-secure ID-AKE protocols in mobile client-server environments. Under the computational Diffie-Hellman (CDH) assumption [7, 12], we demonstrate that our protocol is provably secure in the random oracle model [38, 39]. Finally, we discuss the relationship between our protocol and the extensible authentication protocol (EAP) for wireless networks [40–43]. It turns out that our ESL-secure ID-AKE protocol can be viewed as an authentication method of the EAP framework [40, 41].The remainder of this paper is organized as follows. In Section2, mathematical assumptions are presented. An adversarial model of the ESL-secure ID-AKE protocols is presented in Section 3. The proposed ESL-secure ID-AKE protocol is presented in Section 4. In Section 5, we give security analysis of the proposed protocol. Performance comparisons and discussions are given in Section 6. Finally, conclusions are drawn in Section 7.


## 1.1. Motivation

With rapid growth of wireless communications, clients usually employ mobile devices (e.g., smart card) to obtain services from remote servers via open network channels. In a mobile client-server environment, these mobile devices are generally resource-constrained because they possess only low-power energy and limited computing capability. In this case, cryptographic operations with expensive computations would become heavy load for mobile devices. Hence, it is a critical issue to diminish the computational load of mobile devices in AKE or ID-based AKE protocols.To overcome the resource-constrained situation on the client side, several AKE protocols [24–26] for mobile devices have been proposed for conventional public-key systems. Also, based on Boneh and Franklin’s ID-based public-key setting, a number of ID-based AKE protocols for mobile devices [27–33] have been proposed to focus on the computation issue for mobile devices. These protocols above adopted an imbalanced computation technique to reduce the client’s computational cost by shifting computational burden to a powerful server.On the other hand, the offline precomputation technique is employed to lighten the online computational load of mobile devices. In the offline precomputation phase, ephemeral secrets (or random values) are required to generate some values in advance. In the meantime, the ephemeral secrets and these precomputed values are stored in the memory of mobile devices for the usage in the online phase. As a result, a new type of attacks would occur, called ephemeral-secret-leakage (ESL) attacks [34–36], in the sense that an adversary can reveal the private keys of clients from those precomputed values or the corresponding exchange messages if the ephemeral secrets are compromised. To our knowledge, the existing ID-based AKE protocols [27–33] did not address the ESL attacks at all. In the paper, we will construct an ID-based AKE protocol which is resistant to the ESL attacks under mobile client-server environments.


## 1.2. Related Work

In 2002, Smart [19] proposed the first ID-based AKE (ID-AKE) protocol based on the Weil pairing. However, Shim [20] pointed out that Smart’s protocol does not offer forward secrecy. Shim also presented a new ID-AKE protocol with the optimal number of Weil pairing operations. Afterwards, several ID-AKE protocols [21–23] were proposed to improve performance and achieve more security properties. However, the protocols mentioned above require bilinear pairing operations on both ends and are consequently not suited for low-power computing devices.In 2005, Choi et al. [27] proposed an ID-AKE protocol for mobile client-server environments. They adopted an imbalanced computation technique which shifts the client’s computational burden to a powerful server. In 2010, Wu and Tseng [28, 29] also proposed two efficient ID-AKE protocols which do not require any bilinear pairing operations on the client side under mobile client-server environments. Their protocols are proved to be secure against ID attack, impersonation attack, and passive attack and offer mutual authentication, implicit key confirmation, and partial forward secrecy. In 2012, He [30] presented a new ID-AKE protocol to improve the performance of Wu and Tseng’s protocol on client side. In addition, Islam and Biswas [31] and He et al. [32], independently, proposed ID-AKE protocols based on elliptic curve cryptography (ECC) without using bilinear pairings. Chuang and Tseng [33] proposed a generalized ID-based AKA protocol for mobile multiserver environments which is suitable for both general users with a long validity period and anonymous users with a short validity period. Chuang and Tseng’s protocol is secure against all known attacks and provides forward secrecy. Indeed, all the mentioned ID-AKE protocols [27–33] adopted the precomputation technique to reduce the computational load of the mobile client. In such a case, as mentioned earlier, those ID-AKE protocols would be vulnerable to ESL attacks under mobile client-server environments.In 2007, LaMacchia et al. [34] presented a strong security model for AKE protocols, which is concerned with the ESL attacks. They proposed a concrete AKE protocol resistant to ESL attacks. In their protocol, the leakage of ephemeral secrets would not damage the security of session keys and private keys of parties. In 2011, Ni et al. [35] proposed a strongly secure ID-AKE protocol which captures all basic security properties including the ESL resistance. Although Ni et al.’s protocol requires six bilinear pairing operations, one can employ the precomputation technique to reduce the computation cost if it knows the identity of the other party in communication beforehand. However, they did not address the scenarios for applications to mobile client-server environments. In 2014, Islam [36] also proposed a provably secure ID-AKE protocol resistant to ESL attack. Islam’s protocol still requires two bilinear pairing operations for a client.


## 1.3. Contribution and Organization

In the paper, we propose a new ID-AKE protocol resistant to ESL attacks in mobile client-server environments, called ESL-secure ID-AKE protocol. In the proposed protocol, we also adopt the techniques of imbalanced computation and offline precomputation to reduce the computational cost required by a mobile client. Indeed, our protocol requires no bilinear pairing for mobile clients. Our protocol employs Tseng et al.’s ESL-secure signature scheme [37] to achieve the client-to-server authentication. Also, the offline precomputation is carried out prior to the execution of our protocol to achieve better performance. As compared with previously proposed protocols, our protocol is secure against the ESL attacks while retaining the computational performance. For security analysis, we first formalize the adversary’s capabilities by redefining the adversarial model of ESL-secure ID-AKE protocols in mobile client-server environments. Under the computational Diffie-Hellman (CDH) assumption [7, 12], we demonstrate that our protocol is provably secure in the random oracle model [38, 39]. Finally, we discuss the relationship between our protocol and the extensible authentication protocol (EAP) for wireless networks [40–43]. It turns out that our ESL-secure ID-AKE protocol can be viewed as an authentication method of the EAP framework [40, 41].The remainder of this paper is organized as follows. In Section2, mathematical assumptions are presented. An adversarial model of the ESL-secure ID-AKE protocols is presented in Section 3. The proposed ESL-secure ID-AKE protocol is presented in Section 4. In Section 5, we give security analysis of the proposed protocol. Performance comparisons and discussions are given in Section 6. Finally, conclusions are drawn in Section 7.


## 2. Preliminaries

In this section, we compendiously introduce the concept of bilinear pairings, the related mathematical assumptions, and the notations used throughout this paper.


### 2.1. Bilinear Pairings

LetG1 and G2 be additive and multiplicative cyclic groups of large prime order q, respectively. A map e^:G1×G1→G2 is called an admissible bilinear map if it satisfies the following three conditions:(1)
bilinearity: for allP,Q∈G1 and a,b∈Zq∗, we have e^(aP,bQ)=e^P,Qab;(2)
nondegeneracy: for someP,Q∈G1, e^(P,Q)≠1 holds;(3)
computability: givenP,Q∈G1, there is an efficient algorithm to compute e^(P,Q).Note that condition (1) implies that e^(P+Q,R)=e^(P,R)·e^(Q,R) and e^(P,Q+R)=e^(P,Q)·e^(P,R), for P,Q,R∈G1. Full descriptions of groups, maps, and other parameters are discussed in [7, 12]. The relationship between security level and speed for pairing computations is presented in [29].


### 2.2. Security Assumptions

LetG1, G2, and e^ be defined as above. Here, we define a security assumption on which our scheme is based.Computational Diffie-Hellman (CDH) problem: givenP,aP,bP∈G1 for unknown a,b∈Zq∗, the CDH problem in G1 is to compute abP.Definition 1.
The CDH assumption inG1 is defined as follows. Given P,aP,bP∈G1 for unknown a,b∈Zq∗, no probabilistic polynomial-time (PPT) adversary A can compute abP with a nonnegligible probability. The successful probability (advantage) of the adversary A is presented as (1)AdvA=PrAP,aP,bP=abP∣P∈G1,a,b∈Zq∗,where the probability is measured over the random choices of a,b∈Zq∗ consumed by A.


### 2.3. Notations

For convenience, the system parameters, notations, and functions used throughout this paper are defined as follows:e^: an admissible bilinear map from G1×G1 into G2;P: a generator of the group G1;s: the system private key s randomly chosen from Zq∗;Ppub: the system public key defined by Ppub=s·P;ID: the identity of a client;DID: the private key of the client ID;f1(), f2(), f3(), f4(): one-way hash functions mapping from 0,1∗ into 0,1n, where n is a fixed length with 2n<q;H1(),H2(): map-to-point hash functions mapping from 0,1∗ into G1.


## 2.1. Bilinear Pairings

LetG1 and G2 be additive and multiplicative cyclic groups of large prime order q, respectively. A map e^:G1×G1→G2 is called an admissible bilinear map if it satisfies the following three conditions:(1)
bilinearity: for allP,Q∈G1 and a,b∈Zq∗, we have e^(aP,bQ)=e^P,Qab;(2)
nondegeneracy: for someP,Q∈G1, e^(P,Q)≠1 holds;(3)
computability: givenP,Q∈G1, there is an efficient algorithm to compute e^(P,Q).Note that condition (1) implies that e^(P+Q,R)=e^(P,R)·e^(Q,R) and e^(P,Q+R)=e^(P,Q)·e^(P,R), for P,Q,R∈G1. Full descriptions of groups, maps, and other parameters are discussed in [7, 12]. The relationship between security level and speed for pairing computations is presented in [29].


## 2.2. Security Assumptions

LetG1, G2, and e^ be defined as above. Here, we define a security assumption on which our scheme is based.Computational Diffie-Hellman (CDH) problem: givenP,aP,bP∈G1 for unknown a,b∈Zq∗, the CDH problem in G1 is to compute abP.Definition 1.
The CDH assumption inG1 is defined as follows. Given P,aP,bP∈G1 for unknown a,b∈Zq∗, no probabilistic polynomial-time (PPT) adversary A can compute abP with a nonnegligible probability. The successful probability (advantage) of the adversary A is presented as (1)AdvA=PrAP,aP,bP=abP∣P∈G1,a,b∈Zq∗,where the probability is measured over the random choices of a,b∈Zq∗ consumed by A.


## 2.3. Notations

For convenience, the system parameters, notations, and functions used throughout this paper are defined as follows:e^: an admissible bilinear map from G1×G1 into G2;P: a generator of the group G1;s: the system private key s randomly chosen from Zq∗;Ppub: the system public key defined by Ppub=s·P;ID: the identity of a client;DID: the private key of the client ID;f1(), f2(), f3(), f4(): one-way hash functions mapping from 0,1∗ into 0,1n, where n is a fixed length with 2n<q;H1(),H2(): map-to-point hash functions mapping from 0,1∗ into G1.


## 3. Adversarial Model

Based on the security models in [34, 35], we present an adversarial model of ESL-secure ID-AKE protocols for mobile client-server environments. In 2007, LaMacchia et al. [34] presented a strong security model of AKE protocols, which addresses the ephemeral-secret-leakage (ESL) attacks. Based on LaMacchia et al.’s model, Ni et al. [35] defined the security model of strongly secure ID-AKE protocols (or named ESL-secure ID-AKE protocols) by adding the key extract query. Their model is a modification of LaMacchia et al.’s model altered from the conventional PKI-based setting to the ID-based setting.In the following, we first describe an adversary’s capabilities of ESL-secure ID-AKE protocols for mobile client-server environments. In our adversarial model, we assume that an adversaryA is a probabilistic polynomial-time (PPT) algorithm and potentially control all communications by accessing to a set of oracles described below. In the following, we will denote the kth instance of the participant U∈{C,S} by ΠUk, where C and S indicate a client and the powerful server, respectively.Hash Queries
(
M
). The oracle ΠUk keeps an initially empty list for each hash function. Upon receiving the hash query along with a message M, the same response is returned if the query has been asked before. Otherwise, the oracle ΠUk selects a random value D, records the pair (M,D) in the list, and returns D to the adversary A.(i)
Extract  (ID): upon receiving such a query, the oracle ΠUk computes the private key DID associated with ID and returns it to the adversary A. This query modelsID attacks.(ii)
Send  (ΠUk,M): upon receiving such a query, the oracle ΠUk executes the protocol according to M and responds the corresponding results to the adversary A. This query modelspassive attacks.(iii)
Reveal  (ΠUk): upon receiving such a query, the oracle ΠUk outputs the corresponding session key SK if the oracle has accepted the session; otherwise, it returns a null value. This query addresses theknown-session-key security, in the sense that a compromised session key should not endanger other session keys.(iv)
Ephemeral-secret-leakage  (ΠCk): this query modelsephemeral-secret-leakage attacks. When the adversary A issues this query, the oracle ΠCk returns the used ephemeral secret values (or random values) in the corresponding session. Note that, in our adversarial model, A is forbidden to issue this type of query on the server S.(v)
Corrupt  (ΠCk): this query modelspartial forward secrecy. The adversary A can issue such a query on a client C to obtain the private key of C. Therefore, a compromised private key should not endanger any previous session key between the client and the server. Here, as in [34, 35], the adversary A can issueEphemeral-secret-leakage query orCorrupt query, but not both.(vi)
Test(ΠUk): when the adversary A sends such a query, the oracle flips an unbiased coin b. If b=1, then the oracle ΠUk returns the session key SK; otherwise, it returns a random value. A is allowed to issue such a query only once to the oracle ΠUk.Here, we present the adversarial model of ESL-secure ID-AKE protocols. The reader is referred to [34–36] for detailed descriptions.Definition 2 (partnership).
One says thatΠCk and ΠSt are partners if they can authenticate mutually and accept a common session key.Definition 3 (freshness).
An oracleΠCk with partner ΠSt is fresh if the following conditions hold:(1)
ΠCk and ΠSt accept a session key SK≠NULL while both of them are not requested byReveal query;(2)
noCorrupt query can be issued before the querySend(ΠCk,M) or querySend(ΠSt,M) is asked.Definition 4 (ESL-secure ID-AKE security).
An ESL-secure ID-AKE protocol for mobile multiserver environments offers existential unforgeability and possesses the secrecy of session key against adaptive chosen ID attacks if no PPT adversaryA has a nonnegligible advantage in the following game played between A and a set of oracles ΠUk, where U∈{C,S}.(1)
The adversaryA may ask a finite number of various queries and obtain responses from the corresponding oracles.(2)
Every user is assigned a private key via the key extract phase after the system setup phase accomplishes.(3)
NoReveal(ΠUk) orCorrupt(ΠUk) can be issued before theTest(ΠUk) is asked.(4)
The adversaryA can issueEphemeral-secret-leakage(ΠCk) orCorrupt(ΠCk), but not both.(5)
The adversaryA may adaptively make further queries beforeTest(ΠUk), where ΠUk must be fresh. Finally, A outputs its guess for the bit b which has been previously chosen in theTest(ΠUk).Definition 5 (advantage).
Let Succ denote the event thatA correctly guesses the bit b chosen in theTest query. If A asks aTest(ΠUk) and guesses the bit b, the successful advantage (probability) of A in attacking the ESL-secure ID-AKE protocol P is defined as AdvP(A)=2·PrSucc-1. One says that the ESL-secure ID-AKE protocol P is secure if AdvP(A) is negligible.Definition 6 (partial forward secrecy).
An ESL-secure ID-AKE protocolP provides partial forward secrecy if any adversary A with client C’s private key cannot compromise previous session keys between C and the server.Definition 7 (implicit key authentication).
An ESL-secure ID-AKE protocol provides implicit key authentication if every client is assured that no other clients can learn its session keys with the server.


## 4. Our Protocol

In this section, we present our concrete ESL-secure ID-AKE protocol for mobile client-server environments. Our protocol consists of three phases, namely, the system setup phase, the key extract phase, and the mutual authentication and key agreement phase.


### 4.1. System Setup Phase

Our system consists of a powerful serverS and some mobile clients. These clients refer to users with handheld devices. A client has access to the server through open channels, such as the Internet or wireless networks. The powerful server S is responsible for generating and distributing private keys to clients while providing services or applications. The server S is also responsible for generating the system parameters.In the phase, the serverS first generates two cyclic groups G1 and G2 of a large prime order q, an admissible bilinear map e^:G1×G1→G2, and a random generator P of G1, where G1 and G2 are additive and multiplicative groups, respectively. The server S then performs the following tasks:(1)
randomly select a system private keys∈Zq∗;(2)
compute the system public keyPpub=s·P;(3)
choose six cryptographic hash functionsH1,H2:0,1∗→G1 and f1,f2,f3,f4:0,1∗→0,1n, where n is a fixed length with 2n<q;(4)
publish public parameters and functions as(2)Params=G1,G2,q,P,e^,Ppub,H1,H2,f1,f2,f3,f4.


### 4.2. Key Extract Phase

In the key extract phase, a client submits its identityID to the server S and receives the corresponding private key DID. The key extract phase is depicted in Figure 1. We present the detailed procedures as follows.(1)
The client submits its identityID to the server S.(2)
Upon receiving a client’s identityID, the server chooses an ephemeral secret value l∈Zq∗ and computes QID,1=l·P, h=f1(ID,QID,1), DID,1=l+h·s, QID,2=H1(ID), and DID,2=s·QID,2.(3)
SetDID=(DID,1,DID,2,QID,1) and send it to the client via a secure channel.Figure 1
The key extract phase.


### 4.3. Mutual Authentication and Key Exchange Phase

Suppose that a client with identityID would like to communicate with the powerful server S and to access services of the server. As depicted in Figure 2, the detailed interactions between the client and the server are presented as below.(1)
The client with identityID performs offline computations in advance.
(a)
Random select an ephemeral secretr∈Zq∗.(b)
ComputeU1=r·P and U2=r·QID,2.(c)
ComputeW=H2(U1,U2) and V=(r+DID,1)·W+DID,2.(d)
SendID,U1,U2,V,QID,1 to the server.(2)
Upon receivingID,U1,U2,V,QID,1, the server S performs the following tasks.
(a)
ComputeW=H2(U1,U2), h=f1(ID,QID,1), and QID,2=H1(ID).(b)
Check whether the equalitye^(P,V)=e^(U1+QID,1,W)·e^(Ppub,h·W+QID,2) holds or not. If so, the server S accepts the request. Otherwise, the server terminates the process.(c)
Acquire a nonceN.(d)
ComputeKS=s·U2 and AuthS=f2(ID,U1,U2,V,N,KS).(e)
Finally, sendN,AuthS to the client.(3)
Upon receivingN,AuthS, the client authenticates the server S by performing the following tasks.
(a)
ComputeKC=r·DID,2.(b)
Check whether the equalityAuthS=f2(ID,U1,U2,V,N,KC) holds or not. If so, the client accepts the server S.(c)
ComputeAuthC=f3(ID,U1,U2,V,N,KC,AuthS).(d)
Compute a session keySK=f4(ID,U1,U2,V,N,KC,AuthS,AuthC).(e)
The client sendsAuthC to the serverS.(4)
Upon receivingAuthC, the server S authenticates and establishes a session key by performing the following tasks.
(a)
Check whether the equalityAuthC=f3(ID,U1,U2,V,N,KS,AuthS) holds or not. If so, the server accepts the client.(b)
Compute a session keySK=f4(ID,U1,U2,V,N,KS,AuthS,AuthC).Figure 2
The mutual authentication and key exchange phase.In the following, we present the correctness of the equality in Step  (2)(b):(3)e^P,V=e^P,r+DID,1·W+DID,2=e^P,r+l+h·s·W+s·QID,2=e^P,r+l·W+h·s·W+s·QID,2=e^P,r+l·W+s·h·W+QID,2=e^P,r+l·W·e^P,s·h·W+QID,2=e^r+l·P,W·e^s·P,h·W+QID,2=e^U1+QID,1,W·e^Ppub,h·W+QID,2.On the other hand, we haveKS=KC since KS=s·U2=s·r·QID,2=r·DID,2=KC. And, in this case, we say that AuthS and AuthC are valid, and the client and the server have established a common session key SK.


## 4.1. System Setup Phase

Our system consists of a powerful serverS and some mobile clients. These clients refer to users with handheld devices. A client has access to the server through open channels, such as the Internet or wireless networks. The powerful server S is responsible for generating and distributing private keys to clients while providing services or applications. The server S is also responsible for generating the system parameters.In the phase, the serverS first generates two cyclic groups G1 and G2 of a large prime order q, an admissible bilinear map e^:G1×G1→G2, and a random generator P of G1, where G1 and G2 are additive and multiplicative groups, respectively. The server S then performs the following tasks:(1)
randomly select a system private keys∈Zq∗;(2)
compute the system public keyPpub=s·P;(3)
choose six cryptographic hash functionsH1,H2:0,1∗→G1 and f1,f2,f3,f4:0,1∗→0,1n, where n is a fixed length with 2n<q;(4)
publish public parameters and functions as(2)Params=G1,G2,q,P,e^,Ppub,H1,H2,f1,f2,f3,f4.


## 4.2. Key Extract Phase

In the key extract phase, a client submits its identityID to the server S and receives the corresponding private key DID. The key extract phase is depicted in Figure 1. We present the detailed procedures as follows.(1)
The client submits its identityID to the server S.(2)
Upon receiving a client’s identityID, the server chooses an ephemeral secret value l∈Zq∗ and computes QID,1=l·P, h=f1(ID,QID,1), DID,1=l+h·s, QID,2=H1(ID), and DID,2=s·QID,2.(3)
SetDID=(DID,1,DID,2,QID,1) and send it to the client via a secure channel.Figure 1
The key extract phase.


## 4.3. Mutual Authentication and Key Exchange Phase

Suppose that a client with identityID would like to communicate with the powerful server S and to access services of the server. As depicted in Figure 2, the detailed interactions between the client and the server are presented as below.(1)
The client with identityID performs offline computations in advance.
(a)
Random select an ephemeral secretr∈Zq∗.(b)
ComputeU1=r·P and U2=r·QID,2.(c)
ComputeW=H2(U1,U2) and V=(r+DID,1)·W+DID,2.(d)
SendID,U1,U2,V,QID,1 to the server.(2)
Upon receivingID,U1,U2,V,QID,1, the server S performs the following tasks.
(a)
ComputeW=H2(U1,U2), h=f1(ID,QID,1), and QID,2=H1(ID).(b)
Check whether the equalitye^(P,V)=e^(U1+QID,1,W)·e^(Ppub,h·W+QID,2) holds or not. If so, the server S accepts the request. Otherwise, the server terminates the process.(c)
Acquire a nonceN.(d)
ComputeKS=s·U2 and AuthS=f2(ID,U1,U2,V,N,KS).(e)
Finally, sendN,AuthS to the client.(3)
Upon receivingN,AuthS, the client authenticates the server S by performing the following tasks.
(a)
ComputeKC=r·DID,2.(b)
Check whether the equalityAuthS=f2(ID,U1,U2,V,N,KC) holds or not. If so, the client accepts the server S.(c)
ComputeAuthC=f3(ID,U1,U2,V,N,KC,AuthS).(d)
Compute a session keySK=f4(ID,U1,U2,V,N,KC,AuthS,AuthC).(e)
The client sendsAuthC to the serverS.(4)
Upon receivingAuthC, the server S authenticates and establishes a session key by performing the following tasks.
(a)
Check whether the equalityAuthC=f3(ID,U1,U2,V,N,KS,AuthS) holds or not. If so, the server accepts the client.(b)
Compute a session keySK=f4(ID,U1,U2,V,N,KS,AuthS,AuthC).Figure 2
The mutual authentication and key exchange phase.In the following, we present the correctness of the equality in Step  (2)(b):(3)e^P,V=e^P,r+DID,1·W+DID,2=e^P,r+l+h·s·W+s·QID,2=e^P,r+l·W+h·s·W+s·QID,2=e^P,r+l·W+s·h·W+QID,2=e^P,r+l·W·e^P,s·h·W+QID,2=e^r+l·P,W·e^s·P,h·W+QID,2=e^U1+QID,1,W·e^Ppub,h·W+QID,2.On the other hand, we haveKS=KC since KS=s·U2=s·r·QID,2=r·DID,2=KC. And, in this case, we say that AuthS and AuthC are valid, and the client and the server have established a common session key SK.


## 5. Security Analysis

In this section, we present the security analysis of our proposed protocol in the random oracle model [38, 39]. In the following, five theorems are given to prove that the proposed protocol achieves the security requirements of ESL-secure ID-AKE protocols for mobile client-server environments. These security requirements include client-to-server authentication, server-to-client authentication, key agreement, implicit key confirmation, and partial forward secrecy. In Theorems 8 and 10, we show that the proposed protocol provides the client-to-server and server-to-client authentications under ID, impersonation, and ephemeral-secret-leakage attacks, respectively. Hence, the proposed protocol offers mutual authentication. In Theorem 9, we will show that the proposed protocol provides secure key agreement under known-session-key attacks. Furthermore, the implicit key confirmation and partial forward secrecy are achieved by Theorems 11 and 12, respectively.


### 5.1. Client-to-Server Authentication

First, we prove that an adversary cannot impersonate a legitimate client to communicate with the server under the CDH assumption. We establish this by the methods similar to those in [24, 28], in which aSimulationB is employed to simulate all the queries and oracles which occurred in our proposed protocol. In the following, we use the notations ΠSi and ΠCj to indicate the ith instance of the server S and the jth instance of a clientC, respectively.Theorem 8.
Assume that a probabilistic polynomial-time (PPT) adversaryA can violate the client-to-server authentication with a nonnegligible advantage by making at most qS, qC, qH1, qH2, and qk queries, for k=1,…,4, respectively, to the ΠSi oracle of the server S and the ΠCj oracle of the client C, H1, H2, and fk, for k=1,…,4. Then there is a challenger B that can solve the CDH problem with a nonnegligible probability.Proof.
We assume that there is a probabilistic polynomial-time algorithmA with an advantage ɛ0 within time t0 to perform adaptive chosen message attacks, ID attacks, and ephemeral-secret-leakage attacks to our proposed protocol. By Lemma  1 in [12], A can break the protocol with an advantage ɛ≤ɛ0(1-1/q)/qH1 within running time t≤t0 under adaptive chosen message, ephemeral-secret-leakage, and fixed-ID attacks. Without loss of generality, we set IDT as the fixed target identity. If the oracle ΠSi of the server S accepts with no partner, it means that A has successfully impersonated the client C to the server S and violated the client-to-server authentication.
Next, we would like to construct an algorithmB to solve the CDH problem by appealing to A. Namely, upon receiving a random instance (P,aP,bP) in G1 with unknown a,b∈Zq∗, the algorithm B is able to derive abP by interacting with A. Here, we will adopt the methods similar to those in [24, 28] and Tseng et al.’s ESL-secure signature scheme [37] to achieve the client-to-server authentication. To simulate the actual situations, we employ the algorithm B (called Simulation B) to make the initialization and respond to A according to our protocol. (i)
Initialization: at first, SimulationB generates the system parameters G1,G2,q,P,e^ and sets the system public key Ppub=s·P, where s is the system private key. Simulation B then sends the public parameters to A. Simulation B maintains the lists LH1, LH2, and Lk, k=1,…,4, to respond consistently without collision to the hash queries H1, H2, and fk, k=1,…,4. These lists are initially empty.(ii)
f1(ID,QID,1): upon receiving such a query, the same response is given if the query has been asked before. Otherwise, B randomly selects a value r1∈0,1n, records the tuple (ID,QID,1,r1) in the list L1, and returns r1 to A.(iii)
f2(ID,U1,U2,V,N,K): upon receiving such a query, the same response is given if the query has been asked before. Otherwise, B randomly selects a value r2∈0,1n, records the tuple (ID,U1,U2,V,N,K,r2) in the list L2, and returns r2 to A.(iv)
f3(ID,U1,U2,V,N,K,AuthS): upon receiving such a query, the same response is given if the query has been asked before. Otherwise, B randomly selects a value r3∈0,1n, records the tuple (ID,U1,U2,V,N,K,AuthS,r3) in the list L3, and returns r3 to A.(v)
f4(ID,U1,U2,V,N,K,AuthS,AuthC): upon receiving such a query, the same response is given if the query has been asked before. Otherwise, B randomly selects a value r4∈0,1n, records the tuple (ID,U1,U2,V,N,K,AuthS,AuthC,r4) in L4, and returns r4 to A.(vi)
H1(ID): upon receiving such a query, the same response is given if the query has been asked before. Otherwise, B selects a random value w∈Zq∗ and sets QID,2=w·P-bP if ID=IDT; QID,2=w·P, otherwise. Simulation B records the tuple (ID,w,QID,2) in LH1 and returns QID,2 to A.(vii)
H2(U1,U2): upon receiving such a query, the same response is given if the query has been asked before. Otherwise, B selects a random value u∈Zq∗, records the tuple (U1,U2,W=u·bP) in LH2, and returns W to A.(viii)
Extract(ID); upon receiving such a query and ID≠IDT, B accesses to the corresponding tuples (ID,QID,1,r1) and (ID,w,QID,2) in the lists Lf1 and LH1, respectively. And then, Simulation B chooses a random value v and returns the private key DID=(DID,1=v,DID,2=w·Ppub,QID,1=v·P-r1·Ppub) to A. If ID=IDT, B aborts.(ix)
Ephemeral-secret-leakage(ΠCj): when A issues this query, B returns the ephemeral secret value r adopted in the corresponding session. This query models ephemeral-secret-leakage attacks. Note that A needs not to issue this query to the server S since, in our protocol, no ephemeral secret value is used on the server side.(x)
Send queries:there are four cases.
(1)
WhenA issues aSend(ΠCj, “start”), B uses the signing query in Tseng et al.’s ESL-secure signature scheme [37] to generate a valid signature ID,U1,U2,V,QID,1 for A.(2)
WhenA issues aSend(ΠSi,ID,U1,U2,V,QID,1) and ID≠IDT, B computes W=H2(U1,U2), h=f1(ID,QID,1), and QID,2=H1(ID) and checks whether the equality e^(P,V)=e^(U1+QID,1,W)·e^(Ppub,h·W+QID,2) holds. If the equality holds, B accepts the request, acquires a nonce N, and computes KS=s·U2=s·r·w·P=r·w·Ppub and AuthS=f2(ID,U1,U2,V,N,KS). Finally, B returns N,AuthS to A. Otherwise, B declines the request. On the other hand, if ID=IDT, B acquires a nonce N, selects a random value AuthS∈0,1n, and returns N,AuthS to A. In this case, A is unable to verify the validity of N,AuthS due to the lack of DID,2 and KC=r·DID,2.(3)
Upon receiving theSend(ΠCj,N,AuthS) withC’s identity ID distinct from IDT, B computes KC=r·w·Ppub=r·DID,2 and checks whether the equality AuthS=f2(ID,U1,U2,V,N,KC) holds. If the equality holds, the oracle ΠCj accepts the session. Then B computes AuthC=f3(ID,U1,U2,V,N,KC,AuthS) and returns AuthC to A. Otherwise, B declines the request. On the other hand, if ID=IDT, B selects a random value AuthC∈0,1n and returns AuthC to A. In this case, A is unable to verify the validity of AuthC due to the lack of DID,2 and KC=r·DID,2.(4)
WhenA makes aSend(ΠSi, AuthC), B checks whether AuthC=f3(ID,U1,U2,V,N,KS,AuthS) holds. If so, the oracle ΠSi accepts the session and terminates. Otherwise, the oracle ΠSi also terminates while not accepting.
By the responses to those queries above,B is perfectly indistinguishable from the proposed protocol. If A could violate the client-to-server authentication with a nonnegligible advantage, it would be required to send two valid messages ID,U1,U2,V,QID,1 and AuthC to the oracle ΠSi. In such a case, since ID,U1,U2,V,QID,1 is valid, it must satisfy the equality e^(P,V)=e^(U1+QID,1,W)·e^(Ppub,h·W+QID,2), where W=H2(U1,U2), h=f1(ID,QID,1), and QID,2=H1(ID). We also know that ID,U1,U2,V,QID,1 can be viewed as a signature on the message U2 as in Tseng et al.’s ESL-secure signature scheme [37]. Hence, if A can violate the client-to-server authentication, B can solve the CDH problem with a nonnegligible advantage by adopting the same approach in [37]. On the other hand, to generate a valid message AuthC, A must obtain DID,2 since AuthC is derived from KC which is exactly r·DID,2 (here, we assume that A can obtain the ephemeral secret value r via ESL attacks). This enables B to resolve the CDH problem (P,aP,bP) in G1 with unknown a,b∈Zq∗, namely, to evaluate abP by computing w·aP-DID,2 since w is a known value in the list LH1 and DID,2=a·QID,2 due to the tuple P,Ppub=aP,QID,2=w·P-bP. Therefore, the proposed protocol is secure against adaptive chosen message attacks, ID attacks, and ephemeral-secret-leakage attacks and provides the client-to-server authentication.


### 5.2. Key Agreement

In the following, we prove that the proposed protocol provides key agreement under the CDH assumption. SimulationB is used to simulate the actual situation in our protocol.Theorem 9.
Assume that a PPT adversaryA can guess the value b correctly involved in theTest query with a nonnegligible advantage by making at most qS, qC, qH1, qH2, and qk queries, for k=1,…,4, respectively, to the ΠSi oracle of the server S and the ΠCj oracle of the client C, H1, H2, and fk for k=1,…,4. Then there is a challenger B that can solve the CDH problem with a nonnegligible advantage.Proof.
Firstly, we know that the adversaryA can guess the unbiased coin b correctly with the probability 1/2 in theTestquery. Let the symbol Osk denote the event that A obtains the correct session key. Assume that A can guess the value b correctly with a nonnegligible advantage ε.Hence, A obtains the correct session key with the advantage Pr[Osk]≥ε/2.
Without loss of generality, we denote by the symbols Test(ΠCj) and Test(ΠSi), respectively, the successful events of obtaining the correct session key in theTestquery to the client and the server. Note that A can issue theTestquery to the client or the server. Because the client actively connects to the server, we have the inequality (4)Pr⁡Osk∧TestΠSi∧EventC2S+Pr⁡Osk∧TestΠSi∧¬EventC2S+PrOsk∧TestΠCj≥ε2,where the symbol EventC2S is the event violating the client-to-server authentication. Also, let PrC2S denote the probability of the event EventC2S. Then, we have(5)PrOsk∧TestΠSi∧¬EventC2S+PrOsk∧TestΠCj≥ε2-PrC2S,for some instances i and j of the server S and the client C, respectively.
In the following simulation, we employ the algorithmB (called Simulation B) to make the initialization and to respond to A according to our proposed protocol. Without loss of generality, we set IDT as the fixed target identity. (i)
Initialization: at first,B generates the system parameters G1,G2,q,P,e^ and sets the system public key Ppub=s·P, where s is the system private key. Then B sends the public parameters to A and maintains the lists LH1,LH2,Lk, k=1,…,4, to respond consistently without collision to the hash queries H1, H2, and fk, k=1,…,4, respectively. These lists are initially empty.(ii)
Extract(ID): it is the same as in the proof of Theorem 8.(iii)
H1, H2, fkqueries(for k=1,…,4): they are the same as in the proof of Theorem 8.(iv)
Reveal(ΠUk): on receiving such a query, Simulation B returns the associated session key SK if the corresponding oracle accepts the session; otherwise, it returns a null value. This query addresses the known-key security in the sense that a compromised session key should not endanger other session keys.(v)
Ephemeral-secret-leakage(ΠCj): this query models ephemeral-secret-leakage attacks. When A issues this query, B returns the ephemeral secret value r adopted in the corresponding session.(vi)
Corrupt(ΠCj): this query models partial forward secrecy. The adversary A can issue this query to a client C to obtain its private key. Therefore, a compromised private key should not endanger previous session keys between the client and the server. Note that, as in [34, 35], A can issue eitherEphemeral-secret-leakagequery orCorruptquery, but not both.(vii)
Test(ΠUk): when the adversary A sends such a query, the oracle ΠUk flips an unbiased coin b. If b=1, then the oracle returns the session key SK; otherwise, it returns a random value. A is allowed to issue this query only once to the oracle ΠUk.
In the simulation above, SimulationB is perfectly indistinguishable from the proposed protocol unless the event EventC2S occurs. And, we can see that the event ∃j,Osk∧Test(ΠCj) is equal to the event ∃i,Osk∧Test(ΠSi)∧¬EventC2S so that we have Pr[Osk∧Test(ΠCj)]≥ε/2-PrC2S. Hence, by the simulation of the oracle ΠCj of the client C, we have (6)PrN∈Zq∗U1,U2,KC←G1SK=f4ID,U1,U2,V,N,KC,AuthS,AuthC∣N∈Zq∗U1,U2,KC⟵G1≥ε2-PrC2S.
Note that, ifε is nonnegligible, the probability ε/2-PrC2S is also nonnegligible since the probability PrC2S is negligible by Theorem 8. Also, A can obtain the ephemeral secret value r by the ESL attacks. Now, we assume that Ppub=aP and QID,2=bP. Then, we have U1=r·P and U2=r·QID,2=r·bP. Therefore, if A could obtain the session key SK with a nonnegligible probability, it means that A has obtained KC. In this case, given (U1,U2,Ppub)=(r·P,r·bP,aP), A has obtained KC=r·DID,2=r·abP. Thus, B can evaluate abP by computing r-1·KC so that B solves the CDH problem with a nonnegligible advantage.


### 5.3. Server-to-Client Authentication

In the following theorem, we prove that an adversary cannot impersonate the serverS to communicate with the client C under the CDH assumption.Theorem 10.
If a PPT adversaryA can violate the server-to-client authentication of our proposed protocol with a nonnegligible advantage, then there is a challenger B which can solve the CDH problem with a nonnegligible advantage.Proof.
Here, we employ an algorithmB (called Simulation B) to make the initialization and to respond to the adversary A according to our proposed protocol. As in the proof of Theorem 9, the Simulation B is perfectly indistinguishable unless the event EventC2S occurs. Since the probability PrC2S is negligible by Theorem 8, we can assume that EventC2S does not occur.
Let the symbolEventC2S denote the event violating the server-to-client authentication. If the event EventC2S occurs, there is an instance j of the client C which has accepted the session with no legal partner. Namely, the oracle ΠCj has issued (ID,U1,U2,V,QID,1) and received (N,AuthS), where the latter is not generated by an oracle ΠSi. Therefore, one of the following three cases must have happened.Case  1. The adversary A guessed the value AuthS correctly.Case  2. The values U2 occurred in other sessions.Case  3. A asked f2 for the tuple (ID,U1,U2,V,N,KS) with correct KS.Next, we discuss the probability for each of the three cases. It is obvious that the probability of Case  1 is less thanqC/2n and the probability of Case  2 is (qC/q)(qC-1), which is less than qC2/q. The probability of Case  3 can be denoted by Pr⁡[ID,U1,U2,V,N,KS∣U1,U2,Ppub∈G1,KS=s·U2]. Thus,(7)PrEventS2C∣¬EventC2S≤PrID,U1,U2,V,N,KS∣U1,U2∈G1,KS=s·U2+qC2n+qC2q.As before, A can obtain the ephemeral secret value r by the ESL attacks. Now, we assume that Ppub=sP and QID,2=wP. Then we have U1=r·P and U2=r·QID,2=r·wP with unknown s, w∈Zq∗. In this case, given (U1,U2,Ppub)=(r·P,r·wP,sP), A can compute KS=s·U2=r·swP with a nonnegligible probability. Therefore, if A could obtain the session keySK, it would be able to compute KS. In such a case, B can use A to obtainswP. Therefore, B can solve the CDH problem with a nonnegligible advantage.Hence, by assuming thatA can violate the server-to-client authentication with a nonnegligible advantage ɛ, B then solves the CDH problem with the advantage ɛ′≥ɛ-qC/2n-qC2/q. Therefore, under the CDH assumption, our proposed protocol provides the server-to-client authentication.


### 5.4. Implicit Key Confirmation

Theorem 11.
Under the CDH assumption, our proposed protocol offers implicit key confirmation in the random oracle model.Proof.
We say that an ID-AKE protocol providesimplicit key confirmation if the protocol assures that the server/client can compute a session key which no others can produce. By Theorems 8 and 10, the client and the server can authenticate each other in the random oracle model under the CDH assumption. In Theorem 9, we have proved that an adversary cannot compute the session key. Therefore, our proposed protocol provides implicit key confirmation.


### 5.5. Partial Forward Secrecy

Theorem 12.
Under the CDH assumption, our proposed protocol offers partial forward secrecy in the random oracle model.Proof.
If the adversaryA corrupts the secret key s of the server, then all the previous session keys can be recovered (from the transcripts) since A can then compute KS=s·U2 and SK=f4(ID,U1,U2,V,N,KS,AuthS,AuthC). On the other hand, we show that the corruption of a client does not help A to recover previous session keys. In Theorem 9, we allow A to issue theCorrupt(ID) and obtain DID=(DID,1,DID,2,QID,1). Since, in a session, aTest query is required to occur beforeCorruptquery, Theorem 9 still holds under aCorrupt query to the client. Therefore, our proposed protocol offers partial forward secrecy.


## 5.1. Client-to-Server Authentication

First, we prove that an adversary cannot impersonate a legitimate client to communicate with the server under the CDH assumption. We establish this by the methods similar to those in [24, 28], in which aSimulationB is employed to simulate all the queries and oracles which occurred in our proposed protocol. In the following, we use the notations ΠSi and ΠCj to indicate the ith instance of the server S and the jth instance of a clientC, respectively.Theorem 8.
Assume that a probabilistic polynomial-time (PPT) adversaryA can violate the client-to-server authentication with a nonnegligible advantage by making at most qS, qC, qH1, qH2, and qk queries, for k=1,…,4, respectively, to the ΠSi oracle of the server S and the ΠCj oracle of the client C, H1, H2, and fk, for k=1,…,4. Then there is a challenger B that can solve the CDH problem with a nonnegligible probability.Proof.
We assume that there is a probabilistic polynomial-time algorithmA with an advantage ɛ0 within time t0 to perform adaptive chosen message attacks, ID attacks, and ephemeral-secret-leakage attacks to our proposed protocol. By Lemma  1 in [12], A can break the protocol with an advantage ɛ≤ɛ0(1-1/q)/qH1 within running time t≤t0 under adaptive chosen message, ephemeral-secret-leakage, and fixed-ID attacks. Without loss of generality, we set IDT as the fixed target identity. If the oracle ΠSi of the server S accepts with no partner, it means that A has successfully impersonated the client C to the server S and violated the client-to-server authentication.
Next, we would like to construct an algorithmB to solve the CDH problem by appealing to A. Namely, upon receiving a random instance (P,aP,bP) in G1 with unknown a,b∈Zq∗, the algorithm B is able to derive abP by interacting with A. Here, we will adopt the methods similar to those in [24, 28] and Tseng et al.’s ESL-secure signature scheme [37] to achieve the client-to-server authentication. To simulate the actual situations, we employ the algorithm B (called Simulation B) to make the initialization and respond to A according to our protocol. (i)
Initialization: at first, SimulationB generates the system parameters G1,G2,q,P,e^ and sets the system public key Ppub=s·P, where s is the system private key. Simulation B then sends the public parameters to A. Simulation B maintains the lists LH1, LH2, and Lk, k=1,…,4, to respond consistently without collision to the hash queries H1, H2, and fk, k=1,…,4. These lists are initially empty.(ii)
f1(ID,QID,1): upon receiving such a query, the same response is given if the query has been asked before. Otherwise, B randomly selects a value r1∈0,1n, records the tuple (ID,QID,1,r1) in the list L1, and returns r1 to A.(iii)
f2(ID,U1,U2,V,N,K): upon receiving such a query, the same response is given if the query has been asked before. Otherwise, B randomly selects a value r2∈0,1n, records the tuple (ID,U1,U2,V,N,K,r2) in the list L2, and returns r2 to A.(iv)
f3(ID,U1,U2,V,N,K,AuthS): upon receiving such a query, the same response is given if the query has been asked before. Otherwise, B randomly selects a value r3∈0,1n, records the tuple (ID,U1,U2,V,N,K,AuthS,r3) in the list L3, and returns r3 to A.(v)
f4(ID,U1,U2,V,N,K,AuthS,AuthC): upon receiving such a query, the same response is given if the query has been asked before. Otherwise, B randomly selects a value r4∈0,1n, records the tuple (ID,U1,U2,V,N,K,AuthS,AuthC,r4) in L4, and returns r4 to A.(vi)
H1(ID): upon receiving such a query, the same response is given if the query has been asked before. Otherwise, B selects a random value w∈Zq∗ and sets QID,2=w·P-bP if ID=IDT; QID,2=w·P, otherwise. Simulation B records the tuple (ID,w,QID,2) in LH1 and returns QID,2 to A.(vii)
H2(U1,U2): upon receiving such a query, the same response is given if the query has been asked before. Otherwise, B selects a random value u∈Zq∗, records the tuple (U1,U2,W=u·bP) in LH2, and returns W to A.(viii)
Extract(ID); upon receiving such a query and ID≠IDT, B accesses to the corresponding tuples (ID,QID,1,r1) and (ID,w,QID,2) in the lists Lf1 and LH1, respectively. And then, Simulation B chooses a random value v and returns the private key DID=(DID,1=v,DID,2=w·Ppub,QID,1=v·P-r1·Ppub) to A. If ID=IDT, B aborts.(ix)
Ephemeral-secret-leakage(ΠCj): when A issues this query, B returns the ephemeral secret value r adopted in the corresponding session. This query models ephemeral-secret-leakage attacks. Note that A needs not to issue this query to the server S since, in our protocol, no ephemeral secret value is used on the server side.(x)
Send queries:there are four cases.
(1)
WhenA issues aSend(ΠCj, “start”), B uses the signing query in Tseng et al.’s ESL-secure signature scheme [37] to generate a valid signature ID,U1,U2,V,QID,1 for A.(2)
WhenA issues aSend(ΠSi,ID,U1,U2,V,QID,1) and ID≠IDT, B computes W=H2(U1,U2), h=f1(ID,QID,1), and QID,2=H1(ID) and checks whether the equality e^(P,V)=e^(U1+QID,1,W)·e^(Ppub,h·W+QID,2) holds. If the equality holds, B accepts the request, acquires a nonce N, and computes KS=s·U2=s·r·w·P=r·w·Ppub and AuthS=f2(ID,U1,U2,V,N,KS). Finally, B returns N,AuthS to A. Otherwise, B declines the request. On the other hand, if ID=IDT, B acquires a nonce N, selects a random value AuthS∈0,1n, and returns N,AuthS to A. In this case, A is unable to verify the validity of N,AuthS due to the lack of DID,2 and KC=r·DID,2.(3)
Upon receiving theSend(ΠCj,N,AuthS) withC’s identity ID distinct from IDT, B computes KC=r·w·Ppub=r·DID,2 and checks whether the equality AuthS=f2(ID,U1,U2,V,N,KC) holds. If the equality holds, the oracle ΠCj accepts the session. Then B computes AuthC=f3(ID,U1,U2,V,N,KC,AuthS) and returns AuthC to A. Otherwise, B declines the request. On the other hand, if ID=IDT, B selects a random value AuthC∈0,1n and returns AuthC to A. In this case, A is unable to verify the validity of AuthC due to the lack of DID,2 and KC=r·DID,2.(4)
WhenA makes aSend(ΠSi, AuthC), B checks whether AuthC=f3(ID,U1,U2,V,N,KS,AuthS) holds. If so, the oracle ΠSi accepts the session and terminates. Otherwise, the oracle ΠSi also terminates while not accepting.
By the responses to those queries above,B is perfectly indistinguishable from the proposed protocol. If A could violate the client-to-server authentication with a nonnegligible advantage, it would be required to send two valid messages ID,U1,U2,V,QID,1 and AuthC to the oracle ΠSi. In such a case, since ID,U1,U2,V,QID,1 is valid, it must satisfy the equality e^(P,V)=e^(U1+QID,1,W)·e^(Ppub,h·W+QID,2), where W=H2(U1,U2), h=f1(ID,QID,1), and QID,2=H1(ID). We also know that ID,U1,U2,V,QID,1 can be viewed as a signature on the message U2 as in Tseng et al.’s ESL-secure signature scheme [37]. Hence, if A can violate the client-to-server authentication, B can solve the CDH problem with a nonnegligible advantage by adopting the same approach in [37]. On the other hand, to generate a valid message AuthC, A must obtain DID,2 since AuthC is derived from KC which is exactly r·DID,2 (here, we assume that A can obtain the ephemeral secret value r via ESL attacks). This enables B to resolve the CDH problem (P,aP,bP) in G1 with unknown a,b∈Zq∗, namely, to evaluate abP by computing w·aP-DID,2 since w is a known value in the list LH1 and DID,2=a·QID,2 due to the tuple P,Ppub=aP,QID,2=w·P-bP. Therefore, the proposed protocol is secure against adaptive chosen message attacks, ID attacks, and ephemeral-secret-leakage attacks and provides the client-to-server authentication.


## 5.2. Key Agreement

In the following, we prove that the proposed protocol provides key agreement under the CDH assumption. SimulationB is used to simulate the actual situation in our protocol.Theorem 9.
Assume that a PPT adversaryA can guess the value b correctly involved in theTest query with a nonnegligible advantage by making at most qS, qC, qH1, qH2, and qk queries, for k=1,…,4, respectively, to the ΠSi oracle of the server S and the ΠCj oracle of the client C, H1, H2, and fk for k=1,…,4. Then there is a challenger B that can solve the CDH problem with a nonnegligible advantage.Proof.
Firstly, we know that the adversaryA can guess the unbiased coin b correctly with the probability 1/2 in theTestquery. Let the symbol Osk denote the event that A obtains the correct session key. Assume that A can guess the value b correctly with a nonnegligible advantage ε.Hence, A obtains the correct session key with the advantage Pr[Osk]≥ε/2.
Without loss of generality, we denote by the symbols Test(ΠCj) and Test(ΠSi), respectively, the successful events of obtaining the correct session key in theTestquery to the client and the server. Note that A can issue theTestquery to the client or the server. Because the client actively connects to the server, we have the inequality (4)Pr⁡Osk∧TestΠSi∧EventC2S+Pr⁡Osk∧TestΠSi∧¬EventC2S+PrOsk∧TestΠCj≥ε2,where the symbol EventC2S is the event violating the client-to-server authentication. Also, let PrC2S denote the probability of the event EventC2S. Then, we have(5)PrOsk∧TestΠSi∧¬EventC2S+PrOsk∧TestΠCj≥ε2-PrC2S,for some instances i and j of the server S and the client C, respectively.
In the following simulation, we employ the algorithmB (called Simulation B) to make the initialization and to respond to A according to our proposed protocol. Without loss of generality, we set IDT as the fixed target identity. (i)
Initialization: at first,B generates the system parameters G1,G2,q,P,e^ and sets the system public key Ppub=s·P, where s is the system private key. Then B sends the public parameters to A and maintains the lists LH1,LH2,Lk, k=1,…,4, to respond consistently without collision to the hash queries H1, H2, and fk, k=1,…,4, respectively. These lists are initially empty.(ii)
Extract(ID): it is the same as in the proof of Theorem 8.(iii)
H1, H2, fkqueries(for k=1,…,4): they are the same as in the proof of Theorem 8.(iv)
Reveal(ΠUk): on receiving such a query, Simulation B returns the associated session key SK if the corresponding oracle accepts the session; otherwise, it returns a null value. This query addresses the known-key security in the sense that a compromised session key should not endanger other session keys.(v)
Ephemeral-secret-leakage(ΠCj): this query models ephemeral-secret-leakage attacks. When A issues this query, B returns the ephemeral secret value r adopted in the corresponding session.(vi)
Corrupt(ΠCj): this query models partial forward secrecy. The adversary A can issue this query to a client C to obtain its private key. Therefore, a compromised private key should not endanger previous session keys between the client and the server. Note that, as in [34, 35], A can issue eitherEphemeral-secret-leakagequery orCorruptquery, but not both.(vii)
Test(ΠUk): when the adversary A sends such a query, the oracle ΠUk flips an unbiased coin b. If b=1, then the oracle returns the session key SK; otherwise, it returns a random value. A is allowed to issue this query only once to the oracle ΠUk.
In the simulation above, SimulationB is perfectly indistinguishable from the proposed protocol unless the event EventC2S occurs. And, we can see that the event ∃j,Osk∧Test(ΠCj) is equal to the event ∃i,Osk∧Test(ΠSi)∧¬EventC2S so that we have Pr[Osk∧Test(ΠCj)]≥ε/2-PrC2S. Hence, by the simulation of the oracle ΠCj of the client C, we have (6)PrN∈Zq∗U1,U2,KC←G1SK=f4ID,U1,U2,V,N,KC,AuthS,AuthC∣N∈Zq∗U1,U2,KC⟵G1≥ε2-PrC2S.
Note that, ifε is nonnegligible, the probability ε/2-PrC2S is also nonnegligible since the probability PrC2S is negligible by Theorem 8. Also, A can obtain the ephemeral secret value r by the ESL attacks. Now, we assume that Ppub=aP and QID,2=bP. Then, we have U1=r·P and U2=r·QID,2=r·bP. Therefore, if A could obtain the session key SK with a nonnegligible probability, it means that A has obtained KC. In this case, given (U1,U2,Ppub)=(r·P,r·bP,aP), A has obtained KC=r·DID,2=r·abP. Thus, B can evaluate abP by computing r-1·KC so that B solves the CDH problem with a nonnegligible advantage.


## 5.3. Server-to-Client Authentication

In the following theorem, we prove that an adversary cannot impersonate the serverS to communicate with the client C under the CDH assumption.Theorem 10.
If a PPT adversaryA can violate the server-to-client authentication of our proposed protocol with a nonnegligible advantage, then there is a challenger B which can solve the CDH problem with a nonnegligible advantage.Proof.
Here, we employ an algorithmB (called Simulation B) to make the initialization and to respond to the adversary A according to our proposed protocol. As in the proof of Theorem 9, the Simulation B is perfectly indistinguishable unless the event EventC2S occurs. Since the probability PrC2S is negligible by Theorem 8, we can assume that EventC2S does not occur.
Let the symbolEventC2S denote the event violating the server-to-client authentication. If the event EventC2S occurs, there is an instance j of the client C which has accepted the session with no legal partner. Namely, the oracle ΠCj has issued (ID,U1,U2,V,QID,1) and received (N,AuthS), where the latter is not generated by an oracle ΠSi. Therefore, one of the following three cases must have happened.Case  1. The adversary A guessed the value AuthS correctly.Case  2. The values U2 occurred in other sessions.Case  3. A asked f2 for the tuple (ID,U1,U2,V,N,KS) with correct KS.Next, we discuss the probability for each of the three cases. It is obvious that the probability of Case  1 is less thanqC/2n and the probability of Case  2 is (qC/q)(qC-1), which is less than qC2/q. The probability of Case  3 can be denoted by Pr⁡[ID,U1,U2,V,N,KS∣U1,U2,Ppub∈G1,KS=s·U2]. Thus,(7)PrEventS2C∣¬EventC2S≤PrID,U1,U2,V,N,KS∣U1,U2∈G1,KS=s·U2+qC2n+qC2q.As before, A can obtain the ephemeral secret value r by the ESL attacks. Now, we assume that Ppub=sP and QID,2=wP. Then we have U1=r·P and U2=r·QID,2=r·wP with unknown s, w∈Zq∗. In this case, given (U1,U2,Ppub)=(r·P,r·wP,sP), A can compute KS=s·U2=r·swP with a nonnegligible probability. Therefore, if A could obtain the session keySK, it would be able to compute KS. In such a case, B can use A to obtainswP. Therefore, B can solve the CDH problem with a nonnegligible advantage.Hence, by assuming thatA can violate the server-to-client authentication with a nonnegligible advantage ɛ, B then solves the CDH problem with the advantage ɛ′≥ɛ-qC/2n-qC2/q. Therefore, under the CDH assumption, our proposed protocol provides the server-to-client authentication.


## 5.4. Implicit Key Confirmation

Theorem 11.
Under the CDH assumption, our proposed protocol offers implicit key confirmation in the random oracle model.Proof.
We say that an ID-AKE protocol providesimplicit key confirmation if the protocol assures that the server/client can compute a session key which no others can produce. By Theorems 8 and 10, the client and the server can authenticate each other in the random oracle model under the CDH assumption. In Theorem 9, we have proved that an adversary cannot compute the session key. Therefore, our proposed protocol provides implicit key confirmation.


## 5.5. Partial Forward Secrecy

Theorem 12.
Under the CDH assumption, our proposed protocol offers partial forward secrecy in the random oracle model.Proof.
If the adversaryA corrupts the secret key s of the server, then all the previous session keys can be recovered (from the transcripts) since A can then compute KS=s·U2 and SK=f4(ID,U1,U2,V,N,KS,AuthS,AuthC). On the other hand, we show that the corruption of a client does not help A to recover previous session keys. In Theorem 9, we allow A to issue theCorrupt(ID) and obtain DID=(DID,1,DID,2,QID,1). Since, in a session, aTest query is required to occur beforeCorruptquery, Theorem 9 still holds under aCorrupt query to the client. Therefore, our proposed protocol offers partial forward secrecy.


## 6. Performance Comparisons and Discussions

For convenience, the following notations are used to analyze the performance:TGe: the executing time of a bilinear pairing operation e^:G1×G1→G2;TGmul: the executing time of a scalar multiplication in G1;Texp: the executing time of a modular exponential operation in G2;TGH: the executing time of a map-to-point hash function in G1;TGadd: the executing time of an addition in G1 or a multiplication in G2;TH: the executing time of a hash function;|σ|: the bit length of a transmission message σ.By the simulation results in [44, 45], TGe, TGmul, Texp, and TGH are more time-consuming than TGadd and TH, in which TGe is the most time-consuming operation. Here, we list the simulation result of pairing-based operations with a resource-constrained mobile device. Scott et al. [44] gave the computational costs needed for various pairing-based operations under the Philips HiPersmart card with the processor of maximum clock speed 36 MHz. For the Ate pairing system in [44], a popular and valid choice would be to use a supersingular curve over a finite field E(Fp), with p=512 bits and a large prime order q=160 bits. Table 1 lists the experimental data for related pairing-based operations on the Philips HiPersmart card.Table 1
Computational costs (in seconds) required for pairing-based operations.
T
G
e
T
G
mul
T
exp
⁡
HiPersmart (36 MHz)
0.38 s
0.13 s
0.07 sIn the following, we analyze the computational cost of the proposed protocol. In our protocol, the client side requires4TGmul+TGH and does not require any bilinear pairing operation. Furthermore, the client can perform offline computations in advance in Step  1 of the mutual authentication and key exchange phase described in Section 4.3. Hence, the mutual authentication and key exchange phase requires only TGmul for online computation on the client side. On the other hand, the server side performs Steps  2 and 4 to authenticate a client with a session key. It requires 3TGe+2TGmul+2TGH. As for the communicational cost, the bit length of communication between a client and the server is bounded by 4q+4G1.In Table2, we demonstrate the comparisons among Ni et al.’s protocol [35], Chuang and Tseng’s protocol [33], Islam’s protocol [36], and ours in terms of the computational cost, communicational cost, and ESL security. As mentioned in Section 1, both the proposed protocols of Ni et al. and Islam fulfill all basic security properties including ESL resistance, while Chuang and Tseng’s protocol cannot withstand ESL attacks. In Section 5, we have demonstrated that our protocol also fulfills all basic security properties including ESL resistance. Moreover, Chuang and Tseng’s protocol and ours only require TGmul for online computation on the client side. However, both protocols of Ni et al. and Islam still require two bilinear pairing operations. Hence, according to Table 2, our protocol withstands ESL attacks and possesses better performance.Table 2
Comparisons between some recently proposed protocols and ours.
Ni et al.’sprotocol [35]
Chuang and Tseng’s protocol [33]
Islam’s protocol [36]
Our protocol
Computational cost for each client (total)
6
T
G
e
+
2
T
G
mul
+
2
T
exp
⁡
4
T
G
mul
+
T
exp
⁡
2
T
G
e
+
4
T
G
mul
4
T
G
mul
+
T
G
H
Computational cost for each client (online)
2
T
G
e
+
T
G
mul
+
2
T
exp
⁡ (1.03 seconds)
T
G
mul (0.13 seconds)
2
T
G
e (0.76 seconds)
T
G
mul (0.13 seconds)
Computational cost for the server
6
T
G
e
+
2
T
G
mul
+
2
T
exp
⁡
2
T
G
e
+
3
T
G
mul
+
T
exp
⁡
2
T
G
e
+
4
T
G
mul
3
T
G
e
+
2
T
G
mul
+
2
T
G
H
Bit length of communication
2
|
q
|
+
2
|
G
1
|
+
2
|
G
2
|
4
|
q
|
+
3
|
G
1
|
5
|
q
|
+
6
|
G
1
|
4
|
q
|
+
4
|
G
1
|
Against ESL attacks
Yes
No
Yes
YesIn the following, let us discuss the relationship between our protocol and the extensible authentication protocol (EAP) for wireless networks [40–43]. Typically, the EAP standard or framework [40, 41] is viewed as an authentication framework independent of the underlying authentication technology. Under the EAP framework, many authentication protocols have been proposed, and each of them has various advantages and weaknesses. As in [42], our ESL-secure ID-AKE protocol might be viewed as an authentication method of the EAP framework, without relying on PKI (public key infrastructure). In such a case, there is no need for the management of certificates and the deployment of certification authority (CA).Most EAP authentication protocols lack identity protection or user anonymity. In this paper, we focus on optimizing the authentication process but do not address the issue of user anonymity. Indeed, as mentioned in Section1.2, Chuang and Tseng’s ID-AKA protocol [33] is suitable for general users (with a long validity period) and anonymous users (with a short validity period) as well. Generally, ID-based or certificate-based authentication protocols must rely on other techniques (e.g., Universal Subscriber Identity Module of cellular networks) to provide user anonymity [42]. In addition, the reader can refer to [43] for the privacy protection issue of authentication protocols in the EAP framework.


## 7. Conclusions

In the paper, we proposed an efficient ESL-secure ID-AKE protocol for mobile client-server environments. Under the CDH assumption, our protocol is provably secure to provide mutual authentication, key agreement, implicit key confirmation, partial forward secrecy, and resistance to the ESL attacks in the random oracle model. We adopt the imbalanced computation to reduce the computational cost required by a mobile client. In addition, a mobile client may perform offline precomputation to reduce the online computational cost. When compared with previously proposed ID-AKE protocols for mobile client-server environments, our protocol has higher security and better computational performance.



---

*Source: 898716-2015-05-21.xml*