# An Improved and Privacy-Preserving Mutual Authentication Scheme with Forward Secrecy in VANETs

Authors: Mengting Yao; Xiaoming Wang; Qingqing Gan; Yijian Lin; Chengpeng Huang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Vehicular ad hoc network (VANETs) plays a major part in intelligent transportation to enhance traffic efficiency and safety. Security and privacy are the essential matters needed to be tackled due to the open communication channel. Most of the existing schemes only provide message authentication without identity authentication, especially the inability to support forward secrecy which is a major security goal of authentication schemes. In this article, we propose a privacy-preserving mutual authentication scheme with batch verification for VANETs which support both message authentication and identity authentication. More importantly, the proposed scheme achieves forward secrecy, which means the exposure of the shared key will not compromise the previous interaction. The security proof shows that our scheme can withstand various known security attacks, such as the impersonation attack and forgery attack. The experiment analysis results based on communication and computation cost demonstrate that our scheme is more efficient compared with the related schemes.


---

## Body

## 1. Introduction

With the rapid development of wireless communication technology, VANETs has drawn widespread attention in society over the decades. VANETs will bring great benefits to people in many ways. It can not only help drivers obtain traffic information in advance and provide better routes to ensure traffic safety and reduce traffic burden but also supply other services, such as toll collection and car infotainment and location-based services [1].In spite of the huge advantages offered by VANETs, it is still confronted with some problems that need to be solved such as privacy preserving and secure authentication since the communication in VANETs is on an open channel. Numerous schemes [2–5] have provided message authentication. The receiver must first verify the legality and integrity of the messages broadcast by other vehicles before it trusts them. However, in these schemes, the identity of the vehicle is not authenticated before it communicates with others. So, any vehicle can join the communication range and broadcast messages to others. If there are numerous vicious vehicles in communication area, a lot of false information will be generated and broadcast in the Internet of vehicle system, which has an adverse impact on the efficiency of the entire system. Therefore, the identity authentication before communication is also essential for VANETs.Recently, Cui et al. [6] proposed a mutual authentication scheme for VANETs. In their scheme, the mutual authentication process between the vehicle and TA needs to be executed before the vehicle can communicate with other vehicles and RSUs. However, we find their scheme actually has some security defects. It is vulnerable to forgery attack and impersonation attack and does not provide forward secrecy which is an important security property of authentication scheme. In addition, their scheme cannot meet batch verification. Batch verification allows the verifier to check the validity of many signatures at the same time, which can greatly reduce delay. Many schemes [7–10] with batch verification have been proposed using bilinear pairing or based on elliptic curve.In this paper, we present an improved mutual authentication scheme with forward secrecy for VANETs in order to withstand various known attacks. Concretely, the main contributions of our scheme are given as follows:(1)
We identify and analyze security flaws in Cui et al.’s scheme for VANETs. Their scheme exits forgery attack and impersonation attack.(2)
We propose an improved mutual authentication scheme for VANETs to resist the security attacks in Cui et al.’s scheme. Our solution provides not only message authentication but also identity authentication. Moreover, our scheme can also achieve batch verification without using bilinear pairing.(3)
Finally, the proposed scheme can provide stronger security property, forward secrecy. That is to say, even if the current shared key is exposed, the adversary cannot construct the previous shared key. The security proof and analysis indicate that our scheme is secure. Performance evaluation shows that our scheme has low computation and communication overhead.The rest of the paper is organized as follows. The related work is introduced in Section2. Section 3 presents the system model, security assumptions, and security requirements. In Section 4, we briefly review the scheme of Cui et al. In Section 5, we analyze the security attacks of their scheme. Section 6 introduces the improved mutual authentication scheme with forward secrecy. In Section 7, we give the security proof and analysis. Section 8 presents the performance analysis. Finally, Section 9 shows the conclusion of this paper.


## 2. Related Work

In recent years, the issues of privacy protection and secure authentication for VANETs have drawn more and more attention. To settle the problems mentioned above, many signature and authentication schemes have been proposed. For example, in 2006, a ring signature scheme was first proposed by Gamage et al. [11] to conceal the signer’s real identity. However, their scheme is not suitable for VANETs because no entity could trace the real identities of vehicles when false messages are sent by malicious vehicles caused damage. A year later, a PKI-based authentication scheme using anonymous certificates was proposed in [12]. However, in this scheme, vehicles need to store many public-private keys and corresponding anonymous certificates, which would impose storage burden to vehicles and huge certification management burden to TA. Later, Lin et al. [13] introduced a privacy-preserving authentication protocol based on a group signature [14]. Then, an efficient conditional privacy-preserving authentication (CPPA) scheme using bilinear pairing was proposed in [15]. In this scheme, the RSU needs to update the temporary anonymous certificates periodically and stores them, which would cause huge burden for the RSU and have low efficiency.In order to mitigate the certificate management problem, many identity-based schemes were proposed such as [16–21]. Zhang et al. [16] introduced an identity-based solution with batch verification called IBV. In their paper, the signature key of the vehicle is generated based on its identity. Both vehicles and RSUs do not need to save any certificate. In addition, their solution can simultaneously verify many received messages, which greatly increases the efficiency of verification. Then, the flaws of Zhang et al.’s IBV scheme [16] were found by Lee and Lai [17]. First of all, Zhang et al.’s scheme is subject to the replaying attack. Secondly, the signature nonrepudiation is not achieved in Zhang et al.’s BIV scheme. So, Lee and Lai proposed an improved scheme to resist the above two types of attacks without extra overhead. Unfortunately, Zeng et al. [18] showed Lee and Lai’s scheme [17] exits some weakness in VANETs. Firstly, Lee and Lai’s approach did not achieve privacy preserving because anyone who only knows the public system parameters can calculate the real identity of the sender. Secondly, a malicious vehicle can imitate a valid vehicle to send false messages and even can use an arbitrary identity to escape the TA tracking. For the above weakness in VANETs, Zeng et al. [18] proposed an improved IBV scheme.Soon after, many scholars combined certificateless cryptography and aggregation signature and further constructed various certificateless aggregation signature (CLAS) schemes [22–30]. For example, a CLAS scheme was proposed by Xiong et al. [22]; however, He et al. [23] pointed out that the adversary could forge a legal signature of any message in their scheme and presented an improved CLAS scheme. Unluckily, a security drawback in He et al.’s scheme [23] was found by Li et al. [24]. Xu et al. [30] found that the scheme of Horng et al. [25] cannot resist any type of adversary in the certificateless security model and built a new CLAS scheme. Lately, Cui et al. [26] presented an efficient CLS scheme for VANETs, which was proved to be insecure by Kamil and Ogundoyin [27].To improve the efficiency, some schemes [31–34] have been designed shortly after. For example, in 2015, a new ID-based CPPA scheme for VANETs was firstly introduced by He et al. [31] based on Elliptic Curve Cryptography (ECC) without bilinear pairing. Cui et al. [35] built a secure privacy-preserving authentication (SPACF) scheme for VANETs using cuckoo filter and binary search methods to enhance the efficiency of batch verification. Azees et al. [36] constructed an efficient anonymous authentication (EAAP) protocol with an efficient conditional privacy tracking mechanism for VANETs. Nevertheless, they did not provide batch signatures verification. Soon after, Zhong et al. [37] proposed a privacy-preserving authentication scheme with full aggregation. In their scheme, the RSU could aggregate the signatures of vehicles which are passing through it. However, this scheme has low efficiency due to the use of map-to-point hash functions and bilinear pairing. Later, Ali and Li [38] introduced an efficient CPPA scheme for VANETs based on general one-way hash functions with lower computation overhead. A conditional privacy-preserving authentication protocol based on Chinese remainder theorem (CRT) for VANETs was elaborated by Zhang et al. [39]. In their protocol, they eliminated the need for preloading the master key of the system into Tamper-Proof Device (TPD) of vehicle, thus avoiding the risk of compromising a vehicle’s TPD leading to entire system failure.Some mutual authentication schemes [40–42] in other different scenarios have been proposed. Recently, Cui et al. [6] introduced a secure mutual authentication for VANETs. However, we find their scheme exits some security weaknesses, such as forgery attack and impersonation attack. In this paper, we introduce an improved mutual authentication scheme with forward secrecy. Meanwhile, we provide batch verification, which greatly increases the efficiency of verification.


## 3. Preliminaries

In this part, the system model and security requirements will be given.


### 3.1. System Model

As shown in Figure1, a typical architecture of VANETs is made up of the following units:(1)
Trusted authority (TA): TA is a trusted third party with large storage capacity and powerful computing capabilities. It is in charge of generating system parameters and authenticating the identity of vehicles. Furthermore, the true identities of vehicles could only be revealed by TA.(2)
Road side unit (RSU): RSU is the roadside infrastructure unit and not fully trusted. It can serve as a bridge between TA and the vehicle communication. And, it can also monitor suspicious message signatures broadcast by vehicles.(3)
Vehicles: each vehicle communicates with other vehicles or RSUs by an open dedicated shortrange communication (DSRC) protocol [43].Figure 1
System model.


### 3.2. Security Assumptions

