# An Authentication and Key Agreement Scheme Based on Roadside Unit Cache for VANET

Authors: Sun Mei; Guo Yuyan; Zhang Juan; Jiang Mingming
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Vehicular Ad Hoc Network (VANET) is a wireless Mobile Ad Hoc Network that is used for communication between vehicles, vehicles and fixed access points, and vehicles and pedestrians. However, because of the use of open wireless channels, VANET is more vulnerable. Therefore, VANET security is critical for safe driving and user privacy protection. Authentication and key agreement are crucial for ensuring security. Numerous authentication schemes have been proposed between vehicles and roadside units (RSUs). Many solutions are authentication and key negotiation between the vehicle and a single RSU. The vehicle passing through a region needs to complete authentication and key agreement with multiple RSUs separately, which brings a great burden to the vehicle. In order to simplify the authentication process of vehicles and multiple RSUs and improve the efficiency of authentication and key agreement, an efficient authentication and key agreement scheme based on RSU cache is proposed when the vehicle moves from one RSU to another RSU region. In the proposed scheme, RSUs are divided into regions, and each region has a RSU cluster head. When the vehicle enters a certain region and authenticates with a RSU successfully, the RSU submits the authentication information to the RSU cluster head. The RSU cluster head shares the authentication information with other RSUs in the region using the shared key. Other RSUs record the authentication information in the cache. When the vehicle communicates with other RSUs, the authentication is not necessary; the session key can be negotiated by simply exchanging information. After using the cache, the calculation and communication cost of the authentication and key negotiation between the vehicle and other RSU can be significantly saved, the calculation cost is reduced by 37%, and the traffic is reduced by 35%. The random oracle model is used to prove the security of the scheme. The results revealed that the authentication overhead of the proposed scheme is considerably lower than those of other schemes. Compared with the related schemes, the computational cost of the proposed scheme is reduced by 34% on average; the communication cost is close to other related schemes. Moreover, the security analysis shows that the proposed scheme provides better security compared to other related schemes.


---

## Body

## 1. Introduction

VANETs can be used to obtain timely report road condition information, query road condition information, plan travel routes, improve travel efficiency, and reduce road congestion and traffic accidents. VANETs can facilitate traffic optimization and safe transportation. VANET security is critical because security messages contain life-critical information. Using open wireless modules, VANETs are vulnerable to various types of attacks. These attacks may not only affect the use of network communication and network services but also pose a threat to people’s lives and property. The main components of VANET are roadside units (RSUs), a trust agency (TA), onboard units (OBUs), and application servers (ASs) [1]. The TA is responsible for system initialization and providing system parameters, including the private-public key pair; RSUs are placed on both sides of the road to function as vehicle routers or Internet access points; OBU is a microwave device which is installed on the vehicle to realize vehicle-to-RSU or vehicle-to-vehicle communication. Data storage and various application services of VANET are realized by ASs. IEEE802.11p is a short range communication protocol (DSRC) [2] to achieve vehicle-to-RSU and vehicle-to-vehicle communication.


### 1.1. Related Works

To address the security problems, such as message integrity and privacy protection of VANET, authentication and key agreement have been introduced into VANET. Some logic operations and hash functions are generally used in lightweight protocols to complete authentication and key agreement. Computation is considerably lower than those of the bilinear pairing and elliptic-curve-based authentication schemes. Wazid et al. [3] designed a lightweight no-center service authentication and key negotiation protocol for VANET in which similar vehicles are aggregated into a cluster to realize authentication types, such as vehicle-to-vehicle, vehicle-to-cluster head, and cluster head-to-RSU communication. However, all vehicles and RSUs prestore the same keys x and x′, which cannot provide satisfactory defense against internal node attacks. Vijayakumar et al. [4] proposed a lightweight authentication and group key agreement protocol using a symmetric cryptosystem. The scheme is used to realize the authentication of a vehicle and RSUs through the shared key between the vehicle and TA and the shared key between RSU and TA. After successful authentication, the vehicle signs the message using the authentication code encrypted by group and TA private keys. This scheme involves limited calculation and exhibits high authentication efficiency. However, TA needs to query the key list of all vehicles or RSUs during the authentication. Zhong et al. [5] proposed an authentication and key negotiation scheme based on hash function and registration list. In this scheme, the vehicle and TA, RSU and TA have shared keys, and the authentication and key negotiation between the vehicle and RSU are completed through TA. The computational overhead of this scheme is considerably lower than other schemes. Although this scheme requires TPD support, strong security assumptions are not required. Islam et al. [1] proposed a lightweight authentication scheme combining passwords with group keys. Paliwal et al. [6] proposed a lightweight vehicle-to-RSU authentication scheme based on dynamic password; however “publicidentifierOBU” is unchanged in the authentication process. Cui et al. [2] proposed a scheme based on hash function and group key negotiation, which exhibits high computational efficiency. Zhang and Wen [7] also proposed a lightweight authentication and key negotiation scheme based on XOR and hash functions. Schemes based on [1, 2, 6, 7] require TA to participate in the authentication, and they cannot satisfy the unlinkability of authentication in VANET. Li et al. [8] proposed a lightweight authentication and key agreement protocol based on hash function and XOR operation. However, the authentication between vehicle and RSU should be completed through TA, which requires TAs to continuously generate pseudonyms for vehicles. A study [9] revealed that the scheme proposed by Li et al. cannot resist RSU counterfeiting attacks. And, the anonymity and untraceability of vehicles are not guaranteed. Alfadhli et al. [10] proposed a lightweight vehicle and RSU authentication scheme using general hash function. However, “CRi” [10] of the vehicle remains unchanged during every authentication in the scheme. Therefore, the vehicle is easy to be tracked. Lee et al. [11] proposed a lightweight authentication and key agreement protocol for cloud computing of Internet of vehicles. However, the HIDi [11] of the vehicle remains unchanged during the authentication process, and the vehicle can be easily tracked. In [12], a lightweight VANET authentication and key agreement scheme was proposed. In the scheme, the CA is distributed in multiple regions, and the shared key in one region is obtained through vehicle and CA authentication. However, the authentication between vehicle and RSU is not considered. In a study [13], an authentication protocol for hiding path information from TA was proposed. After successful authentication, the vehicle obtains the keys from TA. The keys are shared between the vehicle and multi-RSU. In this scheme, the path information of the vehicle is hidden by the matrix transformation to protect the vehicle privacy. However, the calculation cost of the scheme is large. Lightweight authentication and key agreement schemes for VANET exhibit excellent computing performance. However, the centralized authentication of TA or CA is required, which is not suitable for large-scale VANETs. Such schemes cannot satisfy high security requirements. Recently, researchers have proposed schemes using public key cryptosystems for VANET authentication and key agreement. Li et al. [14] proposed an authentication and key agreement scheme between vehicles using the private key. In this scheme, bilinear pairing operation is not required. It has high protocol efficiency. However, the scheme cannot satisfy the authentication anonymity of VANETs because the vehicle identification is directly transmitted. In [15, 16], V2V authentication and key agreement schemes based on identity are proposed. The session key is obtained from the vehicles through the private key. However, the communication unlinkability of VANETs is not considered in these schemes. Bayat et al. [17] proposed a public key authentication scheme based on RSU to realize the authentication and key negotiation between the vehicle and RSU. In the scheme, the system key is preinstalled in the TPD of the RSU, the vehicle encrypts and transmits the real name to the RSU using the system public key, and the RSU decrypts the real name of the vehicle using the system key. After verifying that the real name is legal, multiple private keys and shared keys are generated by the RSU for the vehicle. However, in this scheme, bilinear pair operation is required, and considerable authentication calculation is involved. Alazzawi et al. [18] proposed an authentication and key agreement scheme between the vehicle and RSUs. TA prestores the system key in the TPD of RSU. After the vehicle is successfully authenticated, the system key is used in RSAs to generate the private key “sk” for the vehicle. When the vehicle communicates with other RSUs, only “sk” needs to be updated without further authentication. The scheme is implemented using an elliptic curve without bilinear pair operation, and the computational performance is considerably improved. However, system key “s” can be calculated from the key “sk” in the OBU; if the system key “s” is leaked, the scheme security is compromised. Currently, the authentication and key agreement of V2I in VANETs mainly solve the authentication and key agreement from vehicle to RSU. When the vehicle passes through each RSU, numerous authentications and key negotiations are required. TA can perform limited authentications, which can easily result in authentication bottlenecks. To improve V2I authentication efficiency, Xie et al. [19] proposed an authentication and key agreement scheme for VANETs with multiserver architectures. In the scheme, a server cluster is constructed on VANETs, and information is shared between servers. One-time server authentication is required, and the session key is negotiated after successful authentication. Although this scheme has high authentication efficiency, strong TPD security assumptions are required. In [20], an authentication and key agreement protocol was proposed for VANET roaming. In the protocol, there are local and foreign areas, and the tow proxy servers are set in both areas, respectively. The vehicle and the local agent as well as the local agent and the foreign agent are preinstalled with shared keys. When a vehicle enters a foreign area, authentication information is transmitted to the local agent through the foreign agent for authentication. The authentication is completed using the local agent. The proposed protocol is insecure against a MITM attack, impersonation attack, and KCI attack [21]. Centralized authentication and key agreement through cloud server are realized in a few schemes [19, 20]. However, when the server is far from the vehicle and many instantaneous vehicles are present, authentication delay may occur. To address this challenge, Ma et al. [22] proposed an authentication and key agreement scheme for VANET based on fog computing, in which some network services are dispersed to the fog server of the network edge. In the scheme, the authentication between vehicle and fog server is completed using cloud computing servers. However, communication between vehicles and RSUs is not considered.At present, many scholars have proposed some other new authentication and key agreement schemes for VANET. Li et al. [23] proposed a VANET authentication key agreement scheme combined with blockchain, which meets the requirements of anticollusion attack and unlinkability of VANET. In [24], a many-to-many authentication and key negotiation scheme between vehicles and cloud servers is proposed. Zhang et al. [25] proposed a drone-assisted authentication and key agreement scheme between vehicle and control center. In [26], a cache-based access control scheme for vehicle and cloud services based on SDN is proposed.The RSU is closest to the vehicle, and it can provide timely and fast services to the vehicle. However, the authentication and communication of vehicles and RSUs are not considered in much literature. In many proposed authentication and key agreement schemes between vehicles and RSUs, the authentication and key agreement between the vehicle and a single RSU are only considered; the vehicle passing through a region needs to complete authentication and key negotiation with multiple RSUs separately, which brings a great burden to the vehicle, which considerably increases communication and computing burden. In this study, an efficient authentication and key agreement scheme between vehicle and multiple RSUs based on RSU cache is proposed when the vehicle moves from one RSU to another RSU region. RSUs are divided into numerous regions. Each region has a cluster head. The cluster head has high security and can be completed by the sub-TA. The cluster head forms a group with RSUs in the region. When a vehicle enters an area, authentication and negotiation can be performed with any RSU. After successful authentication, part of the authentication information is shared among RSUs in the area through the cluster head. Each RSU sets the security cache to store the authentication information between the vehicle and the RSU, and the authentication information has the survival time. In the survival time, authentication is not required when the vehicle moves from one RSU to another RSU region. The vehicle can negotiate session keys directly with other RSUs. This solution not only solves the problem of repeated authentication and key agreement between vehicles and RSUs but also avoids the problem that vehicles can only authenticate with cloud services.


