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

Abstract

Identity-based user authentication protocols have been presented to be applicable to resource-constrained devices such as mobile phones. Unfortunately, the previous protocols have the drawback of the key escrow problem. A new protocol of a user authenticated key exchange for the mobile client-server environment is presented based on certificateless public key cryptography (CL-PKC). Our protocol solves the key escrow problem in user authentication schemes based on identity-based public key cryptography (ID-PKC). In addition, the proposed protocol is resisted to both adversaries’ types I and II and achieves perfect forward secrecy. The security of the proposed protocol has been proved using computational Diffie-Hellman (CDH) assumption in the random oracle model. Experimental results show that our scheme is better than He et al. and Tsai et al. schemes respectively in communication cost.

1 Introduction

Researchers are developing innovative technologies and intelligence systems to enhance our daily life’s quality by adopting information and communication technology (ICT). For example, in ambient assisted living (AAL) system, the use of ICT can provide health-care monitoring, telehealth services, and it is more convenient to help older adults to take care of themselves. Since the idea of AAL is primarily to support people with peculiar needs, as such, it would involve technical systems which are capable of taking over certain daily tasks whenever required, providing the needy with a high level of autonomy. Several technologies have been used in AAL system to make it more suitable for practical applications such as wireless body area networks (W-BANs), assistive robotics, mobiles, and wearable sensors. Practically, the range of information is received continuously from the embedded sensors and recorded by distributed devices  (Shen et al. 2018; Wang et al. 2015). These provide a cooperation between the natural user interface and sensor interfaces around the person, resulting in an intelligent device environment; able to recognize the person, identify their needs, learn from their behaviors, as well as to act and react in their interest.

Mobile devices are used to send/receive and process sensitive data that are employed in medical health monitoring and emergency response systems (Wang et al. 2016, 2017; Hamida et al. 2017). Consequently, adversaries could corrupt the communication data, which in turn raises several security issues. It is paramount for mobile devices user to ensure communication with the right service provider. In addition, the service provider as well needs to be authenticated on the user. Moreover, both users and providers should agree on the session key to be used for the future communication. So, considering the mobile devices, it is challenging to offer a user authentication, a key exchange and a mutual authentication protocols in this environment (Sabzevar and Sousa 2011; Zhang et al. 2014; Ren et al. 2016; Jaballah et al. 2015).

To find out eventual solutions for these security challenges, some schemes (Nam et al. 2005; Tseng 2006, 2007; Wong and Chan 2001; Wang et al. 2011) have been introduced for the applications of the mobile devices using the traditional public key cryptography. However, the computational cost in these protocols is higher on the user side. An ID-PKC resolving the certificate management in comparison with the traditional certificate-based public key cryptography was proposed by Shamir (1984). However, this system has a major weakness as all the private keys of the users are produced by the private key generator (PKG) which leads directly to the key escrow problem. The system of Shamir relies on the assumption of the integer factorization. Therefore, it is not readily realizable in real practical scenarios. Subsequently, several user authentication protocols for mobile environment have been discussed enormously.

1.1 Related work

In the last decade, several identity-based protocols (Fang and Huang 2006; Das et al. 2006; Tseng et al. 2008; Sun et al. 2014) based on the bilinear pairing have been discussed without mutual authentication and key agreement. Wu and Tseng (2010) worked on a user authenticated key exchange protocol which is secure against the impersonation attack, known session key attack, the identity attack, and the partial forward secrecy. Another user authentication and key agreement protocol for the environment of client-server was introduced by Yoon and Yoo (2010) to improve the performance. He (2012) established a user authentication and key exchange protocol. He mentioned that his proposed protocol protects from various known attacks while the biometrics-based authentication protocol heralded by Shen et al. (2015) is known have a little computational cost. Tsai and Lo (2015) introduced an identity-based authentication scheme. They declared that their scheme is provably secure and the communication overhead is reduced at the side of the mobile user. Wu et al. (2016) presented an efficient user authentication and secure key agreement protocol to overcome the drawbacks found in Tsai and Lo’s scheme by maintaining users anonymity. A new authentication scheme for wireless sensor network as well as the formal proof and verification was introduced by Wu et al. (2017) for mutual authentication. In finding the solution for the key escrow problem of the CL-PKC, Al-Riyami and Paterson (2003) presented a new pattern labeled certificateless public key cryptography (CL-PKC). Based on CL-PKC, some certificateless user authentication schemes (Hou and Xu 2009; He 2012) have been suggested without providing mutual authentication. Hassan et al. (2016) proposed a certificateless user authentication and key agreement protocol which solved the key escrow problem. It is claimed that proposed protocol is resist to the adversary Type I and the adversary Type II. However, their protocol is not secure against the adversary Type 2. Therefore, it is imperative to introduce a provably secure user authentication and key agreement protocol using CL-PKC to ensure the scheme withstands the adversary Type 2. This paper is a revised version of work published in (Hassan et al. 2016).

1.2 Organization

This paper is organized as follows. Section 2 presents the preliminaries of bilinear pairing as well as the security model. Section 3 proposes our protocol and the security of the proposed protocol is shown in Sect. 4. Section 5 demonstrates the analysis of the protocol’s performance while the conclusions are given in Sect. 6.

2 Preliminaries

2.1 Bilinear pairings

While ${\mathbb {G}}_{1}$ and ${\mathbb {G}}_{2}$ are the additive and multiplicative groups of exact prime order q respectively, the bilinear pairing function is given as $e:{\mathbb {G}}_{1}\times {\mathbb {G}}_{1}\rightarrow {\mathbb {G}}_{2}$ and P is the generator of ${\mathbb {G}}_{1}$. The following as described by (Boneh and Franklin 2001; Boneh et al. 2004) are properties of a bilinear pairing:

• 1. Bilinearity Where $\forall a,b \in {\mathbb {Z}}^{*}_{q}$ and $\forall Q,P \in {\mathbb {G}}_{1}$, then $e(aQ, bP)=e(Q,P)^{ab}.$

• 2. Non degeneracy Where Q, P $\in {\mathbb {G}}_{1}$ and $1_{{\mathbb {G}}_{2}}$ is the identity element of ${\mathbb {G}}_{2}$., there exist e(Q, P) $\ne 1_{{\mathbb {G}}_{2}}$.

• 3. Computability The e(Q, P) is computed efficiently if $\forall Q,P \in {\mathbb {G}}_{1}$.

Computational Diffie-Hellman (CDH) Problem

Where $\forall a,b \in {\mathbb {Z}}_q^*$ and $(P,aP,bP) \in {\mathbb {G}}_{1}$ are given it is not easy to solve abP.

2.2 Security model

For user authentication and key agreement protocol proof there are several security models such as CK (Canetti and Krawczyk 2001) model and eCK model (LaMacchia et al. 2007). We have employed Wu and Tseng (2010)’s security model because it is suitable to our protocol. The efficiency of an adversary ${\mathscr {A}}_i$ where $\forall i \in \{1,2\}$ and the security specification list for the mutual authentication and key exchange are described in this section. The schemes which use CL-PKC no doubt resists the two type adversaries, labeled type I and type II as noted in (Al-Riyami and Paterson 2003). While the type I adversary ${\mathscr {A}}_1$ can replace the users’ public key, he/she cannot access the master key of the KGC. In the same line, though the type II adversary ${\mathscr {A}}_2$ own the KGC’s master key, he/she nevertheless can’t substitute the public key of the users.

The instance k of the member U is denoted as $\varPi _U^k$. Below, the following queries of game 1 and game 2 are illustrated:

• Game-1:

  • 1. Setup($1^k$) A certain security parameter k is given to the algorithm as input. Then, the system parameter params and the master key s are generated when the Setup algorithm is run by the challenger ${\mathscr {C}}$. Consequently, while s remains secret, ${\mathscr {C}}$ sends params to the adversary ${\mathscr {A}}_1$.

  • 2. Probing Except the challenged identity $ID_{j}$, ${\mathscr {A}}_1$ performs a polynomial function for any identity $ID_{c}$ of the under-listed queries:

    • (a) Extract partial private key query Except the $ID_{j}$, ${\mathscr {A}}_1$ is capable of requesting the partial private key for any $ID_{c}$ while ${\mathscr {C}}$ computes the corresponding partial private key ${D_{I{D_c}}}$ and returns it to ${\mathscr {A}}_1$ accordingly.

    • (b) Extract private key query Except the $ID_{j}$, ${\mathscr {A}}_1$ is capable of requesting the partial private key for any $ID_{c}$, ${\mathscr {C}}$ computes the corresponding private key and returns it to ${\mathscr {A}}_1$ accordingly.

    • (c) Request public key query Except the $ID_{j}$, ${\mathscr {A}}_1$ is capable of requesting the public key for any $ID_{c}$ while ${\mathscr {C}}$ computes the corresponding public key $P_{ID_c}$ and returns it to ${\mathscr {A}}_1$.

    • (d) Replace public key query: For any $ID_{c}$, ${\mathscr {A}}_1$ can choose a new secret value $x_{_{I{D_c}}}^{'}$ and compute the new public key associated to the value $x_{_{I{D_c}}}^{'}$. Aftermath, ${\mathscr {A}}_1$ substitutes $P_{ID_c}$ with $P^{'}_{ID_c}$.

    • (e) Send ($\varPi _U^k,M)\,query$ When a message M is sent according to the proposed protocol from ${\mathscr {A}}_1$ to ${\mathscr {C}}$, ${\mathscr {C}}$ receives, makes the computation and responses to ${\mathscr {A}}_1$.

    • (f) Reveal ($\varPi _U^k,M)\, query$ A session key sk is received by ${\mathscr {A}}_1$ from ${\mathscr {C}}$ if it has been accepted. In the case it hasn’t, it replies a null.

    • (g) Corrupt (U) query A member U is issued a Corrupt query by ${\mathscr {A}}_1$ to ${\mathscr {C}}$ for the purpose of remitting its private key.

    • (h) Test ($\varPi _U^k)\, query$ When ${\mathscr {A}}_1$ forwards a single Test query to ${\mathscr {C}}$, ${\mathscr {C}}$ tosses a fair coin b. The session key sk is returned to ${\mathscr {A}}_1$ if $b=1$. if not; a randomly string is returned to ${\mathscr {A}}_1$. The semantic security of sk is measured by this query.

    ${\mathscr {A}}_1$ outputs $b'$ as its estimate for value of b in Test query. The value of b can be guessed correctly by ${\mathscr {A}}_1$ with probability $Adv({\mathscr {A}}_1)=|\mathrm{Pr}[b'=b]-1/2|$. The private key of $ID_{j}$ can’t be extracted by ${\mathscr {A}}_1$ at any point in this game. In addition, the public key of $ID_{j}$ can’t replaced by ${\mathscr {A}}_1$ before the challenge phase. But, the partial private key can be extracted by ${\mathscr {A}}_1$ in some phases.

