# A Novel Privacy-Preserving Authentication Protocol Using Bilinear Pairings for the VANET Environment

Authors: Junsong Zhang; Qikun Zhang; Xianling Lu; Yong Gan
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

With the rapid development of communication and microelectronic technology, the vehicular ad hoc network (VANET) has received extensive attention. However, due to the open nature of wireless communication links, it will cause VANET to generate many network security issues such as data leakage, network hijacking, and eavesdropping. To solve the above problem, this paper proposes a new authentication protocol which uses bilinear pairings and temporary pseudonyms. The proposed authentication protocol can realize functions such as the identity authentication of the vehicle and the verification of the message sent by the vehicle. Moreover, the proposed authentication protocol is capable of preventing any party (peer vehicles, service providers, etc.) from tracking the vehicle. To improve the efficiency of message verification, this paper also presents a batch authentication method for the vehicle to verify all messages received within a certain period of time. Finally, through security and performance analysis, it is actually easy to find that the proposed authentication protocol can not only resist various security threats but also have good computing and communication performance in the VANET environment.


---

## Body

## 1. Introduction

In recent years, the vehicular ad hoc network (VANET) has attracted more and more attention in improving people’s lives. The VANET is a special mobile self-organizing network used in the intelligent transportation field [1]. In this application scenario, a vehicle can share the information with other vehicles via vehicle-to-vehicle (V2V) or vehicle-to-roadside unit (V2R) communications, respectively [2]. And both the above two communication scenarios follow the dedicated short-range communication (DSRC) protocol [3]. According to the DSRC protocol, each vehicle must periodically broadcast traffic-related messages. The traffic-related message mainly includes the vehicle’s location, speed, and traffic status. Due to the open nature of wireless connections, the messages transmitted between the vehicles and the roadside unit (RSU) are easily intercepted or eavesdropped on by attackers [4]. Consequently, the security and privacy protection of the message is one of the key components towards the success of VANET applications.The user privacy should be preserved during authentication in VANET [5]. In order to hide the actual identities of the vehicles, the anonymity of vehicles is required for VANET. On the other hand, the VANET backend server must have the ability to extract a vehicle’s actual identity for tracing the malicious vehicles’ activities [6]. Otherwise, a malicious vehicle will randomly send a large amount of false messages in VANET, which will lead to serious consequences [7]. Therefore, privacy preservation and traceability are two seemly conflicting requirements, and hence, we must solve them properly. In addition, unlike other types of self-organizing networks, the VANET has the characteristics of very high node movement speed [8]. Consequently, during the authentication period, the communication time among different nodes will be very short. We must improve the efficiency of the authentication protocol as much as possible.To solve the above issues, in this paper, we present an authentication protocol based on bilinear pairings and temporary pseudonyms. The contributions of this work can be summarized as follows:(1)
We propose a bilinear pairing-based vehicle authentication and the message verification protocol. In addition, to protect privacy, the proposed protocol uses temporary pseudoidentity to identify the messages transmitted between vehicles(2)
To improve the authentication efficiency, the proposed protocol verifies the messages with the single or batch authentication manner on the recipient’s side(3)
In our proposed protocol, the TA and RSU have the ability to trace and revoke a compromised vehicle. The TA is also able to find the RSU who has authenticated the compromised vehicle by the traffic-related message that was sent from the compromised vehicle(4)
The detailed security analysis demonstrated that the proposed vehicle authentication and the message verification protocol can not only resist various security threats but also have good security features, such as unforgeability of identity and message integrity(5)
We evaluate the performance of the proposed authentication protocol and compare it with the related authentication protocols in terms of computation and transmission overheads. In addition, we also have analyzed the relationship between different factors and the message loss rate or the message delay of the authentication protocolThe remainder of this paper is organized as follows. Section2 summarizes the related work. Section 3 explains the system model and some mathematics-related preliminaries. In Section 4, the proposed privacy-preserving anonymous mutual authentication protocol is given. Moreover, we give the security analysis and performance evaluation of the proposed authentication protocol in Sections 5 and 6, respectively. Finally, Section 7 concludes the paper.


## 2. Related Work

In the past few years, many researchers have focused on the VANET’s security and privacy issues. Many solutions based on pseudonyms, group signatures, symmetric cryptography, and identity identifier encryption have been proposed. The existing research works in VANETs can be classified into the following main categories: pseudonym-based authentication protocols [9–14], group signature-based authentication protocols [15–17], and hybrid-based authentication protocols [18, 19].


### 2.1. Pseudonym-Based Authentication Protocols

The main idea of the pseudonym-based protocol [13] is to use the pseudonyms generated by random functions or other methods instead of the vehicles’ identities in the process of authentication in VANET. One of the earliest works in this field is proposed by Raya and Hubaux [9]. The main idea of Raya and Hubaux’s protocol is that the vehicles need to preload a huge number of anonymous certificates and their corresponding private keys based on the anonymity level they require. The main drawback of this protocol is that vehicles need to check a long list of revoked certificates when verifying the received signed message, which is very time-consuming. Sun et al. [10] proposed a pseudonym-based authentication protocol. Their protocol allows RSU to distribute certificate service and allows a vehicle to update its certificate on the way.Although the above method can hide the user’s real identity information successfully, the background server cannot complete the trajectory of the vehicle, which is necessary for certain scenarios. Then, Shen et al. [11] presented an ECC-based privacy-preserving authentication protocol with authority traceability for VANET. Li et al. [12] proposed an ID and pseudonym generation-based privacy-preserving authentication for VANET. He et al. [13] proposed an ID-based conditional privacy-preserving authentication protocol for VANETs based on elliptic curve cryptography. To improve performance further, the batch verification method is introduced in their protocol. Wang et al. [14] proposed a hybrid authentication protocol based on the PKI and identity-based signature, which can meet the requirements of security and conditional privacy in VANETs. However, in most of the abovementioned protocols, they cannot avoid the time-consuming identity legality detection in the message verification process.


### 2.2. Group Signature-Based Authentication Protocols

Another category of privacy-preserving authentication protocols is the group-based protocol [15–17, 20, 21]. In group-based authentication protocols, each group member can sign on behalf of the group without revealing its real identity when it sends traffic-related messages. Other vehicles can only verify that these messages are from a valid group member, but there is no way to determine who sent them. For example, Hao et al. [15] proposed a group signature-based distributed key management scheme for VANETs, which is expected to considerably facilitate location privacy protection and heterogeneous security policies. Later, Zhu et al. [16] presented an efficient privacy-preserving authentication protocol based on group signatures for VANET. In Zhu et al.’s protocol, they use a hash message authentication code (HMAC) to avoid time-consuming CRL checking and to ensure the integrity of messages before batch group authentication. Shao et al. [17] innovatively grouped the vehicle by RSU and proposed a new group signature-based authentication protocol for VANET.With the assistance of the new group signature scheme, the proposed authentication protocol is featured with threshold authentication, efficient revocation, unforgeability, anonymity, and traceability. Wang and Yao [20] proposed a group signature-based conditional privacy-preserving authentication for VANET. In addition, their authentication protocol also supports batch verification. Islam et al. [21] proposed a password-based conditional privacy-preserving authentication and group key generation protocol for VANET. Their protocol offers group key generation, user joining and leaving, and password change facilities. Besides the group-based signature scheme, other techniques have also been proposed to achieve anonymity within a group. For example, Zhang et al. [22] used the k-anonymity concept to protect the user privacy so that a vehicle is indistinguishable from k−1 vehicles. In addition, some researchers use the ring signature or blind signature to build the privacy-preserving authentication protocol [23, 24].


### 2.3. Hybrid-Based Authentication Protocols

Some research activities use a combination of pseudonyms and group signatures to complete the design of authentication protocols in VANET [18, 19, 25]. For instance, Giorgio et al. [18] suggested an authentication protocol for VANET which uses the above methods in combination to protect the messages transmitted between the vehicles. Later, Liu et al. [19] proposed a protocol for VANET which is based on identity-based and group-based signatures. In Liu et al.’s proposal, the vehicles are divided into two different categories: the public vehicles and the private vehicles. The role of a public vehicle is similar to an RSU. The messages sent from the public vehicles and RSUs are authenticated using the identity-based signature [25]. And the messages sent from the private vehicles are authenticated via the group signature for safety reasons.In general, most of the existing group-based protocols have some disadvantages. First, the group manager has all the knowledge about group members. Hence, there is the possibility of internal privilege attacks. Second, the joining and leaving of group members will result in the need to update the group key. Therefore, when the number of vehicles is large and the movement is frequent, a large amount of computing resources is required for updating the group key.


## 2.1. Pseudonym-Based Authentication Protocols

