Efficient identity-based authenticated key agreement protocol with provable security for vehicular ad hoc networks

Abstract

In vehicular ad hoc networks, establishing a secure channel between any two vehicles is fundamental. Authenticated key agreement is a useful mechanism, which can be used to negotiate a shared key for secure data transmission between authentic vehicles in vehicular ad hoc networks. Among the existing identity-based two-party authenticated key agreement protocols without pairings, there are only a few protocols that provide provable security in strong security models such as the extended Canetti–Krawczyk model. This article presents an efficient pairing-free identity-based one-round two-party authenticated key agreement protocol with provable security, which is more suitable for real-time application environments with highly dynamic topology such as vehicular ad hoc networks than the existing identity-based two-party authenticated key agreement protocols. The proposed protocol is proven secure under the passive and active adversaries in the extended Canetti–Krawczyk model based on the Gap Diffie–Hellman assumption. The proposed protocol can capture all essential security attributes including known-session key security, perfect forward secrecy, basic impersonation resistance, key compromise impersonation resistance, unknown key share resistance, no key control, and ephemeral secrets reveal resistance. Compared with the existing identity-based two-party authenticated key agreement protocols, the proposed protocol is superior in terms of computational cost and running time while providing higher security.

Introduction

The significant advances in the embedded technology and wireless communication drive the evolution of vehicular ad hoc networks (VANETs). Vehicular networks comprise three types of components: a trusted authority, road-side units (RSUs) distributed on the roadside, and Connected and Autonomous Vehicles (CAVs) with on-board units (OBUs). Drivers can make some decisions based on the sensed road and traffic information transmitted from other CAVs and RSUs nearby. In many VANET applications such as pothole collection, ¹ file sharing among familiar entities, ² and infotainment applications, the messages exchanged between two vehicles are sensitive and need to be kept secret. Due to the open nature of wireless links, it is crucial for VANETs to establish secure communications between any two vehicles. Compared with traditional public key encryption, symmetric key encryption with a shared key is more efficient in providing confidential communication. Authenticated key agreement (AKA) is an appealing mechanism in which authentic parties can agree on a shared session key over an open network to ensure the confidentiality, authentication, or integrity of subsequent session messages. For instance, in the literatures,^3–5 a key agreement protocol is used for a vehicle to update its pseudonym-private key pairs. In the literature, ⁶ a key agreement protocol is used to establish a vehicular cloud. In addition, AKA protocols achieve implicit authentication, that is, each party is assured that no party but the intended peers can possibly generate the shared session key, which is important in key agreement. The shared session key, which is generated from two or more parties as a function of their long-term keys and ephemeral materials, cannot be predetermined.

In 1993, Bellare and Rogaway ⁷ first presented a security model to formalize symmetric key-based AKA protocols. Based on the Bellare-Rogaway (BR) model, some security models for other types of AKA protocols were formalized, for example, AKA protocols with a trusted server, ⁸ AKA with key confirmation (AKC) protocols, ⁹ asymmetric key-based AKA protocols, ¹⁰ and AKA protocols against dictionary attack. ¹¹ However, these models do not capture ephemeral secrets reveal attack. The Canetti–Krawczyk (CK) model ¹² proposed in 2001 also does not completely cover ephemeral secrets reveal resistance (ESRR) because it cannot support the adversary’s Session-State Reveal queries against the test session. In addition, the CK model also does not catch forward security (FS) and key compromise impersonation resistance (KCIR). In 2005, Choo et al. ¹³ examined and compared the differences among these security models. Subsequently, LaMacchia et al. ¹⁴ made the extended CK (eCK) model to prove the security of AKA protocols in 2007. The eCK model can capture all essential security attributes including known-session key security (K-SKS), perfect forward security (PFS), basic impersonation resistance (BIR), KCIR, unknown key share resistance (UKSR), no key control (NKC), ESRR, and so on. Therefore, AKA protocols should be given formal proofs in the eCK model.

According to the number of involving parties, the existing AKA protocols are divided into three categories: (1) authenticated group KA protocols, (2) three-party AKA protocols, and (3) two-party AKA (2PAKA) protocols. According to the public key setting employed, previously proposed asymmetric key-based AKA protocols are roughly classified into three groups: (1) traditional public key infrastructure (PKI)-based AKA protocols, (2) identity (ID)-based AKA protocols, and (3) certificateless AKA protocols. In the traditional PKI-based 2PAKA protocols, the management of public key certificates is a heavy burden, which contains the maintenance, transmission, and authentication of certificates. To eliminate the certificate management problem, many research works^15–33 employed ID-based cryptography (IBC) first introduced by Shamir, ³⁴ in which a user’s public key is the user’s identities (e.g. telephone number, e-mail address, etc.) and the user’s private key is extracted based on his or her ID and a key generation center (KGC) master key. Therefore, these ID-based 2PAKA protocols^15–33 have improved the efficiency by removing the use of public key certificates. However, these ID-based 2PAKA protocols^15–33 were built using bilinear pairings, which is seen to be one of the most time-consuming operations. The operation cost of a pairing is about 3 to 20 times that of an elliptic curve point multiplication.^25,35,36 Consequently, in order to accomplish a better performance, some ID-based 2PAKA protocols without pairings^35,37–49 have been proposed. Unfortunately, among these pairing-free ID-based 2PAKA protocols,^35,37–49 only a few protocols^46–48 provide provable security in the eCK model. Moreover, the running times of these protocols^46–48 need to be further reduced if they are deployed in real-time application environments with highly dynamic topology such as VANETs. The reason is that the time for key agreement between any two vehicles should be minimized considering the fast moving and topology dynamic natures of VANETs. In addition, ID-based 2PAKA protocol with two message exchanges may be more attractive in reality. Therefore, it is a challenge to design a provably secure and efficient pairing-free ID-based one-round 2PAKA protocol that is more suitable for VANETs.

Related works

Since Boneh and Franklin ⁵⁰ first presented an ID-based encryption scheme from pairings in 2001, a great deal of ID-based 2PAKA protocols^15–33 have been designed using pairings, and some of them have been pointed out having security flaws later. These protocols were continuously devoted to seek a secure ID-based 2PAKA protocol with minimal pairing operations.

In order to remove the expensive pairing operation, Zhu et al. ³⁷ started the research of pairing-free ID-based 2PAKA protocol in 2007. However, Zhu et al.’s protocol realizes explicit authentication by introducing an ID-based signature scheme, which leads to larger computational cost and bandwidth. In addition, Zhu et al.’s protocol requires three message exchanges. After 1 year, Cao et al. ³⁸ put forward an ID-based 2PAKA protocol without pairings, which achieves implicit authentication but requires the same message exchanges as Zhu et al.’s protocol. In 2010, Fiore and Gennaro ³⁹ presented an ID-based 2PAKA protocol using exponentiation operation, which is proven secure in the CK model. However, the CK model cannot cover FS, KCIR, and ESRR. In order to reduce the message exchange, Cao et al. ³⁵ proposed another ID-based two-message 2PAKA protocol without pairings in 2010. Unfortunately, Hou and Xu^40,41 and Islam and Biswas ⁴² independently demonstrated that two protocols proposed by Cao et al. are vulnerable to ephemeral secrets reveal attack, in 2011 and 2012. However, Hou et al. and Islam et al.’s informal security analysis cannot guarantee that their protocols satisfy all essential security properties. Moreover, Islam et al.’s ⁴² protocol requires three message exchanges and the last message exchange may be intercepted by adversaries, which enable the two involved parties to have different session keys. In 2012, Xie and Wang ⁴³ used a signature scheme to realize mutual authentication in their protocol, which causes computation cost to be increased. In 2013, Vivek et al. ⁴⁴ put forward an ID-based 2PAKA protocol using exponentiation, which is provable secure in the CK model. Nevertheless, the CK model cannot ensure Vivek et al.’s protocol catches FS, KCIR, and ESRR. In addition, Vivek et al.’s protocol involves more exponentiation operations than Fiore et al.’s protocol. In 2015, Ghoreishi et al. ⁴⁵ and Sun et al., ⁴⁶ respectively, presented two pairing-free ID-based 2PAKA protocols. Ghoreishi et al. only analyzed the security of their protocol informally and roughly. It is clear that Ghoreishi et al.’s protocol cannot resist key compromise impersonation attack. Sun et al.’s protocol needs six elliptic curve point multiplication operations. Moreover, the formal proof in the eCK model does not take active adversaries into account. In 2016, Bala et al. ⁴⁷ put forward an ID-based 2PAKA protocols without pairings, which only needs four elliptic curve point multiplication operations. However, the security proof in the eCK model also does not consider active adversaries. In the same year, two other ID-based 2PAKA protocols were proposed by Ni et al., ⁴⁸ which require seven and five elliptic curve point multiplication operations, respectively. Ni et al.’s protocols are given the formal proofs under the passive and active adversaries in the eCK model. In 2017, Islam and Biswas ⁴⁹ put forward a pairing-free ID-based 2PAKA protocol. Unfortunately, the security analysis using Burrows-Abadi-Needham (BAN) logic model cannot guarantee that Islam et al.’s protocol is secure. ⁵¹

Our contributions

Our contributions are as below:

1. Our ID-based 2PAKA protocol is proven to be secure under the passive and active adversaries in the eCK model. Therefore, it can capture all essential security attributes including K-SKS, PFS, BIR, KCIR, UKSR, NKC,ESRR, and so on, which is also analyzed later.

2. Performance analysis demonstrates that our protocol has less computational cost and running time than previous ID-based 2PAKA protocols while providing stronger or the same level of security. For example, considering pre-computation, the running time of our protocol is 77.1% of Bala’s protocol, 36.8% of Ni-I protocol, and 53.8% of Ni-II protocol. In conclusion, our protocol is more applicable for VANETs than other existing protocols.

Outline of the article

The remainder of the article is arranged as below. In section “Preliminaries,” we review several computational problems and essential security attributes required by ID-based AKA protocols. The section “Proposed pairing-free ID-based 2PAKA protocol” describes the eCK model and then presents a pairing-free ID-based 2PAKA protocol. The section “Security analyses” gives a formal proof of the proposed protocol in the eCK model, analyzes essential security attributes that the proposed protocol catches, and compares the security of our protocol with the existing ID-based 2PAKA protocols. The section “Performance analyses” provides the performance analyses and comparisons between the proposed protocol and previous ID-based 2PAKA protocols. Finally, the article concludes in section “Conclusions and future works.”

Preliminaries

