# Cryptanalysis of an Efficient and Secure Certificateless Aggregate Signature-Based Authentication Scheme for Vehicular Ad Hoc Networks

Authors: Xiaodong Yang; Aijia Chen; Zhisong Wang; Xiaoni Du; Caifen Wang
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Vehicular ad hoc networks (VANETs) apply the Internet of Things technology to provide secure communication among the vehicles, thereby improving the safe driving of vehicles, the utilization of traffic resources, and the efficiency of information services. Due to the openness and vulnerability of wireless networks in VANETs, messages in sharing and transmission are easily attacked and destroyed. Therefore, a large number of schemes for VANETs were proposed to protect the privacy of vehicles and ensure the authentication, integrity, and nonrepudiation of messages. However, most of these schemes have serious security flaws or poor performance issues. Recently, Thumbur et al. presented an efficient certificateless aggregate signature-based authentication scheme for VANETs and then gave the detailed security proof (IEEE Internet of Things Journal, vol. 8, no. 3, pp. 1908–1920, 2021). In this article, we analyze the security of Thumbur et al.’s scheme and demonstrate that it has significant security problems. Specifically, their scheme cannot resist public key replacement attacks from external adversaries, and it is not secure against coalition attacks from malicious vehicles. Then, we improve Thumbur et al.’s scheme to address the security weaknesses. According to the security and performance analysis, the improved scheme enhances the security while maintaining the performance of the original scheme.


---

## Body

## 1. Introduction

As a new type of mobile network, vehicular ad hoc networks (VANETs) utilize the Internet of Things technology and intelligent transportation mechanisms to achieve secure communication among the vehicles. As a result, it can efficiently improve the safety of vehicle driving, minimize road traffic congestion, avoid traffic accidents, reduce the work intensity of drivers, and provide secure, economic, comfortable, and fast transportation services [1]. VANETs generally involve four types of entities: vehicles with on-board units (OBUs), roadside units (RSUs) installed along the road, a trusted authority (TA) for system initialization, and application servers (ASs) for data analysis [2]. In VANETs, a vehicle employs an OBU to periodically broadcast its vehicle-related information (such as speed, direction, mileage, fuel consumption, location, and brake pad pressure) and real-time road condition information to nearby vehicles and RSUs every 100–300 milliseconds.However, VANETs face numerous security challenges and privacy threats while improving traffic management and road safety [3–5]. Because wireless networks in VANETs are open, the information shared among the vehicles is easy to be attacked and destroyed, such as forgery, tampering, injection, and replay attack. If false traffic information is transmitted by an attacker, it will cause a potential traffic accident or even endanger the safety of drivers and passengers [6]. Hence, it is critical to ensure the integrity and authenticity of traffic data in VANETs. Furthermore, the vehicle’s private information, such as its real identity, should be protected to prevent it from being misused, leaked, or accessed by unauthorized entities. At the same time, TA is capable of tracking down the real identity of the vehicle that issued a controversial message [7, 8]. Therefore, conditional privacy must be provided by VANETs.Digital signature is a cryptographic technology that provides data integrity, anonymity, nonrepudiation, identity authentication, and other security services. Various signature technologies, such as PKC-based and identity-based cryptographic frameworks, are used to construct authentication schemes for VANETs to ensure identity authentication, message integrity, privacy, and traceability. When these schemes are deployed in real-world circumstances, there are some problems, such as complex certificate management or inherent key escrow [9]. Certificateless aggregation signature (CLAS) can not only solve these problems in PKC-based and identity-based settings but also aggregate different signatures of multiple messages into a short signature [10]. Hence, CLAS greatly reduces the computational and communication overhead of signature verification and improves storage efficiency. Due to the advantages of CLAS in terms of security and performance, CLAS is considered to be an efficient and viable solution to some security problems in VANETs.In recent years, researchers have proposed some CLAS-based authentication schemes for VANETs. Unfortunately, most of these schemes [4, 11–14] are not suitable for VANETs due to time-consuming bilinear operations. Based on the additive elliptic curve group, Cui et al. [15] proposed an authentication scheme for VANETS without pairings. However, Kamil and Ogundoyin [16] found that Cui et al.’s scheme [15] is unable to withstand attacks from a malicious key generation centre (KGC) and presented an improved scheme. Zhao et al. [17] showed that the improved authentication scheme of Kamil and Ogundoyin [16] is still insecure against forgery attacks and then constructed an improved scheme to remedy these security vulnerabilities. In 2021, the flaws in the design of Zhao et al.’s scheme [17] were discovered by Thumbur et al. [18]. Furthermore, Thumbur et al. [18] presented a novel pairing-free CLAS-based authentication scheme for VANETs. Unfortunately, we prove that their scheme is not secure by giving concrete attacks; hence, it fails to achieve the expected security goals.In this article, we analyze the security of Thumbur et al.’s scheme [18] and demonstrate that it is not secure against public key replacement attacks of external attackers and coalition attacks of malicious vehicles. To overcome these two kinds of forgery attacks, we also give an improved scheme. The main contributions of our work are as follows:(1)
We show that the CLAS-based authentication scheme for VANETs of Thumbur et al. [18] cannot resist public key replacement attacks(2)
We provide an attack method to demonstrate that Thumbur et al.’s scheme [18] is not secure against coalition attacks launched by malicious vehicles.(3)
We improve Thumbur et al. ’s scheme [18] to address the security issues(4)
Our enhanced scheme meets various security requirements in VANETsThe rest of this article is organized as follows. Section2 describes some preliminaries. Section 3 introduces Thumbur et al.’s scheme [18], and its cryptanalysis is given in Section 4. Section 5 presents our improved scheme and discusses its security and efficiency. Finally, Section 6 concludes this article.


## 2. Preliminaries

In this section, we briefly introduce the elliptic curve group, the system model, and the formal definition of the CLAS-based scheme for VANETs. Some key symbols are listed in Table1.Table 1
Summary of notations.
SymbolsDescriptionspA prime numberFpA finite field of orderpGA cyclic elliptic curve groupPA generator ofGHii=0,…,4Hash functions(s, b)Two master secret keysPpub,TpubTwo master public keysRIDiThe real identity of a vehicleViPIDiThe pseudoidentity ofVivskiThe partial private key ofVixiThe secret value ofVivpkiThe public key ofVimiA messageσiA single signature onmiσaggAn aggregate signatureΔTiThe validity period ofPIDiA1,A2Type I and type II adversaries


### 2.1. Elliptic Curve Group and Computational Assumption

Assume that the order of a finite fieldFp is a prime p>3. All solutions of the equation y2=x3+ax+bmodp form an elliptic curve EFp, where a,b∈Fp and 4a3+27b2≠0. The cyclic elliptic curve group G=x,y∈EFp:x,y∈Fp∪O is composed of all points on EFp and an infinite point O. According to the chord-and-tangent rule [19], the addition operation in G is defined as R=P+Q, where P,Q∈G. The operation kP=P+⋯+P (k times) is called a scalar multiplication in G. For convenience, let P be a generator of G. The computational assumption in G is described as follows.Elliptic Curve Discrete Logarithm Problem (ECDLP). Given two elements P and Q=xP in G, it is intractable to calculate x∈Zp∗ in polynomial time.


### 2.2. System Model

As described in Figure1, the system model of a CLAS-based authentication scheme for VANETs contains five participants: TA, KGC, AS, RSU, and the vehicle equipped with OBU. Communication modes can be divided into two types: upper-level and lower-level. The communication between TA, KGC, AS, and RSU mainly adopts the upper-level mode, which is carried out over a secure wired communication network. The lower-level communication uses the dedicated short-range communication (DSRC) protocol (such as IEEE 802.11P), which mainly occurs in the communication between the vehicle and another, as well as between the vehicle and the RSU. It is worth noting that TA, KGC, and AS are three entities with sufficient computing power, communication bandwidth, and storage capacity. OBU is a resource-constrained device, but RSU outperforms OBU in terms of battery, computation, communication, and storage. The five participants are described in detail below.(1)
TA. It initializes the system, registers vehicles and RSUs, issues pseudonym identities for vehicles, and traces the real identities of malicious vehicles. Because TA is usually the vehicle management department of the local government, it is regarded as a trustworthy authority.(2)
KGC. It is an entity independent of TA, which is primarily responsible for producing each vehicle’s partial private key.(3)
AS. It is an application server that collects and analyzes traffic-related messages sent by RSUs.(4)
RSU. This kind of wireless communication equipment is typically situated on the side of a road or at a crossroads and is mainly responsible for managing the communication of all vehicles within its communication range.(5)
Vehicle. It uses the DSRC protocol to broadcast traffic-related messages frequently, such as road conditions, vehicle speed, and location.Figure 1
The system model of the CLAS-based authentication scheme for VANETs.


### 2.3. Formal Definition of the CLAS-Based Authentication Scheme for VANETs

As defined in [16, 18], a CLAS-based authentication scheme for VANETs is made up of the nine following algorithms:(1)
System Setup. Given a security parameter λ, TA and KGC execute this algorithm to produce system parameters params, two system master keys (s, b), and two system master public keys Ppub,Tpub.(2)
Pseudonym Identity Generation. On receiving the real identity RIDi of a vehicle Vi, TA executes this algorithm to create the pseudoidentity PIDi for Vi.(3)
Partial Private Key Generation. Upon receiving the pseudoidentity PIDi of a vehicle Vi, this algorithm is executed by KGC to create a partial private key vski for Vi.(4)
Set Secret Value. This algorithm is run by a vehicle Vi to create its secret value xi.(5)
Vehicle Key Generation. A vehicle Vi runs this algorithm to produce its private key vski and corresponding public key vpki.(6)
Signature Generation. This algorithm is executed by a vehicle Vi. Given a message mi, Vi uses its private key vski to create a single signature σi on mi.(7)
Signature Verification. Taking a message mi, a single signature σi, and the pseudonym identity and public key pairs PIDi,vpki as inputs, the RSU or other vehicles execute this algorithm to output True if σi is a valid single signature or False otherwise.(8)
Aggregate Signature Generation. Taking n single signatures σii=1n on n messages mii=1n as inputs, RSU executes this algorithm to generate an aggregate signature σagg.(9)
Aggregate Signature Verification. Upon receiving an aggregate signature σagg, n messages mii=1n, and the pseudoidentity and public key pairs PIDi,vpkii=1n of n vehicles, the AS runs this algorithm to output True if σagg is a valid aggregate signature or False otherwise.As described in [16–18], an authentication scheme for VANETs achieves a wide range of security requirements, such as identity anonymity, traceability, message integrity, and authenticity. Based on these security requirements, a secure CLAS-based authentication scheme for VANETs can withstand the following attackers:(1)
Type I Adversary. This is a type of external attacker that can carry out public key replacement attacks. The attacker has the ability to get the vehicle’s secret value or replace its public key. However, the attacker is not allowed to know the KGC’s master secret key and the vehicle’s partial private key.(2)
Type II Adversary. The attacker is usually a malicious KGC and thus possesses KGC’s master key. However, the attacker is unable to compromise the vehicle’s secret value and replace the vehicle’s public key.(3)
Inside Adversary. This type of attacker is two or more malicious vehicles that launch the coalition attack. The attackers can create a legitimate aggregate signature by providing a few invalid single signatures.