The security of our scheme is based on the elliptic curve discrete logarithm (ECDL) problem and the computational Diffie–Hellman (CDH) problem.(1)
ECDL problem: the ECDL problem is to calculates, where s satisfies the known point Q=s⋅P on the curve(2)
CDH problem: the CDH problem is to obtain the pointα⋅β⋅P∈G given two random points α⋅P, β⋅P∈G, where α and β are secret


### 3.3. Security Requirements

On the basis of the previous works for VANETs, the following secure requirements should be met in the proposed scheme:(1)
Message authentication: the receiver must check the integrity and validity of the message signatures sent by other vehicles before it trusts them(2)
Identity authentication: the vehicle needs to complete identity authentication to prove it is legal before allowing it to communicate with other RSUs and vehicles(3)
Traceability: if a malicious vehicle transmits a false message to mislead others, the true identity of it could be traced by TA(4)
Forward secrecy: even if the adversary knows the current shared key, it is impossible to generate the pervious shared key(5)
Resistance against numerous types of attacks: the proposed scheme should be capable of withstanding the following security attacks that exist in VANETs(1)
Replay attack: an adversary may gather and save a message signature and try to send it after the primitive signature becomes invalid(2)
Impersonate attack: a malicious vehicle could diffuse a legal vehicle to send fake messages in order to make profits.(3)
Forgery attack: an adversary could forge some secret information such as identity or authentication credential to generate a signature without being detected(4)
Known key secrecy attack: an adversary could construct the current key if it obtains the key generated in the previous interaction


## 3.1. System Model

As shown in Figure1, a typical architecture of VANETs is made up of the following units:(1)
Trusted authority (TA): TA is a trusted third party with large storage capacity and powerful computing capabilities. It is in charge of generating system parameters and authenticating the identity of vehicles. Furthermore, the true identities of vehicles could only be revealed by TA.(2)
Road side unit (RSU): RSU is the roadside infrastructure unit and not fully trusted. It can serve as a bridge between TA and the vehicle communication. And, it can also monitor suspicious message signatures broadcast by vehicles.(3)
Vehicles: each vehicle communicates with other vehicles or RSUs by an open dedicated shortrange communication (DSRC) protocol [43].Figure 1
System model.


## 3.2. Security Assumptions

The security of our scheme is based on the elliptic curve discrete logarithm (ECDL) problem and the computational Diffie–Hellman (CDH) problem.(1)
ECDL problem: the ECDL problem is to calculates, where s satisfies the known point Q=s⋅P on the curve(2)
CDH problem: the CDH problem is to obtain the pointα⋅β⋅P∈G given two random points α⋅P, β⋅P∈G, where α and β are secret


## 3.3. Security Requirements

On the basis of the previous works for VANETs, the following secure requirements should be met in the proposed scheme:(1)
Message authentication: the receiver must check the integrity and validity of the message signatures sent by other vehicles before it trusts them(2)
Identity authentication: the vehicle needs to complete identity authentication to prove it is legal before allowing it to communicate with other RSUs and vehicles(3)
Traceability: if a malicious vehicle transmits a false message to mislead others, the true identity of it could be traced by TA(4)
Forward secrecy: even if the adversary knows the current shared key, it is impossible to generate the pervious shared key(5)
Resistance against numerous types of attacks: the proposed scheme should be capable of withstanding the following security attacks that exist in VANETs(1)
Replay attack: an adversary may gather and save a message signature and try to send it after the primitive signature becomes invalid(2)
Impersonate attack: a malicious vehicle could diffuse a legal vehicle to send fake messages in order to make profits.(3)
Forgery attack: an adversary could forge some secret information such as identity or authentication credential to generate a signature without being detected(4)
Known key secrecy attack: an adversary could construct the current key if it obtains the key generated in the previous interaction


## 4. Review of Cui et al.’s Mutual Authentication Scheme

Recently, Cui et al. [6] proposed a secure mutual authentication scheme for VANETs. In this section, we briefly review their scheme.


### 4.1. TA Initialization Phase

Step 1: TA picks two large prime numbersp,q, an additive group G with order q, which is formed by points on the elliptic curve E (y2=x3+ax+bmodp, where a,b∈Fp). P is a generator of G.Step 2: TA randomly picks a numbers∈Zq∗ as its secret key and calculates Ppub=s⋅P as its public key.Step 3: TA selects symmetric encryption functionEπ⋅/Dπ (.) and several hash functions: h:G⟶Zq, H1key⋅:0,1∗⟶0,1l, H2⋅:0,1∗⟶0,1l′, H3⋅:0,1∗⟶Γ, where H1key is a hash with key.Step 4: finally, TA publishesψ=a,b,q,p,P,h,H1key⋅,H2⋅,H3⋅ as public system parameters.


### 4.2. Vehicle Setup Phase

The vehicleVi first transmits real identity RID to TA. Then, TA calculates interpseudonym identity IPIDVi=H1RID‖VPi, where VPi is the valid period. Then, TA sends IPIDVi to Vi by a secure channel. Finally, Vi randomly picks an integer λi∈Zq∗ as the encryption key and stores λi and IPIDVi into the TPD. Simultaneously, TA saves the tuple (RID, VPi, IPIDVi, λi).


### 4.3. Mutual Authentication Phase

The mutual authentication process is completed between TA and the vehicleVi. The details are as follows:Step 1: firstly,Vi picks a random integer Nv∈Zq∗ and calculates a hash code HC=hλi‖Nv. Then, it encrypts Nv,HC, and IPIDVi using the shared key λi. Next, Vi sends the messages EλiNv‖HC‖IPIDVi‖IDTA‖IPIDVi‖T1 to nearby RSU, where IDTA is the identity of TA, and T1 is the current timestamp.Step 2: when RSU obtains a message fromVi, it first inspects the validity of the timestamp. If the timestamp is expired, it fails. Otherwise, RSU attaches its identity IDRSU and a new timestamp T2 to the message. Then, it uses its private key rsk shared with TA to encrypt messages. Finally, it broadcasts the encrypted messages ErskEλiNv‖HC‖IPIDVi‖IDTA‖IPIDVi‖IDRSU‖T2 to TA. When TA receives the messages, it first decrypts to get the tuple EλiNv‖HC‖IPIDVi‖IDTA‖IPIDVi‖IDRSU‖T2. Next, it continues to decrypt EλiNv‖HC‖IPIDVi to get HC and Nv. Then, it computes HC′=hλi‖Nv. If HC′=HC, it continues to execute the next step; else it aborts.Step 3: TA calculates the authentication codeAC=hHC‖s. Then, it sends the encrypted messages ErskEλiEsIPIDVi‖T3‖Lifetime‖AC‖IDTA to the nearby RSU, where Lifetime is the valid period of AC.Step 4: as the RSU receives the messages sent by TA, it decrypts the messages to getEλiEsIPIDVi‖T3‖Lifetime‖AC‖IDTA. Then, RSU authenticates IDTA if IDTA is invalid, it fails; else it sends EλiEsIPIDVi‖T3‖Lifetime‖AC to Vi. After Vi receives the messages, it first uses λi to decrypt them and then uses the system public key Ppub to decrypt EsIPIDVi‖T3‖Lifetime‖AC to get IPIDVi. If it is equal to the IPIDVi stored in the TPD, the vehicle Vi successfully completes the mutual authentication with TA and is allowed to broadcast messages to other vehicles and RSU.


### 4.4. Vehicle Signature Phase

In this part,Vi randomly chooses a number ri∈Zq∗ and computes Ri=ri⋅P. Next, Vi calculates its public pseudonym identity PPIDVi=H2IPIDVi‖Ri‖Ti. Then, it generates the signature δi=hPPIDVi‖Mi‖AC‖Ri and broadcasts the messages Mi,δi,PPIDVi,AC,Ri to other RSUs and vehicles.


### 4.5. Message Verification Phase

As RSU obtains the messagesMi,δi,PPIDVi,AC,Ri from Vi, it calculates δi∗=hPPIDVi‖Mi‖AC‖Ri. If δi∗=δi, the message Mi is considered valid; otherwise, the verifier directly discards the messages.


## 4.1. TA Initialization Phase

Step 1: TA picks two large prime numbersp,q, an additive group G with order q, which is formed by points on the elliptic curve E (y2=x3+ax+bmodp, where a,b∈Fp). P is a generator of G.Step 2: TA randomly picks a numbers∈Zq∗ as its secret key and calculates Ppub=s⋅P as its public key.Step 3: TA selects symmetric encryption functionEπ⋅/Dπ (.) and several hash functions: h:G⟶Zq, H1key⋅:0,1∗⟶0,1l, H2⋅:0,1∗⟶0,1l′, H3⋅:0,1∗⟶Γ, where H1key is a hash with key.Step 4: finally, TA publishesψ=a,b,q,p,P,h,H1key⋅,H2⋅,H3⋅ as public system parameters.


## 4.2. Vehicle Setup Phase

The vehicleVi first transmits real identity RID to TA. Then, TA calculates interpseudonym identity IPIDVi=H1RID‖VPi, where VPi is the valid period. Then, TA sends IPIDVi to Vi by a secure channel. Finally, Vi randomly picks an integer λi∈Zq∗ as the encryption key and stores λi and IPIDVi into the TPD. Simultaneously, TA saves the tuple (RID, VPi, IPIDVi, λi).


## 4.3. Mutual Authentication Phase