This section introduces the preliminaries including several computational problems and essential security attributes required in ID-based AKA protocols.

Computational problems

Let $\mathbb{G}$ be a q-order cyclic additive group of $E/{\mathbb{F}}_p$ , and $P$ be a generator of $\mathbb{G}$ . We recall elliptic curve discrete logarithm (ECDL), computational Diffie–Hellman (CDH), Decisional Diffie–Hellman (DDH), and Gap Diffie–Hellman (GDH) problems over the additive group as follows.

Definition 1 (ECDL problem)

Given $(P,\mathrm{xP})$ where unknown $x{\in }_R{\mathbb{Z}}_p^{*}$ , for any probabilistic polynomial time (PPT) algorithm, computing $x$ is intractable.

Definition 2 (CDH problem)

For unknown $x,y{\in }_R{\mathbb{Z}}_p^{*}$ , given $(P,\mathrm{xP},\mathrm{yP})$ , it is infeasible to compute $\mathrm{xyP}$ by any PPT algorithm.

Definition 3 (DDH problem)

For unknown $x,y,z{\in }_R{\mathbb{Z}}_p^{*}$ , given $(P,\mathrm{xP},\mathrm{yP},\mathrm{zP})$ , it is impossible to determine whether or not $z=\mathrm{xy}modq$ in PPT.

Definition 4 (GDH problem)

Given a DDH oracle and $(P,\mathrm{xP},\mathrm{yP})$ where $x,y{\in }_R{\mathbb{Z}}_p^{*}$ , for any PPT algorithm, the probability of computing $\mathrm{xyP}$ is negligible.

Essential security attributes

It is essential for ID-based 2PAKA protocols to satisfy the following security requirements. Suppose that two legal parties A and B run the protocol exactly.

1. K-SKS. Any session key should not be disclosed when an adversary has known the keys generated in some other sessions.

2. Forward secrecy (FS). If the long-term secrets of parties are leaked, past session keys should not be compromised. The security property falls into four types:

3. Perfect forward secrecy (PFS). The loss of all the parties’ long-term secrets should not make past session keys known.

4. Master key forward secrecy (MFS). The past session keys should not be endangered by the leakage of the KGC master private key.

5. Weak perfect forward secrecy (wPFS). In 2005, Krawczyk ⁵² showed that none of one-round AKA protocols can keep full PFS if the adversary can modify communications between the parties. Thus, one-round AKA protocols can achieve PFS under a passive adversary, which is defined as wPFS.

BIR. An adversary who does not acquire a party A’s long-term secret cannot disguise himself as A.

KCIR. The leakage of party A’s long-term secret cannot enable an adversary to masquerade as any other party to A.

UKSR. It will be prevented that two parties A and B compute the same session key but B deem that the key is negotiated with the adversary E.

NKC. No party can enforce the key in a session to a predetermined value.

ESRR. The compromise of one session’s ephemeral private keys cannot affect the security of the session key.

Proposed pairing-free ID-based 2PAKA protocol

This section first describes the eCK model and then presents a secure pairing-free ID-based one-round 2PAKA protocol $\Sigma$ for VANETs, which satisfies all the essential security attributes.

Security model

The original eCK model ¹⁴ was originally proposed for the conventional PKI-based AKA protocols. In order to formalize ID-based AKA protocols, the modified eCK model was presented by Huang and Cao ²⁸ and Ni et al., ²⁹ respectively.

Participants

The protocol participants are modeled as a group of parties, in which each party $I{D}_a$ is regarded as a PPT Turing machine. Any two parties can be involved in a run of the protocol. Each party may participate in a polynomial number of sessions at the same time. $\underset{a,b}{\overset{s}{\Pi }}$ denotes the sth session of party $I{D}_a$ communicating with intended peer $I{D}_b$ . A session $\underset{a,b}{\overset{s}{\Pi }}$ is completed by party $I{D}_a$ when $I{D}_a$ computes a session key.

Adversary model

The adversary $\mathcal{M}$ is regarded as a PPT Turing machine. The communication link is fully controlled by $\mathcal{M}$ . That is to say, $\mathcal{M}$ can possibly eavesdrop, suspend, intercept, replay, modify, and inject messages randomly. The power of the adversary is modeled by allowing it to issue the first six queries in any sequence:

1. $\mathrm{EphemeralKeyReveal}(\underset{\mathit{a},\mathit{b}}{\overset{\mathit{s}}{\Pi }})$ : The adversary $\mathcal{M}$ has access to the ephemeral private key of party $I{D}_a$ in session $\underset{a,b}{\overset{s}{\Pi }}$ .

2. $\mathrm{SessionKeyReveal}(\underset{\mathit{a},\mathit{b}}{\overset{\mathit{s}}{\Pi }})$ : The adversary $\mathcal{M}$ can get the key of a completed session $\underset{a,b}{\overset{s}{\Pi }}$ . The session $\underset{a,b}{\overset{s}{\Pi }}$ enters an opened state when the adversary $\mathcal{M}$ makes the query against it.

3. $\mathrm{StaticKeyReveal}(\mathit{I}{\mathit{D}}_{\mathit{a}})$ : The query returns party $I{D}_a$ ’s long-term secret to the adversary $\mathcal{M}$ .

4. MasterPrivateKeyReveal: The KGC master private key is revealed to the adversary $\mathcal{M}$ . MFS can be modeled by the query.

5. $\mathrm{EstablishParty}({\mathit{ID}}_{\mathit{a}})$ : The adversary $\mathcal{M}$ may register a lawful user in the name of party $I{D}_a$ and obtains ${\mathrm{ID}}_a$ ’s long-term secret by the query. Then party $I{D}_a$ is said to be not honest.

6. $\mathrm{Send}(\underset{\mathit{a},\mathit{b}}{\overset{\mathit{s}}{\Pi }},m)$ : The query enables the adversary $\mathcal{M}$ to send the message m to party $I{D}_a$ in the name of party $I{D}_b$ and control $I{D}_a$ to start the session $\underset{a,b}{\overset{s}{\Pi }}$ with party $I{D}_b$ . If $m=\lambda$ , party $I{D}_a$ launches the session $\underset{a,b}{\overset{s}{\Pi }}$ . Otherwise, if party $I{D}_a$ is an initiator, it only outputs a decision to the session (i.e. accept or reject it); if party $I{D}_a$ is a responder, party $I{D}_a$ selects an ephemeral secret and returns a message and a decision to the session.

7. $\mathrm{Test}(\underset{\mathit{a},\mathit{b}}{\overset{\mathit{s}}{\Pi }})$ : The query can be made to a fresh session $\underset{a,b}{\overset{s}{\Pi }}$ only once. A fair coin $b\in \{0,1\}$ is flipped. If $b=0$ , the session key is returned to the adversary, otherwise the adversary obtains a selected random value from the distribution of session key.

Definition 5 (matching session)

The session $\underset{a,b}{\overset{s}{\Pi }}$ has a matching session $\underset{b,a}{\overset{t}{\Pi }}$ when the session $\underset{b,a}{\overset{t}{\Pi }}$ is executed by the other party $I{D}_b$ with the same message exchanged, although in different sequence.

Definition 6 (fresh session)

Supposing $\underset{a,b}{\overset{s}{\Pi }}$ is a completed session and executed by honest party $I{D}_a$ with honest party $I{D}_b$ , $\underset{a,b}{\overset{s}{\Pi }}$ is a fresh session if none of the three cases occur:

1. Both the session key of $\underset{a,b}{\overset{s}{\Pi }}$ and its matching session $\underset{b,a}{\overset{t}{\Pi }}$ (if $\underset{b,a}{\overset{t}{\Pi }}$ exists) are leaked to the adversary.

2. $\underset{a,b}{\overset{s}{\Pi }}$ has a matching session $\underset{b,a}{\overset{t}{\Pi }}$ , and the adversary $\mathcal{M}$ obtains the long-term and ephemeral secret of party $I{D}_a$ in $\underset{a,b}{\overset{s}{\Pi }}$ or the long-term and ephemeral secret of party $I{D}_b$ in $\underset{b,a}{\overset{t}{\Pi }}$ .

3. The matching session of $\underset{a,b}{\overset{s}{\Pi }}$ does not exist, and the adversary $\mathcal{M}$ obtains the long-term and ephemeral secret of party $I{D}_a$ in $\underset{a,b}{\overset{s}{\Pi }}$ or the long-term secret of $I{D}_b$ .

In the first stage of the game, the adversary queries the first six oracles in any order. During the second stage, the adversary selects a fresh session $\underset{a,b}{\overset{s}{\Pi }}$ (see Definition 6) and makes a $\mathbf{Test}(\underset{\mathit{a},\mathit{b}}{\overset{\mathit{s}}{\Pi }})$ query. The game terminates as soon as the adversary outputs a guess $b\prime$ for b.

The adversary $\mathcal{M}$ wins the game when $b\prime =b$ and the test session is still fresh. Assuming k is the security parameter, the advantage of $\mathcal{M}$ in the game is denoted as

$$\mathrm{Ad}{v}_{\mathcal{M}}\left(k\right)=|\mathrm{Pr}\left[\mathcal{M}\mathrm{wins}\right]-\frac{1}{2}|$$

Definition 7 (secure 2PAKA protocols)

A 2PAKA protocol is deemed secure in the eCK model when the protocol satisfies the following two conditions:

1. Matching sessions executed by two parties, respectively, generate the same session key.

2. No any PPT adversary has a non-negligible advantage to win the above game.

Remark 1

In ID-based 2PAKA protocols, the shared session key can be computed by using four pieces of secret information: the long-term and ephemeral secrets of two involved parties. The eCK model allows the adversary to query the long-term secrets of two parties, the ephemeral secrets of two parties, or the long-term secret of one party and the ephemeral secret of the other party, but cannot know the long-term and ephemeral secrets of one party.

Protocol description

In our protocol, the trusted authority acts as KGC. Our protocol $\Sigma$ is composed of the following three parts:

Setup

With the security parameter $k$ , the trusted authority (acts as KGC) gets system parameters and its master public/private key pair as below:

1. Selects a $k$ -bit prime number $p$ and produces the parameters $〈E/{\mathbb{F}}_p,\mathbb{G},q,P〉$ , where $\mathbb{G}$ is a cyclic additive group over $E/{\mathbb{F}}_p$ with the order $q$ and $P$ is a generator of $\mathbb{G}$ .

2. Picks the master private key $s{\in }_R{\mathbb{Z}}_p^{*}$ , and sets $P_{\mathrm{pub}}=\mathrm{sP}$ as the master public key.