## 2.1. Elliptic Curve Group and Computational Assumption

Assume that the order of a finite fieldFp is a prime p>3. All solutions of the equation y2=x3+ax+bmodp form an elliptic curve EFp, where a,b∈Fp and 4a3+27b2≠0. The cyclic elliptic curve group G=x,y∈EFp:x,y∈Fp∪O is composed of all points on EFp and an infinite point O. According to the chord-and-tangent rule [19], the addition operation in G is defined as R=P+Q, where P,Q∈G. The operation kP=P+⋯+P (k times) is called a scalar multiplication in G. For convenience, let P be a generator of G. The computational assumption in G is described as follows.Elliptic Curve Discrete Logarithm Problem (ECDLP). Given two elements P and Q=xP in G, it is intractable to calculate x∈Zp∗ in polynomial time.


## 2.2. System Model

As described in Figure1, the system model of a CLAS-based authentication scheme for VANETs contains five participants: TA, KGC, AS, RSU, and the vehicle equipped with OBU. Communication modes can be divided into two types: upper-level and lower-level. The communication between TA, KGC, AS, and RSU mainly adopts the upper-level mode, which is carried out over a secure wired communication network. The lower-level communication uses the dedicated short-range communication (DSRC) protocol (such as IEEE 802.11P), which mainly occurs in the communication between the vehicle and another, as well as between the vehicle and the RSU. It is worth noting that TA, KGC, and AS are three entities with sufficient computing power, communication bandwidth, and storage capacity. OBU is a resource-constrained device, but RSU outperforms OBU in terms of battery, computation, communication, and storage. The five participants are described in detail below.(1)
TA. It initializes the system, registers vehicles and RSUs, issues pseudonym identities for vehicles, and traces the real identities of malicious vehicles. Because TA is usually the vehicle management department of the local government, it is regarded as a trustworthy authority.(2)
KGC. It is an entity independent of TA, which is primarily responsible for producing each vehicle’s partial private key.(3)
AS. It is an application server that collects and analyzes traffic-related messages sent by RSUs.(4)
RSU. This kind of wireless communication equipment is typically situated on the side of a road or at a crossroads and is mainly responsible for managing the communication of all vehicles within its communication range.(5)
Vehicle. It uses the DSRC protocol to broadcast traffic-related messages frequently, such as road conditions, vehicle speed, and location.Figure 1
The system model of the CLAS-based authentication scheme for VANETs.


## 2.3. Formal Definition of the CLAS-Based Authentication Scheme for VANETs

As defined in [16, 18], a CLAS-based authentication scheme for VANETs is made up of the nine following algorithms:(1)
System Setup. Given a security parameter λ, TA and KGC execute this algorithm to produce system parameters params, two system master keys (s, b), and two system master public keys Ppub,Tpub.(2)
Pseudonym Identity Generation. On receiving the real identity RIDi of a vehicle Vi, TA executes this algorithm to create the pseudoidentity PIDi for Vi.(3)
Partial Private Key Generation. Upon receiving the pseudoidentity PIDi of a vehicle Vi, this algorithm is executed by KGC to create a partial private key vski for Vi.(4)
Set Secret Value. This algorithm is run by a vehicle Vi to create its secret value xi.(5)
Vehicle Key Generation. A vehicle Vi runs this algorithm to produce its private key vski and corresponding public key vpki.(6)
Signature Generation. This algorithm is executed by a vehicle Vi. Given a message mi, Vi uses its private key vski to create a single signature σi on mi.(7)
Signature Verification. Taking a message mi, a single signature σi, and the pseudonym identity and public key pairs PIDi,vpki as inputs, the RSU or other vehicles execute this algorithm to output True if σi is a valid single signature or False otherwise.(8)
Aggregate Signature Generation. Taking n single signatures σii=1n on n messages mii=1n as inputs, RSU executes this algorithm to generate an aggregate signature σagg.(9)
Aggregate Signature Verification. Upon receiving an aggregate signature σagg, n messages mii=1n, and the pseudoidentity and public key pairs PIDi,vpkii=1n of n vehicles, the AS runs this algorithm to output True if σagg is a valid aggregate signature or False otherwise.As described in [16–18], an authentication scheme for VANETs achieves a wide range of security requirements, such as identity anonymity, traceability, message integrity, and authenticity. Based on these security requirements, a secure CLAS-based authentication scheme for VANETs can withstand the following attackers:(1)
Type I Adversary. This is a type of external attacker that can carry out public key replacement attacks. The attacker has the ability to get the vehicle’s secret value or replace its public key. However, the attacker is not allowed to know the KGC’s master secret key and the vehicle’s partial private key.(2)
Type II Adversary. The attacker is usually a malicious KGC and thus possesses KGC’s master key. However, the attacker is unable to compromise the vehicle’s secret value and replace the vehicle’s public key.(3)
Inside Adversary. This type of attacker is two or more malicious vehicles that launch the coalition attack. The attackers can create a legitimate aggregate signature by providing a few invalid single signatures.


## 3. Review of Thumbur et al.’s Scheme

In this section, we briefly describe the CLAS-based authentication scheme for VANETs proposed by Thumbur et al. [18].(1)
System Setup. The following operations are carried out in collaboration between TA and KGC:(a)
TA and KGC negotiate to choose an elliptic curve groupG with prime order p and select a generator P of G and four hash functions H0,H1,H2,H3:0,1∗⟶Zp∗.(b)
KGC selects a random values∈Zp∗ as its master secret key and calculates the corresponding master public key Ppub=sP.(c)
TA randomly picksb∈Zp∗ as its master secret key and then sets Tpub=bP as its master public key.(d)
Output system parametersparams=p,G,P,Tpub,Ppub,H0,H1,H2,H3.(2)
Pseudonym Identity Generation. To protect the privacy of the identity, the vehicle uses the pseudoidentity issued by TA to hide the real identity for anonymous message communication.(a)
A vehicle Vi selects a random value ti from Zp∗ and calculates PIDi,1=tiP; then it hides its unique real identity RIDi by calculating Ki=tiTpub⊕RIDi and finally transmits Ki,PIDi,1 to TA.(b)
TA uses its master secret keyb to obtain Vi’s real identity by calculating RIDi=bPIDi,1⊕Ki. If RIDi is legal, TA calculates PIDi,2=H0bPIDi,1,ΔTi⊕RIDi, sets Vi’s pseudonym identity PIDi=PIDi,1,PIDi,2,ΔTi, and transmits it to KGC, where ΔTi is the validity period of PIDi.(3)
Partial Private Key Generation. Upon receipt of the pseudonym identity PIDi for a vehicle Vi, KGC executes the following steps:(a)
Pickri∈Zp∗ at random and calculate Ri=riP.(b)
Calculateh1i=H1PIDi,Ri,Ppub.(c)
Calculate the partial private key of Vi as pski=ri+sh1imodp.(d)
SendPIDi,Ri,pski to Vi secretly.Note that Vi checks the validity of pski from KGC by verifying whether pskiP=Ri+h1iPpub holds.(4)
Set Secret Value. A vehicle Vi randomly picks xi∈Zp∗ as its secret value and calculates Xi=xiP.(5)
Vehicle Key Generation. A vehicle Vi performs the following to produce its private key and public key:(a)
Calculateh2i=H2PIDi,Xi.(b)
CalculateQi=Ri+h2iXi.(c)
Set its public keyvpki=Qi,Ri.(d)
Set its private keyvski=pski,xi.(6)
Signature Generation. To achieve secure communication, vehicle Vi with PIDi performs the following signature operations on each traffic-related message mi sent by itself:(a)
Pickui∈Zp∗ at random and calculate Ui=uiP.(b)
Calculateh2i=H2PIDi,Xi.(c)
Calculateh3i=H3PIDi,mi,vpki,Ui,Ti, where Ti is the current timestamp.(d)
Calculatesi=ui+h3ipski+h2iximodp.(e)
Output a single signatureσi=Ui,si on mi.(f)
Sendmi,σi,Ti,vpki,PIDi to the nearby RSU.(7)
Signature Verification. Given a single signature σi=Ui,si on a message mi at timestamp Ti under a pseudonym PIDi and a public key vpki=Qi,Ri, the verifier performs the following verification operations if ΔTi of PIDi and Ti are both valid:(a)
Calculateh1i=H1PIDi,Ri,Ppub.(b)
Calculateh3i=H3PIDi,mi,vpki,Ui,Ti.(c)
Check the single signature verification equation below:(1)siP=Ui+h3iQi+h1iPpub.The verifier acceptsσi if it holds; otherwise, σi is considered invalid.(8)
Aggregate Signature Generation. After receiving n single signatures σi=Ui,sii=1n on messages mii=1n from n vehicles, the RSU performs the following aggregation signature operations:(a)
Calculates=∑i=1nsi.(b)
Output the aggregate signature onmii=1n as σagg=U1,…,Un,s.(9)
Aggregate Signature Verification. Given an aggregate signature σagg=U1,…,Un,s on messages mii=1n under n tuples vpki=Qi,Ri,PIDii=1n, the AS performs the following aggregate signature verification operations if ΔTi and Ti are in the period of validity:(a)
Calculateh1i=H1PIDi,Ri,Ppub for all i∈1,⋯,n.(b)
Calculateh3i=H3PIDi,mi,vpki,Ui,Ti for all i∈1,⋯,n.(c)
Check the aggregation signature verification equation below:(2)sP=∑i=1nUi+∑i=1nh3iQi+h1iPpub.If it holds, the AS accepts and stores messagesmii=1n since σagg is valid.