The mutual authentication process is completed between TA and the vehicleVi. The details are as follows:Step 1: firstly,Vi picks a random integer Nv∈Zq∗ and calculates a hash code HC=hλi‖Nv. Then, it encrypts Nv,HC, and IPIDVi using the shared key λi. Next, Vi sends the messages EλiNv‖HC‖IPIDVi‖IDTA‖IPIDVi‖T1 to nearby RSU, where IDTA is the identity of TA, and T1 is the current timestamp.Step 2: when RSU obtains a message fromVi, it first inspects the validity of the timestamp. If the timestamp is expired, it fails. Otherwise, RSU attaches its identity IDRSU and a new timestamp T2 to the message. Then, it uses its private key rsk shared with TA to encrypt messages. Finally, it broadcasts the encrypted messages ErskEλiNv‖HC‖IPIDVi‖IDTA‖IPIDVi‖IDRSU‖T2 to TA. When TA receives the messages, it first decrypts to get the tuple EλiNv‖HC‖IPIDVi‖IDTA‖IPIDVi‖IDRSU‖T2. Next, it continues to decrypt EλiNv‖HC‖IPIDVi to get HC and Nv. Then, it computes HC′=hλi‖Nv. If HC′=HC, it continues to execute the next step; else it aborts.Step 3: TA calculates the authentication codeAC=hHC‖s. Then, it sends the encrypted messages ErskEλiEsIPIDVi‖T3‖Lifetime‖AC‖IDTA to the nearby RSU, where Lifetime is the valid period of AC.Step 4: as the RSU receives the messages sent by TA, it decrypts the messages to getEλiEsIPIDVi‖T3‖Lifetime‖AC‖IDTA. Then, RSU authenticates IDTA if IDTA is invalid, it fails; else it sends EλiEsIPIDVi‖T3‖Lifetime‖AC to Vi. After Vi receives the messages, it first uses λi to decrypt them and then uses the system public key Ppub to decrypt EsIPIDVi‖T3‖Lifetime‖AC to get IPIDVi. If it is equal to the IPIDVi stored in the TPD, the vehicle Vi successfully completes the mutual authentication with TA and is allowed to broadcast messages to other vehicles and RSU.


## 4.4. Vehicle Signature Phase

In this part,Vi randomly chooses a number ri∈Zq∗ and computes Ri=ri⋅P. Next, Vi calculates its public pseudonym identity PPIDVi=H2IPIDVi‖Ri‖Ti. Then, it generates the signature δi=hPPIDVi‖Mi‖AC‖Ri and broadcasts the messages Mi,δi,PPIDVi,AC,Ri to other RSUs and vehicles.


## 4.5. Message Verification Phase

As RSU obtains the messagesMi,δi,PPIDVi,AC,Ri from Vi, it calculates δi∗=hPPIDVi‖Mi‖AC‖Ri. If δi∗=δi, the message Mi is considered valid; otherwise, the verifier directly discards the messages.


## 5. Attacks on Cui et al.’s Mutual Authentication Scheme

In this section, we describe some attacks existing in the scheme of Cui et al. [6]. The details are as follows.


### 5.1. Forgery Attack

According to our analysis, Cui et al.’s scheme exits forgery attack in VANETs. We consider a case in which an attacker forges the authentication code. Then, it can use the authentication code to generate a message signature and the signature can be successfully verified. The details are described as follows.Suppose an attacker forges an arbitrary authentication codeAC∗. Then, it selects a random integer ri∈Zq∗, computes Ri=ri⋅P, and generates a signature of false message Mi∗ as the following equation:(1)δi∗=hPPIDViMi∗AC∗Ri.Finally, it sends the messagesMi∗,δi∗,PPIDVi,AC∗,Ri to other vehicles and RSUs.After RSU receives the messagesMi∗,δi∗,PPIDVi,AC∗,Ri, it will check that the following equation is satisfied; hence, the message Mi∗ will be considered valid:(2)δi∗=hPPIDViMi∗AC∗Ri.From the above, we notice that a vehicle without executing the mutual authentication process can forge the authentication code and uses it as a credential to successfully communicate with others. Essentially, this is because RSU can only verify whether AC sent byVi has been tampered with the public channel, but cannot verify AC which is distributed by TA.


### 5.2. Impersonation Attack

We find the scheme of Cui et al. cannot withstand the impersonation attack in VANETs. A malicious vehicle could imitate other valid vehicles to broadcast messages. The details of impersonation attack are as follows.Suppose an attacker intercepts the authentication code AC and the pseudonym identityPPIDVi on the open channel, and it executes the following steps:(1)
First, it randomly selects an integerri∈Zq∗ and calculates Ri=ri⋅P.(2)
Next, it uses the intercepted AC andPPIDVi to generate the signature of an arbitrary message Mi∗ as δi∗=hPPIDVi‖Mi∗‖AC‖Ri. Subsequently, it broadcasts the messages Mi∗,δi∗,PPIDVi,AC,Ri to nearby vehicles and RSUs.When the verifier receives the messagesMi∗,δi∗,PPIDVi,AC,Ri, it will consider the messages to be valid by checking that the following equation holds(3)δi∗=hPPIDViMi∗ACRi.As a result, when the messageMi∗ caused an accident, the TA needs to obtain the true identity of the sender from PPIDVi in order to trace responsibility. However, the TA will obtain the real identity IPIDVi and think the message Mi∗ is sent by Vi. Thus, the attacker is able to imitate any vehicle to generate valid signatures of fake messages and escape accountability. Therefore, Cui et al.’s scheme is prone to impersonation attack.


## 5.1. Forgery Attack

According to our analysis, Cui et al.’s scheme exits forgery attack in VANETs. We consider a case in which an attacker forges the authentication code. Then, it can use the authentication code to generate a message signature and the signature can be successfully verified. The details are described as follows.Suppose an attacker forges an arbitrary authentication codeAC∗. Then, it selects a random integer ri∈Zq∗, computes Ri=ri⋅P, and generates a signature of false message Mi∗ as the following equation:(1)δi∗=hPPIDViMi∗AC∗Ri.Finally, it sends the messagesMi∗,δi∗,PPIDVi,AC∗,Ri to other vehicles and RSUs.After RSU receives the messagesMi∗,δi∗,PPIDVi,AC∗,Ri, it will check that the following equation is satisfied; hence, the message Mi∗ will be considered valid:(2)δi∗=hPPIDViMi∗AC∗Ri.From the above, we notice that a vehicle without executing the mutual authentication process can forge the authentication code and uses it as a credential to successfully communicate with others. Essentially, this is because RSU can only verify whether AC sent byVi has been tampered with the public channel, but cannot verify AC which is distributed by TA.


## 5.2. Impersonation Attack

We find the scheme of Cui et al. cannot withstand the impersonation attack in VANETs. A malicious vehicle could imitate other valid vehicles to broadcast messages. The details of impersonation attack are as follows.Suppose an attacker intercepts the authentication code AC and the pseudonym identityPPIDVi on the open channel, and it executes the following steps:(1)
First, it randomly selects an integerri∈Zq∗ and calculates Ri=ri⋅P.(2)
Next, it uses the intercepted AC andPPIDVi to generate the signature of an arbitrary message Mi∗ as δi∗=hPPIDVi‖Mi∗‖AC‖Ri. Subsequently, it broadcasts the messages Mi∗,δi∗,PPIDVi,AC,Ri to nearby vehicles and RSUs.When the verifier receives the messagesMi∗,δi∗,PPIDVi,AC,Ri, it will consider the messages to be valid by checking that the following equation holds(3)δi∗=hPPIDViMi∗ACRi.As a result, when the messageMi∗ caused an accident, the TA needs to obtain the true identity of the sender from PPIDVi in order to trace responsibility. However, the TA will obtain the real identity IPIDVi and think the message Mi∗ is sent by Vi. Thus, the attacker is able to imitate any vehicle to generate valid signatures of fake messages and escape accountability. Therefore, Cui et al.’s scheme is prone to impersonation attack.


## 6. The Proposed Scheme

To overcome the security attacks in Cui et al.’s scheme [6], we construct an improved mutual authentication scheme with forward secrecy. Table 1 displays the notations and descriptions used in the proposed scheme.Table 1
Notations and descriptions in our scheme.
NotationsDescriptionsTAA trusted authorityViTheith vehicleGCycle addition group based on ecliptic curvePA generator ofGsTThe private key of TAsiThe private key ofViPpubThe public key of TAλiThe shared key betweenVi and TArskThe shared key between RSU and TAPIDiThe pseudonym identity ofViRIDThe real identity of vehicleSKiThe signature key ofVi


### 6.1. System Initialization

Step 1: TA picks two large prime numbersp,q and an additive group G with order q formed by points on the elliptic curve E (y2=x3+ax+bmodp, where a,b∈Fp). Then, TA picks P as a generator of G.Step 2: TA randomly selects a numbersT∈Zq∗ as its secret key and calculates Ppub=sT⋅P as the corresponding public key.Step 3: TA chooses some hash functions:H0⋅:G⟶Zq∗, H1⋅:G×G⟶Zq∗, H2⋅:G×G×0,1∗⟶Zq∗, H3⋅:G×G×G×Zq∗⟶Zq∗, and H4⋅:0,1∗⟶Zq∗. The system parameters ψ=a,b,q,p,P,E,G,H0,H1⋅,H2⋅,H3⋅,H4⋅,Ppub are published.