3. Chooses two cryptographic hash functions $H_1:\{0,1{\}}^{*}\times \mathbb{G}\to {\mathbb{Z}}_p^{*}$ and $H_2:\{0,1{\}}^{*}\times \{0,1{\}}^{*}\times \mathbb{G}\times \mathbb{G}\times \mathbb{G}\times \mathbb{G}\times \mathbb{G}\to \{0,1{\}}^k$ .

4. Publishes the parameters $〈E/{\mathbb{F}}_p,\mathbb{G},q,P,P_{\mathrm{pub}},H_1,H_2〉$ and keeps s secret.

Extract

Suppose the ID of a vehicle is $I{D}_i\in \{0,1{\}}^{*}$ , the trusted authority computes the long-term private key of the vehicle as below:

1. Picks randomly $r_i{\in }_R{\mathbb{Z}}_p^{*}$ , and computes $R_i=r_{i}P$ and $h_i=H_1(I{D}_i||R_i)$ .

2. Computes $s_i=r_i+h_{i}smodq$ and sets the key pair $(s_i,R_i)$ as the long-term private key of the vehicle.

3. Return the key pair $(s_i,R_i)$ to the vehicle in a safe manner.

Upon receiving the key pair, the vehicle can validate its correctness by checking if the equation $s_{i}P=R_i+H_1(I{D}_i||R_i)P_{\mathrm{pub}}$ holds. The long-term public key of the vehicle is $P{K}_i=s_{i}P$ .

Key agreement

Suppose that vehicle A with ID $I{D}_A$ wishes to agree a key with vehicle B with ID $I{D}_B$ . Figure 1 shows the proposed ID-based two-message 2PAKA protocol that proceeds as follows:

1. A randomly selects $a{\in }_R{\mathbb{Z}}_p^{*}$ as its ephemeral private key, computes its ephemeral public keys $T_A^1=a{R}_A$ , $T_A^2=a{P}_{\mathrm{pub}}$ , and then sends $(I{D}_A,R_A,T_A^1,T_A^2)$ to B

   $$A\to B:I{D}_A,R_A,T_A^1,T_A^2$$

2. Upon receiving A’s message, B selects $b{\in }_R{\mathbb{Z}}_p^{*}$ at random as its ephemeral private key, calculates its ephemeral public keys $T_B^1=b{R}_B$ , $T_B^2=b{P}_{\mathrm{pub}}$ , and then sends $(I{D}_B,R_B,T_B^1,T_B^2)$ to A

   $$B\to A:I{D}_B,R_B,T_B^1,T_B^2$$

3. A computes $K_{\mathrm{AB}}=a{s}_A(T_B^1+H_1(I{D}_B||R_B)T_B^2)$ and the shared session key $\mathrm{sk}=H_2(I{D}_A||I{D}_B||T_A^1||T_A^2||T_B^1||T_B^2||K_{\mathrm{AB}})$ .

4. B computes $K_{\mathrm{BA}}=b{s}_B(T_A^1+H_1(I{D}_A||R_A)T_A^2)$ and the shared session key $\mathrm{sk}=H_2(I{D}_A||I{D}_B||T_A^1||T_A^2||T_B^1||T_B^2||K_{\mathrm{BA}})$ .

Figure 1.

Proposed ID-based two-message 2PAKA protocol for VANETs.

Consistency

The correctness of the protocol is proved as follows

$$\begin{array}{cc}\multicolumn{1}{c}{K_{\mathrm{AB}}}& =a{s}_A(T_B^1+H_1(I{D}_B||R_B)T_B^2)\hfill \\ \multicolumn{1}{c}{}& =a{s}_A(b{R}_B+H_1(I{D}_B||R_B)b{P}_{\mathrm{pub}})\hfill \\ \multicolumn{1}{c}{}& =a{s}_{A}b{s}_{B}P\hfill \\ \multicolumn{1}{c}{K_{\mathrm{BA}}}& =b{s}_B(T_A^1+H_1(I{D}_A||R_A)T_A^2)\hfill \\ \multicolumn{1}{c}{}& =b{s}_B(a{R}_A+H_1(I{D}_A||R_A)a{P}_{\mathrm{pub}})\hfill \\ \multicolumn{1}{c}{}& =b{s}_{B}a{s}_{A}P=K_{\mathrm{AB}}\hfill \end{array}$$

Thus, A and B can get the same session key

$$\begin{array}{c}\multicolumn{1}{c}{\mathrm{sk}=H_2(I{D}_A||I{D}_B||T_A^1||T_A^2||T_B^1||T_B^2||K_{\mathrm{AB}})}\\ \multicolumn{1}{c}{=H_2(I{D}_A||I{D}_B||T_A^1||T_A^2||T_B^1||T_B^2||K_{\mathrm{BA}})}\end{array}$$

Security analyses

This section first proves that the proposed ID-based 2PAKA protocol is secure in the eCK model, and then analyzes the security attributes that the proposed protocol captures.

Security proof

Theorem 1

Assume that GDH problem is intractable and $H_1$ and $H_2$ are random oracles, the protocol $\Sigma$ proposed in section “Proposed pairing-free ID-based 2PAKA protocol” is said to be secure in the eCK model.

Proof 1

If the two conditions shown in Definition 7 hold, the proposed ID-based 2PAKA protocol $\Sigma$ is deemed secure in the eCK model. The correctness proof of the protocol $\Sigma$ guarantees that matching sessions executed by two involved parties, respectively, generate the same session key. Therefore, the first condition holds. Next, we will demonstrate that the second condition also holds. Namely, no any PPT adversary against the protocol $\Sigma$ can win the game described in section “Security model” with non-negligible probability.

Assume that $k$ is the security parameter and the adversary $\mathcal{M}$ against the protocol $\Sigma$ succeeds in the game outlined above with non-negligible probability ${\mathrm{Adv}}_{\mathcal{M}}^{\Sigma }(k)$ . Suppose that no more than $p(k)$ honest parties are activated by the adversary $\mathcal{M}$ and each party is engaged in at most $s(k)$ sessions. Assume that the adversary $\mathcal{M}$ chooses the Sth protocol session $\underset{A,B}{\overset{S}{\Pi }}$ initiated by party $I{D}_A$ communicating with party $I{D}_B$ as the test session in the game. The adversary $\mathcal{M}$ differentiates between the test session key and a random value only through the following three ways:

1. Guessing attack: The adversary $\mathcal{M}$ conjectures the test session key rightly.

2. Key replication attack: The adversary $\mathcal{M}$ succeeds in establishing a session, which does not match the test session but possesses the same session key with it. Therefore, $\mathcal{M}$ can know the test session key by querying the key of the non-matching session.

3. Forging attack: At some point, $\mathcal{M}$ queries $H_2$ on $(I{D}_A,I{D}_B,T_A^1,T_A^2,T_B^1,T_B^2,K_{\mathrm{AB}})$ in the test session. It is obvious that the adversary $\mathcal{M}$ computes the value $K_{\mathrm{AB}}$ itself.

Since the session key’s size is k bit, the success probability of guessing attack is $\mathcal{O}(1/2^k)$ . If two sessions are not matched, the key derivation function $H_2$ has the same input with probability $\mathcal{O}(s(k{)}^2/2^k)$ . Consequently, the first two attacks succeed with negligible probability.

In the following, forging attack is analyzed by employing a reduction approach. A challenger $\mathcal{S}$ executes the eCK game described in section “Security model” with $\mathcal{M}$ against the protocol $\Sigma$ . In the course of the game, the challenger $\mathcal{S}$ makes a response to all queries of $\mathcal{M}$ . If the adversary $\mathcal{M}$ is successful in forging attack with non-negligible probability ${\mathrm{Adv}}_{\mathcal{M}}^{\Sigma }(k)$ , the challenger $\mathcal{S}$ can utilize $\mathcal{M}$ to solve the GDH problem with non-negligible probability ${\mathrm{Adv}}_{\mathcal{S}}^{\mathrm{GDH}}(k)$ . Given a GDH problem instance $(X=\mathrm{xP},Y=\mathrm{yP})$ where $x,y{\in }_R{\mathbb{Z}}_p^{*}$ , the challenger $\mathcal{S}$ ’s task is to compute $\mathrm{GDH}(X,Y)=\mathrm{xyP}$ with the help of a DDH oracle. When the game begins, the challenger $\mathcal{S}$ ascertains the test session that the adversary $\mathcal{M}$ selects is $\underset{A,B}{\overset{S}{\Pi }}$ with probability greater than $1/p(k{)}^{2}s(k)$ . According to the fresh definition in the eCK model, there are two cases that require attention: (1) the matching session of $\underset{A,B}{\overset{S}{\Pi }}$ (i.e. $\underset{B,A}{\overset{T}{\Pi }}$ ) exists; (2) the test session $\underset{A,B}{\overset{S}{\Pi }}$ has no matching session. In the first case, the adversary is passive and faithfully transmits the messages between party $I{D}_A$ and party $I{D}_B$ . In the second case, the challenger $\mathcal{S}$ also needs to face an active adversary that may alter $I{D}_B$ ’s public key material $R_B$ . Based on the above analysis and the fresh definition, the challenger $\mathcal{S}$ has to guess the strategy that the adversary $\mathcal{M}$ adopts from the following six choices:

• S1. $\mathcal{M}$ does not know $I{D}_A$ ’s ephemeral private key and $I{D}_B$ ’s long-term private key, and $\mathcal{M}$ correctly transmits $I{D}_B$ ’s public key material $R_B$ .

• S2. $\mathcal{M}$ does not know the long-term private keys of $I{D}_A$ and $I{D}_B$ , and $\mathcal{M}$ correctly transmits $I{D}_B$ ’s public key material $R_B$ .

• S3. $\mathcal{M}$ does not know the ephemeral private keys of $I{D}_A$ and $I{D}_B$ .

• S4. $\mathcal{M}$ does not know $I{D}_A$ ’s long-term private key and $I{D}_B$ ’s ephemeral private key.

• S5. $\mathcal{M}$ does not know $I{D}_A$ ’s ephemeral private key and $I{D}_B$ ’s long-term private key, and the adversary $\mathcal{M}$ may alter $I{D}_B$ ’s public key material $R_B$ .

• S6. $\mathcal{M}$ does not know the long-term private keys of $I{D}_A$ and $I{D}_B$ , and the adversary $\mathcal{M}$ may alter $I{D}_B$ ’s public key material $R_B$ .

