A certificateless aggregate signature scheme for security and privacy protection in VANET

Abstract

In the vehicular ad hoc network, moving vehicles can keep communicating with each other by entering or leaving the network at any time to establish a new connection. However, since many users transmit a substantial number of messages, it may cause reception delays and affect the entire system. A certificateless aggregate signature scheme can provide a signature compression that keeps the verification cost low. Therefore, it is beneficial for environments constrained by time, bandwidth, and storage, such as vehicular ad hoc network. In recent years, several certificateless aggregate signature schemes have been proposed. Unfortunately, some of them still have some security and privacy issues under specific existing attacks. This article offers an authentication scheme that can improve security, privacy, and efficiency. First, we apply the certificateless aggregate signature method to prevent the onboard unit devices from leaking sensitive information when sending messages. The scheme is proven to be secure against the Type-1 $({\mathcal{A}}_1)$ and Type-2 $({\mathcal{A}}_2)$ adversaries in the random oracle model under the computational Diffie–Hellman problem assumption. Then, the performance evaluation demonstrates that our proposed scheme is more suitable for deployment in vehicular ad hoc network environments.

Introduction

The vehicular ad hoc network (VANET) is derived from the concept of the mobile ad hoc network (MANET). ¹ It has two communication methods: vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) communications. All smart cars are equipped with onboard units (OBU), which can communicate with each other wirelessly through dedicated short-range communication (DSRC) protocol. ² The device can alert the driver in emergencies (e.g. the vehicle is too close to the vehicle in the front) and issue a collision warning to avoid accidents. In V2I communication, a vehicle can communicate with a roadside unit (RSU) and make a service request. The combination of vehicles and a global positioning system (GPS) obtains road traffic conditions through the transmission of messages and plans a perfect driving route. ³ As a result, road congestion is reduced, and the driving experience is improved.

VANET’s infrastructure consists of three main components: OBU, RSU, and trusted authority (TA) (i.e. trace authority (TRA), and key generator center (KGC)). ⁴ For a legal member in the VANET environment, an OBU must be equipped to enable it as a network node and communicate with other legal devices. The OBU contains the user interface, DSRC communication media, GPS, a computing power processor, an event data recorder (EDR), sensors, storage devices, and tamper-proof devices (TPD). ⁵ RSU allows OBU to communicate with TRA. The RSU communicates with the OBU through open and insecure wireless network channels, while, on the other hand, it connects to the TRA through a secure channel. TRA is responsible for registering RSU and vehicle, generating pseudonyms for the vehicle, and in case of dispute, it can trace the vehicles’ real identity. Meanwhile, KGC is in charge of producing public system parameters and preloading them on RSUs and OBUs in the off-line/on-line mode. It also generates and distributes the partial private keys for RSUs and vehicles. The general topology of VANET is shown in Figure 1.

Figure 1.

The topology of VANET.

Despite all the convincing features provided by VANET, it also has several challenges in its security and privacy.^6,7 In VANET, V2V and V2I communications are taking place on the open wireless communication channel, which is naturally not secure. Therefore, the message must be acknowledged to ensure that it was sent by a legitimate device and withstand various attacks during the transmission. The transmitted message contains sensitive personal information and cannot be leaked. When a large number of OBU devices send messages to the other OBUs and RSU simultaneously, this large number of messages must be verified. This process will increase the verification time, resulting in a reception delay of other road traffic emergencies and essential messages. In addition, another issue that needs to be considered is the significant mobility of vehicles on the road. This condition makes VANETs’ topology rapidly shift, resulting in the connection between vehicles that can change at any time. If the excessive load can disable services for each device, then the VANET environment will be severely affected. Therefore, a robust and lightweight authentication mechanism is critically needed to satisfy the security, privacy, and efficiency of the information dissemination and verification processes in VANET.

In traditional public-key cryptography (PKC), each public key must generate a corresponding digital certificate.^8,9 When a user wants to send a message to a receiver, they must first obtain the recipient’s public key and then use a certificate to validate the user’s identity. He or she then uses this public key to encrypt the message and send it to the recipient. Not only does this require certification management, but it also increases verification time. In 1984, Shamir ¹⁰ proposed a new concept called ID-based public-key cryptography (ID-PKC) to solve the above problems. The public key in ID-PKC consists of the user’s identity information, such as phone number and email address. Therefore, there is no need to generate a certificate, thereby solving the traditional PKC problem. ¹¹ However, the private key corresponding to the public key is caused by a KGC. If the KGC is compromised, the attacker will obtain all the private keys. Thus, attackers can arbitrarily decrypt other people’s encrypted messages or forge signatures. This attack is called a key escrow problem.

To solve the key escrow problem in ID-PKC, in 2003, Al-Riyami and Paterson ¹² introduced a new concept known as certificateless public key cryptography (CL-PKC). Although CL-PKC also requires a key generating center (KGC), it only generates part of the user’s private key, while the other part is generated by the user locally. As a result, key escrow is overcome, and CL-PKC does not need to create certificates. Furthermore, a scheme called aggregate signature can aggregate multiple signatures generated by different users for different messages into a single signature. This approach not only reduces the length of the signature but also improves verification efficiency. Therefore, based on CL-PKC and aggregate signature advantages, some scholars combined these two methods and proposed a certificateless aggregate signature (CLAS) scheme. This scheme will effectively improve the problem of verifying a large number of messages in VANET.

Related work

The idea of CLAS was first introduced by Castro and Dahab, ⁹ by combining the benefits of aggregate signatures and CL-PKC. Since then, many CLAS schemes have been proposed.^9,13–33 From all of these methods, several scholars pay attention to specific applications on VANET.^{18,19,21,23–33}

In 2015, Horng et al. ¹⁹ proposed a new CLAS scheme based on the certificateless signature scheme (CLS) method for V2I communication in VANET. They claimed that their approach could achieve conditional privacy protection, more efficient in the verification process. Moreover, a small amount of constant pair of calculations can resist forgery on adaptively selected message attacks in the random oracle model (ROM). However, in 2016, Li et al. ²¹ showed that Horng et al.’s ¹⁹ scheme is vulnerable to “malicious but passive” KGC attacks. In 2018, Cui et al. ²⁴ proposed a pairing-free CLAS scheme that has an obvious advantage in efficiency over Horng et al.’s ¹⁹ scheme. However, Zhao et al., ²⁸ Kamil and Ogundoyin, ²⁶ and Li et al. ³¹ found out that Cui et al.’s ²⁴ schemes cannot withstand a malicious KGC attack. Zhao et al. ²⁸ also pointed out that Horng et al.’s ¹⁹ scheme cannot withstand users’ public-key replacement attack. Meanwhile, Ming and Shen ³⁴ showed that Horng et al.’s ¹⁹ scheme could not provide authentication and message integrity and failed to resist common attacks such as replay, modification, impersonation, and man-in-the-middle (MITM) attacks. Kamil and Ogundoyin ²⁶ proposed their full aggregation pairing-free CLAS scheme and made cryptanalysis to Cui et al.’s ²⁴ scheme. However, Zhao et al. ²⁸ found out that Kamil and Ogundoyin’s ²⁶ scheme cannot resist Type-1 and Type-2 adversary attacks.

In the same year as Horng et al., ¹⁹ Malhi and Batra ¹⁸ also proposed their CLAS scheme. They aimed for a low computational cost approach that still maintained its security reliability. They demonstrated that theirs could withstand the unforgeability attack and have a low computational cost. So, they emphasized that their scheme is very suitable for VANET. However, Kumar and Sharma ²³ found that Malhi and Batra’s ¹⁸ scheme is vulnerable to malicious KGC attacks. Meanwhile, Zhang et al. ³⁵ also found out that Malhi and Batra’s ¹⁸ scheme cannot provide identity privacy-preserving.

In 2019, Zhong et al. ²⁵ proposed a full aggregation CLAS scheme for VANET and claimed it has better efficiency than Malhi-Batra’s ¹⁸ scheme. However, Li et al., ³¹ Mei et al., ³² and Kamil and Ogundoyin ²⁹ found out that Zhong et al.’s ²⁵ scheme cannot withstand a malicious KGC attack. In the same year, Kumar et al. ²⁷ proposed their CLAS scheme in VANET and claimed to be unforgeable against adaptive chosen-message attacks. In 2021, Mei et al. ³² proposed a full aggregation CLAS scheme in VANET that claimed more efficient than Kumar and Sharma’s ²³ and Kumar et al.’s ²⁷ schemes. Kamil and Ogundoyin ²⁹ also proposed their full aggregation CLAS scheme in VANET and made cryptanalysis to Zhong et al.’s ²⁵ scheme. They show if Zhong et al.’s ²⁵ and Kumar et al.’s ²⁷ schemes are vulnerable to the signature-forgery attack by a malicious KGC and forgery attack, respectively. Xu et al. ³⁰ proposed their CLAS scheme in VANET that claimed unforgeable against adaptive chosen-message and identity attacks. Recently, Thumbur et al. ³³ proposed the newest pairing-free CLAS scheme and compared it to the other CLAS schemes in VANET that employ computational Diffie-Hellman problem (CDHP) complexity assumption. The scheme results in apparent advantages in computation cost.

The other significant authentication schemes related to the CLAS mechanism in VANET are also published in recent years. Bouakkaz and Semchedine ³⁶ recently introduced an efficient certificateless ring signature (BV-CLRS) with batch verification, a conditional privacy preservation authentication system for use in VANET that is based on traceable certificateless ring signatures. The scheme has significantly decreased computation and communication overhead due to the usage of batch verification. It also claimed to be secure against five types of adversaries. In 2020, Cui et al. ³⁷ suggested a privacy-preserving data downloading scheme with edge computing in VANET. Their method allows the RSU to discover common data by recording encrypted requests sent from adjacent nodes while maintaining the download requests’ secrecy. Elliptic-curve cryptography (ECC), TESLA broadcast authentication, and additive homomorphic encryption algorithms are used to build the scheme. Very recently, Zhang et al. ³⁸ proposed a Chinese remainder theorem (CRT)-based conditional privacy-preserving authentication (PA-CRT) protocol to establish secure communication between vehicles in VANET. The scheme eliminates the requirement for TPDs to hold long-term system secrets. The CRT in this scheme is also claimed to greatly reduce the computational complexity of the TA.

A comparative summary of existing state-of-art CLAS authentication schemes for VANET discussed above is presented in Table 1. In addition, the table elaborates the topology CLAS methods in VANETs, including the number of implemented algorithms (further discussion in Section “Preliminaries”), cryptanalysis improvements over other schemes, and the main contribution of security efficiency.

Table 1.

Literature survey.