### 6.2. Vehicle Registration

In this section, the vehicleVi registers with the TA to get the shared key λi, and the process is given as follows.The vehicle randomly picks an integersi∈Zq∗ as its secret key and computes PIDi,1=si⋅P. Subsequently, it transmits the real identity RID and PIDi,1 to TA via a secure channel. When receiving the information, TA randomly picks an integer λi∈Zq∗ as the key shared with the vehicle Vi, and calculates PIDi,2=RID⊕H0sT⋅PIDi,1‖VPi, where VPi is the valid period of PIDi,1 and PIDi,2. Next, TA sends the shared key λi and pseudonym identity PIDi=PIDi,1,PIDi,2,VPi to Vi. Meanwhile, TA saves the tuple (RID,VPi,λi).


### 6.3. Mutual Authentication and Signing Key Generation

As shown in Table2, the vehicle Vi completes the mutual authentication process with TA by the help of RSU. After mutual authentication, Vi is considered legal and generates the signing key SKi.Step 1: the vehicleVi first randomly selects numbers Nv,α∈Zq∗ and computes η1=H2PIDi‖λi‖Nv‖α⋅P. Then, it sends the messages Φ1=η1,PIDi,Nv,α⋅P,T1 to nearby RSU, where T1 is the current timestamp.Step 2: after getting the messagesΦ1, RSU first checks the validity of T1. If T1 is invalid, it ends; otherwise, it chooses a random number Nr∈Zq∗ and calculates η2=H4IDRSU‖rsk‖Nr, where IDRSU is the identity of RSU and rsk is only known to TA and RSU. Finally, RSU sends the messages Φ2=η1,PIDi,Nv,α⋅P,η2,IDRSU,Nr,T2 to TA, where T2 is current timestamp.Step 3: when TA receives the messagesΦ2, it first inspects the expiration date of T2. If T2 is expired, it aborts; else it checks the identity of the RSU. It computes η2∗=H4IDRSU‖rsk‖Nr; if η2∗≠η2, it aborts; else, it continues to authenticate Vi. TA computes η1∗=H2PIDi‖λi‖Nv‖α⋅P; if η1∗≠η1, it ends; otherwise, Vi is successfully authenticated by TA. Then, TA randomly selects numbers β,ωi∈Zq∗ and computes Wi=ωi⋅P,Xi=H1PIDi‖Wi,Si′=ωi+sT⋅Xi,Q=H3λi‖PIDi‖Nv‖Si′‖β⋅P‖Wi,η3=H4rsk‖Nr, and η4=Si′⊕β⋅α⋅P. Finally, TA sends the messages Φ3=η3,η4,Q,β⋅P,Wi,T3 to nearby RSU, where T3 is current timestamp. At the same time, TA updates the shared key λi∗ as H0β⋅α⋅P.Step 4: upon getting the messageΦ3, RSU first checks the freshness of T3 and then calculates η3∗=H4rsk‖Nr. If η3∗=η3, it forwards the messages Φ4=η4,Q,β⋅P,Wi,T4 to the vehicle Vi, otherwise it aborts.Step 5: upon receiving the messageΦ4,Vi first inspects the validity of T4. Then, it retrieves Si′=η4⊕α⋅β⋅P and computes Q∗=H3λi‖PIDi‖Nv‖Si′‖β⋅P‖Wi. If Q∗≠Q, it ends; else, the vehicle Vi successfully authenticates the TA and updates λi∗=H0α⋅β⋅P. Finally, Vi generates the signing key SKi=si−1⋅Si′=si−1⋅ωi+sT⋅Xi.Table 2
Mutual authentication phase between TA and the vehicle.
ViRSUTASelectsNv,α∈Zq∗Computes η1=H2PIDi‖λi‖Nv‖α⋅P⟶Φ1=η1,PIDi,α⋅P,T1VerifiesT1∗−T1≤ΔTSelects Nr∈Zq∗,Computes η2=H4IDRSU‖rsk‖Nv⟶Φ2=Φ1,η2,IDRSU,T2First verifiesT2∗−T2≤ΔTComputes η2∗=H4IDRSU‖rsk‖Nr,Checks η2∗=?η2Computes η1∗=H2PIDi‖λi‖Nv‖α⋅P,Checks η1∗=?η1Selects β,ωi∈Zq∗Computes Wi=ωi⋅PComputes Xi=H1PIDi‖Wi,Si′=ωi+sT⋅XiComputes Q=H3λi‖PIDi‖Nv‖Si′‖β⋅P‖WiComputes η3=H4rsk‖NrComputes η4=Si′⊕β⋅α⋅PUpdates λi∗=H0β⋅α⋅P←Φ3=η3,η4,Q,β⋅P,Wi,T3VerifiesT3∗−T3≤ΔTComputes η3∗=H4rsk‖NrChecks η3∗=?η3←Φ4=η4,Q,β⋅P,Wi,T4T4∗−T4≤ΔTRetrieves Si′=η4⊕α⋅β⋅PChecks Q∗=?QUpdates λi∗=H0α⋅β⋅PGenerates the signing key:SKi=si−1⋅Si′=si−1⋅ωi+sT⋅Xi


### 6.4. Message Signing

When the vehicleVi is ready to broadcast message Mi to others, it picks a random integer ri∈Zq∗ and computes Ri=ri⋅PIDi,1,Yi=H2Mi‖PIDi‖Ri‖Ti. Then, it generates the signature σi=SKi+ri⋅Yi, where Ti is the current time. Subsequently, it broadcasts the messages Mi,σi,PIDi,Ri,Wi,Ti to nearby vehicles and RSUs.


### 6.5. Message Verification

When the RSU obtains the messagesMi,σi,PIDi,Ri,Wi,Ti, it first checks the freshness of Ti and valid period VPi of PIDi. Then, it verifies the signature by checking whether σi⋅PIDi,1=Wi+Xi⋅Ppub+Yi⋅Ri satisfies. If it satisfies, the RSU accepts the messages; otherwise, it directly discards the messages. The correctness proof of the above equation is as follows.


#### 6.5.1. Correctness Proof

(4)σi⋅PIDi,1=SKi+ri⋅Yi⋅PIDi,1=si−1⋅Si′+ri⋅Yi⋅PIDi,1=si−1⋅wi+sT⋅Xi⋅si⋅P+ri⋅Yi⋅PIDi,1=wi+sT⋅Xi⋅P+Yi⋅Ri=Wi+Xi⋅Ppub+Yi⋅Ri.


### 6.6. Batch Verification

When receiving lots of messages from multiple vehicles, the RSU can verify these messages in batch to effectively reduce the computation cost and raise the efficiency of verification. Assume that the RSU obtains the messages fromn vehicles, which are denoted as Mi,σi,PIDi,Ri,Wi,Ti, where i=1,2,…,n. Similar to the single verification, the process of batch verification is executed by the verifier as follows.The RSU first checks the freshness ofTi and valid period VPi of PIDi; if Ti is not fresh or VPi is expired, RSU discards this message; otherwise, it randomly selects a vector vi=v1,v2,…,vn, where vi∈1,2ε and ε is a tiny number. Then, it performs batch verification by inspecting the validity of the following equation:(5)∑i=1nvi⋅σi⋅PIDi,1=∑i=1nvi⋅Wi+∑i=1nvi⋅Xi⋅Ppub+∑i=1nvi⋅Yi⋅Ri.


## 6.1. System Initialization

Step 1: TA picks two large prime numbersp,q and an additive group G with order q formed by points on the elliptic curve E (y2=x3+ax+bmodp, where a,b∈Fp). Then, TA picks P as a generator of G.Step 2: TA randomly selects a numbersT∈Zq∗ as its secret key and calculates Ppub=sT⋅P as the corresponding public key.Step 3: TA chooses some hash functions:H0⋅:G⟶Zq∗, H1⋅:G×G⟶Zq∗, H2⋅:G×G×0,1∗⟶Zq∗, H3⋅:G×G×G×Zq∗⟶Zq∗, and H4⋅:0,1∗⟶Zq∗. The system parameters ψ=a,b,q,p,P,E,G,H0,H1⋅,H2⋅,H3⋅,H4⋅,Ppub are published.


## 6.2. Vehicle Registration

In this section, the vehicleVi registers with the TA to get the shared key λi, and the process is given as follows.The vehicle randomly picks an integersi∈Zq∗ as its secret key and computes PIDi,1=si⋅P. Subsequently, it transmits the real identity RID and PIDi,1 to TA via a secure channel. When receiving the information, TA randomly picks an integer λi∈Zq∗ as the key shared with the vehicle Vi, and calculates PIDi,2=RID⊕H0sT⋅PIDi,1‖VPi, where VPi is the valid period of PIDi,1 and PIDi,2. Next, TA sends the shared key λi and pseudonym identity PIDi=PIDi,1,PIDi,2,VPi to Vi. Meanwhile, TA saves the tuple (RID,VPi,λi).


## 6.3. Mutual Authentication and Signing Key Generation