The success probability that $\mathcal{S}$ chooses both the test session and the strategy is larger than $1/6p(k{)}^{2}s(k)$ . Next, we will analyze the six strategies.

S1

$\mathcal{M}$ does not know $I{D}_A$ ’s ephemeral private key and $I{D}_B$ ’s long-term private key, and $\mathcal{M}$ correctly transmits $I{D}_B$ ’s public key material $R_B$ .

Setup

The challenger $\mathcal{S}$ sets the KGC’s master public key and all parties’ long-term keys as follows:

1. $\mathcal{S}$ randomly selects a value $P_{\mathrm{pub}}\in \mathbb{G}$ as the KGC’s master public key.

2. $\mathcal{S}$ selects $h_B{\in }_R{\mathbb{Z}}_p^{*}$ as $H_1(I{D}_B||R_B)$ , computes $R_B=Y-h_B{P}_{\mathrm{pub}}$ , and sets $(\perp ,R_B)$ as party $I{D}_B$ ’s long-term private key. Therefore, party $I{D}_B$ ’s long-term public key $P{K}_B=R_B+h_B{P}_{\mathrm{pub}}=Y$ .

3. $\mathcal{S}$ picks $h_i,s_i{\in }_R{\mathbb{Z}}_p^{*}$ , computes $R_i=s_{i}P-h_i{P}_{\mathrm{pub}}$ , sets $H_1(I{D}_i||R_i)=h_i$ , and sets $(s_i,R_i)$ as long-term private key of party $I{D}_i(i\ne B)$ . Therefore, $I{D}_i$ ’s long-term public key $P{K}_i=R_i+h_i{P}_{\mathrm{pub}}=s_{i}P$ .

4. For each party $I{D}_i$ , $\mathcal{S}$ passes $(I{D}_i,R_i)$ to $\mathcal{M}$ , and inserts the entry $(I{D}_i,R_i,h_i)$ to $H_1^{\mathrm{list}}$ .

Queries

$\mathcal{S}$ maintains three initially empty lists $H_1^{\mathrm{list}}$ , $H_2^{\mathrm{list}}$ , and $R^{\mathrm{list}}$ to handle the $H_1$ , $H_2$ , and SessionKeyReveal queries. $\mathcal{S}$ responds to the queries issued by $\mathcal{M}$ as follows:

1. $H_1(I{D}_i,R_i)$ . After the challenger $\mathcal{S}$ sets long-term private keys to party $I{D}_i$ , $\mathcal{S}$ adds the entry $(I{D}_i,R_i,h_i)$ to $H_1^{\mathrm{list}}$ . If an $H_1$ query issued by the adversary $\mathcal{M}$ matches one entry in the list $H_1^{\mathrm{list}}$ , $\mathcal{S}$ returns $h_i$ of the entry to $\mathcal{M}$ . Otherwise, $\mathcal{S}$ selects $h_i{\in }_R{\mathbb{Z}}_p^{*}$ , inserts the entry $(I{D}_i,R_i,h_i)$ to $H_1^{\mathrm{list}}$ , and responds with the randomly chosen value.

2. $H_2(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,K_{\mathrm{ij}})$ . At first, $\mathcal{S}$ maintains an empty list $H_2^{\mathrm{list}}$ in which each entry is the form of $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,K_{\mathrm{ij}},h_2)$ .

3. Otherwise, $\mathcal{S}$ looks up the matching entry in the list $R^{\mathrm{list}}$ . If the entry exists and $i=B$ , $\mathcal{S}$ checks if $K_{\mathrm{ij}}$ is correctly generated by verifying whether $\mathrm{DDH}((T_i^1+h_i{T}_i^2),(T_j^1+h_j{T}_j^2),K_{\mathrm{ij}})=1$ . If $K_{\mathrm{ij}}$ is correct, the challenger $\mathcal{S}$ sets $h_2=\mathrm{sk}$ , and stores the new entry $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,K_{\mathrm{ij}},h_2)$ to the list $R^{\mathrm{list}}$ . If the entry exists and $i\ne B$ , the challenger $\mathcal{S}$ sets $h_2=\mathrm{sk}$ , and stores the new entry $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,K_{\mathrm{ij}},h_2)$ to the list $H_2^{\mathrm{list}}$ . Otherwise (no such an entry exists in the list $R^{\mathrm{list}}$ or $K_{\mathrm{ij}}$ is not correctly generated), the challenger $\mathcal{S}$ selects $h_2\in \{0,1{\}}^k$ at random and adds the entry $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,K_{\mathrm{ij}},h_2)$ to the list $H_2^{\mathrm{list}}$ .

$\mathrm{EstablishParty}(I{D}_i)$ . $\mathcal{S}$ selects $h_i,s_i{\in }_R{\mathbb{Z}}_p^{*}$ , computes $R_i=s_{i}P-h_i{P}_{\mathrm{pub}}$ , sets $H_1(I{D}_i||R_i)=h_i$ , and reveals $I{D}_i$ ’s long-term private key $(s_i,R_i)$ to the adversary $\mathcal{M}$ . $\mathcal{M}$ totally controls the party $I{D}_i$ .

$\mathrm{StaticKeyReveal}(I{D}_i)$ . If $i\ne B$ , $\mathcal{S}$ returns $(s_i,R_i)$ to $\mathcal{M}$ . Otherwise, $\mathcal{S}$ aborts.

MasterPrivateKeyReveal. $\mathcal{S}$ aborts.

$\mathrm{EphemeralSecretReveal}(\underset{i,j}{\overset{s}{\Pi }})$ . If $\underset{i,j}{\overset{s}{\Pi }}=\underset{A,B}{\overset{S}{\Pi }}$ , $\mathcal{S}$ aborts. Otherwise, $\mathcal{S}$ reveals the ephemeral private key to $\mathcal{M}$ .

$\mathrm{Send}(\underset{i,j}{\overset{s}{\Pi }},m)$ . At first, the challenger $\mathcal{S}$ maintains an empty list $R^{\mathrm{list}}$ in which each entry is the form of $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,\mathrm{sk})$ .

If $\underset{i,j}{\overset{s}{\Pi }}=\underset{A,B}{\overset{S}{\Pi }}$ and $m=\lambda$ , $\mathcal{S}$ picks $U\in \mathbb{G}$ , and then returns $s_{A}X-h_{A}U$ and U to $\mathcal{M}$ .

If $i=B$ and $m=(s_{j}Z-h_{j}W,W)$ , $\mathcal{S}$ randomly chooses $V\in \mathbb{G}$ , chooses $b{\in }_R{\mathbb{Z}}_p^{*}$ as its ephemeral private key, and returns $\mathrm{bY}-h_{B}V$ and $V$ to the adversary $\mathcal{M}$ . Then, $\mathcal{S}$ looks for the matching entry in the list $H_2^{\mathrm{list}}$ . If the entry exists, $\mathcal{S}$ checks if $K_{\mathrm{ij}}$ is correctly generated by verifying whether $\mathrm{DDH}((T_i^1+h_i{T}_i^2),(T_j^1+h_j{T}_j^2),K_{\mathrm{ij}})=1$ . If $K_{\mathrm{ij}}$ is correct, the challenger $\mathcal{S}$ sets $\mathrm{sk}=h_2$ , and adds the new entry $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,\mathrm{sk})$ to the list $R^{\mathrm{list}}$ . Otherwise (no such an entry exists in the list $H_2^{\mathrm{list}}$ or $K_{\mathrm{ij}}$ is not correctly generated), the challenger $\mathcal{S}$ chooses $\mathrm{sk}\in \{0,1{\}}^k$ at random and adds the entry $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,\mathrm{sk})$ to the list $R^{\mathrm{list}}$ .

If $i\ne B$ , $\mathcal{S}$ responds in accordance with the protocol specification.

$\mathrm{SessionKeyReveal}(\underset{i,j}{\overset{s}{\Pi }})$ . If $\underset{i,j}{\overset{s}{\Pi }}=\underset{A,B}{\overset{S}{\Pi }}$ or $\underset{i,j}{\overset{s}{\Pi }}=\underset{B,A}{\overset{T}{\Pi }}$ , $\mathcal{S}$ aborts. Otherwise, $\mathcal{S}$ returns the stored value $\mathrm{sk}$ in the list $R^{\mathrm{list}}$ to $\mathcal{M}$ .

$\mathrm{Test}(\underset{i,j}{\overset{s}{\Pi }})$ . If $\underset{i,j}{\overset{s}{\Pi }}=\underset{A,B}{\overset{S}{\Pi }}$ , $\mathcal{S}$ selects $\xi \in \{0,1{\}}^k$ and returns it to the adversary $\mathcal{M}$ . Otherwise, $\mathcal{S}$ aborts.

Analysis

If the adversary $\mathcal{M}$ succeeds in forging attack with non-negligible probability, $\mathcal{M}$ should have made a query to $H_2$ with the input $K_{\mathrm{AB}}=s_A\mathrm{DLOG}(X)(\mathrm{bY}-h_{B}V+h_{B}V)=s_A\mathrm{DLOG}(X)\mathrm{bY}$ . To settle the $\mathrm{GDH}(X,Y)$ problem, $\mathcal{S}$ verifies whether there is an $H_2$ query issued by $\mathcal{M}$ on the value $(I{D}_A,I{D}_B,T_A^1,T_A^2,T_B^1,T_B^2,K_{\mathrm{AB}})$ , such that $\mathrm{DDH}((T_A^1+h_A{T}_A^2),(T_B^1+h_B{T}_B^2),K_{\mathrm{AB}})=1$ . If there is such an $H_2$ query, the challenger solves $\mathrm{GDH}(X,Y)=\mathrm{DLOG}(X)Y=(b{s}_A{)}^{-1}{K}_{\mathrm{AB}}$ . $\mathcal{S}$ correctly computes the GDH problem with the following advantage

$${\mathrm{Adv}}_{\mathcal{S}}^{\mathrm{GDH}}\left(k\right)\ge \frac{{\mathrm{Adv}}_{\mathcal{M}}^{\Sigma }\left(k\right)}{6p{(k)}^{2}s\left(k\right)}$$

S2

$\mathcal{M}$ does not know the long-term private keys of $I{D}_A$ and $I{D}_B$ , and $\mathcal{M}$ correctly transmits $I{D}_B$ ’s public key material $R_B$ .

Setup

The challenger $\mathcal{S}$ sets the KGC’s master public key and all parties’ long-term keys as below:

1. The challenger $\mathcal{S}$ selects a value $P_{\mathrm{pub}}\in \mathbb{G}$ as the KGC’s master public key.