### 1.2. Our Contributions

In this study, a temporary cache method was constructed to optimize the authentication scheme of vehicles and RSUs. After using the cache, the calculation and communication cost of the authentication and key negotiation between the vehicle and other RSU can be significantly saved, the calculation cost is reduced by 37%, and the traffic is reduced by 35%. In terms of security performance, this scheme does not require strong security support of TPD, and querying the database during authentication and key agreement is not required.The main contributions of this study are as follows.(1)
We simplify the authentication and key negotiation process between vehicles and multiple RSUs by establishing a group for RSUs and sharing authentication information securely within the group.(2)
In negotiation, the efficiency of key agreement is improved by using secure cache in RSU.(3)
The vehicle and RSU authenticate anonymously through their private keys. We avoid saving the system key in the TPD of RSUs and vehicles. In this study, the strong security of the TPD is not required to support the storage of the system key.(4)
Dual-system keyss1 and s2 are used in this study. Different keys are used in different occasions. If a single key is cracked, the security of other occasions will not be affected and the overall security of the system will be enhanced.


## 1.1. Related Works

To address the security problems, such as message integrity and privacy protection of VANET, authentication and key agreement have been introduced into VANET. Some logic operations and hash functions are generally used in lightweight protocols to complete authentication and key agreement. Computation is considerably lower than those of the bilinear pairing and elliptic-curve-based authentication schemes. Wazid et al. [3] designed a lightweight no-center service authentication and key negotiation protocol for VANET in which similar vehicles are aggregated into a cluster to realize authentication types, such as vehicle-to-vehicle, vehicle-to-cluster head, and cluster head-to-RSU communication. However, all vehicles and RSUs prestore the same keys x and x′, which cannot provide satisfactory defense against internal node attacks. Vijayakumar et al. [4] proposed a lightweight authentication and group key agreement protocol using a symmetric cryptosystem. The scheme is used to realize the authentication of a vehicle and RSUs through the shared key between the vehicle and TA and the shared key between RSU and TA. After successful authentication, the vehicle signs the message using the authentication code encrypted by group and TA private keys. This scheme involves limited calculation and exhibits high authentication efficiency. However, TA needs to query the key list of all vehicles or RSUs during the authentication. Zhong et al. [5] proposed an authentication and key negotiation scheme based on hash function and registration list. In this scheme, the vehicle and TA, RSU and TA have shared keys, and the authentication and key negotiation between the vehicle and RSU are completed through TA. The computational overhead of this scheme is considerably lower than other schemes. Although this scheme requires TPD support, strong security assumptions are not required. Islam et al. [1] proposed a lightweight authentication scheme combining passwords with group keys. Paliwal et al. [6] proposed a lightweight vehicle-to-RSU authentication scheme based on dynamic password; however “publicidentifierOBU” is unchanged in the authentication process. Cui et al. [2] proposed a scheme based on hash function and group key negotiation, which exhibits high computational efficiency. Zhang and Wen [7] also proposed a lightweight authentication and key negotiation scheme based on XOR and hash functions. Schemes based on [1, 2, 6, 7] require TA to participate in the authentication, and they cannot satisfy the unlinkability of authentication in VANET. Li et al. [8] proposed a lightweight authentication and key agreement protocol based on hash function and XOR operation. However, the authentication between vehicle and RSU should be completed through TA, which requires TAs to continuously generate pseudonyms for vehicles. A study [9] revealed that the scheme proposed by Li et al. cannot resist RSU counterfeiting attacks. And, the anonymity and untraceability of vehicles are not guaranteed. Alfadhli et al. [10] proposed a lightweight vehicle and RSU authentication scheme using general hash function. However, “CRi” [10] of the vehicle remains unchanged during every authentication in the scheme. Therefore, the vehicle is easy to be tracked. Lee et al. [11] proposed a lightweight authentication and key agreement protocol for cloud computing of Internet of vehicles. However, the HIDi [11] of the vehicle remains unchanged during the authentication process, and the vehicle can be easily tracked. In [12], a lightweight VANET authentication and key agreement scheme was proposed. In the scheme, the CA is distributed in multiple regions, and the shared key in one region is obtained through vehicle and CA authentication. However, the authentication between vehicle and RSU is not considered. In a study [13], an authentication protocol for hiding path information from TA was proposed. After successful authentication, the vehicle obtains the keys from TA. The keys are shared between the vehicle and multi-RSU. In this scheme, the path information of the vehicle is hidden by the matrix transformation to protect the vehicle privacy. However, the calculation cost of the scheme is large. Lightweight authentication and key agreement schemes for VANET exhibit excellent computing performance. However, the centralized authentication of TA or CA is required, which is not suitable for large-scale VANETs. Such schemes cannot satisfy high security requirements. Recently, researchers have proposed schemes using public key cryptosystems for VANET authentication and key agreement. Li et al. [14] proposed an authentication and key agreement scheme between vehicles using the private key. In this scheme, bilinear pairing operation is not required. It has high protocol efficiency. However, the scheme cannot satisfy the authentication anonymity of VANETs because the vehicle identification is directly transmitted. In [15, 16], V2V authentication and key agreement schemes based on identity are proposed. The session key is obtained from the vehicles through the private key. However, the communication unlinkability of VANETs is not considered in these schemes. Bayat et al. [17] proposed a public key authentication scheme based on RSU to realize the authentication and key negotiation between the vehicle and RSU. In the scheme, the system key is preinstalled in the TPD of the RSU, the vehicle encrypts and transmits the real name to the RSU using the system public key, and the RSU decrypts the real name of the vehicle using the system key. After verifying that the real name is legal, multiple private keys and shared keys are generated by the RSU for the vehicle. However, in this scheme, bilinear pair operation is required, and considerable authentication calculation is involved. Alazzawi et al. [18] proposed an authentication and key agreement scheme between the vehicle and RSUs. TA prestores the system key in the TPD of RSU. After the vehicle is successfully authenticated, the system key is used in RSAs to generate the private key “sk” for the vehicle. When the vehicle communicates with other RSUs, only “sk” needs to be updated without further authentication. The scheme is implemented using an elliptic curve without bilinear pair operation, and the computational performance is considerably improved. However, system key “s” can be calculated from the key “sk” in the OBU; if the system key “s” is leaked, the scheme security is compromised. Currently, the authentication and key agreement of V2I in VANETs mainly solve the authentication and key agreement from vehicle to RSU. When the vehicle passes through each RSU, numerous authentications and key negotiations are required. TA can perform limited authentications, which can easily result in authentication bottlenecks. To improve V2I authentication efficiency, Xie et al. [19] proposed an authentication and key agreement scheme for VANETs with multiserver architectures. In the scheme, a server cluster is constructed on VANETs, and information is shared between servers. One-time server authentication is required, and the session key is negotiated after successful authentication. Although this scheme has high authentication efficiency, strong TPD security assumptions are required. In [20], an authentication and key agreement protocol was proposed for VANET roaming. In the protocol, there are local and foreign areas, and the tow proxy servers are set in both areas, respectively. The vehicle and the local agent as well as the local agent and the foreign agent are preinstalled with shared keys. When a vehicle enters a foreign area, authentication information is transmitted to the local agent through the foreign agent for authentication. The authentication is completed using the local agent. The proposed protocol is insecure against a MITM attack, impersonation attack, and KCI attack [21]. Centralized authentication and key agreement through cloud server are realized in a few schemes [19, 20]. However, when the server is far from the vehicle and many instantaneous vehicles are present, authentication delay may occur. To address this challenge, Ma et al. [22] proposed an authentication and key agreement scheme for VANET based on fog computing, in which some network services are dispersed to the fog server of the network edge. In the scheme, the authentication between vehicle and fog server is completed using cloud computing servers. However, communication between vehicles and RSUs is not considered.At present, many scholars have proposed some other new authentication and key agreement schemes for VANET. Li et al. [23] proposed a VANET authentication key agreement scheme combined with blockchain, which meets the requirements of anticollusion attack and unlinkability of VANET. In [24], a many-to-many authentication and key negotiation scheme between vehicles and cloud servers is proposed. Zhang et al. [25] proposed a drone-assisted authentication and key agreement scheme between vehicle and control center. In [26], a cache-based access control scheme for vehicle and cloud services based on SDN is proposed.The RSU is closest to the vehicle, and it can provide timely and fast services to the vehicle. However, the authentication and communication of vehicles and RSUs are not considered in much literature. In many proposed authentication and key agreement schemes between vehicles and RSUs, the authentication and key agreement between the vehicle and a single RSU are only considered; the vehicle passing through a region needs to complete authentication and key negotiation with multiple RSUs separately, which brings a great burden to the vehicle, which considerably increases communication and computing burden. In this study, an efficient authentication and key agreement scheme between vehicle and multiple RSUs based on RSU cache is proposed when the vehicle moves from one RSU to another RSU region. RSUs are divided into numerous regions. Each region has a cluster head. The cluster head has high security and can be completed by the sub-TA. The cluster head forms a group with RSUs in the region. When a vehicle enters an area, authentication and negotiation can be performed with any RSU. After successful authentication, part of the authentication information is shared among RSUs in the area through the cluster head. Each RSU sets the security cache to store the authentication information between the vehicle and the RSU, and the authentication information has the survival time. In the survival time, authentication is not required when the vehicle moves from one RSU to another RSU region. The vehicle can negotiate session keys directly with other RSUs. This solution not only solves the problem of repeated authentication and key agreement between vehicles and RSUs but also avoids the problem that vehicles can only authenticate with cloud services.