As shown in Table2, the vehicle Vi completes the mutual authentication process with TA by the help of RSU. After mutual authentication, Vi is considered legal and generates the signing key SKi.Step 1: the vehicleVi first randomly selects numbers Nv,α∈Zq∗ and computes η1=H2PIDi‖λi‖Nv‖α⋅P. Then, it sends the messages Φ1=η1,PIDi,Nv,α⋅P,T1 to nearby RSU, where T1 is the current timestamp.Step 2: after getting the messagesΦ1, RSU first checks the validity of T1. If T1 is invalid, it ends; otherwise, it chooses a random number Nr∈Zq∗ and calculates η2=H4IDRSU‖rsk‖Nr, where IDRSU is the identity of RSU and rsk is only known to TA and RSU. Finally, RSU sends the messages Φ2=η1,PIDi,Nv,α⋅P,η2,IDRSU,Nr,T2 to TA, where T2 is current timestamp.Step 3: when TA receives the messagesΦ2, it first inspects the expiration date of T2. If T2 is expired, it aborts; else it checks the identity of the RSU. It computes η2∗=H4IDRSU‖rsk‖Nr; if η2∗≠η2, it aborts; else, it continues to authenticate Vi. TA computes η1∗=H2PIDi‖λi‖Nv‖α⋅P; if η1∗≠η1, it ends; otherwise, Vi is successfully authenticated by TA. Then, TA randomly selects numbers β,ωi∈Zq∗ and computes Wi=ωi⋅P,Xi=H1PIDi‖Wi,Si′=ωi+sT⋅Xi,Q=H3λi‖PIDi‖Nv‖Si′‖β⋅P‖Wi,η3=H4rsk‖Nr, and η4=Si′⊕β⋅α⋅P. Finally, TA sends the messages Φ3=η3,η4,Q,β⋅P,Wi,T3 to nearby RSU, where T3 is current timestamp. At the same time, TA updates the shared key λi∗ as H0β⋅α⋅P.Step 4: upon getting the messageΦ3, RSU first checks the freshness of T3 and then calculates η3∗=H4rsk‖Nr. If η3∗=η3, it forwards the messages Φ4=η4,Q,β⋅P,Wi,T4 to the vehicle Vi, otherwise it aborts.Step 5: upon receiving the messageΦ4,Vi first inspects the validity of T4. Then, it retrieves Si′=η4⊕α⋅β⋅P and computes Q∗=H3λi‖PIDi‖Nv‖Si′‖β⋅P‖Wi. If Q∗≠Q, it ends; else, the vehicle Vi successfully authenticates the TA and updates λi∗=H0α⋅β⋅P. Finally, Vi generates the signing key SKi=si−1⋅Si′=si−1⋅ωi+sT⋅Xi.Table 2
Mutual authentication phase between TA and the vehicle.
ViRSUTASelectsNv,α∈Zq∗Computes η1=H2PIDi‖λi‖Nv‖α⋅P⟶Φ1=η1,PIDi,α⋅P,T1VerifiesT1∗−T1≤ΔTSelects Nr∈Zq∗,Computes η2=H4IDRSU‖rsk‖Nv⟶Φ2=Φ1,η2,IDRSU,T2First verifiesT2∗−T2≤ΔTComputes η2∗=H4IDRSU‖rsk‖Nr,Checks η2∗=?η2Computes η1∗=H2PIDi‖λi‖Nv‖α⋅P,Checks η1∗=?η1Selects β,ωi∈Zq∗Computes Wi=ωi⋅PComputes Xi=H1PIDi‖Wi,Si′=ωi+sT⋅XiComputes Q=H3λi‖PIDi‖Nv‖Si′‖β⋅P‖WiComputes η3=H4rsk‖NrComputes η4=Si′⊕β⋅α⋅PUpdates λi∗=H0β⋅α⋅P←Φ3=η3,η4,Q,β⋅P,Wi,T3VerifiesT3∗−T3≤ΔTComputes η3∗=H4rsk‖NrChecks η3∗=?η3←Φ4=η4,Q,β⋅P,Wi,T4T4∗−T4≤ΔTRetrieves Si′=η4⊕α⋅β⋅PChecks Q∗=?QUpdates λi∗=H0α⋅β⋅PGenerates the signing key:SKi=si−1⋅Si′=si−1⋅ωi+sT⋅Xi


## 6.4. Message Signing

When the vehicleVi is ready to broadcast message Mi to others, it picks a random integer ri∈Zq∗ and computes Ri=ri⋅PIDi,1,Yi=H2Mi‖PIDi‖Ri‖Ti. Then, it generates the signature σi=SKi+ri⋅Yi, where Ti is the current time. Subsequently, it broadcasts the messages Mi,σi,PIDi,Ri,Wi,Ti to nearby vehicles and RSUs.


## 6.5. Message Verification

When the RSU obtains the messagesMi,σi,PIDi,Ri,Wi,Ti, it first checks the freshness of Ti and valid period VPi of PIDi. Then, it verifies the signature by checking whether σi⋅PIDi,1=Wi+Xi⋅Ppub+Yi⋅Ri satisfies. If it satisfies, the RSU accepts the messages; otherwise, it directly discards the messages. The correctness proof of the above equation is as follows.


### 6.5.1. Correctness Proof

(4)σi⋅PIDi,1=SKi+ri⋅Yi⋅PIDi,1=si−1⋅Si′+ri⋅Yi⋅PIDi,1=si−1⋅wi+sT⋅Xi⋅si⋅P+ri⋅Yi⋅PIDi,1=wi+sT⋅Xi⋅P+Yi⋅Ri=Wi+Xi⋅Ppub+Yi⋅Ri.


## 6.5.1. Correctness Proof

(4)σi⋅PIDi,1=SKi+ri⋅Yi⋅PIDi,1=si−1⋅Si′+ri⋅Yi⋅PIDi,1=si−1⋅wi+sT⋅Xi⋅si⋅P+ri⋅Yi⋅PIDi,1=wi+sT⋅Xi⋅P+Yi⋅Ri=Wi+Xi⋅Ppub+Yi⋅Ri.


## 6.6. Batch Verification

When receiving lots of messages from multiple vehicles, the RSU can verify these messages in batch to effectively reduce the computation cost and raise the efficiency of verification. Assume that the RSU obtains the messages fromn vehicles, which are denoted as Mi,σi,PIDi,Ri,Wi,Ti, where i=1,2,…,n. Similar to the single verification, the process of batch verification is executed by the verifier as follows.The RSU first checks the freshness ofTi and valid period VPi of PIDi; if Ti is not fresh or VPi is expired, RSU discards this message; otherwise, it randomly selects a vector vi=v1,v2,…,vn, where vi∈1,2ε and ε is a tiny number. Then, it performs batch verification by inspecting the validity of the following equation:(5)∑i=1nvi⋅σi⋅PIDi,1=∑i=1nvi⋅Wi+∑i=1nvi⋅Xi⋅Ppub+∑i=1nvi⋅Yi⋅Ri.


## 7. Security Analysis and Comparison

### 7.1. Security Analysis