Authors	Literature	Main feature and contribution
Malhi and Batra 18	An efficient certificateless aggregate signature scheme for vehicular ad hoc networks.	The scheme comprises nine algorithms: Setup, Registration, Partial-Private-Key-Gen, Vehicle-Key-Gen, Pseudonym-Gen, Sign, Verify, Aggregate, and Aggregate-Verify. Together with Horng et al., 19 they become the first two CLAS schemes in VANET with partial aggregation. First, however, Zhang et al. 35 found out if Malhi-Batra’s scheme cannot provide identity privacy-preserving.
Horng et al. 19	An efficient certificateless aggregate signature with conditional privacy-preserving for vehicular sensor networks.	The scheme comprises seven algorithms: Setup, Pseudonym-Gen/Partial-Private-Key-Gen, Vehicle-Key-Gen, Sign, Verify, Aggregate, and Aggregate-Verify. As a result, this scheme is more efficient than the other CLAS schemes.9,13,15
Li et al. 21	Cryptanalysis and improvement of certificateless aggregate signature with conditional privacy-preserving for vehicular sensor networks.	The scheme comprises seven algorithms: Setup, Pseudonym-Gen/Partial-Private-Key-Gen, Vehicle-Key-Gen, Sign, Verify, Aggregate, and Aggregate-Verify. Li et al. 21 make cryptanalysis and improvement to the Horng et al.’s 19 scheme. They show if that scheme is vulnerable to malicious-but-passive KGC attacks.
Kumar and Sharma 23	On the security of certificateless aggregate signature scheme in vehicular ad hoc networks.	The scheme comprises seven algorithms: Setup, Partial-Private-Key-Gen, Vehicle-Key-Gen, Pseudonym-Gen, Sign, Verify, and Aggregate-Verify. Partial aggregation CLAS scheme. Kumar and Sharma 23 make cryptanalysis and improvement to the Malhi and Batra’s 18 scheme. They show if that scheme is insecure against Type-2 adversary $({\mathcal{A}}_2)$ .
Cui et al. 24	An efficient certificateless aggregate signature without pairings for vehicular ad hoc networks.	The scheme comprises seven algorithms: Setup, Pseudonym-Gen/Partial-Private-Key-Gen, Vehicle-Key-Gen, Sign, Verify, Aggregate, and Aggregate-Verify. As a result, this scheme is more efficient than the other CLAS schemes.9,13,15,19
Zhong et al. 25	Privacy-preserving authentication scheme with full aggregation in VANET.	The scheme comprises eight algorithms: Setup, Pseudonym-Gen, Partial-Private-Key-Gen, Vehicle-Key-Gen, Sign, Verify, Aggregate, and Aggregate-Verify. This scheme provided a complete aggregation and claimed more efficiency than the other CLAS schemes.13,15,18
Kamil and Ogundoyin 26	An improved certificateless aggregate signature scheme without bilinear pairings for vehicular ad hoc networks.	The scheme comprises nine algorithms: Setup, Registration, Partial-Private-Key-Gen, Pseudonym-Gen, Vehicle-Key-Gen, Sign, Verify, Aggregate, and Aggregate-Verify. This scheme provided a complete aggregation and claimed more efficiency than other CLAS schemes in VANET.18,19,21,24,27 Kamil and Ogundoyin 26 make cryptanalysis and improvement to the Cui et al.’s 24 scheme. Moreover, they show if that scheme is vulnerable against forgery attack in Type-2 adversary $({\mathcal{A}}_2)$ .
Zhao et al. 28	An efficient certificateless aggregate signature scheme for the internet of vehicles.	The scheme comprises nine algorithms: Setup, Registration, Pseudonym-Gen, Partial-Private-Key-Gen, Vehicle-Key-Gen, Sign, Verify, Aggregate, and Aggregate-Verify. This scheme is more efficient than other CLAS schemes in VANET19,24,26,27,31 make cryptanalysis and improvement to Kamil-Ogundoyin’s 26 scheme. They show if that scheme is vulnerable to Type-1 and Type-2 adversary attacks. Zhao et al. also claim if Horng et al.’s 19 scheme suffered from Type-1 adversary $({\mathcal{A}}_1)$ .
Kamil-Ogundoyin 29	On the security of privacy-preserving authentication scheme with full aggregation in vehicular ad hoc network.	The scheme comprises eight algorithms: Setup, Pseudonym-Gen, Partial-Private-Key-Gen, Vehicle-Key-Gen, Sign, Verify, Aggregate, and Aggregate-Verify. This scheme provided a full aggregation. Kamil-Ogundoyin 29 makes cryptanalysis and improvement to Zhong et al.’s 25 scheme. They show if Zhong et al.’s 25 and Kumar et al.’s 27 schemes are vulnerable against a signature-forgery attack by Type-2 adversary $({\mathcal{A}}_2)$ and forgery attack, respectively.
Li et al. 31	An efficient certificateless aggregate signature scheme designed for VANET.	The scheme comprises eight algorithms: Setup, Pseudonym-Gen, Partial-Private-Key-Gen, Vehicle-Key-Gen, Sign, Verify, Aggregate, and Aggregate-Verify. This scheme is more efficient than other CLAS schemes in VANET.23,25–27 Li et al. 31 make cryptanalysis and improvement to the Zhong et al.’s 25 scheme. They show if that scheme is vulnerable against forgery attack in Type-2 adversary $({\mathcal{A}}_2)$ .
Mei et al. 32	Efficient certificateless aggregate signature with conditional privacy preservation in IoV.	The scheme comprises eight algorithms: Setup, Pseudonym-Gen, Partial-Private-Key-Gen, Vehicle-Key-Gen, Sign, Verify, Aggregate, and Aggregate-Verify. This scheme provides a complete aggregation and is claimed more efficient than the other CLAS schemes.16,23,27
Thumbur et al. 33	Efficient and secure certificateless aggregate signature-based authentication scheme for vehicular ad hoc networks.	The scheme comprises nine algorithms: Setup, Pseudonym-Gen, Partial-Private-Key-Gen, Set-Secret-Value, Vehicle-Key-Gen, Sign, Verify, Aggregate, and Aggregate-Verify. Compared to other CLAS schemes in VANETs that employ CDHP complexity assumption, the scheme has apparent advantages inefficiency.

CLAS: certificateless aggregate signature; VANET: vehicular ad hoc network; KGC: key generator center; CDHP: computational Diffie–Hellman problem.

Our contributions

Our main contributions are summarized as follows:

1. We propose a new CLAS scheme that aims to make the computation cost a top priority and provide a secure and more effective CLAS scheme for V2V and V2I communications in VANET.

2. Our scheme provides a significant cost efficiency in the individual and aggregate verification, particularly compared to the other CDHP-based CLAS schemes.^{19,25,27,29,32}

3. Our scheme realizes mutual authentication between vehicle and TRA to confirm that they are the corresponding legal entities.

4. Our scheme could provide pseudonymity, identity privacy-preserving, mutual authentication, message authentication, non-repudiation, traceability, unlinkability, and user location privacy. It also could withstand the Type-1 and Type-2 adversary attacks, replay attacks, MITM attacks, masquerade attacks, and impersonation attacks.

Organization

For a better understanding, the rest of this article is arranged as follows. In section “Preliminaries,” we provide preliminaries about the system model of CLAS, the concepts of bilinear maps, the complexity assumption we used, an outline of the CLAS scheme, security model, and other common security and privacy requirements in VANET. Then, the construction of our proposed scheme and its correctness is described in section “Our proposed CLAS scheme.” Next, section “Security proof and analysis” gives the security proof, analysis, and comparison toward other schemes, followed by the performance analysis in section “Performance analysis.” Finally, the conclusion is conveyed in section “Conclusion.”

Preliminaries

This section discusses the concept of bilinear maps, complexity assumptions, the outline of the CLAS scheme, security model, and other basic security and privacy requirements.

System model

As mentioned in section “Introduction,” in general, the topology of VANET is made up of three main components that are structured as the two-level architecture. In the CLAS scheme of VANET, we have an application server (AS) and TA (i.e. KGC and tracking authorities (TRA)) which make up the higher layer. Meanwhile, RSUs and OBUs cover the lower layer (see Figure 2). In the CLAS-VANET, AS is a trusted entity that serves as a traffic-related server for vehicles (traffic control and analysis center). It will collect traffic-related messages from the RSU and conduct additional traffic analysis. AS communicates with TA and RSU using a secure wired connection. In this scheme, RSU acts as the verifier of the signatures $({\sigma }_1,{\sigma }_2,\dots ,{\sigma }_n)$ on messages $(M_1,M_2,\dots ,M_n)$ sent by vehicles, and aggregate them into an aggregate signature $\sigma$ , then send it to the AS. The AS will collect and verify the aggregate signature $\sigma$ from RSUs, make a further analysis, and provide them back with some preferred services.

Figure 2.

Aggregate signature in VANET.

The bilinear maps

The bilinear map $\hat{e}$ can be obtained from the modified Weil pairing ³⁹ or Tate pairing ⁴⁰ on elliptic curves. Its security and complexity lie in the CDHP, which is difficult to solve. ⁴¹ Let $G_1$ be denoted as a cyclic additive group generated by $P$ , and $G_2$ is a cyclic multiplicative group with the same prime order $q$ . Let $\hat{e}:G_1\times G_1\to G_2$ be a bilinear map if it satisfies the following properties:

• Bilinear: For all $P,Q,R\in G_1$ , we have $\hat{e}(Q,P+R)=\hat{e}(P,Q+R)=\hat{e}(Q,P)·\hat{e}(Q,R)$ . For any $a,b\in Z_q^{*}$ , $\hat{e}(\mathrm{aQ},\mathrm{bP})=\hat{e}(\mathrm{bQ},\mathrm{aP})=\hat{e}(Q,P{)}^{\mathrm{ab}}$ .

• Computable: For any $P,Q\in G_1$ , there is an efficient algorithm to compute $\hat{e}(P,Q)$ .

• Non-degenerate: $\hat{e}(P,Q)\ne 1$ .

Complexity assumption

In CDHP, $G_1$ is a cyclic additive group generated by $P$ , with given $P,\mathrm{aP},\mathrm{bP},\mathrm{cP}\in G_1$ , and $a,b,c\in Z_q^{*}$ are unknown values. The CDHP is difficult to solve by adversary $\mathcal{A}$ , because there is no polynomial time algorithm that can discover $\mathrm{abcP}\in G_1$ .

Outline of CLAS scheme

Generally, a CLAS scheme includes eight following algorithms: Setup, Pseudonym-Gen, Partial-Private-Key-Gen, Vehicle-Key-Gen, Sign, Verify, Aggregate, and Aggregate-Verify.

Setup: TRA and KGC run this algorithm with a security parameter $l\in Z_q^{*}$ as input to produces master public key $P_{\mathrm{pub}}$ , master secret key $s$ , and public parameters $\mathrm{params}$ .

Pseudonym-Gen: TRA run this algorithm by inputs vehicles’ real identity $I{D}_i$ and outputs vehicles’ pseudo-identity $\mathrm{PI}{D}_i$ .

Partial-Private-Key-Gen: KGC inputs vehicle’s identity $\mathrm{PI}{D}_i$ and $\mathrm{params}$ to produces respective partial private key $\mathrm{ps}{k}_{I{D}_i}$ .

Vehicle-Key-Gen: Vehicle takes $\mathrm{params}$ and its $\mathrm{ps}{k}_{I{D}_i}$ to generates private key $\mathrm{vs}{k}_{I{D}_i}$ , and its public key $\mathrm{vp}{k}_{I{D}_i}$ .

Sign: Vehicle inputs $\mathrm{params}$ together with its $\mathrm{PI}{D}_i$ , $\mathrm{ps}{k}_{I{D}_i}$ , $\mathrm{vs}{k}_{I{D}_i}$ , and the message $M_i$ . It returns the signature ${\sigma }_i$ on the message $M_i$ .

Verify: RSU (V2I) or recipient vehicle (V2V) takes ${\sigma }_i$ , $\mathrm{PI}{D}_i$ , $\mathrm{vp}{k}_{I{D}_i}$ as the input. If ${\sigma }_i$ is valid, the receiver accepts it, otherwise rejects.

Aggregate: The aggregator inputs $n$ vehicle’s signatures $({\sigma }_1,{\sigma }_2,\dots ,{\sigma }_n)$ on $n$ distinct messages $(M_1,M_2,\dots ,M_n)$ . Then, the algorithm outputs the aggregate signature $\sigma$ on $(M_1,M_2,\dots ,M_n)$ .

Aggregate-Verify: The verifier inputs $n$ vehicles’ public keys $(\mathrm{vp}{k}_{I{D}_1}$ , $\mathrm{vp}{k}_{I{D}_2}$ , ⋯, $\mathrm{vp}{k}_{I{D}_n})$ , the vehicle’s identity $(\mathrm{PI}{D}_1,\mathrm{PI}{D}_2,\dots ,\mathrm{PI}{D}_n)$ , and the corresponding aggregate signature $\sigma$ on the message set $(M_1,M_2,\dots ,M_n)$ . Finally, if this signature is valid, the verifier accepts it, otherwise rejects.

Security model

Depending on the behavior of adversary $\mathcal{A}$ , we consider two types of adversaries, called Type-1 adversary $({\mathcal{A}}_1)$ and Type-2 adversary $({\mathcal{A}}_2)$ .

Type-1 adversary $({\mathcal{A}}_1)$

The Type-1 adversary ${\mathcal{A}}_1$ serves as an outsider who can compromise or replace a user’s public key with any value but cannot access KGC’s master secret key. It is also known as the public-key replacement attack.

Type-2 adversary $({\mathcal{A}}_2)$

The Type-2 adversary ${\mathcal{A}}_2$ takes on the role of the KGC. It can access the KGC’s master key but cannot replace the user’s public key. It is also known as the malicious KGC attack.

A CLAS scheme is said to be existentially unforgeable against adaptive chosen-message and identity attacks by considering the following two games, $\mathrm{Game}\mathrm{-}1$ and $\mathrm{Game}\mathrm{-}2$ , against $\mathcal{A}\in \{{\mathcal{A}}_1,{\mathcal{A}}_2\}$ . Both ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ can access the following five oracles:

• CreateUser: After receiving a $\mathrm{PI}{D}_i$ , this oracle returns $\mathrm{vp}{k}_{\mathrm{PI}{D}_i}$ to $\mathcal{A}$ .

• RevealPartialPrivateKey: After receiving a vehicle’s $I{D}_i$ , the corresponding $\mathrm{ps}{k}_{I{D}_i}$ is returned to $\mathcal{A}$ by this oracle.

• RevealPrivateKey: After receiving a vehicle’s $\mathrm{PI}{D}_i$ , the corresponding $\mathrm{vs}{k}_{\mathrm{PI}{D}_i}$ is returned to $\mathcal{A}$ by this oracle.

• RevealPseudonym: $\mathcal{A}$ makes a request for the pseudonym of the vehicle with $I{D}_i$ . The challenger $\mathcal{C}$ searches the list $L_K$ and responds with $\mathrm{PI}{D}_i$ if the entry exists, otherwise it returns ⊥.