## 1.2. Our Contributions

In this study, a temporary cache method was constructed to optimize the authentication scheme of vehicles and RSUs. After using the cache, the calculation and communication cost of the authentication and key negotiation between the vehicle and other RSU can be significantly saved, the calculation cost is reduced by 37%, and the traffic is reduced by 35%. In terms of security performance, this scheme does not require strong security support of TPD, and querying the database during authentication and key agreement is not required.The main contributions of this study are as follows.(1)
We simplify the authentication and key negotiation process between vehicles and multiple RSUs by establishing a group for RSUs and sharing authentication information securely within the group.(2)
In negotiation, the efficiency of key agreement is improved by using secure cache in RSU.(3)
The vehicle and RSU authenticate anonymously through their private keys. We avoid saving the system key in the TPD of RSUs and vehicles. In this study, the strong security of the TPD is not required to support the storage of the system key.(4)
Dual-system keyss1 and s2 are used in this study. Different keys are used in different occasions. If a single key is cracked, the security of other occasions will not be affected and the overall security of the system will be enhanced.


## 2. Background Knowledge

### 2.1. Elliptic Curve

LetFp represent a finite field of order p and E be an elliptic curve E:y2=x3+ax+bmodp. Let G be a finite cyclic group with order q on E, and P be the generator, and O be an infinite point.G has the following properties:(1)
Addition (±).P,Q are two points on G; if P≠Q, R=P+Q, then R is the intersection of the straight line passing through P and Q; if P=Q, R=P+Q, then R is the tangent intersection of E and P,Q; if P=−Q, then P+Q=P−P=O.(2)
Scalar multiplication (.). Letm∈Zq∗; then the scalar multiplication of P is m.P=P+P+⋯P (m times in total).Two difficult problems are defined as follows:Define 1 elliptic curve discrete logarithm problem (ECDLP); letQ be a random point on G; the ECDLP problem is to calculate x satisfying Q=xP, where x∈Zq∗.Define 2 elliptic curve calculation Diffie-Hellman problem (ECCDH), forP,aP,bP∈G, where a,b∈Zq∗ are unknown. The ECCDH problem is to calculate abP.If ECDLP or ECCDH on groupG cannot be solved with nonnegligible probability in time t, ECDLP or ECCDH is difficult problem on the elliptic curve.


### 2.2. Network Model

In the network model in this study, as shown in Figure1, TA is a trusted service center with strong security. RSUs are installed on both sides of the road to provide access services for vehicles. Each vehicle is equipped with an OBU to communicate with RSUs or other vehicles. OBUs communicate wirelessly with RSUs through DSRC protocol. TA establishes system parameters, and it is the registration of RSUs and vehicles and generates private-public key pairs for RSUs and vehicles; TA establishes clusters for RSUs and specifies a cluster head for each cluster. The security of the cluster head is higher than that of other RSUs. RSUs in the cluster form a communication group. When the vehicle releases messages to the VANET or receives various services provided by the VANET, the vehicle and RSU first complete authentication and key negotiation.Figure 1
VANET network model.


## 2.1. Elliptic Curve

LetFp represent a finite field of order p and E be an elliptic curve E:y2=x3+ax+bmodp. Let G be a finite cyclic group with order q on E, and P be the generator, and O be an infinite point.G has the following properties:(1)
Addition (±).P,Q are two points on G; if P≠Q, R=P+Q, then R is the intersection of the straight line passing through P and Q; if P=Q, R=P+Q, then R is the tangent intersection of E and P,Q; if P=−Q, then P+Q=P−P=O.(2)
Scalar multiplication (.). Letm∈Zq∗; then the scalar multiplication of P is m.P=P+P+⋯P (m times in total).Two difficult problems are defined as follows:Define 1 elliptic curve discrete logarithm problem (ECDLP); letQ be a random point on G; the ECDLP problem is to calculate x satisfying Q=xP, where x∈Zq∗.Define 2 elliptic curve calculation Diffie-Hellman problem (ECCDH), forP,aP,bP∈G, where a,b∈Zq∗ are unknown. The ECCDH problem is to calculate abP.If ECDLP or ECCDH on groupG cannot be solved with nonnegligible probability in time t, ECDLP or ECCDH is difficult problem on the elliptic curve.


## 2.2. Network Model

In the network model in this study, as shown in Figure1, TA is a trusted service center with strong security. RSUs are installed on both sides of the road to provide access services for vehicles. Each vehicle is equipped with an OBU to communicate with RSUs or other vehicles. OBUs communicate wirelessly with RSUs through DSRC protocol. TA establishes system parameters, and it is the registration of RSUs and vehicles and generates private-public key pairs for RSUs and vehicles; TA establishes clusters for RSUs and specifies a cluster head for each cluster. The security of the cluster head is higher than that of other RSUs. RSUs in the cluster form a communication group. When the vehicle releases messages to the VANET or receives various services provided by the VANET, the vehicle and RSU first complete authentication and key negotiation.Figure 1
VANET network model.


## 3. Proposed Scheme

The scheme includes system initialization, RSU and vehicle registration, RSU group establishment, vehicle and RSU authentication and key negotiation, and vehicle and other RSU key negotiations. The main notations used are shown as Table1.Table 1
The notations used.
NotationDescriptionEElliptic curveGA finite cyclic group with orderq on ETAgThe cluster heads1,s2,Ppub1,Ppub2System private and public keysh0,h1,h2,h3,h4,h5,h6Hash functionsgThe group keyIDgGroup identificationsj,PjThe private key and public key of RSUsm,PmThe private key and public key of other RSUsi,PiThe private key and public key of the vehicleIDi,IDjThe vehicle identification and RSU identificationRIDi,PIDiReal identity and pseudonym of the vehicleTs1,Ts2,Ts3TimestampskgjThe session key between the cluster head and RSUskrvThe session key between RSU and the vehicleskimThe session key between the vehicle and other RSUrj,ri,rm,uj,ug,vj,vi,vm,ziThe random numbers


### 3.1. System Initialization

In TA, two random numberss1,s2 are selected as the system keys, and system public keys Ppub1=s1P,Ppub2=s2P∈G are computed, and TA selects seven secure hash functions: h0:0,1∗×G⟶Zq∗, h1:0,1∗×0,1∗×G×0,1∗×0,1∗⟶Zq∗, h2:0,1∗×G×0,1∗⟶Zq∗, h3:0,1∗×0,1∗×G×0,1∗⟶Zq∗, h4:0,1∗×0,1∗×G×G×0,1∗⟶Zq∗, h5:0,1∗×0,1∗×G⟶Zq∗, h6:G×G×0,1∗⟶Zq∗. TA divides RSUs into an RSU group and assigns a cluster head to each group. The cluster head has strong security. TA assigns TPD to each cluster head and preinstalls the system key s2, the group key g, group identification IDg, and system parameters in the TPD of the cluster head.


### 3.2. Registration

