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

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.

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 Section 2, 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

Let $G_1$ and $G_2$ be additive and multiplicative cyclic groups of large prime order q, respectively. A map $\widehat{e}:G_1\times G_1\to G_2$ is called an admissible bilinear map if it satisfies the following three conditions:

• (1)

bilinearity: for all $P,Q\in G_1$ and $a,b\in Z_q^{\ast }$ , we have $\widehat{e}(aP,bQ)=\widehat{e}{\left(P,Q\right)}^{ab}$ ;

(2)

nondegeneracy: for some $P,Q\in G_1$ , $\widehat{e}(P,Q)\ne 1$ holds;

(3)

computability: given $P,Q\in G_1$ , there is an efficient algorithm to compute $\widehat{e}(P,Q)$ .

Note that condition (1) implies that $\widehat{e}(P+Q,R)=\widehat{e}(P,R)·\widehat{e}(Q,R)$ and $\widehat{e}(P,Q+R)=\widehat{e}(P,Q)·\widehat{e}(P,R)$ , for $P,Q,R\in G_1$ . 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

Let $G_1$ , $G_2$ , and $\widehat{e}$ be defined as above. Here, we define a security assumption on which our scheme is based.

•  

Computational Diffie-Hellman (CDH) problem: given $P,aP,bP\in G_1$ for unknown $a,b\in Z_q^{\ast }$ , the CDH problem in $G_1$ is to compute $abP$ .

Definition 1.

The CDH assumption in $G_1$ is defined as follows. Given $P,aP,bP\in G_1$ for unknown $a,b\in Z_q^{\ast }$ , no probabilistic polynomial-time (PPT) adversary $\mathcal{A}$ can compute $abP$ with a nonnegligible probability. The successful probability (advantage) of the adversary $\mathcal{A}$ is presented as

$$\begin{array}{cc}& {\mathrm{A}\mathrm{d}\mathrm{v}}_{\mathcal{A}}=\mathrm{P}\mathrm{r}\left[\mathcal{A}\left(P,aP,bP\right)=abP\hspace{0.17em}|\hspace{0.17em}P\in G_{\mathrm{1}},\hspace{0.17em}a,b\in Z_q^{\ast }\right],\end{array}$$

(1)

where the probability is measured over the random choices of $a,b\in Z_q^{\ast }$ consumed by $\mathcal{A}$ .

2.3. Notations

For convenience, the system parameters, notations, and functions used throughout this paper are defined as follows:

•   

$\widehat{e}$ : an admissible bilinear map from $G_1\times G_1$ into $G_2$ ;

  

P: a generator of the group $G_1$ ;

  

s: the system private key s randomly chosen from $Z_q^{\ast }$ ;

  

$P_{\mathrm{p}\mathrm{u}\mathrm{b}}$ : the system public key defined by $P_{\mathrm{p}\mathrm{u}\mathrm{b}}=s·P$ ;

  

$\mathrm{I}\mathrm{D}$ : the identity of a client;

  

$D_{\mathrm{I}\mathrm{D}}$ : the private key of the client $\mathrm{I}\mathrm{D}$ ;

  

$f_1()$ , $f_2()$ , $f_3()$ , $f_4()$ : one-way hash functions mapping from ${\left\{\mathrm{0,1}\right\}}^{\ast }$ into ${\left\{\mathrm{0,1}\right\}}^n$ , where n is a fixed length with $2^n<q$ ;

  

$H_1(),H_2()$ : map-to-point hash functions mapping from ${\left\{\mathrm{0,1}\right\}}^{\ast }$ into $G_1$ .

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 adversary $\mathcal{A}$ 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\in \{C,S\}$ by ${\Pi }_U^k$ , where C and S indicate a client and the powerful server, respectively.

Hash Queries $(M)$ . The oracle ${\Pi }_U^k$ 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 ${\Pi }_U^k$ selects a random value D, records the pair $(M,D)$ in the list, and returns D to the adversary $\mathcal{A}$ .

• (i)

Extract  (ID): upon receiving such a query, the oracle ${\Pi }_U^k$ computes the private key $D_{\mathrm{I}\mathrm{D}}$ associated with $\mathrm{I}\mathrm{D}$ and returns it to the adversary $\mathcal{A}$ . This query models ID attacks.

(ii)

Send   $({\Pi }_U^k,M)$ : upon receiving such a query, the oracle ${\Pi }_U^k$ executes the protocol according to M and responds the corresponding results to the adversary $\mathcal{A}$ . This query models passive attacks.

(iii)

Reveal   $({\Pi }_U^k)$ : upon receiving such a query, the oracle ${\Pi }_U^k$ outputs the corresponding session key SK if the oracle has accepted the session; otherwise, it returns a null value. This query addresses the known-session-key security, in the sense that a compromised session key should not endanger other session keys.

(iv)

Ephemeral-secret-leakage  ( ${\Pi }_C^k$ ): this query models ephemeral-secret-leakage attacks. When the adversary $\mathcal{A}$ issues this query, the oracle ${\Pi }_C^k$ returns the used ephemeral secret values (or random values) in the corresponding session. Note that, in our adversarial model, $\mathcal{A}$ is forbidden to issue this type of query on the server S.

(v)