Based on the hard problems introduced inSection 3.2, we prove that our scheme is secure by a game played between an adversary A and a challenger C using random oracle model.Theorem 1.
The proposed scheme for VANETs is secure under the random oracle model in the adaptive chosen-message attack with an assumption that the ECDL problem is hard.Proof.
Suppose an adversaryA could forge a message Mi,σi,PIDi,Ri,Wi,Ti, and a challenger C could tackle the ECDL problem with a nonnegligible probability by running A as a subroutine. The details are as follows:Setup phase:C initializes public system parameters ψ=a,b,p,q,P,H0,H1,H2,H3,H4,Ppub and delivers them to A. Note that Ppub=sT⋅P, where sT∈Zq∗ is randomly selected by TA.Query phase: in each random oracle, the adversaryA initiates an inquiry to the challenger C, and C returns the result of the inquiry to A from the list. Suppose listh1andlisth2 are the lists maintained by C and are initially empty.H1-Oracle: if A launches an inquiry on PIDi,Wi, C will check whether PIDi,Wi,ρh1 exists in listh1. If does exist, C delivers ρh1to A; otherwise, C sets ρh1=H1PIDi‖Wi and adds PIDi,Wi,ρh1 into listh1. Finally, C sends ρh1 to A.H2-Oracle: if A initiates an inquiry on Mi,PIDi,Ri,Ti, C will check whether Mi,PIDi,Ri,Ti,ρh2 exists in listh2. If does exist, C delivers ρh2 to A; else, C sets ρh2=H2Mi‖PIDi‖Ri‖Ti and adds Mi,PIDi,Ri,Ti,ρh2 to listh2. Finally, C sends ρh2 to A.Sign-Oracle: afterC obtains the query on the message Mi from A, it randomly generates three integers σi,Xi,Yi∈Zq∗ and then adds PIDi,Wi,Xi into listh1 and adds Mi,PIDi,Ri,Ti,Yi into listh2. Finally, C sends the messages Mi,PIDi,Ri,Wi,Ti,σi to A. It is obvious that the equation σi⋅PIDi,1=Wi+Xi⋅Ppub+Yi⋅Ri holds.
In the end,A outputs messages Mi,PIDi,Ri,Wi,Ti,σi and C checks whether the following equation satisfies:(6)σi⋅PIDi,1=Wi+Xi⋅Ppub+Yi⋅Ri.
If not,C terminates the game. Otherwise, according to the forgery lemma [44], if the process is executed with different H2−oracle once again, A could generate another valid messages Mi,PIDi,Ri,Wi,Ti,σi∗. Obviously, we can get the following equation:(7)σi∗⋅PIDi,1=Wi+Xi⋅Ppub+Yi∗⋅Ri.
According to equations (6) and (7), C could compute:(8)σi−σi∗⋅PIDi,1=Yi⋅Ri−Yi∗⋅Ri.
So,(9)σi−σi∗=ri⋅Yi−Yi∗modq.
C outputs Yi−Yi∗−1⋅σi−σi∗ as the result of ECDL problem which conflicts the difficulty of the ECDL problem. Consequently, our scheme for VANETs is secure under random oracle model in adaptively chosen message attack. Next, we will briefly analyze the security requirements for VANETS mentioned in Section 3.3.(1)
Message authentication: based on Theorem1, it is known that if the ECDL problem is difficult, any polynomial adversary cannot forge a valid message signature. Thus, the verifier can inspect the integrity and validity of the messages Mi,PIDi,Ri,Wi,Ti,σi by checking whether the equation σi⋅PIDi,1=Wi+H1PIDi‖Wi⋅Ppub+H2Mi‖PIDi‖Ri‖Ti⋅Ri holds. Consequently, the proposed scheme for VANETs ensures the validity and integrity of the broadcast messages.(2)
Identity authentication: during the mutual authentication phase, TA authenticates the identity of the vehicleVi by calculating η1∗=H3PIDi‖λi‖Nv‖α⋅P; Vi verifies the validity of TA by computing Q∗=H3λi‖PIDi‖Nv‖Si′‖β⋅P‖Wi.(3)
Traceability: once the traffic-related message broadcast by the vehicleVi causes an accident, TA can compute the real identity of Vi by RID=PIDi,2⊕H0sT⋅PIDi,1‖VPi. Then, TA adds the vehicle Vi to the blacklist and deletes the information of Vi from its database. TA periodically broadcasts the blacklist to other vehicles and RSUs.(4)
Forward secrecy: the adversary cannot obtain the previous shared key between TA andVi, even though the current shared key is exposed. In each interaction, the shared key will be updated to λi∗=H0α⋅β⋅P with the random numbers α and β chosen by TA and Vi, respectively. The updated shared key has nothing to do with the previous key, but only related to the random numbers α and β. According to the CDH problem, it is known that the adversary cannot obtain α⋅β⋅P even if it intercepts α⋅P and β⋅P from the public channel. Hence, the proposed scheme provides forward security.(5)
Replay attack: upon receiving the messagesMi,σi,PIDi,Ri,Wi,Ti, the RSU will first verify the freshness of Ti by checking wether Ti∗−Ti≤ΔT holds. Even if Ti is fresh, it cannot satisfy the verification equation σi⋅PIDi,1=Wi+Xi⋅Ppub+Yi⋅Ri.(6)
Impersonation attack: according to Theorem1, it is not possible for an adversary to imitate other valid vehicles to successfully broadcast the signatures of messages. Because once the RSU receives the messages Mi,σi,PIDi,Ri,Wi,Ti, it will first check the validity of the verification equation σi⋅PIDi,1=Wi+Xi⋅Ppub+Yi⋅Ri. Hence, the impersonation attack can be resisted in our scheme.(7)
Forgery attack: according to Theorem1, any adversary cannot forge a valid messages Mi,σi,PIDi,Ri,Wi,Ti because this attack can be detected by the verifier through checking whether the equation σi⋅PIDi,1=Wi+Xi⋅Ppub+Yi⋅Ri holds. So, our scheme is resistant of the forgery attack.(8)
Known key secrecy attack: even though the previous shared key between TA andVi is stolen, the adversary cannot generate the current shared key. This is because the shared key will be replaced as λi∗=H0α⋅β⋅P in each round. It is just associated with the random numbers α and β, which are selected, respectively, by the vehicle and TA for each session. The adversary cannot obtain α⋅β⋅P from α⋅P and β⋅P unless it could solve CDH problem. The CDH problem is recognized as hard; hence, the proposed scheme can withstand known key secrecy attack.


### 7.2. Security Comparison

We compare the security of our scheme with three related schemes [6, 37, 38] for VANETs. Suppose S1, S2, S3, S4, S5, S6, S7, and S8, respectively, denote message authentication, identity authentication, traceability, forward secrecy, resistance against replay attack, impersonation attack, forgery attack, and known key secrecy attack. The result of security comparison is shown in Table 3.Table 3
The result of security comparison.
SchemesS1S2S3S4S5S6S7S8Ali and Li [38]√×√×√√√×Zhong et al. [37]√×√×√√√×Cui et al. [6]√√√×√×××Our scheme√√√√√√√√From Table3, we can see that all the four schemes can satisfy the security requirements of message authentication, traceability, and resistance against replay attack. Identity authentication is only met in our scheme and the scheme [6]. Our scheme is the only one that can provide forward secrecy and resist known key secrecy attack. In summary, our scheme provides better security property compared with the recent proposed schemes.


## 7.1. Security Analysis

Based on the hard problems introduced inSection 3.2, we prove that our scheme is secure by a game played between an adversary A and a challenger C using random oracle model.Theorem 1.
The proposed scheme for VANETs is secure under the random oracle model in the adaptive chosen-message attack with an assumption that the ECDL problem is hard.Proof.
Suppose an adversaryA could forge a message Mi,σi,PIDi,Ri,Wi,Ti, and a challenger C could tackle the ECDL problem with a nonnegligible probability by running A as a subroutine. The details are as follows:Setup phase:C initializes public system parameters ψ=a,b,p,q,P,H0,H1,H2,H3,H4,Ppub and delivers them to A. Note that Ppub=sT⋅P, where sT∈Zq∗ is randomly selected by TA.Query phase: in each random oracle, the adversaryA initiates an inquiry to the challenger C, and C returns the result of the inquiry to A from the list. Suppose listh1andlisth2 are the lists maintained by C and are initially empty.H1-Oracle: if A launches an inquiry on PIDi,Wi, C will check whether PIDi,Wi,ρh1 exists in listh1. If does exist, C delivers ρh1to A; otherwise, C sets ρh1=H1PIDi‖Wi and adds PIDi,Wi,ρh1 into listh1. Finally, C sends ρh1 to A.H2-Oracle: if A initiates an inquiry on Mi,PIDi,Ri,Ti, C will check whether Mi,PIDi,Ri,Ti,ρh2 exists in listh2. If does exist, C delivers ρh2 to A; else, C sets ρh2=H2Mi‖PIDi‖Ri‖Ti and adds Mi,PIDi,Ri,Ti,ρh2 to listh2. Finally, C sends ρh2 to A.Sign-Oracle: afterC obtains the query on the message Mi from A, it randomly generates three integers σi,Xi,Yi∈Zq∗ and then adds PIDi,Wi,Xi into listh1 and adds Mi,PIDi,Ri,Ti,Yi into listh2. Finally, C sends the messages Mi,PIDi,Ri,Wi,Ti,σi to A. It is obvious that the equation σi⋅PIDi,1=Wi+Xi⋅Ppub+Yi⋅Ri holds.
In the end,A outputs messages Mi,PIDi,Ri,Wi,Ti,σi and C checks whether the following equation satisfies:(6)σi⋅PIDi,1=Wi+Xi⋅Ppub+Yi⋅Ri.
If not,C terminates the game. Otherwise, according to the forgery lemma [44], if the process is executed with different H2−oracle once again, A could generate another valid messages Mi,PIDi,Ri,Wi,Ti,σi∗. Obviously, we can get the following equation:(7)σi∗⋅PIDi,1=Wi+Xi⋅Ppub+Yi∗⋅Ri.
According to equations (6) and (7), C could compute:(8)σi−σi∗⋅PIDi,1=Yi⋅Ri−Yi∗⋅Ri.
So,(9)σi−σi∗=ri⋅Yi−Yi∗modq.
C outputs Yi−Yi∗−1⋅σi−σi∗ as the result of ECDL problem which conflicts the difficulty of the ECDL problem. Consequently, our scheme for VANETs is secure under random oracle model in adaptively chosen message attack. Next, we will briefly analyze the security requirements for VANETS mentioned in Section 3.3.(1)
Message authentication: based on Theorem1, it is known that if the ECDL problem is difficult, any polynomial adversary cannot forge a valid message signature. Thus, the verifier can inspect the integrity and validity of the messages Mi,PIDi,Ri,Wi,Ti,σi by checking whether the equation σi⋅PIDi,1=Wi+H1PIDi‖Wi⋅Ppub+H2Mi‖PIDi‖Ri‖Ti⋅Ri holds. Consequently, the proposed scheme for VANETs ensures the validity and integrity of the broadcast messages.(2)
Identity authentication: during the mutual authentication phase, TA authenticates the identity of the vehicleVi by calculating η1∗=H3PIDi‖λi‖Nv‖α⋅P; Vi verifies the validity of TA by computing Q∗=H3λi‖PIDi‖Nv‖Si′‖β⋅P‖Wi.(3)
Traceability: once the traffic-related message broadcast by the vehicleVi causes an accident, TA can compute the real identity of Vi by RID=PIDi,2⊕H0sT⋅PIDi,1‖VPi. Then, TA adds the vehicle Vi to the blacklist and deletes the information of Vi from its database. TA periodically broadcasts the blacklist to other vehicles and RSUs.(4)
Forward secrecy: the adversary cannot obtain the previous shared key between TA andVi, even though the current shared key is exposed. In each interaction, the shared key will be updated to λi∗=H0α⋅β⋅P with the random numbers α and β chosen by TA and Vi, respectively. The updated shared key has nothing to do with the previous key, but only related to the random numbers α and β. According to the CDH problem, it is known that the adversary cannot obtain α⋅β⋅P even if it intercepts α⋅P and β⋅P from the public channel. Hence, the proposed scheme provides forward security.(5)
Replay attack: upon receiving the messagesMi,σi,PIDi,Ri,Wi,Ti, the RSU will first verify the freshness of Ti by checking wether Ti∗−Ti≤ΔT holds. Even if Ti is fresh, it cannot satisfy the verification equation σi⋅PIDi,1=Wi+Xi⋅Ppub+Yi⋅Ri.(6)
Impersonation attack: according to Theorem1, it is not possible for an adversary to imitate other valid vehicles to successfully broadcast the signatures of messages. Because once the RSU receives the messages Mi,σi,PIDi,Ri,Wi,Ti, it will first check the validity of the verification equation σi⋅PIDi,1=Wi+Xi⋅Ppub+Yi⋅Ri. Hence, the impersonation attack can be resisted in our scheme.(7)
Forgery attack: according to Theorem1, any adversary cannot forge a valid messages Mi,σi,PIDi,Ri,Wi,Ti because this attack can be detected by the verifier through checking whether the equation σi⋅PIDi,1=Wi+Xi⋅Ppub+Yi⋅Ri holds. So, our scheme is resistant of the forgery attack.(8)
Known key secrecy attack: even though the previous shared key between TA andVi is stolen, the adversary cannot generate the current shared key. This is because the shared key will be replaced as λi∗=H0α⋅β⋅P in each round. It is just associated with the random numbers α and β, which are selected, respectively, by the vehicle and TA for each session. The adversary cannot obtain α⋅β⋅P from α⋅P and β⋅P unless it could solve CDH problem. The CDH problem is recognized as hard; hence, the proposed scheme can withstand known key secrecy attack.