The roadside unitRSUj performs offline authentication with TA. After TA successfully reviews RSUj, it is divided into corresponding groups according to the area, which is designated as IDg, and the group key is g; furthermore, TA assigns a TPD to RSUj. TA assigns identity IDj to RSUj, selects a random number rj, computes Rj=rjP, calculates the private key sj=s1h0IDj,Rj+rj for RSUj, where the public key of RSUj is Pj=h0IDj,RjPpub1+Rj, and saves sj,g,Pj,Rj,IDj,IDg, including the system parameters in the TPD of RSUj. The cluster head can obtain the private key sg and public key Pg through registration.The vehicleVei applies to TA for registration and TA reviews the identity, license, and other information of the vehicle. If the vehicle satisfies the requirements, TA assigns a TPD to the vehicle, selects a random number ri, computes Ri=riP, calculates the private key si=s1h0RIDi,Ri+ri for Vei, where the public key of Vei is Pi=h0RIDi,RiPpub1+Ri, saves si,RIDi,Ri,Pi, and system parameters in the TPD of Vei, and saves the real identity RIDi, the public key Pi, and other registration information of the vehicle in the application database (AS).


### 3.3. Establishing the RSU Group

In the cluster headTAg of the group where RSUj is located, n mutually prime numbers k1,k2,k3⋯kn are selected, Mu=∑j=1nkj, Muj=Mu/kj are calculated, and bj is obtained so that bj satisfies bjMuj≡1modkj to compute γ=∑j=1nbjMuj.TAg negotiates the session key with RSUj.RSUj selects a random number uj and computes σj=sjh1IDj,g,Uj,IDg,Ts1+uj, Uj=ujP where Ts1 is the current timestamp. RSUj sends σj,IDj,Rj,Uj,Ts1 to the cluster TAg. After receiving the message, TAg verifies whether equation (1) is true. If the equation is true, a random number ug is selected, TAg computes skgj=h1IDj,g,ugUj,IDg,Ts1, σg=sgh2IDg,Ug,skgj+ug, Ug=ugP, and sends σg,Ug to RSUj.TAg obtains the session key skgj=h1IDj,g,ugUj,IDg,Ts1.(1)σjP=h0IDj,Rjh1IDj,g,Uj,IDg,Ts1Ppub1+h1IDj,g,Uj,IDg,Ts1Rj+Uj.The proof of equation (1):(2)σjP=sjh1IDj,g,Uj,IDg,Ts1P+ujP=s1h0IDj,Rj+rjh1IDj,g,Uj,IDg,Ts1P+ujP=h0IDj,Rjh1IDj,g,Uj,IDg,Ts1Ppub1+h1IDj,g,Uj,IDg,Ts1Rj+Uj.AfterRSUj receives σg,Ug, skgj=h1IDj,g,ujUg,IDg,Ts1 is calculated to verify whether equation (3) is true, if so. RSUj gets the session key skgj.(3)σgP=h0IDg,Rgh2IDg,Ug,skgjPpub1+h2IDg,Ug,skgjRg+Ug.The proof of equation (3):(4)σgP=sgh2IDg,Ug,skgj+ugP=sgh2IDg,Ug,skgjP+ugP=s1h0IDg,Rg+rgh2IDg,Ug,skgjP+Ug=h0IDg,Rgh2IDg,Ug,skgjPpub1+h2IDg,Ug,skgjRg+Ug.TAg encrypts kj with the session key skgj and sends Eskgjkj to RSUj. RSUj decrypts Eskgjkj with the session key skgj to obtain kj.


### 3.4. Authentication and Session Key Negotiation between Vehicle and RSU

RSUj selects a random number vj and calculates μj=sjh3IDj,IDg,Vj,Ts2+vj, Vj=vjP. RSUj broadcasts message μj,Pj,IDj,IDg,Rj,Vj,Ts2 in the coverage area, where Ts2 indicates the current timestamp.After the vehicleVei receives the message, it checks whether the time stamp of RSUjTs2 has expired; if not, it verifies whether the following equation holds.(5)μjP=h0IDj,Rjh3IDj,IDg,Vj,Ts2Ppub1+h3IDj,IDg,Vj,Ts2Rj+Vj.The proof of equation (5):(6)μjP=sjh3IDj,IDg,Vj,Ts2+vjP=sjh3IDj,IDg,Vj,Ts2P+vjP=s1h0IDj,Rj+rjh3IDj,IDg,Vj,Ts2P+Vj=h0IDj,Rjh3IDj,IDg,Vj,Ts2Ppub1+h3IDj,IDg,Vj,Ts2Rj+Vj.If true, the vehicleVei selects a random number vi, calculates pseudonym PIDi=RIDi⊕h0Ts2,viPpub2, calculates Vi=viP, skrv=h3IDj,PIDi,viVj,Ts2, PR=Ri+viPpub2, μi=h4IDj,PIDi,Vi,PR,skrvsi+vi, and sends PIDi,PR,Vi,μi,Ts2 to RSUj.AfterRSUj receives the message, it checks whether timestamp Ts2 has expired. If it has not expired, RSUj sends EskgjPIDi,PR,Vi,Ts2 to TAg, where Eskgj represents a function for symmetric encryption using the shared key skgj of TAg and RSUj.AfterTAg receives the message, it checks whether timestamp Ts2 has expired. If not, the following calculation is performed: RIDi=PIDi⊕h0Ts2,viPpub2, Ri=PR−s2Vi, Pi=h0RIDi,RiPpub1+Ri, then EskgjPi,Ts2 is sent to RSUj, RSUj decrypts EskgjPi,Ts2 to obtain Pi,Ts2, and RSUj calculates skrv=h3IDj,PIDi,vjVi,Ts2 and verifies whether equation (7) holds.(7)μiP=h4IDj,PIDi,Vi,PR,skrvPi+Vi.If equation (7) holds, RSUj sends EskgjPIDi,Ts2 to TAg.The proof of equation (7):(8)μiP=h4IDj,PIDi,Vi,PR,skrvsi+viP=h4IDj,PIDi,Vi,PR,skrvsiP+Vi=h4IDj,PIDi,Vi,PR,skrvPi+Vi.After receiving the message,TAg selects a random number wc and calculates wcγ, and TAg broadcasts wcγ, Ewch5RIDi,Ts2,Pi,Ts2,Pi in the RSU group. Another RSU node RSUi uses ki to calculate wc=wcγmodki. Furthermore, RSUi decrypts Ewch5RIDi,Ts2,Pi,Ts2,Pi with wc to obtain h5RIDi,Ts2,Pi,Ts2,Pi and records it in RSUi cache. RSU cache is shown as Table 2.Table 2
RSU cache.
Part certification information of vehiclesExpiration timeh5RIDi1,Ts2,Pi1,Ts2,Pi1Tex1h5RIDi2,Ts2,Pi2,Ts2,Pi2Tex2……h5RIDim,Ts2,Pim,Ts2,PimTexmThe vehicleVei obtains the shared key skrv=h3IDj,PIDi,viVj,Ts2 and records IDg,Ts2,IDj in secure cache.RSUj obtains the shared key skrv=h3IDj,PIDi,vjVi,Ts2 with Vei.The authentication and key negotiation between the vehicle and RSU are shown in Figure2.Figure 2
Authentication and session key negotiation process between vehicleVei and RSUj.


### 3.5. Key Negotiation between Vehicle and Other RSUs

When the vehicleVei reaches the region of RSUm (1 ≤ m ≤ n), RSUm broadcasts signature information and public key information μm,Pm,IDm,IDg,Rm,Vm,Ts3 in this region, where μm=smh3IDm,IDg,Vm,Ts3+vm, Vm=vmP, vm is the random number selected by RSUm, IDm is the unique identity of RSUm, IDg is the group ID of RSUm, and Pm,Rm is the public key of RSUm.AfterVei receives the message, it checks whether timestamp Ts3 has expired. If not, it checks whether records of IDg are present in the cache; if not, it is authenticated according to the process in Section 3.4. If yes, it indicates that the vehicle has been authenticated and key negotiated in this area; the vehicle verifies whether equation (9) is true. If so, Vei selects a random number zi and calculates PIDi=h5RIDi,Ts2,Pi⊕h6ziPm,Vm,Ts3, Zi=ziP. Then, Vei sends PIDi,IDm,Zi,Ts3 to RSUm.(9)Pm=h0IDm,RmPpub1+Rm.AfterRSUm receives the message, it calculates h5RIDi,Ts2,Pi=PIDi⊕h6smZi,Vm,Ts3; RSUm looks up whether a value is equal to h5RIDi,Ts2,Pi in the cache. If so, RSUm calculates skim=h4PIDi,IDm,smZi,vmPi,Ts3, λm=h6vmPi,Vm,skim, and RSUm sends PIDi,λm,Ts3 to Vei. After receiving the message, the vehicle calculates skim=h4PIDi,IDm,ziPm,siVm,Ts3 and verifies whether the equation λm=h6siVm,Vm,skim is true. If so, the vehicle Vei obtains the shared key skim=h4PIDi,IDm,ziPm,siVm,Ts3.RSUm obtains the shared key kim=h4PIDi,IDm,smZi,vmPi,Ts3.The key negotiation between the vehicle and other RSUs is shown in Figure3.Figure 3
Session key negotiation process between vehicleVei and other RSUm.


## 3.1. System Initialization

