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 $\hat{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}^{*}$ , we have $\hat{e} (a P, b Q) = \hat{e} {(P, Q)}^{a b}$ ;

(2)

nondegeneracy: for some $P, Q \in G_{1}$ , $\hat{e} (P, Q) \neq 1$ holds;

(3)

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

Note that condition (1) implies that

\hat{e} (P + Q, R) = \hat{e} (P, R) \cdot \hat{e} (Q, R)

and

\hat{e} (P, Q + R) = \hat{e} (P, Q) \cdot \hat{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 $\hat{e}$ be defined as above. Here, we define a security assumption on which our scheme is based.

Computational Diffie-Hellman (CDH) problem: given $P, a P, b P \in G_{1}$ for unknown $a, b \in Z_{q}^{*}$ , the CDH problem in $G_{1}$ is to compute $a b P$ .

Definition 1.

The CDH assumption in $G_{1}$ is defined as follows. Given $P, a P, b P \in G_{1}$ for unknown $a, b \in Z_{q}^{*}$ , no probabilistic polynomial-time (PPT) adversary $A$ can compute $a b P$ with a nonnegligible probability. The successful probability (advantage) of the adversary $A$ is presented as

\begin{matrix} {A d v}_{A} = P r [A (P, a P, b P) = a b P | P \in G_{1}, a, b \in Z_{q}^{*}], \end{matrix}

(1)

where the probability is measured over the random choices of

a, b \in Z_{q}^{*}

consumed by

A

2.3. Notations

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

$\hat{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}^{*}$ ;

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

$I D$ : the identity of a client;

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

$f_{1} ()$ , $f_{2} ()$ , $f_{3} ()$ , $f_{4} ()$ : one-way hash functions mapping from ${\{0,1\}}^{*}$ into ${\{0,1\}}^{n}$ , where n is a fixed length with $2^{n} < q$ ;

$H_{1} (), H_{2} ()$ : map-to-point hash functions mapping from ${\{0,1\}}^{*}$ 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 $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 $Π_{U}^{k}$ , where C and S indicate a client and the powerful server, respectively.

Hash Queries $(M)$ . The oracle $Π_{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 $Π_{U}^{k}$ 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 $Π_{U}^{k}$ computes the private key $D_{I D}$ associated with $I D$ and returns it to the adversary $A$ . This query models ID attacks.

(ii)

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

(iii)

Reveal $(Π_{U}^{k})$ : upon receiving such a query, the oracle $Π_{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 ( $Π_{C}^{k}$ ): this query models ephemeral-secret-leakage attacks. When the adversary $A$ issues this query, the oracle $Π_{C}^{k}$ 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 ( $Π_{C}^{k}$ ): this query models partial 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 issue Ephemeral-secret-leakage query or Corrupt query, but not both.

(vi)

Test ( $Π_{U}^{k}$ ): when the adversary $A$ sends such a query, the oracle flips an unbiased coin b. If $b = 1$ , then the oracle $Π_{U}^{k}$ returns the session key SK; otherwise, it returns a random value. $A$ is allowed to issue such a query only once to the oracle $Π_{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 $Π_{C}^{k}$ and $Π_{S}^{t}$ are partners if they can authenticate mutually and accept a common session key.

Definition 3 (freshness).

An oracle $Π_{C}^{k}$ with partner $Π_{S}^{t}$ is fresh if the following conditions hold: (1)

$Π_{C}^{k}$ and $Π_{S}^{t}$ accept a session key $S K \neq N U L L$ while both of them are not requested by Reveal query;

(2)

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

The adversary $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 ( $Π_{U}^{k}$ ) or Corrupt ( $Π_{U}^{k}$ ) can be issued before the Test ( $Π_{U}^{k}$ ) is asked.

(4)

The adversary $A$ can issue Ephemeral-secret-leakage ( $Π_{C}^{k}$ ) or Corrupt ( $Π_{C}^{k}$ ), but not both.

(5)

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

Definition 5 (advantage).

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

Definition 6 (partial forward secrecy).

An ESL-secure ID-AKE protocol $P$ 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 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 $\hat{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}^{*}$ ;

(2)

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

(3)

choose six cryptographic hash functions $H_{1}, H_{2} : {\{0,1\}}^{*} \to G_{1}$ and $f_{1}, f_{2}, f_{3}, f_{4} : {\{0,1\}}^{*} \to {\{0,1\}}^{n}$ , where n is a fixed length with $2^{n} < q$ ;

(4)

publish public parameters and functions as

\begin{matrix} P a r a m s = 〈G_{1}, G_{2}, q, P, \hat{e}, P_{p u b}, H_{1}, H_{2}, f_{1}, f_{2}, f_{3}, f_{4}〉 . \end{matrix}

(2)

4.2. Key Extract Phase

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

The client submits its identity $I D$ to the server S.

(2)

Upon receiving a client's identity $I D$ , the server chooses an ephemeral secret value $l \in Z_{q}^{*}$ and computes $Q_{I D, 1} = l \cdot P$ , $h = f_{1} (I D, Q_{I D, 1})$ , $D_{I D, 1} = l + h \cdot s$ , $Q_{I D, 2} = H_{1} (I D)$ , and $D_{I D, 2} = s \cdot Q_{I D, 2}$ .

(3)

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

(a)

Random select an ephemeral secret $r \in Z_{q}^{*}$ .

(b)

Compute $U_{1} = r \cdot P$ and $U_{2} = r \cdot Q_{I D, 2}$ .

(c)

Compute $W = H_{2} (U_{1}, U_{2})$ and $V = (r + D_{I D, 1}) \cdot W + D_{I D, 2}$ .

(d)

Send $〈I D, U_{1}, U_{2}, V, Q_{I D, 1}〉$ to the server.

(2)

Upon receiving $〈I D, U_{1}, U_{2}, V, Q_{I D, 1}〉$ , the server S performs the following tasks.

(a)

Compute $W = H_{2} (U_{1}, U_{2})$ , $h = f_{1} (I D, Q_{I D, 1})$ , and $Q_{I D, 2} = H_{1} (I D)$ .

(b)

Check whether the equality $\hat{e} (P, V) = \hat{e} (U_{1} + Q_{I D, 1}, W) \cdot \hat{e} (P_{p u b}, h \cdot W + Q_{I D, 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 \cdot U_{2}$ and ${A u t h}_{S} = f_{2} (I D, U_{1}, U_{2}, V, N, K_{S})$ .

(e)

Finally, send $〈N, {A u t h}_{S}〉$ to the client.

(3)

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

(a)

Compute $K_{C} = r \cdot D_{I D, 2}$ .

(b)

Check whether the equality ${A u t h}_{S} = f_{2} (I D, U_{1}, U_{2}, V, N, K_{C})$ holds or not. If so, the client accepts the server S.

(c)

Compute ${A u t h}_{C} = f_{3} (I D, U_{1}, U_{2}, V, N, K_{C}, {A u t h}_{S})$ .

(d)

Compute a session key $S K = f_{4} (I D, U_{1}, U_{2}, V, N, K_{C}, {A u t h}_{S}, {A u t h}_{C})$ .

(e)

The client sends $〈{A u t h}_{C}〉$ to the server S.

(4)

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

(a)

Check whether the equality ${A u t h}_{C} = f_{3} (I D, U_{1}, U_{2}, V, N, K_{S}, {A u t h}_{S})$ holds or not. If so, the server accepts the client.

(b)

Compute a session key $S K = f_{4} (I D, U_{1}, U_{2}, V, N, K_{S}, {A u t h}_{S}, {A u t 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} \hat{e} (P, V) = \hat{e} (P, (r + D_{I D, 1}) \cdot W + D_{I D, 2}) \\ = \hat{e} (P, (r + l + h \cdot s) \cdot W + s \cdot Q_{I D, 2}) \\ = \hat{e} (P, (r + l) \cdot W + h \cdot s \cdot W + s \cdot Q_{I D, 2}) \\ = \hat{e} (P, (r + l) \cdot W + s \cdot (h \cdot W + Q_{I D, 2})) \\ = \hat{e} (P, (r + l) \cdot W) \cdot \hat{e} (P, s \cdot (h \cdot W + Q_{I D, 2})) \\ = \hat{e} ((r + l) \cdot P, W) \cdot \hat{e} (s \cdot P, h \cdot W + Q_{I D, 2}) \\ = \hat{e} (U_{1} + Q_{I D, 1}, W) \cdot \hat{e} (P_{p u b}, h \cdot W + Q_{I D, 2}) . \end{array}

(3)

On the other hand, we have $K_{S} = K_{C}$ since $K_{S} = s \cdot U_{2} = s \cdot r \cdot Q_{I D, 2} = r \cdot D_{I D, 2} = K_{C}$ . And, in this case, we say that ${A u t h}_{S}$ and ${A u t h}_{C}$ are valid, and the client and the server have established a common session key $S 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 $B$ is employed to simulate all the queries and oracles which occurred in our proposed protocol. In the following, we use the notations $Π_{S}^{i}$ and $Π_{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 $A$ can violate the client-to-server authentication with a nonnegligible advantage by making at most $q_{S}$ , $q_{C}$ , $q_{H 1}$ , $q_{H 2}$ , and $q_{k}$ queries, for $k = 1, \dots, 4$ , respectively, to the $Π_{S}^{i}$ oracle of the server S and the $Π_{C}^{j}$ oracle of the client C, $H_{1}$ , $H_{2}$ , and $f_{k}$ , for $k = 1, \dots, 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 algorithm $A$ with an advantage $ɛ_{0}$ within time $t_{0}$ to perform adaptive chosen message attacks, $I D$ attacks, and ephemeral-secret-leakage attacks to our proposed protocol. By Lemma 1 in [12], $A$ can break the protocol with an advantage $ɛ \leq ɛ_{0} (1 - 1 / q) / q_{H 1}$ within running time $t \leq t_{0}$ under adaptive chosen message, ephemeral-secret-leakage, and fixed- $I D$ attacks. Without loss of generality, we set ${I D}_{T}$ as the fixed target identity. If the oracle $Π_{S}^{i}$ 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 algorithm $B$ to solve the CDH problem by appealing to $A$ . Namely, upon receiving a random instance $(P, a P, b P)$ in $G_{1}$ with unknown $a, b \in Z_{q}^{*}$ , the algorithm $B$ is able to derive $a b P$ 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, Simulation $B$ generates the system parameters $〈G_{1}, G_{2}, q, P, \hat{e}〉$ and sets the system public key $P_{p u b} = s \cdot P$ , where s is the system private key. Simulation $B$ then sends the public parameters to $A$ . Simulation $B$ maintains the lists $L_{H 1}$ , $L_{H 2}$ , 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} (I D, Q_{I D, 1})$ : upon receiving such a query, the same response is given if the query has been asked before. Otherwise, $B$ randomly selects a value $r_{1} \in {\{0,1\}}^{n}$ , records the tuple $(I D, Q_{I D, 1}, r_{1})$ in the list $L_{1}$ , and returns $r_{1}$ to $A$ .

(iii)

$f_{2} (I 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, $B$ randomly selects a value $r_{2} \in {\{0, 1\}}^{n}$ , records the tuple $(I D, U_{1}, U_{2}, V, N, K, r_{2})$ in the list $L_{2}$ , and returns $r_{2}$ to $A$ .

(iv)

$f_{3} (I D, U_{1}, U_{2}, V, N, K, {A u t h}_{S})$ : upon receiving such a query, the same response is given if the query has been asked before. Otherwise, $B$ randomly selects a value $r_{3} \in {\{0, 1\}}^{n}$ , records the tuple $(I D, U_{1}, U_{2}, V, N, K, {A u t h}_{S}, r_{3}$ ) in the list $L_{3}$ , and returns $r_{3}$ to $A$ .

(v)

$f_{4} (I D, U_{1}, U_{2}, V, N, K, {A u t h}_{S}, {A u t h}_{C})$ : upon receiving such a query, the same response is given if the query has been asked before. Otherwise, $B$ randomly selects a value $r_{4} \in {\{0,1\}}^{n}$ , records the tuple $(I D, U_{1}, U_{2}, V, N, K, {A u t h}_{S}, {A u t h}_{C}, r_{4})$ in $L_{4}$ , and returns $r_{4}$ to $A$ .

(vi)

$H_{1} (I D)$ : upon receiving such a query, the same response is given if the query has been asked before. Otherwise, $B$ selects a random value $w \in Z_{q}^{*}$ and sets $Q_{I D, 2} = w \cdot P - b P$ if $I D = {I D}_{T}$ ; $Q_{I D, 2} = w \cdot P$ , otherwise. Simulation $B$ records the tuple $(I D, w, Q_{I D, 2})$ in $L_{H 1}$ and returns $Q_{I D, 2}$ to $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, $B$ selects a random value $u \in Z_{q}^{*}$ , records the tuple $(U_{1}, U_{2}, W = u \cdot b P)$ in $L_{H 2}$ , and returns W to $A$ .

(viii)

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

(ix)

Ephemeral-secret-leakage ( $Π_{C}^{j}$ ): 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)

When $A$ issues a Send ( $Π_{C}^{j}$ , “start”), $B$ uses the signing query in Tseng et al.'s ESL-secure signature scheme [37] to generate a valid signature $〈I D, U_{1}, U_{2}, V, Q_{I D, 1}〉$ for $A$ .

(2)

When $A$ issues a Send ( $Π_{S}^{i}$ , $〈I D, U_{1}, U_{2}, V, Q_{I D, 1}〉$ ) and $I D \neq {I D}_{T}$ , $B$ computes $W = H_{2} (U_{1}, U_{2})$ , $h = f_{1} (I D, Q_{I D, 1})$ , and $Q_{I D, 2} = H_{1} (I D)$ and checks whether the equality $\hat{e} (P, V) = \hat{e} (U_{1} + Q_{I D, 1}, W) \cdot \hat{e} (P_{p u b}, h \cdot W + Q_{I D, 2})$ holds. If the equality holds, $B$ accepts the request, acquires a nonce N, and computes $K_{S} = s \cdot U_{2} = s \cdot r \cdot w \cdot P = r \cdot w \cdot P_{p u b}$ and ${A u t h}_{S} = f_{2} (I D, U_{1}, U_{2}, V, N, K_{S})$ . Finally, $B$ returns $〈N, {A u t h}_{S}〉$ to $A$ . Otherwise, $B$ declines the request. On the other hand, if $I D = {I D}_{T}$ , $B$ acquires a nonce N, selects a random value ${A u t h}_{S} \in {\{0,1\}}^{n}$ , and returns $〈N, {A u t h}_{S}〉$ to $A$ . In this case, $A$ is unable to verify the validity of $〈N, {A u t h}_{S}〉$ due to the lack of $D_{I D, 2}$ and $K_{C} = r \cdot D_{I D, 2}$ .

(3)

Upon receiving the Send $(Π_{C}^{j}, 〈N, {A u t h}_{S}〉)$ with C's identity $I D$ distinct from ${I D}_{T}$ , $B$ computes $K_{C} = r \cdot w \cdot P_{p u b} = r \cdot D_{I D, 2}$ and checks whether the equality ${A u t h}_{S} = f_{2} (I D, U_{1}, U_{2}, V, N, K_{C})$ holds. If the equality holds, the oracle $Π_{C}^{j}$ accepts the session. Then $B$ computes ${A u t h}_{C} = f_{3} (I D, U_{1}, U_{2}, V, N, K_{C}, {A u t h}_{S})$ and returns $〈{A u t h}_{C}〉$ to $A$ . Otherwise, $B$ declines the request. On the other hand, if $I D = {I D}_{T}$ , $B$ selects a random value ${A u t h}_{C} \in {\{0,1\}}^{n}$ and returns $〈{A u t h}_{C}〉$ to $A$ . In this case, $A$ is unable to verify the validity of $〈{A u t h}_{C}〉$ due to the lack of $D_{I D, 2}$ and $K_{C} = r \cdot D_{I D, 2}$ .

(4)

When $A$ makes a Send ( $Π_{S}^{i}$ , $〈{A u t h}_{C}〉$ ), $B$ checks whether ${A u t h}_{C} = f_{3} (I D, U_{1}, U_{2}, V, N, K_{S}, {A u t h}_{S})$ holds. If so, the oracle $Π_{S}^{i}$ accepts the session and terminates. Otherwise, the oracle $Π_{S}^{i}$ 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 $〈I D, U_{1}, U_{2}, V, Q_{I D, 1}〉$ and $〈{A u t h}_{C}〉$ to the oracle $Π_{S}^{i}$ . In such a case, since $〈I D, U_{1}, U_{2}, V, Q_{I D, 1}〉$ is valid, it must satisfy the equality $\hat{e} (P, V) = \hat{e} (U_{1} + Q_{I D, 1}, W) \cdot \hat{e} (P_{p u b}, h \cdot W + Q_{I D, 2}$ ), where $W = H_{2} (U_{1}, U_{2})$ , $h = f_{1} (I D, Q_{I D, 1})$ , and $Q_{I D, 2} = H_{1} (I D)$ . We also know that $〈I D, U_{1}, U_{2}, V, Q_{I D, 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 $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 $〈{A u t h}_{C}〉$ , $A$ must obtain $D_{I D, 2}$ since $〈{A u t h}_{C}〉$ is derived from $K_{C}$ which is exactly $r \cdot D_{I D, 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, a P, b P)$ in $G_{1}$ with unknown $a, b \in Z_{q}^{*}$ , namely, to evaluate $a b P$ by computing $w \cdot a P - D_{I D, 2}$ since w is a known value in the list $L_{H 1}$ and $D_{I D, 2} = a \cdot Q_{I D, 2}$ due to the tuple $〈P, P_{p u b} = a P, Q_{I D, 2} = w \cdot P - b P〉$ . 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 $B$ is used to simulate the actual situation in our protocol.

Theorem 9.

Assume that a PPT adversary $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 1}$ , $q_{H 2}$ , and $q_{k}$ queries, for $k = 1, \dots, 4$ , respectively, to the $Π_{S}^{i}$ oracle of the server S and the $Π_{C}^{j}$ oracle of the client C, $H_{1}$ , $H_{2}$ , and $f_{k}$ for $k = 1, \dots, 4$ . Then there is a challenger $B$ that can solve the CDH problem with a nonnegligible advantage.

Proof.

Firstly, we know that the adversary $A$ can guess the unbiased coin b correctly with the probability $1 / 2$ in the Test query. Let the symbol $O s k$ 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 $P r [O s k] \geq ε / 2$ .

Without loss of generality, we denote by the symbols Test $(Π_{C}^{j})$ and Test $(Π_{S}^{i})$ , respectively, the successful events of obtaining the correct session key in the Test query to the client and the server. Note that $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} \Pr [O s k \land T e s t (Π_{S}^{i}) \land E v e n t^{C 2 S}] \\ + \Pr [O s k \land T e s t (Π_{S}^{i}) \land \neg E v e n t^{C 2 S}] \\ + P r [O s k \land T e s t (Π_{C}^{j})] \geq \frac{ε}{2}, \end{array}

(4)

where the symbol

E v e n t^{C 2 S}

is the event violating the client-to-server authentication. Also, let

{P r}_{C 2 S}

denote the probability of the event

E v e n t^{C 2 S}

. Then, we have

\begin{array}{l} P r [O s k \land T e s t (Π_{S}^{i}) \land \neg E v e n t^{C 2 S}] \\ + P r [O s k \land T e s t (Π_{C}^{j})] \geq \frac{ε}{2} - P r_{C 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 $B$ (called Simulation $B$ ) to make the initialization and to respond to $A$ according to our proposed protocol. Without loss of generality, we set ${I D}_{T}$ as the fixed target identity. (i)

Initialization: at first, $B$ generates the system parameters $〈G_{1}, G_{2}, q, P, \hat{e}〉$ and sets the system public key $P_{p u b} = s \cdot P$ , where s is the system private key. Then $B$ sends the public parameters to $A$ and maintains the lists $L_{H 1}, L_{H 2}, 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 ( $Π_{U}^{k}$ ): 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 ( $Π_{C}^{j}$ ): 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 ( $Π_{C}^{j}$ ): 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 either Ephemeral-secret-leakage query or Corrupt query, but not both.

(vii)

Test ( $Π_{U}^{k}$ ): when the adversary $A$ sends such a query, the oracle $Π_{U}^{k}$ 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 $Π_{U}^{k}$ .

In the simulation above, Simulation $B$ is perfectly indistinguishable from the proposed protocol unless the event $E v e n t^{C 2 S}$ occurs. And, we can see that the event $\exists j, O s k \land T e s t (Π_{C}^{j})$ is equal to the event $\exists i, O s k \land T e s t (Π_{S}^{i}) \land \neg E v e n t^{C 2 S}$ so that we have $P r [O s k \land T e s t (Π_{C}^{j})] \geq ε / 2 - P r_{C 2 S}$ . Hence, by the simulation of the oracle $Π_{C}^{j}$ of the client C, we have

\begin{array}{l} P r [S K = f_{4} (I D, U_{1}, U_{2}, V, N, K_{C}, \\ {A u t h}_{S}, {A u t h}_{C}) | \begin{array}{l} N \in Z_{q}^{*} \\ U_{1}, U_{2}, K_{C} ⟵ G_{1} \end{array}] \\ \geq \frac{ε}{2} - P r_{C 2 S} . \end{array}

(6)

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

Theorem 10.

If a PPT adversary $A$ 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 algorithm $B$ (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 ${E v e n t}^{C 2 S}$ occurs. Since the probability ${P r}_{C 2 S}$ is negligible by Theorem 8, we can assume that ${E v e n t}^{C 2 S}$ does not occur.

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

Case 1. The adversary $A$ guessed the value ${A u t h}_{S}$ correctly.

Case 2. The values $U_{2}$ occurred in other sessions.

Case 3. $A$ asked $f_{2}$ for the tuple $(I 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 $P r [(I D, U_{1}, U_{2}, V, N, K_{S}) | U_{1}, U_{2}, P_{p u b} \in G_{1}, K_{S} = s \cdot U_{2}]$ . Thus,

\begin{array}{l} P r [E v e n t^{S 2 C} | \neg E v e n t^{C 2 S}] \\ \leq P r [(I D, U_{1}, U_{2}, V, N, K_{S}) | U_{1}, U_{2} \in G_{1}, K_{S} = s \cdot U_{2}] \\ + \frac{q_{C}}{2^{n}} + \frac{q_{C}^{2}}{q} . \end{array}

(7)

As before,

A

can obtain the ephemeral secret value r by the ESL attacks. Now, we assume that

P_{p u b} = s P

and

Q_{I D, 2} = w P

. Then we have

U_{1} = r \cdot P

and

U_{2} = r \cdot Q_{I D, 2} = r \cdot w P

with unknown s,

w \in Z_{q}^{*}

. In this case, given

(U_{1}, U_{2}, P_{p u b}) = (r \cdot P, r \cdot w P, s P)

A

can compute

K_{S} = s \cdot U_{2} = r \cdot s w P

with a nonnegligible probability. Therefore, if

A

could obtain the session key SK, it would be able to compute

K_{S}

. In such a case,

B

can use

A

to obtain swP. Therefore,

B

can solve the CDH problem with a nonnegligible advantage.

Hence, by assuming that $A$ can violate the server-to-client authentication with a nonnegligible advantage ɛ, $B$ then solves the CDH problem with the advantage $ɛ^{'} \geq ɛ - 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 $A$ 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 $K_{S} = s \cdot U_{2}$ and $S K = f_{4} (I D, U_{1}, U_{2}, V, N, K_{S}, {A u t h}_{S}, {A u t h}_{C})$ . 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 the Corrupt (ID) and obtain $D_{I D} = (D_{I D, 1}, D_{I D, 2}, Q_{I D, 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 $\hat{e} : G_{1} \times G_{1} \to G_{2}$ ;

$T G_{m u l}$ : the executing time of a scalar multiplication in $G_{1}$ ;

$T_{e x p}$ : the executing time of a modular exponential operation in $G_{2}$ ;

${T G}_{H}$ : the executing time of a map-to-point hash function in $G_{1}$ ;

${T G}_{a d 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;

$| σ |$ : the bit length of a transmission message σ.

By the simulation results in [44, 45], $T G_{e}$ , $T G_{m u l}$ , $T_{e x p}$ , and $T G_{H}$ are more time-consuming than $T G_{a d 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_{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 $4 T G_{m u 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_{m u 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 $3 T G_{e} + 2 T G_{m u l} + 2 T G_{H}$ . As for the communicational cost, the bit length of communication between a client and the server is bounded by $4 |q| + 4 |G_{1}|$ .

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_{m u 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)	$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	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.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgment

This research was partially supported by the Ministry of Science and Technology, Taiwan, under Contract no. MOST103-2221-E-018-022-MY2.

References

Menezes

Vanstone

Some new key agreement protocols providing mutual implicit authentication

Proceedings of the 2nd Workshop on Selected Areas in Cryptography (SAC '95)

1995

22 32

Bellare

Pointcheval

Rogaway

Authenticated key exchange secure against dictionary attacks

Advances in Cryptology—Eurocrypt 2000 2000

Springer

139 155

10.1007/3-540-45539-6_11

Canetti

Krawczyk

Analysis of key-exchange protocols and their use for building secure channels

Proceedings of Advances in Cryptology—Eurocrypt2001 2001 2045

Berlin, Germany

Springer

453 474

MR1895449

ElGamal

A public key cryptosystem and a signature scheme based on discrete logarithms

IEEE Transactions on Information Theory 1985 31 4 469 472

10.1109/TIT.1985.1057074

MR798552

Rivest

R. L.

Shamir

Adleman

A method for obtaining digital signatures and public-key cryptosystems

Communications of the ACM 1978 21 2 120 126

10.1145/359340.359342

MR700103

2-s2.0-0017930809

Shamir

Identity-based cryptosystems and signature schemes

Advances in Cryptology: Proceedings of CRYPTO 84 1985 196 47 53 Lecture Notes in Computer Science

10.1007/3-540-39568-7_5

Boneh

Franklin

Identity-based encryption from the Weil pairing

Advances in Cryptology—CRYPTO 2001 2001 2139

Berlin, Germany

Springer

213 229

10.1007/3-540-44647-8_13

Waters

Efficient identity-based encryption without random oracles

Advances in Cryptology—EUROCRYPT 2005 2005 3494

Berlin, Germany

Springer

114 127 Lecture Notes in Computer Science

Boneh

Hamburg

Generalized identity based and broadcast encryption schemes

Advances in Cryptology—ASIACRYPT 2008 2008 5350

Berlin, Germany

Springer

455 470

10.1007/978-3-540-89255-7_28

10.

Tseng

Y.-M.

Tsai

T.-T.

Efficient revocable ID-based encryption with a public channel

The Computer Journal 2012 55 4 475 486

10.1093/comjnl/bxr098

2-s2.0-84859342049

11.

Tsai

T.-T.

Tseng

Y.-M.

T.-Y.

RHIBE: constructing revocable hierarchical ID-based encryption from HIBE

Informatica 2014 25 2 299 326

MR3228773

12.

Cha

J. C.

Cheon

J. H.

An identity-based signature from gap Diffie-Hellman groups

Public Key Cryptography—PKC 2003 2002 2567

Berlin, Germany

Springer

18 30 Lecture Notes in Computer Science

10.1007/3-540-36288-6_2

MR2171914

13.

Paterson

K. G.

Schuldt

J. C. N.

Efficient identity-based signatures secure in the standard model

Information Security and Privacy 2006 4058

Berlin, Germany

Springer

207 222

10.1007/11780656_18

14.

Tsai

T.-T.

Tseng

Y.-M.

T.-Y.

Provably secure revocable ID-based signature in the standard model

Security and Communication Networks 2013 6 10 1250 1260

2-s2.0-84884706246

10.1002/sec.696

15.

Choi

K. Y.

Hwang

J. Y.

Lee

D. H.

ID-based authenticated group key agreement secure against insider attacks

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 2008 91 7 1828 1830

10.1093/ietfec/e91-a.7.1828

2-s2.0-77951282858

16.

T.-Y.

Tseng

Y.-M.

C.-W.

A secure ID-based authenticated group key exchange protocol resistant to insider attacks

Journal of Information Science and Engineering 2011 27 3 915 932

MR2829993

2-s2.0-79958112453

17.

T.-Y.

Tseng

Y.-M.

Towards ID-based authenticated group key exchange protocol with identifying malicious participants

Informatica 2012 23 2 315 334

MR2944168

2-s2.0-84863643575

18.

Islam

S. K. H.

Biswas

G. P.

A pairing-free identity-based authenticated group key agreement protocol for imbalanced mobile networks

Annals of Telecommunications 2012 67 11-12 547 558

10.1007/s12243-012-0296-9

2-s2.0-84870878817

19.

Smart

N. P.

Identity-based authenticated key agreement protocol based on Weil pairing

Electronics Letters 2002 38 13 630 632

10.1049/el:20020387

2-s2.0-0037142442

20.

Shim

Efficient ID-based authenticated key agreement protocol based on Weil pairing

Electronics Letters 2003 39 8 653 654

10.1049/el:20030448

2-s2.0-0038680685

21.

Chen

Kudla

Identity-based authenticated key agreement from pairings

Proceedings of the 16th IEEE Computer Security Foundations Workshop (CSFW '03)

2003

219 233

22.

Choie

Y. J.

Jeong

Lee

Efficient identity-based authenticated key agreement protocol from pairings

Applied Mathematics and Computation 2005 162 1 179 188

10.1016/j.amc.2003.12.092

MR2107266

ZBL1062.94555

2-s2.0-10444220191

23.

Chen

Cheng

Smart

N. P.

Identity-based key agreement protocols from pairings

International Journal of Information Security 2007 6 4 213 241

10.1007/s10207-006-0011-9

2-s2.0-34347393777

24.

Jakobsson

Pointcheval

Mutual authentication for low-power mobile devices

Financial Cryptography: Proceedings of Financial Cryptography 2002 2339 178 195 Lecture Notes in Computer Science

25.

Wong

D. S.

Chan

A. H.

Efficient and mutually authenticated key exchange for low power computing devices

Proceedings of Advances in Cryptology—Asiacrypt2001 2001 2248

Berlin, Germany

Springer

272 289

10.1007/3-540-45682-1_17

MR1934848

26.

Wen

H.-A.

Lin

C.-L.

Hwang

Provably secure authenticated key exchange protocols for low power computing clients

Computers & Security 2006 25 2 106 113

10.1016/j.cose.2005.09.010

2-s2.0-33644748254

27.

Choi

K. Y.

Hwang

J. Y.

Lee

D. H.

Seo

I. S.

ID-based authenticated key agreement for low-power mobile devices

Proceedings of the 10th Australasian Conference on Information Security and Privacy (ACISP '05)

July 2005

Brisbane, Australia

494 505

2-s2.0-26444474509

28.

T.-Y.

Tseng

Y.-M.

An efficient user authentication and key exchange protocol for mobile client-server environment

Computer Networks 2010 54 9 1520 1530

10.1016/j.comnet.2009.12.008

2-s2.0-77955659710

29.

T.-Y.

Tseng

Y.-M.

An ID-based mutual authentication and key exchange protocol for low-power mobile devices

Computer Journal 2010 53 7 1062 1070

10.1093/comjnl/bxp083

2-s2.0-77955703761

30.

An efficient remote user authentication and key agreement protocol for mobile client-server environment from pairings

Ad Hoc Networks 2012 10 6 1009 1016

10.1016/j.adhoc.2012.01.002

2-s2.0-84859767453

31.

Islam

S. H.

Biswas

G. P.

A more efficient and secure ID-based remote mutual authentication with key agreement scheme for mobile devices on elliptic curve cryptosystem

Journal of Systems and Software 2011 84 11 1892 1898

10.1016/j.jss.2011.06.061

2-s2.0-80052774690

32.

Jianhua

An ID-based client authentication with key agreement protocol for mobile client-server environment on ECC with provable security

Information Fusion 2012 13 3 223 230

10.1016/j.inffus.2011.01.001

2-s2.0-80051571433

33.

Chuang

Y. H.

Tseng

Y. M.

Towards generalized ID-based user authentication for mobile multi-server environment

International Journal of Communication Systems 2012 25 4 447 460

10.1002/dac.1268

2-s2.0-84859161671

34.

LaMacchia

Lauter

Mityagin

Stronger security of authenticated key exchange

Proceedings of the 1st International Conference on Provable Security (ProvSec '07)

2007

1 16

35.

Chen

Hao

Strongly secure identity-based authenticated key agreement protocols

Computers and Electrical Engineering 2011 37 2 205 217

10.1016/j.compeleceng.2011.03.001

ZBL1217.94121

2-s2.0-79955705154

36.

Islam

S. K. H.

A provably secure ID-based mutual authentication and key agreement scheme for mobile multi-server environment without ESL attack

Wireless Personal Communications 2014

10.1007/s11277-014-1968-8

37.

Tseng

Y. M.

Tsai

T. T.

Huang

S. S.

Leakage-free ID-based signature

The Computer Journal 2013

10.1093/comjnl/bxt116

38.

Bellare

Rogaway

Random oracles are practical: a paradigm for designing efficient protocols

Proceedings of the 1st ACM Conference on Computer and Communications Security

1993

62 73

39.

Pointcheval

Stern

Security arguments for digital signatures and blind signatures

Journal of Cryptology 2000 13 3 361 396

10.1007/S001450010003

ZBL1025.94015

2-s2.0-0000901529

40.

Aboba

Blunk

Vollbrecht

Carlson

Levkowetz

Extensible authentication protocol (EAP)

IETF 2004 RFC3748

41.

Simon

Aboba

Hurst

The EAP-TLS authentication protocol

IETF RFC 5216, March 2008

42.

Tseng

Y. M.

USIM-based EAP-TLS authentication protocol for wireless local area networks

Computer Standards and Interfaces 2009 31 1 128 136

10.1016/j.csi.2007.11.014

2-s2.0-54349092335

43.

Pereñiguez-Garcia

Kambourakis

López

R. M.

Gritzalis

Gómez-Skarmeta

A. F.

Privacy-enhanced fast re-authentication for EAP-based next generation network

Computer Communications 2010 33 14 1682 1694

10.1016/j.comcom.2010.02.021

2-s2.0-77955350425

44.

Scott

Costigan

Abdulwahab

Implementing cryptographic pairings on smartcards

Cryptographic Hardware and Embedded Systems—CHES 2006 2006 4249 134 147 Lecture Notes in Computer Science

10.1007/11894063_11

45.

Oliveira

L. B.

Scott

López

Dahab

TinyPBC: pairings for authenticated identity-based non-interactive key distribution in sensor networks

Proceedings of the 5th International Conference on Networked Sensing Systems (INSS '08)

June 2008

173 180

2-s2.0-53149126145

10.1109/INSS.2008.4610921