# Anonymous Authentication and Key Agreement Scheme Combining the Group Key for Vehicular Ad Hoc Networks

Authors: Mei Sun; Yuyan Guo; Dongbing Zhang; MingMing Jiang
Journal: Complexity
 (2021)

---

## Abstract

Vehicular ad hoc network (VANET) is a multihop mobile wireless communication network that can realize many vehicle-related applications through multitop communication. In the open wireless communication environment, security and privacy protection are important contents of VANET research. The most basic method of VANET privacy protection is anonymous authentication. Even through, there are many existing schemes to provide anonymous authentication for VANETs. Many existing schemes suffer from high computational cost by using bilinear pairing operation or need the assistance of the trust authorities (TAs) during the authentication process or rely on an ideal tamper-proof device (TPD), which requires very strong security assumption. In this study, an anonymous authentication and key negotiation scheme by using private key and group key is proposed, which is based on pseudonym using the nonsingular elliptic curve. In this scheme, there is no third party trust center to participate in the authentication, there is no need to query the database, and there is no need of the local database to save the identity information of many vehicles, which reduce the storage space and the authentication time compared with other schemes. The proposed scheme only needs realistic TPDs. In the proposed scheme, TPDs do not need to preinstall the system key as many other schemes do; hence, the failure of a single TPD does not affect the security of the entire system. The security of the scheme is proved under the random oracle model. Compared with the related schemes using bilinear pairings, the computational cost and communication cost of the proposed scheme are reduced by 82% and 50%, respectively.


---

## Body

## 1. Introduction

With the development of network technology, there are many forms of network and new technologies [1, 2]. Vehicular ad hoc network (VANET) is a highly mobile self-organizing wireless communication network. By using VANET, vehicles in front can in a timely manner report the road condition information to the rear vehicles; this can improve the travel efficiency and reduce road congestion and traffic accidents. VANET plays a significant role in traffic optimization and safety [3]. Since VANET mainly adopts a wireless communication mode, messages are vulnerable to various attacks, such as counterfeiting, interception, tampering, tracking, and other attacks [4, 5]. These attacks seriously threaten the safety of vehicles and the privacy of users. Therefore, security authentication and privacy protection are important research directions of VANET. VANET generally has the following main components: road side unit (RSU), trust agency (TA), and on-board unit (OBU) [6]. OBU is installed in the vehicle and can realize the communication between the vehicle and RSU or other vehicles. The communication between OBU and RSU adopts dedicated short range communication (DSRC) [7]. The communication with vehicles requires authenticating one another and negotiating the communication key to prevent attacks such as tracking, privacy exposure, and message counterfeiting. Authentication and key agreement in VANETs are anonymous. Hence, even if an attacker intercepts the message, the specific source of the message cannot be determined. Additionally, the authority of VANET can identify every message sent by vehicles, and this can prevent vehicles from sending false messages maliciously.


### 1.1. Related Works

In recent years, some authentication protocols based on public key infrastructure (PKI) [8–10] have been proposed. In these works, some anonymous authentication and key agreement schemes are proposed, in which a large number of certificates are assigned to vehicles. However, these schemes require vehicles to be equipped with many anonymous certificates in advance; this leads to many problems such as certificate storage and certificate management. Lu et al. [11] proposed a key agreement and authentication scheme for generating a short-term key and certificate between the vehicle and RSU. However, the communication efficiency of the scheme is low due to the frequent interaction between the vehicle and RSU for changing the authenticated group. Rajput et al. [12] proposed an anonymous authentication scheme with hierarchical privacy protection to solve the defects based on PKI. This protocol does not need to manage the certificate revocation list (CRL), and each vehicle uses two pseudonyms to complete anonymous authentication, but once the pseudonym expires, the vehicle needs to acquire the pseudonym from TA or RSU again; this increased the number of communications. Wang [13] proposed a local identity-based anonymous authentication protocol for VANET (LIAP). In this method, each vehicle and RSU are assigned a unique long-term certificate from the certification authority (CA) in the registration phase. The vehicle and RSU complete mutual authentication through certificates. After successful authentication, RSU distributes a local-master key to the vehicle. The vehicle randomly generates a pseudonym to communicate with the RSU through the local-master key. The use of the local-master key improves the communication efficiency and system security. But this scheme needs to manage CRL.The storage and management of certificates restrict the development of authentication schemes based on PKI. To overcome the problems caused by authentication certificates, some identity-based public key cryptosystems are introduced into authentication of VANET [4, 14–19]. In 1984, Miller first proposed an identity cryptosystem [14]. In this cryptosystem, the user’s public key is calculated by the user’s identity, and the user’s private key is generated by the authentication center through the system key according to the user’s identity. In 2008, Zhang et al. [15] proposed an authentication protocol for VANET using the identity of the vehicle user, solving the certificate storage and management problem and supporting batch authentication. In 2011, Huang [16] proposed an anonymous batch authenticated and key agreement scheme based on identity authentication for VANET. Shim et al. [17] noted that the scheme [15] was vulnerable to replay attack and did not achieve the nonrepudiation of signature and proposed a vehicle-to-infrastructure (V2I) authentication scheme. However, the scheme is vulnerable to tampering attacks [18] and cannot satisfy its claimed chosen message attack resistance [17]. Wang et al. [20] mentioned that Huang et al. [16] could not resist a collusion attack, and therefore, they proposed an improved scheme. And, in [20], it is indicated that the scheme [18] cannot resist replay attacks and cannot track the real identity of the message sender. In 2016, Azees and Vijayakumar [21] proposed a novel key distribution scheme for secure group communication using Lagrange polynomials. The limitation of the scheme is that it only provides one-way authentication from vehicle to TA. Then, Vijayakumar et al. [22] proposed a privacy-preserving anonymous mutual and batch authentication scheme for vehicle-to-vehicle. This scheme implements the authentication of message source and message integrity and has the mechanism of tracking and revoking vehicles. In 2017, Azees et al. [23] proposed an anonymous authentication scheme to avoid malicious vehicles into the VANET based on bilinear pairing. Each user computes multiple temporary short time certificates to realize anonymous authentication in the scheme. The scheme has high computing performance and security. However, the dummy identity (DIUui) in each certificate is the same, and the scheme does not consider the unlinkability of different sessions. In 2018, Pournaghi et al. [24]. proposed an anonymous authentication and key agreement scheme combining TPD and RSU. The scheme saves the system master key in the TPD of RSU instead of the TPD of each vehicle, which improves the security and authentication efficiency of the system. In 2019, Ikram et al. [25] proposed a conditional privacy-preserving authentication scheme for V2I. This scheme uses general one-way hash functions instead of map-to-point hash functions to achieve high efficiency.The identity-based authentication schemes for VANET address the problems presented by the schemes based on PKI. The existing schemes [21–25] are novel in design and have good security. However, the bilinear pairing operations of elliptic curve are used, and the computational efficiency of bilinear pairing operation is low. The works [26–28] based on pseudonym on elliptic curve, which do not use bilinear pairing operation and have achieved high computational efficiency. However, TA is required to participate in authentication, this increases communication times and communication burden. He et al. [29] proposed a privacy protection authentication scheme based on identity. This scheme also uses elliptic curve instead of bilinear pairing operations and achieves satisfactory performance in both computation and communication. However, the scheme is based on ideal TPD, and the master key is stored on the TPD of each vehicle. Islam et al. [30] proposed a conditional privacy-preserving authentication scheme based on hash function. And the scheme offers group-key generation, user leaving, user join, and password change facilities. The scheme does not need bilinear pairing mapping or elliptic curve operation and is lightweight in terms computation and communication. However, TA is required to participate in each authentication between the vehicle and RSU. Wu et al. [6] proposed an effective location-based conditional secret authentication scheme. The scheme does not require bilinear pairing operations or TPDs. However, when RSU is certified by vehicle, TA needs to query the database and return the results. Cui et al. [31] proposed a scheme without relying on any special hardware such as TPD. The scheme is based on elliptic discrete logarithm and has high computational performance. The cuckoo filter and binary tree search method are used to achieve a higher success rate in batch authentication. However, TA is required to generate communication key for the vehicle and RSU. Zhong et al. [32] proposed an authentication and key agreement scheme based on hash function and registration list. And the scheme does not require the strong security assumptions of TPD. Xiong Li et al. [33] proposed a lightweight authentication scheme for VANETs with only hash functions and exclusive-OR operations. Compared with previous schemes, the computational cost of the schemes [32, 33] has been greatly improved. However, the schemes also need TA to participate in the authentication. In recent years, there are some authentication schemes using group key, which can reduce the authentication burden of TA. The works [34, 35] introduce group key management schemes based on Chinese remainder theorem, which reduces computation complexity of the key server. In 2019, Jing Zhang et al. [36] proposed a message authentication scheme based on the group key using Chinese remainder theorem. The TPD of the vehicle only save the real identity and the group key. So the proposed scheme only requires realistic TPDs and ensures higher security for the entire system. In 2020, Wei et al. [37] proposed tow privacy-preserving multimodal implicit authentication protocols for Internet of connected vehicles. The proposed protocols use the password and vehicle owner’s behavior features as the authentication factors skillfully and do not reveal any information about vehicle owner’s behavior. The protocols have advantages in computational cost and accuracy. However, the protocols do not consider the unlinkability of sessions. Vinoth et al. [38] proposed a multifactor authenticated key agreement scheme for industrial Internet of things (IoT). The scheme implements authentication and key agreement between the user and multiple sensing devices at the same time. The scheme only used hash function, bit-wise XOR operation, and symmetric cryptography. It has less communication cost and computational cost compared with other correlative schemes. However, the scheme does not consider internal attack.


### 1.2. Our Contributions

In this study, an anonymous authentication and key agreement scheme based on elliptic curve for VANET is proposed. Each vehicle is equipped with a TPD. The TPD saves the private key of the vehicle and the group key for multivehicle communication. The vehicle can authenticate with RSU anonymously by combining a private key with a group key. After successful authentication, the session key can be negotiated for both parties. The scheme can also implement message signature and anonymous verification. In this scheme, the TPD only saves the private key of the vehicle and the group key instead of the system key. The attack on the TPD will not affect other nodes in VANET. So, we only need realistic TPD instead of ideal TPD. There is no need for the third party to participate in the authentication and key agreement between vehicle and RSU compared with the works [6, 30–33], and there is no need to query the database in the scheme. In addition, the use of group key in this scheme can help RSU resist certain denial of service (DoS) attacks.The main contributions of this study are summarized as follows.(1)
In order to optimize the computational cost and key management, we present an efficient anonymous authentication and key agreement scheme for RSUs and vehicles using the private key of the vehicle and the group key(2)
In order to reduce the communication time and storage space, we implement independent authentication and key agreement between vehicle and RSU, and RSU does not need to save vehicle information or query database.(3)
In this scheme, we also implement anonymous signature and verification of messages(4)
In this scheme, we use realistic TPDs instead of ideal TPDs, which is more suitable for VANET