In TA, two random numberss1,s2 are selected as the system keys, and system public keys Ppub1=s1P,Ppub2=s2P∈G are computed, and TA selects seven secure hash functions: h0:0,1∗×G⟶Zq∗, h1:0,1∗×0,1∗×G×0,1∗×0,1∗⟶Zq∗, h2:0,1∗×G×0,1∗⟶Zq∗, h3:0,1∗×0,1∗×G×0,1∗⟶Zq∗, h4:0,1∗×0,1∗×G×G×0,1∗⟶Zq∗, h5:0,1∗×0,1∗×G⟶Zq∗, h6:G×G×0,1∗⟶Zq∗. TA divides RSUs into an RSU group and assigns a cluster head to each group. The cluster head has strong security. TA assigns TPD to each cluster head and preinstalls the system key s2, the group key g, group identification IDg, and system parameters in the TPD of the cluster head.


## 3.2. Registration

The roadside unitRSUj performs offline authentication with TA. After TA successfully reviews RSUj, it is divided into corresponding groups according to the area, which is designated as IDg, and the group key is g; furthermore, TA assigns a TPD to RSUj. TA assigns identity IDj to RSUj, selects a random number rj, computes Rj=rjP, calculates the private key sj=s1h0IDj,Rj+rj for RSUj, where the public key of RSUj is Pj=h0IDj,RjPpub1+Rj, and saves sj,g,Pj,Rj,IDj,IDg, including the system parameters in the TPD of RSUj. The cluster head can obtain the private key sg and public key Pg through registration.The vehicleVei applies to TA for registration and TA reviews the identity, license, and other information of the vehicle. If the vehicle satisfies the requirements, TA assigns a TPD to the vehicle, selects a random number ri, computes Ri=riP, calculates the private key si=s1h0RIDi,Ri+ri for Vei, where the public key of Vei is Pi=h0RIDi,RiPpub1+Ri, saves si,RIDi,Ri,Pi, and system parameters in the TPD of Vei, and saves the real identity RIDi, the public key Pi, and other registration information of the vehicle in the application database (AS).


## 3.3. Establishing the RSU Group

In the cluster headTAg of the group where RSUj is located, n mutually prime numbers k1,k2,k3⋯kn are selected, Mu=∑j=1nkj, Muj=Mu/kj are calculated, and bj is obtained so that bj satisfies bjMuj≡1modkj to compute γ=∑j=1nbjMuj.TAg negotiates the session key with RSUj.RSUj selects a random number uj and computes σj=sjh1IDj,g,Uj,IDg,Ts1+uj, Uj=ujP where Ts1 is the current timestamp. RSUj sends σj,IDj,Rj,Uj,Ts1 to the cluster TAg. After receiving the message, TAg verifies whether equation (1) is true. If the equation is true, a random number ug is selected, TAg computes skgj=h1IDj,g,ugUj,IDg,Ts1, σg=sgh2IDg,Ug,skgj+ug, Ug=ugP, and sends σg,Ug to RSUj.TAg obtains the session key skgj=h1IDj,g,ugUj,IDg,Ts1.(1)σjP=h0IDj,Rjh1IDj,g,Uj,IDg,Ts1Ppub1+h1IDj,g,Uj,IDg,Ts1Rj+Uj.The proof of equation (1):(2)σjP=sjh1IDj,g,Uj,IDg,Ts1P+ujP=s1h0IDj,Rj+rjh1IDj,g,Uj,IDg,Ts1P+ujP=h0IDj,Rjh1IDj,g,Uj,IDg,Ts1Ppub1+h1IDj,g,Uj,IDg,Ts1Rj+Uj.AfterRSUj receives σg,Ug, skgj=h1IDj,g,ujUg,IDg,Ts1 is calculated to verify whether equation (3) is true, if so. RSUj gets the session key skgj.(3)σgP=h0IDg,Rgh2IDg,Ug,skgjPpub1+h2IDg,Ug,skgjRg+Ug.The proof of equation (3):(4)σgP=sgh2IDg,Ug,skgj+ugP=sgh2IDg,Ug,skgjP+ugP=s1h0IDg,Rg+rgh2IDg,Ug,skgjP+Ug=h0IDg,Rgh2IDg,Ug,skgjPpub1+h2IDg,Ug,skgjRg+Ug.TAg encrypts kj with the session key skgj and sends Eskgjkj to RSUj. RSUj decrypts Eskgjkj with the session key skgj to obtain kj.


## 3.4. Authentication and Session Key Negotiation between Vehicle and RSU

RSUj selects a random number vj and calculates μj=sjh3IDj,IDg,Vj,Ts2+vj, Vj=vjP. RSUj broadcasts message μj,Pj,IDj,IDg,Rj,Vj,Ts2 in the coverage area, where Ts2 indicates the current timestamp.After the vehicleVei receives the message, it checks whether the time stamp of RSUjTs2 has expired; if not, it verifies whether the following equation holds.(5)μjP=h0IDj,Rjh3IDj,IDg,Vj,Ts2Ppub1+h3IDj,IDg,Vj,Ts2Rj+Vj.The proof of equation (5):(6)μjP=sjh3IDj,IDg,Vj,Ts2+vjP=sjh3IDj,IDg,Vj,Ts2P+vjP=s1h0IDj,Rj+rjh3IDj,IDg,Vj,Ts2P+Vj=h0IDj,Rjh3IDj,IDg,Vj,Ts2Ppub1+h3IDj,IDg,Vj,Ts2Rj+Vj.If true, the vehicleVei selects a random number vi, calculates pseudonym PIDi=RIDi⊕h0Ts2,viPpub2, calculates Vi=viP, skrv=h3IDj,PIDi,viVj,Ts2, PR=Ri+viPpub2, μi=h4IDj,PIDi,Vi,PR,skrvsi+vi, and sends PIDi,PR,Vi,μi,Ts2 to RSUj.AfterRSUj receives the message, it checks whether timestamp Ts2 has expired. If it has not expired, RSUj sends EskgjPIDi,PR,Vi,Ts2 to TAg, where Eskgj represents a function for symmetric encryption using the shared key skgj of TAg and RSUj.AfterTAg receives the message, it checks whether timestamp Ts2 has expired. If not, the following calculation is performed: RIDi=PIDi⊕h0Ts2,viPpub2, Ri=PR−s2Vi, Pi=h0RIDi,RiPpub1+Ri, then EskgjPi,Ts2 is sent to RSUj, RSUj decrypts EskgjPi,Ts2 to obtain Pi,Ts2, and RSUj calculates skrv=h3IDj,PIDi,vjVi,Ts2 and verifies whether equation (7) holds.(7)μiP=h4IDj,PIDi,Vi,PR,skrvPi+Vi.If equation (7) holds, RSUj sends EskgjPIDi,Ts2 to TAg.The proof of equation (7):(8)μiP=h4IDj,PIDi,Vi,PR,skrvsi+viP=h4IDj,PIDi,Vi,PR,skrvsiP+Vi=h4IDj,PIDi,Vi,PR,skrvPi+Vi.After receiving the message,TAg selects a random number wc and calculates wcγ, and TAg broadcasts wcγ, Ewch5RIDi,Ts2,Pi,Ts2,Pi in the RSU group. Another RSU node RSUi uses ki to calculate wc=wcγmodki. Furthermore, RSUi decrypts Ewch5RIDi,Ts2,Pi,Ts2,Pi with wc to obtain h5RIDi,Ts2,Pi,Ts2,Pi and records it in RSUi cache. RSU cache is shown as Table 2.Table 2
RSU cache.
Part certification information of vehiclesExpiration timeh5RIDi1,Ts2,Pi1,Ts2,Pi1Tex1h5RIDi2,Ts2,Pi2,Ts2,Pi2Tex2……h5RIDim,Ts2,Pim,Ts2,PimTexmThe vehicleVei obtains the shared key skrv=h3IDj,PIDi,viVj,Ts2 and records IDg,Ts2,IDj in secure cache.RSUj obtains the shared key skrv=h3IDj,PIDi,vjVi,Ts2 with Vei.The authentication and key negotiation between the vehicle and RSU are shown in Figure2.Figure 2
Authentication and session key negotiation process between vehicleVei and RSUj.


## 3.5. Key Negotiation between Vehicle and Other RSUs

When the vehicleVei reaches the region of RSUm (1 ≤ m ≤ n), RSUm broadcasts signature information and public key information μm,Pm,IDm,IDg,Rm,Vm,Ts3 in this region, where μm=smh3IDm,IDg,Vm,Ts3+vm, Vm=vmP, vm is the random number selected by RSUm, IDm is the unique identity of RSUm, IDg is the group ID of RSUm, and Pm,Rm is the public key of RSUm.AfterVei receives the message, it checks whether timestamp Ts3 has expired. If not, it checks whether records of IDg are present in the cache; if not, it is authenticated according to the process in Section 3.4. If yes, it indicates that the vehicle has been authenticated and key negotiated in this area; the vehicle verifies whether equation (9) is true. If so, Vei selects a random number zi and calculates PIDi=h5RIDi,Ts2,Pi⊕h6ziPm,Vm,Ts3, Zi=ziP. Then, Vei sends PIDi,IDm,Zi,Ts3 to RSUm.(9)Pm=h0IDm,RmPpub1+Rm.AfterRSUm receives the message, it calculates h5RIDi,Ts2,Pi=PIDi⊕h6smZi,Vm,Ts3; RSUm looks up whether a value is equal to h5RIDi,Ts2,Pi in the cache. If so, RSUm calculates skim=h4PIDi,IDm,smZi,vmPi,Ts3, λm=h6vmPi,Vm,skim, and RSUm sends PIDi,λm,Ts3 to Vei. After receiving the message, the vehicle calculates skim=h4PIDi,IDm,ziPm,siVm,Ts3 and verifies whether the equation λm=h6siVm,Vm,skim is true. If so, the vehicle Vei obtains the shared key skim=h4PIDi,IDm,ziPm,siVm,Ts3.RSUm obtains the shared key kim=h4PIDi,IDm,smZi,vmPi,Ts3.The key negotiation between the vehicle and other RSUs is shown in Figure3.Figure 3
Session key negotiation process between vehicleVei and other RSUm.