2. For the party $I{D}_A$ , $\mathcal{S}$ selects $h_A{\in }_R{\mathbb{Z}}_p^{*}$ as $H_1(I{D}_A||R_A)$ , computes $R_A=X-h_A{P}_{\mathrm{pub}}$ , and sets $(\perp ,R_A)$ as party $I{D}_A$ ’s long-term private key. Therefore, party $I{D}_A$ ’s long-term public key $P{K}_A=R_A+h_A{P}_{\mathrm{pub}}=X$ .

3. For the party $I{D}_B$ , $\mathcal{S}$ selects $h_B{\in }_R{\mathbb{Z}}_p^{*}$ as $H_1(I{D}_B||R_B)$ , computes $R_B=Y-h_B{P}_{\mathrm{pub}}$ , and sets $(\perp ,R_B)$ as party $I{D}_B$ ’s long-term private key. Therefore, party $I{D}_B$ ’s long-term public key $P{K}_B=R_B+h_B{P}_{\mathrm{pub}}=Y$ .

4. For any party $I{D}_i$ ( $i\ne A$ and $i\ne B$ ), $\mathcal{S}$ selects $h_i,s_i{\in }_R{\mathbb{Z}}_p^{*}$ , computes $R_i=s_{i}P-h_i{P}_{\mathrm{pub}}$ , sets $H_1(I{D}_i||R_i)=h_i$ , and sets $(s_i,R_i)$ as long-term private key of party $I{D}_i$ . Therefore, party $I{D}_i$ ’s long-term public key $P{K}_i=R_i+h_i{P}_{\mathrm{pub}}=s_{i}P$ .

5. For each party $I{D}_i$ , $\mathcal{S}$ passes $(I{D}_i,R_i)$ to $\mathcal{M}$ , and inserts the entry $(I{D}_i,R_i,h_i)$ to $H_1^{\mathrm{list}}$ .

Queries

$\mathcal{S}$ maintains three initially empty lists $H_1^{\mathrm{list}}$ , $H_2^{\mathrm{list}}$ , and $R^{\mathrm{list}}$ to handle the $H_1$ , $H_2$ , and SessionKeyReveal queries. $\mathcal{S}$ responds to the queries issued by $\mathcal{M}$ as follows. Note that $\mathcal{S}$ answers $H_1(I{D}_i,R_i)$ , $\mathrm{EstablishParty}(I{D}_i)$ , MasterPrivateKeyReveal, $\mathrm{SessionKeyReveal}(\underset{\mathcal{i}\mathcal{,}\mathcal{j}}{\overset{s}{\Pi }})$ , and $\mathrm{Test}(\underset{i,j}{\overset{s}{\Pi }})$ as it does in S1.

1. $H_2(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,K_{\mathrm{ij}})$ . At first, $\mathcal{S}$ maintains an empty list $H_2^{\mathrm{list}}$ in which each entry consists of $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,K_{\mathrm{ij}},h_2)$ .

2. Otherwise, $\mathcal{S}$ looks for the matching entry in the list $R^{\mathrm{list}}$ . If the entry exists and $i=A$ or $i=B$ , $\mathcal{S}$ checks if $K_{\mathrm{ij}}$ is correctly generated by verifying whether $\mathrm{DDH}((T_i^1+h_i{T}_i^2),(T_j^1+h_j{T}_j^2),K_{\mathrm{ij}})=1$ . If $K_{\mathrm{ij}}$ is correct, the challenger $\mathcal{S}$ sets $h_2=\mathrm{sk}$ , and stores the new entry $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,K_{\mathrm{ij}},h_2)$ to the list $H_2^{\mathrm{list}}$ . If the entry exists and $i\ne A$ and $i\ne B$ , the challenger $\mathcal{S}$ sets $h_2=\mathrm{sk}$ , and stores the new entry $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,K_{\mathrm{ij}},h_2)$ to the list $H_2^{\mathrm{list}}$ . Otherwise (no such an entry exists in the list $R^{\mathrm{list}}$ or $K_{\mathrm{ij}}$ is not correctly generated), the challenger $\mathcal{S}$ randomly chooses $h_2\in \{0,1{\}}^k$ and adds the entry $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,K_{\mathrm{ij}},h_2)$ to the list $H_2^{\mathrm{list}}$ .

$\mathrm{StaticKeyReveal}(I{D}_i)$ . If $i\ne A$ and $i\ne B$ , $\mathcal{S}$ returns $(s_i,R_i)$ to $\mathcal{M}$ . Otherwise, $\mathcal{S}$ aborts.

$\mathrm{EphemeralSecretReveal}(\underset{i,j}{\overset{s}{\Pi }})$ . $\mathcal{S}$ responds to $\mathcal{M}$ with the ephemeral private key.

$\mathrm{Send}(\underset{i,j}{\overset{s}{\Pi }},m)$ . At first, $\mathcal{S}$ maintains an empty list $R^{\mathrm{list}}$ whose each entry is $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,\mathrm{sk})$ .

If $\underset{i,j}{\overset{s}{\Pi }}=\underset{A,B}{\overset{S}{\Pi }}$ , the challenger $\mathcal{S}$ randomly chooses $U\in \mathbb{G}$ , chooses $a{\in }_R{\mathbb{Z}}_p^{*}$ as its ephemeral private key, and then returns $\mathrm{aX}-h_{A}U$ and U to the adversary $\mathcal{M}$ .

If $i=B$ , the challenger $\mathcal{S}$ randomly chooses $V\in \mathbb{G}$ , chooses $b{\in }_R{\mathbb{Z}}_p^{*}$ as its ephemeral private key, and returns $\mathrm{bY}-h_{B}V$ and V to the adversary $\mathcal{M}$ . Then $\mathcal{S}$ simulates the oracle in the same way as does in S1.

If $i=A$ , the simulation of $\mathcal{S}$ is similar to that when $i=B$ .

Otherwise, the challenger $\mathcal{S}$ responds according to the protocol specification.

Analysis

If the adversary $\mathcal{M}$ is successful in forging attack with non-negligible probability, $\mathcal{M}$ should have made a query to $H_2$ with the input $K_{\mathrm{AB}}=\mathrm{aDLOG}(X)(\mathrm{bY}-h_{B}V+h_{B}V)=\mathrm{abDLOG}(X)Y$ . To settle the $\mathrm{GDH}(X,Y)$ problem, $\mathcal{S}$ verifies whether there is an $H_2$ query issued by $\mathcal{M}$ on the value $(I{D}_A,I{D}_B,T_A^1,T_A^2,T_B^1,T_B^2,K_{\mathrm{AB}})$ , such that $\mathrm{DDH}((T_A^1+h_A{T}_A^2),(T_B^1+h_B{T}_B^2),K_{\mathrm{AB}})=1$ . If there is such an $H_2$ query, $\mathcal{S}$ calculates $\mathrm{GDH}(X,Y)=\mathrm{DLOG}(X)Y=(\mathrm{ab}{)}^{-1}{K}_{\mathrm{AB}}$ . $\mathcal{S}$ correctly computes the GDH problem with the following advantage

$${\mathrm{Adv}}_{\mathcal{S}}^{\mathrm{GDH}}\left(k\right)\ge \frac{{\mathrm{Adv}}_{\mathcal{M}}^{\Sigma }\left(k\right)}{6p{(k)}^{2}s\left(k\right)}$$

S3

$\mathcal{M}$ does not know the ephemeral private keys of $I{D}_A$ and $I{D}_B$ .

Setup

The challenger $\mathcal{S}$ sets the master keys of KGC and all parties’ long-term keys as below:

1. $\mathcal{S}$ selects $s{\in }_R{\mathbb{Z}}_p^{*}$ as the master private key of KGC and computes $P_{\mathrm{pub}}=\mathrm{sP}$ as the master public key of KGC. Therefore, S3 simulates MFS.

2. $\mathcal{S}$ picks $h_i,s_i{\in }_R{\mathbb{Z}}_p^{*}$ , computes $R_i=s_{i}P-h_i{P}_{\mathrm{pub}}$ , sets $H_1(I{D}_i||R_i)=h_i$ , and sets $(s_i,R_i)$ as long-term private key of party $I{D}_i$ . Therefore, party $I{D}_i$ ’s long-term public key $P{K}_i=R_i+h_i{P}_{\mathrm{pub}}=s_{i}P$ .

3. For each party $I{D}_i$ , $\mathcal{S}$ passes $(I{D}_i,R_i)$ to $\mathcal{M}$ , and inserts the entry $(I{D}_i,R_i,h_i)$ to $H_1^{\mathrm{list}}$ .

Queries

$\mathcal{S}$ maintains three initially empty lists $H_1^{\mathrm{list}}$ , $H_2^{\mathrm{list}}$ , and $R^{\mathrm{list}}$ to handle the $H_1$ , $H_2$ , and SessionKeyReveal queries. $\mathcal{S}$ responds to the queries issued by $\mathcal{M}$ as follows. Note that $\mathcal{S}$ answers $H_1(I{D}_i,R_i)$ , $\mathrm{EstablishParty}(I{D}_i)$ , $\mathrm{SessionKeyReveal}(\underset{i,j}{\overset{s}{\Pi }})$ , and $\mathrm{Test}(\underset{i,j}{\overset{s}{\Pi }})$ as it does in S1.

1. $H_2(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,K_{\mathrm{ij}})$ . Originally, $\mathcal{S}$ maintains an empty list $H_2^{\mathrm{list}}$ in which each entry is $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,K_{\mathrm{ij}},h_2)$ .

2. Otherwise, $\mathcal{S}$ looks up the matching entry in $R^{\mathrm{list}}$ . If the entry exists, the challenger $\mathcal{S}$ sets $h_2=\mathrm{sk}$ , and stores the new entry $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,K_{\mathrm{ij}},h_2)$ to the list $H_2^{\mathrm{list}}$ . Otherwise, the challenger $\mathcal{S}$ chooses $h_2\in \{0,1{\}}^k$ at random and adds the entry $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,K_{\mathrm{ij}},h_2)$ to the list $H_2^{\mathrm{list}}$ .

$\mathrm{StaticKeyReveal}(I{D}_i)$ . $\mathcal{S}$ returns $(s_i,R_i)$ to $\mathcal{M}$ .

MasterPrivateKeyReveal. $\mathcal{S}$ returns s to $\mathcal{M}$ .