• ReplaceKey: After receiving a new public key ${\mathrm{vpk}}_{\mathrm{PI}{D}_i}^{\prime }$ chosen by $\mathcal{A}$ and a $\mathrm{PI}{D}_i$ , this oracle updates vehicle’s $\mathrm{vp}{k}_{\mathrm{PI}{D}_i}$ with ${\mathrm{vpk}}_{\mathrm{PI}{D}_i}^{\prime }$ .

• Sign: After receiving $\mathrm{PI}{D}_i$ and $M_i\in \{(0,1{)}^{*}\}$ , a ${\sigma }_i$ of $M_i$ is returned to $\mathcal{A}$ by this oracle.

Game-1

The challenger $\mathcal{C}$ deals with ${\mathcal{A}}_1$ executes the following steps.

• Setup: $\mathcal{C}$ runs Setup algorithm, which takes $l$ to generate $s$ and $\mathrm{params}$ . The $\mathrm{params}$ is sent by $\mathcal{C}$ to ${\mathcal{A}}_1$ while keeps $s$ as secret to itself.

• Query: ${\mathcal{A}}_1$ is allowed to runs CreateUser, RevealPartialPrivateKey, RevealPrivateKey, and $\mathrm{Sign}$ oracles.

• Forgery: Finally, ${\mathcal{A}}_1$ outputs an aggregate signature ${\sigma }^{\prime }$ on the messages set $(M_1^{\prime }$ , $M_2^{\prime }$ , ⋯, $M_n^{\prime })$ corresponding to a targeted identities $({\mathrm{PID}}_1^{\prime }$ , ${\mathrm{PID}}_2^{\prime }$ , ⋯, ${\mathrm{PID}}_n^{\prime })$ with public keys $(\mathrm{vp}{k}_{{\mathrm{ID}}_1^{\prime }}$ , $\mathrm{vp}{k}_{{\mathrm{ID}}_2^{\prime }}$ , ⋯, $\mathrm{vp}{k}_{{\mathrm{ID}}_n^{\prime }})$ .

In this case, ${\mathcal{A}}_1$ wins Game-1 if:

• ${\sigma }^{\prime }$ is a valid aggregate signature on $(M_1^{\prime }$ , $M_2^{\prime }$ , ⋯, $M_n^{\prime })$ with identities $({\mathrm{PID}}_1^{\prime }$ , ${\mathrm{PID}}_2^{\prime }$ , ⋯, ${\mathrm{PID}}_n^{\prime })$ and public keys $(\mathrm{vp}{k}_{{\mathrm{ID}}_1^{\prime }}$ , $\mathrm{vp}{k}_{{\mathrm{ID}}_2^{\prime }}$ , ⋯, $\mathrm{vp}{k}_{{\mathrm{ID}}_n^{\prime }})$ .

• The ${\mathrm{PID}}_i^{\prime }$ has not queried partial private key $\mathrm{ps}{k}_{{\mathrm{ID}}_i^{\prime }}$ during RevealPartialPrivateKey queries.

• Sign oracle has never been queried with ${\mathrm{PID}}_i^{\prime }$ and $M_i^{\prime }$ .

Definition 1

If ${\mathcal{A}}_1$ cannot win Game-1 with non-negligible advantage in polynomial time, the CLAS scheme is secure against ${\mathcal{A}}_1$ .

Game-2

The challenger $\mathcal{C}$ deals with ${\mathcal{A}}_2$ executes the following steps.

• Setup: $\mathcal{C}$ runs $\mathrm{Setup}$ algorithm, which takes $l$ to generate $s$ and $\mathrm{params}$ . The both $s$ and $\mathrm{params}$ are sent by $\mathcal{C}$ to ${\mathcal{A}}_2$ .

• Query: ${\mathcal{A}}_2$ is allowed to runs CreateUser, RevealPrivateKey, ReplaceKey, and Sign oracles in this phase. The ${\mathcal{A}}_2$ is no longer needs RevealPartialPrivateKey since it has the access to $s$ .

• Forgery: Finally, ${\mathcal{A}}_2$ outputs an aggregate signature ${\sigma }^{\prime }$ on the message set $(M_1^{\prime }$ , $M_2^{\prime }$ , ⋯, $M_n^{\prime })$ corresponding to a targeted identities $({\mathrm{PID}}_1^{\prime }$ , ${\mathrm{PID}}_2^{\prime }$ , ⋯, ${\mathrm{PID}}_n^{\prime })$ with public keys $(\mathrm{vp}{k}_{{\mathrm{ID}}_1^{\prime }}$ , $\mathrm{vp}{k}_{{\mathrm{ID}}_2^{\prime }}$ , ⋯, $\mathrm{vp}{k}_{{\mathrm{ID}}_n^{\prime }})$ .

In this case, ${\mathcal{A}}_2$ wins Game-2 if:

• ${\sigma }^{\prime }$ is a valid aggregate signature on $(M_1^{\prime }$ , $M_2^{\prime }$ , ⋯, $M_n^{\prime })$ with identities $({\mathrm{PID}}_1^{\prime }$ , ${\mathrm{PID}}_2^{\prime }$ , ⋯, ${\mathrm{PID}}_n^{\prime })$ and public keys $(\mathrm{vp}{k}_{{\mathrm{ID}}_1^{\prime }}$ , $\mathrm{vp}{k}_{{\mathrm{ID}}_2^{\prime }}$ , ⋯, $\mathrm{vp}{k}_{{\mathrm{ID}}_n^{\prime }})$ .

• The ${\mathrm{PID}}_i^{\prime }$ has not queried private key $\mathrm{vs}{k}_{{\mathrm{ID}}_i^{\prime }}$ during RevealPrivateKey queries.

• Sign oracle has never been queried with ${\mathrm{PID}}_i^{\prime }$ and $M_i^{\prime }$ .

Definition 2

If ${\mathcal{A}}_2$ cannot win Game-2 with non-negligible advantage in polynomial time, the CLAS scheme is secure against ${\mathcal{A}}_2$ .

From Definition 1 and Definition 2 above, a CLAS scheme is claimed to be existentially unforgeable under an adaptive chosen message attack, if there exists no polynomial-time adversary ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ with a non-negligible advantage in $\mathrm{Game}\mathrm{-}1$ and $\mathrm{Game}\mathrm{-}2$ , respectively.

Other security and privacy requirements

As depicted in Figure 1, the V2V and V2I communication occur under an open wireless communication channel, so it is vulnerable to various attacks. To design a secure authentication mechanism, we define the security and privacy requirements that need to be met in VANET as follows.^3,4,11,12,42

Pseudonimity

TRA can create a unique pseudo-identity from the vehicle’s real identity to protect the user’s privacy.

Identity privacy-preserving

Since the pseudonym covers the message’s sender’s identity, it would be anonymous, and only TRA can reveal their real identity.

Mutual authentication

Two parties can authenticate each other simultaneously to be assured and certain doing business exclusively with legitimate entities.

Message authentication

The receiver must be capable of differentiating the original message from the bogus message.

Non-repudiation

Messages’ senders cannot deny the information they have sent.

Traceability

TRA must be able to reveal the real identities of the pseudo-identities $\mathrm{PI}{D}_i$ of the user in the case of a dispute.

Unlinkability

An adversary (vehicle or RSU) should not link two or more subsequent pseudonym messages of the same vehicle.

Replaying attack resistance

The networks could endure a passive data capture and subsequent retransmission to produce an unauthorized message by the adversaries.

MITM attack resistance

The networks could endure the eavesdropper to intercept a message and sometimes alter the intended message. Mutual authentication can prevent MITM attacks because both the sender and recipient verify each other before sending them.

Masquerade attack resistance

The networks could endure a fake identity that tries to gain unauthorized access to transmitted information through legitimate access identification.

Impersonation attack resistance

The networks could endure toward the attacker who tries to assume or impersonate the legitimate vehicles’ identity in VANET to generate the signature for any messages.

User location privacy

The networks could prevent other parties from learning the vehicle’s past, current, or next destination location.

Our proposed CLAS scheme

It is necessary to design an effective VANET authentication scheme in an environment where the communication channels are not protected. To enhance the security and improve message verification efficiency of V2V and V2I communication in VANET, we propose a CLS (Setup, Registration, Partial-Private-Key-Gen, Vehicle-Key-Gen, Pseudonym-Gen, Sign, Verify) scheme followed by an efficient CLAS (Aggregate, Aggregate-Verify) scheme. To comprehend the scheme’s procedure, notations throughout this article are presented in Table 2.

Table 2.

Notations of this article.

Notation	Definition
KGC	Key generator center
TRA	Trace authority
OBU	On-board unit
TPD	Tamper-proof device
RSU	Road-side unit
$G_1$	A cyclic additive group
$G_2$	A cyclic multiplicative group
$q$	Prime order of $G_1$ and $G_2$
$P$	Generator point of $G_1$
$\hat{e}$	A bilinear pairing
	$\hat{e}:G_1\times G_1\to G_2$
$H(·),h(·)$	MapToPoint hash function, $H(·):\{0,1{\}}^{*}\to G_1$ and one-way hash function, $h(·):{\{0,1\}}^{\ast }\to Z_q^{\ast }$
$\alpha ,P_{\mathrm{pub}}$	KGC’s master private and public keys
$\beta ,T_{\mathrm{pub}}$	TRA’s private and public keys
$y_i,P_{\mathrm{rs}{u}_i}$	RSU’s private and public keys
$I{D}_i$	Vehicle’s identity
$\mathrm{ps}{k}_{I{D}_i}$	Vehicle’s partial private key
$\mathrm{PI}{D}_i$	Vehicle’s pseudo-identity
$T_i,t_i$	A current timestamp
$\mathrm{vs}{k}_{I{D}_i},\mathrm{vp}{k}_{I{D}_i}$	Vehicle’s private and public keys

Construction

Our proposed nine-phase CLAS scheme is described as follows.

Setup

This phase aims to generate the system’s public parameters and the secret parameters of TRA and KGC. They are used for message encryption and signature generation. These parameters are used to generate a pseudo-identity of the device in the future and perform proper verification on the message’s signature. The KGC first selects a security parameter $l\in N$ and then generates a cyclic addition group $G_1$ , a cyclic multiplication group $G_2$ , a generator point $P$ that belongs to $G_1$ , and a bilinear pairing function $\hat{e}:G_1\times G_1\to G_2$ . Both $G_1$ and $G_2$ have the same prime order of $q$ . KGC then selects a secret value $\alpha \in Z_q^{*}$ as the master key and calculates $P_{\mathrm{pub}}=\alpha P$ as the public key. KGC then chooses six secure one-way hash functions $h_1,h_2,h_3,h_4,h_5,h_6:\{0,1{\}}^{*}\to Z_q^{*}$ .

Meanwhile, TRA selects a secret value $\beta \in Z_q^{*}$ to calculates its public key $T_{\mathrm{pub}}=\beta P$ . Each RSU in VANET needs to select a private key $y_i\in Z_q^{*}$ for calculating their public key $P_{\mathrm{rs}{u}_i}=y_{i}P$ , and sends it to KGC. After receiving $P_{\mathrm{rs}{u}_i}$ , KGC sends the public parameters $\mathrm{params}=\{q,G_1,G_2,P,\hat{e},P_{\mathrm{pub}},h_1,h_2,h_3,h_4,h_5,h_6,P_{\mathrm{rs}{u}_i}\}$ to every vehicle in the network, which will be preloaded into their TPD. The process is shown in Figure 3.

Figure 3.

Setup phase.

Registration

In this phase, every vehicle equipped with the OBU device needs to register itself to the TRA. So, in the case of dispute, the TRA can track the vehicle’s pseudo-identity and determine which vehicle owns that pseudo-identity. First, TRA chooses a hash function $H(·):{\{0,1\}}^{\ast }\to G_1$ . When a new vehicle needs to register, the driver must personally go to the TRA in his or her area to provide personal identity information (offline mode). Then the TRA picks the vehicle’s identity $I{D}_i$ and a random number $r_i\in Z_q^{*}$ to relate it with their new actual identity $Q_{I{D}_i}=H(I{D}_i,r_i)$ that will be used in all further communications. The TRA sends $\{Q_{I{D}_i},r_i\}$ to the vehicle under a secure communication channel. After the vehicle receives this information, it selects a random value $\mathrm{nonce}$ and calculates the password $\mathrm{pas}{s}_{I{D}_i}=h_1(r_i,\mathrm{nonce})$ . Finally, $\mathrm{pas}{s}_{I{D}_i}$ is transmitted to the TRA under the secure communication channel. The TRA stores $\mathrm{pas}{s}_{I{D}_i}$ to complete the registration of the vehicle. The process of this phase is shown in Figure 4.