### 1.3. Organization of This Article

The rest of the study is structured as follows: Section2 describes the preliminaries of the proposed scheme, Section 3 gives the working of the proposed scheme, Sections 4 and 5 present a security analysis and a performance analysis, respectively. Our study is concluded in Section 6.


## 1.1. Related Works

In recent years, some authentication protocols based on public key infrastructure (PKI) [8–10] have been proposed. In these works, some anonymous authentication and key agreement schemes are proposed, in which a large number of certificates are assigned to vehicles. However, these schemes require vehicles to be equipped with many anonymous certificates in advance; this leads to many problems such as certificate storage and certificate management. Lu et al. [11] proposed a key agreement and authentication scheme for generating a short-term key and certificate between the vehicle and RSU. However, the communication efficiency of the scheme is low due to the frequent interaction between the vehicle and RSU for changing the authenticated group. Rajput et al. [12] proposed an anonymous authentication scheme with hierarchical privacy protection to solve the defects based on PKI. This protocol does not need to manage the certificate revocation list (CRL), and each vehicle uses two pseudonyms to complete anonymous authentication, but once the pseudonym expires, the vehicle needs to acquire the pseudonym from TA or RSU again; this increased the number of communications. Wang [13] proposed a local identity-based anonymous authentication protocol for VANET (LIAP). In this method, each vehicle and RSU are assigned a unique long-term certificate from the certification authority (CA) in the registration phase. The vehicle and RSU complete mutual authentication through certificates. After successful authentication, RSU distributes a local-master key to the vehicle. The vehicle randomly generates a pseudonym to communicate with the RSU through the local-master key. The use of the local-master key improves the communication efficiency and system security. But this scheme needs to manage CRL.The storage and management of certificates restrict the development of authentication schemes based on PKI. To overcome the problems caused by authentication certificates, some identity-based public key cryptosystems are introduced into authentication of VANET [4, 14–19]. In 1984, Miller first proposed an identity cryptosystem [14]. In this cryptosystem, the user’s public key is calculated by the user’s identity, and the user’s private key is generated by the authentication center through the system key according to the user’s identity. In 2008, Zhang et al. [15] proposed an authentication protocol for VANET using the identity of the vehicle user, solving the certificate storage and management problem and supporting batch authentication. In 2011, Huang [16] proposed an anonymous batch authenticated and key agreement scheme based on identity authentication for VANET. Shim et al. [17] noted that the scheme [15] was vulnerable to replay attack and did not achieve the nonrepudiation of signature and proposed a vehicle-to-infrastructure (V2I) authentication scheme. However, the scheme is vulnerable to tampering attacks [18] and cannot satisfy its claimed chosen message attack resistance [17]. Wang et al. [20] mentioned that Huang et al. [16] could not resist a collusion attack, and therefore, they proposed an improved scheme. And, in [20], it is indicated that the scheme [18] cannot resist replay attacks and cannot track the real identity of the message sender. In 2016, Azees and Vijayakumar [21] proposed a novel key distribution scheme for secure group communication using Lagrange polynomials. The limitation of the scheme is that it only provides one-way authentication from vehicle to TA. Then, Vijayakumar et al. [22] proposed a privacy-preserving anonymous mutual and batch authentication scheme for vehicle-to-vehicle. This scheme implements the authentication of message source and message integrity and has the mechanism of tracking and revoking vehicles. In 2017, Azees et al. [23] proposed an anonymous authentication scheme to avoid malicious vehicles into the VANET based on bilinear pairing. Each user computes multiple temporary short time certificates to realize anonymous authentication in the scheme. The scheme has high computing performance and security. However, the dummy identity (DIUui) in each certificate is the same, and the scheme does not consider the unlinkability of different sessions. In 2018, Pournaghi et al. [24]. proposed an anonymous authentication and key agreement scheme combining TPD and RSU. The scheme saves the system master key in the TPD of RSU instead of the TPD of each vehicle, which improves the security and authentication efficiency of the system. In 2019, Ikram et al. [25] proposed a conditional privacy-preserving authentication scheme for V2I. This scheme uses general one-way hash functions instead of map-to-point hash functions to achieve high efficiency.The identity-based authentication schemes for VANET address the problems presented by the schemes based on PKI. The existing schemes [21–25] are novel in design and have good security. However, the bilinear pairing operations of elliptic curve are used, and the computational efficiency of bilinear pairing operation is low. The works [26–28] based on pseudonym on elliptic curve, which do not use bilinear pairing operation and have achieved high computational efficiency. However, TA is required to participate in authentication, this increases communication times and communication burden. He et al. [29] proposed a privacy protection authentication scheme based on identity. This scheme also uses elliptic curve instead of bilinear pairing operations and achieves satisfactory performance in both computation and communication. However, the scheme is based on ideal TPD, and the master key is stored on the TPD of each vehicle. Islam et al. [30] proposed a conditional privacy-preserving authentication scheme based on hash function. And the scheme offers group-key generation, user leaving, user join, and password change facilities. The scheme does not need bilinear pairing mapping or elliptic curve operation and is lightweight in terms computation and communication. However, TA is required to participate in each authentication between the vehicle and RSU. Wu et al. [6] proposed an effective location-based conditional secret authentication scheme. The scheme does not require bilinear pairing operations or TPDs. However, when RSU is certified by vehicle, TA needs to query the database and return the results. Cui et al. [31] proposed a scheme without relying on any special hardware such as TPD. The scheme is based on elliptic discrete logarithm and has high computational performance. The cuckoo filter and binary tree search method are used to achieve a higher success rate in batch authentication. However, TA is required to generate communication key for the vehicle and RSU. Zhong et al. [32] proposed an authentication and key agreement scheme based on hash function and registration list. And the scheme does not require the strong security assumptions of TPD. Xiong Li et al. [33] proposed a lightweight authentication scheme for VANETs with only hash functions and exclusive-OR operations. Compared with previous schemes, the computational cost of the schemes [32, 33] has been greatly improved. However, the schemes also need TA to participate in the authentication. In recent years, there are some authentication schemes using group key, which can reduce the authentication burden of TA. The works [34, 35] introduce group key management schemes based on Chinese remainder theorem, which reduces computation complexity of the key server. In 2019, Jing Zhang et al. [36] proposed a message authentication scheme based on the group key using Chinese remainder theorem. The TPD of the vehicle only save the real identity and the group key. So the proposed scheme only requires realistic TPDs and ensures higher security for the entire system. In 2020, Wei et al. [37] proposed tow privacy-preserving multimodal implicit authentication protocols for Internet of connected vehicles. The proposed protocols use the password and vehicle owner’s behavior features as the authentication factors skillfully and do not reveal any information about vehicle owner’s behavior. The protocols have advantages in computational cost and accuracy. However, the protocols do not consider the unlinkability of sessions. Vinoth et al. [38] proposed a multifactor authenticated key agreement scheme for industrial Internet of things (IoT). The scheme implements authentication and key agreement between the user and multiple sensing devices at the same time. The scheme only used hash function, bit-wise XOR operation, and symmetric cryptography. It has less communication cost and computational cost compared with other correlative schemes. However, the scheme does not consider internal attack.


## 1.2. Our Contributions

In this study, an anonymous authentication and key agreement scheme based on elliptic curve for VANET is proposed. Each vehicle is equipped with a TPD. The TPD saves the private key of the vehicle and the group key for multivehicle communication. The vehicle can authenticate with RSU anonymously by combining a private key with a group key. After successful authentication, the session key can be negotiated for both parties. The scheme can also implement message signature and anonymous verification. In this scheme, the TPD only saves the private key of the vehicle and the group key instead of the system key. The attack on the TPD will not affect other nodes in VANET. So, we only need realistic TPD instead of ideal TPD. There is no need for the third party to participate in the authentication and key agreement between vehicle and RSU compared with the works [6, 30–33], and there is no need to query the database in the scheme. In addition, the use of group key in this scheme can help RSU resist certain denial of service (DoS) attacks.The main contributions of this study are summarized as follows.(1)
In order to optimize the computational cost and key management, we present an efficient anonymous authentication and key agreement scheme for RSUs and vehicles using the private key of the vehicle and the group key(2)
In order to reduce the communication time and storage space, we implement independent authentication and key agreement between vehicle and RSU, and RSU does not need to save vehicle information or query database.(3)
In this scheme, we also implement anonymous signature and verification of messages(4)
In this scheme, we use realistic TPDs instead of ideal TPDs, which is more suitable for VANET


## 1.3. Organization of This Article

The rest of the study is structured as follows: Section2 describes the preliminaries of the proposed scheme, Section 3 gives the working of the proposed scheme, Sections 4 and 5 present a security analysis and a performance analysis, respectively. Our study is concluded in Section 6.


## 2. Preliminaries

In this section, we introduce the related background information of VANET and the proposed scheme.


### 2.1. Network Model

As shown in Figure1, the network model of VANET mainly includes TA, RSU, OBU, TPD, and application server (AS). TA is a trusted service center. It is responsible for generating the private and public keys for RSU and vehicle and the group key for multivehicle communication. TA is an entity with the highest level of security protection and is completely trusted. RSU is the communication equipment installed on both sides of the road, with high security, thus providing access service for vehicles. The RSU communicates with the vehicle using DSRC protocol. Each vehicle is equipped with an OBU. The OBU of the vehicle realizes short distance communication with RSU and OBUs of other vehicles. TA allocates a TPD to each vehicle. TPD has high security, and other attackers cannot obtain sensitive information from the device [39]. AS is an application server and provides data service for TA. AS has high security and is credible.Figure 1
VANET network model.


### 2.2. Elliptic Curve