• Game-2:

  • 1. Setup($1^k$) A certain security parameter k is given to the algorithm as input. Then, the system parameter params and the master key s are generated when the Setup algorithm is run by the challenger ${\mathscr {C}}$. Consequently, ${\mathscr {C}}$ sends params and s to ${\mathscr {A}}_2$.

  • 2. Probing Except $ID_{j}$, ${\mathscr {A}}_2$ performs a polynomial function for any $ID_{c}$ of the under-listed queries:

    The Extract private key, Request public Key, Send ($\varPi _U^k,M$), Reveal ($\varPi _U^k,M$), Corrupt (U), and Test ($\varPi _U^k$) queries are made by ${\mathscr {A}}_2$ similar to that in game-1. Extract partial private key query and Replace public key query can’t be made by ${\mathscr {A}}_2$ in this game. However, ${\mathscr {A}}_2$ makes the extraction of the partial private key ${D_{I{D_c}}}$ by oneself since, it has the master key s.

  ${\mathscr {A}}_2$ outputs $b'$ estimate for value of b in Test query. The value of b can be guessed correctly by ${\mathscr {A}}_2$ with probability $Adv({\mathscr {A}}_1)=|\mathrm{Pr}[b'=b]-1/2|$. Extract partial private key and Replace public key queries of $ID_{j}$ can’t be made by ${\mathscr {A}}_2$ at any point in this game.

Send query, Reveal query, Corrupt query, and Test query can be made by ${\mathscr {A}}_i\{i=1,2\}$ for key exchange characteristics without authentication (Jakobsson and Pointcheval 2001). Figure that ${\mathscr {A}}_1$ and ${\mathscr {A}}_2$ are capable to establish limited queries under adaptive chosen message attacks (Choon and Cheon 2003). More details about security requirements for the mutual authentication and key exchange scheme could be found by the reader in (Boneh and Franklin 2001).

3 Proposed protocol

Our protocol is consisted of two phases, namely the initialization phase and the user authentication key exchange phase. He et al. (2013)’s short signature have employed by the proposed protocol. The notations apply in this paper are illustrated in Table 1. Our protocol’s phases are described as follows:

Table 1 Notation

3.1 Initialization phase

The following algorithms are executed during initialization as shown in Fig 1.

• Setup ($1^k$): This algorithm is executed by the key generator center (KGC). A security parameter k is taken by KGC while the parameters are generated as follows:

  • 1. Two groups ${\mathbb {G}}_{1}$ and ${\mathbb {G}}_{2}$ are determined with exact prime order q and a bilinear pairing $e:{\mathbb {G}}_{1} \times {\mathbb {G}}_{1}\rightarrow {\mathbb {G}}_{2}$ where P is a generator of ${\mathbb {G}}_{1}$.

  • 2. The master private key of the KGC is determined randomly $s\in {\mathbb {Z}}_q^*$ and the corresponding master public key ${P_{pub}}= sP$ is computed.

  • 3. The public key ${P_{I{D_s}}} = {x_{I{D_s}}}P$ is computed where ${x_{I{D_s}}} \in {\mathbb {Z}}_q^*$ and four cryptographic secure hash functions ${H_1}:{\{ 0,1\} ^*} \times {\mathbb {G}}_{1} \times {\mathbb {G}}_{1} \rightarrow {\mathbb {Z}}_q^*$, ${H_2}:{\mathbb {G}}_{1}\times \{ 0,1\} ^* \times {\mathbb {Z}}_q^* \times {\mathbb {G}}_{1} \times {\mathbb {G}}_{1} \times {\mathbb {G}}_{1} \rightarrow {\mathbb {Z}}_q^*,$ ${H_3}:{\{ 0,1\} ^*} \times {\mathbb {G}}_{1} \times {\mathbb {G}}_{1} \times {\mathbb {G}}_{1} \times {\mathbb {Z}}_q^* \times {\mathbb {G}}_{1} \times {\mathbb {Z}}_q^* \rightarrow {\mathbb {Z}}_q^*,$ and ${H_4}:{\{ 0,1\} ^*}\times {\mathbb {G}}_{1} \times {\mathbb {G}}_{1} \times {\mathbb {G}}_{1} \times {\mathbb {Z}}_q^* \times {\mathbb {G}}_{1} \times {\mathbb {Z}}_q^* \rightarrow {\mathbb {G}}_{1}$ are chosen.

  • 4. $\{ {\mathbb {G}}_{1},{\mathbb {G}}_{2},q,e,P,{P_{pub}}, {P_{I{D_s}}},{H_1},{H_2},{H_3},{H_4}\}$ are published as general.

• Extract partial private key The partial private key ${R_{I{D_c}}} = {r_{I{D_c}}}{P}$ where ${r_{I{D_c}}} \in {\mathbb {Z}}_q^*$, ${h_{I{D_c}}} = {H_1}(I{D_c},{R_{I{D_c}}},{P_{pub}})$, and ${s_{I{D_c}}} = ({r_{I{D_c}}} + {h_{I{D_c}}}s)\bmod q$ are computed by the server while a master private key, the public parameters and the identity of the client are given. The server’s public key $P_{ID_s}=x_{ID_s}P$ is computed where ${x_{I{D_s}}} \in {\mathbb {Z}}_q^*$ is chosen randomly. Then, the ${D_{I{D_c}}}$ is sent to the client.

• Set private key The reliability of the ${D_{I{D_c}}}$ is checked by the client since it is received from the server by the following equation ${s_{I{D_c}}}{P}\mathop = \limits ^? {R_{I{D_c}}} + {h_{I{D_c}}}{P_{pub}}$. The client’s private key $SK_{ID_{c}}=({x_{I{D_c}}},{D_{I{D_c}}})$ is computed by itself where ${x_{I{D_c}}} \in {\mathbb {Z}}_q^*$ is chosen randomly.

• Set public key: The client’s public key ${P_{I{D_c}}} = {x_{I{D_c}}}P$ is computed by itself.

Fig. 1

Initialization phase

3.2 User authentication and key exchange phase

The interaction between the client and the server in this phase is displayed in Fig 2 while this phase is described as follows:

• 1. $U = rP$, $k_1 = r{P_{pub}}$, and $k_2 = r{P_{ID_s}}$ are computed by the client where $r\in {\mathbb {Z}}_q^*$ is chosen randomly. Then, $(I{D_c},U)$ is sent to the server.

• 2. $\alpha \in {\mathbb {Z}}_q^*$ is chosen randomly while ${k_3}= sU$, ${k_4} = {x_{I{D_s}}}U$, and $Auth = {H_2}(P_{pub},I{D_c},\alpha ,U,{k_3},{k_4})$ are computed by the server since $(I{D_c},U)$ is received from the client. Finally, $(\alpha ,Auth)$ is sent to the client.

• 3. $Auth\mathop = \limits H_2(P_{pub},ID_c,\alpha ,U, k_1,k_2)$ is computed by the client since $(\alpha ,Auth)$ is received from the server to ensure that the Auth of the client is equal to the Auth that is computed in the server. Then, the session key $sk = {H_2}(P_{pub}, ID_c,\alpha ,U,k_1,k_2)$ is computed while $k_{ID_c}$, Q and V are calculated as follows:

  $$\begin{aligned} k_{ID_c}=\, & H_3(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth) \end{aligned}$$

  (1)
  $$\begin{aligned} Q= \,& {H_4}(I{D_c},{P_{I{D_c}}},{R_{I{D_c}}},{P_{pub}},\alpha ,U,Auth) \end{aligned}$$

  (2)
  $$\begin{aligned} V=\, & ({k_{I{D_c}}}{x_{I{D_c}}} + {s_{I{D_c}}})Q \end{aligned}$$

  (3)

  Finally, V is sent to the server.

• 4. $k_{ID_c}=H_3(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth)$ and $Q={H_4}(I{D_c},{P_{I{D_c}}},{R_{I{D_c}}},{P_{pub}},\alpha ,U,Auth)$ are computed by the server since V is received from the client. Then, the reliability of V is checked by the following equality

  $$\begin{aligned} e(V,P) = e(Q,{k_{I{D_c}}}{P_{I{D_c}}} + {R_{I{D_c}}} + {h_{I{D_c}}}{P_{pub}}) \end{aligned}$$

  (4)

  The session key $sk=H_2(P_{pub},I{D_c},\alpha ,U,k_3,k_4)$ is computed by the server if the V is satisfied the above equality.

Fig. 2

User authentication and key exchange phase

3.3 Correctness of our protocol

Where ${P_{ID_c}} = x_{ID_{c}}P$ is the client’s public key, ${s_{I{D_c}}}{P} = {R_{I{D_c}}} + {h_{I{D_c}}}{P_{pub}}$ can be computed by the client to verify the partial private key and $V = ({k_{I{D_c}}}{x_{I{D_c}}}+ {s_{I{D_c}}})Q$ is the signature are given while V satisfy this equality $e(V,P) = e(Q,{k_{I{D_c}}}$ ${P_{I{D_c}}}+ {R_{I{D_c}}} + {h_{I{D_c}}}{P_{pub}})$ the proposed protocol is correct. Using the bilinear pairing properties the correctness is illustrated by the following equalities:

$$\begin{aligned} e(V,P)&= e(({k_{I{D_c}}}{x_{I{D_c}}} + {s_{I{D_c}}})Q,P) \\&= e(Q,({k_{I{D_c}}}{x_{I{D_c}}} + {s_{I{D_c}}})P)\\&= e(Q,({k_{I{D_c}}}{x_{I{D_c}}}P + {s_{I{D_c}}}P)) \\&= e(Q,{k_{I{D_c}}}{P_{I{D_c}}} + {R_{I{D_c}}} + {h_{I{D_c}}}{P_{pub}}) \end{aligned}$$

4 Security analysis

This section shows our protocol achieves the security requirements in Sect. 2, which is proved in the random oracle model (Bellare and Rogaway 1993). The approach in (Wu and Tseng 2010; He et al. 2013) is employed by our security proof.

4.1 Client-to-server authentication

Theorem 1 demonstrates that the communication from the client to the server can’t be impersonated by ${\mathscr {A}}_i$ where $\{i=1,2\}$ under CDH assumption. The proof is given by the declaration in Lemma 1 and 2.

Theorem 1