## 4. Cryptanalysis of Thumbur et al.’s Scheme

Thumbur et al. [18] claimed that their CLAS-based authentication scheme for VANETs is capable of withstanding forgery attacks and achieves various security requirements. Nevertheless, in this section, we provide two attack methods to demonstrate that their scheme is vulnerable to public key replacement attacks and coalition attacks.


### 4.1. Public Key Replacement Attack

Assume that Vi is the target vehicle selected by a Type I adversary A1. A1 obtains Vi’s pseudoidentity PIDi and public key vpki=Qi,Ri and then uses the following attack steps to forge a valid single signature of a message mi∗:(1)
Calculateh1i∗=H1PIDi,Ri,Ppub.(2)
Pickzi∈Zp∗ randomly and calculate Qi∗=ziP−h1i∗Ppub.(3)
Replace the new public key of the target vehicle asvpki∗=Qi∗,Ri.(4)
Pickui∗∈Zp∗ randomly and calculate Ui∗=ui∗P.(5)
Select a desired messagemi∗ and calculate h3i∗=H3PIDi,mi∗,vpki∗,Ui∗,Ti∗, where Ti∗ is the current timestamp.(6)
Calculatesi∗=ui∗+h3i∗zimodp.(7)
Setσi∗=Ui∗,si∗ as a forged single signature on mi∗.Obviously,σi∗ is a valid single signature on mi∗ at Ti∗ under PIDi,vpki∗, since(3)si∗P=ui∗+h3i∗ziP=ui∗P+h3i∗ziP=Ui∗+h3i∗Qi∗+h1i∗Ppub.In the above attack,A1 only replaces the public key of the target vehicle, but the partial private key of the target vehicle is unknown to A1. Therefore, the CLAS-based authentication scheme for VANETs of Thumbur et al. [18] cannot resist public key replacement attacks. The reason why A1 can attack successfully is that Ppub is offset by Qi in siP=Ui+h3iQi+h1iPpub.


### 4.2. Coalition Attack

Two or more malicious vehicles can produce a valid aggregate signature by providing some false single signatures. Without loss of generality, suppose thatV1 and V2 are two malicious vehicles. The coalition attack launched by V1 and V2 is as follows:(1)
V1 arbitrarily selects a message m1∗ and creates a single signature σ1=U1,s1 on m1∗ by invoking the Signature Generation algorithm in Thumbur et al.’s scheme [18].(2)
V2 arbitrarily selects a message m2∗ and creates a single signature σ2=U2,s2 on m2∗ by invoking the Signature Generation algorithm in Thumbur et al.’s scheme [18].(3)
V1 and V2 exchange s1 and s2 in σ1=U1,s1 and σ2=U2,s2 to obtain two invalid single signatures σ1∗=U1,s2 and σ2∗=U2,s1.(4)
After receivingm1∗,σ1∗=U1,s2,T1∗,vpk1,PID1 and m2∗,σ2∗=U2,s1,T2∗,vpk2,PID2 sent by V1 and V2, respectively, the RSU invokes the Aggregate Signature Generation algorithm in Thumbur et al.’s scheme [18] to output an aggregate signature σagg∗=U1,U2,s∗ on m1∗,m2∗, where s∗=s2+s1.Clearly,σi∗ is an invalid single signature on mi∗ at timestamp Ti∗ under the pseudonym PIDi and the public key vpki=Qi,Ri, where i=1,2. However, σagg∗ is a valid aggregate signature for m1∗,m2∗ under vpki=Qi,Ri,PIDii=12, since(4)s∗P=s2+s1P=s1+s2P=U1+h31Q1+h11Ppub+U2+h32Q2+h12Ppub=∑i=12Ui+∑i=12h3iQi+h1iPpub.Therefore, two incorrect single signaturesσ2∗,σ2∗ jointly constructed by V1 and V2 can be used to produce a valid aggregate signature σagg∗. It is concluded that Thumbur et al.’s scheme [18] cannot resist coalition attacks from malicious vehicles. Malicious vehicles can successfully launch coalition attacks because there is no restriction on the order exchange of si in s=∑i=1nsi. If a CLAS-based authentication scheme for VANETs is vulnerable to coalition attacks, the AS is unable to determine whether a few incorrect single signatures produce a valid aggregate signature, and TA cannot track down the vehicle that sent a contentious message.


## 4.1. Public Key Replacement Attack

Assume that Vi is the target vehicle selected by a Type I adversary A1. A1 obtains Vi’s pseudoidentity PIDi and public key vpki=Qi,Ri and then uses the following attack steps to forge a valid single signature of a message mi∗:(1)
Calculateh1i∗=H1PIDi,Ri,Ppub.(2)
Pickzi∈Zp∗ randomly and calculate Qi∗=ziP−h1i∗Ppub.(3)
Replace the new public key of the target vehicle asvpki∗=Qi∗,Ri.(4)
Pickui∗∈Zp∗ randomly and calculate Ui∗=ui∗P.(5)
Select a desired messagemi∗ and calculate h3i∗=H3PIDi,mi∗,vpki∗,Ui∗,Ti∗, where Ti∗ is the current timestamp.(6)
Calculatesi∗=ui∗+h3i∗zimodp.(7)
Setσi∗=Ui∗,si∗ as a forged single signature on mi∗.Obviously,σi∗ is a valid single signature on mi∗ at Ti∗ under PIDi,vpki∗, since(3)si∗P=ui∗+h3i∗ziP=ui∗P+h3i∗ziP=Ui∗+h3i∗Qi∗+h1i∗Ppub.In the above attack,A1 only replaces the public key of the target vehicle, but the partial private key of the target vehicle is unknown to A1. Therefore, the CLAS-based authentication scheme for VANETs of Thumbur et al. [18] cannot resist public key replacement attacks. The reason why A1 can attack successfully is that Ppub is offset by Qi in siP=Ui+h3iQi+h1iPpub.


## 4.2. Coalition Attack

Two or more malicious vehicles can produce a valid aggregate signature by providing some false single signatures. Without loss of generality, suppose thatV1 and V2 are two malicious vehicles. The coalition attack launched by V1 and V2 is as follows:(1)
V1 arbitrarily selects a message m1∗ and creates a single signature σ1=U1,s1 on m1∗ by invoking the Signature Generation algorithm in Thumbur et al.’s scheme [18].(2)
V2 arbitrarily selects a message m2∗ and creates a single signature σ2=U2,s2 on m2∗ by invoking the Signature Generation algorithm in Thumbur et al.’s scheme [18].(3)
V1 and V2 exchange s1 and s2 in σ1=U1,s1 and σ2=U2,s2 to obtain two invalid single signatures σ1∗=U1,s2 and σ2∗=U2,s1.(4)
After receivingm1∗,σ1∗=U1,s2,T1∗,vpk1,PID1 and m2∗,σ2∗=U2,s1,T2∗,vpk2,PID2 sent by V1 and V2, respectively, the RSU invokes the Aggregate Signature Generation algorithm in Thumbur et al.’s scheme [18] to output an aggregate signature σagg∗=U1,U2,s∗ on m1∗,m2∗, where s∗=s2+s1.Clearly,σi∗ is an invalid single signature on mi∗ at timestamp Ti∗ under the pseudonym PIDi and the public key vpki=Qi,Ri, where i=1,2. However, σagg∗ is a valid aggregate signature for m1∗,m2∗ under vpki=Qi,Ri,PIDii=12, since(4)s∗P=s2+s1P=s1+s2P=U1+h31Q1+h11Ppub+U2+h32Q2+h12Ppub=∑i=12Ui+∑i=12h3iQi+h1iPpub.Therefore, two incorrect single signaturesσ2∗,σ2∗ jointly constructed by V1 and V2 can be used to produce a valid aggregate signature σagg∗. It is concluded that Thumbur et al.’s scheme [18] cannot resist coalition attacks from malicious vehicles. Malicious vehicles can successfully launch coalition attacks because there is no restriction on the order exchange of si in s=∑i=1nsi. If a CLAS-based authentication scheme for VANETs is vulnerable to coalition attacks, the AS is unable to determine whether a few incorrect single signatures produce a valid aggregate signature, and TA cannot track down the vehicle that sent a contentious message.


## 5. Improved Authentication Scheme for VANETs

To enhance the security of the CLAS-based authentication scheme for VANETs proposed by Thumbur et al. [18], we present an improved scheme on the basis of the original scheme and analyze its security and performance.


### 5.1. Our Improved Scheme