## 7.2. Security Comparison

We compare the security of our scheme with three related schemes [6, 37, 38] for VANETs. Suppose S1, S2, S3, S4, S5, S6, S7, and S8, respectively, denote message authentication, identity authentication, traceability, forward secrecy, resistance against replay attack, impersonation attack, forgery attack, and known key secrecy attack. The result of security comparison is shown in Table 3.Table 3
The result of security comparison.
SchemesS1S2S3S4S5S6S7S8Ali and Li [38]√×√×√√√×Zhong et al. [37]√×√×√√√×Cui et al. [6]√√√×√×××Our scheme√√√√√√√√From Table3, we can see that all the four schemes can satisfy the security requirements of message authentication, traceability, and resistance against replay attack. Identity authentication is only met in our scheme and the scheme [6]. Our scheme is the only one that can provide forward secrecy and resist known key secrecy attack. In summary, our scheme provides better security property compared with the recent proposed schemes.


## 8. Performance Analysis

In this part, we present the performance analysis with respect to the computational and communication overhead of our scheme and the schemes proposed by Ali and Li [38], Zhong et al. [37], and Cui et al. [6].


### 8.1. Computation Cost Analysis

To estimate the computational cost of our scheme and other related schemes [6, 37, 38], we adapt the Java Pairing-Based Cryptography (JPBC) library. In terms of the bilinear map e:G×G⟶GT , we choose the Type A pairing for schemes [37, 38]. It is constructed on the elliptic curve y2=x3+x :modp over the field Fq, where p and the order of group G1 are, respectively, 512 bits and 160 bits. While in the proposed scheme using the elliptic curve, the group G2 is generated by the elliptic curve y2=x3+a⋅x+b :modp, where the order of G2 and the prime p are both 160 bits. The experiment is conducted on a Laptop running Intel I5–8250U, 4 GB memory, 1.8 GHz processor with Windows 10 operating system. In our simulation experiment, we only consider the cryptographic operations which have a major impact on efficiency and ignore the execution time of addition operation. Table 4 shows the notations and the execution time of several cryptographic-related operations.Table 4
The execution time of cryptographic operations.
Cryptographic operationsThe notations of cryptographic operationsExecution time (ms)TpThe execution time of the bilinear pairing operation22.4Tmp−pThe execution time of multiplication operation based on bilinear pairing3.1Tmp−ECCThe execution time of multiplication operation based on the elliptic curve12.4TmtpThe execution time of the map-to-point operation30.6ThThe execution time of hash function0.7Table5 lists the total computation overhead about message signing, single signature verification, and n signatures’ verification. In the process of message signing, our scheme requires one multiplication operation based on ECC and one hash function operation. Accordingly, the computation overhead of this process is Tmp−ECC+Th≈13.1ms. In Ali and Li’s scheme [38], the computation overhead of message signing is 3Tmp−ECC+2Th≈38.6ms. The cost of generating a signature is 3Tmp−ECC+Tmtp+Th≈68.5ms in Zhong et al.’s scheme [37]. In Cui et al.’s scheme [6], the computation overhead of generating a signature is 2Tmp−ECC+2Th≈26.2ms.Table 5
The comparison of computation costs.
SchemesMessage signingSingle message verificationMultiple messages verificationAli and Li [38]3Tmp−ECC+2ThTp+Tmp−ECC+ThTp+nTmp−ECC+nThZhong et al. [37]3Tmp−ECC+Tmtp+Th3Tp+Tmtp+2Tmp−ECC+Tmp−p+Th3Tp+nTmtp+2nTmp−ECC+Tmp−p+nThCui et al. [6]2Tmp−ECC+2ThThnThOur schemeTmp−ECC+Th3Tmp−ECC+2Th2n+1Tmp−ECC+2nThDuring the message verification phase, in our scheme, the verifier takes three multiplication operations based on ECC and two hash function operations for single message verification,2n+1 multiplication operations based on ECC, and 2n hash function operations for n signatures verification. Therefore, the computation cost of verifying a single signature and n signatures are 3Tmp−ECC+2Th≈38.6ms and 2n+1Tmp−ECC+2nTh≈12.4+26.2nms, respectively. In the scheme of Ali and Li [38], the computation overhead of single signature verification and batch verification are Tp+Tmp−ECC+Th≈35.5ms and Tp+nTmp−ECC+nTh≈22.4+13.1nms, respectively. In the scheme of Zhong et al. [37], 3Tp+Tmtp+2Tmp−ECC+Tmp−p+Th≈126.4ms and 3Tp+nTmtp+2nTmp−ECC+nTh+Tmp−p≈70.3+56.1nms are, respectively, spent on the phase of single verification and batch verification. In Cui et al.’s scheme [6], the verifier spends Th≈0.7ms and nTh≈0.7nms on verifying a single signature and n signatures, respectively.From Figures2–4, compared with the three recently proposed schemes [6, 37, 38], we can more intuitively and clearly find that our scheme has the least computation overhead in the message signing step. During the single verification and batch verification phases, although the computation overhead of Cui et al.’s scheme [6] is negligible, their scheme is subject to some security attacks such as impersonation attack and forgery attack; the computation overhead of our scheme is far lower than that of Zhong et al. [37] and slightly higher than that of Ali and Li [38]. However, our scheme has better security performance such as supporting identity authentication and forward secrecy, withstanding known key secrecy attack. On the whole, our solution is suitable for VANETs in terms of security and efficiency.Figure 2
Message signing cost.Figure 3
Single signature verification cost.Figure 4
Multiple signatures’ verification cost.


### 8.2. Communication Cost Analysis