Suppose thatFP denotes a finite field of order p, where p is a large prime number. E denotes an elliptic curve over FP. The curve E is defined as y2=x3+ax+bmodp, where a,b∈Fp. The group G is a cyclic additive group of order q on E, and P is the generator and O is the infinite point.The groupG has the following properties:(1)
Additive (±). ForP,Q∈G, if P ≠Q, R = P + Q, then R is the intersection point of the straight line passing through P and Q with E; if P = Q, R = P + Q, then R is the tangent intersection point of P and Q with E; if P = -Q, then P + Q = P - P = O.(2)
Scalar multiplication (.). Letm∈Zq∗, scalar point multiplication in G is defined as m. P = P + P + … + P (m times).Two difficult problems are defined as follows:Definition 1.
Elliptic curve discrete logarithm problem (ECDLP). LetQ be a random point on G and calculate a solution x which satisfies Q = xP, where x∈Zq∗.Definition 2.
Elliptic curve computational Diffie–Hellman problem (ECCDH). Assume a generatorP of G, aP,bP∈G, where a,b∈Zq∗ are unknown. The ECCDH problem is to compute abP∈G.
If ECDLP or ECCDH on a groupG cannot be solved with nonnegligible probability ε in time t, then ECDLP or ECCDH is said to be a difficult problem on elliptic curve.


### 2.3. Security Requirements

The open multihop wireless network is vulnerable to various attacks. Therefore, the authentication and key agreement for VANET need to meet the following security requirements [29, 39]:(1)
Authentication and integrity. After receiving the message, VANET needs to determine whether the source of the message is reliable and whether the message has been tampered by others(2)
Privacy protection. When users are communicating, VANET should protect the confidential information such as user’s identity, session record, location, and driving path. VANET provides privacy protection by imparting anonymity.(3)
Session key agreement. When the vehicle transmits data with RSU, the session key should be used to encrypt the data to protect the session privacy(4)
Traceability. To prevent malicious users from sending false messages by anonymity, the authentication scheme should trace the real identity of the sender when the message is in dispute(5)
Resistance to attacks. VANET is vulnerable to various attacks, such as replay attacks and forgery attacks. Authentication and key agreement of VANET needs to be able to resist all kinds of attacks to ensure the security and reliability of the scheme.(6)
Unlinkability. In order to protect privacy, attackers or other vehicles cannot link different sessions of the same vehicle via the public channel.


## 2.1. Network Model

As shown in Figure1, the network model of VANET mainly includes TA, RSU, OBU, TPD, and application server (AS). TA is a trusted service center. It is responsible for generating the private and public keys for RSU and vehicle and the group key for multivehicle communication. TA is an entity with the highest level of security protection and is completely trusted. RSU is the communication equipment installed on both sides of the road, with high security, thus providing access service for vehicles. The RSU communicates with the vehicle using DSRC protocol. Each vehicle is equipped with an OBU. The OBU of the vehicle realizes short distance communication with RSU and OBUs of other vehicles. TA allocates a TPD to each vehicle. TPD has high security, and other attackers cannot obtain sensitive information from the device [39]. AS is an application server and provides data service for TA. AS has high security and is credible.Figure 1
VANET network model.


## 2.2. Elliptic Curve

Suppose thatFP denotes a finite field of order p, where p is a large prime number. E denotes an elliptic curve over FP. The curve E is defined as y2=x3+ax+bmodp, where a,b∈Fp. The group G is a cyclic additive group of order q on E, and P is the generator and O is the infinite point.The groupG has the following properties:(1)
Additive (±). ForP,Q∈G, if P ≠Q, R = P + Q, then R is the intersection point of the straight line passing through P and Q with E; if P = Q, R = P + Q, then R is the tangent intersection point of P and Q with E; if P = -Q, then P + Q = P - P = O.(2)
Scalar multiplication (.). Letm∈Zq∗, scalar point multiplication in G is defined as m. P = P + P + … + P (m times).Two difficult problems are defined as follows:Definition 1.
Elliptic curve discrete logarithm problem (ECDLP). LetQ be a random point on G and calculate a solution x which satisfies Q = xP, where x∈Zq∗.Definition 2.
Elliptic curve computational Diffie–Hellman problem (ECCDH). Assume a generatorP of G, aP,bP∈G, where a,b∈Zq∗ are unknown. The ECCDH problem is to compute abP∈G.
If ECDLP or ECCDH on a groupG cannot be solved with nonnegligible probability ε in time t, then ECDLP or ECCDH is said to be a difficult problem on elliptic curve.


## 2.3. Security Requirements

The open multihop wireless network is vulnerable to various attacks. Therefore, the authentication and key agreement for VANET need to meet the following security requirements [29, 39]:(1)
Authentication and integrity. After receiving the message, VANET needs to determine whether the source of the message is reliable and whether the message has been tampered by others(2)
Privacy protection. When users are communicating, VANET should protect the confidential information such as user’s identity, session record, location, and driving path. VANET provides privacy protection by imparting anonymity.(3)
Session key agreement. When the vehicle transmits data with RSU, the session key should be used to encrypt the data to protect the session privacy(4)
Traceability. To prevent malicious users from sending false messages by anonymity, the authentication scheme should trace the real identity of the sender when the message is in dispute(5)
Resistance to attacks. VANET is vulnerable to various attacks, such as replay attacks and forgery attacks. Authentication and key agreement of VANET needs to be able to resist all kinds of attacks to ensure the security and reliability of the scheme.(6)
Unlinkability. In order to protect privacy, attackers or other vehicles cannot link different sessions of the same vehicle via the public channel.


## 3. Proposed Authentication Scheme for VANET

Our scheme includes the following phases: initialization, RSU and vehicle registration, authentication and communication key agreement, message signing, signature verification, identity extraction, and updating the group key. The mutual authentication and the key agreement process between RSU and the vehicle is shown in Figure2. The main notations used in the scheme are given in Table 1.Figure 2
Mutual authentication and key agreement.Table 1
Notations used.
NotationDescriptionEAn elliptic curveGAn additive group based onEPA generator ofGp, qLarge prime numberss, PpubPrivate key and public key pairs of the systemX, PxGroup key and group public key pairsh0, h1, h2, h3,h4,h5Six secure hash functionsIDjIdentity of the RSUsj, PjPrivate key and public key pairs of the RSUsi, PiPrivate key and public key pairs of the vehicleRIDiReal identities of the vehiclePIDiPseudonym of the vehicleTi, TmTimestampskSession key between RSU and the vehicleMiTraffic-related message


### 3.1. Initialization Phase

TA selects random numberss,x∈Zq∗, s is the private key of the system, x is the group key for multivehicle communication, and it can be used to compute the public key Ppub=sP∈G. Furthermore, Px=xP∈G. TA selects five secure hash functions: h0:0,1∗×G⟶Zq∗, h1:G⟶Zq∗, h2:0,1∗×0,1∗×G×0,1∗⟶Zq∗, h3:0,1∗×0,1∗×G×G×0,1∗, h4:0,1∗×0,1∗×G×0,1∗×0,1∗⟶Zq∗, and h5:0,1∗×0,1∗×G×G×G×0,1∗⟶Zq∗. TA also broadcasts the system parameters: Paras=E,a,b,p,q,P,Ppub,Px,h0,h1,h2,h3,h4,h5.


### 3.2. RSU and Vehicle Registration Phase

Roadside unit RSUj applies to TA for registration. After TA verifies the information of RSUj successfully, it allocates the identity IDj to RSUj. Then, TA selects a random number rj, computes hrj=h0IDj,Rj and Rj=rjP. TA also generates the private key sj=rj+hrjs and then returns Rj, sjto RSUj. RSUj computes Pj=sjP and verifies whether the following equation holds.(1)Pj=Rj+hrjPpub,∵Pj=sjP=rjP+hrjsP=Rj+hrjPpub.If (1) holds, RSUj broadcasts Rj, IDj, and Pj. Otherwise, the message is rejected. After RSU broadcasts the public key Pj, the vehicle can use Pj to compute the pseudonym of the vehicle. The detailed process is shown in Section 3.3.During the registration process, the vehicle users go to TA directly. The vehicle users submit the required information such as identification, phone number, and license, etc., to TA. TA checks whether the vehicle user is qualified. If the vehicle user is qualified, TA allocates a TPD to the vehicleVi and assigns a unique identity RIDi to the vehicle Vi. TA allows users to set a username and password for TPD. Then, TA chooses a random number ri and computes Ri=riP, hvi=h0RIDi,Ri, si=ri+hvis, and Pi=siP. TA saves si, x, RIDi, Ri, and Pi in the TPD of the vehicle Vi. At the same time, the vehicle information such as RIDi, Ri, and Pi is saved in AS.


### 3.3. Authentication and Communication Key Agreement Phase

RSUj broadcasts Rj, IDj and Pj; the OBU of the vehicle receives them and verifies whether (1) holds. If it holds, the OBU forwards them to the TPD of the vehicle. The TPD selects the random numbers ui,li∈Zq∗, and the timestamp Ti. The TPD computes the pseudonymPIDi=RIDi⊕h1liPj and generates the signatures δi1=ui+hi1x and δi2=li+hi2si, where Ui=uiP, hi1=h2IDj,PIDi,Ui,Ti, Li=liP, PR=Ri+liPj, and hi2=h3IDj,PIDi,PR,Li,Ti. It sends δi1,δi2,Ui,PIDi,PR,Li,Ti to RSUj through the OBU.RSUj receives δi1,δi2,Ui,PIDi,PR,Li,Ti), and then, it computes hi1=h2IDj,PIDi,Ui,Ti and verifies whether the following equation holds.(2)δi1P=Ui+hi1Px,∵δi1P=uiP+hi1xP=Ui+hi1Px.If (2) holds, RSUj computes RIDi=PIDi⊕h1sjLi, Ri=PR−sjliP=PR−sjLi, hvi=h0RIDi,Ri, and hi2=h3IDj,PIDi,PR,Li,Ti and verifies whether the following equation holds.(3)δi2P=Li+hi2Ri+hi2hviPpub,∵δi2P=liP+hriP+hvisPi2,=Li+hi2Ri+hi2hviPpub,if both (2) and (3) hold, the vehicle is legal. RSUj chooses a random number uj∈Zq∗ and computes Uj=ujP, sk=h2IDj,RIDi,ujUi,Ti, hj=h4IDj,RIDi,Uj,sk,Ti, and δj=hjsj+uj. RSUj sends δj,Uj,PIDi,IDj,Rj to the vehicle Vi.The vehicleVi receivesδj,Uj,PIDi,IDj,Rj, and then, it computes hrj=h0IDj,Rj and hj=h4IDj,RIDi,Uj,sk,Ti and verifies whether the following equation holds.(4)δjP=hjRj+hjhrjPpub+Uj,∵δjP=hjsjP+ujP=hjPj+Uj,=hjRj+hjhrjPpub+Uj.If (4) holds, the vehicle Vi computes sk=h2IDj,RIDi,uiUj,Ti, which is the session key between Vi and RSUj.The process of authentication and key agreement between vehicle and RSU is shown in Figure2.


### 3.4. Message Signing Phase