We mainly revise the Signature Generation method and the definition of hash functionH2 in Thumbur et al.’s scheme [18] to resist the forgery attacks described in Section 4. Our improved scheme is described as follows:(1)
The algorithmsSystem Setup, Pseudonym Identity Generation, Partial Private Key Generation, and Set Secret Value are the same as those in the scheme in [18]. Note that a hash function H4:0,1∗⟶Zp∗ is added to the System Setup algorithm in the revised scheme.(2)
Vehicle Key Generation. A vehicle Vi sets its private key vski=pski,xi and the corresponding public key vpki=Xi,Ri=xiP,riP. Similarly, the AS sets its private key vskAS=pskAS,xAS and the corresponding public key vpkAS=XAS,RAS=xASP,rASP.(3)
Signature Generation. Vehicle Vi with PIDi utilizes its private key vski=pski,xi to sign a traffic-related message mi as follows:(a)
Pickui∈Zp∗ at random and calculate Ui=uiP.(b)
Calculateh2i=H2PIDi,mi,Ppub,Ui,Ti and h3i=H3PIDi,mi,vpki,Ui,Ti, where Ti is the current timestamp.(c)
Calculatesi=ui+h2ipski+h3iximodp.(d)
Output a single signatureσi=Ui,si on mi.(e)
Sendmi,σi,Ti,vpki,PIDi to the nearby RSU.(4)
Signature Verification. Given a single signature σi=Ui,si on a message mi at timestamp Ti under a pseudonym PIDi and a public key vpki=Xi,Ri, the verifier performs the following verification operations if ΔTi and Ti are both valid:(a)
Calculateh1i=H1PIDi,Ri,Ppub.(b)
Calculateh2i=H2PIDi,mi,Ppub,Ui,Ti and h3i=H3PIDi,mi,vpki,Ui,Ti.(c)
Check the single signature verification equation below:(5)siP=Ui+h2iRi+h1iPpub+h3iXi.The verifier acceptsσi if it holds; otherwise, σi is considered invalid.correctness,(6)siP=ui+h2ipski+h3ixiP=uiP+h2ipskiP+h3ixiP=Ui+h2iRi+h1iPpub+h3iXi.(5)
Aggregate Signature Generation. After receiving n single signatures σi=Ui,sii=1n on messages mii=1n from n vehicles, the RSU utilizes AS’s public key vpkAS=XAS,RAS to aggregate single signatures.(a)
Calculates=H4s1XAS,…,snXAS.(b)
Setσagg=U1,…,Un,s as the aggregate signature on mii=1n.(6)
Aggregate Signature Verification. Given an aggregate signature σagg=U1,…,Un,s on messages mii=1n under n tuples vpki=Xi,Ri,PIDii=1n, the AS utilizes its secret value xAS to perform the following aggregate signature verification operations if ΔTi and Ti in each message mi are in the period of validity:(a)
Calculateh1i=H1PIDi,Ri,Ppub for all i∈1,…,n.(b)
Calculateh2i=H2PIDi,mi,Ppub,Ui,Ti and h3i=H3PIDi,mi,vpki,Ui,Ti for all i∈1,…,n.(c)
Check the aggregation signature verification equation below:(7)s=H4xASU1+h21R1+h11Ppub+h31X1,…,xASUn+h2nRn+h1nPpub+h3nXn.If it holds, AS accepts and stores these messagesmii=1n since σagg is valid.


### 5.2. Security Analysis