Figure 4.

Registration—Partial-Private-Key-Gen phases.

Partial-Private-Key-Gen

The KGC performs this phase to generate a partial private key $\mathrm{ps}{k}_{I{D}_i}=\alpha Q_{I{D}_i}$ of the vehicle according to the vehicle’s identity $Q_{I{D}_i}$ and KGC’s secret parameters $\alpha$ . When a vehicle needs to send messages or requests in the future, it can use $\mathrm{ps}{k}_{I{D}_i}$ to calculate a legal signature. KGC transmits $\mathrm{ps}{k}_{I{D}_i}$ to the vehicle via a secure communication channel. The vehicle can verify whether $Q_{I{D}_i}$ and $\mathrm{ps}{k}_{I{D}_i}$ are generated by legitimate TRA and KGC through $\hat{e}(\mathrm{ps}{k}_{I{D}_i},P)=\hat{e}(Q_{I{D}_i},P_{\mathrm{pub}})$ . The process of this phase is shown in Figure 4.

Vehicle-Key-Gen

When the vehicle needs to apply for a pseudo-identity to the TRA, first, it has to generate a private and public keys on its own. The vehicle selects a random number $x_i\in Z_q^{*}$ as its private key $\mathrm{vs}{k}_{I{D}_i}$ , therefore, $\mathrm{vs}{k}_{I{D}_i}=x_i$ . Then it uses the public parameter $P$ to calculate the public key $\mathrm{vp}{k}_{I{D}_i}=x_{i}P$ . Subsequently, vehicle needs to generate a one-time password $(\mathrm{OTP})$ ⁴³ for a mutual authentication with TRA. The vehicle first joins the current timestamp $T_i$ with $\mathrm{pas}{s}_{I{D}_i}$ and $Q_{I{D}_i}$ to calculate the one time password $\mathrm{OTP}=h_2(\mathrm{pas}{s}_{I{D}_i}\oplus Q_{I{D}_i}\oplus T_i)$ . This $\mathrm{OTP}$ can only be used once, and it must be regenerated every time when applying for pseudo-identities later. Afterward, vehicle sends $(m,\mathrm{OTP},I{D}_i,T_i,\mathrm{vp}{k}_{I{D}_i})$ to the TRA by encrypting it with TRA’s public key $T_{\mathrm{pub}}$ , with $m$ refers to the number of pseudo-identities stored in the vehicle’s OBU device. The operation is expressed in equation (1)

$$\begin{array}{c}〈E_{T_{\mathrm{pub}}}(m,\mathrm{OTP},I{D}_i,T_i,\mathrm{vp}{k}_{I{D}_i})〉\hfill \end{array}$$

(1)

After receiving (1), TRA then decrypts the message with its private key $\beta$ and verifies whether $T_i$ is within a reasonable time interval or not. If yes, TRA computes $Q_{I{D}_i}°=H(I{D}_i,r_i)$ and $\mathrm{OT}P°=h_2(\mathrm{pas}{s}_{I{D}_i}\oplus Q_{I{D}_i}°\oplus T_i)$ . If $\mathrm{OT}P°=\mathrm{OTP}$ , then TRA can authenticates the vehicle. The whole process is shown in Figure 5.

Figure 5.

Vehicle-Key-Gen—Pseudonym-Gen phases.

Pseudonym-Gen

After the mutual authentication process between TRA and vehicle is successful, the TRA will generate a pseudo-identity $\mathrm{PI}{D}_i$ for the vehicle. First, the TRA calculates $C_i=h_3(\beta ,I{D}_i,T_i°)$ to creates pseudo-identity $\mathrm{PI}{D}_i=Q_{I{D}_i}{C}_i$ . Next, TRA calculates $D_i=h_4(\mathrm{PI}{D}_i)$ and $K_i=C_i{D}_i$ . Vehicles need to preload with multiple pseudo-identities, and a single of them cannot be reused. Each time a message sends to another vehicle, different pseudo-identities are used. When the vehicles are at intersections or parking lots where many vehicles are gathered, this method will make a legitimate vehicle difficult to track by malicious attackers. The TRA will measure how many pseudo-identities to generate based on the number of current pseudo-identities stored in the OBU device. Each application will generate multiple pseudo-identities $(\mathrm{PI}{D}_{i,1},\mathrm{PI}{D}_{i,2},\dots ,\mathrm{PI}{D}_{i,n})$ . Then, TRA calculates $j=h_5(Q_{I{D}_i},T_i°)$ , and with vehicle’s public key $\mathrm{vp}{k}_{I{D}_i}$ to encrypt the message

$$\begin{array}{c}〈E_{\mathrm{vp}{k}_{I{D}_i}}((\mathrm{PI}{D}_{i,1},K_{i,1}),(\mathrm{PI}{D}_{i,2},K_{i,2}),\cdots ,\hfill \\ (\mathrm{PI}{D}_{i,n},K_{i,n}),j,T_i°)〉\hfill \end{array}$$

(2)

Message (2) is transmitted to the vehicle via RSU. After vehicle receives the message, it decrypts the message using its private key $\mathrm{vs}{k}_{I{D}_i}$

$$\begin{array}{c}〈D_{\mathrm{vs}{k}_{I{D}_i}}(E_{\mathrm{vp}{k}_{I{D}_i}}((\mathrm{PI}{D}_{i,1},K_{i,1}),(\mathrm{PI}{D}_{i,2},K_{i,2}),\hfill \\ \cdots ,(\mathrm{PI}{D}_{i,n},K_{i,n}),j,T_i°))〉\hfill \end{array}$$

(3)

and verifies whether $T_i°$ is in reasonable time interval. If yes, vehicle calculates $j°=h_5(Q_{I{D}_i},T_i°)$ and verifies whether $j°=j$ . If the verification is successful, both vehicle and TRA are mutually authenticated, and the vehicle stores the pseudo-identities and $K$ . Because the OBU device must store a sufficient number of pseudo-identities, the vehicle needs to re-apply to the TRA at an appropriate time to avoid having no pseudo-identities. The whole process of this phase is shown in Figure 5.

Sign

At this phase, when a vehicle wants to send a message or request, it needs to produce a valid certificateless signature. The receiver can verify the signature to determine whether to receive the message or not. The vehicle selects a random number $u_i\in Z_q^{*}$ and calculates $U_i=u_{i}P\in G_1$ . Then OBU computes

$$h_i=h_6(M_i,\mathrm{PI}{D}_i,\mathrm{vp}{k}_{I{D}_i},U_i,t_i)$$

(4)

$$S_i=\mathrm{ps}{k}_{I{D}_i}K+\mathrm{vs}{k}_{I{D}_i}{P}_{\mathrm{pub}}+h_i{u}_i{P}_{\mathrm{rs}{u}_i}$$

(5)

to generate a certificateless signature ${\sigma }_i=(U_i,S_i)$ on message $M_i$ . Finally, vehicle broadcasts final message $(M_i,\mathrm{PI}{D}_i,\mathrm{vp}{k}_{I{D}_i},{\sigma }_i,t_i)$ , with $t_i$ is the timestamp. The process of this phase is shown in Figure 6.

Figure 6.

Sign—Verify phase.

Verify

At this phase, RSU acts as the verifier. It verifies whether a legitimate vehicle generated the signature and whether it has been tampered with during the transmission or not. When it senses the message transmitted by vehicles, the $t_i$ is first verified to check whether the message is signed within a reasonable time interval. If it is not, it will not be accepted, and the message will be discarded. If yes, then computes $h_i=h_6(M_i,\mathrm{PI}{D}_i,\mathrm{vp}{k}_{I{D}_i},U_i,t_i)$ and $D_i=h_4(\mathrm{PI}{D}_i)$ . Finally, RSU verifies whether equation (6) holds or not

$$\hat{e}(S,P)=\hat{e}(\mathrm{PI}{D}_i{D}_i+\mathrm{vp}{k}_{I{D}_i},P_{\mathrm{pub}})·\hat{e}(h_i{U}_i,P_{\mathrm{rs}{u}_i})$$

(6)

If equation (6) holds, the certificateless signature is received. If the check fails, the message may have been tampered with and not accepted. The process of this phase is shown in Figure 6. To speed up the verification of frequently visited RSU, the proposed scheme pre-stores the parameter $P_{\mathrm{rs}{u}_i}$ in OBU. However, if the memory of OBU is limited, some parameters of visiting RSU that are not frequently visited are not stored. In this case, if vehicles visit this RSU, the vehicles can send a request to KGC to obtain the parameters of this RSU.

Aggregate

RSU acts as an aggregator. On receiving $n$ message-signature pairs $(M_1~M_n,\sigma =(U_1~U_n,S_1~S_n),t_1~t_n)$ from several vehicles with pseudo-identities $(\mathrm{PI}{D}_1~\mathrm{PI}{D}_n)$ and corresponding public keys $(\mathrm{vp}{k}_{I{D}_1}~\mathrm{vp}{k}_{I{D}_n})$ , RSU computes (7) and returns $\sigma =(U_1~U_n,S)$ as an aggregate signature. Finally, RSU sends $(M_1~M_n,\mathrm{PI}{D}_1~\mathrm{PI}{D}_n,\mathrm{vp}{k}_{I{D}_1}~\mathrm{vp}{k}_{I{D}_n},\sigma ,t_1~t_n)$ to AS. This process is shown in Figure 7

$$S=\sum _{i=1}^n{S}_i$$

(7)

Figure 7.

Aggregate—Aggregate-Verify phases.

Aggregate-verify

This phase is used to verify the legality of the aggregated signature by checking whether the legal device generates the signature and has not been tampered with during transmission. On receiving $\sigma =(U_1~U_n,S)$ from RSU, as the aggregate verifier, AS computes $h_i$ in equation (4) and $D_i$ for $i=1,2,\dots ,n$ . Finally, AS verifies whether

$$\begin{array}{c}\hat{e}(S,P)=\hat{e}(\sum _{i=1}^n\mathrm{PI}{D}_i{D}_i+\mathrm{vp}{k}_{I{D}_i},P_{\mathrm{pub}})\hfill \\ ·\hat{e}(\sum _{i=1}^n{h}_i{U}_i,P_{\mathrm{rs}{u}_i})\hfill \end{array}$$

(8)

If the verification fails, the message may have been tampered with and not accepted. If the verification hold, the CLAS is accepted. The process of this phase is shown in Figure 7.

When a vehicle’s density is high, such as at the intersection, the CLAS scheme enables many vehicle broadcast messages to verify and receive after aggregated. Thus, compared to verifying the signatures one by one, CLAS will increase verification efficiency.

Correctness

Our proposed CLAS scheme is correct if and only if the Verify and Aggregate-Verify phases can satisfy equations (6) and (8), respectively. The correctness of both phases is elaborated as follows:

Verify

$$\begin{array}{c}\hat{e}(S,P)=\hfill \\ =\hat{e}(\mathrm{ps}{k}_{I{D}_i}K+\mathrm{vs}{k}_{I{D}_i}{P}_{\mathrm{pub}}+h_i{u}_i{P}_{\mathrm{rs}{u}_i},P)\hfill \\ =\hat{e}(\mathrm{ps}{k}_{I{D}_i}K,P)·\hat{e}(\mathrm{vs}{k}_{I{D}_i}{P}_{\mathrm{pub}},P)·\hat{e}(h_i{u}_i{P}_{\mathrm{rs}{u}_i},P)\hfill \\ =\hat{e}(\alpha Q_{I{D}_i}{C}_i{D}_i,P)·\hat{e}(x_i\alpha P,P)·\hat{e}(h_i{u}_i{P}_{\mathrm{rs}{u}_i},P)\hfill \\ =\hat{e}(\mathrm{PI}{D}_i{D}_i,P_{\mathrm{pub}})·\hat{e}(\mathrm{vp}{k}_{I{D}_i},P_{\mathrm{pub}})·\hat{e}(h_i{U}_i,P_{\mathrm{rs}{u}_i})\hfill \\ =\hat{e}(\mathrm{PI}{D}_i{D}_i+\mathrm{vp}{k}_{I{D}_i},P_{\mathrm{pub}})·\hat{e}(h_i{U}_i,P_{\mathrm{rs}{u}_i})\hfill \end{array}$$

Aggregate-Verify