In this part, we analyze and compare the communication overhead between the proposed scheme and other schemes [6, 37, 38]. For the group G1 using the bilinear pairing and the group G2 using the ECC, the size of p is, respectively, 512 bits and 160 bits. Hence, the size of each element in group G1 is 128 bytes and that of each element in G2 is 40 bytes. Besides, the length of timestamp is 4 bytes; the elements in an integer group and the general hash are both considered 20 bytes. We assume that the length of all traffic-related messages is the same, so we ignore the size of traffic-related messages when calculating the communication overhead.As shown in Table6, in the scheme of Ali and Li [38], the vehicle Vi broadcasts a signature σi=Ai,Bi∈G1 on the message Mi for the pseudonym identity VPIDi=VPIDi,1,VPIDi,2 with the timestamp Ti to the verifier, where VPIDi,1∈G1andVPIDi,2∈Zq∗. Accordingly, the total communication cost of Ali et al.’ scheme is Ai+Bi+VPIDi,1+VPIDi,2+Ti=12.8∗3+20+4=408 bytes. In the scheme of Zhong et al. [37], Vi transmits the messages Mi,VPIDi,VPKi,Ri,Ti,ti to the RSU, where VPIDi=VPIDi,1,VPIDi,2,ti is the timestamp, and VPIDi,1,VPIDi,2,VPKi,Ri,Ti∈G1. Hence, the sum of communication overhead is VPIDi,1+VPIDi,2+VPKi+Ri+Ti+Ti=12.8∗5+4=644 bytes. In Cui et al.’s scheme [6], Vi sends the messages PPIDi,AC,δi,Ri to the verifier, where PPIDi,AC,δi are all hash values, and Ri∈G2. Thus, the sum of communication overhead is PPIDi+AC+σi+Ri=20∗3+40=100 bytes. Then, in our scheme, Vi transmits the messages Mi,σi,PIDi,Ri,Wi,Ti, where PIDi=PIDi,1,PIDi,2,VPi, and σi,PIDi,2∈Zq∗,PIDi,1,Ri,Wi∈G2, and Ti is the timestamp. So, the whole communication overhead is σi+PIDi+Ri+Wi+Ti=20∗2+40∗3+4∗2=168 bytes.Table 6
The comparison of communication cost.
SchemesBroadcasting single signature (bytes)Broadcastingn signatures (bytes)Ali and Li [38]408408nZhong et al. [37]644644nCui et al. [6]100100nOur scheme168168nFrom Table6, we can see that the total communication cost of our scheme is far less than that of the schemes [37, 38], but slightly more than that of Cui et al.’s scheme [6]. However, the scheme of Cui et al. is subject to the impersonation attack and forgery attack. In addition, our scheme can not only provide identity authentication and forward secrecy but also resist known key secrecy attack. Therefore, our scheme is appropriate for VANETs with respect to communication overhead.


## 8.1. Computation Cost Analysis

To estimate the computational cost of our scheme and other related schemes [6, 37, 38], we adapt the Java Pairing-Based Cryptography (JPBC) library. In terms of the bilinear map e:G×G⟶GT , we choose the Type A pairing for schemes [37, 38]. It is constructed on the elliptic curve y2=x3+x :modp over the field Fq, where p and the order of group G1 are, respectively, 512 bits and 160 bits. While in the proposed scheme using the elliptic curve, the group G2 is generated by the elliptic curve y2=x3+a⋅x+b :modp, where the order of G2 and the prime p are both 160 bits. The experiment is conducted on a Laptop running Intel I5–8250U, 4 GB memory, 1.8 GHz processor with Windows 10 operating system. In our simulation experiment, we only consider the cryptographic operations which have a major impact on efficiency and ignore the execution time of addition operation. Table 4 shows the notations and the execution time of several cryptographic-related operations.Table 4
The execution time of cryptographic operations.
Cryptographic operationsThe notations of cryptographic operationsExecution time (ms)TpThe execution time of the bilinear pairing operation22.4Tmp−pThe execution time of multiplication operation based on bilinear pairing3.1Tmp−ECCThe execution time of multiplication operation based on the elliptic curve12.4TmtpThe execution time of the map-to-point operation30.6ThThe execution time of hash function0.7Table5 lists the total computation overhead about message signing, single signature verification, and n signatures’ verification. In the process of message signing, our scheme requires one multiplication operation based on ECC and one hash function operation. Accordingly, the computation overhead of this process is Tmp−ECC+Th≈13.1ms. In Ali and Li’s scheme [38], the computation overhead of message signing is 3Tmp−ECC+2Th≈38.6ms. The cost of generating a signature is 3Tmp−ECC+Tmtp+Th≈68.5ms in Zhong et al.’s scheme [37]. In Cui et al.’s scheme [6], the computation overhead of generating a signature is 2Tmp−ECC+2Th≈26.2ms.Table 5
The comparison of computation costs.
SchemesMessage signingSingle message verificationMultiple messages verificationAli and Li [38]3Tmp−ECC+2ThTp+Tmp−ECC+ThTp+nTmp−ECC+nThZhong et al. [37]3Tmp−ECC+Tmtp+Th3Tp+Tmtp+2Tmp−ECC+Tmp−p+Th3Tp+nTmtp+2nTmp−ECC+Tmp−p+nThCui et al. [6]2Tmp−ECC+2ThThnThOur schemeTmp−ECC+Th3Tmp−ECC+2Th2n+1Tmp−ECC+2nThDuring the message verification phase, in our scheme, the verifier takes three multiplication operations based on ECC and two hash function operations for single message verification,2n+1 multiplication operations based on ECC, and 2n hash function operations for n signatures verification. Therefore, the computation cost of verifying a single signature and n signatures are 3Tmp−ECC+2Th≈38.6ms and 2n+1Tmp−ECC+2nTh≈12.4+26.2nms, respectively. In the scheme of Ali and Li [38], the computation overhead of single signature verification and batch verification are Tp+Tmp−ECC+Th≈35.5ms and Tp+nTmp−ECC+nTh≈22.4+13.1nms, respectively. In the scheme of Zhong et al. [37], 3Tp+Tmtp+2Tmp−ECC+Tmp−p+Th≈126.4ms and 3Tp+nTmtp+2nTmp−ECC+nTh+Tmp−p≈70.3+56.1nms are, respectively, spent on the phase of single verification and batch verification. In Cui et al.’s scheme [6], the verifier spends Th≈0.7ms and nTh≈0.7nms on verifying a single signature and n signatures, respectively.From Figures2–4, compared with the three recently proposed schemes [6, 37, 38], we can more intuitively and clearly find that our scheme has the least computation overhead in the message signing step. During the single verification and batch verification phases, although the computation overhead of Cui et al.’s scheme [6] is negligible, their scheme is subject to some security attacks such as impersonation attack and forgery attack; the computation overhead of our scheme is far lower than that of Zhong et al. [37] and slightly higher than that of Ali and Li [38]. However, our scheme has better security performance such as supporting identity authentication and forward secrecy, withstanding known key secrecy attack. On the whole, our solution is suitable for VANETs in terms of security and efficiency.Figure 2
Message signing cost.Figure 3
Single signature verification cost.Figure 4
Multiple signatures’ verification cost.


## 8.2. Communication Cost Analysis

In this part, we analyze and compare the communication overhead between the proposed scheme and other schemes [6, 37, 38]. For the group G1 using the bilinear pairing and the group G2 using the ECC, the size of p is, respectively, 512 bits and 160 bits. Hence, the size of each element in group G1 is 128 bytes and that of each element in G2 is 40 bytes. Besides, the length of timestamp is 4 bytes; the elements in an integer group and the general hash are both considered 20 bytes. We assume that the length of all traffic-related messages is the same, so we ignore the size of traffic-related messages when calculating the communication overhead.As shown in Table6, in the scheme of Ali and Li [38], the vehicle Vi broadcasts a signature σi=Ai,Bi∈G1 on the message Mi for the pseudonym identity VPIDi=VPIDi,1,VPIDi,2 with the timestamp Ti to the verifier, where VPIDi,1∈G1andVPIDi,2∈Zq∗. Accordingly, the total communication cost of Ali et al.’ scheme is Ai+Bi+VPIDi,1+VPIDi,2+Ti=12.8∗3+20+4=408 bytes. In the scheme of Zhong et al. [37], Vi transmits the messages Mi,VPIDi,VPKi,Ri,Ti,ti to the RSU, where VPIDi=VPIDi,1,VPIDi,2,ti is the timestamp, and VPIDi,1,VPIDi,2,VPKi,Ri,Ti∈G1. Hence, the sum of communication overhead is VPIDi,1+VPIDi,2+VPKi+Ri+Ti+Ti=12.8∗5+4=644 bytes. In Cui et al.’s scheme [6], Vi sends the messages PPIDi,AC,δi,Ri to the verifier, where PPIDi,AC,δi are all hash values, and Ri∈G2. Thus, the sum of communication overhead is PPIDi+AC+σi+Ri=20∗3+40=100 bytes. Then, in our scheme, Vi transmits the messages Mi,σi,PIDi,Ri,Wi,Ti, where PIDi=PIDi,1,PIDi,2,VPi, and σi,PIDi,2∈Zq∗,PIDi,1,Ri,Wi∈G2, and Ti is the timestamp. So, the whole communication overhead is σi+PIDi+Ri+Wi+Ti=20∗2+40∗3+4∗2=168 bytes.Table 6
The comparison of communication cost.
SchemesBroadcasting single signature (bytes)Broadcastingn signatures (bytes)Ali and Li [38]408408nZhong et al. [37]644644nCui et al. [6]100100nOur scheme168168nFrom Table6, we can see that the total communication cost of our scheme is far less than that of the schemes [37, 38], but slightly more than that of Cui et al.’s scheme [6]. However, the scheme of Cui et al. is subject to the impersonation attack and forgery attack. In addition, our scheme can not only provide identity authentication and forward secrecy but also resist known key secrecy attack. Therefore, our scheme is appropriate for VANETs with respect to communication overhead.


## 9. Conclusion

In this paper, we first analyze and point out that the mutual authentication scheme of Cui et al. is subject to the impersonation attack and the forgery attack. Then, we propose an improved mutual authentication scheme with forward security for VANETs. Security proof and analysis show that our scheme can not only resist general attacks but also achieve forward secrecy and withstand known key secrecy key attack, which are not achieved in other related schemes [6, 37, 38]. In addition, our solution has relatively balanced performance.



---

*Source: 6698099-2021-04-21.xml*