## 4. Proof of Safety

Lemma 1.
The message broadcasted by RSU cannot be forged. When ECDLP is a difficult problem, this scheme can resist the forgery attack of adaptive selection message.Proof.
Assume an attacker who can successfully forge the request message of a vehicle in polynomial time, given the ECDLP problem instanceP,Q=xP,P,Q∈G,x∈Zq∗. Assuming a challenger C who acts as the game challenger to solve the ECDLP problem, the ECDLP problem can be solved in polynomial time.
ChallengerC runs system initialization and initializes system parameters paras = Epa,b,p,q,G,P,Ppub1,Ppub2,h0,h1,h2,h3,h4,h5,h6; C randomly selects the identity IDj of a RSU as the identity of the challenger. Next, A adaptively queries the oracle machine from C, and C replies to the query of A as follows:(1)
hlml: when A initiates a query with ml, if it does not exist in the list, C selects a random number rl∈Zq∗, stores ml,rl in the list Lhl, and sends rl to A. Here, l=0,1,2…,6.(2)
Query RSU private key.Furthermore,C maintains the list. When A initiates the query of the oracle model, C queries list LR. When IDj is in the list, C returns the information sj in the list to A; otherwise, it selects randomly sj,h0∈Zq∗ and makes Rj=sjP−h0Ppub1. Next, IDj,Rj,sj is added to the list LR.(3)
Query the message of vehicle certification request.
WhenA queries with IDj,Ts2, C randomly selects h0,h3,μj∈Zq∗ and makes Vj=μjP−h0h3Ppub1−h3Rj. Next, C returns h0,h3,μj,Rj,Vj to A and A receives it. According to the bifurcation lemma [27], A selects different h0′ to output another valid signature h0′,h3,μj′,Rj,Vj in polynomial time. At this stage, the two signatures meet as follows:(10)μjP=h0h3Ppub1+h3Rj+Vj,(11)μj′P=h0′h3Ppub1+h3Rj+Vj.
From equations (10) and (11), we have the following:(12)μj−μj′P=h0h3−h0′h3Ppub1,where C is according to equation (12), and s1=μj−μj′h0h3−h0′h3−1 can be calculated with nonnegligible probability. However, solving s1 is an ECDLP problem. According to Definition 1, the attacker cannot solve the ECDLP problem in polynomial time.Lemma 2.
Authentication response message cannot be forged. When ECDLP is a difficult problem, this scheme can resist the forgery attack of adaptive selection message.Proof.
Assume is an attackerA who can successfully forge the request message of a vehicle in polynomial time ε. Given the ECDLP problem instance P,Q=xP,P,Q∈G,x∈Zq∗, assuming that a challenger C acts as the game challenger to solve the ECDLP problem, the ECDLP problem can be solved in polynomial time.(1)
hlml. When A initiates a query with ml, if ml does not exist in the list, C selects a random number rl∈Zq∗, stores ml,rl in the list Lhl, and sends rl to A; here, l=0,1,2…,6.(2)
Query vehicle private key.C maintains the list Lv=RIDi,Ri,si. When A initiates the query of the oracle model, C queries the list Lv=RIDi,Ri,si. When RIDi is in the list, si in the list is returned to A; otherwise, C selects randomly si,h0∈Zq∗ and makes Ri=siP−h0Ppub1. Next, it adds RIDi,Ri,si to the list Lv.(3)
Query vehicle authentication request message.WhenA queries PIDi,Ts2, C randomly selects h0,h4,μi∈Zq∗ and makes Ri=siP−h0Ppub1, Pi=h0Ppub1+Ri, Vi=μiP−h4Ri−h0h4Ppub. Then, C returns μi,Vi,PIDi to A and A receives it. According to the bifurcation lemma [27], A selects different h0′ to generate another valid signature μi′,Vi,PIDi in polynomial time. At this time, the two signatures meet as follows:(13)μiP=h4Pi+Vi=h4Ri+h0h4Ppub1+Vi,(14)μi′P=h4Pi+Vi=h4Ri+h0′h4Ppub1+Vi.
From equations (13) and (14):(15)μi−μi′P=h0h4−h0′h4Ppub1,s1=μi−μi′h0h4−h0′h4−1 can be calculated according to equation (15). However, solving s1 is an ECDLP problem. According to Definition 1, it is impossible for an enemy to solve the ECDLP problem in polynomial time.Theorem 1.
Lemmas1 and 2 reveal that when the ECDLP problem is difficult, the opponent cannot forge the authentication request message and response message. Thus, the authentication scheme can resist the adaptive selection message forgery attack.Theorem 2.
The key agreement of this scheme is to secure under the ECCDH problem.Proof.
Given an ECCDH problem instanceQ1=x1P,Q2=x2P,Q3=x1x2P, where x1,x2∈Zq∗, in the key agreement between vehicle Vei and RSUj in this paper, let Q1←Vi=viP, Q2←Vj=vjP, Q3←vivjP. If attacker A can calculate vivjP according to Vi,Vj, the attacker can obtain the key negotiated between the vehicle and RSU. According to Definition 2, the enemy cannot solve the ECCDH problem in polynomial time; that is, the key negotiation between vehicle Vei and RSUj is secure.Theorem 3.
Under the random oracle model, this scheme can realize anonymity and identity tracking.Proof.
In this scheme, the pseudonymPIDi=RIDi⊕h0Ts2,viPpub2 is used for authentication and key negotiation between vehicle Vei and RSUj; the authentication response sent is PIDi,PR,Vi,μi,Ts2, PR=Ri+viPpub2, Vi=viP, μi=h4IDj,PIDi,Vi,PR,skrvsi+vi, and skrv=h3IDj,PIDi,viVj,Ts2, where Ppub2=s2P, viPpub2=vis2P; if the attacker wants to obtain the real identity RIDi of the vehicle, vis2P should be solved according to Vi=viP and Ppub2=s2P, that is, to solve the ECCDH problem. In the authentication response sent by the vehicle, vi is a random number. The response message generated in the communication between the vehicle and RSU each time contains unrelated pseudonym and different random number. Similarly, when the vehicle negotiates with other RSUs, the pseudonym PIDi=h5RIDi,Ts2,Pi⊕h6ziPm,Vm,Ts3 is used, and the authentication response sent is PIDi,IDm,Zi,Vm,Ts3, Zi=ziP; here, zi is a random number. The attacker solves zismP according to the known Zi=ziP and Pm=smP, that is, to solve ECCDH problem. According to Definition 2, an opponent cannot solve the ECCDH problem in polynomial time. The messages generated by the vehicle each time are irrelevant pseudonyms and different random numbers. Therefore, the authentication and key agreement of this scheme can realize the anonymity of vehicles under the ECCDH problem. Furthermore, the scheme can realize the traceability of real identity. In this study, the pseudonym used for the first authentication between the vehicle and a RSU is PIDi=RIDi⊕h0viPpub2,Ts2. The cluster head in this area can calculate the real identity RIDi=PIDi⊕h0s2Vi,Ts2 of the vehicle through the system key s2. The pseudonym used for the authentication between the vehicle and other RSUs in this area is PIDi=h5RIDi,Ts2,Pi⊕h6ziPm,Vm,Ts3. If a dispute occurs, the RSU can calculate h5RIDi,Ts2,Pi=PIDi⊕h6smZi,Vm,Ts3 through the private key and sends h5RIDi,Ts2,Pi,Ts2 to TA, which can recover the real identity RIDi of the vehicle by querying the vehicle information database. Therefore, this scheme can realize identity traceability.


### 4.1. Other Safety Analyses