The main idea of the pseudonym-based protocol [13] is to use the pseudonyms generated by random functions or other methods instead of the vehicles’ identities in the process of authentication in VANET. One of the earliest works in this field is proposed by Raya and Hubaux [9]. The main idea of Raya and Hubaux’s protocol is that the vehicles need to preload a huge number of anonymous certificates and their corresponding private keys based on the anonymity level they require. The main drawback of this protocol is that vehicles need to check a long list of revoked certificates when verifying the received signed message, which is very time-consuming. Sun et al. [10] proposed a pseudonym-based authentication protocol. Their protocol allows RSU to distribute certificate service and allows a vehicle to update its certificate on the way.Although the above method can hide the user’s real identity information successfully, the background server cannot complete the trajectory of the vehicle, which is necessary for certain scenarios. Then, Shen et al. [11] presented an ECC-based privacy-preserving authentication protocol with authority traceability for VANET. Li et al. [12] proposed an ID and pseudonym generation-based privacy-preserving authentication for VANET. He et al. [13] proposed an ID-based conditional privacy-preserving authentication protocol for VANETs based on elliptic curve cryptography. To improve performance further, the batch verification method is introduced in their protocol. Wang et al. [14] proposed a hybrid authentication protocol based on the PKI and identity-based signature, which can meet the requirements of security and conditional privacy in VANETs. However, in most of the abovementioned protocols, they cannot avoid the time-consuming identity legality detection in the message verification process.


## 2.2. Group Signature-Based Authentication Protocols

Another category of privacy-preserving authentication protocols is the group-based protocol [15–17, 20, 21]. In group-based authentication protocols, each group member can sign on behalf of the group without revealing its real identity when it sends traffic-related messages. Other vehicles can only verify that these messages are from a valid group member, but there is no way to determine who sent them. For example, Hao et al. [15] proposed a group signature-based distributed key management scheme for VANETs, which is expected to considerably facilitate location privacy protection and heterogeneous security policies. Later, Zhu et al. [16] presented an efficient privacy-preserving authentication protocol based on group signatures for VANET. In Zhu et al.’s protocol, they use a hash message authentication code (HMAC) to avoid time-consuming CRL checking and to ensure the integrity of messages before batch group authentication. Shao et al. [17] innovatively grouped the vehicle by RSU and proposed a new group signature-based authentication protocol for VANET.With the assistance of the new group signature scheme, the proposed authentication protocol is featured with threshold authentication, efficient revocation, unforgeability, anonymity, and traceability. Wang and Yao [20] proposed a group signature-based conditional privacy-preserving authentication for VANET. In addition, their authentication protocol also supports batch verification. Islam et al. [21] proposed a password-based conditional privacy-preserving authentication and group key generation protocol for VANET. Their protocol offers group key generation, user joining and leaving, and password change facilities. Besides the group-based signature scheme, other techniques have also been proposed to achieve anonymity within a group. For example, Zhang et al. [22] used the k-anonymity concept to protect the user privacy so that a vehicle is indistinguishable from k−1 vehicles. In addition, some researchers use the ring signature or blind signature to build the privacy-preserving authentication protocol [23, 24].


## 2.3. Hybrid-Based Authentication Protocols

Some research activities use a combination of pseudonyms and group signatures to complete the design of authentication protocols in VANET [18, 19, 25]. For instance, Giorgio et al. [18] suggested an authentication protocol for VANET which uses the above methods in combination to protect the messages transmitted between the vehicles. Later, Liu et al. [19] proposed a protocol for VANET which is based on identity-based and group-based signatures. In Liu et al.’s proposal, the vehicles are divided into two different categories: the public vehicles and the private vehicles. The role of a public vehicle is similar to an RSU. The messages sent from the public vehicles and RSUs are authenticated using the identity-based signature [25]. And the messages sent from the private vehicles are authenticated via the group signature for safety reasons.In general, most of the existing group-based protocols have some disadvantages. First, the group manager has all the knowledge about group members. Hence, there is the possibility of internal privilege attacks. Second, the joining and leaving of group members will result in the need to update the group key. Therefore, when the number of vehicles is large and the movement is frequent, a large amount of computing resources is required for updating the group key.


## 3. System Model and Preliminaries

### 3.1. System Model

A typical VANET system model is shown in Figure1. There are three important components in VANET: the trusted authority (TA), on-board unit (OBU), and roadside unit (RSU) [26]. The TA is mainly responsible for the registration and certification of OBUs and RSUs. It is a trusted management and certification center. Generally, it is assumed that the TA is powerful enough in terms of communication, computation, and storage capabilities, and it is infeasible to compromise by the adversary.Figure 1
A typical communication model in VANET.The RSU, deployed on the roadside, can be regarded as the communication medium between OBU and TA. It is generally believed that there is a secure communication channel between RSU and TA, while the channel between RSU and OBU is an insecure wireless communication channel. In addition, due to working in unattended environments, the RSU can send secret information to the attackers when they are compromised. For the above reasons, all the RSUs must be managed and monitored by the TA. The OBU’s role is to achieve the communication between vehicles and vehicles or vehicles and RSUs. In addition, it periodically broadcasts traffic-related messages such as location and speed to other vehicles to alert them to avoid traffic jams or accidents [27]. It is generally assumed that the OBU is a tamper-proof device to store the real identity of the vehicle and some other key materials.


### 3.2. Attacker Model

Since the VANET uses open-featured wireless links to transmit traffic-related messages, attackers can launch various attacks against the VANET through eavesdropping and tampering. In the VANET environment, attackers are mainly divided into the external attacker and internal attacker [28]. The external attacker can eavesdrop or modify all the exchanged information in VANET. Based on these capabilities, the attacker may masquerade as a legitimate vehicle or RSU and communicate with the target entity to obtain illegal benefits. In addition, the external attacker has the ability to launch a denial-of-service attack. And the external attacker may be performed by a single attacker or a group of colluding attackers. In general, the external attacker has more computing and communication capabilities than the vehicle or RSU [29, 30].The internal attacker mainly refers to the malicious vehicle inside the VANET or the internal administrator [31–33]. The vehicle itself may also be a malicious node that can launch attacks such as the man-in-the-middle attack and replay attack. Besides, the attacker seeks to breach the anonymity of the vehicle. The internal attackers are potent as well since they are part of the system and have access to shared secrets. In addition, the attacker may eavesdrop on the communication link among the vehicles and RSUs. He/she may also attempt to establish the relationship between the successive pseudonyms and link these pseudonyms to a unique real entity.In addition, the impact of certain human factors will also pose a great threat to the security of the VANET. For example, the OBU may be stolen by the thief. The thief may use the stolen OBU to send false messages to the other vehicle or the RSUs, which may cause new security threats to the VANET. Therefore, we need to take into account the negative impact of the stolen device.


### 3.3. Elliptic Curve Cryptosystem (ECC)

ECC is one of the commonly used public key encryption algorithms, and its security relies on the difficulties of the discrete logarithm problem of the elliptic curve [34]. Compared to the well-known RSA public key encryption algorithm, ECC can achieve the same public key strength as RSA with a shorter key.Letp be a large prime number, and let GFp be a field of integers modulo p. A nonsuper singular elliptic curve E over GFp leads to an equation of the following form:
(1)y2=x3+ax+bmodp,where a,b∈GFp and 4a3+27b2≠0modp. And then we look at the points on E with coordinates in GFp which we denote by the following form:
(2)Epa,b=x,y:x,y∈GFpsatisfyy2=x3+ax+b∪∞.The point multiplication overE can be computed by repeated addition as
(3)k⋅P=P+P+⋯+Pktimes,where k∈GFp and P is a point P∈Epa,b. In view of shortness, we omit the details of ECC and refer to [35, 36].In order to prove the security of our proposed protocol, here, we present two important mathematical problems on elliptic curves as follows:Elliptic curve discrete logarithm problem (ECDLP). Given an elliptic curve E defined over a finite field GFp, and two points P,Q∈E of order q, it is hard to find an integer k∈Zq∗ such that Q=kP.Computational Diffie-Hellman problem (CDHP). Given an elliptic curve E defined over a finite field GFp, and the points P,aP,bP∈E, it is hard to compute abP.


### 3.4. Bilinear Pairings

The bilinear mapping defines three multiplicative cyclic groups with prime orderq:G1,G2,GT. Let e^:G1×G2→GT be a computable bilinear map, which satisfies the following properties:Bilinearity. For any P,Q∈G and a,b∈Zq∗, e^aP,bQ=e^P,Qab, where Zq∗=j∣1≤j≤q−1. This can be restated in the following way: for any P,Q∈G and a,∈Zq∗, e^a·P,Q=e^P,a·Q=e^P,Qa.Nondegenerate. For any P∈G, e^P,P≠e, where e is the identity element of the group GT.Computability. There exists an efficient algorithm to compute e^P,Q for any P∈G1 and Q∈G2.Then, we callede a bilinear map. The bilinear mapping can be constructed by Tate pairs or Weil pairs on elliptic curves over a finite field.


## 3.1. System Model