We assume the client-to-server authentication is broken by ${\mathscr {A}}_i$ where $\{i=1,2\}$ with a non-negligible advantage $\varepsilon$. Then, the CDH assumption is solved by an algorithm ${\mathscr {C}}$ with a non-negligible probability. At most $q_S$ queries to the oracle $\varPi _{s}^{i}$ of the server , $q_c$ queries to the oracle $\varPi _c^j$ of the client, and $q_{H_i}$ queries on $H_i$ oracle $\forall i \in \{1,2,..,5\}$ are made by ${\mathscr {C}}$.

Proof

Suppose that the client-to-server authentication of the presented protocol is broken by ${\mathscr {A}}_{i}$ with a non-negligible ${\varepsilon }$ advantage while a polynomial time is given under adaptive chosen message and identity attacks. Then, by Lemma 1 in (Choon and Cheon 2003), for a chosen challenge identity the client-to-server authentication of our protocol is owned with ${\varepsilon }$ by ${\mathscr {A}}_{i}$ while a polynomial time is given.

Lemma 1

The proposed protocol can’t be broken under CDH assumption by the type I adversary ${\mathscr {A}}_{1}$ in the random oracle model.

The queries of ${\mathscr {A}}_1$ is answered by the algorithm ${\mathscr {C}}$ to prove Lemma 1. We assume that the random elements (P, $X=aP$, and $Y=bP$) $\in {\mathbb {G}}_{1}$ are received by ${\mathscr {C}}$ while $\forall a,b \in {\mathbb {Z}}_q^*$ are unknown values. The value of abP is derived by ${\mathscr {C}}$ with answering the ${\mathscr {A}}_1$’s oracle queries as follows:

• Setup ($1^k$) The system parameters $\{e,{G_1},{G_2},P,{P_{pub}},H_1, H_2,H_3,H_4\}$ are generated by ${\mathscr {C}}$ where $P_{pub}=Y$ and are sent to ${\mathscr {A}}_1$. An identity $ID_j$ is selected randomly by ${\mathscr {C}}$ as the challenge identity in this game. For queries and responses six lists $L_{H_{1}}$, $L_{H_{2}}$, $L_{H_{3}}$, $L_{H_{4}}$, $L_{PK_{1}}$ and $L_{PK_{2}}$ are maintained by ${\mathscr {C}}$ to avoid collision and consistency.

• $H_{1} query$ When the adversary ${\mathscr {A}}_{1}$ submits this query on ($I{D_c}$,${R_{I{D_c}}},{P_{pub}}$), ${\mathscr {C}}$ randomly chooses $h_1\in {\mathbb {Z}}_q^*$ and returns it to ${\mathscr {A}}_{1}$. ${\mathscr {C}}$ updates $L_{H_{1}}$ with ($I{D_c},{R_{I{D_c}}},{P_{pub}},h_{1}$).

• $H_{2} query$ When the adversary ${\mathscr {A}}_{1}$ submits this query on $({P_{pub}},I{D_c},\alpha ,U,k_{1},k_2)$, ${\mathscr {C}}$ randomly chooses $h_2\in {\mathbb {Z}}_q^*$ and returns it to ${\mathscr {A}}_{1}$. ${\mathscr {C}}$ updates $L_{H_{2}}$ with $({P_{pub}},I{D_c},\alpha ,U, k_{1},k_2,h_{2})$.

• $H_{3} query$ When the adversary ${\mathscr {A}}_{1}$ submits this query on ($I{D_c},{P_{I{D_c}}},{R_{I{D_c}}},{P_{pub}},\alpha ,U,Auth$), ${\mathscr {C}}$ randomly chooses $h_3\in {\mathbb {Z}}_q^*$ and returns it to ${\mathscr {A}}_{1}$. ${\mathscr {C}}$ updates $L_{H_{3}}$ with ($I{D_c}, {P_{I{D_c}}},{R_{I{D_c}}},{P_{pub}},\alpha ,U,Auth,h_{3}$).

• $H_{4} query:$ When the adversary ${\mathscr {A}}_{1}$ submits this query on $(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth)$, the following reactions are done by ${\mathscr {C}}$:

  • 1. If $L_{H_{4}}$ consists of $(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth, Q_i,t_i,c_i)$, ${\mathscr {C}}$ returns $Q_{i}$ to ${\mathscr {A}}_{1}$.

  • 2. Else, a coin ${c_i} \in \{ 0,1\}$ is flipped with $\Pr [{c_i} = 0] = 1/({q_s} + 1)$ and $Q_i = \mathrm{{ }}(\mathrm{{1}} - {c_i})Y + {t_i}P$ is computed by ${\mathscr {C}}$ while ${t_i} \in {\mathbb {Z}}_q^*$ is generated randomly. Finally, $(ID_c, P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth,Q_i,t_i,c_i)$ is added to $L_{H_{4}}$ and $Q_{i}$ is returned to ${\mathscr {A}}_{1}$ by ${\mathscr {C}}$.

• Extract partial private key query When the adversary ${\mathscr {A}}_{1}$ submits this query on $ID_{c}$, ${\mathscr {C}}$ generates two random numbers ${a_{I{D_c}}},{b_{I{D_c}}}\in {\mathbb {Z}}_n^*$, sets ${R_{I{D_c}}} = {a_{I{D_c}}}P$, ${h_{I{D_c}}} = {H_1}(I{D_c},{R_{I{D_c}}},{P_{pub}}) = {b_{I{D_c}}}$, ${r_{I{D_c}}} = {a_{I{D_c}}}$ and ${s_{I{D_c}}} ={r_{I{D_c}}}+ {h_{I{D_c}}}s$. Then, ${\mathscr {C}}$ adds $(I{D_{I{D_c}}},{R_{I{D_c}}},{h_{I{D_c}}})$ and $(I{D_{I{D_c}}},{R_{I{D_c}}}, {s_{I{D_c}}})$ to $L_{H_{1}}$ and $L_{PK_{1}}$ separately.

• Extract private key query When ${\mathscr {A}}_{1}$ submits this query on $ID_{c}$, the following reactions are done by ${\mathscr {C}}$:

  • 1. If $I{D_c} \ne ID_j$, ${\mathscr {C}}$ searches in list $L_{PK_{2}}$ and returns full private key $(x_{ID_c},D_{ID_c})$ to ${\mathscr {A}}_{1}$.

  • 2. Otherwise, ${\mathscr {C}}$ stops and terminates.

• Request public key query When this query on $ID_{j}$ is submitted by ${\mathscr {A}}_{1}$, $(I{D_c},{s_{I{D_c}}},{R_{I{D_c}}})$ and $(I{D_c},{x_{I{D_c}}},{P_{I{D_c}}})$ are looked in $L_{PK_{1}}$ and $L_{PK_{2}}$ respectively by ${\mathscr {C}}$. Then, $P{K_{_{I{D_c}}}} = ({P_{I{D_c}}},{R_{I{D_c}}})$ is computed by ${\mathscr {C}}$. Otherwise, Extract private key query is made by ${\mathscr {C}}$. Finally, $P{K_{_{I{D_c}}}}$ is returned to ${\mathscr {A}}_{1}$.

• Replace public key query Whenever ${\mathscr {A}}_{1}$ submits this query on $(ID_j,P_{ID_j}^{'},R_{ID_c}^{'})$, ${\mathscr {C}}$ searches in $L_{PK_1}$ and $L_{PK_2}$ for tuples $(ID_c,s_{ID_c},R_{ID_c})$ and $(ID_c,x_{ID_c},P_{ID_c})$. ${\mathscr {C}}$ sets $P_{ID_c} = P_{ID_c}^{'}$, $R_{ID_c} = R_{ID_c}^{'}$, $s_{ID_c} = \bot$ and $x_{ID_c} = \bot$.