$$\begin{array}{c}\hat{e}(S,P)=\hfill \\ =\hat{e}(\sum _{i=1}^n\mathrm{ps}{k}_{I{D}_i}K+\mathrm{vs}{k}_{I{D}_i}{P}_{\mathrm{pub}}+h_i{u}_i{P}_{\mathrm{rs}{u}_i},P)\hfill \\ =\hat{e}(\sum _{i=1}^n\mathrm{ps}{k}_{I{D}_i}K,P)·\hat{e}(\sum _{i=1}^n\mathrm{vs}{k}_{I{D}_i}{P}_{\mathrm{pub}},P)\hfill \\ ·\hat{e}(\sum _{i=1}{h}_i{u}_i{P}_{\mathrm{rs}{u}_i},P)\hfill \\ =\hat{e}(\sum _{i=1}^n\alpha Q_{I{D}_i}{C}_i{D}_i,P)·\hat{e}(\sum _{i=1}^n{x}_i\alpha P,P)\hfill \\ ·\hat{e}(\sum _{i=1}^n{h}_i{u}_i{y}_{i}P,P)\hfill \\ =\hat{e}(\sum _{i=1}^n\mathrm{PI}{D}_i{D}_i,P_{\mathrm{pub}})·\hat{e}(\sum _{i=1}^n\mathrm{vp}{k}_{I{D}_i},P_{\mathrm{pub}})\hfill \\ ·\hat{e}(\sum _{i=1}^n{h}_i{U}_i,P_{\mathrm{rs}{u}_i})\hfill \\ =\hat{e}(\sum _{i=1}^n\mathrm{PI}{D}_i{D}_i+\mathrm{vp}{k}_{I{D}_i},P_{\mathrm{pub}})\hfill \\ ·\hat{e}(\sum _{i=1}^n{h}_i{U}_i,P_{\mathrm{rs}{u}_i})\hfill \end{array}$$

Security proof and analysis

In this section, we give the security proof of the proposed scheme against two types of adversaries ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ , as well as a challenger $\mathcal{C}$ . First, the security models of CLAS are defined by simulating the behavior of potential ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ . Then, we analyze the other basic security and privacy requirements described in section “Preliminaries.” Finally, we give a security and privacy comparison between our proposed scheme and the others in Table 3.

Table 3.

Comparison of the security and privacy.

Scheme	${\mathcal{A}}_1$	${\mathcal{A}}_2$	M. auth.	Ano.	Unlink.	Trace.	RAR	IAR
Malhi and Batra 18	V	X	X	X	X	V	X	X
Horng et al. 19	X	X	X	V	V	V	X	X
Kumar and Sharma 23	V	X	V	V	V	V	V	V
Kamil and Ogundoyin26	X	X	V	V	V	V	V	V
Zhong et al. 25	V	X	V	V	V	V	V	V
Kumar et al. 27	X	X	V	V	X	V	X	V
Ours	V	V	V	V	V	V	V	V

V: The scheme is secure or supports feature; X: The scheme is insecure or does not support feature; M. Auth: Message authentication; Ano: Anonymity; Unlink: Unlinkability; Trace: Traceability; RAR: Resistance to replaying attack; IAR: Impersonation attack resistance.

Security proof

As mentioned in Definition 1 and Definition 2, the CLAS scheme is secure against ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ if it cannot win Game-1 and Game-2 with non-negligible advantage in polynomial time, respectively.

Theorem 1

Our proposed CLAS scheme is existentially unforgeable against ${\mathcal{A}}_1$ in the ROM under the intractability of the CDH problem. If ${\mathcal{A}}_1$ can forge a valid CLS during time $t$ with a non-negligible probability $ϵ$ after making $q_H$ and $q_{h_i}$ queries, with $i=1,2,\dots ,6$ , CreateUser queries $q_c$ , RevealPartiaPrivatelKey queries $q_{\mathrm{ps}{k}_{I{D}_i}}$ , RevealPrivateKey queries $q_{\mathrm{vs}{k}_{I{D}_i}}$ , Sign queries $q_s$ , then there is exists $\mathcal{C}$ who can solve CDH problem $\mathrm{abcP}\in G_1$ with probability $\frac{ϵ}{q_{\mathrm{ps}{k}_{I{D}_i}}e}$ within a time $t^{\prime }=t+(q_c+q_H+q_{h_i}+q_{\mathrm{ps}{k}_{I{D}_i}}+q_{\mathrm{vs}{k}_{I{D}_i}}+q_s)t_m$ , with $e$ is the base of the natural logarithm, and $t_m$ is the time for scalar multiplication. ²⁹

Proof

We can prove the unforgeability of our CLAS scheme against ${\mathcal{A}}_1$ in Game-1 that also involves $\mathcal{C}$ . Let $X=\mathrm{aP}$ , $Y=\mathrm{bP}$ , and $P_{\mathrm{rs}{u}_i}=\mathrm{cP}$ where $P$ is the generator of $G_1$ with prime order $q$ and $a,b,c\in Z_q^{*}$ are unknown to ${\mathcal{A}}_1$ .

1. Setup: $\mathcal{C}$ randomly selects ${\mathrm{PID}}_i^{\prime }$ as the challenged identity and submits public parameters $\mathrm{params}=\{q,G_1,G_2,P,\hat{e},P_{\mathrm{pub}},h(·),P_{\mathrm{rs}{u}_i}\}$ to ${\mathcal{A}}_1$ . Following by sets $P_{\mathrm{pub}}=X=\mathrm{aP}$ . The hash functions $H(·)$ and $h_i(·)$ , with $i=1,2,\dots ,6$ , are considered random oracles. $\mathcal{C}$ also manages eight lists $L_H$ , $L_{h_1}$ , $L_{h_2}$ , $L_{h_3}$ , $L_{h_4}$ , $L_{h_5}$ , $L_{h_6}$ , and $L_K$ , as follows.

2. CreateUser queries: Suppose ${\mathcal{A}}_1$ makes a query on $\mathrm{PI}{D}_i$ , with $i\in [1,q_c]$ . If list $L_K$ includes $(\mathrm{PI}{D}_i,\mathrm{ps}{k}_{I{D}_i},\mathrm{vs}{k}_{I{D}_i},\mathrm{vp}{k}_{I{D}_i})$ , $\mathcal{C}$ will check whether $\mathrm{vp}{k}_{I{D}_i}=\perp$ . If true, $\mathcal{C}$ picks a random value $v_i\in Z_q^{*}$ as $\mathrm{vs}{k}_{I{D}_i}$ and computes $\mathrm{vp}{k}_{I{D}_i}=v_{i}P$ . Then, $\mathcal{C}$ sends $\mathrm{vp}{k}_{I{D}_i}$ to ${\mathcal{A}}_1$ , and updates $(\mathrm{vp}{k}_{I{D}_i},\mathrm{vs}{k}_{I{D}_i})$ into $L_K$ . Otherwise, if $\mathrm{vp}{k}_{I{D}_i}\ne \perp$ , $\mathcal{C}$ directly sends $\mathrm{vp}{k}_{I{D}_i}$ to ${\mathcal{A}}_1$ . In another case, if $L_K$ does not include $(\mathrm{PI}{D}_i,\mathrm{ps}{k}_{I{D}_i},\mathrm{vs}{k}_{I{D}_i},\mathrm{vp}{k}_{I{D}_i})$ , $\mathcal{C}$ sets $\mathrm{vp}{k}_{I{D}_i}=\perp$ , picks $v_i\in Z_q^{*}$ as $\mathrm{vs}{k}_{I{D}_i}$ , and computes $\mathrm{vp}{k}_{I{D}_i}=v_{i}P$ . Then, $\mathcal{C}$ sends $\mathrm{vp}{k}_{I{D}_i}$ to ${\mathcal{A}}_1$ , and includes $(\mathrm{PI}{D}_i,\mathrm{ps}{k}_{I{D}_i},\mathrm{vs}{k}_{I{D}_i},\mathrm{vp}{k}_{I{D}_i})$ into $L_K$ .

3. RevealPartialPrivateKey queries: When ${\mathcal{A}}_1$ makes a RevealPartialPrivateKey query on $\mathrm{PI}{D}_i$ , with $i\in [1,q_{\mathrm{psk}}]$ , $\mathcal{C}$ computes $Q_{I{D}_i}=H(I{D}_i,r_i)$ and examines whether the tuple $(I{D}_i,r_i,Q_{I{D}_i})$ is already in the list $L_H$ or not. If yes, $\mathcal{C}$ computes $\mathrm{ps}{k}_{I{D}_i}=\alpha Q_{I{D}_i}$ , then output the value to ${\mathcal{A}}_1$ . Otherwise, $\mathcal{C}$ outputs failure and halts because it is unable to coherently answer the query.

4. RevealPseudonym queries: The corresponding tuple $(\mathrm{PI}{D}_i,\mathrm{ps}{k}_{I{D}_i},\mathrm{vs}{k}_{I{D}_i},\mathrm{vp}{k}_{I{D}_i})$ is recovered from $L_K$ . If $L_K$ contains $(\mathrm{PI}{D}_i,\mathrm{ps}{k}_{I{D}_i},\mathrm{vs}{k}_{I{D}_i},\mathrm{vp}{k}_{I{D}_i})$ , $\mathcal{C}$ checks if $\mathrm{PI}{D}_i=\perp$ or not. If $\mathrm{PI}{D}_i\ne \perp$ , $\mathcal{C}$ returns $\mathrm{PI}{D}_i$ to ${\mathcal{A}}_1$ . Otherwise, $\mathcal{C}$ randomly chooses $k_i\in Z_q^{*}$ and computes $\mathrm{PI}{D}_i=k_i{c}_i$ , where $c_i$ corresponds to $L_{h_3}=(\beta ,I{D}_i,T_i°,C_i)$ . $\mathcal{C}$ returns $\mathrm{PI}{D}_i$ to ${\mathcal{A}}_1$ and adds $(\mathrm{PI}{D}_i,\mathrm{ps}{k}_{I{D}_i},\mathrm{vs}{k}_{I{D}_i},\mathrm{vp}{k}_{I{D}_i})$ to $L_K$ . If $L_K$ does not contains $(\mathrm{PI}{D}_i,\mathrm{ps}{k}_{I{D}_i},\mathrm{vs}{k}_{I{D}_i},\mathrm{vp}{k}_{I{D}_i})$ , then $\mathcal{C}$ sets $\mathrm{PI}{D}_i=\perp$ , picks $k_i\in Z_q^{*}$ , and computes $\mathrm{PI}{D}_i=k_i{c}_i$ from corresponding $L_{h_3}=(\beta ,I{D}_i,T_i°,C_i)$ . $\mathcal{C}$ answers $\mathrm{PI}{D}_i$ to ${\mathcal{A}}_1$ and adds to $L_K$ . $(\mathrm{PI}{D}_i,\mathrm{ps}{k}_{I{D}_i},\mathrm{vs}{k}_{I{D}_i},\mathrm{vp}{k}_{I{D}_i})$ .

5. RevealPrivateKey queries: When ${\mathcal{A}}_1$ makes a RevealPrivateKey query on $\mathrm{PI}{D}_i$ , with $i\in [1,q_{\mathrm{vsk}}]$ , $\mathcal{C}$ checks whether the tuple $(\mathrm{PI}{D}_i,\mathrm{ps}{k}_{I{D}_i},\mathrm{vs}{k}_{I{D}_i},\mathrm{vp}{k}_{I{D}_i})$ is included in list $L_K$ or not. If yes, then $\mathcal{C}$ checks whether $\mathrm{vp}{k}_{I{D}_i}=\perp$ . If true, $\mathcal{C}$ makes a CreateUser query, picks a random value $v_i\in Z_q^{*}$ as $\mathrm{vs}{k}_{I{D}_i}$ , and computes $\mathrm{vp}{k}_{I{D}_i}=v_{i}P$ . Then, $\mathcal{C}$ sends $\mathrm{vp}{k}_{I{D}_i}$ to ${\mathcal{A}}_1$ , and updates $(\mathrm{vp}{k}_{I{D}_i},\mathrm{vs}{k}_{I{D}_i})$ into $L_K$ . Otherwise, if $\mathrm{vp}{k}_{I{D}_i}\ne \perp$ , $\mathcal{C}$ directly sends $\mathrm{vp}{k}_{I{D}_i}$ to ${\mathcal{A}}_1$ . In another case, if $L_K$ does not include $(\mathrm{PI}{D}_i,\mathrm{ps}{k}_{I{D}_i},\mathrm{vs}{k}_{I{D}_i},\mathrm{vp}{k}_{I{D}_i})$ , $\mathcal{C}$ makes a CreateUser query, sends $\mathrm{vs}{k}_{I{D}_i}$ to ${\mathcal{A}}_1$ , and includes $(\mathrm{PI}{D}_i,\mathrm{ps}{k}_{I{D}_i},\mathrm{vs}{k}_{I{D}_i},\mathrm{vp}{k}_{I{D}_i})$ into $L_K$ .

6. ReplaceKey queries: When ${\mathcal{A}}_1$ submits query on $\mathrm{PI}{D}_i$ , $\mathcal{C}$ checks if list $L_K$ includes $(\mathrm{PI}{D}_i,\mathrm{ps}{k}_{I{D}_i},\mathrm{vs}{k}_{I{D}_i},\mathrm{vp}{k}_{I{D}_i})$ , sets $\mathrm{vs}{k}_{I{D}_i}=\perp$ , and replaces $\mathrm{vp}{k}_{I{D}_i}$ to ${\mathrm{vpk}}_{I{D}_i}^{\prime }$ .