A typical VANET system model is shown in Figure1. There are three important components in VANET: the trusted authority (TA), on-board unit (OBU), and roadside unit (RSU) [26]. The TA is mainly responsible for the registration and certification of OBUs and RSUs. It is a trusted management and certification center. Generally, it is assumed that the TA is powerful enough in terms of communication, computation, and storage capabilities, and it is infeasible to compromise by the adversary.Figure 1
A typical communication model in VANET.The RSU, deployed on the roadside, can be regarded as the communication medium between OBU and TA. It is generally believed that there is a secure communication channel between RSU and TA, while the channel between RSU and OBU is an insecure wireless communication channel. In addition, due to working in unattended environments, the RSU can send secret information to the attackers when they are compromised. For the above reasons, all the RSUs must be managed and monitored by the TA. The OBU’s role is to achieve the communication between vehicles and vehicles or vehicles and RSUs. In addition, it periodically broadcasts traffic-related messages such as location and speed to other vehicles to alert them to avoid traffic jams or accidents [27]. It is generally assumed that the OBU is a tamper-proof device to store the real identity of the vehicle and some other key materials.


## 3.2. Attacker Model

Since the VANET uses open-featured wireless links to transmit traffic-related messages, attackers can launch various attacks against the VANET through eavesdropping and tampering. In the VANET environment, attackers are mainly divided into the external attacker and internal attacker [28]. The external attacker can eavesdrop or modify all the exchanged information in VANET. Based on these capabilities, the attacker may masquerade as a legitimate vehicle or RSU and communicate with the target entity to obtain illegal benefits. In addition, the external attacker has the ability to launch a denial-of-service attack. And the external attacker may be performed by a single attacker or a group of colluding attackers. In general, the external attacker has more computing and communication capabilities than the vehicle or RSU [29, 30].The internal attacker mainly refers to the malicious vehicle inside the VANET or the internal administrator [31–33]. The vehicle itself may also be a malicious node that can launch attacks such as the man-in-the-middle attack and replay attack. Besides, the attacker seeks to breach the anonymity of the vehicle. The internal attackers are potent as well since they are part of the system and have access to shared secrets. In addition, the attacker may eavesdrop on the communication link among the vehicles and RSUs. He/she may also attempt to establish the relationship between the successive pseudonyms and link these pseudonyms to a unique real entity.In addition, the impact of certain human factors will also pose a great threat to the security of the VANET. For example, the OBU may be stolen by the thief. The thief may use the stolen OBU to send false messages to the other vehicle or the RSUs, which may cause new security threats to the VANET. Therefore, we need to take into account the negative impact of the stolen device.


## 3.3. Elliptic Curve Cryptosystem (ECC)

ECC is one of the commonly used public key encryption algorithms, and its security relies on the difficulties of the discrete logarithm problem of the elliptic curve [34]. Compared to the well-known RSA public key encryption algorithm, ECC can achieve the same public key strength as RSA with a shorter key.Letp be a large prime number, and let GFp be a field of integers modulo p. A nonsuper singular elliptic curve E over GFp leads to an equation of the following form:
(1)y2=x3+ax+bmodp,where a,b∈GFp and 4a3+27b2≠0modp. And then we look at the points on E with coordinates in GFp which we denote by the following form:
(2)Epa,b=x,y:x,y∈GFpsatisfyy2=x3+ax+b∪∞.The point multiplication overE can be computed by repeated addition as
(3)k⋅P=P+P+⋯+Pktimes,where k∈GFp and P is a point P∈Epa,b. In view of shortness, we omit the details of ECC and refer to [35, 36].In order to prove the security of our proposed protocol, here, we present two important mathematical problems on elliptic curves as follows:Elliptic curve discrete logarithm problem (ECDLP). Given an elliptic curve E defined over a finite field GFp, and two points P,Q∈E of order q, it is hard to find an integer k∈Zq∗ such that Q=kP.Computational Diffie-Hellman problem (CDHP). Given an elliptic curve E defined over a finite field GFp, and the points P,aP,bP∈E, it is hard to compute abP.


## 3.4. Bilinear Pairings

The bilinear mapping defines three multiplicative cyclic groups with prime orderq:G1,G2,GT. Let e^:G1×G2→GT be a computable bilinear map, which satisfies the following properties:Bilinearity. For any P,Q∈G and a,b∈Zq∗, e^aP,bQ=e^P,Qab, where Zq∗=j∣1≤j≤q−1. This can be restated in the following way: for any P,Q∈G and a,∈Zq∗, e^a·P,Q=e^P,a·Q=e^P,Qa.Nondegenerate. For any P∈G, e^P,P≠e, where e is the identity element of the group GT.Computability. There exists an efficient algorithm to compute e^P,Q for any P∈G1 and Q∈G2.Then, we callede a bilinear map. The bilinear mapping can be constructed by Tate pairs or Weil pairs on elliptic curves over a finite field.


## 4. The Proposed Authentication Scheme

In this section, we present a bilinear pairing-based vehicle authentication and the message authentication protocol to improve the security and efficiency of communication in VANET. It contains seven phases, namely, system initialization, registration, RSU temporary key retrieval, vehicle authentication, vehicle verification, message signing, and message verification. To facilitate the subsequent description, the various symbols used in this paper are listed in Table1.Table 1
The symbols used in this paper.
NotationsDescriptionRiTheith roadside unit (RSU)RIDiThe identity of the RSURiTAThe trusted authorityVjThejth vehiclepIDjThe pseudoidentity of the vehicle which containspIDj=pIDj1,pIDj2s, PpubThe master and public keys of TArprki, rpukiThe master and public keys of theith RSUuprkj, upukjThe master and public keys of thejth OBUh·h:0,1∗→Zq∗ is a secure hash functionH·H:Epa,b→0,1l, where l is the length of the stringH1·H1:0,1∗→G is a map-to-point hash function⊕The bitwise XOR operation‖String concatenation operation


### 4.1. Initialization

In the initialization phase, TA sets the required parameters used in the proposed scheme:Step I1. TA first selects a prime number p and an appropriate elliptic curve E over the finite field GFp and then selects a base point P over the elliptic curve E, and the order of P is q. Let G be a cyclic additive group generated by P and GT be a cyclic multiplicative group with the same order q. Then, TA constructs an appropriate bilinear map e^:G×G→GT.Step I2. The TA selects two secure cryptographic hash functions h·, H·, and H1·, where h:0,1∗→Zq∗ is a secure hash function, H:Epa,b→0,1l, where l is the length of the string, and H1:0,1∗→G is a map-to-point hash function.Step I3. Next, TA chooses its private key s∈Zq∗ and computes its corresponding public key Ppub=s⋅P. Then, TA selects two secret values x,y∈Zq∗ and saves them properly.Step I4. After completing the above operations, the TA publishes the system parameters E,q,P,G,GT,h·,H·,Ppub.


### 4.2. Registration Phase

Due to different roles and characteristics, the registration phase is divided into two parts: OBU registration and RSU registration.


#### 4.2.1. OBU Registration

When the vehicleVj wants to accept the services provided by VANET, it must be registered by the TA:Step OR1. The vehicle Vj selects a unique identity IDvj and a password PWvj. Then, it chooses a random number bvj∈Zq∗ and computes Bvj=hbvjPWvj. Next, the Vj sends IDvj,Bvj to the TA through a secure channel.Step OR2. Upon receiving the message IDvj,Bvj, the TA randomly generates a number rvj and then calculates
(4)Avj=hxrvj,Cvj=Avj⊕Bvj,Dvj=hIDvjBvjAvj.Then, TA chooses a random numberuprkj∈Zq∗ as the user’s private key and computes the corresponding public key upukj=uprkj·P.Step OR3. Next, the TA embedded the information Cvj,Dvj,rvj,h·,H·,q,uprkj,upukj into the Vj’s tamper-proof device (TPD) and keeps IDvj,upukj in its tracking list.


#### 4.2.2. RSU Registration

The registration process of the RSURi, i∈1,2,3,⋯,n, is explained as follows:Step RR1. The RSU Ri sends the information about the network to which it is connected to the TA securely.Step RR2. The TA chooses a random value rprki∈Zq∗ as Ri’s private key and computes the corresponding public key rpuki=rprki·P.Step RR3. The TA generates the signature Signri=hyRIDi, where RIDi is Ri’s identifier number. Then, TA injects the information RIDi,Signri,rprki,rpuki into the RSU via a secure channel.


### 4.3. RSU Temporary Key Retrieval Phase

In order to improve the efficiency of message verification, RSU is responsible for regularly distributing its local temporary keys for the vehicles which enter into the RSU’s communication range.The RSURi randomly chooses a value δi∈Zq∗ and calculates the temporary master key MKi=hrprki⊕δi. Then, the RSU stores the temporary master key in its TPD. And then, the RSU calculates the corresponding temporary public key RPKi=MKiP.Next, the RSU releases its temporary public keyRPKi together with the random number δi in its coverage area periodically.


### 4.4. The Vehicle Authentication Phase