When a vehicle needs to send a messageMi in the area covered by the roadside unit RSUj, the TPD of the vehicle chooses a random number vi∈Zq∗ and the timestamp Tm and computes Vi=viP, Pv=Ri+viPj, the pseudonym PIDi=RIDi⊕h1viPj, and σi=hrvhvi−1si+vi+hmix, where hrv=h2Mi,PIDi,Rvi,Tm, R=vihvi−1Ri+Vi, and hmi=h5Mi,PIDi,Pv,Vi,Rvi,Tm. The TPD then broadcasts the signature σi,Mi,PIDi,Vi,Pv,Rvi,Tm.


### 3.5. Signature Verification

RSUj receives σi,Mi,PIDi,Vi,Pv,Rvi,Tm, and then, it checks whether the timestamp Tm is within the valid time. If it is, RSUj extracts the real identity of the vehicle RIDi=PIDi⊕h1sjViand computes Ri=Pv−sjVi, hvi=h0RIDi,Ri, Rvi=hvi−1Ri+Vi, hrv=h2Mi,PIDi,Rvi,Tm, hmi=h5Mi,PIDi,Pv,Vi,Rvi,Tm, and verifies whether (5) holds.(5)hviσiP=hrvRi+Vi+hrvhviPpub+hvihmiPx,∵hviσiP=hrvsi+viP+hvihmixP,=hrvRi+hvisP+Vi+hvihmiPx=hrvRi+Vi+hrvhviPpub+hvihmiPx.If it holds, RSUj accepts the message. If it does not, it means that the TPD of the vehicle is damaged. For example, suppose the attackers stole the private and group keys of the TPD, faked the identity RIDi′, generated the pseudonym PIDi′, forged the signature (σi,Mi,PIDi′,Vi′,Pv′,Rvi′,Tm), and enabled it to satisfy (6). However, according to the TPD security assumption, this situation is extremely rare. If RSUj detects that the TPD has been attacked, it immediately broadcasts that the signature σi,Mi,PIDi′,Vi′,Pv′,Rvi′,Tm is not valid.Other vehicles receiveσi,Mi,PIDi,Vi,Pv,Rvi,Tm, and then, they check whether the timestamp Tm is within the valid time. If it is, the vehicles compute hrv=h2Mi,PIDi,Rvi,Tm and hmi=h5Mi,PIDi,Pv,Vi,Rvi,Tm and verify whether the following equation holds.(6)σiP=hrvRvi+hrvPpub+hmiPx,∵σiP=hrvhvi−1si+viP+hmixP=hrvhvi−1Ri+hvisP+Vi+hmiPx=hrvhvi−1Ri+Vi+hrvPpub+hmiPx=hrvRvi+hrvPpub+hmiPx.If it does and the vehicles do not receive an invalid signature broadcasted by RSUj within the specified time, the vehicles accept the message Mi.


### 3.6. Identity Extraction

When a valid message signatureσi,Mi,PIDi,Vi,Pv,Rvi,Tm is in dispute, it is necessary to track the real identity of a vehicle. RSUj can extract the real identity of the vehicle through computing RIDi=PIDi⊕h1sjVi.


### 3.7. Updating the Group Key Phase

TA chooses a random numberwi∈Zq∗ and the timestamp Tv and computes Wi=xwiP, δt=sh0xwiP,Tv+xwi, Px=h3wiP,xP,TvP, where Px is as a new group public key. TA broadcasts the signature δt,Wi,Tv,Px.After the vehicles receiveδt,Wi,Tv,Px, they compute x−1Wi and verify whether the following equation holds. If it does, the vehicles update the group key as x=h3x−1Wi,xP,Tv.(7)δtP=h0Wi,TvPpub+xWi.


## 3.1. Initialization Phase

TA selects random numberss,x∈Zq∗, s is the private key of the system, x is the group key for multivehicle communication, and it can be used to compute the public key Ppub=sP∈G. Furthermore, Px=xP∈G. TA selects five secure hash functions: h0:0,1∗×G⟶Zq∗, h1:G⟶Zq∗, h2:0,1∗×0,1∗×G×0,1∗⟶Zq∗, h3:0,1∗×0,1∗×G×G×0,1∗, h4:0,1∗×0,1∗×G×0,1∗×0,1∗⟶Zq∗, and h5:0,1∗×0,1∗×G×G×G×0,1∗⟶Zq∗. TA also broadcasts the system parameters: Paras=E,a,b,p,q,P,Ppub,Px,h0,h1,h2,h3,h4,h5.


## 3.2. RSU and Vehicle Registration Phase

Roadside unit RSUj applies to TA for registration. After TA verifies the information of RSUj successfully, it allocates the identity IDj to RSUj. Then, TA selects a random number rj, computes hrj=h0IDj,Rj and Rj=rjP. TA also generates the private key sj=rj+hrjs and then returns Rj, sjto RSUj. RSUj computes Pj=sjP and verifies whether the following equation holds.(1)Pj=Rj+hrjPpub,∵Pj=sjP=rjP+hrjsP=Rj+hrjPpub.If (1) holds, RSUj broadcasts Rj, IDj, and Pj. Otherwise, the message is rejected. After RSU broadcasts the public key Pj, the vehicle can use Pj to compute the pseudonym of the vehicle. The detailed process is shown in Section 3.3.During the registration process, the vehicle users go to TA directly. The vehicle users submit the required information such as identification, phone number, and license, etc., to TA. TA checks whether the vehicle user is qualified. If the vehicle user is qualified, TA allocates a TPD to the vehicleVi and assigns a unique identity RIDi to the vehicle Vi. TA allows users to set a username and password for TPD. Then, TA chooses a random number ri and computes Ri=riP, hvi=h0RIDi,Ri, si=ri+hvis, and Pi=siP. TA saves si, x, RIDi, Ri, and Pi in the TPD of the vehicle Vi. At the same time, the vehicle information such as RIDi, Ri, and Pi is saved in AS.


## 3.3. Authentication and Communication Key Agreement Phase

RSUj broadcasts Rj, IDj and Pj; the OBU of the vehicle receives them and verifies whether (1) holds. If it holds, the OBU forwards them to the TPD of the vehicle. The TPD selects the random numbers ui,li∈Zq∗, and the timestamp Ti. The TPD computes the pseudonymPIDi=RIDi⊕h1liPj and generates the signatures δi1=ui+hi1x and δi2=li+hi2si, where Ui=uiP, hi1=h2IDj,PIDi,Ui,Ti, Li=liP, PR=Ri+liPj, and hi2=h3IDj,PIDi,PR,Li,Ti. It sends δi1,δi2,Ui,PIDi,PR,Li,Ti to RSUj through the OBU.RSUj receives δi1,δi2,Ui,PIDi,PR,Li,Ti), and then, it computes hi1=h2IDj,PIDi,Ui,Ti and verifies whether the following equation holds.(2)δi1P=Ui+hi1Px,∵δi1P=uiP+hi1xP=Ui+hi1Px.If (2) holds, RSUj computes RIDi=PIDi⊕h1sjLi, Ri=PR−sjliP=PR−sjLi, hvi=h0RIDi,Ri, and hi2=h3IDj,PIDi,PR,Li,Ti and verifies whether the following equation holds.(3)δi2P=Li+hi2Ri+hi2hviPpub,∵δi2P=liP+hriP+hvisPi2,=Li+hi2Ri+hi2hviPpub,if both (2) and (3) hold, the vehicle is legal. RSUj chooses a random number uj∈Zq∗ and computes Uj=ujP, sk=h2IDj,RIDi,ujUi,Ti, hj=h4IDj,RIDi,Uj,sk,Ti, and δj=hjsj+uj. RSUj sends δj,Uj,PIDi,IDj,Rj to the vehicle Vi.The vehicleVi receivesδj,Uj,PIDi,IDj,Rj, and then, it computes hrj=h0IDj,Rj and hj=h4IDj,RIDi,Uj,sk,Ti and verifies whether the following equation holds.(4)δjP=hjRj+hjhrjPpub+Uj,∵δjP=hjsjP+ujP=hjPj+Uj,=hjRj+hjhrjPpub+Uj.If (4) holds, the vehicle Vi computes sk=h2IDj,RIDi,uiUj,Ti, which is the session key between Vi and RSUj.The process of authentication and key agreement between vehicle and RSU is shown in Figure2.


## 3.4. Message Signing Phase

When a vehicle needs to send a messageMi in the area covered by the roadside unit RSUj, the TPD of the vehicle chooses a random number vi∈Zq∗ and the timestamp Tm and computes Vi=viP, Pv=Ri+viPj, the pseudonym PIDi=RIDi⊕h1viPj, and σi=hrvhvi−1si+vi+hmix, where hrv=h2Mi,PIDi,Rvi,Tm, R=vihvi−1Ri+Vi, and hmi=h5Mi,PIDi,Pv,Vi,Rvi,Tm. The TPD then broadcasts the signature σi,Mi,PIDi,Vi,Pv,Rvi,Tm.


## 3.5. Signature Verification

RSUj receives σi,Mi,PIDi,Vi,Pv,Rvi,Tm, and then, it checks whether the timestamp Tm is within the valid time. If it is, RSUj extracts the real identity of the vehicle RIDi=PIDi⊕h1sjViand computes Ri=Pv−sjVi, hvi=h0RIDi,Ri, Rvi=hvi−1Ri+Vi, hrv=h2Mi,PIDi,Rvi,Tm, hmi=h5Mi,PIDi,Pv,Vi,Rvi,Tm, and verifies whether (5) holds.(5)hviσiP=hrvRi+Vi+hrvhviPpub+hvihmiPx,∵hviσiP=hrvsi+viP+hvihmixP,=hrvRi+hvisP+Vi+hvihmiPx=hrvRi+Vi+hrvhviPpub+hvihmiPx.If it holds, RSUj accepts the message. If it does not, it means that the TPD of the vehicle is damaged. For example, suppose the attackers stole the private and group keys of the TPD, faked the identity RIDi′, generated the pseudonym PIDi′, forged the signature (σi,Mi,PIDi′,Vi′,Pv′,Rvi′,Tm), and enabled it to satisfy (6). However, according to the TPD security assumption, this situation is extremely rare. If RSUj detects that the TPD has been attacked, it immediately broadcasts that the signature σi,Mi,PIDi′,Vi′,Pv′,Rvi′,Tm is not valid.Other vehicles receiveσi,Mi,PIDi,Vi,Pv,Rvi,Tm, and then, they check whether the timestamp Tm is within the valid time. If it is, the vehicles compute hrv=h2Mi,PIDi,Rvi,Tm and hmi=h5Mi,PIDi,Pv,Vi,Rvi,Tm and verify whether the following equation holds.(6)σiP=hrvRvi+hrvPpub+hmiPx,∵σiP=hrvhvi−1si+viP+hmixP=hrvhvi−1Ri+hvisP+Vi+hmiPx=hrvhvi−1Ri+Vi+hrvPpub+hmiPx=hrvRvi+hrvPpub+hmiPx.If it does and the vehicles do not receive an invalid signature broadcasted by RSUj within the specified time, the vehicles accept the message Mi.