Theorems 1 and 2 suggest that, under the random oracle model, the authentication and key agreement in this study can resist the adaptive selection message forgery attack. Therefore, the proposed scheme can resist attacks, such as the impersonation attack, tampering attack, and man-in-the-middle attack. When the vehicle is certified with RSU for the first time, querying the certification form is not necessary. When the vehicle conducts key negotiation with other RSUs, the authentication and signature use time stamps, so the authentication and key negotiation scheme proposed herein can resist replay attacks. When the vehicle authenticates the RSU group for the first time, the private key of the vehicle and RSU is used to sign the message in the authentication. When the vehicle authenticates other RSUs, it queries the RSU cache, even if the cache is intercepted by an internal attacker. An internal attacker cannot forge a vehicle for key negotiation with RSU because calculating the session keyskim=h4PIDi,IDm,ziPm,siVm,Ts3 requires the private keys of the vehicle and the RSU. Given the public keys of the vehicle and RSU, solving the private keys of the vehicle and RSU requires solving the ECDLP problem. According to Definition 1, an opponent cannot solve the ECDLP problem in polynomial time. Therefore, the proposed authentication scheme can resist internal attacks. In this scheme, when updating the RSU cache, the cluster head uses the group key to encrypt and calculate Ewch5RIDi,Ts2,Pi,Ts2,Pi and then broadcasts in the RSU area. After receiving the key, other RSU nodes decrypt it to get h5RIDi,Ts2,Pi,Ts2,Pi and then update the local RSU cache. The group key is updated every time, which can effectively avoid other malicious nodes forging the cluster head and issuing false authentication information. Furthermore, spoofing attacks in other caches, such as ARP spoofing attacks, can be avoided.In [17], each RSU requires TPD to save the system key. When the system key is leaked, attacks such as forgery and internal impersonation attacks can occur. Therefore, TPD should ideally possess strong security. During authentication and key negotiation, RSU must extract the real identity of the vehicle using the system key according to the pseudonym of the vehicle and verify the legitimacy of the real identity of the vehicle according to the database. In [19], saving the system key in the TPD of the vehicle is necessary, and TPD should have ideal strong security. According to [20], when the vehicle and the external server agent as well as the vehicle and the local server agent authenticate and negotiate the key, the external server agent and the local server agent query the vehicle’s public key Qi using the database. In [22], the authentication and key negotiation of vehicle and fog node are realized using a cloud server. In the negotiation, both vehicle and fog node authenticate through their private keys, and TPD support is not required for authentication. In our scheme, the vehicle and RSU authenticate each other through their own private key. In this scheme, the dual-system keys s1 and s2 are used, and s1 is saved in TA with high security, it is used to calculate the private keys of vehicles and RSUs, and s2 is saved in the cluster head to help RSU calculate the public key of the vehicle. Even if s2 is cracked, the attacker can only calculate the public key of the vehicle according to s2, but the public key of the vehicle is not transmitted in plaintext during the authentication and key negotiation between the vehicle and RSU. Thus, the attacker cannot track the vehicle according to the public key or negotiate the communication key using the public key. Therefore, the vehicle does not require strong TPD security to support the system key storage. The schemes proposed in [17, 19, 22] and that proposed in this study can resist forgery, replay, and internal attacks. When the vehicle falls into a dispute, the real identity of the vehicle can be restored through TA. Table 3 lists the safety comparison of various schemes.Table 3
Safety comparison.
SchemesAnti-forgery attackTraceabilityStrong security of TPDResist replay attacksAnti-internal attackRequire database supportLiterature [17]YesYesYesYesYesYesLiterature [19]YesYesYesYesYesNoLiterature [20]NoYesNoYesYesYesLiterature [22]YesYesNoYesYesNoOur schemeYesYesNoYesYesNo


## 4.1. Other Safety Analyses

Theorems 1 and 2 suggest that, under the random oracle model, the authentication and key agreement in this study can resist the adaptive selection message forgery attack. Therefore, the proposed scheme can resist attacks, such as the impersonation attack, tampering attack, and man-in-the-middle attack. When the vehicle is certified with RSU for the first time, querying the certification form is not necessary. When the vehicle conducts key negotiation with other RSUs, the authentication and signature use time stamps, so the authentication and key negotiation scheme proposed herein can resist replay attacks. When the vehicle authenticates the RSU group for the first time, the private key of the vehicle and RSU is used to sign the message in the authentication. When the vehicle authenticates other RSUs, it queries the RSU cache, even if the cache is intercepted by an internal attacker. An internal attacker cannot forge a vehicle for key negotiation with RSU because calculating the session keyskim=h4PIDi,IDm,ziPm,siVm,Ts3 requires the private keys of the vehicle and the RSU. Given the public keys of the vehicle and RSU, solving the private keys of the vehicle and RSU requires solving the ECDLP problem. According to Definition 1, an opponent cannot solve the ECDLP problem in polynomial time. Therefore, the proposed authentication scheme can resist internal attacks. In this scheme, when updating the RSU cache, the cluster head uses the group key to encrypt and calculate Ewch5RIDi,Ts2,Pi,Ts2,Pi and then broadcasts in the RSU area. After receiving the key, other RSU nodes decrypt it to get h5RIDi,Ts2,Pi,Ts2,Pi and then update the local RSU cache. The group key is updated every time, which can effectively avoid other malicious nodes forging the cluster head and issuing false authentication information. Furthermore, spoofing attacks in other caches, such as ARP spoofing attacks, can be avoided.In [17], each RSU requires TPD to save the system key. When the system key is leaked, attacks such as forgery and internal impersonation attacks can occur. Therefore, TPD should ideally possess strong security. During authentication and key negotiation, RSU must extract the real identity of the vehicle using the system key according to the pseudonym of the vehicle and verify the legitimacy of the real identity of the vehicle according to the database. In [19], saving the system key in the TPD of the vehicle is necessary, and TPD should have ideal strong security. According to [20], when the vehicle and the external server agent as well as the vehicle and the local server agent authenticate and negotiate the key, the external server agent and the local server agent query the vehicle’s public key Qi using the database. In [22], the authentication and key negotiation of vehicle and fog node are realized using a cloud server. In the negotiation, both vehicle and fog node authenticate through their private keys, and TPD support is not required for authentication. In our scheme, the vehicle and RSU authenticate each other through their own private key. In this scheme, the dual-system keys s1 and s2 are used, and s1 is saved in TA with high security, it is used to calculate the private keys of vehicles and RSUs, and s2 is saved in the cluster head to help RSU calculate the public key of the vehicle. Even if s2 is cracked, the attacker can only calculate the public key of the vehicle according to s2, but the public key of the vehicle is not transmitted in plaintext during the authentication and key negotiation between the vehicle and RSU. Thus, the attacker cannot track the vehicle according to the public key or negotiate the communication key using the public key. Therefore, the vehicle does not require strong TPD security to support the system key storage. The schemes proposed in [17, 19, 22] and that proposed in this study can resist forgery, replay, and internal attacks. When the vehicle falls into a dispute, the real identity of the vehicle can be restored through TA. Table 3 lists the safety comparison of various schemes.Table 3
Safety comparison.
SchemesAnti-forgery attackTraceabilityStrong security of TPDResist replay attacksAnti-internal attackRequire database supportLiterature [17]YesYesYesYesYesYesLiterature [19]YesYesYesYesYesNoLiterature [20]NoYesNoYesYesYesLiterature [22]YesYesNoYesYesNoOur schemeYesYesNoYesYesNo


## 5. Performance Analysis

Two critical indicators to measure VANET authentication protocol are computing overhead and communication overhead. We mainly analyze computing overhead and communication overhead of the proposed scheme.


### 5.1. Calculation Overhead

In [19, 20, 22], nonsingular elliptic curve cryptography was used, and in [17] bilinear pair construction scheme was used. At the same security level, we constructed two cryptographic operation schemes with 80-bit security level. The bilinear pairing scheme is set as follows: e:G1×G1⟶G2. Here, the generator of the additive group G1 is P¯, the order is q¯, and P¯ is the point on the hypersingular curve E¯:y2=x3+ax+bmodp¯ with degree 2, and p¯ is a 512-bit prime. The elliptic curve cryptography with the same security level is set as follows: the nonsingular elliptic curve is E:y2=x3+ax+bmodp, G is the addition group on E, P is the generator of G, and the order of G is q, and p and q are 160 bit primes, a,b∈Zq∗. Let Tbp,Tbm,andTba represent the bilinear pairing operation, scalar multiplication operation, and scalar addition operation time of the bilinear pair, respectively, Tem and Tea represent the scalar multiplication and scalar addition operation time of elliptic curve cryptography, and TH represents the hash operation time of map to point. Let Eed represent symmetric encryption or decryption operation time. For performing the abovementioned operations on E¯,E, we use the functions defined in MIRACL cryptographic library on a 1.8-GHz machine with 8 GB memory. The running environment is Visual Studio 2012 on Windows 10. The experimental method is similar to [28]. Table 4 presents the average execution time of cryptographic operations.Table 4
Execution time of main cryptographic operations.
Execution timeValue (ms)Tbp7.272Tbm1.211Tba0.039Tem0.652Tea0.006TH2.543Eed0.004Statistical values of the main time-consuming operations used in the protocols of [17, 19, 20, 22], such as bilinear pairing operation, scalar multiplication operation, scalar addition operation, map-to-point hash operation, the scalar multiplication, and the addition operations of elliptic curve cryptography, were obtained. We ignored other operations with short time and simple calculation, such as the hash operation and logic operation. From Table 5 and Figure 4, the total calculation amount of authentication and session key negotiation for the first time in this paper is saved by 57.7%, 7.9%, 35.0%, and 34.7%, respectively, compared with the other four schemes. The scheme of this paper has certain advantages in terms of calculation.Table 5
Calculation cost of authentication and session key negotiation of various schemes.
SchemesUser (ms)RSU (ms) or proxy nodeTA or server (ms)Total (ms)Literature [17]1Tbp + 3 Tbm + 1TH + 1Eed3Tbm + 1EedNo1Tbp + 6 Tbm + 1TH + 2Eed ≈ 17.09Literature [19]7Tem + 2TeaNo5Tem + 2Tea12Tem + 4Tea ≈ 7.85Literature [20]6Tem + 2Tea7Tem + 2Tea4Tem + 2Tea17Tem + 6Tea ≈ 11.12Literature [22]3Tem4Tem10Tem17Tem ≈ 11.08Our scheme6Tem + 3Tea3Tem + 1Tea + 3Eed2Tem + 2Tea + 3Eed11Tem + 6Tea + 6Eed ≈ 7.23Figure 4
Comparison of calculation cost.Vehicle and RSU group authentication obtained for the first time is given by11Tem+6Tea+6Eed≈7.23ms. After using the cache, the vehicle and other RSU authentications and key negotiations can be given by 7Tem+1Tea≈4.57ms, which is reduced by 37%.