$\mathrm{EphemeralSecretReveal}(\underset{i,j}{\overset{s}{\Pi }})$ . If $\underset{i,j}{\overset{s}{\Pi }}=\underset{A,B}{\overset{S}{\Pi }}$ or $\underset{i,j}{\overset{s}{\Pi }}=\underset{B,A}{\overset{T}{\Pi }}$ , $\mathcal{S}$ aborts. Otherwise, $\mathcal{S}$ reveals the ephemeral private key to $\mathcal{M}$ .

$\mathrm{Send}(\underset{i,j}{\overset{s}{\Pi }},m)$ . At first, $\mathcal{S}$ maintains an empty list $R^{\mathrm{list}}$ whose each entry is $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,\mathrm{sk})$ .

If $\underset{i,j}{\overset{s}{\Pi }}=\underset{A,B}{\overset{S}{\Pi }}$ , the challenger $\mathcal{S}$ randomly chooses $U\in \mathbb{G}$ , and then returns $s_{A}X-h_{A}U$ and U to the adversary $\mathcal{M}$ .

If $\underset{i,j}{\overset{s}{\Pi }}=\underset{B,A}{\overset{T}{\Pi }}$ , $\mathcal{S}$ randomly chooses $V\in \mathbb{G}$ , and returns $s_{B}Y-h_{B}V$ and V to $\mathcal{M}$ . Then $\mathcal{S}$ looks up the matching entry in $H_2^{\mathrm{list}}$ . If the entry exists, the challenger $\mathcal{S}$ sets $\mathrm{sk}=h_2$ , and adds the new entry $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,\mathrm{sk})$ to the list $R^{\mathrm{list}}$ . Otherwise, the challenger $\mathcal{S}$ chooses $\mathrm{sk}\in \{0,1{\}}^k$ at random and adds the entry $(I{D}_i,I{D}_j,T_i^1,T_i^2,T_j^1,T_j^2,\mathrm{sk})$ to the list $H_2^{\mathrm{list}}$ .

Otherwise, the challenger $\mathcal{S}$ responds according to the protocol specification.

Analysis

If the adversary $\mathcal{M}$ successfully mounts the forging attack with non-negligible probability, $\mathcal{M}$ should issue a query to $H_2$ with the input $K_{\mathrm{AB}}=\mathrm{DLOG}(X)s_A(s_{B}Y-h_{B}V+h_{B}V)=\mathrm{DLOG}(X)s_A{s}_{B}Y$ . To solve the $\mathrm{GDH}(X,Y)$ problem, $\mathcal{S}$ verifies whether there is an $H_2$ query issued by $\mathcal{M}$ on the value $(I{D}_A,I{D}_B,T_A^1,T_A^2,T_B^1,T_B^2,K_{\mathrm{AB}})$ , such that $\mathrm{DDH}((T_A^1+h_A{T}_A^2),(T_B^1+h_B{T}_B^2),K_{\mathrm{AB}})=1$ . If there is such an $H_2$ query, $\mathcal{S}$ calculates $\mathrm{GDH}(X,Y)=\mathrm{DLOG}(X)Y=(s_A{s}_B{)}^{-1}{K}_{\mathrm{AB}}$ . $\mathcal{S}$ successfully solves the GDH problem with the following advantage

$${\mathrm{Adv}}_{\mathcal{S}}^{\mathrm{GDH}}\left(k\right)\ge \frac{{\mathrm{Adv}}_{\mathcal{M}}^{\Sigma }\left(k\right)}{6p{(k)}^{2}s\left(k\right)}$$

S4

$\mathcal{M}$ does not know $I{D}_A$ ’s long-term private key and $I{D}_B$ ’s ephemeral private key.

For S4, the simulation of $\mathcal{S}$ is similar to that in S1 (only $I{D}_A$ and $I{D}_B$ are exchanged). The details are omitted. $\mathcal{S}$ successfully solves the GDH problem with the advantage

$${\mathrm{Adv}}_{\mathcal{S}}^{\mathrm{GDH}}\left(k\right)\ge \frac{{\mathrm{Adv}}_{\mathcal{M}}^{\Sigma }\left(k\right)}{6p{(k)}^{2}s\left(k\right)}$$

S5

$\mathcal{M}$ does not know $I{D}_A$ ’s ephemeral private key and $I{D}_B$ ’s long-term private key, and the adversary $\mathcal{M}$ may alter $I{D}_B$ ’s public key material $R_B$ .

Initially, the challenger $\mathcal{S}$ randomly selects $X\in \mathbb{G}$ as the KGC’s master public key. Then, $\mathcal{S}$ sets all parties’ long-term keys as follows. $\mathcal{S}$ selects $h_i,s_i{\in }_R{\mathbb{Z}}_p^{*}$ , computes $R_i=s_{i}P-h_i{P}_{\mathrm{pub}}$ , sets $H_1(I{D}_i||R_i)=h_i$ , and sets $(s_i,R_i)$ as long-term private key of party $I{D}_i$ . Therefore, party $I{D}_i$ ’s long-term public key $P{K}_i=R_i+h_i{P}_{\mathrm{pub}}=s_{i}P$ . For each party $I{D}_i$ , $\mathcal{S}$ passes $(I{D}_i,R_i)$ to $\mathcal{M}$ , and inserts the entry $(I{D}_i,R_i,h_i)$ to $H_1^{\mathrm{list}}$ . Specifically, $\mathcal{S}$ randomly chooses $Y,U\in \mathbb{G}$ , and sets the ephemeral public keys of $I{D}_A$ to $s_{A}Y-h_{A}U$ and $U$ . Since $\mathcal{S}$ is aware of all parties’ long-term private keys, the answers to all queries are easy.

Assume that $\mathcal{M}$ neither queries $\mathrm{EphemeralSecret}\mathrm{Reveal}(\underset{A,B}{\overset{S}{\Pi }})$ nor $\mathrm{StaticKeyReveal}(I{D}_B)$ , and the simulation does not abort. Assume that the session $\underset{A,B}{\overset{S}{\Pi }}$ has the incoming message $(I{D}_B,R_{(B,\mathcal{M})},\mathrm{bP}{K}_B-b{h}_{B}X,\mathrm{bX})$ which can possibly be generated by $\mathcal{M}$ . Here the adversary $\mathcal{M}$ selects $b{\in }_R{\mathbb{Z}}_p^{*}$ , and may alter $I{D}_B$ ’s public key material $R_B$ . Suppose that $\mathcal{S}$ selects ${\overline{h}}_B{\in }_R{\mathbb{Z}}_p^{*}$ , and sets $H_1(I{D}_B||R_{(B,\mathcal{M})})={\overline{h}}_B$ . If the adversary $\mathcal{M}$ is successful in forging attack with non-negligible probability, $\mathcal{M}$ should make a query to $H_2$ with the input $K_{\mathrm{AB}}=\mathrm{DLOG}(Y)s_A(\mathrm{bP}{K}_B-b{h}_{B}X+H_1(I{D}_B||R_{(B,\mathcal{M}))}\mathrm{bX})=\mathrm{DLOG}(Y)s_A(\mathrm{bP}{K}_B-b{h}_{B}X+{\overline{h}}_B\mathrm{bX})$ . $\mathcal{S}$ verifies whether there is an $H_2$ query issued by $\mathcal{M}$ on the value $(I{D}_A,I{D}_B,T_A^1,T_A^2,T_B^1,T_B^2,K_{\mathrm{AB}})$ , such that $\mathrm{DDH}((T_A^1+h_A{T}_A^2),(T_B^1+h_B{T}_B^2),K_{\mathrm{AB}})=1$ .

According to the forking lemma, ⁵³ $\mathcal{S}$ replays $\mathcal{M}$ with the same input and tossing coins. During this run, $\mathcal{S}$ selects ${\overline{h}}_B^{\prime }{\in }_R{\mathbb{Z}}_p^{*}$ , and sets $H_1(I{D}_B||R_{(B,\mathcal{M})})={\overline{h}}_B^{\prime }$ , where ${\overline{h}}_B^{\prime }\ne {\overline{h}}_B$ . If the adversary $\mathcal{M}$ succeeds in forging attack with non-negligible probability, $\mathcal{M}$ should make a query to $H_2$ with the input ${\tilde{K}}_{\mathrm{AB}}=\mathrm{DLOG}(Y)s_A(\mathrm{bP}{K}_B-b{h}_{B}X+H_1(I{D}_B||R_{(B,\mathcal{M})})\mathrm{bX})=\mathrm{DLOG}(Y)s_A(\mathrm{bP}{K}_B-b{h}_{B}X+{\overline{h}}_B^{\prime }\mathrm{bX})$ . $\mathcal{S}$ verifies whether there is an $H_2$ query issued by $\mathcal{M}$ on the value $(I{D}_A,I{D}_B,T_A^1,T_A^2,T_B^1,T_B^2,{\tilde{K}}_{\mathrm{AB}})$ , such that $\mathrm{DDH}((T_A^1+h_A{T}_A^2),(T_B^1+h_B{T}_B^2),{\tilde{K}}_{\mathrm{AB}})=1$ .

To solve the $\mathrm{GDH}(X,Y)$ problem, $\mathcal{S}$ computes $K_{AB}-{\tilde{K}}_{AB}=DLOG(Y)s_A(bP{K}_B-b{h}_{B}X+{\overline{h}}_{B}bX)-DLOG(Y)s_A(bP{K}_B-b{h}_{B}X+{\overline{h}}_B^{\prime }bX)=DLOG(Y)s_A({\overline{h}}_B-{\overline{h}}_B^{\prime })bX$ , and then $\mathcal{S}$ computes $\mathrm{GDH}(X,Y)=\mathrm{DLOG}(Y)X=(b{s}_A({\overline{h}}_B-{\overline{h}}_B^{\prime }){)}^{-1}(K_{\mathrm{AB}}-{\tilde{K}}_{\mathrm{AB}})$ . Suppose that $\lambda$ is the utilization factor of the forking lemma in S5. Consequently, $\mathcal{S}$ successfully solves the GDH problem with the following advantage

$${\mathrm{Adv}}_{\mathcal{S}}^{\mathrm{GDH}}\left(k\right)\ge \frac{\lambda {\mathrm{Adv}}_{\mathcal{M}}^{\Sigma }\left(k\right)}{6p{(k)}^{2}s\left(k\right)}$$

S6

$\mathcal{M}$ does not know the long-term private keys of $I{D}_A$ and $I{D}_B$ , and the adversary $\mathcal{M}$ may alter $I{D}_B$ ’s public key material $R_B$ .