## 3.6. Identity Extraction

When a valid message signatureσi,Mi,PIDi,Vi,Pv,Rvi,Tm is in dispute, it is necessary to track the real identity of a vehicle. RSUj can extract the real identity of the vehicle through computing RIDi=PIDi⊕h1sjVi.


## 3.7. Updating the Group Key Phase

TA chooses a random numberwi∈Zq∗ and the timestamp Tv and computes Wi=xwiP, δt=sh0xwiP,Tv+xwi, Px=h3wiP,xP,TvP, where Px is as a new group public key. TA broadcasts the signature δt,Wi,Tv,Px.After the vehicles receiveδt,Wi,Tv,Px, they compute x−1Wi and verify whether the following equation holds. If it does, the vehicles update the group key as x=h3x−1Wi,xP,Tv.(7)δtP=h0Wi,TvPpub+xWi.


## 4. Security Analysis

Under the random oracle model, the security model of [39] is used to prove the security of our scheme.


### 4.1. Proof of Safety

Lemma 1.
The authentication request message of the vehicle cannot be forged. When ECDLP is a difficult problem, our scheme can resist the forgery attack of adaptive chosen message.Proof:.
We assume that there is an attacker Ad who can successfully forge the request message of a vehicle in polynomial timeε. Given an ECDLP instance P,Q=xP,P,Q∈G,x∈Zq∗, the challenger Ch can solve the ECDLP in polynomial time ε.
The challengerCh sets system parameters paras = Epa,b,p,q,G,P,Ppub,Px,h0,h1,h2,h3,h4,h5. Ch randomly chooses RIDi of a vehicle as the identity of the challenger Ch. Ch builds and maintains six hash lists: Lhl, where l=0,1,2,…,5. Finally, Ch sends params to Ad.
h1-Oracle. When Ad makes a query with θ, Ch checks whether the tuple θ,τh1 is already in Lh1 or not. If it is, Ch sends τh1 to Ad. Otherwise, Ch randomly selects τh1∈Zq∗ and adds θ,τh1to Lh1. Finally, Ch sends τh1=h1θ to Ad.
h2-Oracle. When Ad makes a query with IDj,PIDi,Ui,Ti, Ch checks whether the tuple IDj,PIDi,Ui,Ti,τh2 is already in Lh2 or not. If it is, Ch sends τh2 to Ad. Otherwise, Ch randomly selects τh2∈Zq∗ and adds IDj,PIDi,Ui,Ti,τh2to Lh2. Finally, Ch sends τh2=h2IDj,PIDi,Ui,Ti to Ad.
h3-Oracle. When Ad makes a query with IDj,PIDi,PR,Li,Ti, Ch checks whether the tuple IDj,PIDi,PR,Li,Ti,τh3 is already in Lh3 or not. If it is, Ch sends τh3 to Ad. Otherwise, Ch randomly selectsτh3∈Zq∗ and adds IDj,PIDi,PR,Li,Ti,τh3 to Lh3. Finally, Ch sends τh3=h3IDj,PIDi,PR,Li,Ti to Ad.
Extract (RIDi). Ch builds and maintains the list Lv=RIDi,Ri,si. When Ad makes a query with RIDi and Ri, Ch checks whether the tuple RIDi,Ri,si is in Lv. If it is, Ch sends sito Ad. Otherwise, Ch randomly selects si,hvi∈Zq∗, lets Ri=siP−hviP, and adds them to Lv. Finally, Ch sends Lv=RIDi,Ri,si to Ad.
Sign-Oracle. When Ad makes a query with PIDi,Ti, Ch randomly selects hi1,hi2,hvi,δi1,δi2∈Zq∗ and sets Ui=δi1P−hi1Px, Ri=siP−hviP, Li=δi2P−hi2Ri−hi2hviPpub, and PR=Ri+sjLi. Finally, Ch sends δi1,δi2,Ui,PIDi,PR,Li,Ti to Ad.
Output. Finally, Ad outputs an authentication request message δi1,δi2,Ui,PIDi,PR,Li,Ti with nonnegligible probability. According to the forgery lemma [40],.Ad chooses different hi1′ andhvi′ and generates another valid authentication request message δi1′,δi2′,Ui,PIDi,PR,Li,Ti in polynomial time. At this time, the two authentication request messages satisfy the following:(8)δi1P=Ui+hi1Px,(9)δi1′P=Ui+hi1′Px,(10)δi2P=hi2Ri+hi2hviPpub+Li,(11)δi2′P=hi2Ri+hi2hvi′Ppub+Li.
From (8)–(11), we can obtain(12)δi1−δi1′P=hi1−hi1′Px,(13)δi2−δi2′P=hi2hvi−hi2hvi′Ppub.
Now, according to (12) and (13), Ad outputsx=δi1−δi1′hi1−hi2′−1, and s=δi2−δi2′hi2hvi−hi2hvi′−1.However, solving x or s is an ECDLP problem. Furthermore, it is impossible for an adversary to solve the ECDLP problem in polynomial time.Lemma 2.
The authentication response message cannot be forged. Since ECDLP is difficult to solve, our scheme can resist the forgery attack of adaptive chosen message.Proof.
We assume that there is an attacker Ad who can successfully forge an authentication response message in polynomial time. Given an ECDLP instanceP,Q=xP,P,Q∈G,x∈Zq∗, then the challenger Ch can solve the ECDLP with nonnegligible probability. The challenger Ch sets system parameters paras =  Epa,b,p,q,G,P,Ppub,Px,h0,h1,h2,h3,h4,h5. Ch builds and maintains six lists: Lhl, where l=0,1,2,…,5. Finally, Ch sends params to Ad.
h1-Oracle. When Ad makes a query with θ, Ch checks whether the tuple θ,τh1 is already in Lh1 or not. If it is, Ch sends τh1 to Ad. Otherwise, Ch randomly selects τh1∈Zq∗ and adds θ,τh1 to Lh1. Finally, Ch sends τh1=h1θ to Ad.
h2-Oracle. When Ad makes a query with IDj,RIDi,ujUi,Ti, Ch checks whether the tuple IDj,RIDi,ujUi,Ti,τh2 is already in Lh2 or not. If it is, Ch sends τh2 to Ad. Otherwise, Ch randomly selects τh2∈Zq∗ and adds IDj,RIDi,ujUi,Ti,τh2 to hh22. Finally, Ch sends τh2=h2IDj,RIDi,ujUi,Ti to Ad.
Extract (IDj). Ch builds and maintains the list LR=IDj,Rj,sj. When Ad makes a query with IDj, Ch checks whether the tuple IDj,Rj,sj is in LR. If it is, Ch sends sjto Ad. Otherwise, Ch randomly selectssj,hrj∈Zq∗, lets Rj=sjP−hrjPpub, and adds IDj,Rj,sjto LR. Finally, Ch sends LR=IDj,Rj,sj to Ad.
Sign-Oracle. When Ad makes a query with (PIDi,Ti), Ch randomly chooses sk,hrj,hj,δj∈Zq∗and setsUj=δjP−hjRj−hjhrjPpub . Finally, Ch sends δj,Uj,PIDi,IDj,Rj to Ad.
Output. Finally, Ad outputs an authentication request message δj,Uj,PIDi,IDj,Rj with nonnegligible probability. According to the forgery lemma [40].Ad chooses different hrj′ and generates another valid authentication request message δj′,Uj,PIDi,IDj,Rj in polynomial time. Now, the two authentication request messages satisfy the following:(14)δjP=hjRj+hjhrjPpub+Uj,(15)δj′P=hjRj+hjhrj′Ppub+Uj.
From (14) and (15), we can deduce the following expression:(16)δj−δj′P=hjhrj−hrj′Ppub.
Next, Ch can outputs=δj−δj′hjhrj−hrj′−1modq. However, solving s is an ECDLP, which is impossible for an adversary to solve in polynomial time.Theorem 1.
From Lemma1 and Lemma 2, we know that when the ECDLP problem is difficult to solve, and the adversary cannot forge the authentication request message and response message, that is, our authentication scheme can resist adaptive chosen message forgery attack.Theorem 2.
The message signature cannot be forged. Since ECDLP is hard to solve, our scheme can resist the forgery attack of adaptive chosen message attack.Proof.
We assume that there is an attacker Ad who can successfully forge an authentication response message in polynomial time. Given an ECDLP instanceP,Q=xP,P,Q∈G,x∈Zq∗, the challenger Ch can solve the ECDLP in polynomial time ε.
The challenger Ch sets system parameters paras =Epa,b,p,q,G,P,Ppub,Px,h0,h1,h2,h3,h4,h5. Ch randomly chooses IDj as the identity of the challenger Ch. Ch builds and maintains six lists: Lhl, where l=0,1,2,…,5. Then, Ad adaptively queries the oracle machine to Ch, and Ch replies to Ad in the following way.
When Ad makes a query withPIDi,Mi,Tm, Ch randomly chooses hrv,hmi,σi∈Zq∗, and Vi,Pv∈G; furthermore, it sets Rvi=hrv−1σiP−hrvPpub−hmiPx. Finally, Ch sends σi,Mi,Vi,Pv,Rvi,Tm to Ad.
Subsequently, Ad outputs a valid signatureσi,Mi,Vi,Pv,Rvi,Tm with a nonnegligible probability. According to the forgery lemma [40], Ad chooses different hmi′ and generates another valid signature σi′,Mi,Vi,Pv,Rvi,Tm in polynomial time. At this time, the two signatures satisfy the following relationships:(17)σiP=hrvRvi+hrvPpub+hmiPx,(18)σi′P=hrvRvi+hrvPpub+hmi′Px.
From (17) and (18), we can obtain the following equation:(19)σi−σi′P=h−mihmi′Px.
Now, according to (19), Ch can output x=σi−σi′hmi−hmi′−1modq. However, solving for x is an ECDLP problem, which is impossible for an adversary to solve in polynomial time. Thus, our proposed signature scheme under the random oracle model is resistant against a chosen adaptive message attack.Theorem 3.
The key agreement of our scheme is secure under the ECCDH problem.Proof.
Given an ECCDH instance,Q1=x1P,Q2=x2P, and Q3=x1x2P, where x1,x2∈Zq∗. In our key agreement, we let Q1⟵Ui=uiP, Q2⟵Uj=ujP,Q3⟵uiujP. In this method, if the attacker Ad gets uiujP according to Ui,Uj, the key negotiated between the vehicle and RSU can be obtained. However, it is impossible for the adversary to solve the ECCDH problem in polynomial time, implying that the key agreement proposed in this study is secure.Theorem 4.
In the random oracle model, we can achieve conditional anonymity and traceability.Proof.
In the proposed scheme, the authentication request message uses the pseudonymPIDi=RIDi⊕h1liPj, where Li=liP, li∈Zq∗. According to ECDLP, it is not feasible for the adversary to solve liPj without knowing li. The request authentication signatures areδi1=ui+hi1x and δi2=hi2si+li, where hi1=h2IDj,PIDi,Ui,Ti, hi2=h3IDj,PIDi,PR,Li,Ti, and ui,li∈zq∗ are the random numbers. Every time a vehicle is certified, it can produce unrelated pseudonyms and different authentication requests. Similarly, the pseudonym is also used in message signature PIDi=RIDi⊕hviPj, Vi=viP. The message signature is σi,Mi,Vi,Pv,Rvi,Tm, σi=hrvhvi−1si+vi+hmix, hrv=h2Mi,PIDi,Rvi,Tm, and hmi=h5Mi,PIDi,Pv,Vi,Rvi,Tm. The pseudonym used in the signature is different every time. Therefore, the scheme can provide anonymity for vehicle users in authentication and message signature. In addition, this scheme can also realize the traceability of the real identity; RSU can calculate the real identity of the vehicle RIDi=PIDi⊕h1sjLi through the private key. Similarly, through pseudonym of signature message PIDi=RIDi⊕hviPj, RSU can also calculate RIDi=PIDi⊕h1sjVi using the private key. Therefore, this scheme can realize the traceability of identity.Theorem 5.
In the proposed scheme, we can achieve unlinkability.Proof.
In our scheme, the authentication request message of the vehicleδi1,δi2,Ui,PIDi,PR,Li,Ti is different for each session. Meanwhile, the signature message σi,Mi,PIDi,Vi,Pv,Rvi,Tm is also different for each message. Therefore, all elements from the message of the vehicle are different, and any attacker cannot tell apart if two different messages from the same vehicle. Thus, our proposed scheme supports unlinkability.