7. $\mathit{H}$ query: When ${\mathcal{A}}_1$ queries the oracle of $H$ , $\mathcal{C}$ searches $L_H$ for the tuple $(I{D}_i,r_i,Q_{I{D}_i})$ . If it can be found, $\mathcal{C}$ submits $Q_{I{D}_i}$ to ${\mathcal{A}}_1$ ; otherwise, it randomly picks $Q_{I{D}_i}\in Z_q^{*}$ , adds $(I{D}_i,r_i,Q_{I{D}_i})$ to $L_H$ , and eventually, submits $Q_{I{D}_i}$ to ${\mathcal{A}}_1$ .

8. ${\mathit{h}}_1$ query: When ${\mathcal{A}}_1$ queries the oracle of $h_1$ , $\mathcal{C}$ searches $L_{h_1}$ for the tuple $(r_i,\mathrm{nonce},\mathrm{pas}{s}_{I{D}_i})$ . If it can be found, $\mathcal{C}$ submits $\mathrm{pas}{s}_{I{D}_i}$ to ${\mathcal{A}}_1$ ; otherwise, it randomly picks $\mathrm{pas}{s}_{I{D}_i}\in Z_q^{*}$ , adds $(r_i,\mathrm{nonce},\mathrm{pas}{s}_{I{D}_i})$ to $L_{h_1}$ , and eventually, submits $\mathrm{pas}{s}_{I{D}_i}$ to ${\mathcal{A}}_1$ .

9. ${\mathit{h}}_2$ query: When ${\mathcal{A}}_1$ queries the oracle of $h_2$ , $\mathcal{C}$ searches $L_{h_2}$ for the tuple $(\mathrm{pas}{s}_{I{D}_i},Q_{I{D}_i},T_i,\mathrm{OTP})$ . If it can be found, $\mathcal{C}$ submits $\mathrm{OTP}$ to ${\mathcal{A}}_1$ ; otherwise, it randomly picks $\mathrm{OTP}\in Z_q^{*}$ , adds $(\mathrm{pas}{s}_{I{D}_i},Q_{I{D}_i},T_i,\mathrm{OTP})$ to $L_{h_2}$ , and eventually, submits $\mathrm{OTP}$ to ${\mathcal{A}}_1$ .

10. ${\mathit{h}}_3$ query: When ${\mathcal{A}}_1$ queries the oracle of $h_3$ , $\mathcal{C}$ searches $L_{h_3}$ for the tuple $(\beta ,I{D}_i,T_i°,C_i)$ . If it can be found, $\mathcal{C}$ submits $C_i$ to ${\mathcal{A}}_1$ ; otherwise, it randomly picks $C_i\in Z_q^{*}$ , adds $(\beta ,I{D}_i,T_i°,C_i)$ to $L_{h_3}$ , and eventually, submits $C_i$ to ${\mathcal{A}}_1$ .

11. ${\mathit{h}}_4$ query: When ${\mathcal{A}}_1$ queries the oracle of $h_4$ , $\mathcal{C}$ searches $L_{h_4}$ for the tuple $(\mathrm{PI}{D}_i,D_i,{\mu }_i)$ . If it can be found, $\mathcal{C}$ submits $D_i$ to ${\mathcal{A}}_1$ ; otherwise, if $\mathrm{PI}{D}_i={\mathrm{PID}}_i^{\prime }$ , $\mathcal{C}$ picks a random ${\mu }_i\in Z_q^{*}$ , calculates $D_i={\mu }_{i}Y\in G_1$ , inserts it in $L_{h_4}$ , and returns in to ${\mathcal{A}}_1$ . If $\mathrm{PI}{D}_i\ne {\mathrm{PID}}_i^{\prime }$ , $\mathcal{C}$ picks a random ${\mu }_i\in Z_q^{*}$ , calculates $D_i={\mu }_{i}P\in G_1$ , inserts it in $L_{h_4}$ , and returns in to ${\mathcal{A}}_1$ .

12. ${\mathit{h}}_5$ query: When ${\mathcal{A}}_1$ queries the oracle of $h_5$ , $\mathcal{C}$ searches $L_{h_5}$ for the tuple $(Q_{I{D}_i},T_i°,j)$ . If it can be found, $\mathcal{C}$ submits $j$ to ${\mathcal{A}}_1$ ; otherwise, it randomly picks $j\in Z_q^{*}$ , adds $(Q_{I{D}_i},T_i°,j)$ to $L_{h_5}$ , and eventually, submits $j$ to ${\mathcal{A}}_1$ .

13. ${\mathit{h}}_6$ query: When ${\mathcal{A}}_1$ queries the oracle of $h_6$ , $\mathcal{C}$ searches $L_{h_6}$ for the tuple $(M_i,\mathrm{PI}{D}_i,\mathrm{vp}{k}_{I{D}_i},U_i,t_i,h_i)$ . If it can be found, $\mathcal{C}$ submits $h_i$ to ${\mathcal{A}}_1$ ; otherwise, it randomly picks $h_i\in Z_q^{*}$ , adds $(M_i,\mathrm{PI}{D}_i,\mathrm{vp}{k}_{I{D}_i},U_i,t_i,h_i)$ to $L_{h_6}$ , and eventually, submits $h_i$ to ${\mathcal{A}}_1$ .

14. Sign: When ${\mathcal{A}}_1$ makes a Sign query on $(\mathrm{PI}{D}_i,M_i)$ , $\mathcal{C}$ examines all eight lists $L_H$ , $L_{h_1}$ , $L_{h_2}$ , $L_{h_3}$ , $L_{h_4}$ , $L_{h_5}$ , $L_{h_6}$ , $L_K$ . If the tuple $(\mathrm{PI}{D}_i,\mathrm{ps}{k}_{I{D}_i},\mathrm{vs}{k}_{I{D}_i},\mathrm{vp}{k}_{I{D}_i})$ is not present in $L_K$ , then $\mathcal{C}$ sets $\mathrm{vp}{k}_{I{D}_i}=\perp$ , picks $v_i\in Z_q^{*}$ as $\mathrm{vs}{k}_{I{D}_i}$ , and computes $\mathrm{vp}{k}_{I{D}_i}=v_{i}P$ , so $\mathcal{C}$ generates $(\mathrm{vs}{k}_{I{D}_i},\mathrm{vp}{k}_{I{D}_i})$ pair. Then, $\mathcal{C}$ inserts tuple $(\mathrm{PI}{D}_i,\mathrm{ps}{k}_{I{D}_i},\mathrm{vs}{k}_{I{D}_i},\mathrm{vp}{k}_{I{D}_i})$ in $L_K$ . Otherwise, if the tuple $(\mathrm{PI}{D}_i,\mathrm{ps}{k}_{I{D}_i},\mathrm{vs}{k}_{I{D}_i},\mathrm{vp}{k}_{I{D}_i})$ is present in $L_K$ , then $\mathcal{C}$ checks whether $\mathrm{vs}{k}_i=\perp$ . If true, $\mathcal{C}$ executes ReplaceKey query to obtain $\mathrm{vp}{k}_{I{D}_i}=v_{i}P$ , where $v_i\in Z_q^{*}$ . Otherwise, $\mathcal{C}$ returns $\mathrm{vp}{k}_{I{D}_i}$ to ${\mathcal{A}}_1$ .

15. Forgery: To generate ${\sigma }_i=(U_i,S_i)$ , $\mathcal{C}$ executes the following:

By using Forking lemma, ¹⁰ after replaying ${\mathcal{A}}_1$ with the same random string but different choice of $h_6$ -oracle, $\mathcal{C}$ can gain two valid signatures ${\sigma }_i^{\prime }=(U_i^{\prime },S_i^{\prime })$ and ${\sigma }_i^{\prime *}=(U_i^{\prime *},S_i^{\prime *})$ within a polynomial time, where $S_i^{\prime }={\mathrm{psk}}_{I{D}_i}^{\prime }{K}^{\prime }+{\mathrm{vsk}}_{I{D}_i}^{\prime }{P}_{\mathrm{pub}}^{\prime }+h_i^{\prime }{u}_i^{\prime }{P}_{\mathrm{rs}{u}_i}^{\prime }$ and $S_i^{\prime *}={\mathrm{psk}}_{I{D}_i}^{\prime }{K}^{\prime }+{\mathrm{vsk}}_{I{D}_i}^{\prime }{P}_{\mathrm{pub}}^{\prime }+h_i^{\prime *}{u}_i^{\prime }{P}_{\mathrm{rs}{u}_i}^{\prime }$ . We set ${\mathrm{psk}}_{I{D}_i}^{\prime }=C_i^{\prime }{D}_i^{\prime }$ , where $D_i^{\prime }={\mu }_i^{\prime }{Y}^{\prime }$ , and $Y^{\prime }=b{P}^{\prime }$ . Then, ${\mathrm{vsk}}_{I{D}_i}^{\prime }=v_i^{\prime }a{P}^{\prime }$ . From $S_i^{\prime }$ and $S_i^{\prime *}$ , we have

$$\begin{array}{c}{S}_i^{\prime }-S_i^{\prime *}={\mathrm{psk}}_{I{D}_i}^{\prime }{K}^{\prime }+{\mathrm{vsk}}_{I{D}_i}^{\prime }{P}_{\mathrm{pub}}^{\prime }+h_i^{\prime }{u}_i^{\prime }{P}_{\mathrm{rs}{u}_i}^{\prime }-\hfill \\ {\mathrm{psk}}_{I{D}_i}^{\prime }{K}^{\prime }+{\mathrm{vsk}}_{I{D}_i}^{\prime }{P}_{\mathrm{pub}}^{\prime }+h_i^{\prime *}{u}_i^{\prime }{P}_{\mathrm{rs}{u}_i}^{\prime }\hfill \\ =(C_i^{\prime }{D}_i^{\prime }+{\mathrm{vsk}}_{I{D}_i}^{\prime }{P}_{\mathrm{pub}}^{\prime }+h_i^{\prime }{u}_i^{\prime }{P}_{\mathrm{rs}{u}_i}^{\prime })-\hfill \\ (C_i^{\prime }{D}_i^{\prime }+{\mathrm{vsk}}_{I{D}_i}^{\prime }{P}_{\mathrm{pub}}^{\prime }+h_i^{\prime *}{u}_i^{\prime }{P}_{\mathrm{rs}{u}_i}^{\prime })\hfill \\ =({\mu }_i^{\prime }{Y}^{\prime }+v_i^{\prime }\mathrm{aP}\prime +h_i^{\prime }c{P}^{\prime })-\hfill \\ ({\mu }_i^{\prime }{Y}^{\prime }+v_i^{\prime }a{P}^{\prime }+h_i^{\prime *}c{P}^{\prime })\hfill \\ =({\mu }_i^{\prime }b{P}^{\prime }+v_i^{\prime }\mathrm{aP}\prime +h_i^{\prime }c{P}^{\prime })-\hfill \\ ({\mu }_i^{\prime }b{P}^{\prime }+v_i^{\prime }a{P}^{\prime }+h_i^{\prime *}c{P}^{\prime })\hfill \\ =(({\mu }_i^{\prime }+v_i^{\prime }+h_i^{\prime })-({\mu }_i^{\prime }+v_i^{\prime }+h_i^{\prime *}))\mathrm{abc}{P}^{\prime }\hfill \end{array}$$

Therefore, with $\mathrm{abc}{P}^{\prime }=\mathrm{abcP}$ , $\mathcal{C}$ returns $\mathrm{abcP}=(S_i^{\prime }-S_i^{\prime *})-(({\mu }_i^{\prime }+v_i^{\prime }+h_i^{\prime })-({\mu }_i^{\prime }+v_i^{\prime }+h_i^{\prime *}){)}^{-1}$ , as the solution to the CDHP with a probability of at least $\frac{ϵ}{q_{\mathrm{cu}}e}$ analyzed as follows.

There are three events that required for $\mathcal{C}$ to succeed in the game:

• $E_1$ : $\mathcal{C}$ does not quit during the game.

• $E_2$ : ${\mathcal{A}}_1$ forges a valid signature.

• $E_3$ : ${\mathcal{A}}_1$ produce a valid signature and $\mathcal{C}$ not terminating the game.

When all the above events happen, the probability of $\mathcal{C}$ winning the game is $P[E_1\wedge E_2\wedge E_3]=P[E_1]P[E_2|E_1]P[E_3|E_2\wedge E_1]$ , with $P[E_1]\ge {(1-\frac{1}{(q_{\mathrm{ps}{k}_{I{D}_i}+1})})}^{q_{\mathrm{ps}{k}_{I{D}_i}}}$ ; $P[E_2|E_1]=ϵ$ ; $P[E_3|E_2\wedge E_1]\ge \frac{1}{q_{\mathrm{ps}{k}_{I{D}_i}}+1}$ . Hence, we have