Corrupt  ( ${\Pi }_C^k$ ): this query models partial forward secrecy. The adversary $\mathcal{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 $\mathcal{A}$ can issue Ephemeral-secret-leakage query or Corrupt query, but not both.

(vi)

Test  ( ${\Pi }_U^k$ ): when the adversary $\mathcal{A}$ sends such a query, the oracle flips an unbiased coin b. If $b=1$ , then the oracle ${\Pi }_U^k$ returns the session key SK; otherwise, it returns a random value. $\mathcal{A}$ is allowed to issue such a query only once to the oracle ${\Pi }_U^k$ .

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 ${\Pi }_C^k$ and ${\Pi }_S^t$ are partners if they can authenticate mutually and accept a common session key.

Definition 3 (freshness).

An oracle ${\Pi }_C^k$ with partner ${\Pi }_S^t$ is fresh if the following conditions hold:

• (1)

${\Pi }_C^k$ and ${\Pi }_S^t$ accept a session key $\mathrm{S}\mathrm{K}\ne \mathrm{N}\mathrm{U}\mathrm{L}\mathrm{L}$ while both of them are not requested by Reveal query;

(2)

no Corrupt query can be issued before the query Send  $({\Pi }_C^k,M)$ or query Send  $({\Pi }_S^t,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 adversary $\mathcal{A}$ has a nonnegligible advantage in the following game played between $\mathcal{A}$ and a set of oracles ${\Pi }_U^k$ , where $U\in \{C,S\}$ .

• (1)

The adversary $\mathcal{A}$ 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)

No Reveal ( ${\Pi }_U^k$ ) or Corrupt ( ${\Pi }_U^k$ ) can be issued before the Test ( ${\Pi }_U^k$ ) is asked.

(4)

The adversary $\mathcal{A}$ can issue Ephemeral-secret-leakage ( ${\Pi }_C^k$ ) or Corrupt ( ${\Pi }_C^k$ ), but not both.

(5)

The adversary $\mathcal{A}$ may adaptively make further queries before Test ( ${\Pi }_U^k$ ), where ${\Pi }_U^k$ must be fresh. Finally, $\mathcal{A}$ outputs its guess for the bit b which has been previously chosen in the Test ( ${\Pi }_U^k$ ).

Definition 5 (advantage).

Let Succ denote the event that $\mathcal{A}$ correctly guesses the bit b chosen in the Test query. If $\mathcal{A}$ asks a Test ( ${\Pi }_U^k$ ) and guesses the bit b, the successful advantage (probability) of $\mathcal{A}$ in attacking the ESL-secure ID-AKE protocol $\mathcal{P}$ is defined as ${\mathrm{A}\mathrm{d}\mathrm{v}}_{\mathcal{P}}(\mathcal{A})=\left|2·\mathrm{P}\mathrm{r}\left[\mathrm{S}\mathrm{u}\mathrm{c}\mathrm{c}\right]-1\right|$ . One says that the ESL-secure ID-AKE protocol $\mathcal{P}$ is secure if ${\mathrm{A}\mathrm{d}\mathrm{v}}_{\mathcal{P}}(\mathcal{A})$ is negligible.

Definition 6 (partial forward secrecy).

An ESL-secure ID-AKE protocol $\mathcal{P}$ provides partial forward secrecy if any adversary $\mathcal{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 server S 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 server S first generates two cyclic groups $G_1$ and $G_2$ of a large prime order q, an admissible bilinear map $\widehat{e}:G_1\times G_1\to G_2$ , and a random generator P of $G_1$ , where $G_1$ and $G_2$ are additive and multiplicative groups, respectively. The server S then performs the following tasks:

• (1)

randomly select a system private key $s\in Z_q^{\ast }$ ;

(2)

compute the system public key $P_{\mathrm{p}\mathrm{u}\mathrm{b}}=s·P$ ;

(3)

choose six cryptographic hash functions $H_1,H_2:{\left\{\mathrm{0,1}\right\}}^{\ast }\to G_1$ and $f_1,f_2,f_3,f_4:{\left\{\mathrm{0,1}\right\}}^{\ast }\to {\left\{\mathrm{0,1}\right\}}^n$ , where n is a fixed length with $2^n<q$ ;

(4)

publish public parameters and functions as

$$\begin{array}{cc}& \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s}=〈G_{\mathrm{1}},G_{\mathrm{2}},q,P,\widehat{e},P_{\mathrm{p}\mathrm{u}\mathrm{b}},H_{\mathrm{1}},H_{\mathrm{2}},f_{\mathrm{1}},f_{\mathrm{2}},f_{\mathrm{3}},f_{\mathrm{4}}〉.\end{array}$$

(2)

4.2. Key Extract Phase

In the key extract phase, a client submits its identity $\mathrm{I}\mathrm{D}$ to the server S and receives the corresponding private key $D_{\mathrm{I}\mathrm{D}}$ . The key extract phase is depicted in Figure 1. We present the detailed procedures as follows.

• (1)

The client submits its identity $\mathrm{I}\mathrm{D}$ to the server S.

(2)

Upon receiving a client's identity $\mathrm{I}\mathrm{D}$ , the server chooses an ephemeral secret value $l\in Z_q^{\ast }$ and computes $Q_{\mathrm{I}\mathrm{D},\mathrm{1}}=l·P$ , $h=f_1(\mathrm{I}\mathrm{D},Q_{\mathrm{I}\mathrm{D},1})$ , $D_{\mathrm{I}\mathrm{D},\mathrm{1}}=l+h·s$ , $Q_{\mathrm{I}\mathrm{D},\mathrm{2}}=H_1(\mathrm{I}\mathrm{D})$ , and $D_{\mathrm{I}\mathrm{D},\mathrm{2}}=s·Q_{\mathrm{I}\mathrm{D},\mathrm{2}}$ .

(3)

Set $D_{\mathrm{I}\mathrm{D}}=(D_{\mathrm{I}\mathrm{D},\mathrm{1}},D_{\mathrm{I}\mathrm{D},\mathrm{2}},Q_{\mathrm{I}\mathrm{D},\mathrm{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 identity $\mathrm{I}\mathrm{D}$ 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 identity $\mathrm{I}\mathrm{D}$ performs offline computations in advance.

• (a)

Random select an ephemeral secret $r\in Z_q^{\ast }$ .

(b)

Compute $U_1=r·P$ and $U_2=r·Q_{\mathrm{I}\mathrm{D},\mathrm{2}}$ .

(c)

Compute $W=H_2(U_1,U_2)$ and $V=(r+D_{\mathrm{I}\mathrm{D},\mathrm{1}})·W+D_{\mathrm{I}\mathrm{D},\mathrm{2}}$ .

(d)

Send $〈\mathrm{I}\mathrm{D},U_1,U_2,V,Q_{\mathrm{I}\mathrm{D},\mathrm{1}}〉$ to the server.

(2)

Upon receiving $〈\mathrm{I}\mathrm{D},U_1,U_2,V,Q_{\mathrm{I}\mathrm{D},\mathrm{1}}〉$ , the server S performs the following tasks.

• (a)

Compute $W=H_2(U_1,U_2)$ , $h=f_1(\mathrm{I}\mathrm{D},Q_{\mathrm{I}\mathrm{D},\mathrm{1}})$ , and $Q_{\mathrm{I}\mathrm{D},\mathrm{2}}=H_1(\mathrm{I}\mathrm{D})$ .

(b)

Check whether the equality $\widehat{e}(P,V)=\widehat{e}(U_1+Q_{\mathrm{I}\mathrm{D},\mathrm{1}},W)·\widehat{e}(P_{\mathrm{p}\mathrm{u}\mathrm{b}},h·W+Q_{\mathrm{I}\mathrm{D},\mathrm{2}})$ holds or not. If so, the server S accepts the request. Otherwise, the server terminates the process.

(c)

Acquire a nonce N.

(d)

Compute $K_S=s·U_2$ and ${\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S=f_2(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K_S)$ .

(e)

Finally, send $〈N,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S〉$ to the client.

(3)

Upon receiving $〈N,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S〉$ , the client authenticates the server S by performing the following tasks.

• (a)

Compute $K_C=r·D_{\mathrm{I}\mathrm{D},\mathrm{2}}$ .

(b)

Check whether the equality ${\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S=f_2(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K_C)$ holds or not. If so, the client accepts the server S.

(c)

Compute ${\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C=f_3(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K_C,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S)$ .

(d)

Compute a session key $\mathrm{S}\mathrm{K}=f_4(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K_C,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C)$ .

(e)

The client sends $〈{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C〉$ to the server S.

(4)

Upon receiving $〈{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C〉$ , the server S authenticates and establishes a session key by performing the following tasks.

• (a)

Check whether the equality ${\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C=f_3(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K_S,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S)$ holds or not. If so, the server accepts the client.

(b)

Compute a session key $\mathrm{S}\mathrm{K}=f_4(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K_S,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C)$ .

Figure 2

The mutual authentication and key exchange phase.

In the following, we present the correctness of the equality in Step  (2)(b):

$$\begin{array}{l}\widehat{e}\left(P,V\right)=\widehat{e}\left(P,\left(r+D_{\mathrm{I}\mathrm{D},\mathrm{1}}\right)·W+D_{\mathrm{I}\mathrm{D},\mathrm{2}}\right)\\ =\widehat{e}\left(P,\left(r+l+h·s\right)·W+s·Q_{\mathrm{I}\mathrm{D},\mathrm{2}}\right)\\ =\widehat{e}\left(P,\left(r+l\right)·W+h·s·W+s·Q_{\mathrm{I}\mathrm{D},\mathrm{2}}\right)\\ =\widehat{e}\left(P,\left(r+l\right)·W+s·\left(h·W+Q_{\mathrm{I}\mathrm{D},\mathrm{2}}\right)\right)\\ =\widehat{e}\left(P,\left(r+l\right)·W\right)·\widehat{e}\left(P,s·\left(h·W+Q_{\mathrm{I}\mathrm{D},\mathrm{2}}\right)\right)\\ =\widehat{e}\left(\left(r+l\right)·P,W\right)·\widehat{e}\left(s·P,h·W+Q_{\mathrm{I}\mathrm{D},\mathrm{2}}\right)\\ =\widehat{e}\left(U_{\mathrm{1}}+Q_{\mathrm{I}\mathrm{D},\mathrm{1}},W\right)·\widehat{e}\left(P_{\mathrm{p}\mathrm{u}\mathrm{b}},h·W+Q_{\mathrm{I}\mathrm{D},\mathrm{2}}\right).\end{array}$$

(3)

On the other hand, we have $K_S=K_C$ since $K_S=s·U_2=s·r·Q_{\mathrm{I}\mathrm{D},\mathrm{2}}=r·D_{\mathrm{I}\mathrm{D},\mathrm{2}}=K_C$ . And, in this case, we say that ${\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S$ and ${\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C$ are valid, and the client and the server have established a common session key $\mathrm{S}\mathrm{K}$ .

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 a Simulation $\mathcal{B}$ is employed to simulate all the queries and oracles which occurred in our proposed protocol. In the following, we use the notations ${\Pi }_S^i$ and ${\Pi }_C^j$ to indicate the ith instance of the server S and the jth instance of a client C, respectively.

Theorem 8.

Assume that a probabilistic polynomial-time (PPT) adversary $\mathcal{A}$ can violate the client-to-server authentication with a nonnegligible advantage by making at most $q_S$ , $q_C$ , $q_{H1}$ , $q_{H2}$ , and $q_k$ queries, for $k=1,\dots ,4$ , respectively, to the ${\Pi }_S^i$ oracle of the server S and the ${\Pi }_C^j$ oracle of the client C, $H_{\mathrm{1}}$ , $H_{\mathrm{2}}$ , and $f_k$ , for $k=1,\dots ,4$ . Then there is a challenger $\mathcal{B}$ that can solve the CDH problem with a nonnegligible probability.

Proof.

We assume that there is a probabilistic polynomial-time algorithm $\mathcal{A}$ with an advantage ${\varepsilon }_0$ within time $t_0$ to perform adaptive chosen message attacks, $\mathrm{I}\mathrm{D}$ attacks, and ephemeral-secret-leakage attacks to our proposed protocol. By Lemma  1 in [12], $\mathcal{A}$ can break the protocol with an advantage $\varepsilon \le {\varepsilon }_0(1-1/q)/q_{H1}$ within running time $t\le t_0$ under adaptive chosen message, ephemeral-secret-leakage, and fixed- $\mathrm{I}\mathrm{D}$ attacks. Without loss of generality, we set ${\mathrm{I}\mathrm{D}}_T$ as the fixed target identity. If the oracle ${\Pi }_S^i$ of the server S accepts with no partner, it means that $\mathcal{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 algorithm $\mathcal{B}$ to solve the CDH problem by appealing to $\mathcal{A}$ . Namely, upon receiving a random instance $(P,aP,bP)$ in $G_1$ with unknown $a,b\in Z_q^{\ast }$ , the algorithm $\mathcal{B}$ is able to derive $abP$ by interacting with $\mathcal{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 $\mathcal{B}$ (called Simulation $\mathcal{B}$ ) to make the initialization and respond to $\mathcal{A}$ according to our protocol.

• (i)

Initialization: at first, Simulation $\mathcal{B}$ generates the system parameters $〈G_1,G_2,q,P,\widehat{e}〉$ and sets the system public key $P_{\mathrm{p}\mathrm{u}\mathrm{b}}=s·P$ , where s is the system private key. Simulation $\mathcal{B}$ then sends the public parameters to $\mathcal{A}$ . Simulation $\mathcal{B}$ maintains the lists $L_{H1}$ , $L_{H2}$ , and $L_k$ , $k=1,\dots ,4$ , to respond consistently without collision to the hash queries $H_1$ , $H_2$ , and $f_k$ , $k=1,\dots ,4$ . These lists are initially empty.

(ii)

$f_1(\mathrm{I}\mathrm{D},Q_{\mathrm{I}\mathrm{D},\mathrm{1}})$ : upon receiving such a query, the same response is given if the query has been asked before. Otherwise, $\mathcal{B}$ randomly selects a value $r_1\in {\left\{\mathrm{0,1}\right\}}^n$ , records the tuple $(\mathrm{I}\mathrm{D},Q_{\mathrm{I}\mathrm{D},\mathrm{1}},r_1)$ in the list $L_1$ , and returns $r_1$ to $\mathcal{A}$ .

(iii)

$f_2(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K)$ : upon receiving such a query, the same response is given if the query has been asked before. Otherwise, $\mathcal{B}$ randomly selects a value $r_2\in {\left\{0,1\right\}}^n$ , records the tuple $(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K,r_2)$ in the list $L_2$ , and returns $r_2$ to $\mathcal{A}$ .

(iv)

$f_3(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S)$ : upon receiving such a query, the same response is given if the query has been asked before. Otherwise, $\mathcal{B}$ randomly selects a value $r_3\in {\left\{0,1\right\}}^n$ , records the tuple $(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S,r_3$ ) in the list $L_3$ , and returns $r_3$ to $\mathcal{A}$ .

(v)

$f_4(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C)$ : upon receiving such a query, the same response is given if the query has been asked before. Otherwise, $\mathcal{B}$ randomly selects a value $r_4\in {\left\{\mathrm{0,1}\right\}}^n$ , records the tuple $(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C,r_4)$ in $L_4$ , and returns $r_4$ to $\mathcal{A}$ .

(vi)

$H_1(\mathrm{I}\mathrm{D})$ : upon receiving such a query, the same response is given if the query has been asked before. Otherwise, $\mathcal{B}$ selects a random value $w\in Z_q^{\ast }$ and sets $Q_{\mathrm{I}\mathrm{D},\mathrm{2}}=w·P-bP$ if $\mathrm{I}\mathrm{D}={\mathrm{I}\mathrm{D}}_T$ ; $Q_{\mathrm{I}\mathrm{D},\mathrm{2}}=w·P$ , otherwise. Simulation $\mathcal{B}$ records the tuple $(\mathrm{I}\mathrm{D},w,Q_{\mathrm{I}\mathrm{D},\mathrm{2}})$ in $L_{H1}$ and returns $Q_{\mathrm{I}\mathrm{D},\mathrm{2}}$ to $\mathcal{A}$ .

(vii)

$H_2(U_1,U_2)$ : upon receiving such a query, the same response is given if the query has been asked before. Otherwise, $\mathcal{B}$ selects a random value $u\in Z_q^{\ast }$ , records the tuple $(U_1,U_2,W=u·bP)$ in $L_{H2}$ , and returns W to $\mathcal{A}$ .

(viii)

Extract (ID); upon receiving such a query and $\mathrm{I}\mathrm{D}\ne {\mathrm{I}\mathrm{D}}_T$ , $\mathcal{B}$ accesses to the corresponding tuples $(\mathrm{I}\mathrm{D},Q_{\mathrm{I}\mathrm{D},\mathrm{1}},r_1)$ and $(\mathrm{I}\mathrm{D},w,Q_{\mathrm{I}\mathrm{D},\mathrm{2}})$ in the lists $L_{f_{\mathrm{1}}}$ and $L_{H_{\mathrm{1}}}$ , respectively. And then, Simulation $\mathcal{B}$ chooses a random value v and returns the private key $D_{\mathrm{I}\mathrm{D}}=(D_{\mathrm{I}\mathrm{D},\mathrm{1}}=v,D_{\mathrm{I}\mathrm{D},\mathrm{2}}=w·P_{\mathrm{p}\mathrm{u}\mathrm{b}},Q_{\mathrm{I}\mathrm{D},\mathrm{1}}=v·P-r_1·P_{\mathrm{p}\mathrm{u}\mathrm{b}})$ to $\mathcal{A}$ . If $\mathrm{I}\mathrm{D}={\mathrm{I}\mathrm{D}}_T$ , $\mathcal{B}$ aborts.

(ix)

Ephemeral-secret-leakage ( ${\Pi }_C^j$ ): when $\mathcal{A}$ issues this query, $\mathcal{B}$ returns the ephemeral secret value r adopted in the corresponding session. This query models ephemeral-secret-leakage attacks. Note that $\mathcal{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)

When $\mathcal{A}$ issues a Send ( ${\Pi }_C^j$ , “start”), $\mathcal{B}$ uses the signing query in Tseng et al.'s ESL-secure signature scheme [37] to generate a valid signature $〈\mathrm{I}\mathrm{D},U_1,U_2,V,Q_{\mathrm{I}\mathrm{D},\mathrm{1}}〉$ for $\mathcal{A}$ .

(2)

When $\mathcal{A}$ issues a Send ( ${\Pi }_S^i$ , $〈\mathrm{I}\mathrm{D},U_1,U_2,V,Q_{\mathrm{I}\mathrm{D},\mathrm{1}}〉$ ) and $\mathrm{I}\mathrm{D}\ne {\mathrm{I}\mathrm{D}}_T$ , $\mathcal{B}$ computes $W=H_2(U_1,U_2)$ , $h=f_1(\mathrm{I}\mathrm{D},Q_{\mathrm{I}\mathrm{D},\mathrm{1}})$ , and $Q_{\mathrm{I}\mathrm{D},\mathrm{2}}=H_1(\mathrm{I}\mathrm{D})$ and checks whether the equality $\widehat{e}(P,V)=\widehat{e}(U_1+Q_{\mathrm{I}\mathrm{D},\mathrm{1}},W)·\widehat{e}(P_{\mathrm{p}\mathrm{u}\mathrm{b}},h·W+Q_{\mathrm{I}\mathrm{D},\mathrm{2}})$ holds. If the equality holds, $\mathcal{B}$ accepts the request, acquires a nonce N, and computes $K_S=s·U_2=s·r·w·P=r·w·P_{\mathrm{p}\mathrm{u}\mathrm{b}}$ and ${\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S=f_2(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K_S)$ . Finally, $\mathcal{B}$ returns $〈N,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S〉$ to $\mathcal{A}$ . Otherwise, $\mathcal{B}$ declines the request. On the other hand, if $\mathrm{I}\mathrm{D}={\mathrm{I}\mathrm{D}}_T$ , $\mathcal{B}$ acquires a nonce N, selects a random value ${\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S\in {\left\{\mathrm{0,1}\right\}}^n$ , and returns $〈N,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S〉$ to $\mathcal{A}$ . In this case, $\mathcal{A}$ is unable to verify the validity of $〈N,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S〉$ due to the lack of $D_{\mathrm{I}\mathrm{D},\mathrm{2}}$ and $K_C=r·D_{\mathrm{I}\mathrm{D},\mathrm{2}}$ .

(3)

Upon receiving the Send  $({\Pi }_C^j,〈N,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S〉)$ with C's identity $\mathrm{I}\mathrm{D}$ distinct from ${\mathrm{I}\mathrm{D}}_T$ , $\mathcal{B}$ computes $K_C=r·w·P_{\mathrm{p}\mathrm{u}\mathrm{b}}=r·D_{\mathrm{I}\mathrm{D},\mathrm{2}}$ and checks whether the equality ${\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S=f_2(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K_C)$ holds. If the equality holds, the oracle ${\Pi }_C^j$ accepts the session. Then $\mathcal{B}$ computes ${\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C=f_3(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K_C,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S)$ and returns $〈{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C〉$ to $\mathcal{A}$ . Otherwise, $\mathcal{B}$ declines the request. On the other hand, if $\mathrm{I}\mathrm{D}={\mathrm{I}\mathrm{D}}_T$ , $\mathcal{B}$ selects a random value ${\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C\in {\left\{\mathrm{0,1}\right\}}^n$ and returns $〈{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C〉$ to $\mathcal{A}$ . In this case, $\mathcal{A}$ is unable to verify the validity of $〈{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C〉$ due to the lack of $D_{\mathrm{I}\mathrm{D},\mathrm{2}}$ and $K_C=r·D_{\mathrm{I}\mathrm{D},\mathrm{2}}$ .

(4)

When $\mathcal{A}$ makes a Send ( ${\Pi }_S^i$ , $〈{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C〉$ ), $\mathcal{B}$ checks whether ${\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C=f_3(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K_S,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S)$ holds. If so, the oracle ${\Pi }_S^i$ accepts the session and terminates. Otherwise, the oracle ${\Pi }_S^i$ also terminates while not accepting.

By the responses to those queries above, $\mathcal{B}$ is perfectly indistinguishable from the proposed protocol. If $\mathcal{A}$ could violate the client-to-server authentication with a nonnegligible advantage, it would be required to send two valid messages $〈\mathrm{I}\mathrm{D},U_1,U_2,V,Q_{\mathrm{I}\mathrm{D},\mathrm{1}}〉$ and $〈{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C〉$ to the oracle ${\Pi }_S^i$ . In such a case, since $〈\mathrm{I}\mathrm{D},U_1,U_2,V,Q_{\mathrm{I}\mathrm{D},\mathrm{1}}〉$ is valid, it must satisfy the equality $\widehat{e}(P,V)=\widehat{e}(U_1+Q_{\mathrm{I}\mathrm{D},\mathrm{1}},W)·\widehat{e}(P_{\mathrm{p}\mathrm{u}\mathrm{b}},h·W+Q_{\mathrm{I}\mathrm{D},\mathrm{2}}$ ), where $W=H_2(U_1,U_2)$ , $h=f_1(\mathrm{I}\mathrm{D},Q_{\mathrm{I}\mathrm{D},\mathrm{1}})$ , and $Q_{\mathrm{I}\mathrm{D},\mathrm{2}}=H_1(\mathrm{I}\mathrm{D})$ . We also know that $〈\mathrm{I}\mathrm{D},U_1,U_2,V,Q_{\mathrm{I}\mathrm{D},\mathrm{1}}〉$ can be viewed as a signature on the message $U_2$ as in Tseng et al.'s ESL-secure signature scheme [37]. Hence, if $\mathcal{A}$ can violate the client-to-server authentication, $\mathcal{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 $〈{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C〉$ , $\mathcal{A}$ must obtain $D_{\mathrm{I}\mathrm{D},\mathrm{2}}$ since $〈{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C〉$ is derived from $K_C$ which is exactly $r·D_{\mathrm{I}\mathrm{D},\mathrm{2}}$ (here, we assume that $\mathcal{A}$ can obtain the ephemeral secret value r via ESL attacks). This enables $\mathcal{B}$ to resolve the CDH problem $(P,aP,bP)$ in $G_1$ with unknown $a,b\in Z_q^{\ast }$ , namely, to evaluate $abP$ by computing $w·aP-D_{\mathrm{I}\mathrm{D},\mathrm{2}}$ since w is a known value in the list $L_{H1}$ and $D_{\mathrm{I}\mathrm{D},\mathrm{2}}=a·Q_{\mathrm{I}\mathrm{D},\mathrm{2}}$ due to the tuple $〈P,P_{\mathrm{p}\mathrm{u}\mathrm{b}}=aP,Q_{\mathrm{I}\mathrm{D},\mathrm{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. Simulation $\mathcal{B}$ is used to simulate the actual situation in our protocol.

Theorem 9.

Assume that a PPT adversary $\mathcal{A}$ can guess the value b correctly involved in the Test query with a nonnegligible advantage by making at most $q_S$ , $q_C$ , $q_{H\mathrm{1}}$ , $q_{H\mathrm{2}}$ , and $q_k$ queries, for $k=\mathrm{1},\dots ,\mathrm{4}$ , respectively, to the ${\Pi }_S^i$ oracle of the server S and the ${\Pi }_C^j$ oracle of the client C, $H_{\mathrm{1}}$ , $H_{\mathrm{2}}$ , and $f_k$ for $k=\mathrm{1},\dots ,\mathrm{4}$ . Then there is a challenger $\mathcal{B}$ that can solve the CDH problem with a nonnegligible advantage.

Proof.

Firstly, we know that the adversary $\mathcal{A}$ can guess the unbiased coin b correctly with the probability $1/2$ in the Test query. Let the symbol $\mathrm{O}\mathrm{s}\mathrm{k}$ denote the event that $\mathcal{A}$ obtains the correct session key. Assume that $\mathcal{A}$ can guess the value b correctly with a nonnegligible advantage ε. Hence, $\mathcal{A}$ obtains the correct session key with the advantage $\mathrm{P}\mathrm{r}[\mathrm{O}\mathrm{s}\mathrm{k}]\ge \epsilon /2$ .

Without loss of generality, we denote by the symbols Test  $({\Pi }_C^j)$ and Test  $({\Pi }_S^i)$ , respectively, the successful events of obtaining the correct session key in the Test query to the client and the server. Note that $\mathcal{A}$ can issue the Test query to the client or the server. Because the client actively connects to the server, we have the inequality

$$\begin{array}{l}\mathrm{Pr}\left[\mathrm{O}\mathrm{s}\mathrm{k}\wedge \mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}\left({\Pi }_S^i\right)\wedge \mathrm{E}\mathrm{v}\mathrm{e}\mathrm{n}{\mathrm{t}}^{C\mathrm{2}S}\right]\\ \hspace{1em}+\mathrm{Pr}\left[\mathrm{O}\mathrm{s}\mathrm{k}\wedge \mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}\left({\Pi }_S^i\right)\wedge \neg \mathrm{E}\mathrm{v}\mathrm{e}\mathrm{n}{\mathrm{t}}^{C\mathrm{2}S}\right]\\ \hspace{1em}+\mathrm{P}\mathrm{r}\left[\mathrm{O}\mathrm{s}\mathrm{k}\wedge \mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}\left({\Pi }_C^j\right)\right]\ge \frac{\epsilon }{\mathrm{2}},\end{array}$$

(4)

where the symbol $\mathrm{E}\mathrm{v}\mathrm{e}\mathrm{n}{\mathrm{t}}^{C\mathrm{2}S}$ is the event violating the client-to-server authentication. Also, let ${\mathrm{P}\mathrm{r}}_{C2S}$ denote the probability of the event $\mathrm{E}\mathrm{v}\mathrm{e}\mathrm{n}{\mathrm{t}}^{C\mathrm{2}S}$ . Then, we have

$$\begin{array}{l}\mathrm{P}\mathrm{r}\left[\mathrm{O}\mathrm{s}\mathrm{k}\wedge \mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}\left({\Pi }_S^i\right)\wedge \neg \mathrm{E}\mathrm{v}\mathrm{e}\mathrm{n}{\mathrm{t}}^{C\mathrm{2}S}\right]\\ \hspace{1em}+\mathrm{P}\mathrm{r}\left[\mathrm{O}\mathrm{s}\mathrm{k}\wedge \mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}\left({\Pi }_C^j\right)\right]\ge \frac{\epsilon }{\mathrm{2}}-\mathrm{P}{\mathrm{r}}_{C\mathrm{2}S},\end{array}$$

(5)

for some instances i and j of the server S and the client C, respectively.

In the following simulation, we employ the algorithm $\mathcal{B}$ (called Simulation $\mathcal{B}$ ) to make the initialization and to respond to $\mathcal{A}$ according to our proposed protocol. Without loss of generality, we set ${\mathrm{I}\mathrm{D}}_T$ as the fixed target identity.

• (i)

Initialization: at first, $\mathcal{B}$ generates the system parameters $〈G_1,G_2,q,P,\widehat{e}〉$ and sets the system public key $P_{\mathrm{p}\mathrm{u}\mathrm{b}}=s·P$ , where s is the system private key. Then $\mathcal{B}$ sends the public parameters to $\mathcal{A}$ and maintains the lists $L_{H1},L_{H2},L_k$ , $k=1,\dots ,4$ , to respond consistently without collision to the hash queries $H_1$ , $H_2$ , and $f_k$ , $k=1,\dots ,4$ , respectively. These lists are initially empty.

(ii)

Extract (ID): it is the same as in the proof of Theorem 8.

(iii)

$H_1$ , $H_2$ , $f_k$ queries (for $k=1,\dots ,4$ ): they are the same as in the proof of Theorem 8.

(iv)

Reveal ( ${\Pi }_U^k$ ): on receiving such a query, Simulation $\mathcal{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 ( ${\Pi }_C^j$ ): this query models ephemeral-secret-leakage attacks. When $\mathcal{A}$ issues this query, $\mathcal{B}$ returns the ephemeral secret value r adopted in the corresponding session.

(vi)

Corrupt ( ${\Pi }_C^j$ ): this query models partial forward secrecy. The adversary $\mathcal{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], $\mathcal{A}$ can issue either Ephemeral-secret-leakage query or Corrupt query, but not both.

(vii)

Test ( ${\Pi }_U^k$ ): when the adversary $\mathcal{A}$ sends such a query, the oracle ${\Pi }_U^k$ flips an unbiased coin b. If $b=1$ , then the oracle returns the session key SK; otherwise, it returns a random value. $\mathcal{A}$ is allowed to issue this query only once to the oracle ${\Pi }_U^k$ .

In the simulation above, Simulation $\mathcal{B}$ is perfectly indistinguishable from the proposed protocol unless the event $\mathrm{E}\mathrm{v}\mathrm{e}\mathrm{n}{\mathrm{t}}^{C\mathrm{2}S}$ occurs. And, we can see that the event $\exists j,\mathrm{O}\mathrm{s}\mathrm{k}\wedge \mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}\hspace{0.17em}({\Pi }_C^j)$ is equal to the event $\exists i,\mathrm{O}\mathrm{s}\mathrm{k}\wedge \mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}\hspace{0.17em}({\Pi }_S^i)\wedge \neg \mathrm{E}\mathrm{v}\mathrm{e}\mathrm{n}{\mathrm{t}}^{C\mathrm{2}S}$ so that we have $\mathrm{P}\mathrm{r}[\mathrm{O}\mathrm{s}\mathrm{k}\wedge \mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}\hspace{0.17em}({\Pi }_C^j)]\ge \epsilon /\mathrm{2}-\mathrm{P}{\mathrm{r}}_{C\mathrm{2}S}$ . Hence, by the simulation of the oracle ${\Pi }_C^j$ of the client C, we have

$$\begin{array}{l}\mathrm{P}\mathrm{r}\left[\phantom{\begin{array}{l}N\in {Z_q}^{\ast }\\ U_{\mathrm{1}},U_{\mathrm{2}},K_C\leftarrow G_{\mathrm{1}}\end{array}}\mathrm{S}\mathrm{K}=f_{\mathrm{4}}\left(\mathrm{I}\mathrm{D},U_{\mathrm{1}},U_{\mathrm{2}},V,N,K_C,\right.\right.\\ \left.\left.{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C\right)\hspace{0.17em}|\hspace{0.17em}\begin{array}{l}N\in Z_q^{\ast }\\ U_{\mathrm{1}},U_{\mathrm{2}},K_C⟵G_{\mathrm{1}}\end{array}\right]\\ \hspace{1em}\ge \frac{\epsilon }{\mathrm{2}}-\mathrm{P}{\mathrm{r}}_{C\mathrm{2}S}.\end{array}$$

(6)

Note that, if ε is nonnegligible, the probability $\epsilon /2-{\mathrm{P}\mathrm{r}}_{C2S}$ is also nonnegligible since the probability ${\mathrm{P}\mathrm{r}}_{C2S}$ is negligible by Theorem 8. Also, $\mathcal{A}$ can obtain the ephemeral secret value r by the ESL attacks. Now, we assume that $P_{\mathrm{p}\mathrm{u}\mathrm{b}}=aP$ and $Q_{\mathrm{I}\mathrm{D},\mathrm{2}}=bP$ . Then, we have $U_1=r·P$ and $U_2=r·Q_{\mathrm{I}\mathrm{D},\mathrm{2}}=r·bP$ . Therefore, if $\mathcal{A}$ could obtain the session key SK with a nonnegligible probability, it means that $\mathcal{A}$ has obtained $K_C$ . In this case, given $(U_1,U_2,P_{\mathrm{p}\mathrm{u}\mathrm{b}})=(r·P,r·bP,aP)$ , $\mathcal{A}$ has obtained $K_C=r·D_{\mathrm{I}\mathrm{D},\mathrm{2}}=r·abP$ . Thus, $\mathcal{B}$ can evaluate $abP$ by computing $r^{-1}·K_C$ so that $\mathcal{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 server S to communicate with the client C under the CDH assumption.

Theorem 10.

If a PPT adversary $\mathcal{A}$ can violate the server-to-client authentication of our proposed protocol with a nonnegligible advantage, then there is a challenger $\mathcal{B}$ which can solve the CDH problem with a nonnegligible advantage.

Proof.

Here, we employ an algorithm $\mathcal{B}$ (called Simulation $\mathcal{B}$ ) to make the initialization and to respond to the adversary $\mathcal{A}$ according to our proposed protocol. As in the proof of Theorem 9, the Simulation $\mathcal{B}$ is perfectly indistinguishable unless the event ${\mathrm{E}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{t}}^{C2S}$ occurs. Since the probability ${\mathrm{P}\mathrm{r}}_{C2S}$ is negligible by Theorem 8, we can assume that ${\mathrm{E}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{t}}^{C2S}$ does not occur.

Let the symbol ${\mathrm{E}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{t}}^{C2S}$ denote the event violating the server-to-client authentication. If the event ${\mathrm{E}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{t}}^{C2S}$ occurs, there is an instance j of the client C which has accepted the session with no legal partner. Namely, the oracle ${\Pi }_C^j$ has issued $(\mathrm{I}\mathrm{D},U_1,U_2,V,Q_{\mathrm{I}\mathrm{D},\mathrm{1}})$ and received $(N,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S)$ , where the latter is not generated by an oracle ${\Pi }_S^i$ . Therefore, one of the following three cases must have happened.

Case  1. The adversary $\mathcal{A}$ guessed the value ${\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S$ correctly.

Case  2. The values $U_2$ occurred in other sessions.

Case  3. $\mathcal{A}$ asked $f_2$ for the tuple $(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K_S)$ with correct $K_S$ .

Next, we discuss the probability for each of the three cases. It is obvious that the probability of Case  1 is less than $q_C/2^n$ and the probability of Case  2 is $(q_C/q)(q_C-1)$ , which is less than $q_C^2/q$ . The probability of Case  3 can be denoted by $\mathrm{P}\mathrm{r}[\left(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K_S\right)\hspace{0.17em}|\hspace{0.17em}{U}_1,U_2,P_{\mathrm{p}\mathrm{u}\mathrm{b}}\in G_1,K_S=s·U_2]$ . Thus,

$$\begin{array}{l}\mathrm{P}\mathrm{r}\left[\mathrm{E}\mathrm{v}\mathrm{e}\mathrm{n}{\mathrm{t}}^{S\mathrm{2}C}\hspace{0.17em}|\hspace{0.17em}\neg \mathrm{E}\mathrm{v}\mathrm{e}\mathrm{n}{\mathrm{t}}^{C\mathrm{2}S}\right]\\ \hspace{1em}\le \mathrm{P}\mathrm{r}\left[\left(\mathrm{I}\mathrm{D},U_{\mathrm{1}},U_{\mathrm{2}},V,N,K_S\right)\hspace{0.17em}|\hspace{0.17em}{U}_{\mathrm{1}},U_{\mathrm{2}}\in G_{\mathrm{1}},K_S=s·U_{\mathrm{2}}\right]\\ \hspace{1em}\hspace{1em}+\frac{q_C}{{\mathrm{2}}^n}+\frac{q_C^2}{q}.\end{array}$$

(7)

As before, $\mathcal{A}$ can obtain the ephemeral secret value r by the ESL attacks. Now, we assume that $P_{\mathrm{p}\mathrm{u}\mathrm{b}}=sP$ and $Q_{\mathrm{I}\mathrm{D},\mathrm{2}}=wP$ . Then we have $U_1=r·P$ and $U_2=r·Q_{\mathrm{I}\mathrm{D},\mathrm{2}}=r·wP$ with unknown s, $w\in Z_q^{\ast }$ . In this case, given $(U_1,U_2,P_{\mathrm{p}\mathrm{u}\mathrm{b}})=(r·P,r·wP,sP)$ , $\mathcal{A}$ can compute $K_S=s·U_2=r·swP$ with a nonnegligible probability. Therefore, if $\mathcal{A}$ could obtain the session key SK, it would be able to compute $K_S$ . In such a case, $\mathcal{B}$ can use $\mathcal{A}$ to obtain swP. Therefore, $\mathcal{B}$ can solve the CDH problem with a nonnegligible advantage.

Hence, by assuming that $\mathcal{A}$ can violate the server-to-client authentication with a nonnegligible advantage ɛ, $\mathcal{B}$ then solves the CDH problem with the advantage ${\varepsilon }^{\prime }\ge \varepsilon -q_C/2^n-q_C^2/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 provides implicit 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 adversary $\mathcal{A}$ corrupts the secret key s of the server, then all the previous session keys can be recovered (from the transcripts) since $\mathcal{A}$ can then compute $K_S=s·U_2$ and $\mathrm{S}\mathrm{K}=f_4(\mathrm{I}\mathrm{D},U_1,U_2,V,N,K_S,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_S,{\mathrm{A}\mathrm{u}\mathrm{t}\mathrm{h}}_C)$ . On the other hand, we show that the corruption of a client does not help $\mathcal{A}$ to recover previous session keys. In Theorem 9, we allow $\mathcal{A}$ to issue the Corrupt (ID) and obtain $D_{\mathrm{I}\mathrm{D}}=(D_{\mathrm{I}\mathrm{D},\mathrm{1}},D_{\mathrm{I}\mathrm{D},\mathrm{2}},Q_{\mathrm{I}\mathrm{D},\mathrm{1}})$ . Since, in a session, a Test query is required to occur before Corrupt query, Theorem 9 still holds under a Corrupt 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:

•   

$T{G}_e$ : the executing time of a bilinear pairing operation $\widehat{e}:G_1\times G_1\to G_2$ ;

  

$T{G}_{\mathrm{m}\mathrm{u}\mathrm{l}}$ : the executing time of a scalar multiplication in $G_1$ ;

  

$T_{\mathrm{e}\mathrm{x}\mathrm{p}}$ : the executing time of a modular exponential operation in $G_2$ ;

  

${TG}_H$ : the executing time of a map-to-point hash function in $G_1$ ;

  

${TG}_{\mathrm{a}\mathrm{d}\mathrm{d}}$ : the executing time of an addition in $G_1$ or a multiplication in $G_2$ ;

  

$T_H$ : the executing time of a hash function;

  

$\left|\sigma \right|$ : the bit length of a transmission message σ.

By the simulation results in [44, 45], $T{G}_e$ , $T{G}_{\mathrm{m}\mathrm{u}\mathrm{l}}$ , $T_{\mathrm{e}\mathrm{x}\mathrm{p}}$ , and $T{G}_H$ are more time-consuming than $T{G}_{\mathrm{a}\mathrm{d}\mathrm{d}}$ and $T_H$ , in which $T{G}_e$ 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(F_p)$ , 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}_{\text{mul}}$$	$$T_{\exp }$$
HiPersmart (36 MHz)	0.38 s	0.13 s	0.07 s

In the following, we analyze the computational cost of the proposed protocol. In our protocol, the client side requires $4T{G}_{\mathrm{m}\mathrm{u}\mathrm{l}}+T{G}_H$ 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 $T{G}_{\mathrm{m}\mathrm{u}\mathrm{l}}$ 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 $3T{G}_e+2T{G}_{\mathrm{m}\mathrm{u}\mathrm{l}}+2T{G}_H$ . As for the communicational cost, the bit length of communication between a client and the server is bounded by $4\left|q\right|+4\left|G_1\right|$ .

In Table 2, 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 $T{G}_{\mathrm{m}\mathrm{u}\mathrm{l}}$ 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.'s protocol [35]	Chuang and Tseng's protocol [33]	Islam's protocol [36]	Our protocol
Computational cost for each client (total)	$$6T{G}_e+2T{G}_{\text{mul}}+2T_{\exp }$$	$$4T{G}_{\text{mul}}+T_{\exp }$$	$$2T{G}_e+4T{G}_{\text{mul}}$$	$$4T{G}_{\text{mul}}+T{G}_H$$
Computational cost for each client (online)	$$2T{G}_e+T{G}_{\text{mul}}+2T_{\exp }$$   (1.03 seconds)	$$T{G}_{\text{mul}}$$   (0.13 seconds)	$$2T{G}_e$$   (0.76 seconds)	$$T{G}_{\text{mul}}$$   (0.13 seconds)
Computational cost for the server	$$6T{G}_e+2T{G}_{\text{mul}}+2T_{\exp }$$	$$2T{G}_e+3T{G}_{\text{mul}}+T_{\exp }$$	$$2T{G}_e+4T{G}_{\text{mul}}$$	$$3T{G}_e+2T{G}_{\text{mul}}+2T{G}_H$$
Bit length of communication	$$2\left|q\right|+2\left|G_1\right|+2\left|G_2\right|$$	$$4\left|q\right|+3\left|G_1\right|$$	$$5\left|q\right|+6\left|G_1\right|$$	$$4\left|q\right|+4\left|G_1\right|$$
Against ESL attacks	Yes	No	Yes	Yes

In 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 Section 1.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.