Similar to Theorems1 and 2 in [18], we use the following Theorems 1 and 2 to show that our enhanced scheme is secure for Type I and II attackers in the random oracle model. In addition, Theorem 3 proves that the aggregate signature is secure in the enhanced scheme as long as the individual signatures participating in the aggregation are secure.Theorem 1.
In the random oracle model, our improved scheme is existentially unforgeable against Type I attackers under the intractability of the ECDLP.Proof.
Assuming that a Type I attackerA1 can forge a legitimate signature with probability ε1, there exists an algorithm C1 that successfully solves the ECDLP using the forged signature of A1. Given a random ECDLP instance P,Q=yP, where y∈Zp∗ is unknown to C1, in order to calculate y, C1 plays the following interactive game with A1:(1)
Initialization Phase.C1 chooses PID∗ as the challenged pseudonym identity of the target user. Then, C1 picks s∈Zp∗ at random as the master secret key of KGC and calculates Ppub=sP. After that, C1 runs the System Setup algorithm to produce parameters params=p,G,P,Tpub,Ppub,H0,H1,H2,H3,H4 and sends params to A1.(2)
Queries Phase.C1 creates six initially empty lists L0, L1, L2, L3, L4, and LCU. A1 adaptively initiates a series of queries, and C1 responds to them in the following ways:(1)
H0-Queries. When A1 initiates an inquiry about H0bPIDi,1,ΔTi, C1 submits h0i to A1 if there exists the tuple bPIDi,1,ΔTi,h0i in list L0. Otherwise, C1 picks h0i∈Zp∗ at random, assigns h0i=H0bPIDi,1,ΔTi, transmits h0i to A1, and stores bPIDi,1,ΔTi,h0i in L0.(2)
H1-Queries. When A1 initiates an inquiry about H1PIDi,Ri,Ppub, C1 submits h1i to A1 if there exists the tuple PIDi,Ri,Ppub,h1i in list L1. Otherwise, C1 picks h1i∈Zp∗ at random, assigns h1i=H1PIDi,Ri,Ppub, transmits h1i to A1, and stores PIDi,Ri,Ppub,h1i in L1.(3)
H2-Queries. When A1 initiates an inquiry about H2PIDi,mi,Ppub,Ui,Ti, C1 submits h2i to A1 if there exists the tuple PIDi,mi,Ppub,Ui,Ti,h2i in list L2. Otherwise, C1 picks h2i∈Zp∗ at random, assigns h2i=H2PIDi,mi,Ppub,Ui,Ti, transmits h2i to A1, and stores the tuple PIDi,mi,Ppub,Ui,Ti,h2i in L2.(4)
H3-Queries. When A1 initiates an inquiry about H3PIDi,mi,vpki,Ui,Ti, C1 submits h3i to A1 if there exists the tuple PIDi,mi,vpki,Ui,Ti,h3i in list L3. Otherwise, C1 picks h3i∈Zp∗ at random, assigns h3i=H3PIDi,mi,vpki,Ui,Ti, transmits h3i to A1, and stores the tuple PIDi,mi,vpki,Ui,Ti,h3i in L3.(5)
H4-Queries. When A1 initiates an inquiry about H4s1iXAS,…,sniXAS, C1 submits h4i to A1 if there exists the tuple s1iXAS,…,sniXAS,h4i in list L4. Otherwise, C1 picks h4i∈Zp∗ at random, assigns h4i=H4s1iXAS,…,sniXAS, transmits h4i to A1, and stores s1iXAS,…,sniXAS,h4i in L4.(6)
Create-User-Queries. When A1 initiates an inquiry about PIDi, C1 submits vpki=Qi,Ri to A1 if there exists the tuple PIDi,ri,Ri,pski,xi,Xi in list LCU. Otherwise, C1 executes as follows:(a)
IfPIDi=PID∗, C1 randomly picks x∗,h1∗∈Zp∗ and sets R∗=Q, X∗=x∗P, r∗=⊥, psk∗=⊥, and h1∗=H1PID∗,R∗,Ppub. Then, C1 transmits vpk∗=X∗,R∗ to A1 and stores PID∗,R∗,Ppub,h1∗ in L1 and PID∗,⊥,R∗,⊥i,x∗,X∗ in LCU.(b)
IfPIDi≠PID∗, C1 randomly picks xi,ri,h1i∈Zp∗, calculates Ri=riP, Xi=xiP, and pski=ri+sh1imodp, and sets h1i=H1PIDi,Ri,Ppub. Then, C1 transmits vpki=Xi,Ri to A1 and stores PIDi,Ri,Ppub,h1i in L1 and PIDi,ri,Ri,pski,xi,Xi in LCU.(7)
Partial-Private-Key-Queries. When A1 submits an inquiry about PIDi, C1 aborts if PIDi≠PID∗. Otherwise, C1 searches the tuple PIDi,ri,Ri,pski,xi,Xi in LCU and transmits pski to A1.(8)
Set-Secret-Value-Queries. When A1 submits an inquiry about PIDi, C1 searches the tuple PIDi,ri,Ri,pski,xi,Xi in LCU and transmits xi to A1.(9)
Replace-Public-Key-Queries. When A1 submits an inquiry about PIDi,Ri′,Xi′, C1 finds the tuple PIDi,ri,Ri,pski,xi,Xi in LCU and replaces Ri,Xi with Ri′,Xi′.(10)
Sign-Queries. When A1 submits an inquiry about PIDi,mi, C1 does the following:(a)
IfPIDi≠PID∗, C1 runs the Signature Generation algorithm to output a single signature σi=Ui,si on mi and transmits σi to A1.(b)
IfPIDi=PID∗, C1 picks si,h2i,h3i∈Zp∗ at random and the current timestamp Ti. Then, C1 recovers PID∗,R∗,Ppub,h1∗ and PID∗,⊥,R∗,⊥i,x∗,X∗ from L1 and LCU, respectively. After that, C1 sets Ui=siP−h2iR∗+h1∗Ppub−h3iX∗, transmits σi=Ui,si to A1, and stores PID∗,mi,Ppub,Ui,Ti,h2i in L2 and PID∗,mi,vpk∗,Ui,Ti,h3i in L3.(3)
Forgery Phase. After initiating a limited number of the above-mentioned inquiries, A1 creates a valid single signature σ∗=U∗,s∗ on a message m∗ under PIDi and vpki=Xi,Ri. If PIDi≠PID∗, C1 aborts. Otherwise, according to the Forking lemma [20], C1 can obtain another valid signature σ′=U∗,s' with the same random tape and a different value h2i' assigned by H2. Since σ∗=U∗,s∗ and σ′=U∗,s′ are valid, the following equations hold:(8)s∗P=U∗+h2i∗R∗+h1∗Ppub+h3i∗X∗,s′P=U∗+h2i'R∗+h1∗Ppub+h3i∗X∗.
SinceR∗=Q=yP, Ppub=sP, and X∗=x∗P, the following equations can be easily derived from the above two equations:(9)s∗P=U∗+h2i∗yP+h1∗sP+h3i∗X∗,s′P=U∗+h2i′yP+h1∗sP+h3i∗X∗.
Then, we haves∗−s′P=h2i∗−h2i′yP+h2i∗−h2i′h1∗sP. Hence, C1 calculates the solution of the given ECDLP instance as y=h2i∗−h2i′−1s∗−s′−h2i∗−h2i′h1∗smodp.
Letqppk denote the total number of partial private key queries initiated by A1 in the whole game. In Partial-Private-Key-Queries, the probability of C1 completing the game is at least 1−1/qppk+1qppk. In Forgery Phase, the probability that C1 does not terminate the game is at least 1/qppk+1. If A1 can forge a legitimate signature with probability ε1, then C1 successfully solves the ECDLP with probability 1−1/qppk+1qppk1/qppk+1ε1. However, the ECDLP is intractable in polynomial time; hence, our improved scheme is secure against Type I attacks. ▪Theorem 2.
In the random oracle model, our enhanced scheme is existentially unforgeable against Type II attackers under the intractability of the ECDLP.Proof.
Assuming that a Type II attackerA2 can forge a legitimate signature with probability ε2, there exists an algorithm C2 that successfully solves the ECDLP by using the forged signature of A2. Given a random ECDLP instance P,Q=yP, where y∈Zp∗ is unknown to C2, in order to calculate y, C2 plays the following interactive game with A2.(1)
Initialization Phase.A2 chooses s∈Zp∗ at random as KGC’s master secret key and calculates Ppub=sP. Then, A2 runs the System Setup algorithm to output parameters params=p,G,P,Tpub,Ppub,H0,H1,H2,H3,H4. Following that, A2 returns params and s to C2.(2)
Queries Phase.C2 chooses PID∗ as the challenged pseudonym identity of the target user. Similar to Theorem 1, C2 creates six initially empty lists L0, L1, L2, L3, L4, and LCU. A2 adaptively initiates a series of queries, and C2 responds to them in the following ways:(1)
H0-Queries, H1-Queries, H2-Queries, H3-Queries, and H4-Queries are the same as Theorem 1.(2)
Create-User-Queries. When A2 initiates an inquiry about PIDi, C2 submits vpki=Qi,Ri to A2 if there exists the tuple PIDi,ri,Ri,pski,xi,Xi in list LCU. Otherwise, C2 executes as follows:(a)
IfPIDi=PID∗, C2 picks r∗,h1∗∈Zp∗ at random and sets X∗=Q, R∗=r∗P, psk∗=r∗+sh1∗modp, x∗=⊥, and h1∗=H1PID∗,R∗,Ppub. Then, C2 transmits vpk∗=X∗,R∗ to A2 and stores PID∗,R∗,Ppub,h1∗ in L1 and PID∗,r∗,R∗,psk∗,⊥,X∗ in LCU.(b)
IfPIDi≠PID∗, C2 randomly picks xi,ri,h1i∈Zp∗, calculates Ri=riP, Xi=xiP, and pski=ri+sh1imodp, and sets h1i=H1PIDi,Ri,Ppub. Then, C2 transmits vpki=Xi,Ri to A2 and stores PIDi,Ri,Ppub,h1i in L1 and PIDi,ri,Ri,pski,xi,Xi in LCU.(3)
Partial-Private-Key-Queries. When A2 submits an inquiry about PIDi, C2 looks for the tuple PIDi,ri,Ri,pski,xi,Xi in LCU and transmits pski to A2.(4)
Set-Secret-Value-Queries. WhenA2 submits an inquiry about PIDi, C2 aborts if PIDi≠PID∗. Otherwise, C2 finds the tuple PIDi,ri,Ri,pski,xi,Xi in LCU and transmits xi to A2.(5)
Sign-Queries is the same as Theorem 1.(3)
Forgery Phase. After initiating a limited number of the above-mentioned inquiries, A2 generates a valid single signature σ∗=U∗,s∗ on a message m∗ under PIDi and vpki=Xi,Ri. If PIDi≠PID∗, C2 aborts. Otherwise, according to the Forking lemma [20], C2 can obtain another valid signature σ′=U∗,s′ with the same random tape and a different value h3i' assigned by H3. Since σ∗=U∗,s∗ and σ′=U∗,s′ are valid, the following equations hold:(10)s∗P=U∗+h2i∗R∗+h1∗Ppub+h3i∗X∗,s′P=U∗+h2i'R∗+h1∗Ppub+h3i∗X∗.
SinceX∗=Q=yP, Ppub=sP, and R∗=r∗P, the following equations can be easily derived from the above two equations:(11)s∗P=U∗+h2i∗r∗P+h1∗sP+h3i∗yP,s′P=U∗+h2i∗r∗P+h1∗sP+h3i'yP.
Then, we haves∗−s′P=h3i∗−h3i′yP. Hence, C2 calculates the solution of the given ECDLP instance as y=h3i∗−h3i′−1s∗−s′modp.
Letqssv denote the total number of secret value queries initiated by A2 in the whole game. In Set-Secret-Value-Queries, the probability that C2 completes the game is at least 1−1/qssv+1qssv. In Forgery Phase, the probability that C2 does not terminate the game is at least 1/qssv+1. If A2 can forge a legitimate signature with probability ε2, then C2 successfully solves the ECDLP with probability 1−1/qssv+1qssv1/qssv+1ε2. However, the ECDLP is intractable in polynomial time; hence, our enhanced scheme is resistant to Type II attacks. ▪Theorem 3.
Our improved scheme can withstand the coalition attack from malicious vehicles ifH4 is a collision-resistant hash function.Proof.
Ifσagg=U1,⋯,Un,s is a valid aggregate signature, then σagg satisfies the following aggregate signature verification equation:(12)s=H4xASU1+h21R1+h11Ppub+h31X1,…,xASUn+h2nRn+h1nPpub+h3nXn.
From theAggregate Signature Generation algorithm in the improved scheme, it is easy to get(13)s=H4s1XAS,…,snXAS.
According to the collision resistance ofH4, we can obtain(14)siXAS=xASUi+h2iRi+h1iPpub+h3iXi,i∈1,⋯,n.
SinceXAS=xASP, we have(15)xASsiP=xASUi+h2iRi+h1iPpub+h3iXi,i∈1,…,n.
Hence, we can obtain(16)siP=Ui+h2iRi+h1iPpub+h3iXi,i∈1,…,n
This shows that each single signatureσi=Ui,si used to generate σagg is valid.
On the other hand, ifσi=Ui,si is a valid single signature, then σi must satisfy the following single signature verification equation:(17)siP=Ui+h2iRi+h1iPpub+h3iXi,i∈1,…,n.
Then, we can obtain(18)xASsiP=xASUi+h2iRi+h1iPpub+h3iXi,i∈1,…,n.
From the above equations, we can easily derive(19)siXAS=xASUi+h2iRi+h1iPpub+h3iXi,i∈1,…,n.
Hence, we have(20)s=H4s1XAS,…,snXAS=H4xASU1+h21R1+h11Ppub+h31X1,…,xASUn+h2nRn+h1nPpub+h3nXn.
This shows that the aggregate signatureσagg=U1,…,Un,s constructed with σi is valid.
In our improved scheme, it can be seen from the above analysis that an aggregate signature is valid if and only if every single signature participating in the aggregation is valid. Therefore, our enhanced scheme is secure against coalition attacks from malicious vehicles. ▪
We show that the improved scheme satisfies the following security requirements in VANETs:(1)
Resistance to Forgery Attacks. In the Signature Generation algorithm of our improved scheme, the master public key Ppub of KGC is an input of h2i=H2PIDi,mi,Ppub,Ui,Ti, and the public key vpki=Xi,Ri of the vehicle is an input of h3i=H3PIDi,mi,vpki,Ui,Ti. Furthermore, in si=ui+h2ipski+h3iximodp, h2i is bound to the partial private key pski, and h3i is bound to the secret value xi. If either Ppub or vpki is changed in the Signature Verification algorithm, the single signature verification equation siP=Ui+h2iRi+h1iPpub+h3iXi will fail. Hence, it is not feasible for an attacker to forge a single signature by bypassing the secret value or the partial private key of the vehicle. As a result, our improved scheme can withstand the public key replacement attack described in Section 4 as well as the forgery attack from a malicious KGC. More importantly, in the Aggregate Signature Generation algorithm, the collision resistance of the hash function H4s1XAS,…,snXAS ensures that the exchange or illegal modification of any single signature value cannot pass the aggregate signature verification equation in the Aggregate Signature Verification algorithm. Therefore, our scheme is resistant to the coalition attack given in Section 4.(2)
Unlinkability. In our improved scheme, vehicle Vi with the pseudoidentity PIDi transmits message mi and the corresponding signature σi=Ui,si to the RSU, where Ui=uiP and si=ui+h2ipski+h3iximodp. Furthermore, value ui used in the signature σi is random, so the attacker is unable to associate two different messages transmitted by the same vehicle. That is, our improved scheme achieves the unlinkability of messages.(3)
Replay Attack. Because of the openness of wireless networks in VANETs, the signature σi=Ui,si transmitted by the vehicle to the RSU can be easily obtained by an attacker. Timestamp Ti is embedded in h2i=H2PIDi,mi,Ppub,Ui,Ti and h3i=H3PIDi,mi,vpki,Ui,Ti, and si=ui+h2ipski+h3iximodp is a component of signature σi. The RSU uses Ti to check the freshness of message mi and then verifies the validity of signature σi. Hence, our revised scheme is resistant to replay attacks.(4)
Message Authenticity, Nonrepudiation, and Integrity. Compared with the scheme of Thumbur et al. [18], the algorithms Pseudonym Identity Generation, Partial Private Key Generation, and Set Secret Value in our improved scheme are the same as those in the original scheme. Furthermore, we only modify h2i=H2PIDi,mi,Ppub,Ui,Ti in the enhanced scheme, and the remainder of the Signature Generation algorithm is the same as that of the original scheme. The existential unforgeability of our improved scheme is guaranteed by Theorems 1 and 2. Furthermore, the identity information PIDi of the vehicle is embedded in the signature, so that the vehicle cannot deny any previous messages. Therefore, the improved scheme can guarantee authenticity, nonrepudiation, and integrity of messages among the vehicles.(5)
Anonymity and Traceability. To achieve the anonymity of the vehicle during communication, the vehicle uses a pseudonym PIDi=PIDi,1,PIDi,2,ΔTi to communicate with RSU or other vehicles. When a controversial traffic-related message occurs, TA uses its master key b and the vehicle’s pseudonym PIDi to obtain the real identity RIDi=bPIDi,1⊕Ki. Thus, our improved scheme provides anonymity and traceability of the vehicle. It is generally assumed that TA is trustworthy. To further limit the rights of TA, a smart contract can be introduced to store the vehicle’s pseudoidentity PIDi and relevant information on the blockchain during the vehicle’s registration and traceability [21]. The data on the blockchain cannot be tampered with, so it can effectively prevent TA from abusing its rights.


### 5.3. Efficiency Analysis