$$\begin{array}{c}P[E_1\wedge E_2\wedge E_3]\ge \hfill \\ \ge {(1-\frac{1}{(q_{\mathrm{ps}{k}_{I{D}_i}}+1)})}^{q_{\mathrm{ps}{k}_{I{D}_i}}}\left(\frac{1}{(q_{\mathrm{ps}{k}_{I{D}_i}}+1)}\right)ϵ\hfill \\ \ge {(1-\frac{1}{(q_{\mathrm{ps}{k}_{I{D}_i}}+1)})}^{q_{\mathrm{ps}{k}_{I{D}_i}}}\left(\frac{1}{(q_{\mathrm{ps}{k}_{I{D}_i}}+1)}\right)\hfill \\ \frac{1}{q_{\mathrm{ps}{k}_{I{D}_i}}}ϵ\hfill \\ \ge \frac{1}{q_{\mathrm{ps}{k}_{I{D}_i}}}{(1-\frac{1}{(q_{\mathrm{ps}{k}_{I{D}_i}}+1)})}^{q_{\mathrm{ps}{k}_{I{D}_i}}+1}ϵ\hfill \end{array}$$

For adequately large $q_{\mathrm{ps}{k}_{I{D}_i}}$ , $(1-\frac{1}{(q_{\mathrm{ps}{k}_{I{D}_i}}+1)})\to \frac{1}{e}$ . Therefore, $\mathcal{C}$ solves the CDHP complexity with a probability of $\frac{ϵ}{q_{c}e}$ , within a time $t^{\prime }=t+(q_c+q_H+q_{h_i}+q_{\mathrm{ps}{k}_{I{D}_i}}+q_{\mathrm{vs}{k}_{I{D}_i}}+q_s)t_m$ .

Theorem 2

Our proposed CLAS scheme is existentially unforgeable against ${\mathcal{A}}_2$ in the ROM under the intractability of the CDH problem. If ${\mathcal{A}}_2$ can forge a valid CLAS during time $t$ with a non-negligible probability $ϵ$ after making $q_H$ and $q_{h_i}$ queries, with $i=1,2,\dots ,6$ , RevealPartiaPrivateKey queries $q_{\mathrm{ps}{k}_{I{D}_i}}$ , RevealPrivateKey queries $q_{\mathrm{vs}{k}_{I{D}_i}}$ , ReplaceKey queries, Sign queries $q_s$ , then there is exists $\mathcal{C}$ who can solve CDHP with probability $\frac{ϵ}{q_{\mathrm{ps}{k}_{I{D}_i}}e}$ within a time $t^{\prime }=t+(q_c+q_H+q_{h_i}+q_{\mathrm{ps}{k}_{I{D}_i}}+q_{\mathrm{vs}{k}_{I{D}_i}}+q_s)t_m$ . ²⁹

Proof

Because the Type-2 secure proof is comparable to the Type-1 secure proof, the proof process is omitted.

Analysis of security requirements

Because V2V and V2I communication is carried out under open wireless communication channels, VANET is vulnerable to various attacks. To design a secure authentication scheme, we define the security and privacy that need to be met in VANET.^3,4,12,13,43 This section analyzes whether our scheme satisfies security and privacy and then illustrates what problems we solve.

Pseudonymity

In our proposed scheme, each OBU device in a vehicle must apply multiple pseudo-identities $\mathrm{PI}{D}_i$ to the TRA once and preload into the vehicle. TRA uses its secret value $\beta$ to generate unique $\mathrm{PI}{D}_i$ for different vehicles, and only TRA can generate them. If there is a traffic or regulation violation in the future, TRA can reveal the real identity of the corresponding $\mathrm{PI}{D}_i$ . Since pseudo-identity can protect the user’s real identity, our proposed scheme satisfies pseudonymity.

Identity privacy preservation

In our method, the final message $(M_i,\mathrm{PI}{D}_i,\mathrm{vp}{k}_{I{D}_i},{\sigma }_i,t_i)$ does not contains the vehicles’ real identity. So, the recipient cannot identify the owners of the pseudo-identity. When the pseudo-identity changes, the private and public keys are regenerated. It is difficult for an attacker to infer whether different messages belong to the same vehicle or not. Under the insecure communication channel, we use the public key to encrypt messages. So, only the device with the corresponding private key can decrypt it to ensure that the personal information is not leaked during the message’s transmission.

Mutual authentication

Our proposed scheme uses signature encryption and $\mathrm{OTP}$ to perform mutual authentication between vehicle and TRA to confirm that they are the corresponding legal entities. When the vehicle wants to apply for $\mathrm{PI}{D}_i$ , it must first generate an $\mathrm{OTP}=h_2(\mathrm{pas}{s}_{I{D}_i}\oplus Q_{I{D}_i}\oplus T_i)$ . Then it uses TRA’s public key $T_{\mathrm{pub}}$ to encrypt messages $〈E_{T_{\mathrm{pub}}}(m,\mathrm{OTP},I{D}_i,T_i,\mathrm{vp}{k}_{I{D}_i})〉$ and sends it to TRA. The TRA can use the previously registered $\mathrm{pas}{s}_{I{D}_i}$ of vehicle and calculates $Q_{I{D}_i}$ , then obtain $\mathrm{OTP}$ and compare it. This process can verify the identity of the vehicle. After successful verification, TRA will generate $\mathrm{PI}{D}_i$ for this vehicle and calculates $j=h_5(Q_{I{D}_i},T_i°)$ . Finally, TRA encrypts the message with the vehicle’s public key $\mathrm{vp}{k}_{I{D}_i}$ and transmits it back to the vehicle through the RSU. After the vehicle receives it, it decrypts the message with its private key $\mathrm{vs}{k}_{I{D}_i}$ and verifies the timestamp $T_i°$ . Then vehicle calculates $j°=h_5(Q_{I{D}_i},T_i°)$ to verify TRA. Since $Q_{I{D}_i}$ is generated using vehicle’s $I{D}_i$ and the parameter $r_i$ is selected by TRA, so only TRA can calculate $Q_{I{D}_i}$ , and resulting $j°=j$ . Therefore, our scheme satisfies mutual authentication.

Message authentication

Each message created by the vehicle must be signed before being delivered to the nearest RSU, so that the RSU can verify that the message has not been falsified or modified by an attacker $\mathcal{A}$ . According to Theorem 1 , the CDHP is hard, hence no polynomial adversary can forge a valid message. As a result, the verifier can check the legitimacy and integrity of $(M_i,\mathrm{PI}{D}_i,\mathrm{vp}{k}_{I{D}_i},{\sigma }_i,t_i)$ , by verifying whether $\hat{e}(S,P)=\hat{e}(\mathrm{PI}{D}_i{D}_i+\mathrm{vp}{k}_{I{D}_i},P_{\mathrm{pub}})·\hat{e}(h_i{U}_i,P_{\mathrm{rs}{u}_i})$ holds.

Non-repudiation

In our method, each vehicle must register itself to the TRA to obtain the identity $I{D}_i$ and $Q_{I{D}_i}$ . Then it uses $Q_{I{D}_i}$ to apply for partial private key $\mathrm{ps}{k}_{I{D}_i}=\alpha Q_{I{D}_i}$ to KGC. The TRA also generates the vehicle’s $\mathrm{PI}{D}_i$ based on the vehicle’s identity $Q_{I{D}_i}$ . The ${\sigma }_i$ and $\mathrm{PI}{D}_i$ generation are contained information representing the unique identity of the vehicle, such as $Q_{I{D}_i}$ and $\mathrm{ps}{k}_{I{D}_i}$ . The TRA can know the true identity of the vehicle based on $\mathrm{PI}{D}_i=Q_{I{D}_i}{C}_i$ , which makes the vehicle sending the message unable to deny that he or she did not address the message. Therefore, our proposed scheme satisfies the non-repudiation.

Untraceability

In Pseudonym-Gen phase, TRA generates $\mathrm{PI}{D}_i$ based on the vehicle’s real identity $Q_{I{D}_i}$ when it sends a message. The TRA can trace the attacker’s real identity and whereabouts based on the malicious message’s virtual identity. Other entities who receive the messages cannot trace that vehicle based on the messages. Therefore, our scheme satisfies untraceability.

Unlinkability

In our scheme, each virtual identity can only be used once. Each time the OBU sends a message, it uses a different $\mathrm{PI}{D}_i$ . This pseudo-identity makes it more difficult for the receiver to know the sender’s real identity and suggests it be sent by different vehicles. Therefore, our scheme satisfies the unlinkability.

Resistance to replay attack

In order to resist replay attacks, vehicles need to be verified before applying for a $\mathrm{PI}{D}_i$ . In equation (1), the vehicle transmits $〈E_{T_{\mathrm{pub}}}(m,\mathrm{OTP},I{D}_i,T_i,\mathrm{vp}{k}_{I{D}_i})〉$ to the TRA, and TRA replies with $〈E_{\mathrm{vp}{k}_{I{D}_i}}((\mathrm{PI}{D}_{i,1},K_{i,1})$ , $(\mathrm{PI}{D}_{i,2},K_{i,2})$ ,⋯, $(\mathrm{PI}{D}_{i,n},K_{i,n}),j,T_i°)〉$ , which both of the messages using a timestamp. The generation of certificateless signatures adds timestamp $t_i$ to calculate equations (4) and (5). Finally, signer generates ${\sigma }_i=(U_i,S_i)$ and message include timestamp $(M_i,\mathrm{PI}{D}_i,\mathrm{vp}{k}_{I{D}_i},{\sigma }_i,t_i)$ . The verifier can verify whether the timestamp $t_i$ is within a reasonable time interval. Therefore, our proposed scheme can resist replay attack.

Resistance to MITM attack

In order to resist MITM attack, the vehicle is required to generate a legal signature ${\sigma }_i=(U_i,S_i)$ when it wants to transmit messages $(M_i,\mathrm{PI}{D}_i,\mathrm{vp}{k}_{I{D}_i},{\sigma }_i,t_i)$ in V2V or V2I communications. If $\mathcal{A}$ intercepts this message and modifies the content, the verification process will not pass because the signature ${\sigma }_i$ is generated by the legal vehicle’s partial private key $\mathrm{ps}{k}_{I{D}_i}$ , private key $\mathrm{vs}{k}_{I{D}_i}$ , $K$ , and so on. So, these messages are only known by the legal vehicle. Besides that, the $\mathrm{PI}{D}_i$ also changes every time. When the vehicle wants to apply for $\mathrm{PI}{D}_i$ to the TRA, it needs to perform V2I communication with the RSU, and the RSU then forwards the service request to the TRA. When the TRA returns the generated virtual identity to the vehicle, it also needs to pass through the RSU. Between the vehicle and the RSU, there is an open wireless communication channel. In our scheme, the TRA generates a unique parameter $r_i$ for the vehicle. The vehicle also generates a unique parameter $\mathrm{pas}{s}_{I{D}_i}=h_1(r_i,\mathrm{nonce})$ and sends to the TRA. Only vehicle and TRA who know $r_i$ and $\mathrm{pas}{s}_{I{D}_i}$ . Therefore, they can verify each other’s identity. Thus, our scheme can resist the MITM attack.

Resistance to masquerade attack

In our proposed CLAS scheme, each vehicle broadcasts the final message using it’s $\mathrm{PI}{D}_i$ , and ${\sigma }_i$ needs to be verified. If an attacker uses other people’s $\mathrm{PI}{D}_i$ , he or she cannot check successfully because the attacker could not know the $\mathrm{ps}{k}_{I{D}_i}$ and $K_i$ , so he or she could not calculate the legal signature. Furthermore, our scheme uses a different $\mathrm{PI}{D}_i$ each time when a vehicle transmits a message. Therefore, our scheme effectively resists the masquerade attack.

Resistance to impersonation attack

To be able to impersonate a valid vehicle, $\mathcal{A}$ must be able to forge a valid message $(M_i,\mathrm{PI}{D}_i,\mathrm{vp}{k}_{I{D}_i},{\sigma }_i,t_i)$ , that satisfying the verification $\hat{e}(S,P)=\hat{e}(\mathrm{PI}{D}_i{D}_i+\mathrm{vp}{k}_{I{D}_i},P_{\mathrm{pub}})·\hat{e}(h_i{U}_i,P_{\mathrm{rs}{u}_i})$ or $\hat{e}(S,P)=\hat{e}(\sum _{i=1}^n\mathrm{PI}{D}_i{D}_i+\mathrm{vp}{k}_{I{D}_i},P_{\mathrm{pub}})·\hat{e}(\sum _{i=1}^n{h}_i{U}_i,P_{\mathrm{rs}{u}_i})$ . However, according to Theorem 1 , this is infeasible based on the hardness assumption of the CDHP. Therefore, our proposed scheme could withstand impersonation attack.