When a vehicle arrives at the area covered by the RSURi, it first checks the identity of Ri and determines whether it is a new RSU. If so, the vehicle Vj should be authenticated to Ri to get the of RSUi’s temporary master key. Then, Vj calculates its anonymous identity via the Ri’s temporary master key.In this phase, the vehicleVj generates an anonymous identity and constructs a message authentication code. Then, the TA verifies the authentication message to verify the legality of the vehicle Vj. The detailed message authentication process is described as follows:Step A1. The user of the vehicle Vj enters the identity IDvj and the password PWvj into the OBUj. The OBU of the vehicle Vj calculates the following formulas:
(5)Bvj∗=hbvjPWvj,Avj∗=Bvj∗⊕Cvj,Dvj∗=hIDvjBvj∗Avj∗.And then, it verifies whetherDvj∗=Dvj holds. If they are not equal, the OBUj will require the user to enter the correct identity and password again. Otherwise, the OBUj generates a timestamp Tvj and computes TIDvj=IDvj⊕hAvjTvj and Certvj=hAvjIDvjTvj.Step A2. Then, the OBU of the vehicle Vj sends the message M1=TIDvj,rvj,Tvj,upukj,Certvj to the RSUi via a public communication channel.Step A3. Upon receiving the message, the Ri first checks the freshness of the timestamp Tvj. If it holds, the RSUi then computes Certri=Hrprki·Ppub⊕TIDvjCertvjSignriTc1 and sends the message M1,Certri,RIDi,rpuki,Tc1 to the TA via a public channel.


### 4.5. The Vehicle Verification Phase

Step V1. Upon receiving the message M1,Certri,RIDi,rpuki,Tc1, the TA first checks the timestamp Tc1. If the condition holds, the TA computes
(6)Signri∗=hyRIDi,Hs·rpuki⊕Certri=TIDvjCertvjSignriTc1.Then, TA determines whether the equationSignri∗=Signri is true. If they are equal, the TA considers Ri to be a legitimate RSU.Step V2. Next, the TA extracts the message M1 and continues to calculate
(7)Avj∗=hxrvj,IDvj∗=TIDvj⊕hAvj∗Tvj,Certvj∗=hAvj∗IDvj∗Tvj.And then it checks whetherCertvj∗=Certvj holds. If they are equal, the TA considers Vj to be a legitimate vehicle.Step V3. The TA computes CertTA=Hs·rpuki⊕TIDvjhyRIDiTc1Tc2 and sends the message CertTA,Tc2 to Ri via a public channel to tell Ri the vehicle Vj is a legitimate vehicle. Upon receiving the message, Ri computes C1=Hrprki·upukj⊕TIDvjMKiTc1Tc2 and sends C1 to the vehicle Vj via a public communication channel.Step V4. Upon receiving the message, the vehicle Vj computes C1⊕Huprkj·rpuki=TIDvjMKiTc1Tc2 and extracts Ri’s local master keys MKi to prepare for the next message signing phase. The sequence diagram of the vehicle’s login and certification steps is described in Figure 2.Figure 2
The vehicle’s login and certification process.


### 4.6. Message Signing Phase

As discussed previously, the vehicle driving on the road needs to send out traffic-related messages periodically. To protect the privacy of the vehicle, the message should be signed with the vehicle’s pseudoidentity. However, in order to ensure the legitimacy of the received traffic-related messages, the receiver needs to verify the messages. Hence, message authentication is very important in VANET. The receiver checks the integrity and validity of the traffic-related message by verifying the correctness of the signature. The details of the signing phase can be described as follows:Step M1. The vehicle Vj first chooses a random number σ∈Zq∗ and generates its pseudo-ID pIDj=pIDj1,pIDj2 and the corresponding private key SKj=SKj1,SKj2 as follows:
(8)pIDj1=σ⋅P,pIDj2=IDvj⊕hσMKi,SKj1=MKi⋅pIDj1,SKj2=MKi⋅H1pIDj1pIDj2δi.Step M2. The vehicle Vj then generates a traffic message Ms which includes the timestamp and the traffic information related to the vehicle. Next, Vj signs the message Ms as follows:
(9)θj=SKj1+hMs⋅SKj2.Step M3. Finally, the vehicle Vj releases the traffic-related message pIDj,θj,Ms,RIDi. Here, RIDi is the identity of the RSU Ri. It is used to let the verifier know that the traffic-related message is signed by the key which is based on the temporary master key of Ri.


### 4.7. Message Verification Phase

When the traffic-related messagepIDj,θj,Ms,RIDi is received by other recipients, they should check the validity of this message. And the validity of the traffic-related message can be verified when the value of the following equation is true:
(10)e^θj,P=e^pIDj1,RPKi×e^hMs⋅H1pIDj1pIDj2δi,RPKi.Equation (10) can be derived as follow:
(11)L.H.S=e^θj,P=e^SKj1+hMs⋅SKj2,P=e^SKj1,P×e^hMs⋅SKj2,P=e^MKi⋅pIDj1,P×e^hMs⋅MKi⋅H1pIDj1IDj2δi,P=e^pIDj1,MKi⋅P×e^hMs⋅H1pIDj1pIDj2δi,MKi⋅P=e^pIDj1,RPKi×e^hMs⋅H1pIDj1pIDj2δi,RPKi=R.H.S.The recipients have obtained the system parameterP, the RSU’s temporary public key RPKi, and the random number δi. After receiving vehicle Vj’s traffic-related message, they can get the traffic-related message Ms, the signature θj, and the anonymous identity pIDj. If the above formula is true, it proves that the sender of the traffic-related message is legal, and the integrity of this message can also be confirmed.When the recipient receives multiple messages at the same time, the recipient can use the batch verification method to verify these messages. Suppose these messages are marked aspID1,θ1,Ms1,RIDi,pID2,θ2,Ms2,RIDi,⋯,pIDn,θn,Msn,RIDi. The batch verification of these messages uses the following equation:
(12)e^∑j=1nθj,P=e^∑j=1npIDj1,RPKi×e^∑j=1nhzMsj⋅H1pIDj1pIDj2δi,RPKi.Verifying a number of signatures with the batch verification method is much faster than verifying them individually. In addition, the proof process of formula (12) is similar to that of formula (10). For brevity, we omit the proof process of formula (12). The sequence diagram of the message signing and verification processes is described in Figure 3.Figure 3
The message signing and verification processes.


### 4.8. Real Identity Tracking and Revocation

In the proposed authentication protocol, the traffic-related messages are signed with pseudoidentities to protect privacy. When an OBU is compromised and releases false traffic-related messages, TA should have the ability to reveal its real identity and revoke its long-term certificate. In the proposed protocol, only the TA and RSU have the ability to trace and revoke a compromised vehicle. Therefore, TA is able to find the compromised vehicle by theRIDi which is contained in the traffic-related messages. Then, TA calculates the real identity of the compromised vehicle using the following equation:
(13)pIDj2⊕hσMKi=IDvj.Next, TA adds the genuine identityIDvj of this vehicle to its compromised vehicle list (CVL) and sends the updated CVL to all RSUs. When a vehicle is compromised, the RSU will discard its request message in the early stages of mutual authentication. Consequently, the compromised vehicle will not get the RSU’s local master keys. And it cannot calculate the corresponding temporary key to release the malicious wrong traffic-related message.


## 4.1. Initialization

In the initialization phase, TA sets the required parameters used in the proposed scheme:Step I1. TA first selects a prime number p and an appropriate elliptic curve E over the finite field GFp and then selects a base point P over the elliptic curve E, and the order of P is q. Let G be a cyclic additive group generated by P and GT be a cyclic multiplicative group with the same order q. Then, TA constructs an appropriate bilinear map e^:G×G→GT.Step I2. The TA selects two secure cryptographic hash functions h·, H·, and H1·, where h:0,1∗→Zq∗ is a secure hash function, H:Epa,b→0,1l, where l is the length of the string, and H1:0,1∗→G is a map-to-point hash function.Step I3. Next, TA chooses its private key s∈Zq∗ and computes its corresponding public key Ppub=s⋅P. Then, TA selects two secret values x,y∈Zq∗ and saves them properly.Step I4. After completing the above operations, the TA publishes the system parameters E,q,P,G,GT,h·,H·,Ppub.


## 4.2. Registration Phase

Due to different roles and characteristics, the registration phase is divided into two parts: OBU registration and RSU registration.


### 4.2.1. OBU Registration

When the vehicleVj wants to accept the services provided by VANET, it must be registered by the TA:Step OR1. The vehicle Vj selects a unique identity IDvj and a password PWvj. Then, it chooses a random number bvj∈Zq∗ and computes Bvj=hbvjPWvj. Next, the Vj sends IDvj,Bvj to the TA through a secure channel.Step OR2. Upon receiving the message IDvj,Bvj, the TA randomly generates a number rvj and then calculates
(4)Avj=hxrvj,Cvj=Avj⊕Bvj,Dvj=hIDvjBvjAvj.Then, TA chooses a random numberuprkj∈Zq∗ as the user’s private key and computes the corresponding public key upukj=uprkj·P.Step OR3. Next, the TA embedded the information Cvj,Dvj,rvj,h·,H·,q,uprkj,upukj into the Vj’s tamper-proof device (TPD) and keeps IDvj,upukj in its tracking list.