### 4.2. Other Security Analysis and Feature Comparison

From Theorem1 and Theorem 2, it is ascertained that under the random oracle model, the authentication, key agreement, and message signature can resist adaptive chosen message forgery attacks. Additionally, there is no need for the certification table or TA to participate in the certification between vehicle and RSU. Both authentication and message signature use timestamp, which can resist replay attack. In the authentication process, RSU first checks whether the group key signature is legal, and then, it verifies the vehicle private key signature. If the group key signature is illegal, the signature is discarded directly, which can resist DoS attack to a certain extent. In this scheme, the vehicle is equipped with a TPD, which stores the private key of the vehicle and the group key. Even if a single TPD is attacked, the attacker can only intercept the group key and the private key of the vehicle. The authentication, key agreement, and message signature all need the private key of the vehicle. Thus, the attacker can only forge the signature of a single vehicle, without affecting the communication security of other VANET nodes. The schemes [13, 24] keep the system key in the TPD of each vehicle; this requires a strong TPD security assumption. If a single TPD is successfully attacked, the whole system will not be secure. Table 2 provides the features comparison with other schemes. It can be seen from Table 2 that the proposed scheme has strong advantages in security and communication efficiency.Table 2
Features comparison.
FeatureLIAPNECPPAWu et al.Our schemeUsing bilinear paring operationYesYesNoNoUsing ideal TPDYesYesNoNoRequiring TA to participate in certificationYesYesYesNoSearching databaseYesYesYesNo


## 4.1. Proof of Safety

Lemma 1.
The authentication request message of the vehicle cannot be forged. When ECDLP is a difficult problem, our scheme can resist the forgery attack of adaptive chosen message.Proof:.
We assume that there is an attacker Ad who can successfully forge the request message of a vehicle in polynomial timeε. Given an ECDLP instance P,Q=xP,P,Q∈G,x∈Zq∗, the challenger Ch can solve the ECDLP in polynomial time ε.
The challengerCh sets system parameters paras = Epa,b,p,q,G,P,Ppub,Px,h0,h1,h2,h3,h4,h5. Ch randomly chooses RIDi of a vehicle as the identity of the challenger Ch. Ch builds and maintains six hash lists: Lhl, where l=0,1,2,…,5. Finally, Ch sends params to Ad.
h1-Oracle. When Ad makes a query with θ, Ch checks whether the tuple θ,τh1 is already in Lh1 or not. If it is, Ch sends τh1 to Ad. Otherwise, Ch randomly selects τh1∈Zq∗ and adds θ,τh1to Lh1. Finally, Ch sends τh1=h1θ to Ad.
h2-Oracle. When Ad makes a query with IDj,PIDi,Ui,Ti, Ch checks whether the tuple IDj,PIDi,Ui,Ti,τh2 is already in Lh2 or not. If it is, Ch sends τh2 to Ad. Otherwise, Ch randomly selects τh2∈Zq∗ and adds IDj,PIDi,Ui,Ti,τh2to Lh2. Finally, Ch sends τh2=h2IDj,PIDi,Ui,Ti to Ad.
h3-Oracle. When Ad makes a query with IDj,PIDi,PR,Li,Ti, Ch checks whether the tuple IDj,PIDi,PR,Li,Ti,τh3 is already in Lh3 or not. If it is, Ch sends τh3 to Ad. Otherwise, Ch randomly selectsτh3∈Zq∗ and adds IDj,PIDi,PR,Li,Ti,τh3 to Lh3. Finally, Ch sends τh3=h3IDj,PIDi,PR,Li,Ti to Ad.
Extract (RIDi). Ch builds and maintains the list Lv=RIDi,Ri,si. When Ad makes a query with RIDi and Ri, Ch checks whether the tuple RIDi,Ri,si is in Lv. If it is, Ch sends sito Ad. Otherwise, Ch randomly selects si,hvi∈Zq∗, lets Ri=siP−hviP, and adds them to Lv. Finally, Ch sends Lv=RIDi,Ri,si to Ad.
Sign-Oracle. When Ad makes a query with PIDi,Ti, Ch randomly selects hi1,hi2,hvi,δi1,δi2∈Zq∗ and sets Ui=δi1P−hi1Px, Ri=siP−hviP, Li=δi2P−hi2Ri−hi2hviPpub, and PR=Ri+sjLi. Finally, Ch sends δi1,δi2,Ui,PIDi,PR,Li,Ti to Ad.
Output. Finally, Ad outputs an authentication request message δi1,δi2,Ui,PIDi,PR,Li,Ti with nonnegligible probability. According to the forgery lemma [40],.Ad chooses different hi1′ andhvi′ and generates another valid authentication request message δi1′,δi2′,Ui,PIDi,PR,Li,Ti in polynomial time. At this time, the two authentication request messages satisfy the following:(8)δi1P=Ui+hi1Px,(9)δi1′P=Ui+hi1′Px,(10)δi2P=hi2Ri+hi2hviPpub+Li,(11)δi2′P=hi2Ri+hi2hvi′Ppub+Li.
From (8)–(11), we can obtain(12)δi1−δi1′P=hi1−hi1′Px,(13)δi2−δi2′P=hi2hvi−hi2hvi′Ppub.
Now, according to (12) and (13), Ad outputsx=δi1−δi1′hi1−hi2′−1, and s=δi2−δi2′hi2hvi−hi2hvi′−1.However, solving x or s is an ECDLP problem. Furthermore, it is impossible for an adversary to solve the ECDLP problem in polynomial time.Lemma 2.
The authentication response message cannot be forged. Since ECDLP is difficult to solve, our scheme can resist the forgery attack of adaptive chosen message.Proof.
We assume that there is an attacker Ad who can successfully forge an authentication response message in polynomial time. Given an ECDLP instanceP,Q=xP,P,Q∈G,x∈Zq∗, then the challenger Ch can solve the ECDLP with nonnegligible probability. The challenger Ch sets system parameters paras =  Epa,b,p,q,G,P,Ppub,Px,h0,h1,h2,h3,h4,h5. Ch builds and maintains six lists: Lhl, where l=0,1,2,…,5. Finally, Ch sends params to Ad.
h1-Oracle. When Ad makes a query with θ, Ch checks whether the tuple θ,τh1 is already in Lh1 or not. If it is, Ch sends τh1 to Ad. Otherwise, Ch randomly selects τh1∈Zq∗ and adds θ,τh1 to Lh1. Finally, Ch sends τh1=h1θ to Ad.
h2-Oracle. When Ad makes a query with IDj,RIDi,ujUi,Ti, Ch checks whether the tuple IDj,RIDi,ujUi,Ti,τh2 is already in Lh2 or not. If it is, Ch sends τh2 to Ad. Otherwise, Ch randomly selects τh2∈Zq∗ and adds IDj,RIDi,ujUi,Ti,τh2 to hh22. Finally, Ch sends τh2=h2IDj,RIDi,ujUi,Ti to Ad.
Extract (IDj). Ch builds and maintains the list LR=IDj,Rj,sj. When Ad makes a query with IDj, Ch checks whether the tuple IDj,Rj,sj is in LR. If it is, Ch sends sjto Ad. Otherwise, Ch randomly selectssj,hrj∈Zq∗, lets Rj=sjP−hrjPpub, and adds IDj,Rj,sjto LR. Finally, Ch sends LR=IDj,Rj,sj to Ad.
Sign-Oracle. When Ad makes a query with (PIDi,Ti), Ch randomly chooses sk,hrj,hj,δj∈Zq∗and setsUj=δjP−hjRj−hjhrjPpub . Finally, Ch sends δj,Uj,PIDi,IDj,Rj to Ad.
Output. Finally, Ad outputs an authentication request message δj,Uj,PIDi,IDj,Rj with nonnegligible probability. According to the forgery lemma [40].Ad chooses different hrj′ and generates another valid authentication request message δj′,Uj,PIDi,IDj,Rj in polynomial time. Now, the two authentication request messages satisfy the following:(14)δjP=hjRj+hjhrjPpub+Uj,(15)δj′P=hjRj+hjhrj′Ppub+Uj.
From (14) and (15), we can deduce the following expression:(16)δj−δj′P=hjhrj−hrj′Ppub.
Next, Ch can outputs=δj−δj′hjhrj−hrj′−1modq. However, solving s is an ECDLP, which is impossible for an adversary to solve in polynomial time.Theorem 1.
From Lemma1 and Lemma 2, we know that when the ECDLP problem is difficult to solve, and the adversary cannot forge the authentication request message and response message, that is, our authentication scheme can resist adaptive chosen message forgery attack.Theorem 2.
The message signature cannot be forged. Since ECDLP is hard to solve, our scheme can resist the forgery attack of adaptive chosen message attack.Proof.
We assume that there is an attacker Ad who can successfully forge an authentication response message in polynomial time. Given an ECDLP instanceP,Q=xP,P,Q∈G,x∈Zq∗, the challenger Ch can solve the ECDLP in polynomial time ε.
The challenger Ch sets system parameters paras =Epa,b,p,q,G,P,Ppub,Px,h0,h1,h2,h3,h4,h5. Ch randomly chooses IDj as the identity of the challenger Ch. Ch builds and maintains six lists: Lhl, where l=0,1,2,…,5. Then, Ad adaptively queries the oracle machine to Ch, and Ch replies to Ad in the following way.
When Ad makes a query withPIDi,Mi,Tm, Ch randomly chooses hrv,hmi,σi∈Zq∗, and Vi,Pv∈G; furthermore, it sets Rvi=hrv−1σiP−hrvPpub−hmiPx. Finally, Ch sends σi,Mi,Vi,Pv,Rvi,Tm to Ad.
Subsequently, Ad outputs a valid signatureσi,Mi,Vi,Pv,Rvi,Tm with a nonnegligible probability. According to the forgery lemma [40], Ad chooses different hmi′ and generates another valid signature σi′,Mi,Vi,Pv,Rvi,Tm in polynomial time. At this time, the two signatures satisfy the following relationships:(17)σiP=hrvRvi+hrvPpub+hmiPx,(18)σi′P=hrvRvi+hrvPpub+hmi′Px.
From (17) and (18), we can obtain the following equation:(19)σi−σi′P=h−mihmi′Px.
Now, according to (19), Ch can output x=σi−σi′hmi−hmi′−1modq. However, solving for x is an ECDLP problem, which is impossible for an adversary to solve in polynomial time. Thus, our proposed signature scheme under the random oracle model is resistant against a chosen adaptive message attack.Theorem 3.
The key agreement of our scheme is secure under the ECCDH problem.Proof.
Given an ECCDH instance,Q1=x1P,Q2=x2P, and Q3=x1x2P, where x1,x2∈Zq∗. In our key agreement, we let Q1⟵Ui=uiP, Q2⟵Uj=ujP,Q3⟵uiujP. In this method, if the attacker Ad gets uiujP according to Ui,Uj, the key negotiated between the vehicle and RSU can be obtained. However, it is impossible for the adversary to solve the ECCDH problem in polynomial time, implying that the key agreement proposed in this study is secure.Theorem 4.
In the random oracle model, we can achieve conditional anonymity and traceability.Proof.
In the proposed scheme, the authentication request message uses the pseudonymPIDi=RIDi⊕h1liPj, where Li=liP, li∈Zq∗. According to ECDLP, it is not feasible for the adversary to solve liPj without knowing li. The request authentication signatures areδi1=ui+hi1x and δi2=hi2si+li, where hi1=h2IDj,PIDi,Ui,Ti, hi2=h3IDj,PIDi,PR,Li,Ti, and ui,li∈zq∗ are the random numbers. Every time a vehicle is certified, it can produce unrelated pseudonyms and different authentication requests. Similarly, the pseudonym is also used in message signature PIDi=RIDi⊕hviPj, Vi=viP. The message signature is σi,Mi,Vi,Pv,Rvi,Tm, σi=hrvhvi−1si+vi+hmix, hrv=h2Mi,PIDi,Rvi,Tm, and hmi=h5Mi,PIDi,Pv,Vi,Rvi,Tm. The pseudonym used in the signature is different every time. Therefore, the scheme can provide anonymity for vehicle users in authentication and message signature. In addition, this scheme can also realize the traceability of the real identity; RSU can calculate the real identity of the vehicle RIDi=PIDi⊕h1sjLi through the private key. Similarly, through pseudonym of signature message PIDi=RIDi⊕hviPj, RSU can also calculate RIDi=PIDi⊕h1sjVi using the private key. Therefore, this scheme can realize the traceability of identity.Theorem 5.
In the proposed scheme, we can achieve unlinkability.Proof.
In our scheme, the authentication request message of the vehicleδi1,δi2,Ui,PIDi,PR,Li,Ti is different for each session. Meanwhile, the signature message σi,Mi,PIDi,Vi,Pv,Rvi,Tm is also different for each message. Therefore, all elements from the message of the vehicle are different, and any attacker cannot tell apart if two different messages from the same vehicle. Thus, our proposed scheme supports unlinkability.