We evaluate the computational efficiency of our enhanced scheme by adopting the experimental data in [22]. Table 2 provides the measured value of the running time of every cryptographic operation. To evaluate the performance of the scheme based on bilinear pairing, the super singular elliptic curve E:y2=x3+xmodp1 was picked, where the length of prime p1 is 521 bits and the length of an element in G1 is 1024 bits. In order to achieve the same security level, the Koblitz elliptic curve E:y2=x3+ax+bmodp was chosen to evaluate the performance of the scheme without bilinear pairing, where the length of p is 160 bits and the length of an element in G is 320 bits.Table 2
Running time of a single cryptographic operation.
NotationCryptographic operationExecution time (ms)TPBilinear pairing4.441043TPMBilinear pairing scalar multiplication4.87256TsmECC scalar multiplication0.165217TaddECC point addition0.001404THMap to point hash function0.142682We compare the computational overhead of the improved scheme with the other four CLAS-based authentication schemes in VAENTs [4, 13, 14, 18] in signing a message, verifying the signature of a message and verifying the aggregate signature of n messages. The comparison results are shown in Table 3. We do not consider the computational overhead of ordinary hash function, the modular addition operation, and the modular multiplication operation because their execution time is very short.Table 3
Comparison of computational overhead.
SchemeSingle signature generation (ms)Single signature verification (ms)Aggregate signature verificationKumar et al. [4]4Tsm+2Tadd+TH ≈0.8063583Tsm+2TH+4TP+2TPM ≈28.2903073nTsm+3n−1Tadd+4TP+2TPMMei et al. [13]4Tsm+2Tadd+2TH ≈0.949042Tsm+2TH+4TP+2TPM ≈28.125092nTsm+2n−2Tadd+2TH+4TP+2TPMXu et al. [14]3Tsm+Tadd+TH ≈0.6397372Tsm+Tadd+2TH+3TP+TPM ≈18.8128912nTsm+3n−2Tadd+n+1TH+3TP+TPMThumbur et al. [18]Tsm≈0.1652173Tsm+2Tadd ≈0.4984592n+1Tsm+3n−1TaddOur schemeTsm≈0.1652174Tsm+3Tadd ≈0.665084nTsm+3nTaddNote.n: the number of messages.The time cost of our improved scheme and Thumbur et al.’s scheme [18] to generate a single signature is 0.168785 ms, which is the minimum time overhead among all schemes [4, 13, 14, 18]. In addition, the time cost of verifying a single signature and an aggregate signature in [18] is slightly lower than that in the proposed scheme. Nevertheless, in Section 4, we have shown that Thumbur et al.’s scheme [18] is insecure; hence, it cannot be practically applied to VANETS.As demonstrated in Figure2, in the generation and verification phase of a single signature, the computational cost of our scheme and Thumbur et al.’s scheme [18] is lower than those of the other three schemes [4, 13, 14]. Furthermore, our scheme requires somewhat more processing time to validate the legality of a single signature compared to Thumbur et al.’s scheme [18], but our scheme has the ability to resist all kinds of attacks given in Section 4.Figure 2
Comparison of the computational cost of a single signature.Table4 and Figure 3 provide the comparison results of the five schemes regarding communication costs. As can be seen from Table 4 and Figure 3, our improved scheme and Thumbur et al.’s scheme [18] have the shortest single signature length, so the vehicle has a lower communication overhead. However, with the exception of our improved scheme, the other four schemes [4, 13, 14, 18] are incapable of resisting the coalition attack described in Section 4.2. Hence, our improved scheme enhances the security while maintaining the communication performance of the original scheme.Figure 3
Comparison of single signature length.Table 4
Comparison of communication overhead.
SchemeSingle signature lengthAggregate signature lengthCoalition attackTypes I and II attacksKumar et al. [4]2G1  = 2048 bitsn+1G1=1024n+1 bitsNoYesMei et al. [13]2G1  = 2048 bits2G1  = 2048 bitsNoYesXu et al. [14]2G1  = 2048 bitsn+1G1=1024n+1 bitsNoYesThumbur et al. [18]G+Zp∗  = 480 bitsnG+Zp∗  = 320n + 160 bitsNoNoOur schemeG+Zp∗  = 480 bitsnG+Zp∗  = 320n + 160 bitsYesYesNote.n: the number of messages.


## 5.1. Our Improved Scheme

We mainly revise the Signature Generation method and the definition of hash functionH2 in Thumbur et al.’s scheme [18] to resist the forgery attacks described in Section 4. Our improved scheme is described as follows:(1)
The algorithmsSystem Setup, Pseudonym Identity Generation, Partial Private Key Generation, and Set Secret Value are the same as those in the scheme in [18]. Note that a hash function H4:0,1∗⟶Zp∗ is added to the System Setup algorithm in the revised scheme.(2)
Vehicle Key Generation. A vehicle Vi sets its private key vski=pski,xi and the corresponding public key vpki=Xi,Ri=xiP,riP. Similarly, the AS sets its private key vskAS=pskAS,xAS and the corresponding public key vpkAS=XAS,RAS=xASP,rASP.(3)
Signature Generation. Vehicle Vi with PIDi utilizes its private key vski=pski,xi to sign a traffic-related message mi as follows:(a)
Pickui∈Zp∗ at random and calculate Ui=uiP.(b)
Calculateh2i=H2PIDi,mi,Ppub,Ui,Ti and h3i=H3PIDi,mi,vpki,Ui,Ti, where Ti is the current timestamp.(c)
Calculatesi=ui+h2ipski+h3iximodp.(d)
Output a single signatureσi=Ui,si on mi.(e)
Sendmi,σi,Ti,vpki,PIDi to the nearby RSU.(4)
Signature Verification. Given a single signature σi=Ui,si on a message mi at timestamp Ti under a pseudonym PIDi and a public key vpki=Xi,Ri, the verifier performs the following verification operations if ΔTi and Ti are both valid:(a)
Calculateh1i=H1PIDi,Ri,Ppub.(b)
Calculateh2i=H2PIDi,mi,Ppub,Ui,Ti and h3i=H3PIDi,mi,vpki,Ui,Ti.(c)
Check the single signature verification equation below:(5)siP=Ui+h2iRi+h1iPpub+h3iXi.The verifier acceptsσi if it holds; otherwise, σi is considered invalid.correctness,(6)siP=ui+h2ipski+h3ixiP=uiP+h2ipskiP+h3ixiP=Ui+h2iRi+h1iPpub+h3iXi.(5)
Aggregate Signature Generation. After receiving n single signatures σi=Ui,sii=1n on messages mii=1n from n vehicles, the RSU utilizes AS’s public key vpkAS=XAS,RAS to aggregate single signatures.(a)
Calculates=H4s1XAS,…,snXAS.(b)
Setσagg=U1,…,Un,s as the aggregate signature on mii=1n.(6)
Aggregate Signature Verification. Given an aggregate signature σagg=U1,…,Un,s on messages mii=1n under n tuples vpki=Xi,Ri,PIDii=1n, the AS utilizes its secret value xAS to perform the following aggregate signature verification operations if ΔTi and Ti in each message mi are in the period of validity:(a)
Calculateh1i=H1PIDi,Ri,Ppub for all i∈1,…,n.(b)
Calculateh2i=H2PIDi,mi,Ppub,Ui,Ti and h3i=H3PIDi,mi,vpki,Ui,Ti for all i∈1,…,n.(c)
Check the aggregation signature verification equation below:(7)s=H4xASU1+h21R1+h11Ppub+h31X1,…,xASUn+h2nRn+h1nPpub+h3nXn.If it holds, AS accepts and stores these messagesmii=1n since σagg is valid.


## 5.2. Security Analysis