• Send query:

  • 1. When the adversary ${\mathscr {A}}_{1}$ submits Send $(\varPi _C^j,{``\text {start} ''})$ query, ${\mathscr {C}}$ randomly chooses $U,k_1,k_2 \in {G_1}$ and returns $(I{D_j},U)$ to ${\mathscr {A}}_{1}$.

  • 2. When the adversary ${\mathscr {A}}_{1}$ submits Send $(\varPi _S^i,(I{D_j},U))$ query to the server and $I{D_c} \ne I{D_j}$, ${\mathscr {C}}$ randomly chooses an integer $\alpha \in {\mathbb {Z}}_q^*$, computes ${k_3}=sU$, $k_4=x_{ID_s}U$, and $Auth = {H_2}(P_{pub},I{D_c},\alpha ,U,{k_3},{k_4})$. Otherwise $I{D_c} =I{D_j}$, ${\mathscr {C}}$ fails and terminates. Denote that the simulator does not know the s. Finally ${\mathscr {C}}$ returns $(\alpha ,Auth)$ to ${\mathscr {A}}_{1}$.

  • 3. When the adversary ${\mathscr {A}}_{1}$ submits Send $(\varPi _c^j,(\alpha ,Auth))$ query to the client and $ID_c \ne ID_j$, ${\mathscr {C}}$ checks whether $Auth\mathop =\limits ^? {H_2}(P_{pub},I{D_c},\alpha ,U,{k_1},k_2)$. If it holds, ${\mathscr {C}}$ finds $(I{D_c},{s_{I{D_c}}},{R_{I{D_c}}})$ and $(I{D_c},{x_{I{D_c}}},{P_{I{D_c}}})$ in $L_{PK_{1}}$ and $L_{PK_{2}}$, respectively. ${\mathscr {C}}$ computes $k_{ID_c}=H_3(ID_c,P_{ID_c},R_{ID_c}, P_{pub},\alpha ,U,Auth)$, carries out $H_{4}$ query, and obtains $Q_{i}={H_4}(I{D_c},{P_{I{D_c}}},{R_{I{D_c}}},P_{pub},\alpha ,U,Auth)$. Let $(I{D_c}, {P_{I{D_c}}},{R_{I{D_c}}},P_{pub},\alpha ,U,Auth,{Q_i},{t_i},{c_i})$ be the corresponding tuple on $L_{H_{4}}$. If $c_{i}=0$, the simulation is failed and stopped by ${\mathscr {C}}$. Else, $c_{i}=1$ and ${Q_i} = {t_i}P$ are set. ${\mathscr {C}}$ defines $V=({k_{I{D_c}}}{x_{I{D_c}}} + {s_{I{D_c}}})Q$. Then, ${\mathscr {C}}$ returns V to ${\mathscr {A}}_{1}$. If $I{D_c}=I{D_j}$, ${\mathscr {C}}$ is achieved correctly since ${\mathscr {A}}_{1}$ is not capable to satisfy $Auth^{'}$ because of the lack of $k_1$ and $k_2$.

  • 4. When the adversary ${\mathscr {A}}_{1}$ submits Send $(\varPi _S^i,V)$ query to the server, ${\mathscr {C}}$ computes $k_{ID_c}=H_3(ID_c,P_{ID_c},R_{ID_c}, P_{pub},\alpha ,U,Auth)$ and $Q_{i}={H_4}(I{D_c},{P_{I{D_c}}},{R_{I{D_c}}},P_{pub}, \alpha ,U,Auth)$. ${\mathscr {C}}$ checks $e({V_i},P) = e({Q_i},{k_{I{D_c}}}{P_{I{D_c}}} + {R_{I{D_c}}} + {h_{I{D_c}}}{P_{pub}})$. If it holds, ${\mathscr {C}}$ accepts and terminates. Else, ${\mathscr {C}}$ terminates.

• Forgery Eventually, ${\mathscr {A}}_1$ outputs a valid signature $(I{D_c},{V^{'}})$. If $I{D_c} \ne ID_j$, ${\mathscr {C}}$ stops the simulation. Otherwise, ${\mathscr {C}}$ finds $(I{D_c},{s_{I{D_c}}},{R_{I{D_c}}})$ and $(I{D_c},{x_{I{D_c}}},{P_{I{D_c}}})$ in $L_{PK_{1}}$ and $L_{PK_{2}}$, respectively. Then, ${Q_n}= {H_4}(I{D_c},{P_{I{D_c}}},{R_{I{D_c}}},{P_{pub}},\alpha ,U,Auth)$ is computed by ${\mathscr {C}}$ while this equality $e({V_n},P) = e({Q_n},{k_{I{D_c}}} {P_{I{D_c}}} + {R_{I{D_c}}} + {h_{I{D_c}}}{P_{pub}})$ is tested to ensure that the $V_n$ is satisfied the equality. If is satisfied, the simulation is terminated by ${\mathscr {C}}$ while $PK_{ID_{c}}$ is noted as the original public key. The corresponding tuple on $L_{H_{4}}$ is assumed with $(I{D_c},{P_{I{D_c}}},{R_{I{D_c}}}, P_{pub},\alpha ,U,Auth,{Q_n},{t_n},{c_n})$. If $c_{n}=1$, the simulation is failed and stopped by ${\mathscr {C}}$. Else, $c_{n}=0$ and ${Q_n}= bP+ {t_i}P$ is computed. Therefore, ${V_i}= {t_i}(b + {t_i}P)({k_{I{D_c}}}a + {r_{I{D_c}}}+ {h_{I{D_c}}}s)P$. As done in Forking Lemma (Pointcheval and Stern 1996, 2000), ${\mathscr {C}}$ outputs ${({t_i}{k_{I{D_c}}})^{ - 1}}({V_i} -t_i^2({k_{I{D_c}}}{P_{I{D_c}}} + {R_{I{D_c}}} + {h_{I{D_c}}}X)- {t_i}({r_{I{D_c}}}+ {h_{I{D_c}}}s)Y)$ as the solution of the CDH assumption.

• Analysis In the analysis, we are interested in the probability of the following independent events:

  $E_{1}$:the challenger ${\mathscr {C}}$ does not abort any of ${\mathscr {A}}_{1}$’s signature queries.

  $E_{2}$: The adversary ${\mathscr {A}}_{1}$ successfully falsifies the $e({V_i},P) = e({Q_i},{k_{I{D_c}}}{P_{I{D_c}}} + {R_{I{D_c}}} + {h_{I{D_c}}}{P_{pub}})$ on $m_{n}$.

  $E_{3}$: The ${\mathscr {A}}_{1}$ falsifies $V^{'}$ and satisfies $ID_c = ID_j$.

  $E_{4}$: $E_{2}$ happens and $c_{n}=0$ in $L_{H_{4}}$.

The signature queries $q_{s}$ and the hash queries $q_{H}$ are made by ${\mathscr {A}}_{1}$ to ${\mathscr {C}}$. Then, these probability we have $\Pr [{E_1}] \ge (1 - {1}/({q_S+1}))^{q_S}$ , $\Pr [E_2|E_1] \ge \varepsilon$, $\Pr [{E_3}|{E_1} \wedge {E_2}] \ge {1}/{q_H}$ and $\Pr [{E_4}|{E_1} \wedge {E_2} \wedge {E_3}] = {1}/{q_S+1}$. Since $\varepsilon$ is non-negligible, then ${\mathscr {A}}_{1}$ solves the CDHP with the non-negligible probability

$$\begin{aligned}&\Pr [{E_1} \wedge {E_2} \wedge {E_3} \wedge {E_4}]\\&\Pr [{E_1}]\Pr [{E_2}|{E_1}]\Pr [{E_3}|{E_1} \wedge {E_2}]\Pr [{E_4}|{E_1} \wedge {E_2} \wedge {E_3}]\\&\quad \ge ((1 - {1}/{{q_S} + 1})^{{q_{S}}}/{q_{H}}({q_S} + 1))\varepsilon \end{aligned}$$

Therefore, the client-to-server authentication scheme is broken by ${\mathscr {A}}_{1}$ while the CDH assumption is solved by an algorithm ${\mathscr {C}}$. $\square$

Lemma 2

The proposed protocol can’t be broken under CDH assumption by the type II adversary ${\mathscr {A}}_{2}$ in the random oracle model.

Proof

The queries of ${\mathscr {A}}_2$ is answered by the algorithm ${\mathscr {C}}$ to prove Lemma 2. We assume that the random elements (P, $X=aP$, and $Y=bP$) $\in {\mathbb {G}}_{1}$ are received by ${\mathscr {C}}$ while $\forall a,b \in {\mathbb {Z}}_q^*$ are unknown values. The value of abP is derived by ${\mathscr {C}}$ with answering the ${\mathscr {A}}_2$’s oracle queries as follows:

• Setup ($1^k$) The system parameters $\{e,{G_1},{G_2},P,{P_{pub}},H_1, H_2,H_3,H_4\}$ are generated by ${\mathscr {C}}$ where $P_{pub}=Y$ and are sent to ${\mathscr {A}}_2$. An identity $ID_j$ is selected randomly by ${\mathscr {C}}$ as the challenge identity in this game. For queries and responses six lists $L_{H_{1}}$, $L_{H_{2}}$, $L_{H_{3}}$, $L_{H_{4}}$, $L_{PK_{1}}$ and $L_{PK_{2}}$ are maintained by ${\mathscr {C}}$ to avoid collision and consistency.

• $H_{1} query$ When the adversary ${\mathscr {A}}_{2}$ submits this query on ($I{D_c}$,${R_{I{D_c}}},{P_{pub}}$), ${\mathscr {C}}$ randomly chooses $h_1\in {\mathbb {Z}}_q^*$ and returns it to ${\mathscr {A}}_{2}$. ${\mathscr {C}}$ updates $L_{H_{1}}$ with ($I{D_c},{R_{I{D_c}}},{P_{pub}},h_{1}$).

• $H_{2} query$ When the adversary ${\mathscr {A}}_{2}$ submits this query on $({P_{pub}},I{D_c},\alpha ,U,k_{1},k_2)$, ${\mathscr {C}}$ randomly chooses $h_2\in {\mathbb {Z}}_q^*$ and returns it to ${\mathscr {A}}_{2}$. ${\mathscr {C}}$ updates $L_{H_{2}}$ with $({P_{pub}},I{D_c},\alpha ,U, k_{1},k_2,h_{2})$.

• $H_{3} query$ When the adversary ${\mathscr {A}}_{2}$ submits this query on ($ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth$), ${\mathscr {C}}$ randomly chooses $h_3\in {\mathbb {Z}}_q^*$ and returns it to ${\mathscr {A}}_{2}$. ${\mathscr {C}}$ updates $L_{H_3}$ with ($ID_c, P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth,h_{3}$).

• $H_{4} query$ When the adversary ${\mathscr {A}}_{2}$ submits this query on $(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth)$, the following reactions are done by ${\mathscr {C}}$:

  • 1. If $L_{H_{4}}$ consists of $(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U, Auth,{Q_i},{t_i},{c_i})$, ${\mathscr {C}}$ returns $Q_{i}$ to ${\mathscr {A}}_{2}$.

  • 2. Else, a coin ${c_i} \in \{ 0,1\}$ is flipped with $\Pr [{c_i} = 0] = 1/({q_s} + 1)$ and $Q_i = \mathrm{{ }}(\mathrm{{1}} - {c_i})Y + {t_i}P$ is computed by ${\mathscr {C}}$ while ${t_i} \in {\mathbb {Z}}_q^*$ is generated randomly. Finally, $(ID_c, P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth,Q_i,t_i,c_i)$ is added to $L_{H_{4}}$ and $Q_{i}$ is returned to ${\mathscr {A}}_{2}$ by ${\mathscr {C}}$.

• Extract private key query When The adversary ${\mathscr {A}}_{2}$ submits this query on $ID_{c}$, the following reactions are done by ${\mathscr {C}}$:

  • 1. If $I{D_c} \ne ID_j$, ${\mathscr {C}}$ searches in $L_{PK_{2}}$ and returns full private key $(x_{ID_c},D_{ID_c})$ to ${\mathscr {A}}_{2}$.

  • 2. Otherwise, ${\mathscr {C}}$ stops and terminates.

• Request public key query When this query on $ID_{j}$ is submitted by ${\mathscr {A}}_{2}$, $(I{D_c},{s_{I{D_c}}},{R_{I{D_c}}})$ and $(I{D_c},{x_{I{D_c}}},{P_{I{D_c}}})$ are looked in $L_{PK_{1}}$ and $L_{PK_{2}}$ respectively by ${\mathscr {C}}$. Then, $P{K_{_{I{D_c}}}} = ({P_{I{D_c}}},{R_{I{D_c}}})$ is computed by ${\mathscr {C}}$. Otherwise, Extract private key query is made by ${\mathscr {C}}$. Finally, $P{K_{_{I{D_c}}}}$ is returned to ${\mathscr {A}}_{2}$. When the adversary ${\mathscr {A}}_{2}$ submits this query on $ID_{j}$, ${\mathscr {C}}$ searches in $L_{PK_{1}}$ and $L_{PK_{2}}$ for tuples $(I{D_c},{s_{I{D_c}}},{R_{I{D_c}}})$ and $(I{D_c},{x_{I{D_c}}},{P_{I{D_c}}})$. ${\mathscr {C}}$ returns $P_{ID_c} = ({P_{I{D_c}}},{R_{I{D_c}}})$ to ${\mathscr {A}}_{2}$. Otherwise ${\mathscr {C}}$ makes Extract private key query and returns $P_{ID_c}$ to ${\mathscr {A}}_{2}$.

• Send query:

  • 1. When the adversary ${\mathscr {A}}_{2}$ submits Send $(\varPi _C^j,{``\text {start} ''})$ query, ${\mathscr {C}}$ randomly chooses $U,{k_1},k_2 \in {G_1}$ and returns $(I{D_j},U)$ to ${\mathscr {A}}_{2}$.

  • 2. When the adversary ${\mathscr {A}}_{2}$ submits Send $(\varPi _S^i,(I{D_j},U))$ query to the server and $I{D_c}\ne I{D_j}$, ${\mathscr {C}}$ randomly chooses an integer $\alpha \in {\mathbb {Z}}_q^*$, computes ${k_3}=sU$, $k_4=x_{ID_s}U$, and $Auth = {H_2}(P_{pub},I{D_c},\alpha ,U,{k_3},{k_4})$. Note that the simulator does not know the s. Otherwise $I{D_c} =I{D_j}$, ${\mathscr {C}}$ fails and terminates. Finally ${\mathscr {C}}$ returns $(\alpha ,Auth)$ to ${\mathscr {A}}_{2}$.

  • 3. When the adversary ${\mathscr {A}}_{2}$ submits Send $(\varPi _C^j,(\alpha ,Auth))$ query to the client and $I{D_c}\ne I{D_j}$, ${\mathscr {C}}$ checks whether $Auth\mathop =\limits ^? {H_2}(P_{pub},I{D_c}, \alpha ,U,{k_1},k_2)$. If it holds, ${\mathscr {C}}$ finds $(I{D_c},{s_{I{D_c}}},{R_{I{D_c}}})$ and $(I{D_c},{x_{I{D_c}}},{P_{I{D_c}}})$ in $L_{PK_{1}}$ and $L_{PK_{2}}$ respectively. ${\mathscr {C}}$ computes $k_{I{D_c}}={H_3}(I{D_c},{P_{I{D_c}}}, {R_{I{D_c}}},P_{pub},\alpha ,U,Auth)$, carries out $H_{5}$ query and obtains $Q_{i}={H_4}(I{D_c},{P_{I{D_c}}},{R_{I{D_c}}},P_{pub},\alpha ,U,Auth)$. Let $(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth,{Q_i},{t_i},{c_i})$ be the corresponding tuple on $L_{H_{4}}$. If $c_{i}=0$, the simulation is failed and stopped by ${\mathscr {C}}$. Else, $c_{i}=1$ and ${Q_i} = {t_i}P$ are set. ${\mathscr {C}}$ defines $V=({k_{I{D_c}}}{x_{I{D_c}}} + {s_{I{D_c}}})Q$. Then, ${\mathscr {C}}$ returns V to ${\mathscr {A}}_{2}$. If $I{D_c}=I{D_j}$, ${\mathscr {C}}$ is achieved correctly since ${\mathscr {A}}_{2}$ is not capable to satisfy $Auth^{'}$ because of the lack of $k_1$ and $k_2$.

  • 4. When the adversary ${\mathscr {A}}_{2}$ submits Send $(\varPi _S^i,(V))$ query to the server, ${\mathscr {C}}$ computes $k_{ID_c}=H_3(ID_c,P_{ID_c},R_{ID_c}, P_{pub},\alpha ,U,Auth)$ and $Q_{i}={H_4}(I{D_c},{P_{I{D_c}}},{R_{I{D_c}}},P_{pub}, \alpha ,U,Auth)$. ${\mathscr {C}}$ checks $e({V_i},P)=e({Q_i},{k_{I{D_c}}}{P_{I{D_c}}}+ {R_{I{D_c}}}+ {h_{I{D_c}}}{P_{pub}})$. If it holds, ${\mathscr {C}}$ accepts and terminates. Else, ${\mathscr {C}}$ terminates.

• Forgery Eventually, ${\mathscr {A}}_2$ outputs a valid signature $(I{D_c},{V^{'}})$. If $I{D_c} \ne ID_j$, ${\mathscr {C}}$ stops the simulation. Otherwise, ${\mathscr {C}}$ finds $(I{D_c},{s_{I{D_c}}},{R_{I{D_c}}})$ and $(I{D_c},{x_{I{D_c}}},{P_{I{D_c}}})$ in $L_{PK_{1}}$ and $L_{PK_{2}}$, respectively. Then, ${Q_n}= {H_4}(I{D_c},{P_{I{D_c}}},{R_{I{D_c}}},{P_{pub}},\alpha ,U,Auth)$ is computed by ${\mathscr {C}}$ while this equality $e({V_n},P) = e({Q_n},{k_{I{D_c}}}{P_{I{D_c}}} + {R_{I{D_c}}} + {h_{I{D_c}}}{P_{pub}})$ is tested to ensure that the $V_n$ is satisfied the equality. If is satisfied, the simulation is terminated by ${\mathscr {C}}$ while $PK_{ID_{c}}$ is noted as the original public key. The corresponding tuple on $L_{H_{4}}$ is assumed with $(I{D_c},{P_{I{D_c}}},{R_{I{D_c}}}, P_{pub},\alpha ,U,Auth,{Q_n},{t_n},{c_n})$. If $c_{n}=1$, the simulation is failed and stopped by ${\mathscr {C}}$. Else, $c_{n}=0$ and ${Q_n}= bP+ {t_i}P$ is computed. Therefore, ${V_i}= {t_i}(b + {t_i}P)({k_{I{D_c}}}a + {r_{I{D_c}}}+ {h_{I{D_c}}}s)P$. As done in Forking Lemma (Pointcheval and Stern 1996, 2000), ${\mathscr {C}}$ outputs ${({t_i}{k_{I{D_c}}})^{ - 1}}({V_i} -t_i^2({k_{I{D_c}}}{P_{I{D_c}}} + {R_{I{D_c}}} + {h_{I{D_c}}}X)- {t_i}({r_{I{D_c}}}+ {h_{I{D_c}}}s)Y)$ as the solution of the CDH assumption.

• Analysis: Analysis is similar to the description in Lemma 1.

$\square$

4.2 Key exchange

The following Theorem 2 demonstrates that a key exchange is provided by our protocol under CDH assumption. The proof is given by the declaration in Lemma 1 and 2.

Theorem 2

We assume that the value of b in Test query can be guessed by ${\mathscr {A}}_i$ where $\{i=1,2\}$ with a non-negligible advantage $\varepsilon$. Then, the CDH assumption is solved by a challenger ${\mathscr {C}}$ with a non-negligible probability. At most $q_S$ qu-eries to the oracle $\varPi _{s}^{i}$ of the server, $q_c$ queries to the oracle $\varPi _C^j$ of the client, and $q_{H_i}$ queries on $H_i$ oracle $\forall i \in \{1,2,...,5\}$ are made by ${\mathscr {C}}$.

Lemma 1

The proposed protocol can’t be broken under CDH assumption by the type I adversary ${\mathscr {A}}_{1}$ in the random oracle model.

Proof

The coin in the Test query can be perfectly guessed with the probability 1 / 2 by ${\mathscr {A}}_1$. If the coin can be guessed by ${\mathscr {A}}_1$ with advantage $\varepsilon$, then the session key can be obtained correctly with advantage $\Pr [Ocsk] \ge \varepsilon /2$. The event that can achieving the correct session key is denoted by Osk. The success events of the oracle $\varPi ^j_C$ of the client and the oracle $\varPi ^i_S$ of the server are assumed by $Test(C^{j})$ and Test($S^{i}$) respectively, while the event that succeed to break the client-server authentication is assumed by $E^{C2S}$. Test query may be submitted by ${\mathscr {A}}_1$ to the client, then the following probability is had

$$\begin{aligned}&\Pr [Ocsk \wedge Test({S^i}) \wedge E^{C2S}] + \Pr [Ocsk \wedge Test({S^i}) \wedge \lnot E^{C2S}]\\&\quad + \Pr [Ocsk \wedge Test({C^j})] \ge \frac{\varepsilon }{2} \end{aligned}$$

for specific j and i. Then, the following probability is had

$$\begin{aligned}&\Pr [Ocsk \wedge Test({S^i}) \wedge \lnot E^{C2S}] + \Pr [Ocsk \wedge Test({C^j})] \\&\quad \ge \frac{\varepsilon }{2} - \Pr _{C2S} \end{aligned}$$

for specific j and i. The queries of ${\mathscr {A}}_1$ is answered by the algorithm ${\mathscr {C}}$ to prove Lemma 1. We assume that the random elements (P, $X=aP$, and $Y=bP$) $\in {\mathbb {G}}_{1}$ are received by ${\mathscr {C}}$ while $\forall a,b \in {\mathbb {Z}}_q^*$ are unknown values. The value of abP is derived by ${\mathscr {C}}$ with answering the ${\mathscr {A}}_1$’s oracle queries as follows:

• Setup ($1^k$) The system parameters $\{e,{G_1},{G_2},P,{P_{pub}},H_1,H_2,H_3,H_4\}$ are generated by ${\mathscr {C}}$ where $P_{pub}=Y$ and are sent to ${\mathscr {A}}_1$. An identity $ID_j$ is selected randomly by ${\mathscr {C}}$ as the challenge identity in this game. For queries and responses six lists $L_{H_{1}}$, $L_{H_{2}}$, $L_{H_{3}}$, $L_{H_{4}}$, $L_{PK_{1}}$ and $L_{PK_{2}}$ are maintained by ${\mathscr {C}}$ to avoid collision and consistency.

• $H_{1}$ query: When the adversary ${\mathscr {A}}_{1}$ submits this query on ($I{D_c}$,${R_{I{D_c}}},{P_{pub}}$). ${\mathscr {C}}$ randomly chooses $h_1\in {\mathbb {Z}}_q^*$ and returns it to ${\mathscr {A}}_{1}$. ${\mathscr {C}}$ updates $L_{H_{1}}$ with ($I{D_c},{R_{I{D_c}}},{P_{pub}},h_{1}$).

• $H_{2}$ query: Whenever ${\mathscr {A}}_{1}$ submits this query on $({P_{pub}},I{D_c},\alpha ,U,k_{1},k_2)$, ${\mathscr {C}}$ randomly chooses $h_2\in {\mathbb {Z}}_q^*$ and returns it to ${\mathscr {A}}_{1}$. ${\mathscr {C}}$ updates $L_{H_{2}}$ with $({P_{pub}},I{D_c},\alpha ,U,k_{1},k_2,h_{2})$.

• $H_{3}$ query: When the adversary ${\mathscr {A}}_{1}$ submits this query on ($I{D_c},P_{ID_c},R_{ID_c},{P_{pub}},\alpha ,U,Auth$), ${\mathscr {C}}$ randomly chooses $h_3\in {\mathbb {Z}}_q^*$ and returns it to ${\mathscr {A}}_{1}$. ${\mathscr {C}}$ updates $L_{H_{3}}$ with ($ID_c,P_{ID_c},R_{ID_c},{P_{pub}},\alpha ,U,Auth,h_{3}$).

• $H_{4}$ query: the following reactions are done by ${\mathscr {C}}$:

  • 1. If $L_{H_{4}}$ consists of $(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth,Q_i,t_i,c_i)$, ${\mathscr {C}}$ returns $Q_{i}$ to ${\mathscr {A}}_{1}$.

  • 2. Else, a coin ${c_i} \in \{ 0,1\}$ is flipped with $\Pr [{c_i} = 0] = 1/({q_s} + 1)$ and $Q_i = \mathrm{{ }}(\mathrm{{1}} - {c_i})Y + {t_i}P$ is computed by ${\mathscr {C}}$ while ${t_i} \in {\mathbb {Z}}_q^*$ is generated randomly. Finally, $(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth,Q_i,t_i,c_i)$ is added to $L_{H_{4}}$ and $Q_{i}$ is returned to ${\mathscr {A}}_{1}$ by ${\mathscr {C}}$.

• Extract partial private key query When the adversary ${\mathscr {A}}_{1}$ submits this query on $ID_{c}$, ${\mathscr {C}}$ generates two random numbers ${a_{I{D_c}}},{b_{I{D_c}}} \in {\mathbb {Z}}_n^*$, sets ${R_{I{D_c}}}= {a_{I{D_c}}}P$, ${h_{I{D_c}}}= {H_1}(I{D_c},{R_{I{D_c}}},{P_{pub}}) = {b_{I{D_c}}}$, ${r_{I{D_c}}} = {a_{I{D_c}}}$, and ${s_{I{D_c}}} = {r_{I{D_c}}} + {h_{I{D_c}}}s$. Then, ${\mathscr {C}}$ adds $(I{D_{I{D_c}}},{R_{I{D_c}}},{h_{I{D_c}}})$ and $(I{D_{I{D_c}}},{R_{I{D_c}}},{s_{I{D_c}}})$ to $L_{H_{1}}$ and $L_{PK_{1}}$, separately.

• Extract private key query When ${\mathscr {A}}_{1}$ submits this query on $ID_{c}$, the following reactions are done by ${\mathscr {C}}$:

  • 1. If $I{D_c} \ne ID_j$, ${\mathscr {C}}$ searches in list $L_{PK_{2}}$ and returns full private key $(x_{ID_c},D_{ID_c})$ to ${\mathscr {A}}_{1}$.

  • 2. Otherwise, ${\mathscr {C}}$ stops and terminates.

• Request public key query: When this query on $ID_{j}$ is submitted by ${\mathscr {A}}_{1}$, $(I{D_c},{s_{I{D_c}}},{R_{I{D_c}}})$ and $(I{D_c},{x_{I{D_c}}},{P_{I{D_c}}})$ are looked in $L_{PK_{1}}$ and $L_{PK_{2}}$ respectively by ${\mathscr {C}}$. Then, $P{K_{_{I{D_c}}}} = ({P_{I{D_c}}},{R_{I{D_c}}})$ is computed by ${\mathscr {C}}$. Otherwise, Extract private key query is made by ${\mathscr {C}}$. Finally, $P{K_{_{I{D_c}}}}$ is returned to ${\mathscr {A}}_{1}$.

• Replace public key query: Whenever ${\mathscr {A}}_{1}$ submits this query on $(ID_j,P_{ID_j}^{'},R_{ID_c}^{'})$, ${\mathscr {C}}$ searches in $L_{PK_1}$ and $L_{PK_2}$ for tuples $(ID_c,s_{ID_c},R_{ID_c})$ and $(ID_c,x_{ID_c},P_{ID_c})$. ${\mathscr {C}}$ sets $P_{ID_c} = P_{ID_c}^{'}$, $R_{ID_c} = R_{ID_c}^{'}$, $s_{ID_c} = \bot$ and $x_{ID_c} = \bot$.

• Send query:

  • 1. When the adversary ${\mathscr {A}}_{1}$ submits Send $(\varPi _C^j, {``\text {start} ''})$ query, ${\mathscr {C}}$ randomly chooses $r \in {\mathbb {Z}}^{*}_{q}$. ${\mathscr {C}}$ computes $U=rP, k_{1}=rP_{pub}$, $k_2=rP_{ID_s}$, and returns $(I{D_j},U)$ to ${\mathscr {A}}_{1}$.

  • 2. When the adversary ${\mathscr {A}}_{1}$ submits Send $(\varPi _S^i,(I{D_j},U))$ query to the server and $I{D_c} \ne I{D_j}$, ${\mathscr {C}}$ randomly chooses an integer $\alpha \in {\mathbb {Z}}_q^*$, computes ${k_3}=sU$, ${k_4} =x_{ID_c}U$ and $Auth = {H_2}(P_{pub},I{D_c},\alpha ,U,{k_3},{k_4})$. Note that the s isn’t known by the. Otherwise $I{D_c} =I{D_j}$, ${\mathscr {C}}$ fails and terminates. Finally, ${\mathscr {C}}$ returns $(\alpha ,Auth)$ to ${\mathscr {A}}_{1}$.

  • 3. When the adversary ${\mathscr {A}}_{1}$ submits Send $(\varPi _C^j,(\alpha ,Auth))$ query to the client and $I{D_c} \ne I{D_j}$, ${\mathscr {C}}$ checks whether $Auth\mathop = \limits {H_2}(P_{pub},I{D_c},\alpha ,U,{k_1}, {k_2})$. If it holds, ${\mathscr {C}}$ finds $(I{D_c},{s_{I{D_c}}},{R_{I{D_c}}})$ and $(I{D_c},{x_{I{D_c}}},{P_{I{D_c}}})$ in $L_{PK_{1}}$ and $L_{PK_{2}}$, respectively. ${\mathscr {C}}$ computes $k_{ID_c}=H_3(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth)$, carries out $H_{4}$ query and obtains $Q_{i}=H_4(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth)$. Let $(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth,{Q_i},{t_i},{c_i})$ be the corresponding tuple in the list $L_{H_{4}}$. If $c_{i}=0$, the simulation is failed and stopped by ${\mathscr {C}}$. Else, $c_{i}=1$ and ${Q_i} = {t_i}P$ are set. ${\mathscr {C}}$ defines $V=({k_{I{D_c}}}{x_{I{D_c}}} + {s_{I{D_c}}})Q$, then ${\mathscr {C}}$ returns V to ${\mathscr {A}}_{1}$. If $I{D_c}=I{D_j}$, ${\mathscr {C}}$ is achieved correctly since ${\mathscr {A}}_{1}$ is not capable to satisfy $Auth^{'}$ because of the lack of $k_1$ and $k_2$.

  • 4. When the adversary ${\mathscr {A}}_{1}$ submits Send $(\varPi _S^i,(V))$ query, to the server, ${\mathscr {C}}$ computes $k_{ID_c}=H_3(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth)$ and $Q_{i}={H_4}(I{D_c},{P_{I{D_c}}},{R_{I{D_c}}},P_{pub},\alpha ,U,Auth)$. ${\mathscr {C}}$ checks $e({V_i},P) = e({Q_i},{k_{I{D_c}}}{P_{I{D_c}}} + {R_{I{D_c}}} + {h_{I{D_c}}}{P_{pub}})$. If it holds, ${\mathscr {C}}$ accepts and terminates. Else, ${\mathscr {C}}$ terminates.

• Corrupt query If the adversary ${\mathscr {A}}_{1}$ submits a Corrupt query on $ID_{c}$, ${\mathscr {C}}$ returns $D_{ID_{c}}$.

• Reveal query When the adversary ${\mathscr {A}}_{1}$ submits a Reveal query and the oracle of the participate u for $u\in c,s$ has accepted, ${\mathscr {C}}$ returns the session key sk.

• Test query When the adversary ${\mathscr {A}}_{1}$ submits a Test query and the query is not requesting, ${\mathscr {C}}$ sets $U=X$ as an instance of CDH assumption and aborts. Else, a fair coin b is flipped by ${\mathscr {C}}$. if $b=1$. if not; a randomly string is returned to ${\mathscr {A}}_1$.

From above interactions with ${\mathscr {A}}_1$, without the occurs of $E^{C2S}$, ${\mathscr {C}}$ is correctly indistinguishable from our scheme. Note that the events $\exists i,Ocsk \wedge Test({S^i}) \wedge \lnot E^{C2S}$ and $\exists j,Ocsk \wedge Test({C^j})$ are equivalent, then we have

$$\begin{aligned} \Pr [Ocsk \wedge Test({C^j})] \ge \varepsilon /2 -\Pr _{C2S} \end{aligned}$$

also, we have the following probability

$$\begin{aligned} \Pr \left[ {sk = {H_2}({P_{pub}},I{D_c},\alpha ,U,{k_1},k_2)|_{U,{k_1},k_2 \leftarrow {G_1}}^{\alpha \in \mathrm{Z}_q^*}} \right] \ge \frac{\varepsilon }{2}-\Pr _{C2S} \end{aligned}$$

Assume that if $\varepsilon$ is non-negligible, then the $(\varepsilon /2) - {\Pr _{C2S}}$ is $\varepsilon$ since the $\Pr _{C2S}$ is negligible by Theorem 1. Assume that the coin b in Test query is guessed with an advantage $\varepsilon$ by ${\mathscr {A}}_{1}$. Given $(P,{P_{pub}} = bP=Y,U= aP=X)$ to ${\mathscr {A}}_{1}$. The instances $abP=k_1$, $abP=k_2$, $abP=k_3$, and $abP=k_4$ can be computed with an advantage $\varepsilon$ by ${\mathscr {A}}_{1}$. The CDH assumption is resolved with a non-negligible advantage while ${\mathscr {A}}_{1}$ is used by ${\mathscr {C}}$. Indeed, our protocol provides a secure key exchange. $\square$

Lemma 2

The proposed protocol can’t be broken under CDH assumption by the type II adversary ${\mathscr {A}}_{1}$ in the random oracle model.

Proof

The coin in the Test query can be perfectly guessed with the probability 1 / 2 by ${\mathscr {A}}_1$. If the coin can be guessed by ${\mathscr {A}}_1$ with an advantage $\varepsilon$, then the session key can be obtained correctly with advantage $\Pr [Ocsk] \ge \varepsilon /2$. The event that can achieving the correct session key is denoted by Osk. The success events of the oracle $\varPi ^j_C$ of the client and the oracle $\varPi ^i_S$ of the server are assumed by $Test(C^{j})$ and Test($S^{i}$) respectively, while the event that succeed to break the client-server authentication is assumed by $E^{C2S}$. Test query may be submitted by ${\mathscr {A}}_1$ to the client, then the following probability is had

$$\begin{aligned}&\Pr [Ocsk \wedge Test({S^i}) \wedge E^{C2S}] + \Pr [Ocsk \wedge Test({S^i}) \wedge \lnot E^{C2S}] \\&\quad + \Pr [Ocsk \wedge Test({C^j})] \ge \frac{\varepsilon }{2} \end{aligned}$$

for specific j and i. Then, the following probability is had

$$\begin{aligned}&\Pr [Ocsk \wedge Test({S^i}) \wedge \lnot E^{C2S}] + \Pr [Ocsk \wedge Test({C^j})] \\&\quad \ge \frac{\varepsilon }{2} - \Pr _{C2S} \end{aligned}$$

for specific j and i. The queries of ${\mathscr {A}}_2$ is answered by the algorithm ${\mathscr {C}}$ to prove Lemma 1. We assume that the random elements (P, $X=aP$, and $Y=bP$) $\in {\mathbb {G}}_{1}$ are received by ${\mathscr {C}}$ while $\forall a,b \in {\mathbb {Z}}_q^*$ are unknown values. The value of abP is derived by ${\mathscr {C}}$ with answering the ${\mathscr {A}}_2$’s oracle queries as follows:

• Setup ($1^k$) The system parameters $\{e,{G_1},{G_2},P,{P_{pub}},H_1,H_2,H_3,H_4\}$ are generated by ${\mathscr {C}}$ where $P_{pub}=Y$ and are sent to ${\mathscr {A}}_2$. An identity $ID_j$ is selected randomly by ${\mathscr {C}}$ as the challenge identity in this game. For queries and responses six lists $L_{H_{1}}$, $L_{H_{2}}$, $L_{H_{3}}$, $L_{H_{4}}$, $L_{PK_{1}}$ and $L_{PK_{2}}$ are maintained by ${\mathscr {C}}$ to avoid collision and consistency.

• $H_{1} query$ When the adversary ${\mathscr {A}}_{2}$ submits this query on ($I{D_c}$,${R_{I{D_c}}},{P_{pub}}$). ${\mathscr {C}}$ randomly chooses $h_1\in {\mathbb {Z}}_q^*$ and returns it to ${\mathscr {A}}_{2}$. ${\mathscr {C}}$ updates $L_{H_{1}}$ with ($I{D_c},{R_{I{D_c}}},{P_{pub}},h_{1}$).

• $H_{2} query$ When the adversary ${\mathscr {A}}_{2}$ submits this query on $({P_{pub}},I{D_c},\alpha ,U,k_{1},k_2)$, ${\mathscr {C}}$ randomly chooses $h_2\in {\mathbb {Z}}_q^*$ and returns it to ${\mathscr {A}}_{2}$. ${\mathscr {C}}$ updates $L_{H_{2}}$ with $({P_{pub}},I{D_c},\alpha ,U,k_{1},k_2,h_{2})$.

• $H_{3} query$ When the adversary ${\mathscr {A}}_{2}$ submits this query on ($I{D_c},{P_{I{D_c}}}{R_{I{D_c}}},{P_{pub}},\alpha ,U,Auth$), ${\mathscr {C}}$ randomly chooses $h_3 \in {\mathbb {Z}}_q^*$ and returns it to ${\mathscr {A}}_{2}$. ${\mathscr {C}}$ updates $L_{H_{3}}$ with ($I{D_c},{P_{I{D_c}}},{R_{I{D_c}}},{P_{pub}},\alpha ,U,Auth,h_{3}$).

• $H_{4} query$ When the adversary ${\mathscr {A}}_{2}$ submits this query on $(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth)$, the following reactions are done by ${\mathscr {C}}$:

  • 1. If $L_{H_{4}}$ consists of $(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U, Auth,{Q_i},{t_i},{c_i})$, ${\mathscr {C}}$ returns $Q_{i}$ to ${\mathscr {A}}_{2}$.

  • 2. Else, a coin ${c_i} \in \{ 0,1\}$ is flipped with $\Pr [{c_i} = 0] = 1/({q_s} + 1)$ and $Q_i = \mathrm{{ }}(\mathrm{{1}} - {c_i})Y + {t_i}P$ is computed by ${\mathscr {C}}$ while ${t_i} \in {\mathbb {Z}}_q^*$ is generated randomly. Finally, $(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth,Q_i,t_i,c_i)$ is added to $L_{H_{4}}$ and $Q_{i}$ is returned to ${\mathscr {A}}_{2}$ by ${\mathscr {C}}$.

• Extract private key query: When The adversary ${\mathscr {A}}_{2}$ submits this query on $ID_{c}$, the following reactions are done by ${\mathscr {C}}$:

  • 1. If $I{D_c} \ne ID_j$, ${\mathscr {C}}$ searches in $L_{PK_{2}}$ and returns full private key $(x_{ID_c},D_{ID_c})$ to ${\mathscr {A}}_{2}$.

  • 2. Otherwise, ${\mathscr {C}}$ stops and terminates.

• Request public key query: When this query on $ID_{j}$ is submitted by ${\mathscr {A}}_{2}$, $(I{D_c},{s_{I{D_c}}},{R_{I{D_c}}})$ and $(I{D_c},{x_{I{D_c}}},{P_{I{D_c}}})$ are looked in $L_{PK_{1}}$ and $L_{PK_{2}}$ respectively by ${\mathscr {C}}$. Then, $P{K_{_{I{D_c}}}} = ({P_{I{D_c}}},{R_{I{D_c}}})$ is computed by ${\mathscr {C}}$. Otherwise, Extract private key query is made by ${\mathscr {C}}$. Finally, $P{K_{_{I{D_c}}}}$ is returned to ${\mathscr {A}}_{2}$. When the adversary ${\mathscr {A}}_{2}$ submits this query on $ID_{j}$, ${\mathscr {C}}$ searches in $L_{PK_{1}}$ and $L_{PK_{2}}$ for tuples $(I{D_c},{s_{I{D_c}}},{R_{I{D_c}}})$ and $(I{D_c},{x_{I{D_c}}},{P_{I{D_c}}})$. ${\mathscr {C}}$ returns $P_{ID_c} = ({P_{I{D_c}}},{R_{I{D_c}}})$ to ${\mathscr {A}}_{2}$. Otherwise ${\mathscr {C}}$ makes Extract private key query and returns $P_{ID_c}$ to ${\mathscr {A}}_{2}$.

• Send query

  • 1. When the adversary ${\mathscr {A}}_{2}$ submits Send $(\varPi _C^j, {``\text {start} ''})$ query, ${\mathscr {C}}$ randomly chooses $w\in {\mathbb {Z}}^{*}_{q}$ and ${\mathscr {C}}$ computes $U=rP, k_{1}=rP_{pub}$, $k_2=rP_{ID_s}$ and returns $(I{D_j},U)$ to ${\mathscr {A}}_{2}$.

  • 2. When the adversary ${\mathscr {A}}_{2}$ submits Send $(\varPi _S^i,(I{D_j},U))$ query to the server and $I{D_c} \ne I{D_j}$, ${k_3} = sU$, ${k_4}= x_{ID_s}U$, and $Auth = {H_2}(P_{pub},I{D_c},\alpha ,U,{k_3},{k_4})$ are computed by ${\mathscr {C}}$ while $\alpha \in {\mathbb {Z}}_q^*$ is chosen randomly. Note that the s isn’t known by the simulator. Otherwise $I{D_c} =I{D_j}$, ${\mathscr {C}}$ fails and terminates. Finally, ${\mathscr {C}}$ returns $(\alpha ,Auth)$ to ${\mathscr {A}}_{2}$.

  • 3. When the adversary ${\mathscr {A}}_{2}$ submits Send $(\varPi _C^j,(\alpha ,Auth))$ query to the client and $I{D_c} \ne I{D_j}$, ${\mathscr {C}}$ checks whether $Auth\mathop = \limits ^? {H_2}(P_{pub},I{D_c},\alpha ,U,{k_1},k_2)$. If it holds, ${\mathscr {C}}$ finds $(I{D_c},{s_{I{D_c}}},{R_{I{D_c}}})$ and $(I{D_c},{x_{I{D_c}}},{P_{I{D_c}}})$ in $L_{PK_1}$ and $L_{PK_2}$, respectively. ${\mathscr {C}}$ computes $k_{ID_c}=H_3(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth)$, carries out $H_{4}$ query and obtains $Q_{i}=H_4(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth)$. Let $(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth,{Q_i},{t_i},{c_i})$ be the corresponding tuple on the list $L_{H_{4}}$. If $c_{i}=0$, the simulation is failed and stopped by ${\mathscr {C}}$. Else, $c_{i}=1$ and ${Q_i} = {t_i}P$ are set. ${\mathscr {C}}$ defines $V =({k_{I{D_c}}}{x_{I{D_c}}} + {s_{I{D_c}}})Q$ then ${\mathscr {C}}$ returns V to ${\mathscr {A}}_{2}$. If $I{D_c} =I{D_j}$, ${\mathscr {C}}$ works perfectly since ${\mathscr {A}}_{2}$ is unable to verify $Auth^{'}$ because of the lack of $k_1$ and $k_2$.

  • 4. When the adversary ${\mathscr {A}}_{2}$ submits Send $(\varPi _S^i,(V))$ query, to the server. ${\mathscr {C}}$ computes $k_{ID_c}=H_3(ID_c,P_{ID_c},R_{ID_c},P_{pub},\alpha ,U,Auth)$ and $Q_{i}=H_4(ID_c,P_{ID_c},R_{ID_c},P_{pub}, \alpha ,U,Auth)$. ${\mathscr {C}}$ checks $e({V_i},P) = e({Q_i},{k_{I{D_c}}}{P_{I{D_c}}} + {R_{I{D_c}}} + {h_{I{D_c}}}{P_{pub}})$. If it holds, ${\mathscr {C}}$ accepts and terminates. Else, ${\mathscr {C}}$ terminates.

• Corrupt query If the adversary ${\mathscr {A}}_{2}$ submits Corrupt query on $ID_{c}$, ${\mathscr {C}}$ returns the corresponding $D_{ID_{c}}$.

• Reveal query When the adversary ${\mathscr {A}}_{2}$ submits Reveal query and the oracle of the participate u for $u\in c,s$ has accepted, ${\mathscr {C}}$ returns the session key sk,

• Test query When the adversary ${\mathscr {A}}_{2}$ submits Test query and the query is not asked in the session, ${\mathscr {C}}$ sets $U=X$ as an instance of CDHP and aborts. Else, a fair coin b is flipped by ${\mathscr {C}}$. if $b=1$. if not; a randomly string is returned to ${\mathscr {A}}_2$.

By the answers to the queries above, ${\mathscr {C}}$ is perfectly indistinguishable from our protocol unless the event $E^{C2S}$ occurs. Note that the events $\exists i,Ocsk \wedge Test({S^i}) \wedge \lnot E^{C2S}$ and $\exists j,Ocsk \wedge Test({C^j})$ are equivalent, then we have

$$\begin{aligned} \Pr [Ocsk \wedge Test({C^j})] \ge \varepsilon /2 - \Pr _{C2S} \end{aligned}$$

also, we have the following probability

$$\begin{aligned} \Pr \left[ {sk = {H_2}({P_{pub}},I{D_c},\alpha ,U,{k_1},k_2)|_{U,{k_1},k_2 \leftarrow {G_1}}^{\alpha \in \mathrm{Z}_q^*}} \right] \ge \frac{\varepsilon }{2}-Pr_{C2S} \end{aligned}$$

Assume that if $\varepsilon$ is non-negligible, then the $(\varepsilon /2) - {\Pr _{C2S}}$ is $\varepsilon$ since the $\Pr _{C2S}$ is negligible by Theorem 1. Assume that the coin b in Test query is guessed with an advantage $\varepsilon$ by ${\mathscr {A}}_{1}$. Given $(P,{P_{pub}} = bP=Y,U= aP=X)$ to ${\mathscr {A}}_{1}$. The instances $abP=k_1$, $abP=k_2$, $abP=k_3$, and $abP=k_4$ can be computed with an advantage $\varepsilon$ by ${\mathscr {A}}_{1}$. The CDH assumption is resolved with a non-negligible advantage while ${\mathscr {A}}_{1}$ is used by ${\mathscr {C}}$. Hence, our protocol provides a secure key exchange. $\square$

4.3 Server-to-client authentication

The following Theorem 3 demonstrates that the interaction from the server to the client can’t be impersonated by ${\mathscr {A}}_i$ where $\{i=1,2\}$ under the CDH assumption.

Theorem 3

We assume that the server-to-client authentication can be broken by adversary ${\mathscr {A}}_i$ where $\{i=1,2\}$ with an advantage $\varepsilon$. Then, the CDH assumption is solved by ${\mathscr {C}}$ with a non-negligible probability. At most $q_S$ queries to the oracle $\varPi _{S}^{i}$ of the server, $q_C$ queries to the oracle $\varPi _C^j$ of the client, and $q_{H_i}$ queries on $H_i$ oracle $\forall i \in \{1,2,...,5\}$ are made by ${\mathscr {C}}$.

Proof

Let the algorithm be as presented previously in Theorem 2. Without the event $E^{C2S}$ is happened, Our protocol is correctly indistinguishable from ${\mathscr {C}}$. The event that break the server-to-client authentication is denoted by $E^{S2C}$. The event $E^{S2C}$ is accursed specifically, when $(I{D_j},U = X)$ is sent and $(\alpha ,Auth)$ is accepted by the client. Note that $(\alpha ,Auth)$ is not processed by the right server. Due to this circumstance one of the following condition will be occurred:

• 1. ${\mathscr {A}}_i$ guessed the value Auth with a probability less than $q_C/2^k$.

• 2. the value U occurred in another session with a probability $q_c/q\times ({q_C} - 1)$ less than $q_C^2/q$.

• 3. ${\mathscr {A}}_i$ asked ${H_2}({P_{pub}},I{D_j},\alpha ,{U, k_3,k_4})$ with a probability $\Pr [({P_{pub}},I{D_j},\alpha ,{U,k_3,k_4})|{P_{pub}}{ \in _R}{G_1},{k_3} = bU, {k_4}=bU ]$.

Then we have

$$\begin{aligned} \Pr [E^{S2C}|\lnot E^{C2S}]&\le \Pr [{P_{pub}},I{D_j},\alpha ,{U, k_3}, k_4)|{P_{pub}}{ \in _R}{G_1},{k_3},{k_4} \\&= b.U] + \frac{q_C}{2^k} + \frac{q_C^2}{q} \end{aligned}$$

The queries of ${\mathscr {A}}_i$ is answered by the algorithm ${\mathscr {C}}$ to prove Theorem 3. We assume that the random elements (P, $X=aP$, and $Y=bP$) $\in {\mathbb {G}}_{1}$ are received by ${\mathscr {C}}$ while $\forall a,b \in {\mathbb {Z}}_q^*$ are unknown values. The value of abP is derived by ${\mathscr {C}}$ with answering the ${\mathscr {A}}_i$’s oracle queries. The challenged identity $ID_{j}$ is selected randomly by ${\mathscr {C}}$ while ${P_{pub}}=Y$, and $U=X$ are set. Given $(P,U,{P_{pub}}) = (P,X,Y)$ to the adversary ${\mathscr {A}}_i$. Then, ${\mathscr {A}}_i$ computes $abP = bX = k_3$ and $abP = bX = k_4$ with probability $\varepsilon$. After that, ${\mathscr {C}}$ uses ${\mathscr {A}}_i$ to compute abP. ${\mathscr {C}}$ solves the CDH assumption with the ${\varepsilon ^{'}} \ge \varepsilon - q_c/2^k - q_c^2/q$ is non-negligible. Hence, our protocol is secure against ${\mathscr {A}}_i$ and provides server-to-client authentication. $\square$

5 Performance analysis

The computation cost, the communication cost and the security properties are assessed in this section. The proposed scheme is compared with (Wu and Tseng 2010), (He 2012), and (Tsai and Lo 2015) protocols. Due to convenience, the following notations are defined to evaluate the computational cost:

• $T_{e}$: The time of $e:{\mathbb {G}}_{1} \times {\mathbb {G}}_{1} \rightarrow {\mathbb {G}}_{2}$.

• $T_{M}$: The time of a scalar multiplication operation of ${\mathbb {G}}_{1}$.

• $T_{i}$: The time of performing a modular inversion operation.

• $T_{A}$: The time of an addition operation of ${\mathbb {G}}_{1}$.

• $T_{H}$: The performing time of a one-way hash function.

Table 2 The comparison based on the computation and communication costs

Table 3 Comparison based on the security proprieties

Table 4 Various security levels of our experiment (Bits)

The computation and communication costs analysis of our protocol is represented in Table 2 compared with specific related protocols. Table 3 shows that the security properties that are provided by our protocol more than the other protocols.

We have implemented four schemes using java pairing-based cryptography Library (JPBC) (De Caro and Iovino 2011), on an Intel Core i $3-3110$ CPU dual core 2.40 and GHz 2.40 GHz and machine with 4 GB RAM for the server and Honor EMUI 4.0.1 CPU Octa-core 1.5 GHz with 2.0 GB RAM for the client (mobile device). We have employed Type A pairings constructed from the curve $y^2 = x^3 + x$ over the field $F_p$ for some prime $p = 3$ mod 4. Our experimental, entailed 80-bit, 112-bit and 128-bit AES key sizes security levels (Daemen and Rijmen 2013) as shown in Table 4.

Fig 3 and Fig 4 respectively show the computational costs of the client side and the server-side for the four schemes at 80-bit, 112-bit and 128-bit security levels. The proposed scheme has higher computational cost than the other schemes because of using the CL-PKC.

Fig. 5 shows the communication cost, we assume that $|m| = \frac{160}{8}$ bytes , $|ID| = \frac{80}{8}$ bytes and $|{\mathbb {G}}_{1}|=1024$ bits using an elliptic curve with $q=\frac{160}{8}$ bytes. By using the standard compression technique in (Shim et al. 2013), the size of ${\mathbb {G}}_{1}$ can be reduced to 65 bytes. A comparison of the computation cost for various schemes is as follows:

• 1. Communication cost in (Wu and Tseng 2010) is $|ID|+2|{\mathbb {Z}}^{*}_{q}|+2|{\mathbb {G}}_{1}|=10+2 \times 20+2 \times 65=180$ bytes.

• 2. Communication cost in (He 2012) is $|ID|+2|{\mathbb {Z}}^{*}_{q}|+3|{\mathbb {G}}_{1}|=10+2\times 20+3\times 65=245$ bytes.

• 3. Communication cost in (Tsai and Lo 2015) is $2|{\mathbb {Z}}^{*}_{q}|+3|{\mathbb {G}}_{1}|=2\times 20+3\times 65=235$ bytes.

• 4. Communication cost in our scheme is $|ID|+2|{\mathbb {Z}}^{*}_{q}|+2|{\mathbb {G}}_{1}|=10+2\times 20+2\times 65=180$ bytes.

According to Fig. 5 our scheme has a lower communication cost compared with that one obtained in He (2012) and Tsai and Lo (2015).

Fig. 3

The Client computational time

Fig. 4

The server computational time

Fig. 5

The Communication Cost

6 Application

When the information are communicated between the older person and the AAL server is sensitive, we need to consider the authentication and key exchange in this environment to prevent these information. The proposed scheme is suitable for the AAL applications that consider the authentication and key exchange. Here, we give application scenario that can be applicable to our scheme as shown in Fig. 6. In our application, the Controller (mobile device) is used as interface between the older person and the AAL server. The wearable sensors are connected to the controller sent data to the AAL server, which help the older person to care about his/her self. We assume that the server is the KGC in our protocol. The server runs the Setup algorithm to generate the public parameters and sends it to the client (controller). The older person sends his identity to the server. Since, the client identity is received by the AAL server, the partial private key ${D_{I{D_c}}}$ is computed and is sent to the client. Next, the Set private key and the public key ${P_{I{D_c}}}$ are performed by the client. Finally, the client and the server are cooperated to authenticate from each other by running the user authentication and key exchange algorithm.

Fig. 6

The application scenario

7 Conclusion

A new certificateless user authenticated key exchange protocol is introduced to preform the key escrow problem of the identity-based user authentication schemes. Our protocol provides a mutual authentication and under the CDH assumption its security is demonstrated in the random oracle model. The proposed protocol needs 4.738 seconds in the client side and 5.772 seconds in the server side, when the security level is 128 bit. Furthermore, the communication cost of our protocol is 180 bytes. Indeed, Our protocol can be applied in the assisted living systems environment.