## 4.2. Other Security Analysis and Feature Comparison

From Theorem1 and Theorem 2, it is ascertained that under the random oracle model, the authentication, key agreement, and message signature can resist adaptive chosen message forgery attacks. Additionally, there is no need for the certification table or TA to participate in the certification between vehicle and RSU. Both authentication and message signature use timestamp, which can resist replay attack. In the authentication process, RSU first checks whether the group key signature is legal, and then, it verifies the vehicle private key signature. If the group key signature is illegal, the signature is discarded directly, which can resist DoS attack to a certain extent. In this scheme, the vehicle is equipped with a TPD, which stores the private key of the vehicle and the group key. Even if a single TPD is attacked, the attacker can only intercept the group key and the private key of the vehicle. The authentication, key agreement, and message signature all need the private key of the vehicle. Thus, the attacker can only forge the signature of a single vehicle, without affecting the communication security of other VANET nodes. The schemes [13, 24] keep the system key in the TPD of each vehicle; this requires a strong TPD security assumption. If a single TPD is successfully attacked, the whole system will not be secure. Table 2 provides the features comparison with other schemes. It can be seen from Table 2 that the proposed scheme has strong advantages in security and communication efficiency.Table 2
Features comparison.
FeatureLIAPNECPPAWu et al.Our schemeUsing bilinear paring operationYesYesNoNoUsing ideal TPDYesYesNoNoRequiring TA to participate in certificationYesYesYesNoSearching databaseYesYesYesNo


## 5. Performance Analysis

In this section, we analyze the computation cost and communication cost of message authentication.


### 5.1. Computation Performance Analysis

In this study, nonsingular elliptic curve cryptography is used, whereas bilinear pairing construction scheme is utilized in works [13, 24]. To compare at the same security level, we construct two 80 bit security level cryptographic operation schemes. Bilinear pairing cryptographic schemes are set as follows: e:G1×G1⟶G2. E¯:y2=x3+ax+bmodp¯ is a hyper singular curve with degree 2, where p¯ is a 512 bit prime. G1is an additive group based on E¯ with order q¯ and P¯ is the generator of G1 with order q¯. The elliptic curve cryptography of the same security level is set as follows: E:y2=x3+ax+bmodp is a nonsuper singular elliptic curve, where p and q are 160 bit primes, a,b∈Zp∗. G is an additive group on E. P is the generator of G with order q. Let Tbp,Tbm,andTba denote the execution time of bilinear pairing operation, scalar multiplication operation, and scalar addition operation, respectively. Tem and Tea denote the execution time of scalar multiplication and scalar addition on elliptic curve cryptography, and TH denotes the hash operation time of map-to-point. We use MIRACL cryptographic library, an i5-7200U processor with 2.5 GHz clock frequency and 8 GB memory in our experiment. The operating system is Windows 10. Table 3 provides the average execution time of cryptographic operations.Table 3
Execution time of cryptographic operations.
Execution timeValue (ms)Tbp7.142Tbm1.445Tba0.041Tem0.821Tea0.006TH2.228Next, we analyze the computation cost of the message signature and verification with the protocols given in Table4. Message signature of LIAP [13] requires five bilinear scalar multiplication operations, one bilinear scalar addition operation, and one map-to-point operation; signature verification requires three bilinear pair operations, one bilinear scalar multiplication operation, and one map-to-point operation. Similarly, we can calculate the computation cost of message signature and signature verification for NECPPA [24], Wu et al.’ scheme [6], and our scheme. As given in Table 4, the message signature cost of the vehicle is 2.475 ms in our scheme. Compared with LIAP and NECPPA, the message signature computation cost of our scheme is reduced by 74% and 87%, respectively. However, compared with Wu et al., it costs 1.65 ms more. Compared with LIAP and NECPPA, the cost of signature verification is reduced by 69% and 87%, and it is equal to Wu et al.‘s scheme.Table 4
Computation cost of signature and verification of single message for various schemes.
SchemesMessage signature (ms)Signature verification (ms)LIAP5Tbm + 1Tba + 1TH ≈ 9.4943Tbp + 1 Tbm + 1TH ≈ 25.099NECPPA4Tbm + 1Tba + 1TH ≈ 8.0493Tbp + 1 Tbm + TH ≈ 25.099Wu et al.1Tem ≈ 0.8214Tem + 2Tea ≈ 3.296Our scheme3Tem + 2Tea ≈ 2.4754Tem + 2Tea ≈ 3.296Figure3 presents the comparisons of these computational costs graphically.Figure 3
Comparison of computation costs.


### 5.2. Communication Overhead

It can be seen from the analysis in the previous section thatp¯ is 64 bytes, G1 is 128 bytes, and p is 20 bytes, G is 40 bytes. Suppose the timestamp is 4 bytes, the hash function value is 20 bytes, and the other nongroup elements have a value of 20 bytes. The signature message of the proposed method is σi,Mi,PIDi,Vi,Pv,Rvi,Tm, and the communication length is 20 + 20 + 20 + 40 + 40 + 40 + 4 = 184 bytes. The signature message of LIAP is PIDi,Ms,PKRi,σi, and the communication length is 128 + 20 + 20 + 128 + 128 = 424 bytes. The signature message of NECPPA is PIDi,δi,Mi,IDRSUj, and the communication length is 128 + 20 + 128 + 20 + 20 = 316 bytes. The signature message of Wu et al.’ scheme is mi,PIDvi,Ti,Tvi,hki,Ri,δi, and the communication length is 20 + 40 + 4 + 4 + 20 + 40 + 20 = 148 bytes. Compared with LIAP and NECPPA, the proposed scheme can save 57% and 42% of the communication cost, respectively. Compared with Wu et al.’ scheme, the communication length is slightly increased by 40 bytes. However, in the scheme proposed by Wu et al., RSU needs to store t pairs of the pseudonyms and local private keys PIDvi,kvi [6] for each vehicle. When there are too many vehicles, it will cause a heavy burden on the memory of RSU. Similarly, each TPD also needs additional 60t bytes of storage space. The communication cost of message signature is provided in Table 5.Table 5
Communication cost of message signature in each scheme.
SchemesMessage signatureCommunication overhead (bytes)LIAPPIDi,Ms,PKRi,σi424NECPPAPIDi,δi,Mi,IDRSUj316Wu et al.mi,PIDvi,Ti,Tvi,hki,Ri,δi148Our schemeσi,Mi,PIDi,Vi,Pv,Rvi,Tm184Figure4 presents the comparisons graphically.Figure 4
Comparison of communication overhead.