### 4.2.2. RSU Registration

The registration process of the RSURi, i∈1,2,3,⋯,n, is explained as follows:Step RR1. The RSU Ri sends the information about the network to which it is connected to the TA securely.Step RR2. The TA chooses a random value rprki∈Zq∗ as Ri’s private key and computes the corresponding public key rpuki=rprki·P.Step RR3. The TA generates the signature Signri=hyRIDi, where RIDi is Ri’s identifier number. Then, TA injects the information RIDi,Signri,rprki,rpuki into the RSU via a secure channel.


## 4.2.1. OBU Registration

When the vehicleVj wants to accept the services provided by VANET, it must be registered by the TA:Step OR1. The vehicle Vj selects a unique identity IDvj and a password PWvj. Then, it chooses a random number bvj∈Zq∗ and computes Bvj=hbvjPWvj. Next, the Vj sends IDvj,Bvj to the TA through a secure channel.Step OR2. Upon receiving the message IDvj,Bvj, the TA randomly generates a number rvj and then calculates
(4)Avj=hxrvj,Cvj=Avj⊕Bvj,Dvj=hIDvjBvjAvj.Then, TA chooses a random numberuprkj∈Zq∗ as the user’s private key and computes the corresponding public key upukj=uprkj·P.Step OR3. Next, the TA embedded the information Cvj,Dvj,rvj,h·,H·,q,uprkj,upukj into the Vj’s tamper-proof device (TPD) and keeps IDvj,upukj in its tracking list.


## 4.2.2. RSU Registration

The registration process of the RSURi, i∈1,2,3,⋯,n, is explained as follows:Step RR1. The RSU Ri sends the information about the network to which it is connected to the TA securely.Step RR2. The TA chooses a random value rprki∈Zq∗ as Ri’s private key and computes the corresponding public key rpuki=rprki·P.Step RR3. The TA generates the signature Signri=hyRIDi, where RIDi is Ri’s identifier number. Then, TA injects the information RIDi,Signri,rprki,rpuki into the RSU via a secure channel.


## 4.3. RSU Temporary Key Retrieval Phase

In order to improve the efficiency of message verification, RSU is responsible for regularly distributing its local temporary keys for the vehicles which enter into the RSU’s communication range.The RSURi randomly chooses a value δi∈Zq∗ and calculates the temporary master key MKi=hrprki⊕δi. Then, the RSU stores the temporary master key in its TPD. And then, the RSU calculates the corresponding temporary public key RPKi=MKiP.Next, the RSU releases its temporary public keyRPKi together with the random number δi in its coverage area periodically.


## 4.4. The Vehicle Authentication Phase

When a vehicle arrives at the area covered by the RSURi, it first checks the identity of Ri and determines whether it is a new RSU. If so, the vehicle Vj should be authenticated to Ri to get the of RSUi’s temporary master key. Then, Vj calculates its anonymous identity via the Ri’s temporary master key.In this phase, the vehicleVj generates an anonymous identity and constructs a message authentication code. Then, the TA verifies the authentication message to verify the legality of the vehicle Vj. The detailed message authentication process is described as follows:Step A1. The user of the vehicle Vj enters the identity IDvj and the password PWvj into the OBUj. The OBU of the vehicle Vj calculates the following formulas:
(5)Bvj∗=hbvjPWvj,Avj∗=Bvj∗⊕Cvj,Dvj∗=hIDvjBvj∗Avj∗.And then, it verifies whetherDvj∗=Dvj holds. If they are not equal, the OBUj will require the user to enter the correct identity and password again. Otherwise, the OBUj generates a timestamp Tvj and computes TIDvj=IDvj⊕hAvjTvj and Certvj=hAvjIDvjTvj.Step A2. Then, the OBU of the vehicle Vj sends the message M1=TIDvj,rvj,Tvj,upukj,Certvj to the RSUi via a public communication channel.Step A3. Upon receiving the message, the Ri first checks the freshness of the timestamp Tvj. If it holds, the RSUi then computes Certri=Hrprki·Ppub⊕TIDvjCertvjSignriTc1 and sends the message M1,Certri,RIDi,rpuki,Tc1 to the TA via a public channel.


## 4.5. The Vehicle Verification Phase

Step V1. Upon receiving the message M1,Certri,RIDi,rpuki,Tc1, the TA first checks the timestamp Tc1. If the condition holds, the TA computes
(6)Signri∗=hyRIDi,Hs·rpuki⊕Certri=TIDvjCertvjSignriTc1.Then, TA determines whether the equationSignri∗=Signri is true. If they are equal, the TA considers Ri to be a legitimate RSU.Step V2. Next, the TA extracts the message M1 and continues to calculate
(7)Avj∗=hxrvj,IDvj∗=TIDvj⊕hAvj∗Tvj,Certvj∗=hAvj∗IDvj∗Tvj.And then it checks whetherCertvj∗=Certvj holds. If they are equal, the TA considers Vj to be a legitimate vehicle.Step V3. The TA computes CertTA=Hs·rpuki⊕TIDvjhyRIDiTc1Tc2 and sends the message CertTA,Tc2 to Ri via a public channel to tell Ri the vehicle Vj is a legitimate vehicle. Upon receiving the message, Ri computes C1=Hrprki·upukj⊕TIDvjMKiTc1Tc2 and sends C1 to the vehicle Vj via a public communication channel.Step V4. Upon receiving the message, the vehicle Vj computes C1⊕Huprkj·rpuki=TIDvjMKiTc1Tc2 and extracts Ri’s local master keys MKi to prepare for the next message signing phase. The sequence diagram of the vehicle’s login and certification steps is described in Figure 2.Figure 2
The vehicle’s login and certification process.


## 4.6. Message Signing Phase

As discussed previously, the vehicle driving on the road needs to send out traffic-related messages periodically. To protect the privacy of the vehicle, the message should be signed with the vehicle’s pseudoidentity. However, in order to ensure the legitimacy of the received traffic-related messages, the receiver needs to verify the messages. Hence, message authentication is very important in VANET. The receiver checks the integrity and validity of the traffic-related message by verifying the correctness of the signature. The details of the signing phase can be described as follows:Step M1. The vehicle Vj first chooses a random number σ∈Zq∗ and generates its pseudo-ID pIDj=pIDj1,pIDj2 and the corresponding private key SKj=SKj1,SKj2 as follows:
(8)pIDj1=σ⋅P,pIDj2=IDvj⊕hσMKi,SKj1=MKi⋅pIDj1,SKj2=MKi⋅H1pIDj1pIDj2δi.Step M2. The vehicle Vj then generates a traffic message Ms which includes the timestamp and the traffic information related to the vehicle. Next, Vj signs the message Ms as follows:
(9)θj=SKj1+hMs⋅SKj2.Step M3. Finally, the vehicle Vj releases the traffic-related message pIDj,θj,Ms,RIDi. Here, RIDi is the identity of the RSU Ri. It is used to let the verifier know that the traffic-related message is signed by the key which is based on the temporary master key of Ri.


## 4.7. Message Verification Phase

When the traffic-related messagepIDj,θj,Ms,RIDi is received by other recipients, they should check the validity of this message. And the validity of the traffic-related message can be verified when the value of the following equation is true:
(10)e^θj,P=e^pIDj1,RPKi×e^hMs⋅H1pIDj1pIDj2δi,RPKi.Equation (10) can be derived as follow:
(11)L.H.S=e^θj,P=e^SKj1+hMs⋅SKj2,P=e^SKj1,P×e^hMs⋅SKj2,P=e^MKi⋅pIDj1,P×e^hMs⋅MKi⋅H1pIDj1IDj2δi,P=e^pIDj1,MKi⋅P×e^hMs⋅H1pIDj1pIDj2δi,MKi⋅P=e^pIDj1,RPKi×e^hMs⋅H1pIDj1pIDj2δi,RPKi=R.H.S.The recipients have obtained the system parameterP, the RSU’s temporary public key RPKi, and the random number δi. After receiving vehicle Vj’s traffic-related message, they can get the traffic-related message Ms, the signature θj, and the anonymous identity pIDj. If the above formula is true, it proves that the sender of the traffic-related message is legal, and the integrity of this message can also be confirmed.When the recipient receives multiple messages at the same time, the recipient can use the batch verification method to verify these messages. Suppose these messages are marked aspID1,θ1,Ms1,RIDi,pID2,θ2,Ms2,RIDi,⋯,pIDn,θn,Msn,RIDi. The batch verification of these messages uses the following equation:
(12)e^∑j=1nθj,P=e^∑j=1npIDj1,RPKi×e^∑j=1nhzMsj⋅H1pIDj1pIDj2δi,RPKi.Verifying a number of signatures with the batch verification method is much faster than verifying them individually. In addition, the proof process of formula (12) is similar to that of formula (10). For brevity, we omit the proof process of formula (12). The sequence diagram of the message signing and verification processes is described in Figure 3.Figure 3
The message signing and verification processes.