User location privacy

As mentioned in the Pseudonym-Gen phase, vehicles need to preload with multiple pseudo-identities $\mathrm{PI}{D}_i$ , and a single of them cannot be reused. Each time a vehicle sends a message to the other vehicles, it will use a different $\mathrm{PI}{D}_i$ . This method will make a legitimate vehicle difficult to track by $\mathcal{A}$ , particularly in the area when the vehicle’s density is high. At this point, the TRA will measure how many $\mathrm{PI}{D}_i$ to generate based on the number of current stored ones in the OBU device.

Security and privacy comparison

Lu et al. ⁴⁴ distinguished the privacy-preserving authentication of VANET into five categories, including certificateless signature. Based on Lu et al.’s classification, we compared the security and privacy of our proposed scheme with the other existing CLAS schemes in VANET.

In Table 3, we compare the security of our proposed CLAS scheme with the other six CLAS schemes for VANET.^{18,19,23,25–27} For ease of description, let ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ denote if the scheme could withstand the Type-1 and the Type-2 adversaries, respectively. We can find that all of the first six schemes^{18,19,23,25–27} cannot withstand ${\mathcal{A}}_2$ adversary, with Horng et al.’s¹⁹, Zhong et al.’s²⁵, and Kumar et al.’s²⁷ schemes also cannot withstand ${\mathcal{A}}_1$ adversary either. In addition, for the security and privacy requirements expressed in Table 3 that comprises message authentication, anonymity, unlinkability, traceability, replaying attack resistance, and impersonation attack resistance, Horng et al.’s ¹⁹ scheme also lacks mutual authentication and is vulnerable to MITM attacks. Meanwhile, Malhi and Batra’s ¹⁸ scheme lacks mutual authentication and user location privacy. Both mentioned schemes are the first two CLAS mechanisms specifically designed for VANET. After comparing all of those schemes with our proposed one, it is clear that our scheme satisfies all the above security and privacy requirements.

Performance analysis

To provide a fair comparison, particularly in terms of computation and communication costs, we compare our proposed scheme with the existing CDHP-based CLAS schemes in VANET.^{18,25,27,29,32}

Computation overhead

To equally assess the performance of our proposed scheme, we take the other CDHP-based CLAS schemes in VANET,^{18,25,27,29,32} which also employ bilinear maps in their Verify and Aggregate-Verify phases as the benchmark. We adopt the experiment in previous works,^{19,25,27,45,46} which observes the processing time for the Tate pairing on a 159-bit subgroup of an MNT curve with an embeds degree 6 at an 80-bit security level and running on an Intel i7 3.07 GHz CPU. Let $\mathrm{PC}$ denote the time of a pairing operation cost, $\mathrm{SC}$ is the time of a scalar multiplication cost in bilinear operation $G_1$ , $\mathrm{HC}$ is the time of a MapToPoint hash operation cost, and $n$ in Aggregate-Verify cost is the number of the verified messages. In CDHP, $\mathrm{PC}$ is the most time-consuming one compared to $\mathrm{SC}$ and $\mathrm{HC}$ . The obtained results for $\mathrm{PC}$ , $\mathrm{SC}$ , and $\mathrm{HC}$ are 3.21, 0.39, and 0.09 ms, respectively. We only consider these three operations regarding their significance.

Table 4 shows the comparison of the computation cost between our scheme and the other schemes,^{18,25,27,29,32} in terms of Sign, Verify, and Aggregate-Verify cost. Our scheme uses $3\mathrm{SC}$ in the Sign phase, which is relatively the same with some schemes.^18,25,27,29 We can see the $S_i=\mathrm{ps}{k}_{I{D}_i}{K}_i+\mathrm{vs}{k}_{I{D}_i}{P}_{\mathrm{pub}}+h_i{u}_i{P}_{\mathrm{rs}{u}_i}$ in certificateless signature ${\sigma }_i=(U_i,S_i)$ . The first one is $\mathrm{ps}{k}_{I{D}_i}{K}_i$ , the second is $\mathrm{vs}{k}_{I{D}_i}{P}_{\mathrm{pub}}$ , and the third is $h_i{u}_i{P}_{\mathrm{rs}{u}_i}$ . In the Verify phase, we use $3\mathrm{PC}$ and $2\mathrm{SC}$ . Our scheme needs to calculate $\hat{e}(S_i,P)=\hat{e}(\mathrm{PI}{D}_i{D}_i+\mathrm{vp}{k}_{I{D}_i},P_{\mathrm{pub}})·\hat{e}(h_i{U}_i,P_{\mathrm{rs}{u}_i})$ . We can divide $\hat{e}(\mathrm{PI}{D}_i{D}_i+\mathrm{vp}{k}_{I{D}_i},P_{\mathrm{pub}})·\hat{e}(h_i{U}_i,P_{\mathrm{rs}{u}_i})$ into $\hat{e}(\mathrm{PI}{D}_i{D}_i,P_{\mathrm{pub}})·\hat{e}(\mathrm{vp}{k}_{I{D}_i},P_{\mathrm{pub}})·\hat{e}(h_i{U}_i,P_{\mathrm{rs}{u}_i})$ , so it is $3\mathrm{PC}$ . Then, the $2\mathrm{SC}$ are composed of $\mathrm{PI}{D}_i{D}_i$ and $h_i{U}_i$ . In the Aggregate-Verify phase, we use $3\mathrm{PC}$ and $2\mathrm{nSC}$ . The pairing operation cost of Aggregate-Verify and Verify are the same. The scalar multiplication cost is based on the number of $n$ . We can see from $\widehat{e}(S,P)=\widehat{e}(\sum _{i=1}^{n}PI{D}_i{D}_i+vp{k}_{I{D}_i},P_{pub})·\widehat{e}(\sum _{i=1}^n{h}_i{U}_i,P_{rs{u}_i})$ . Figures 8–10 visualize the comparison of Sign, Verify, and Aggregate-Verify cost for all the schemes, respectively.

Table 4.

Comparison of the computation cost.

Scheme	Sign	Verify	Aggregate-Verify
Malhi and Batra 18	$3\mathrm{SC}$	$3\mathrm{PC}+3\mathrm{SC}$	$3\mathrm{PC}+3\mathrm{nSC}$
	= 1.17 m	= 10.8 ms	= (9.63 + 1.17 $n$ ) ms
Zhong et al. 25	$3\mathrm{SC}$	$3\mathrm{PC}+2\mathrm{SC}+\mathrm{HC}$	$3\mathrm{PC}+2\mathrm{nSC}+\mathrm{nHC}$
	= 1.17 ms	= 10.5 ms	= (9.63 + 0.87 $n$ ) ms
Kumar et al. 27	$3\mathrm{SC}$	$3\mathrm{PC}+3\mathrm{SC}$	$3\mathrm{PC}+3\mathrm{nSC}$
	= 1.17 ms	= 10.8 ms	= (9.63 + 1.17 $n$ ) ms
Kamil and Ogundoyin 29	$3\mathrm{SC}$	$3\mathrm{PC}+2\mathrm{SC}+\mathrm{HC}$	$3\mathrm{PC}+2\mathrm{nSC}+\mathrm{nHC}$
	= 1.17 ms	= 10.5 ms	= (9.63 + 0.87 $n$ ) ms
Mei et al. 32	$4\mathrm{SC}+2\mathrm{HC}$	$4\mathrm{PC}+2\mathrm{SC}$	$4\mathrm{PC}+2\mathrm{nSC}$
	= 1.74 ms	= 13.62 ms	= (12.84 + 0.78 $n$ ) ms
Ours	$3\mathrm{SC}$	$3\mathrm{PC}+2\mathrm{SC}$	$3\mathrm{PC}+2\mathrm{nSC}$
	= 1.17 ms	= 10.41 ms	= (9.63 + 0.78 $n$ ) ms

$\mathrm{PC}$ : Pairing operation cost (3.21 ms).

$\mathrm{SC}$ : Scalar multiplication cost (0.39 ms).

$\mathrm{HC}$ : MapToPoint hash function cost (0.09 ms).

Figure 8.

Sign cost.

Figure 9.

Verify cost.

Figure 10.

Aggregate-Verify cost.

From the Verify and Aggregate-Verify cost comparison in Table 4, it is apparent if our proposed scheme is more efficient than the already existing CDHP-based CLAS schemes.^{18,25,27,29,32}

Communication overhead

Meanwhile, to evaluate the communication cost of one successful information exchanged in V2I or V2V communication, we follow the general parameters mentioned in most related schemes.^26,34,47 We consider the length of a cyclic additive group $G_1$ and multiplicative group $G_2$ as 128 Bytes and 40 Bytes, respectively. Let the output length of the general one-way hash function and number in $Z_q^{*}$ are 20 Bytes, and the length of the timestamp is 4 Bytes. Referred to IEEE Trial-Use standard, ⁴⁸ the length of the traffic-related message VANET is 67 Bytes.

In Malhi and Batra’s ¹⁸ scheme, vehicle sends final message containing $\mathrm{PI}{D}_i=(\mathrm{PI}{D}_{i,1}\in G_1,\mathrm{PI}{D}_{i,2}\in Z_q^{*}),(\mathrm{vp}{k}_{I{D}_i},\mathrm{ps}{k}_{I{D}_i},{\sigma }_i=(U_i,V_i)\in G_1)$ , and $M_i$ . Thus, the total communication cost is 727 Bytes. In Zhong et al.’s ²⁵ scheme, vehicle sends final message contains of $\mathrm{PI}{D}_i=((\mathrm{PI}{D}_{i,1},\mathrm{PI}{D}_{i,2}\in G_1),(T_i)),$ $(\mathrm{vp}{k}_{I{D}_i},$ ${\sigma }_i=(U_i,S_i)\in G_1)$ , $t_i$ , and $M_i$ to a RSU. Hence, the total communication cost is 715 Bytes. In Mei et al.’s ³² scheme, vehicle sends final message contains of ${\mathrm{PID}}_i=((\mathrm{PI}{D}_{i,1},\mathrm{PI}{D}_{i,2}\in G_1),(T_i))$ , $\mathrm{RS}{U}_{I{D}_i}\in Z_q^{*},$ $(\mathrm{vp}{k}_{I{D}_i},$ ${\sigma }_i=(U_i,S_i)\in G_1),$ $t_i$ and $M_i$ . Hence, the total communication cost is 735 Bytes. In Kamil and Ogundoyin’s ²⁹ scheme, vehicle broadcasts final message that contains $\mathrm{PI}{D}_i=((\mathrm{PI}{D}_{i,1},\mathrm{PI}{D}_{i,2}\in G_1),(T_i)),$ $(\mathrm{vp}{k}_{I{D}_i},$ ${\sigma }_i=(U_i,S_i)\in G_1)$ , $t_i$ , and $M_i$ to a RSU. Hence, the total communication cost is 715 Bytes. In Kumar et al.’s ²⁷ scheme, vehicle sends final message contains of $\mathrm{PI}{D}_i=(\mathrm{PI}{D}_{i,1}\in G_1,\mathrm{PI}{D}_{i,2}\in Z_q^{*}),(\mathrm{vp}{k}_{I{D}_i},\mathrm{ps}{k}_{I{D}_i},{\sigma }_i=(U_i,S_i)\in G_1)$ , and $M_i$ . Thus, the total communication cost is 727 Bytes. Finally, in our proposed scheme, a vehicle broadcasts final message that consists of $M_i,t_i,(\mathrm{PI}{D}_i,\mathrm{vp}{k}_{I{D}_i},{\sigma }_i=(U_i,S_i)\in G_1)$ . Therefore, the total communication cost of our scheme is the most efficient of them all, that is 583 Bytes. The comparison of communication cost of all schemes is shown in Figure 11 and Table 5.

Figure 11.

Communication cost for a single message.

Table 5.

Comparison of the communication cost.

Scheme	Single message	$n$ messages
Malhi and Batra 18	727 bytes	727 $n$ bytes
Zhong et al. 25	715 bytes	715 $n$ bytes
Kumar et al. 27	727 bytes	727 $n$ bytes
Kamil and Ogundoyin 29	715 bytes	715 $n$ bytes
Mei et al. 32	735 bytes	735 $n$ bytes
Ours	583 bytes	583 $n$ bytes

Conclusion

In this article, we proposed a CLAS scheme to improve security and privacy in VANET, with efficiency becoming the main spotlight. Our proposed scheme could solve the mentioned issues by satisfying all security and privacy requirements such as pseudonymity, message authentication, untraceability, unlinkability, privacy preservation, and resistance to some common attacks. According to an extensive performance study, our proposed scheme is substantially more efficient in terms of computation and communication costs than the existing reputable schemes. Hence, it is more suitable for both V2V and V2I communication in VANET.