### 5.3. Comparison with Other Authentication Protocols

Wei et al.’ protocols [37] use cosine similarity to realize the authentication for the intelligent and the authentication server. They have less computation cost and better accuracy compared with other implicit authentication schemes. The optimized computation complexity of two protocols is 3O(n2.3) and 3O(n2.3) + 2Encp + Decp, respectively, where n is the dimension of the multimodal behavior feature vector, and Encp and Decp are Pailler operations; our scheme is based on elliptic curve. Elliptic curve can achieve high security in 160-bit finite field. The complex operation used in our scheme is scalar multiplication operation. The complexity of scalar multiplication operation can be optimized to O (k), where k is the length of the coefficient, which is 160-bit in our scheme. In the process of mutual authentication between the vehicle and RSU, there are 15 scalar multiplication operations, and the computation complexity is 15O (160). It can be seen from the above analysis that when n is small, the work [37] has an advantage in computation cost, and when n is large, our scheme is better. In addition, in Wei et al.’ protocols, the identity of the vehicle Ui is the same in different sessions, so they do not consider the unlinkability of sessions. In our scheme, we use different pseudonyms to realize unlinkability of the sessions.Vinoth et at.’ scheme [38] is a lightweight authentication and key agreement scheme, which is better than our scheme in terms of computation cost, communication cost, and storage cost. However, the scheme does not consider the internal attack. If one sensing device is attacked, the symmetric key KEYGWN-Ui and the session key SK can be obtained by the attacker. The attacker can monitor the communication between the user and the gateway node as well as between the user and other sensing devices. In our scheme, the vehicle is equipped with TPD, which stores the private key of the vehicle and the group key. Even if a single TPD is attacked, the attacker can only intercept the group key and the private key of the vehicle. The authentication, key agreement, and message signature all need the private key of the vehicle. Thus, the attacker can only forge the signature of a single vehicle, without affecting the communication security of other VANET nodes.


## 5.1. Computation Performance Analysis

In this study, nonsingular elliptic curve cryptography is used, whereas bilinear pairing construction scheme is utilized in works [13, 24]. To compare at the same security level, we construct two 80 bit security level cryptographic operation schemes. Bilinear pairing cryptographic schemes are set as follows: e:G1×G1⟶G2. E¯:y2=x3+ax+bmodp¯ is a hyper singular curve with degree 2, where p¯ is a 512 bit prime. G1is an additive group based on E¯ with order q¯ and P¯ is the generator of G1 with order q¯. The elliptic curve cryptography of the same security level is set as follows: E:y2=x3+ax+bmodp is a nonsuper singular elliptic curve, where p and q are 160 bit primes, a,b∈Zp∗. G is an additive group on E. P is the generator of G with order q. Let Tbp,Tbm,andTba denote the execution time of bilinear pairing operation, scalar multiplication operation, and scalar addition operation, respectively. Tem and Tea denote the execution time of scalar multiplication and scalar addition on elliptic curve cryptography, and TH denotes the hash operation time of map-to-point. We use MIRACL cryptographic library, an i5-7200U processor with 2.5 GHz clock frequency and 8 GB memory in our experiment. The operating system is Windows 10. Table 3 provides the average execution time of cryptographic operations.Table 3
Execution time of cryptographic operations.
Execution timeValue (ms)Tbp7.142Tbm1.445Tba0.041Tem0.821Tea0.006TH2.228Next, we analyze the computation cost of the message signature and verification with the protocols given in Table4. Message signature of LIAP [13] requires five bilinear scalar multiplication operations, one bilinear scalar addition operation, and one map-to-point operation; signature verification requires three bilinear pair operations, one bilinear scalar multiplication operation, and one map-to-point operation. Similarly, we can calculate the computation cost of message signature and signature verification for NECPPA [24], Wu et al.’ scheme [6], and our scheme. As given in Table 4, the message signature cost of the vehicle is 2.475 ms in our scheme. Compared with LIAP and NECPPA, the message signature computation cost of our scheme is reduced by 74% and 87%, respectively. However, compared with Wu et al., it costs 1.65 ms more. Compared with LIAP and NECPPA, the cost of signature verification is reduced by 69% and 87%, and it is equal to Wu et al.‘s scheme.Table 4
Computation cost of signature and verification of single message for various schemes.
SchemesMessage signature (ms)Signature verification (ms)LIAP5Tbm + 1Tba + 1TH ≈ 9.4943Tbp + 1 Tbm + 1TH ≈ 25.099NECPPA4Tbm + 1Tba + 1TH ≈ 8.0493Tbp + 1 Tbm + TH ≈ 25.099Wu et al.1Tem ≈ 0.8214Tem + 2Tea ≈ 3.296Our scheme3Tem + 2Tea ≈ 2.4754Tem + 2Tea ≈ 3.296Figure3 presents the comparisons of these computational costs graphically.Figure 3
Comparison of computation costs.


## 5.2. Communication Overhead

It can be seen from the analysis in the previous section thatp¯ is 64 bytes, G1 is 128 bytes, and p is 20 bytes, G is 40 bytes. Suppose the timestamp is 4 bytes, the hash function value is 20 bytes, and the other nongroup elements have a value of 20 bytes. The signature message of the proposed method is σi,Mi,PIDi,Vi,Pv,Rvi,Tm, and the communication length is 20 + 20 + 20 + 40 + 40 + 40 + 4 = 184 bytes. The signature message of LIAP is PIDi,Ms,PKRi,σi, and the communication length is 128 + 20 + 20 + 128 + 128 = 424 bytes. The signature message of NECPPA is PIDi,δi,Mi,IDRSUj, and the communication length is 128 + 20 + 128 + 20 + 20 = 316 bytes. The signature message of Wu et al.’ scheme is mi,PIDvi,Ti,Tvi,hki,Ri,δi, and the communication length is 20 + 40 + 4 + 4 + 20 + 40 + 20 = 148 bytes. Compared with LIAP and NECPPA, the proposed scheme can save 57% and 42% of the communication cost, respectively. Compared with Wu et al.’ scheme, the communication length is slightly increased by 40 bytes. However, in the scheme proposed by Wu et al., RSU needs to store t pairs of the pseudonyms and local private keys PIDvi,kvi [6] for each vehicle. When there are too many vehicles, it will cause a heavy burden on the memory of RSU. Similarly, each TPD also needs additional 60t bytes of storage space. The communication cost of message signature is provided in Table 5.Table 5
Communication cost of message signature in each scheme.
SchemesMessage signatureCommunication overhead (bytes)LIAPPIDi,Ms,PKRi,σi424NECPPAPIDi,δi,Mi,IDRSUj316Wu et al.mi,PIDvi,Ti,Tvi,hki,Ri,δi148Our schemeσi,Mi,PIDi,Vi,Pv,Rvi,Tm184Figure4 presents the comparisons graphically.Figure 4
Comparison of communication overhead.


## 5.3. Comparison with Other Authentication Protocols

Wei et al.’ protocols [37] use cosine similarity to realize the authentication for the intelligent and the authentication server. They have less computation cost and better accuracy compared with other implicit authentication schemes. The optimized computation complexity of two protocols is 3O(n2.3) and 3O(n2.3) + 2Encp + Decp, respectively, where n is the dimension of the multimodal behavior feature vector, and Encp and Decp are Pailler operations; our scheme is based on elliptic curve. Elliptic curve can achieve high security in 160-bit finite field. The complex operation used in our scheme is scalar multiplication operation. The complexity of scalar multiplication operation can be optimized to O (k), where k is the length of the coefficient, which is 160-bit in our scheme. In the process of mutual authentication between the vehicle and RSU, there are 15 scalar multiplication operations, and the computation complexity is 15O (160). It can be seen from the above analysis that when n is small, the work [37] has an advantage in computation cost, and when n is large, our scheme is better. In addition, in Wei et al.’ protocols, the identity of the vehicle Ui is the same in different sessions, so they do not consider the unlinkability of sessions. In our scheme, we use different pseudonyms to realize unlinkability of the sessions.Vinoth et at.’ scheme [38] is a lightweight authentication and key agreement scheme, which is better than our scheme in terms of computation cost, communication cost, and storage cost. However, the scheme does not consider the internal attack. If one sensing device is attacked, the symmetric key KEYGWN-Ui and the session key SK can be obtained by the attacker. The attacker can monitor the communication between the user and the gateway node as well as between the user and other sensing devices. In our scheme, the vehicle is equipped with TPD, which stores the private key of the vehicle and the group key. Even if a single TPD is attacked, the attacker can only intercept the group key and the private key of the vehicle. The authentication, key agreement, and message signature all need the private key of the vehicle. Thus, the attacker can only forge the signature of a single vehicle, without affecting the communication security of other VANET nodes.


## 6. Conclusion

The instantaneous characteristic of VANET communication requires high efficiency in authentication and key agreement. Therefore, this study proposes an efficient anonymous authentication and key agreement scheme. The scheme includes mutual authentication and key agreement between vehicle and RSU, as well as signature and verification of the vehicle message. In the proposed scheme, an elliptic curve is used to improve the efficiency of computation and communication. Our authentication and key agreement scheme does not need to communicate with the third party authority or establish a local database, and furthermore, it avoids database query operation. It can effectively save the communication time and storage space of related nodes and is more suitable for VANET. Compared with other schemes, this scheme also has strong computing and communication advantages in message authentication. However, we do not address key negotiation and authentication between vehicles and vehicles. Lightweight and effective encryption methods to achieve anonymous authentication and communication between vehicles and vehicles is a worthy research direction. The implementation of anonymous authentication and key agreement based on channel condition is also one of the directions worthy of discussion [41, 42].In this study, the authentication technology combined with cryptography is mainly presented. At present, deep learning and cloud computing are increasingly used in network applications. In the next step, more technologies such as deep learning [43, 44] and cloud computing can be combined into authentication and privacy protection of VANET.



---

*Source: 5526412-2021-05-04.xml*