## 4.8. Real Identity Tracking and Revocation

In the proposed authentication protocol, the traffic-related messages are signed with pseudoidentities to protect privacy. When an OBU is compromised and releases false traffic-related messages, TA should have the ability to reveal its real identity and revoke its long-term certificate. In the proposed protocol, only the TA and RSU have the ability to trace and revoke a compromised vehicle. Therefore, TA is able to find the compromised vehicle by theRIDi which is contained in the traffic-related messages. Then, TA calculates the real identity of the compromised vehicle using the following equation:
(13)pIDj2⊕hσMKi=IDvj.Next, TA adds the genuine identityIDvj of this vehicle to its compromised vehicle list (CVL) and sends the updated CVL to all RSUs. When a vehicle is compromised, the RSU will discard its request message in the early stages of mutual authentication. Consequently, the compromised vehicle will not get the RSU’s local master keys. And it cannot calculate the corresponding temporary key to release the malicious wrong traffic-related message.


## 5. Security Analysis

In this section, we analyze the security and privacy features of the proposed authentication protocol as follows.


### 5.1. Unforgeability of Identity

The proposed protocol guarantees that no one can use an identity that does not belong to him/her to take part in the system. When the vehicleVj needs to be authenticated at the RSUi, the message TIDvj,rvj,Tvj,upukj,Certvj sent by Vj does contain its real identity IDvj. However, due to the one-way nature of the hash function, the attacker cannot get IDvj from the above message.On the other hand, the attacker also cannot pretend to be an RSU to spoof. Even if the attacker obtains theRSUi’s identity RIDi and the corresponding public key rpuki, the attacker is unable to calculate the parameter Hrprki·Ppub for authentication with the TA because it cannot obtain the RSUi’s private key rprki. Then, the attacker is unable to establish a secure connection with the vehicle Vj and perform subsequent operations.


### 5.2. Replay Attacks

Due to the open nature of the wireless channel, the message can be easily captured or modified by the attacker. Therefore, the attacker may use the captured traffic-related message to launch a replay attack. In our proposed scheme, the timestampTvj is used to keep the freshness of the messages and resist the replay attack in the vehicle authentication phase. Although the attacker may obtain another vehicle’s authentication message TIDvj,rvj,Tvj,upukj,Certvj, without knowing the secure variable Avj, he/she cannot get the session key and finish the authentication successfully.Similarly, the attacker cannot replay the traffic-related message. The reason is that the traffic-related message contains the random numberσ and the corresponding private key SKvj which is only owned by the vehicle Vj. If an attacker replays this data, he/she will not be able to structure a valid signature about the traffic-related message. Through the above analysis, it is clear that the proposed authentication protocol has the ability to resist the replay attack.


### 5.3. Message Integrity and Authentication

For VANET, which is composed of open communication links, the integrity and authenticity of the message must be guaranteed. In the proposed authentication protocol, the TA injects the relevant secret information into every RSU’s and OBU’s memory in the registration phase. In V2R communication, the vehicleVj sends the request message to RSUi to authenticate with the RSUi and obtain its local master keys MKi. Then, the RSUi returns its local master key MKi to the requested vehicle. All the messages mentioned above are encrypted with the secret values obtained from the TA. Therefore, the receiver can easily verify the integrity and identity of the messages.After mutual authentication, the vehicleVj obtains the local master key from the RSUi. In the next V2V communication, the vehicle Vj uses the RSUi’s local master key MKi to generate its pseudo-ID pIDj=pIDj1,pIDj2 and the corresponding private key SKj=SKj1,SKj2. Because of the use of identity-based signature algorithms, the receiver can easily verify the integrity of the traffic-related messages broadcasted by vehicle Vj. With the above analysis, we can find that our proposed protocol satisfies the requirements of message integrity and authentication.


### 5.4. Conditional Privacy-Preserving Property

As described earlier, in the authentication phase, the main role of RSU is to distribute the temporary public key to the vehicles nearby it. However, the privacy of the vehicle’s identity must be protected in this environment. The proposed authentication protocol achieves the conditional privacy-preserving property in two aspects.First, when a vehicleVj moves near the RSU, Vj needs to generate a fresh timestamp Tvj and uses it to calculate with the user’s real identity IDvj via the hash function to generate an authentication message. Since the timestamp Tvj used to calculate the authentication message is different each time and the hash function has a strong collision resistance property, the adversary cannot get the genuine identity information of the vehicle Vj through the message M1=TIDvj,rvj,Tvj,upukj,Certvj.Second, when the vehicleVj joins an RSU Ri’s group, it obtains the Ri’s local master key MKi and the corresponding temporary public key RPKi. And then, it generates a new pseudo-ID and the corresponding private key to sign the traffic-related message by the temporary master key of Ri. Since the traffic-related message is signed with different temporary master keys of Ri at different time, no entity except TA and Ri can establish the link between signatures and pseudo-IDs of the vehicle Vj. In summary, we can find that the proposed authentication protocol satisfies the conditional privacy-preserving property.


### 5.5. Traceability and Revocability

In the proposed authentication protocol, only the TA can get the authentic identityIDvj of the vehicle Vj from its authentication request message. Other participants (including vehicles and attackers) cannot extract the authentic identity IDvj of the vehicle Vj from the authentication request message.In addition, to protect privacy, the proposed protocol signs the traffic-related messages with different pseudo-IDs in the message signing phase. And the TA can get the authentic identityIDvj of the vehicle Vj by using equation (13). Consequently, when a vehicle is compromised, the TA could reveal its authentic identity to other entities. As a result, the revoked vehicle cannot join the RSU’s communication group to release any messages. This means that the proposed authentication protocol supports the traceability and revocability property.


## 5.1. Unforgeability of Identity

The proposed protocol guarantees that no one can use an identity that does not belong to him/her to take part in the system. When the vehicleVj needs to be authenticated at the RSUi, the message TIDvj,rvj,Tvj,upukj,Certvj sent by Vj does contain its real identity IDvj. However, due to the one-way nature of the hash function, the attacker cannot get IDvj from the above message.On the other hand, the attacker also cannot pretend to be an RSU to spoof. Even if the attacker obtains theRSUi’s identity RIDi and the corresponding public key rpuki, the attacker is unable to calculate the parameter Hrprki·Ppub for authentication with the TA because it cannot obtain the RSUi’s private key rprki. Then, the attacker is unable to establish a secure connection with the vehicle Vj and perform subsequent operations.


## 5.2. Replay Attacks

Due to the open nature of the wireless channel, the message can be easily captured or modified by the attacker. Therefore, the attacker may use the captured traffic-related message to launch a replay attack. In our proposed scheme, the timestampTvj is used to keep the freshness of the messages and resist the replay attack in the vehicle authentication phase. Although the attacker may obtain another vehicle’s authentication message TIDvj,rvj,Tvj,upukj,Certvj, without knowing the secure variable Avj, he/she cannot get the session key and finish the authentication successfully.Similarly, the attacker cannot replay the traffic-related message. The reason is that the traffic-related message contains the random numberσ and the corresponding private key SKvj which is only owned by the vehicle Vj. If an attacker replays this data, he/she will not be able to structure a valid signature about the traffic-related message. Through the above analysis, it is clear that the proposed authentication protocol has the ability to resist the replay attack.


## 5.3. Message Integrity and Authentication

For VANET, which is composed of open communication links, the integrity and authenticity of the message must be guaranteed. In the proposed authentication protocol, the TA injects the relevant secret information into every RSU’s and OBU’s memory in the registration phase. In V2R communication, the vehicleVj sends the request message to RSUi to authenticate with the RSUi and obtain its local master keys MKi. Then, the RSUi returns its local master key MKi to the requested vehicle. All the messages mentioned above are encrypted with the secret values obtained from the TA. Therefore, the receiver can easily verify the integrity and identity of the messages.After mutual authentication, the vehicleVj obtains the local master key from the RSUi. In the next V2V communication, the vehicle Vj uses the RSUi’s local master key MKi to generate its pseudo-ID pIDj=pIDj1,pIDj2 and the corresponding private key SKj=SKj1,SKj2. Because of the use of identity-based signature algorithms, the receiver can easily verify the integrity of the traffic-related messages broadcasted by vehicle Vj. With the above analysis, we can find that our proposed protocol satisfies the requirements of message integrity and authentication.


## 5.4. Conditional Privacy-Preserving Property