Initially, the challenger $\mathcal{S}$ randomly selects $X\in \mathbb{G}$ as the KGC’s master public key. Then $\mathcal{S}$ sets all parties’ long-term keys as follows. For any party $I{D}_i(i\ne A)$ , $\mathcal{S}$ selects $h_i,s_i{\in }_R{\mathbb{Z}}_p^{*}$ , computes $R_i=s_{i}P-h_i{P}_{\mathrm{pub}}$ , sets $H_1(I{D}_i||R_i)=h_i$ , and sets $(s_i,R_i)$ as long-term private key of party $I{D}_i$ . Therefore, party $I{D}_i$ ’s long-term public key $P{K}_i=R_i+h_i{P}_{\mathrm{pub}}=s_{i}P$ . For the party $I{D}_A$ , $\mathcal{S}$ selects $h_A{\in }_R{\mathbb{Z}}_p^{*}$ as $H_1(I{D}_A||R_A)$ , computes $R_A=Y-h_A{P}_{\mathrm{pub}}$ , and sets $(\perp ,R_A)$ as party $I{D}_A$ ’s long-term private key. Therefore, party $I{D}_A$ ’s long-term public key $P{K}_A=R_A+h_A{P}_{\mathrm{pub}}=Y$ . For each party $I{D}_i$ , $\mathcal{S}$ passes $(I{D}_i,R_i)$ to $\mathcal{M}$ , and inserts the entry $(I{D}_i,R_i,h_i)$ to $H_1^{\mathrm{list}}$ . Specifically, $\mathcal{S}$ randomly chooses $U\in \mathbb{G}$ , chooses $a{\in }_R{\mathbb{Z}}_p^{*}$ , and sets the ephemeral public keys of $I{D}_A$ to $\mathrm{aY}-h_{A}U$ and $U$ .

Assume that $\mathcal{M}$ neither queries $\mathrm{StaticKey}\mathrm{Reveal}(I{D}_A)$ nor $\mathrm{StaticKeyReveal}(I{D}_B)$ , and the simulation does not abort. Assume that the session $\underset{A,B}{\overset{S}{\Pi }}$ has the incoming message $(I{D}_B,R_{(B,\mathcal{M})},\mathrm{bP}{K}_B-b{h}_{B}X,\mathrm{bX})$ which can possibly be generated by $\mathcal{M}$ . Here the adversary $\mathcal{M}$ selects $b{\in }_R{\mathbb{Z}}_p^{*}$ , and may alter $I{D}_B$ ’s public key material $R_B$ . Suppose that $\mathcal{S}$ selects ${\overline{h}}_B{\in }_R{\mathbb{Z}}_p^{*}$ and sets $H_1(I{D}_B||R_{(B,\mathcal{M})})={\overline{h}}_B$ . If the success probability of the adversary in forging attack is non-negligible, it must have queried $H_2$ with inputs of the form $K_{\mathrm{AB}}=\mathrm{aDLOG}(Y)(\mathrm{bP}{K}_B-b{h}_{B}X+H_1(I{D}_B||R_{(B,\mathcal{M}))}\mathrm{bX}))=\mathrm{aDLOG}(Y)(\mathrm{bP}{K}_B-b{h}_{B}X+{\overline{h}}_B\mathrm{bX})$ . $\mathcal{S}$ verifies whether there is an $H_2$ query issued by $\mathcal{M}$ on the value $(I{D}_A,I{D}_B,T_A^1,T_A^2,T_B^1,T_B^2,K_{\mathrm{AB}})$ , such that $\mathrm{DDH}((T_A^1+h_A{T}_A^2),(T_B^1+h_B{T}_B^2),K_{\mathrm{AB}})=1$ .

According to the forking lemma, $\mathcal{S}$ replays $\mathcal{M}$ with the same input and tossing coins. In the course of this run, $\mathcal{S}$ selects ${\overline{h}}_B^{\prime }{\in }_R{\mathbb{Z}}_p^{*}$ and sets $H_1(I{D}_B||R_{(B,\mathcal{M})})$ to ${\overline{h}}_B^{\prime }$ , where ${\overline{h}}_B^{\prime }\ne {\overline{h}}_B$ . If the success probability of the adversary in forging attack is non-negligible, it should make a query to $H_2$ with the input ${\tilde{K}}_{\mathrm{AB}}=\mathrm{aDLOG}(Y)(\mathrm{bP}{K}_B-b{h}_{B}X+H_1(I{D}_B||R_{(B,\mathcal{M})})\mathrm{bX})=\mathrm{aDLOG}(Y)(\mathrm{bP}{K}_B-b{h}_{B}X+{\overline{h}}_B^{\prime }\mathrm{bX})$ . $\mathcal{S}$ checks if there is an $H_2$ query issued by $\mathcal{M}$ on the value $(I{D}_A,I{D}_B,T_A^1,T_A^2,T_B^1,T_B^2,{\tilde{K}}_{\mathrm{AB}})$ , such that $\mathrm{DDH}((T_A^1+h_A{T}_A^2),(T_B^1+h_B{T}_B^2),{\tilde{K}}_{\mathrm{AB}})=1$ .

To solve the $\mathrm{GDH}(X,Y)$ problem, $\mathcal{S}$ computes $K_{\mathrm{AB}}-{\tilde{K}}_{\mathrm{AB}}=\mathrm{aDLOG}(Y)(\mathrm{bP}{K}_B-b{h}_{B}X+{\overline{h}}_B\mathrm{bX})-\mathrm{aDLOG}(Y)(\mathrm{bP}{K}_B-b{h}_{B}X+{\overline{h}}_B^{\prime }\mathrm{bX})=\mathrm{aDLOG}(Y)({\overline{h}}_B-{\overline{h}}_B^{\prime })\mathrm{bX}$ , and then $\mathcal{S}$ computes $\mathrm{GDH}(X,Y)=\mathrm{DLOG}(Y)X=(\mathrm{ab}({\overline{h}}_B-{\overline{h}}_B^{\prime }){)}^{-1}(K_{\mathrm{AB}}-{\tilde{K}}_{\mathrm{AB}})$ . Suppose that $\theta$ is the utilization factor of the forking lemma in S6. Therefore, $\mathcal{S}$ successfully solves the GDH problem with the following advantage

$${\mathrm{Adv}}_{\mathcal{S}}^{\mathrm{GDH}}\left(k\right)\ge \frac{\theta {\mathrm{Adv}}_{\mathcal{M}}^{\Sigma }\left(k\right)}{6p{(k)}^{2}s\left(k\right)}$$

For the six strategies, since ${\mathrm{Adv}}_{\mathcal{M}}^{\Sigma }(k)$ is assumed to be non-negligible, ${\mathrm{Adv}}_{\mathcal{S}}^{\mathrm{GDH}}(k)$ is also non-negligible. This is in contradiction to the GDH assumption.

The proof of Theorem 1 is complete.□

Security attributes

Our protocol $\Sigma$ catches all essential security attributes.

1. K-SKS. The eCK model can cover the K-SKS property because it supports the SessionKeyReveal query. According to the fresh definition, the adversary $\mathcal{M}$ may reveal the session keys of other sessions than the test session and its matching session (if its matching session exists). The probability that $\mathcal{M}$ differentiates between the test session key and a random value is negligible. Therefore, the test session key is not disclosed even if $\mathcal{M}$ has known any other session keys.

2. FS. Our protocol captures the wPFS and MFS properties. In section “Security proof,” our protocol is proven to be secure in the eCK model. Therefore, the adversary cannot know the long-term and ephemeral secrets of one party, which implies wPFS. Moreover, the proof of S3 guarantees MFS.

3. BIR. When the long-term secret of party A is not revealed to an adversary $\mathcal{M}$ , $\mathcal{M}$ does not know the key of the session of party A with any other party because it cannot calculate the correct input to $H_2$ . Therefore, the adversary cannot impersonate party A.

4. KCIR. The property is guaranteed by the proofs of S1, S3, S4, and S5. Even when $\mathcal{M}$ learns the long-term secret of party A and modifies the message sent to party A, it cannot calculate the key of the session of party A with any other party with no knowledge of party A’s ephemeral secret. Therefore, $\mathcal{M}$ cannot masquerade as any other party to party A. That is to say, the proposed protocol can catch KCIR.

5. UKSR. Unknown key share (UKS) attack should not be launched successfully in ID-based AKA protocols because the involved parties’ identities are the input of the key derivation function. In addition, a party’s public key is derived from its ID, which also resists UKS attack.

6. NKC. Because two sessions that are not matched do not have the same input of the key derivation function $H_2$ , the session key cannot be forced to a predetermined value by one involved party or an outside adversary. Moreover, from the security proof, we can know that the adversary $\mathcal{M}$ cannot differentiate between the test session key and a random value. Thus, our protocol can prevent key control attack.

7. ESRR. The property is guaranteed by the proofs of all strategies except for S3. The proofs for S1, S4, and S5 guarantee the proposed protocol is secure when ephemeral secrets are revealed partially. The proofs for S2 and S6 guarantee the proposed protocol is secure when ephemeral secrets are disclosed entirely.

Comparisons with the existing protocols

We compare our protocol with other existing ID-based 2PAKA protocols: the most efficient ID-based 2PAKA protocol using pairings (McCullagh-Barreto (MB)-I protocol ²⁰ ), a provably secure ID-based one-round 2PAKA protocol with pairings in the eCK model that catches all essential security attributes (Huang et al.’s ²⁸ protocol), and four latest provably secure pairing-free ID-based one-round 2PAKA protocols that catch all essential security attributes (Sun et al.’s ⁴⁶ protocol, Bala et al.’s ⁴⁷ protocol, Ni et al.’s ⁴⁸ protocols; and Islam and Biswas’s ⁴⁹ protocol).

Table 1 shows the comparison results in term of security, in which we only list security model, assumption, and the properties of KCIR and ESRR because these compared protocols catch other basic desirable security properties including K-SKS, wPFS, BIR, UKSR, and NKC. “√” and “×” mean that the security property is captured and is not captured by the protocol, respectively. “ ${\mathrm{eCK}}^{*}$ ” is used to denote the eCK model that does not take active adversaries into account. From Table 1, it is clear that Huang and Cao’s ²⁸ protocol, Sun et al.’s ⁴⁶ protocol, and Bala et al.’s ⁴⁷ protocol do not consider active adversaries although they are given the security proofs in strong model such as eCK model. In addition, the security analysis based on BAN logic model does not make certain that Islam and Biswas’s ⁴⁹ protocol is secure. ⁵¹ Therefore, among these compared ID-based 2PAKA protocols, only Ni-I, ⁴⁸ Ni-II, ⁴⁸ and our protocol are proven secure under the passive and active adversaries in the eCK model. It can be concluded that Ni et al.’s ⁴⁸ protocols and our protocol achieve higher security than the five protocols.^{20,28,46,47,49}