### 5.2. Communication Overhead

According to the analysis in the previous section,p¯ is 64 bytes and G1 is 128 bytes, and p is 20 bytes, so G is 40 bytes. We assume that the timestamp is 4 bytes, the hash function value is 20 bytes, and the other nongroup element is 20 bytes. Let |G1| represent the length of the element in the group G1, let |G| represent the length of the group G element, let Zq∗ represent the length of the nongroup element, and let |T| represent the length of the timestamp.According to the communication comparison in Table6, the communication volume of this scheme before using RSU cache is 32 bytes more than that in [17], 236 bytes more than that in [19], 124 bytes more than that in [20], and 220 bytes less than that in [22]. Table 6 reveals that the traffic volume of this paper slightly increased compared with [17, 20] and decreased compared with [22].Table 6
Comparison of communication overhead.
SchemesUser (byte)RSU (byte) or proxy nodeTA or server (byte)Total (byte)Literature [17]1|G1| + 1| Zq∗|2|G1| + 2| Zq∗| + |T|3|G1| + 3|Zq∗| + |T| = 448Literature [19]2|G| + 3|Zq∗| + |T||G| + 3|Zq∗|3|G| + 6|Zq∗| + |T| = 244Literature [20]1|G| + 3| Zq∗| + |T|3|G| + 5| Zq∗| + 2|T||Zq∗| + |T|4|G| + 9|Zq∗| + 4|T| = 356Literature [22]1|G| + 4|Zq∗| + |T|6|G| + 6| Zq∗| + 3|T|3|G| + 4|Zq∗| + |T|10|G| + 14|Zq∗| + 5|T| = 700Our scheme2|G| + 2|Zq∗| + |T|5|G| + 5|Zq∗| + 3|T|1|G| + |T|8|G| + 7|Zq∗| + 5|T| = 480Before using the RSU cache, authentication and key negotiation require five interactions, but after using the RSU cache, three interactions are required. The authentication does not require the participation of cluster heads. Before using cache, the traffic is 8|G| + 7|Zq∗| + 5|T| = 480 bytes, while after using cache, it is 4|G| + 7|Zq∗| + 3|T| = 312 bytes, and the traffic is reduced by 35%.


## 5.1. Calculation Overhead

In [19, 20, 22], nonsingular elliptic curve cryptography was used, and in [17] bilinear pair construction scheme was used. At the same security level, we constructed two cryptographic operation schemes with 80-bit security level. The bilinear pairing scheme is set as follows: e:G1×G1⟶G2. Here, the generator of the additive group G1 is P¯, the order is q¯, and P¯ is the point on the hypersingular curve E¯:y2=x3+ax+bmodp¯ with degree 2, and p¯ is a 512-bit prime. The elliptic curve cryptography with the same security level is set as follows: the nonsingular elliptic curve is E:y2=x3+ax+bmodp, G is the addition group on E, P is the generator of G, and the order of G is q, and p and q are 160 bit primes, a,b∈Zq∗. Let Tbp,Tbm,andTba represent the bilinear pairing operation, scalar multiplication operation, and scalar addition operation time of the bilinear pair, respectively, Tem and Tea represent the scalar multiplication and scalar addition operation time of elliptic curve cryptography, and TH represents the hash operation time of map to point. Let Eed represent symmetric encryption or decryption operation time. For performing the abovementioned operations on E¯,E, we use the functions defined in MIRACL cryptographic library on a 1.8-GHz machine with 8 GB memory. The running environment is Visual Studio 2012 on Windows 10. The experimental method is similar to [28]. Table 4 presents the average execution time of cryptographic operations.Table 4
Execution time of main cryptographic operations.
Execution timeValue (ms)Tbp7.272Tbm1.211Tba0.039Tem0.652Tea0.006TH2.543Eed0.004Statistical values of the main time-consuming operations used in the protocols of [17, 19, 20, 22], such as bilinear pairing operation, scalar multiplication operation, scalar addition operation, map-to-point hash operation, the scalar multiplication, and the addition operations of elliptic curve cryptography, were obtained. We ignored other operations with short time and simple calculation, such as the hash operation and logic operation. From Table 5 and Figure 4, the total calculation amount of authentication and session key negotiation for the first time in this paper is saved by 57.7%, 7.9%, 35.0%, and 34.7%, respectively, compared with the other four schemes. The scheme of this paper has certain advantages in terms of calculation.Table 5
Calculation cost of authentication and session key negotiation of various schemes.
SchemesUser (ms)RSU (ms) or proxy nodeTA or server (ms)Total (ms)Literature [17]1Tbp + 3 Tbm + 1TH + 1Eed3Tbm + 1EedNo1Tbp + 6 Tbm + 1TH + 2Eed ≈ 17.09Literature [19]7Tem + 2TeaNo5Tem + 2Tea12Tem + 4Tea ≈ 7.85Literature [20]6Tem + 2Tea7Tem + 2Tea4Tem + 2Tea17Tem + 6Tea ≈ 11.12Literature [22]3Tem4Tem10Tem17Tem ≈ 11.08Our scheme6Tem + 3Tea3Tem + 1Tea + 3Eed2Tem + 2Tea + 3Eed11Tem + 6Tea + 6Eed ≈ 7.23Figure 4
Comparison of calculation cost.Vehicle and RSU group authentication obtained for the first time is given by11Tem+6Tea+6Eed≈7.23ms. After using the cache, the vehicle and other RSU authentications and key negotiations can be given by 7Tem+1Tea≈4.57ms, which is reduced by 37%.


## 5.2. Communication Overhead

According to the analysis in the previous section,p¯ is 64 bytes and G1 is 128 bytes, and p is 20 bytes, so G is 40 bytes. We assume that the timestamp is 4 bytes, the hash function value is 20 bytes, and the other nongroup element is 20 bytes. Let |G1| represent the length of the element in the group G1, let |G| represent the length of the group G element, let Zq∗ represent the length of the nongroup element, and let |T| represent the length of the timestamp.According to the communication comparison in Table6, the communication volume of this scheme before using RSU cache is 32 bytes more than that in [17], 236 bytes more than that in [19], 124 bytes more than that in [20], and 220 bytes less than that in [22]. Table 6 reveals that the traffic volume of this paper slightly increased compared with [17, 20] and decreased compared with [22].Table 6
Comparison of communication overhead.
SchemesUser (byte)RSU (byte) or proxy nodeTA or server (byte)Total (byte)Literature [17]1|G1| + 1| Zq∗|2|G1| + 2| Zq∗| + |T|3|G1| + 3|Zq∗| + |T| = 448Literature [19]2|G| + 3|Zq∗| + |T||G| + 3|Zq∗|3|G| + 6|Zq∗| + |T| = 244Literature [20]1|G| + 3| Zq∗| + |T|3|G| + 5| Zq∗| + 2|T||Zq∗| + |T|4|G| + 9|Zq∗| + 4|T| = 356Literature [22]1|G| + 4|Zq∗| + |T|6|G| + 6| Zq∗| + 3|T|3|G| + 4|Zq∗| + |T|10|G| + 14|Zq∗| + 5|T| = 700Our scheme2|G| + 2|Zq∗| + |T|5|G| + 5|Zq∗| + 3|T|1|G| + |T|8|G| + 7|Zq∗| + 5|T| = 480Before using the RSU cache, authentication and key negotiation require five interactions, but after using the RSU cache, three interactions are required. The authentication does not require the participation of cluster heads. Before using cache, the traffic is 8|G| + 7|Zq∗| + 5|T| = 480 bytes, while after using cache, it is 4|G| + 7|Zq∗| + 3|T| = 312 bytes, and the traffic is reduced by 35%.


## 6. Conclusion

In this paper, we proposed an efficient authentication method for the successful transfer of information when the vehicle moves from one RSU to another RSU region. The proposed scheme can resist forgery, replay, internal attacks, and traceability. The scheme in [22] exhibits the same security performance, but the computation and communication required are higher than those in the proposed scheme. The traffic volume presented in [19] is considerably better than that of the proposed scheme; however, in [19], centralized authentication of vehicles and cloud services is required. When the vehicle is far away from the cloud server, the communication delay is considerably increased, and each vehicle stores the system keys, which requires TPD to ideally have strong security. If a single TPD is attacked, the security of the whole system is compromised. Thus, the proposed scheme can overcome these problems and can be used for the development of effective authentication schemes in the future.At present, artificial intelligence and blockchain technologies [29, 30] are widely used. How to introduce artificial intelligence or blockchain technology into the secure communication of VANET is the current research hotspot.



---

*Source: 3116682-2022-08-08.xml*