As described earlier, in the authentication phase, the main role of RSU is to distribute the temporary public key to the vehicles nearby it. However, the privacy of the vehicle’s identity must be protected in this environment. The proposed authentication protocol achieves the conditional privacy-preserving property in two aspects.First, when a vehicleVj moves near the RSU, Vj needs to generate a fresh timestamp Tvj and uses it to calculate with the user’s real identity IDvj via the hash function to generate an authentication message. Since the timestamp Tvj used to calculate the authentication message is different each time and the hash function has a strong collision resistance property, the adversary cannot get the genuine identity information of the vehicle Vj through the message M1=TIDvj,rvj,Tvj,upukj,Certvj.Second, when the vehicleVj joins an RSU Ri’s group, it obtains the Ri’s local master key MKi and the corresponding temporary public key RPKi. And then, it generates a new pseudo-ID and the corresponding private key to sign the traffic-related message by the temporary master key of Ri. Since the traffic-related message is signed with different temporary master keys of Ri at different time, no entity except TA and Ri can establish the link between signatures and pseudo-IDs of the vehicle Vj. In summary, we can find that the proposed authentication protocol satisfies the conditional privacy-preserving property.


## 5.5. Traceability and Revocability

In the proposed authentication protocol, only the TA can get the authentic identityIDvj of the vehicle Vj from its authentication request message. Other participants (including vehicles and attackers) cannot extract the authentic identity IDvj of the vehicle Vj from the authentication request message.In addition, to protect privacy, the proposed protocol signs the traffic-related messages with different pseudo-IDs in the message signing phase. And the TA can get the authentic identityIDvj of the vehicle Vj by using equation (13). Consequently, when a vehicle is compromised, the TA could reveal its authentic identity to other entities. As a result, the revoked vehicle cannot join the RSU’s communication group to release any messages. This means that the proposed authentication protocol supports the traceability and revocability property.


## 6. Performance Evaluations

In this section, we evaluate the performance of the proposed authentication protocol and compare it with the related authentication protocols in terms of computation and transmission overheads. In our implementation, we use a PC with Intel Core i7 CPU 2.6 GHz and 8 GB memory to run the verification authentication protocol. Then, we use currently very popular experimental platforms, OMNeT++ and SUMO, to implement the proposed authentication protocol and test the indicators of communication performance and reliability.The various parameters used in the experimental simulation platform are shown in Table2. In the implementation of our protocol, the point multiplication operations of ECC are based on a 160-bit private key. And we select SHA-256 as the elementary hash function to structure the hash functions used in the proposed authentication protocol (i.e., h·, H·). We use the pairing-based cryptography library [37] for algorithm experimental verification. The computation overhead of the proposed authentication protocol consists of the vehicle authentication phase and the signature verification phase.Table 2
Parameters used in the experimental simulation platform.
Bit rate20 MbpsMinimum frequency5.890e9 HzMaximum transmission20 mWMinimum signal attenuation threshold-80 dBmApplication packet lengthUniform (256 bits, 15000 bits)


### 6.1. Computation Overhead Analysis

Table3 illustrates the experimental results for related pairing-based operations on the Intel Core i7 CPU 2.6 GHz machine. In our simulation, each randomized ID is 1024 bits, and the size of the ECC point is 160 bits. From the results, we observe that the bilinear pairing operation takes 3.61 milliseconds at the application server when averaging over 10 experiments to run the pairing-based operation. Figure 4 further shows the results on Intel Core i7 CPU 2.6 GHz for the above metrics. Furthermore, if the proposed authentication protocol is implemented on a more powerful high-end server, the running time will be greatly reduced, as shown in Table 3.Table 3
Execution time of the related pairing-based operations.
SymbolsExecution time for various operationsRunning time (ms)ThOne-way hash functionH· or h·<1TGhMap-to-point hash functionH1·<1TpairBilinear pairing computation3.61TaddAddition operation of points in ECC<1TexpExponential operation2.74TmulScalar multiplication of elliptic curves1.63TenSymmetric encryption algorithm AES (128-bit key)<1Figure 4
The relationship between the number of vehicles and the loss rate of messages.The main computational cost involved in the proposed authentication protocol is the registration phase, vehicle authentication phase, and message verification phase. However, in the proposed authentication protocol, it is not required to register a large number of vehicles and RSUs at the same time. Therefore, the time consumed in this phase does not require counting in the real-time running process. We focus on the time-consuming vehicle authentication phase and message signing and verification phases. In Table4, we illustrate the running time of the proposed authentication protocol in different phases.Table 4
Execution time of the proposed scheme in different phases.
Different phasesOn the OBU sideOn the RSU sideVehicle authentication4Th≈4msTmul+Th≈2.63msVehicle verificationTmul+Th≈2.63ms2Tmul+4Th≈7.26msMessage signing3Tmul+Tadd+Th+TGh≈7.89ms—Message verification3Tpair+Tmul+TGh+Th≈14.46ms—On the TA side, it is only involved in the system initialization phase and the vehicle verification phase. Note that the system initialization phase can be computed offline, and thus, we omit the computational overhead of this phase. And the TA’s computation cost in the vehicle verification phase is3Tmul+6Th≈10.89ms. On the OBU side, it is involved in the vehicle authentication phase, vehicle verification phase, message signing phase, and message verification phase. On the RSU side, it is only involved in the following stages: vehicle authentication and vehicle verification. From the proposed authentication, it is easy to find that the OBU is involved in almost all phases, except the identity tracking and revocation phase. Table 4 gives the detailed numbers.From Table4, we can see that if there are many message signatures for the OBU to verify, it will take a long time to run the message verification phase. To speed up the verification process, the proposed authentication protocol uses the batch authentication manner (see equation (12)) to reduce the time of pairing computation. We can analyze that the computation overhead in the single authentication manner is n+1Tmul+nTGh+3nTpair from equation (10). And the computation overhead in the batch authentication manner is only n+1Tmul+nTGh+3Tpair from equation (12). As a result, we can reduce the number of pairing computation from 3n to only 3. In Table 5, we have compared the computational cost of the proposed authentication protocol with the related works for each step.Table 5
Comparisons between the related research and our protocol.
ProtocolsVehicle authentication phaseMessage signing phaseWang and Yao [20]Tmul+Ten+Th≈3.63ms5Tmul+Tadd+2Th≈11.15msIslam et al. [21]3Ten+Tpair+Th≈7.61msTmul+2Ten+4Th≈7.63msAhamed et al. [29]3Tmul+2Tpair+2Th≈10.85ms3Texp+Tmul≈9.22msThe proposedTmul+Th≈2.63ms3Tmul+Tadd+Th+TGh≈7.89ms


### 6.2. Communication Overhead Analysis

We assume that the vehicles and RSUs have the same communication speed. Then, the communication overhead can be estimated by the length of messages. In our implementation, we adopt SHA-256 as the elementary hash function to structure the hash function, whose output length is 32 bytes. We use the vehicle identification number (VIN) [38] proposed by the International Organization for Standardization as the identifier of the vehicle. In Table 6, we illustrate the default length of the elements used in the proposed authentication protocol.Table 6
Length of the elements used in our protocol.
ElementIDvjRIDiTimestampPoint of ECCPseudo-IDNonceMs (traffic message)Length17 bytes20 bytes8 bytes40 bytes72 bytes8 bytes200 bytesIn the vehicle authentication phase, the communication overhead is mainly caused by the authentication request messageTIDvj,rvj,Tvj,upukj,Certvj. Just as summarized in the previous part, the sizes of TIDvj and Certvj are 32 bytes. And the sizes of rvj, Tvj, and upukj are 8 bytes, 8 bytes, and 40 bytes, respectively. Therefore, the size of the authentication message is 32+32+8+8+40=120bytes. Similarly, the size of the safety-related message pIDj,θj,Ms,RIDi is 40+40+200+20=300bytes. From Table 7, the communication cost of our protocol is slightly higher than that of the protocols in [25]. However, the proposed protocol provides more security of the vehicle authentication than the related research.Table 7
Communication cost comparisons between the related research and our protocol.
ProtocolsVehicle authenticationMessage authenticationWang and Yao [20]181 bytes352 bytesIslam et al. [21]324 bytes388 bytesAhamed et al. [29]108 bytes288 bytesThe proposed120 bytes300 bytes


### 6.3. Authentication Message Loss Rate Analysis

The message loss rate (MLR) is defined by formula (14), where N is used to represent the total number of authentication messages, Mrevi represents the total number of messages received by vehicle Vi, and Msendi represents the total number of authentication messages sent by the RSU.
(14)MLR=1N∑i=1NMreviMsendi.Figure4 shows the relationship between the message loss rate and the number of vehicles in the system. It can be seen from the simulation results that as the volume of message authentication services increases, the message loss rate is gradually increasing. In addition, in the same environment, we also compare the proposed protocol with the PKI-based protocol and that in [23] in terms of the message loss rate. It can be found that the message loss rate of the authentication protocol proposed in this paper is the lowest.


### 6.4. Authentication Protocol’s Delay Factor Analysis