Table 1.

Security comparison of ID-based 2PAKA protocols.

Protocol	Security model	Assumption	KCIR	ESRR
MB-I 20	mBR	BIDH	×	×
Huang and Cao 28	${\mathrm{eCK}}^{*}$	CBDH	√	√
Sun et al. 46	${\mathrm{eCK}}^{*}$	GDH	√	√
Bala et al. 47	${\mathrm{eCK}}^{*}$	GDH	√	√
Ni-I 48	eCK	CDH	√	√
Ni-II 48	eCK	GDH	√	√
Islam and Biswas 49	BAN	GDH	√	√
Our protocol	eCK	GDH	√	√

ID: identity; 2PAKA: two-party authenticated key agreement; KCIR: key compromise impersonation resistance; ESRR: ephemeral secrets reveal resistance; MB: McCullagh-Barreto; mBR: modified Bellare-Rogaway; BIDH: bilinear inverse Diffie-Hellman; eCK: extended Canetti-Krawczyk; CBDH: computational bilinear Diffie-Hellman; GDH: Gap Diffie-Hellman; CDH: computational Diffie–Hellman; BAN: Burrows-Abadi-Needham.

Performance analyses

In this section, the efficiency of our protocol is compared with the existing protocols in terms of message size, computational cost, and running time. We omit the communication round because these compared protocols all have one-round communication. We implement the cryptographic operations by using MIRACL, ⁵⁴ a standard cryptographic library. Since a vehicle has unlimited computation ability and power in VANETs, ⁵⁵ the hardware platform that we select is an Intel Core 2 E8400 processor with 2 GB memory and a Windows XP operation system. For the two protocols using pairings,^20,28 to provide the 80-bit security level, we choose the Tate pairing on the elliptic curve $y^2=x^3+x$ over $\mathbb{F}$ _p with embedding degree 2, where q is a 160-bit prime $q=2^{159}+2^{17}+1$ and p is a 512-bit prime meeting the condition of $p+1=12\mathrm{qr}$ . As for the pairing-free protocols,^46–49 to reach the same level of security, we employ the group on elliptic curve cryptography (ECC) secp160r1. The cryptographic operating times are shown in Table 2 where Exponent. in mult.group and poi.mult. stands for exponentiation in a multiplicative group and point multiplication, respectively.

Table 2.

Cryptographic Operating Time (in milliseconds).

Pairing	Exponent. in mult.group	Pairing-based poi.mult.	ECC-based poi.mult.
18.32	5.30	5.54	2.01

Table 3 lists the comparison results in terms of message size, computational cost, and running time. Assume that one user ID is 2 bytes long. Our protocol’s exchanged message is one ID and three points, and thus the message size is $(2\times 8+160\times 3)/8=62\mathrm{bytes}$ . In Bala et al.’s ⁴⁷ protocol, the exchanged message comprises one ID and two points, and thus the message size is $(2\times 8+160\times 2)/8=42\mathrm{bytes}$ . Similarly, the message sizes of other compared protocols can be given.

Table 3.

Performance comparison of ID-based 2PAKA protocols (using pre-computation).

Protocol	Message size	Computational cost	Running time
MB-I 20	64 bytes	$1P+1E+1\mathrm{PM}$	$24.276\mathrm{ms}$
Huang and Cao 28	66 bytes	$2P+3\mathrm{PM}$	$42.852\mathrm{ms}$
Sun et al. 46	42 bytes	$6\mathrm{EM}(5\mathrm{EM})$	$10.594\mathrm{ms}$
Bala et al. 47	42 bytes	$4\mathrm{EM}(3\mathrm{EM})$	$6.574\mathrm{ms}$
Ni-I 48	62 bytes	$7\mathrm{EM}(6\mathrm{EM})$	$12.716\mathrm{ms}$
Ni-II 48	62 bytes	$5\mathrm{EM}(4\mathrm{EM})$	$8.696\mathrm{ms}$
Islam and Biswas 49	62 bytes	$5\mathrm{EM}(4\mathrm{EM})$	$8.696\mathrm{ms}$
Our protocol	62 bytes	$4\mathrm{EM}(2\mathrm{EM})$	$4.676\mathrm{ms}$

ID: identity; 2PAKA: two-party authenticated key agreement; MB: McCullagh and Barreto.

In the comparison of the computational cost, for simplicity, we only consider the expensive operations including pairing operation, exponentiation in a multiplicative group, pairing-based point multiplication, and ECC-based point multiplication, which are denoted as P, E, PM, and EM, respectively. The values in parentheses are the computational costs of these protocols when pre-computation is considered.

The running time of an AKA protocol is approximately equal to the computation time of one party and the transmission times of two exchanged messages in wireless links. In vehicular environments, the time spent on one message transmission is the sum of transmission times of the physical layer convergence procedure (PLCP) preamble (i.e. $0.032\mathrm{ms}$ ), the SIGNAL field (i.e. $0.008\mathrm{ms}$ ), and DATA field. The DATA field consists of the 16-bit SERVICE field, the physical service data unit (PSDU) (i.e. the medium-access control (MAC) frame), the 6-bit TAIL field, and the PAD field. The length of PAD field satisfies the condition that the number of bits in the DATA field should be a multiple of the number of data bits per orthogonal frequency division multiplexing (OFDM) symbol. According to 802.11 ⁵⁶ and dedicated short-range communications (DSRC) standards, ⁵⁷ the data rate varies from 3 to 27 Mbps. In addition, the network and transport layers, Wave Short Message (WSM) header is at least 5 bytes in length, and subnetwork access protocol (SNAP) header and the logical link control (LLC) sublayer header are 5 and 3 bytes in length, respectively. The MAC sublayer header is 28 bytes in length. In order to better reflect the performation advantages of our protocol, the minimum data rate (i.e. 3 Mbps) and the corresponding number of data bits per OFDM symbol (i.e. 24 data bits) are chosen to compute the running time of compared protocols. Accordingly, the running time of our protocol can be computed as follows: 2EM + 2 (the transmission time of PLCP preamble + the transmission time of SIGNAL + (PSDU + TAIL + PAD) / (data rate)) = 4.676 ms. Similiarly, the running times of other compared protocols are listed in Table 3.

As listed in Table 3, it is clear that the ID-based pairing-free 2PAKA protocols achieve much better performance than the ID-based 2PAKA protocols using pairings. In addition, it is found that our protocol is superior to Ni-I ⁴⁸ protocol and Ni-II ⁴⁸ protocol in terms of computational cost and running time while having the same message size as them. Specifically, the running time of our protocol is 36.8% of Ni-I protocol, 53.8% of Ni-II protocol when pre-computation is considered. From Table 3, we can observe that our protocol is computationally more efficient than Bala et al.’s ⁴⁷ protocol considering pre-computation with the disadvantage of slightly increased message size. The reason is that, (1) the intended partner vehicles communicating with vehicle A are not the same in different sessions of vehicle A; (2) in our protocol, $a{R}_A$ and $a{P}_{\mathrm{pub}}$ are suitable for pre-computation as these two values have nothing to do with other parties and party A only needs to store two points; (3) in Bala’s protocol, vehicle A is not suitable to pre-compute and store $h_B{P}_{\mathrm{pub}}$ for large numbers of unpredictable vehicles due to the rapid topology changes nature of vehicular networks. Therefore, Bala et al.’s ⁴⁷ protocol and our protocol require three and two ECC-based point multiplication operations, respectively, when pre-computation is carried out. Moreover, the security proof of Bala et al.’s ⁴⁷ protocol does not take active adversaries into account. Although the message size of our protocol is one point more than that of Bala’s protocol, our protocol has less running time than Bala’s protocol. Namely, the running time of our protocol is 77.1% of that of Bala’s protocol. Figure 2 illustrates the comparison result of Bala et al.’s ⁴⁷ protocol, Ni-I, ⁴⁸ Ni-II, ⁴⁸ and our protocol in terms of running time when pre-computation is carried out.

Figure 2.

Comparison result of the running time (with pre-computation).

To summarize, our protocol has better performance than previous ID-based protocols while achieving higher or the same security level. It is concluded that our protocol is more suitable to real-time application environments with highly dynamic topology such as VANETs than the existing ID-based 2PAKA protocols.

Discussion

The proposed 2PAKA protocol enables two authentic vehicles to agree on a shared session key, which can be used for secure communication. For example, the secure communication protocol for VANETs ⁵⁸ achieves the multi-level conditional privacy preservation authentication and integrity of transmitted messages based on ring signature. However, the signature is generated by using the private key of sender and L collected public keys, and the transmitted message consists of payload, timestamp, signature, and L public keys. Therefore, the message size is a little long and the signature verification requires 2 × L + 3 time-consuming pairing operations. The secure communication protocol for VANETs ² offers the confidentiality, conditional privacy preservation authentication, and integrity of transmitted messages based on group signcryption. The session key used for signcryption is derived from the group secret key, which is generated by the group secret key agreement. However, the group secret key and group public key need to be updated on all unrevoked vehicles each time a member is revoked or quits the group. In addition, the group-based communication protocols for VANETs^2,58 are only suitable for the application scenarios with low mobility and little topology changing, such as traffic jam, urban road, and parking lot. Therefore, the article focuses on 2PAKA for VANETs.

Conclusions and future works

This article presents a provably secure and efficient one-round ID-based 2PAKA protocol without pairings for VANETs. The proposed protocol is given the formal proof under the passive and active adversaries in the eCK model. We also analyze that the proposed protocol can capture all essential security properties including K-SKS, wPFS, MFS, BIR, KCIR, UKSR, NKC, ESRR, and so on. The proposed protocol outperforms the existing ID-based 2PAKA protocols in terms of computational cost and running time while providing higher or the same level of security. In particular, if pre-computation is considered, our protocol reduces the running time to 77.1% of Bala’s protocol, 36.8% of Ni-I protocol, and 53.8% of Ni-II protocol while providing stronger or the same security level. As a result, our protocol is more applicable than other existing ID-based 2PAKA protocols for real-time application environments with quickly changing topology such as VANETs. Our future work is to present a provably secure and efficient certificateless 2PAKA protocol without pairings.