Similar to Theorems1 and 2 in [18], we use the following Theorems 1 and 2 to show that our enhanced scheme is secure for Type I and II attackers in the random oracle model. In addition, Theorem 3 proves that the aggregate signature is secure in the enhanced scheme as long as the individual signatures participating in the aggregation are secure.Theorem 1.
In the random oracle model, our improved scheme is existentially unforgeable against Type I attackers under the intractability of the ECDLP.Proof.
Assuming that a Type I attackerA1 can forge a legitimate signature with probability ε1, there exists an algorithm C1 that successfully solves the ECDLP using the forged signature of A1. Given a random ECDLP instance P,Q=yP, where y∈Zp∗ is unknown to C1, in order to calculate y, C1 plays the following interactive game with A1:(1)
Initialization Phase.C1 chooses PID∗ as the challenged pseudonym identity of the target user. Then, C1 picks s∈Zp∗ at random as the master secret key of KGC and calculates Ppub=sP. After that, C1 runs the System Setup algorithm to produce parameters params=p,G,P,Tpub,Ppub,H0,H1,H2,H3,H4 and sends params to A1.(2)
Queries Phase.C1 creates six initially empty lists L0, L1, L2, L3, L4, and LCU. A1 adaptively initiates a series of queries, and C1 responds to them in the following ways:(1)
H0-Queries. When A1 initiates an inquiry about H0bPIDi,1,ΔTi, C1 submits h0i to A1 if there exists the tuple bPIDi,1,ΔTi,h0i in list L0. Otherwise, C1 picks h0i∈Zp∗ at random, assigns h0i=H0bPIDi,1,ΔTi, transmits h0i to A1, and stores bPIDi,1,ΔTi,h0i in L0.(2)
H1-Queries. When A1 initiates an inquiry about H1PIDi,Ri,Ppub, C1 submits h1i to A1 if there exists the tuple PIDi,Ri,Ppub,h1i in list L1. Otherwise, C1 picks h1i∈Zp∗ at random, assigns h1i=H1PIDi,Ri,Ppub, transmits h1i to A1, and stores PIDi,Ri,Ppub,h1i in L1.(3)
H2-Queries. When A1 initiates an inquiry about H2PIDi,mi,Ppub,Ui,Ti, C1 submits h2i to A1 if there exists the tuple PIDi,mi,Ppub,Ui,Ti,h2i in list L2. Otherwise, C1 picks h2i∈Zp∗ at random, assigns h2i=H2PIDi,mi,Ppub,Ui,Ti, transmits h2i to A1, and stores the tuple PIDi,mi,Ppub,Ui,Ti,h2i in L2.(4)
H3-Queries. When A1 initiates an inquiry about H3PIDi,mi,vpki,Ui,Ti, C1 submits h3i to A1 if there exists the tuple PIDi,mi,vpki,Ui,Ti,h3i in list L3. Otherwise, C1 picks h3i∈Zp∗ at random, assigns h3i=H3PIDi,mi,vpki,Ui,Ti, transmits h3i to A1, and stores the tuple PIDi,mi,vpki,Ui,Ti,h3i in L3.(5)
H4-Queries. When A1 initiates an inquiry about H4s1iXAS,…,sniXAS, C1 submits h4i to A1 if there exists the tuple s1iXAS,…,sniXAS,h4i in list L4. Otherwise, C1 picks h4i∈Zp∗ at random, assigns h4i=H4s1iXAS,…,sniXAS, transmits h4i to A1, and stores s1iXAS,…,sniXAS,h4i in L4.(6)
Create-User-Queries. When A1 initiates an inquiry about PIDi, C1 submits vpki=Qi,Ri to A1 if there exists the tuple PIDi,ri,Ri,pski,xi,Xi in list LCU. Otherwise, C1 executes as follows:(a)
IfPIDi=PID∗, C1 randomly picks x∗,h1∗∈Zp∗ and sets R∗=Q, X∗=x∗P, r∗=⊥, psk∗=⊥, and h1∗=H1PID∗,R∗,Ppub. Then, C1 transmits vpk∗=X∗,R∗ to A1 and stores PID∗,R∗,Ppub,h1∗ in L1 and PID∗,⊥,R∗,⊥i,x∗,X∗ in LCU.(b)
IfPIDi≠PID∗, C1 randomly picks xi,ri,h1i∈Zp∗, calculates Ri=riP, Xi=xiP, and pski=ri+sh1imodp, and sets h1i=H1PIDi,Ri,Ppub. Then, C1 transmits vpki=Xi,Ri to A1 and stores PIDi,Ri,Ppub,h1i in L1 and PIDi,ri,Ri,pski,xi,Xi in LCU.(7)
Partial-Private-Key-Queries. When A1 submits an inquiry about PIDi, C1 aborts if PIDi≠PID∗. Otherwise, C1 searches the tuple PIDi,ri,Ri,pski,xi,Xi in LCU and transmits pski to A1.(8)
Set-Secret-Value-Queries. When A1 submits an inquiry about PIDi, C1 searches the tuple PIDi,ri,Ri,pski,xi,Xi in LCU and transmits xi to A1.(9)
Replace-Public-Key-Queries. When A1 submits an inquiry about PIDi,Ri′,Xi′, C1 finds the tuple PIDi,ri,Ri,pski,xi,Xi in LCU and replaces Ri,Xi with Ri′,Xi′.(10)
Sign-Queries. When A1 submits an inquiry about PIDi,mi, C1 does the following:(a)
IfPIDi≠PID∗, C1 runs the Signature Generation algorithm to output a single signature σi=Ui,si on mi and transmits σi to A1.(b)
IfPIDi=PID∗, C1 picks si,h2i,h3i∈Zp∗ at random and the current timestamp Ti. Then, C1 recovers PID∗,R∗,Ppub,h1∗ and PID∗,⊥,R∗,⊥i,x∗,X∗ from L1 and LCU, respectively. After that, C1 sets Ui=siP−h2iR∗+h1∗Ppub−h3iX∗, transmits σi=Ui,si to A1, and stores PID∗,mi,Ppub,Ui,Ti,h2i in L2 and PID∗,mi,vpk∗,Ui,Ti,h3i in L3.(3)
Forgery Phase. After initiating a limited number of the above-mentioned inquiries, A1 creates a valid single signature σ∗=U∗,s∗ on a message m∗ under PIDi and vpki=Xi,Ri. If PIDi≠PID∗, C1 aborts. Otherwise, according to the Forking lemma [20], C1 can obtain another valid signature σ′=U∗,s' with the same random tape and a different value h2i' assigned by H2. Since σ∗=U∗,s∗ and σ′=U∗,s′ are valid, the following equations hold:(8)s∗P=U∗+h2i∗R∗+h1∗Ppub+h3i∗X∗,s′P=U∗+h2i'R∗+h1∗Ppub+h3i∗X∗.
SinceR∗=Q=yP, Ppub=sP, and X∗=x∗P, the following equations can be easily derived from the above two equations:(9)s∗P=U∗+h2i∗yP+h1∗sP+h3i∗X∗,s′P=U∗+h2i′yP+h1∗sP+h3i∗X∗.
Then, we haves∗−s′P=h2i∗−h2i′yP+h2i∗−h2i′h1∗sP. Hence, C1 calculates the solution of the given ECDLP instance as y=h2i∗−h2i′−1s∗−s′−h2i∗−h2i′h1∗smodp.
Letqppk denote the total number of partial private key queries initiated by A1 in the whole game. In Partial-Private-Key-Queries, the probability of C1 completing the game is at least 1−1/qppk+1qppk. In Forgery Phase, the probability that C1 does not terminate the game is at least 1/qppk+1. If A1 can forge a legitimate signature with probability ε1, then C1 successfully solves the ECDLP with probability 1−1/qppk+1qppk1/qppk+1ε1. However, the ECDLP is intractable in polynomial time; hence, our improved scheme is secure against Type I attacks. ▪Theorem 2.
In the random oracle model, our enhanced scheme is existentially unforgeable against Type II attackers under the intractability of the ECDLP.Proof.
Assuming that a Type II attackerA2 can forge a legitimate signature with probability ε2, there exists an algorithm C2 that successfully solves the ECDLP by using the forged signature of A2. Given a random ECDLP instance P,Q=yP, where y∈Zp∗ is unknown to C2, in order to calculate y, C2 plays the following interactive game with A2.(1)
Initialization Phase.A2 chooses s∈Zp∗ at random as KGC’s master secret key and calculates Ppub=sP. Then, A2 runs the System Setup algorithm to output parameters params=p,G,P,Tpub,Ppub,H0,H1,H2,H3,H4. Following that, A2 returns params and s to C2.(2)
Queries Phase.C2 chooses PID∗ as the challenged pseudonym identity of the target user. Similar to Theorem 1, C2 creates six initially empty lists L0, L1, L2, L3, L4, and LCU. A2 adaptively initiates a series of queries, and C2 responds to them in the following ways:(1)
H0-Queries, H1-Queries, H2-Queries, H3-Queries, and H4-Queries are the same as Theorem 1.(2)
Create-User-Queries. When A2 initiates an inquiry about PIDi, C2 submits vpki=Qi,Ri to A2 if there exists the tuple PIDi,ri,Ri,pski,xi,Xi in list LCU. Otherwise, C2 executes as follows:(a)
IfPIDi=PID∗, C2 picks r∗,h1∗∈Zp∗ at random and sets X∗=Q, R∗=r∗P, psk∗=r∗+sh1∗modp, x∗=⊥, and h1∗=H1PID∗,R∗,Ppub. Then, C2 transmits vpk∗=X∗,R∗ to A2 and stores PID∗,R∗,Ppub,h1∗ in L1 and PID∗,r∗,R∗,psk∗,⊥,X∗ in LCU.(b)
IfPIDi≠PID∗, C2 randomly picks xi,ri,h1i∈Zp∗, calculates Ri=riP, Xi=xiP, and pski=ri+sh1imodp, and sets h1i=H1PIDi,Ri,Ppub. Then, C2 transmits vpki=Xi,Ri to A2 and stores PIDi,Ri,Ppub,h1i in L1 and PIDi,ri,Ri,pski,xi,Xi in LCU.(3)
Partial-Private-Key-Queries. When A2 submits an inquiry about PIDi, C2 looks for the tuple PIDi,ri,Ri,pski,xi,Xi in LCU and transmits pski to A2.(4)
Set-Secret-Value-Queries. WhenA2 submits an inquiry about PIDi, C2 aborts if PIDi≠PID∗. Otherwise, C2 finds the tuple PIDi,ri,Ri,pski,xi,Xi in LCU and transmits xi to A2.(5)
Sign-Queries is the same as Theorem 1.(3)
Forgery Phase. After initiating a limited number of the above-mentioned inquiries, A2 generates a valid single signature σ∗=U∗,s∗ on a message m∗ under PIDi and vpki=Xi,Ri. If PIDi≠PID∗, C2 aborts. Otherwise, according to the Forking lemma [20], C2 can obtain another valid signature σ′=U∗,s′ with the same random tape and a different value h3i' assigned by H3. Since σ∗=U∗,s∗ and σ′=U∗,s′ are valid, the following equations hold:(10)s∗P=U∗+h2i∗R∗+h1∗Ppub+h3i∗X∗,s′P=U∗+h2i'R∗+h1∗Ppub+h3i∗X∗.
SinceX∗=Q=yP, Ppub=sP, and R∗=r∗P, the following equations can be easily derived from the above two equations:(11)s∗P=U∗+h2i∗r∗P+h1∗sP+h3i∗yP,s′P=U∗+h2i∗r∗P+h1∗sP+h3i'yP.
Then, we haves∗−s′P=h3i∗−h3i′yP. Hence, C2 calculates the solution of the given ECDLP instance as y=h3i∗−h3i′−1s∗−s′modp.
Letqssv denote the total number of secret value queries initiated by A2 in the whole game. In Set-Secret-Value-Queries, the probability that C2 completes the game is at least 1−1/qssv+1qssv. In Forgery Phase, the probability that C2 does not terminate the game is at least 1/qssv+1. If A2 can forge a legitimate signature with probability ε2, then C2 successfully solves the ECDLP with probability 1−1/qssv+1qssv1/qssv+1ε2. However, the ECDLP is intractable in polynomial time; hence, our enhanced scheme is resistant to Type II attacks. ▪Theorem 3.
Our improved scheme can withstand the coalition attack from malicious vehicles ifH4 is a collision-resistant hash function.Proof.
Ifσagg=U1,⋯,Un,s is a valid aggregate signature, then σagg satisfies the following aggregate signature verification equation:(12)s=H4xASU1+h21R1+h11Ppub+h31X1,…,xASUn+h2nRn+h1nPpub+h3nXn.
From theAggregate Signature Generation algorithm in the improved scheme, it is easy to get(13)s=H4s1XAS,…,snXAS.
According to the collision resistance ofH4, we can obtain(14)siXAS=xASUi+h2iRi+h1iPpub+h3iXi,i∈1,⋯,n.
SinceXAS=xASP, we have(15)xASsiP=xASUi+h2iRi+h1iPpub+h3iXi,i∈1,…,n.
Hence, we can obtain(16)siP=Ui+h2iRi+h1iPpub+h3iXi,i∈1,…,n
This shows that each single signatureσi=Ui,si used to generate σagg is valid.
On the other hand, ifσi=Ui,si is a valid single signature, then σi must satisfy the following single signature verification equation:(17)siP=Ui+h2iRi+h1iPpub+h3iXi,i∈1,…,n.
Then, we can obtain(18)xASsiP=xASUi+h2iRi+h1iPpub+h3iXi,i∈1,…,n.
From the above equations, we can easily derive(19)siXAS=xASUi+h2iRi+h1iPpub+h3iXi,i∈1,…,n.
Hence, we have(20)s=H4s1XAS,…,snXAS=H4xASU1+h21R1+h11Ppub+h31X1,…,xASUn+h2nRn+h1nPpub+h3nXn.
This shows that the aggregate signatureσagg=U1,…,Un,s constructed with σi is valid.
In our improved scheme, it can be seen from the above analysis that an aggregate signature is valid if and only if every single signature participating in the aggregation is valid. Therefore, our enhanced scheme is secure against coalition attacks from malicious vehicles. ▪
We show that the improved scheme satisfies the following security requirements in VANETs:(1)
Resistance to Forgery Attacks. In the Signature Generation algorithm of our improved scheme, the master public key Ppub of KGC is an input of h2i=H2PIDi,mi,Ppub,Ui,Ti, and the public key vpki=Xi,Ri of the vehicle is an input of h3i=H3PIDi,mi,vpki,Ui,Ti. Furthermore, in si=ui+h2ipski+h3iximodp, h2i is bound to the partial private key pski, and h3i is bound to the secret value xi. If either Ppub or vpki is changed in the Signature Verification algorithm, the single signature verification equation siP=Ui+h2iRi+h1iPpub+h3iXi will fail. Hence, it is not feasible for an attacker to forge a single signature by bypassing the secret value or the partial private key of the vehicle. As a result, our improved scheme can withstand the public key replacement attack described in Section 4 as well as the forgery attack from a malicious KGC. More importantly, in the Aggregate Signature Generation algorithm, the collision resistance of the hash function H4s1XAS,…,snXAS ensures that the exchange or illegal modification of any single signature value cannot pass the aggregate signature verification equation in the Aggregate Signature Verification algorithm. Therefore, our scheme is resistant to the coalition attack given in Section 4.(2)
Unlinkability. In our improved scheme, vehicle Vi with the pseudoidentity PIDi transmits message mi and the corresponding signature σi=Ui,si to the RSU, where Ui=uiP and si=ui+h2ipski+h3iximodp. Furthermore, value ui used in the signature σi is random, so the attacker is unable to associate two different messages transmitted by the same vehicle. That is, our improved scheme achieves the unlinkability of messages.(3)
Replay Attack. Because of the openness of wireless networks in VANETs, the signature σi=Ui,si transmitted by the vehicle to the RSU can be easily obtained by an attacker. Timestamp Ti is embedded in h2i=H2PIDi,mi,Ppub,Ui,Ti and h3i=H3PIDi,mi,vpki,Ui,Ti, and si=ui+h2ipski+h3iximodp is a component of signature σi. The RSU uses Ti to check the freshness of message mi and then verifies the validity of signature σi. Hence, our revised scheme is resistant to replay attacks.(4)
Message Authenticity, Nonrepudiation, and Integrity. Compared with the scheme of Thumbur et al. [18], the algorithms Pseudonym Identity Generation, Partial Private Key Generation, and Set Secret Value in our improved scheme are the same as those in the original scheme. Furthermore, we only modify h2i=H2PIDi,mi,Ppub,Ui,Ti in the enhanced scheme, and the remainder of the Signature Generation algorithm is the same as that of the original scheme. The existential unforgeability of our improved scheme is guaranteed by Theorems 1 and 2. Furthermore, the identity information PIDi of the vehicle is embedded in the signature, so that the vehicle cannot deny any previous messages. Therefore, the improved scheme can guarantee authenticity, nonrepudiation, and integrity of messages among the vehicles.(5)
Anonymity and Traceability. To achieve the anonymity of the vehicle during communication, the vehicle uses a pseudonym PIDi=PIDi,1,PIDi,2,ΔTi to communicate with RSU or other vehicles. When a controversial traffic-related message occurs, TA uses its master key b and the vehicle’s pseudonym PIDi to obtain the real identity RIDi=bPIDi,1⊕Ki. Thus, our improved scheme provides anonymity and traceability of the vehicle. It is generally assumed that TA is trustworthy. To further limit the rights of TA, a smart contract can be introduced to store the vehicle’s pseudoidentity PIDi and relevant information on the blockchain during the vehicle’s registration and traceability [21]. The data on the blockchain cannot be tampered with, so it can effectively prevent TA from abusing its rights.