In the simulation environment, we obtained the relationship between different factors and the delay of the authentication protocol by modifying the relevant parameters, such as the speed of the vehicle and the number of vehicles. Figure5 reflects the relationship between vehicle speed and message delay, and Figure 6 reflects the relationship between the number of vehicles and the delay of authentication messages.Figure 5
The relationship between the speed of vehicles and the delay of messages.Figure 6
The relationship between the number of vehicles and the delay of messages.It can be seen from Figure5 that when the speed is lower than 35 m/s (126 km/h), the increase in vehicle speed does not have much impact on the message delay of the authentication protocol. This shows that the proposed protocol can meet the demand for message delay under the condition of normal vehicle speed. From Figure 6, it is easy to see that when the proposed is used for high traffic density occasions, the authentication message delay time will increase a bit. However, when the number of vehicles in the area covered by an RSU is less than 80, the delay is still relatively small. In fact, the probability that the number of vehicles in the area covered by an RSU exceeds 80 is negligible. Obviously, the message delay of the proposed protocol is very small in the daily traffic environment.


## 6.1. Computation Overhead Analysis

Table3 illustrates the experimental results for related pairing-based operations on the Intel Core i7 CPU 2.6 GHz machine. In our simulation, each randomized ID is 1024 bits, and the size of the ECC point is 160 bits. From the results, we observe that the bilinear pairing operation takes 3.61 milliseconds at the application server when averaging over 10 experiments to run the pairing-based operation. Figure 4 further shows the results on Intel Core i7 CPU 2.6 GHz for the above metrics. Furthermore, if the proposed authentication protocol is implemented on a more powerful high-end server, the running time will be greatly reduced, as shown in Table 3.Table 3
Execution time of the related pairing-based operations.
SymbolsExecution time for various operationsRunning time (ms)ThOne-way hash functionH· or h·<1TGhMap-to-point hash functionH1·<1TpairBilinear pairing computation3.61TaddAddition operation of points in ECC<1TexpExponential operation2.74TmulScalar multiplication of elliptic curves1.63TenSymmetric encryption algorithm AES (128-bit key)<1Figure 4
The relationship between the number of vehicles and the loss rate of messages.The main computational cost involved in the proposed authentication protocol is the registration phase, vehicle authentication phase, and message verification phase. However, in the proposed authentication protocol, it is not required to register a large number of vehicles and RSUs at the same time. Therefore, the time consumed in this phase does not require counting in the real-time running process. We focus on the time-consuming vehicle authentication phase and message signing and verification phases. In Table4, we illustrate the running time of the proposed authentication protocol in different phases.Table 4
Execution time of the proposed scheme in different phases.
Different phasesOn the OBU sideOn the RSU sideVehicle authentication4Th≈4msTmul+Th≈2.63msVehicle verificationTmul+Th≈2.63ms2Tmul+4Th≈7.26msMessage signing3Tmul+Tadd+Th+TGh≈7.89ms—Message verification3Tpair+Tmul+TGh+Th≈14.46ms—On the TA side, it is only involved in the system initialization phase and the vehicle verification phase. Note that the system initialization phase can be computed offline, and thus, we omit the computational overhead of this phase. And the TA’s computation cost in the vehicle verification phase is3Tmul+6Th≈10.89ms. On the OBU side, it is involved in the vehicle authentication phase, vehicle verification phase, message signing phase, and message verification phase. On the RSU side, it is only involved in the following stages: vehicle authentication and vehicle verification. From the proposed authentication, it is easy to find that the OBU is involved in almost all phases, except the identity tracking and revocation phase. Table 4 gives the detailed numbers.From Table4, we can see that if there are many message signatures for the OBU to verify, it will take a long time to run the message verification phase. To speed up the verification process, the proposed authentication protocol uses the batch authentication manner (see equation (12)) to reduce the time of pairing computation. We can analyze that the computation overhead in the single authentication manner is n+1Tmul+nTGh+3nTpair from equation (10). And the computation overhead in the batch authentication manner is only n+1Tmul+nTGh+3Tpair from equation (12). As a result, we can reduce the number of pairing computation from 3n to only 3. In Table 5, we have compared the computational cost of the proposed authentication protocol with the related works for each step.Table 5
Comparisons between the related research and our protocol.
ProtocolsVehicle authentication phaseMessage signing phaseWang and Yao [20]Tmul+Ten+Th≈3.63ms5Tmul+Tadd+2Th≈11.15msIslam et al. [21]3Ten+Tpair+Th≈7.61msTmul+2Ten+4Th≈7.63msAhamed et al. [29]3Tmul+2Tpair+2Th≈10.85ms3Texp+Tmul≈9.22msThe proposedTmul+Th≈2.63ms3Tmul+Tadd+Th+TGh≈7.89ms


## 6.2. Communication Overhead Analysis

We assume that the vehicles and RSUs have the same communication speed. Then, the communication overhead can be estimated by the length of messages. In our implementation, we adopt SHA-256 as the elementary hash function to structure the hash function, whose output length is 32 bytes. We use the vehicle identification number (VIN) [38] proposed by the International Organization for Standardization as the identifier of the vehicle. In Table 6, we illustrate the default length of the elements used in the proposed authentication protocol.Table 6
Length of the elements used in our protocol.
ElementIDvjRIDiTimestampPoint of ECCPseudo-IDNonceMs (traffic message)Length17 bytes20 bytes8 bytes40 bytes72 bytes8 bytes200 bytesIn the vehicle authentication phase, the communication overhead is mainly caused by the authentication request messageTIDvj,rvj,Tvj,upukj,Certvj. Just as summarized in the previous part, the sizes of TIDvj and Certvj are 32 bytes. And the sizes of rvj, Tvj, and upukj are 8 bytes, 8 bytes, and 40 bytes, respectively. Therefore, the size of the authentication message is 32+32+8+8+40=120bytes. Similarly, the size of the safety-related message pIDj,θj,Ms,RIDi is 40+40+200+20=300bytes. From Table 7, the communication cost of our protocol is slightly higher than that of the protocols in [25]. However, the proposed protocol provides more security of the vehicle authentication than the related research.Table 7
Communication cost comparisons between the related research and our protocol.
ProtocolsVehicle authenticationMessage authenticationWang and Yao [20]181 bytes352 bytesIslam et al. [21]324 bytes388 bytesAhamed et al. [29]108 bytes288 bytesThe proposed120 bytes300 bytes


## 6.3. Authentication Message Loss Rate Analysis

The message loss rate (MLR) is defined by formula (14), where N is used to represent the total number of authentication messages, Mrevi represents the total number of messages received by vehicle Vi, and Msendi represents the total number of authentication messages sent by the RSU.
(14)MLR=1N∑i=1NMreviMsendi.Figure4 shows the relationship between the message loss rate and the number of vehicles in the system. It can be seen from the simulation results that as the volume of message authentication services increases, the message loss rate is gradually increasing. In addition, in the same environment, we also compare the proposed protocol with the PKI-based protocol and that in [23] in terms of the message loss rate. It can be found that the message loss rate of the authentication protocol proposed in this paper is the lowest.


## 6.4. Authentication Protocol’s Delay Factor Analysis

In the simulation environment, we obtained the relationship between different factors and the delay of the authentication protocol by modifying the relevant parameters, such as the speed of the vehicle and the number of vehicles. Figure5 reflects the relationship between vehicle speed and message delay, and Figure 6 reflects the relationship between the number of vehicles and the delay of authentication messages.Figure 5
The relationship between the speed of vehicles and the delay of messages.Figure 6
The relationship between the number of vehicles and the delay of messages.It can be seen from Figure5 that when the speed is lower than 35 m/s (126 km/h), the increase in vehicle speed does not have much impact on the message delay of the authentication protocol. This shows that the proposed protocol can meet the demand for message delay under the condition of normal vehicle speed. From Figure 6, it is easy to see that when the proposed is used for high traffic density occasions, the authentication message delay time will increase a bit. However, when the number of vehicles in the area covered by an RSU is less than 80, the delay is still relatively small. In fact, the probability that the number of vehicles in the area covered by an RSU exceeds 80 is negligible. Obviously, the message delay of the proposed protocol is very small in the daily traffic environment.


## 7. Conclusion

In the future smart transportation system, VANET will play an increasingly important role. The communication security and vehicle privacy protection in VANET are the fundamental requirements for its rapid development. In this paper, we proposed a bilinear pairing-based vehicle authentication and the message verification protocol to solve these problems. To protect user privacy, the proposed protocol uses a temporary pseudoidentity-based anonymous method in the message signing and verification phases. In addition, to improve the efficiency of the proposed authentication protocol, the recipients can verify the traffic-related messages with the single or batch authentication manner. Finally, we give the security and performance analysis of the proposed protocol. The security analysis shows that the proposed authentication protocol can resist various security threats and protect user privacy in the VANET environment. The performance analysis results show that the proposed scheme has lower communication overhead and computational cost when compared with the related protocol. Therefore, the proposed authentication protocol is very suitable for the VANET environment.



---

*Source: 6692568-2021-06-28.xml*