## 5.3. Efficiency Analysis

We evaluate the computational efficiency of our enhanced scheme by adopting the experimental data in [22]. Table 2 provides the measured value of the running time of every cryptographic operation. To evaluate the performance of the scheme based on bilinear pairing, the super singular elliptic curve E:y2=x3+xmodp1 was picked, where the length of prime p1 is 521 bits and the length of an element in G1 is 1024 bits. In order to achieve the same security level, the Koblitz elliptic curve E:y2=x3+ax+bmodp was chosen to evaluate the performance of the scheme without bilinear pairing, where the length of p is 160 bits and the length of an element in G is 320 bits.Table 2
Running time of a single cryptographic operation.
NotationCryptographic operationExecution time (ms)TPBilinear pairing4.441043TPMBilinear pairing scalar multiplication4.87256TsmECC scalar multiplication0.165217TaddECC point addition0.001404THMap to point hash function0.142682We compare the computational overhead of the improved scheme with the other four CLAS-based authentication schemes in VAENTs [4, 13, 14, 18] in signing a message, verifying the signature of a message and verifying the aggregate signature of n messages. The comparison results are shown in Table 3. We do not consider the computational overhead of ordinary hash function, the modular addition operation, and the modular multiplication operation because their execution time is very short.Table 3
Comparison of computational overhead.
SchemeSingle signature generation (ms)Single signature verification (ms)Aggregate signature verificationKumar et al. [4]4Tsm+2Tadd+TH ≈0.8063583Tsm+2TH+4TP+2TPM ≈28.2903073nTsm+3n−1Tadd+4TP+2TPMMei et al. [13]4Tsm+2Tadd+2TH ≈0.949042Tsm+2TH+4TP+2TPM ≈28.125092nTsm+2n−2Tadd+2TH+4TP+2TPMXu et al. [14]3Tsm+Tadd+TH ≈0.6397372Tsm+Tadd+2TH+3TP+TPM ≈18.8128912nTsm+3n−2Tadd+n+1TH+3TP+TPMThumbur et al. [18]Tsm≈0.1652173Tsm+2Tadd ≈0.4984592n+1Tsm+3n−1TaddOur schemeTsm≈0.1652174Tsm+3Tadd ≈0.665084nTsm+3nTaddNote.n: the number of messages.The time cost of our improved scheme and Thumbur et al.’s scheme [18] to generate a single signature is 0.168785 ms, which is the minimum time overhead among all schemes [4, 13, 14, 18]. In addition, the time cost of verifying a single signature and an aggregate signature in [18] is slightly lower than that in the proposed scheme. Nevertheless, in Section 4, we have shown that Thumbur et al.’s scheme [18] is insecure; hence, it cannot be practically applied to VANETS.As demonstrated in Figure2, in the generation and verification phase of a single signature, the computational cost of our scheme and Thumbur et al.’s scheme [18] is lower than those of the other three schemes [4, 13, 14]. Furthermore, our scheme requires somewhat more processing time to validate the legality of a single signature compared to Thumbur et al.’s scheme [18], but our scheme has the ability to resist all kinds of attacks given in Section 4.Figure 2
Comparison of the computational cost of a single signature.Table4 and Figure 3 provide the comparison results of the five schemes regarding communication costs. As can be seen from Table 4 and Figure 3, our improved scheme and Thumbur et al.’s scheme [18] have the shortest single signature length, so the vehicle has a lower communication overhead. However, with the exception of our improved scheme, the other four schemes [4, 13, 14, 18] are incapable of resisting the coalition attack described in Section 4.2. Hence, our improved scheme enhances the security while maintaining the communication performance of the original scheme.Figure 3
Comparison of single signature length.Table 4
Comparison of communication overhead.
SchemeSingle signature lengthAggregate signature lengthCoalition attackTypes I and II attacksKumar et al. [4]2G1  = 2048 bitsn+1G1=1024n+1 bitsNoYesMei et al. [13]2G1  = 2048 bits2G1  = 2048 bitsNoYesXu et al. [14]2G1  = 2048 bitsn+1G1=1024n+1 bitsNoYesThumbur et al. [18]G+Zp∗  = 480 bitsnG+Zp∗  = 320n + 160 bitsNoNoOur schemeG+Zp∗  = 480 bitsnG+Zp∗  = 320n + 160 bitsYesYesNote.n: the number of messages.


## 6. Conclusions

In 2021, Thumbur et al. [18] presented an efficient CLAS-based authentication scheme for VANETS. In this article, we cryptanalyze their scheme and find that it is insecure against public key replacement attacks and coalition attacks. To improve the security of their scheme, we also present the corresponding improvement scheme. Furthermore, the analysis results demonstrate that the improved scheme meets a variety of security requirements. However, some security properties such as identity revocation and authentication [23–25] are not considered in the enhanced and original schemes. Hence, our future work is to design a CLAS-based authentication scheme that supports the revocation mechanism of the vehicle’s identity.



---

*Source: 4472945-2022-04-14.xml*