# A Batch Authentication Design to Protect Conditional Privacy in Internet of Vehicles

Authors: Yuhao Yang; Xiujie Huang; Jinyu Hu
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Internet of vehicles (IoV), a novel technology, holds paramount importance within the transportation domain due to its ability to increase traffic efficiency and safety. Information privacy is of vital importance in IoV when sharing information among vehicles. However, due to the openness of the communication network, information sharing is vulnerable to potential attacks, such as impersonation, modification, side-channel and replay attacks, and so on. In order to resolve the aforementioned problem, we present a conditional privacy-preserving batch authentication (CPPBA) scheme based on elliptic curve cryptography (ECC). The proposed scheme avoids the certificate management problem, conducing to efficiency improvement. When a message is transmitted by a vehicle, its pseudo identity rather than the real identity is also broadcasted along with the shared message, which protects the privacy of the vehicle’s identity. But this privacy is conditional because TA and only the TA can reveal the real identity of the vehicle by tracing. The proposed scheme is batch verifiable, which reduces the computation costs. In addition, our scheme does not involve bilinear pairing operations and does not use the map-to-point hash function, thus making the verification process more effective. An exhaustive efficiency comparison has been carried to show that the proposed CPPBA scheme has lower computation, communication, and storage overheads than the state-of-the-art ones. A relatively comprehensive security analysis has also been carried, which not only shows that the signature design in the CPPBA scheme is unforgeable under the random oracle model but also illustrates that the CPPBA scheme is resistant to various potential attacks. The security is also verified by a popular automated simulation tool, that is, AVISPA.


---

## Body

## 1. Introduction

With the rapid growth of networks and information technology, the internet of vehicles (IoV) has attracted more and more attention because of its ability to provide communication between vehicles, road side units (RSUs), and other devices (including personal devices and sensors), known as vehicle-to-everything (V2X) [1]. The vehicles ad hoc network (VANET), as a predecessor of IoV, effectively combines the driver, vehicle, and roads so as to provide the driver with information about the state of other vehicles outside the visual range [2], road conditions [3], and location-related life services [4], which is helpful to improve road safety and traffic efficiency. The VANET is equipped with wireless communication equipment road side units distributed along both sides of the road, which have sufficient energy supply, good wireless communication capabilities, and strong computing storage capabilities, and can also bear part of the computing overhead for the vehicle nodes. However, the VANET is a network that treats each vehicle node as a router and a custom node. The network coverage of these nodes is small, and the computing power is limited. Moreover, in the VANET, the network capacity is limited, and the wireless channel quality is unstable because it is affected by many factors, such as interference signals, complex infrastructure, and relative vehicle speed [5]. The IoV, as an evolution of the conventional VANET, is expected to remove these restrictions and promises huge commercial interest and research value [6].To realize V2X communication, various protocols including the IEEE 802.11p standard, the dedicated short-range communication (DSRC), and cellular wireless communication are employed in IoV. Vehicles in IoV, equipped with an on-board unit (OBU), are usually connected by DSRC. Through GPS, radio frequency identification (RFID), sensors, cameras, image processing equipment, and so on, the vehicle can collect information about its own environment and surrounding vehicle status (e.g., road status, weather, and driving directions) and then broadcast the information within the coverage of the RSU. The RSU collects this information and rebroadcasts it along with other services or warning messages to other vehicles [7] (e.g., it is expected that safety information will be broadcasted every 100–300 milliseconds [8]). This information can be analyzed and processed by the OBU to provide the driver with a safe driving environment and plan the optimal driving route [9]. It can be seen that vehicles in IoV act as information providers and consumers at the same time. Therefore, it is very important to successfully realize effective data distribution in IoV applications.When the information is shared in the IoV network, it is necessary to ensure that the right information reaches the right places at the right time. However, due to the openness of the communication network, hackers, malicious vehicles, and other nodes may change the information transmitted in IoV and pretend a legitimate node to send the bogus information over the IoV network. This results that the information sharing is vulnerable to potential attacks [10], such as side-channel attacks, impersonation attacks, modification attacks, and replay attacks. In order to resist various malicious attacks, one solution is to design a secure authentication scheme. Moreover, the environment in the IoV always changes because the vehicle communication range is short and the speed of the vehicle is high (over 36 km/h) [11]. This rapid change of the IoV network topology limits the communication time between vehicles. In addition, when in a traffic-intensive area, information exchange is very frequent, and the vehicle is usually required to be able to quickly authenticate a large amount of traffic-related information. In particular, when the shared information is a collision warning or emergency notification, this information is related to the safety of life and property, and a quick response must be made. To overcome the limitations of the computing and communication capabilities of the IoV, it is necessary to ask that the designed secure authentication scheme is efficient enough with a very low overhead in computation, communication, and storage.Although extensive research of the authentication design has been conducted on the IoV in recent years, it has not yet been fully commercialized, partly because the above-mentioned challenges of security and efficiency still need to be resolved. (A short review of the related work on authentication designs for IoV will be given in the next section.) Therefore, a new CPPBA scheme is proposed. The main contributions of this article are summarized as follows:(1)
The proposed scheme is conditional privacy-preserving. That is, the vehicle uses a pseudo identity to share information, but TA and only the TA can reveal the real identity of the vehicle by tracing.(2)
The proposed scheme for IoV does not use the expensive pairing operations and map-to-point hash function so that it improves the computational efficiency of the system.(3)
The proposed scheme is proven secure and unforgeable against the potential adversariesA1 and A2 under the ECDLP assumption, and the AVISPA tool is used to simulate the proposed scheme.(4)
Compared with the state-of-the-art schemes, our scheme has lower computation, communication, and storage overhead.The remainder of this article is organized as follows. In Section2, we present related work on various authentication schemes in VANET and IoV. System model and preliminaries are introduced in Section 3. Based on the model, our scheme is proposed in detail in Section 4. The security proof and analysis of the proposed scheme are presented in Section 5. In Section 6, the performance analysis of our scheme is shown to demonstrate its efficiency. Finally, we conclude this article in Section 7.


## 2. Related Work

There are mainly two types of authentication designs in IoV: one is on the basis of public-key infrastructure (PKI) and the other is on the basis of identity-based (ID-based) cryptography. The PKI-based authentication scheme has a disadvantage of low efficiency mainly because it requires a certificate authority (CA) to manage the identity/public key of the vehicle, which increases the computation, communication, and storage burdens. For example, in the anonymous certificate authentication scheme proposed by Raya and Hubaux in 2007 [12], it is necessary to install many anonymous certificates and public and private keys for each vehicle in advance, which brings a huge certificate management burden to CA. In the pseudonymous authentication scheme, called PASS, proposed by Sun et al. in 2010 [13], the size of the certificate revocation list (CRL) is linear with the number of revoked vehicles, and the vehicles are allowed to update certificates on road by the aid of RSU, which reduces the certificate management overhead to an acceptable extent at that time.To improve efficiency, many researchers have invested a lot of energy to design ID-based authentication schemes because they exploit ID-based signatures and do not need to use certificates for identity verification. In order to protect the privacy of the user’s identity, ID-based authentication schemes use pseudo identity to communicate over the IoV network. The ID-based authentication schemes can be roughly divided into two categories, namely, the bilinear-pairing-based authentication schemes those adopt bilinear pairings operations (e.g., see [14–17]), and the elliptic-curve-based authentication schemes are designed on the basis of the elliptic curve cryptography (ECC) without bilinear pairings (such as references [18–22]).In 2016, to solve the problem of privacy leakage caused by the CRL checking process, Jiang et al. [14] proposed an anonymous batch authentication scheme using bilinear pairings, called ABAH, where the CRL checking process is performed by calculating a hash message authentication code. But the ABAH scheme [14] is inefficient due to the frequent update and revocation of the group key under the group key agreement and the complicated operations of bilinear pairings in processing batch authentication. In 2017, based on short-time anonymous certificates, Azees et al. [15] presented an authentication scheme using bilinear pairings, called EAAP. But the EAAP scheme does not protect against the bogus message attack, framing attack, Sybil attack, and replay attack [23]. In 2020, Ali and Li [16] proposed a scheme using bilinear pairings to achieve V2I secure communication. This scheme supports batch verification of messages to improve the efficiency of message verification, but compared with other schemes using elliptic curve construction, this scheme still has a larger computational and communication overhead. In 2021, Mei et al. [17] proposed an effective certificateless aggregation signature scheme. However, it suffers from the modification attack as proposed by Liu et al. [24], and has a huge computational and communication overhead because it uses bilinear pairings and map-to-point hash operations.It is well-known that the bilinear pairings are the most expensive operation among all the cryptographic operations because of their highest computation and storage overhead. It is also well-known that ECC can provide higher security with smaller keys in size and then improve the computational and communication efficiency, storage capacity, and bandwidth efficiency. Particularly, ECC with 160 bit keys provides the same level of security as RSA with 1,024 bit keys [25]. Therefore, researchers are dedicated to studying the use of ECC to implement an identity-based signature scheme without bilinear pairings. In 2017, in order to solve the existing schemes that rely heavily on a tamper-proof device (TPD) or cannot satisfy the security requirement, Cui et al. [18] proposed the SPACF scheme that is based on software without relying on any special hardware. In the SPACF scheme [18], the Cuckoo filter and the binary search methods are presented to improve performance in the batch verification phase, but the communication interactions are very frequent such that it is less efficient in practical applications. Contrary to [18], in 2018, Xie et al. [19] proposed an efficient message authentication scheme supporting batch messages verification as well as signatures aggregation. In their scheme, the master key of the system will be loaded into the TPD of each registered vehicle. However, this approach is very dangerous because it means that the TPD of each vehicle contains the master key of the system. When the TPD of a certain vehicle is compromised, the entire authentication system will collapse. As we know, such an attack on TPD exists. That is, some attackers can obtain part of TPD information through side-channel attacks [26, 27], such as power analysis and laser scanning. In addition, it is more troublesome to revoke the identity of the vehicle because the master key of the system is already loaded in the TPD of each vehicle. Therefore, this approach is not advisable, and few researchers have continued this method afterwards. In the same year, Gayathri et al. [20] proposed a certificateless authentication scheme without pairings, thereby improving communication and computing efficiency. However, in Gayathri et al.’s scheme, a vehicle can impersonate other vehicles through the pseudonym generated by itself, and the secure key update is not provided, so it is vulnerable to impersonate attack and side-channel attack. In 2020, Sutrala et al. [21] proposed a conditional privacy protection certification scheme with pairings. However, we found that the scheme was not secure because the signature was forgeable and a forgery of the signature was constructed [28]. In 2021, Thumbur et al. [22] proposed an efficient authentication scheme based on signature aggregation. Similar to Mei et al.’s scheme [17], Thumbur et al.’s scheme is also vulnerable to modification attacks [24]. Finally, we summarize the related work on the authentication schemes for IoV in Table 1, which shows each design with the basis of ECC or bilinears and the property of batch authentication.Table 1
A review of authentication schemes.
SchemePKI/ID-basedECC/bilinear-basedBatch authenticationRaya et al. [12]PKIECCNoSun et al. [13]PKIBilinear-basedNoJiang et al. [14]ID-basedBilinear-basedYesAzees et al. [15]ID-basedBilinear-basedYesAli et al. [16]ID-basedBilinear-basedYesMei et al. [17]ID-basedBilinear-basedYesCui et al. [18]ID-basedECCYesXie et al. [19]ID-basedECCYesGayathri et al. [20]ID-basedECCYesSutra et al. [21]ID-basedECCYesThumbur et al. [22]ID-basedECCYesFrom the above review, it can be seen that the above authentication schemes for IoV still have some problems in security and efficiency. In order to fill these problems, we propose a secure and efficient ID-based conditional privacy protection batch authentication scheme on the basis of ECC without pairings. It can be shown that our scheme meets the security requirements, including anonymous authentication, message integrity, traceability, unlinkability, and so on and that our scheme has low computation, communication, and storage cost.


## 3. System Model and Preliminaries

In this section, the system model, security model, security goals, and the elliptic curve discrete logarithm assumption are briefly introduced.


### 3.1. System Model

As shown in Figure1, the system model of the IoV in this paper consists of four entities: the trusted authority (TA), the key generation center (KGC), road side units (RSUs) fixed at the road side, and vehicles.(1)
TA: The TA is considered to be a fully trusted third party, which can be a government entity or a trusted organization entity with sufficient calculation and storage capabilities. It is responsible for generating system parameters and the registration of vehicles. Moreover, TA is the only entity that can track the vehicle’s real identity when it maliciously spreads false information.(2)
KGC: The KGC is another trusted entity enriched with computation and communication resources in the system. The KGC is responsible for generating the pseudo identity and partial private key of the vehicle, and KGC and TA are two independent third parties.(3)
RSUs: RSUs are wireless communication equipment, such as base stations deployed along the road. The RSU acts as an intermediate node between the TA/KGC and the vehicle. The RSU connects with the TA/KGC by a wired link and the vehicle by a wireless channel under the DSRC protocol (IEEE 802.11p) [29] or the cellular communication technology. The RSU can inspect the validity of the messages received from the vehicle and forward the valid message to nearby vehicles and RSUs.(4)
Vehicles: Each vehicle is equipped with an OBU, which is responsible for message generation and transmission to nearby vehicles and RSUs, and stores sensitive information in its TPD.Figure 1
System model.


### 3.2. Security Model of CPPBA Scheme

In this subsection, the security model of CPPBA schemes will be described. Similar to [17, 21, 22, 30–32], we consider the following types of adversaries:(1)
Type-I adversaryA1: This adversary is also called a public-key replacement attacker, who can compromise the vehicle’s secret value or is capable to replace the public key of any vehicle with a value of his choice but cannot access the KGC’s master secret key.(2)
Type-II adversaryA2: This adversary is also called a malicious KGC attacker, who can access the KGC’s master secret key but cannot replace the public key of any vehicle.To show the capabilities of adversaries, the following two games, that is, Game I and Game II, are introduced, which are, respectively, performed by a Type-I adversary and a Type-II adversary interaction with some challengers.Game I: This game is executed between the challengerΓ1 and an adversary A1 as follows:(1)
Setup phase: In this phase, challengerΓ1 initializes system parameters params and k, and then Γ1 forwards params to the adversary A1 and keeps k secretly.(2)
H3_query: The adversary A1 makes H3_query on identity PIDi, and then challenger Γ1 returns fi to A1.(3)
H4_query: The adversary A1 makes H4_query on identity PIDi and message M, and then challenger Γ1 returns hi to A1.(4)
Sign_query: The adversaryA1 makes signature queries on messages M under identity PIDi that are adaptively chosen by the adversary himself. Then, the challenger Γ1 runs the signing algorithm to compute the signature σi to the adversary.(5)
Forgery: The adversary outputs a forged signatureσi∗ on message M under identity PIDi∗ and wins the game if:(a)
σi∗ is a valid signature on the message M under identity PIDi∗.(b)
There exists the casePIDi∗=PIDi in the valid signature forged by A1.(c)
When the adversaryA1 makes H3_query on identity PIDi∗=PIDi, challenger Γ1 returns fi∗≠fi.Game II: This game is executed between the challengerΓ2 and an adversary A2 as follows:(1)
Setup phase: In this phase, challengerΓ2 initializes system parameters params and k, and then Γ2 forwards params and k to the adversary A2.(2)
H3_query: The adversary A2 makes H3_query on identity PIDi, and then challenger Γ2 returns fi to A2.(3)
H4_query: The adversary A2 makes H4_query on identity PIDi and message M, and then challenger Γ2 returns hi to A2.(4)
Extract_query: The adversaryA2 makes Extract_query for PIDi1 and the partial private key pskVi using PIDi; Γ2 runs the Extract_query algorithm to compute the PIDi1 and the partial private key pskVi and returns them to adversary A2.(5)
Sign_query: The adversaryA2 makes signature queries on messages M under identity PIDi that are adaptively chosen by the adversary himself. Then, the challenger Γ2 runs the signing algorithm to compute the signature σi to the adversary.(6)
Forgery: The adversary outputs a forged signatureσi∗ on message M under identity PIDi∗ and wins the game if(a)
σi∗ is a valid signature on the message M under identity PIDi∗,(b)
there exists the casePIDi∗=PIDi in the valid signature forged by A2,(c)
when the adversaryA2 makes H4_query on identity PIDi∗=PIDi, challenger Γ2 returns hi∗≠hiDefinition 1: An authentication scheme in IoV is said to be provable security (i.e., existential unforgeability) if there are no polynomial-time Type-I and Type-II adversaries who can, respectively, win Game I and Game II with non-negligible advantages.


### 3.3. Security Goals

According to [16, 17, 21–23], we find that a secure authentication scheme in IoV should satisfy the following security requirements:(1)
Message authentication and integrity: The receiver should be able to verify the signature and inspect whether the received message was modified or forged.(2)
Conditional privacy-preserving or traceability: The vehicle’s real identity should be hidden during message transmission and authentication processes to prevent the leakage of the vehicle’s sensitive information. Only TA is able to track the vehicle’s real identity from its signature.(3)
Unthinkability: No attacker can link any two received messages, even if two messages are sent from the same vehicle.(4)
Resistance to impersonation attack: In this type of attack, the attacker is able to imitate a legitimate vehicle to generate a valid signature. A secure CPPBA scheme should be able to prevent the impersonation attack.(5)
Resistance to message modification attack: In this type of attack, the attacker is able to modify the legitimate message that is transmitted over the network to achieve its specific purpose. For example, the attacker sends a fable traffic jam message to nearby vehicles to get a better traffic condition for itself. A secure CPPBA scheme should be able to prevent the message from modification attacks.(6)
Resistance to side-channel attack: In this type of attack, the attacker is able to attack the TPD of the vehicle by some physical methods to obtain part information stored in the TPD. In the secure CPPBA scheme, the secret stored in the TPD of the vehicle should not be disclosed by side-channel attacks.(7)
Resistance to replay attack: This attack is a type of network attack, in which some valid data is maliciously repeated or delayed in transmission. A secure CPPBA scheme should be able to withstand such an attack.The security requirements of the CPPBA scheme will be analyzed in detail in Section5.2.


### 3.4. Elliptic Curve Discrete Logarithm Assumption

Letp and q be two large prime numbers, and Fp represent a finite field of p elements. Suppose an elliptic curve is defined by the equation as follows: y2=x3+ax+bmodp, where a,b∈Fp and 4a3+27b2modp≠0. Let O be the point at infinity. The point O and all points on the elliptic curve form an additive group G of order q. Let P be a generator of group G. The scalar multiplication of the elliptic curve is defined as kP=P+P⋯+Pktimes, where k∈Zq∗.Elliptic curve discrete logarithm problem (ECDLP) and assumption: Given two points on the elliptic curveP,Q∈G, where Q=xP and x∈Zq∗, the ECDLP problem is to determine the integer x. It is assumed that the ECDLP problem is hard when q is large.


## 3.1. System Model

As shown in Figure1, the system model of the IoV in this paper consists of four entities: the trusted authority (TA), the key generation center (KGC), road side units (RSUs) fixed at the road side, and vehicles.(1)
TA: The TA is considered to be a fully trusted third party, which can be a government entity or a trusted organization entity with sufficient calculation and storage capabilities. It is responsible for generating system parameters and the registration of vehicles. Moreover, TA is the only entity that can track the vehicle’s real identity when it maliciously spreads false information.(2)
KGC: The KGC is another trusted entity enriched with computation and communication resources in the system. The KGC is responsible for generating the pseudo identity and partial private key of the vehicle, and KGC and TA are two independent third parties.(3)
RSUs: RSUs are wireless communication equipment, such as base stations deployed along the road. The RSU acts as an intermediate node between the TA/KGC and the vehicle. The RSU connects with the TA/KGC by a wired link and the vehicle by a wireless channel under the DSRC protocol (IEEE 802.11p) [29] or the cellular communication technology. The RSU can inspect the validity of the messages received from the vehicle and forward the valid message to nearby vehicles and RSUs.(4)
Vehicles: Each vehicle is equipped with an OBU, which is responsible for message generation and transmission to nearby vehicles and RSUs, and stores sensitive information in its TPD.Figure 1
System model.


## 3.2. Security Model of CPPBA Scheme

In this subsection, the security model of CPPBA schemes will be described. Similar to [17, 21, 22, 30–32], we consider the following types of adversaries:(1)
Type-I adversaryA1: This adversary is also called a public-key replacement attacker, who can compromise the vehicle’s secret value or is capable to replace the public key of any vehicle with a value of his choice but cannot access the KGC’s master secret key.(2)
Type-II adversaryA2: This adversary is also called a malicious KGC attacker, who can access the KGC’s master secret key but cannot replace the public key of any vehicle.To show the capabilities of adversaries, the following two games, that is, Game I and Game II, are introduced, which are, respectively, performed by a Type-I adversary and a Type-II adversary interaction with some challengers.Game I: This game is executed between the challengerΓ1 and an adversary A1 as follows:(1)
Setup phase: In this phase, challengerΓ1 initializes system parameters params and k, and then Γ1 forwards params to the adversary A1 and keeps k secretly.(2)
H3_query: The adversary A1 makes H3_query on identity PIDi, and then challenger Γ1 returns fi to A1.(3)
H4_query: The adversary A1 makes H4_query on identity PIDi and message M, and then challenger Γ1 returns hi to A1.(4)
Sign_query: The adversaryA1 makes signature queries on messages M under identity PIDi that are adaptively chosen by the adversary himself. Then, the challenger Γ1 runs the signing algorithm to compute the signature σi to the adversary.(5)
Forgery: The adversary outputs a forged signatureσi∗ on message M under identity PIDi∗ and wins the game if:(a)
σi∗ is a valid signature on the message M under identity PIDi∗.(b)
There exists the casePIDi∗=PIDi in the valid signature forged by A1.(c)
When the adversaryA1 makes H3_query on identity PIDi∗=PIDi, challenger Γ1 returns fi∗≠fi.Game II: This game is executed between the challengerΓ2 and an adversary A2 as follows:(1)
Setup phase: In this phase, challengerΓ2 initializes system parameters params and k, and then Γ2 forwards params and k to the adversary A2.(2)
H3_query: The adversary A2 makes H3_query on identity PIDi, and then challenger Γ2 returns fi to A2.(3)
H4_query: The adversary A2 makes H4_query on identity PIDi and message M, and then challenger Γ2 returns hi to A2.(4)
Extract_query: The adversaryA2 makes Extract_query for PIDi1 and the partial private key pskVi using PIDi; Γ2 runs the Extract_query algorithm to compute the PIDi1 and the partial private key pskVi and returns them to adversary A2.(5)
Sign_query: The adversaryA2 makes signature queries on messages M under identity PIDi that are adaptively chosen by the adversary himself. Then, the challenger Γ2 runs the signing algorithm to compute the signature σi to the adversary.(6)
Forgery: The adversary outputs a forged signatureσi∗ on message M under identity PIDi∗ and wins the game if(a)
σi∗ is a valid signature on the message M under identity PIDi∗,(b)
there exists the casePIDi∗=PIDi in the valid signature forged by A2,(c)
when the adversaryA2 makes H4_query on identity PIDi∗=PIDi, challenger Γ2 returns hi∗≠hiDefinition 1: An authentication scheme in IoV is said to be provable security (i.e., existential unforgeability) if there are no polynomial-time Type-I and Type-II adversaries who can, respectively, win Game I and Game II with non-negligible advantages.


## 3.3. Security Goals

According to [16, 17, 21–23], we find that a secure authentication scheme in IoV should satisfy the following security requirements:(1)
Message authentication and integrity: The receiver should be able to verify the signature and inspect whether the received message was modified or forged.(2)
Conditional privacy-preserving or traceability: The vehicle’s real identity should be hidden during message transmission and authentication processes to prevent the leakage of the vehicle’s sensitive information. Only TA is able to track the vehicle’s real identity from its signature.(3)
Unthinkability: No attacker can link any two received messages, even if two messages are sent from the same vehicle.(4)
Resistance to impersonation attack: In this type of attack, the attacker is able to imitate a legitimate vehicle to generate a valid signature. A secure CPPBA scheme should be able to prevent the impersonation attack.(5)
Resistance to message modification attack: In this type of attack, the attacker is able to modify the legitimate message that is transmitted over the network to achieve its specific purpose. For example, the attacker sends a fable traffic jam message to nearby vehicles to get a better traffic condition for itself. A secure CPPBA scheme should be able to prevent the message from modification attacks.(6)
Resistance to side-channel attack: In this type of attack, the attacker is able to attack the TPD of the vehicle by some physical methods to obtain part information stored in the TPD. In the secure CPPBA scheme, the secret stored in the TPD of the vehicle should not be disclosed by side-channel attacks.(7)
Resistance to replay attack: This attack is a type of network attack, in which some valid data is maliciously repeated or delayed in transmission. A secure CPPBA scheme should be able to withstand such an attack.The security requirements of the CPPBA scheme will be analyzed in detail in Section5.2.


## 3.4. Elliptic Curve Discrete Logarithm Assumption

Letp and q be two large prime numbers, and Fp represent a finite field of p elements. Suppose an elliptic curve is defined by the equation as follows: y2=x3+ax+bmodp, where a,b∈Fp and 4a3+27b2modp≠0. Let O be the point at infinity. The point O and all points on the elliptic curve form an additive group G of order q. Let P be a generator of group G. The scalar multiplication of the elliptic curve is defined as kP=P+P⋯+Pktimes, where k∈Zq∗.Elliptic curve discrete logarithm problem (ECDLP) and assumption: Given two points on the elliptic curveP,Q∈G, where Q=xP and x∈Zq∗, the ECDLP problem is to determine the integer x. It is assumed that the ECDLP problem is hard when q is large.


## 4. The Proposed Scheme

For the requirement of conditional privacy-preserving and high authentication efficiency in IoV, a CPPBA scheme is proposed. Table2 describes the notations used in our scheme. The details of the proposed scheme are described as follows, whose working flow is also illustrated in Figure 2.Table 2
Notations and their meanings.
SymbolDescriptionp,qTwo large primesGAn additive group of elliptic curve points with prime order,qPA generator ofGEAn elliptic curveTATrusted authorityKGCKey generation centerRSURoad side unitViith vehiclePIDi=PIDi1,PIDi2,TViVi ’s pseudo identityTViValidity period ofPIDiRIDiVi ’s real identityPpub,sPublic and private keys of TAKpub,kPublic and private keys of KGCpskViVi’s partial private keyMiA messageσiSignature on message,MiH1,H2,H3,H4Secure one-way hash functions‖Concatenation operation⊕Exclusive OR operationFigure 2
Working flow of our proposed scheme.


### 4.1. System Initialization

This phase is performed by TA and KGC to generate the initial system parameters along with their public and private key pairs using the following steps:(1)
TA chooses two large primesp and q. TA selects elliptic curve additive group G of order q, which is defined by E:y2=x3+ax+bmodp, where a,b∈Fp and 4a3+27b2modp≠0. P is a generator of the group G.(2)
TA randomly selectss∈Zq∗ as its master key and computes Ppub=sP as the corresponding public key.(3)
KGC randomly selectsk∈Zq∗ as its master private key and computes Kpub=kP as the corresponding public key.(4)
TA chooses four one-way cryptographic hash functionsH1:G⟶Zq∗, H2:0,1∗⟶Zq∗,H3:0,1∗⟶Zq∗, H4:0,1∗⟶Zq∗.(5)
Finally, TA and KGC broadcast public parametersparams=p,q,E,P,G,Ppub,Kpub,H1,H2,H3,H4.


### 4.2. Vehicle Registration

In this stage, TA communicates with the vehicleVi in a secure channel. The following steps will be performed:(1)
Vi first sends its real identity RIDi to TA, which contains the real information of the user, such as the ID number of the vehicle owner, the license plate number, and vehicle identification number.(2)
TA computesαi=H1RIDi and stores the pair RIDi,αi. Then TA marks Vi as a registered vehicle and sends αi to Vi via the secure channel.


### 4.3. Vehicle Partial Key and Pseudo Identity Generation

In order to protect the privacy of the vehicle, anonymous communication is necessary. On the other hand, the TA is asked to be able to reveal the real identity of the vehicle if necessary. Hence, this privacy is conditional. To this end, a pseudo identity is generated for each registered vehicleVi along with the partial private key by KGC interaction with the vehicle through a secure channel before signing a message. This phase consists of the following steps:(1)
Vi sends αi to KGC via the secure channel.(2)
KGC checks whetherαi exists in the registered vehicle list obtained from TA via the secure channel. If it does not exist, KGC terminates. Otherwise, KGC generates Vi’s partial private key and pseudo identity by steps (3) and (4).(3)
KGC randomly choosesμi∈Zq∗ and computes PIDi1=μiP and PIDi2=αi⊕H2μiPpub‖TVi. Let Vi’s pseudo identity as PIDi=PIDi1,PIDi2,TVi, where TVi is the validity period of PIDi.(4)
Then, KGC computesVi’s partial private key as pskVi=fik+μi, where fi=H3PIDi‖Kpub.(5)
Finally, KGC sendspskVi,PIDi to Vi via the secure channel. Vi stores pskVi,PIDi in its TPD.This phase is also shown in Figure3.Figure 3
Vehicle partial key and pseudo-identity generation.


### 4.4. Vehicle Key Generation and Message Signature

To ensure the integrity and validity of the messageMi, the vehicle signs the message Mi before broadcasting it.(1)
Vi randomly selects ri∈Zq∗ as its private key and computes Ri=riP.(2)
Vi computes hi=H4Mi‖PIDi‖Ti, where Ti is the current timestamp. Then Vi generates the signature σi=δi,Ri, where δi=pskVi+rihi. Finally, Vi broadcasts the message-signature tuple Mi,PIDi,σi,Ti to the vicinal RSUs and other vehicles.


### 4.5. Signature Verification

When the RSU and other vehicles receive the message broadcasted by the vehicleVi, the validity of the message is verified through the following steps:(1)
The receiver first validatesTVi of PIDi and then checks the validity of the timestamp Ti. If Ti′−Ti>ΔT, the receiver discards this message, where Ti′ is the time when the receiver receives the message and ΔT represents the difference between the clock of the vehicle Vi and the local clock. Otherwise, the receiver continues to do the next verification.(2)
The receiver computesfi=H3PIDi‖Kpub and hi=H4Mi‖PIDi‖Ti and checks whether equation (1) holds or not. If it holds, the receiver accepts the message. Otherwise, the receiver discards it.(1)δiP=fiKpub+PIDi1+hiRi.The correctness of equation (1) is proved as follows:(2)δiP=pskVi+rihiP,=fik+μi+rihiP,=fiKpub+PIDi1+hiRi.


### 4.6. Batch Verification

A vehicle may broadcast or receive multiple messages at the same time, especially in traffic-extensive areas. If the receiver verifies the messages one by one, it may cause redundant computation and a relatively long delay. In our scheme, efficient batch verification is developed, which is shown as follows:(1)
Supposen messages-signature tuples M1,PID1,σ1,T1,M2,PID2,σ2,T2,…,Mn,PIDn,σn,Tn are received. The receiver first checks the freshness of the timestamp Ti for message Mi and Tvi. If Ti or Tvi has expired, it rejects this message Mi. Otherwise, it performs the next verification.(2)
Letσii=1,…,n′ be the list of signatures that are freshly generated having valid pseudo identities. The receiver selects a random vector λ¯=λ1,λ2,…,λn′, where λi∈0,1l, l is usually 80 [24].(3)
The receiver computesfi=H3PIDi‖Kpub and hi=H4Mi‖PIDi‖Ti and inspects whether the equation (3) holds. If it holds, the receiver accepts these n′ messages.(3)∑i=1n′λiδiP=∑i=1n′λifiKpub+∑i=1n′λiPIDi1+∑i=1n′λihiRi.The correctness of equation (3) is as follows:(4)∑i=1n′λiδiP=∑i=1n′λipskVi+rihiP,=∑i=1n′λifik+μi+rihiP,=∑i=1n′λifiKpub+∑i=1n′λiPIDi1+∑i=1n′λihiRi.


## 4.1. System Initialization

This phase is performed by TA and KGC to generate the initial system parameters along with their public and private key pairs using the following steps:(1)
TA chooses two large primesp and q. TA selects elliptic curve additive group G of order q, which is defined by E:y2=x3+ax+bmodp, where a,b∈Fp and 4a3+27b2modp≠0. P is a generator of the group G.(2)
TA randomly selectss∈Zq∗ as its master key and computes Ppub=sP as the corresponding public key.(3)
KGC randomly selectsk∈Zq∗ as its master private key and computes Kpub=kP as the corresponding public key.(4)
TA chooses four one-way cryptographic hash functionsH1:G⟶Zq∗, H2:0,1∗⟶Zq∗,H3:0,1∗⟶Zq∗, H4:0,1∗⟶Zq∗.(5)
Finally, TA and KGC broadcast public parametersparams=p,q,E,P,G,Ppub,Kpub,H1,H2,H3,H4.


## 4.2. Vehicle Registration

In this stage, TA communicates with the vehicleVi in a secure channel. The following steps will be performed:(1)
Vi first sends its real identity RIDi to TA, which contains the real information of the user, such as the ID number of the vehicle owner, the license plate number, and vehicle identification number.(2)
TA computesαi=H1RIDi and stores the pair RIDi,αi. Then TA marks Vi as a registered vehicle and sends αi to Vi via the secure channel.


## 4.3. Vehicle Partial Key and Pseudo Identity Generation

In order to protect the privacy of the vehicle, anonymous communication is necessary. On the other hand, the TA is asked to be able to reveal the real identity of the vehicle if necessary. Hence, this privacy is conditional. To this end, a pseudo identity is generated for each registered vehicleVi along with the partial private key by KGC interaction with the vehicle through a secure channel before signing a message. This phase consists of the following steps:(1)
Vi sends αi to KGC via the secure channel.(2)
KGC checks whetherαi exists in the registered vehicle list obtained from TA via the secure channel. If it does not exist, KGC terminates. Otherwise, KGC generates Vi’s partial private key and pseudo identity by steps (3) and (4).(3)
KGC randomly choosesμi∈Zq∗ and computes PIDi1=μiP and PIDi2=αi⊕H2μiPpub‖TVi. Let Vi’s pseudo identity as PIDi=PIDi1,PIDi2,TVi, where TVi is the validity period of PIDi.(4)
Then, KGC computesVi’s partial private key as pskVi=fik+μi, where fi=H3PIDi‖Kpub.(5)
Finally, KGC sendspskVi,PIDi to Vi via the secure channel. Vi stores pskVi,PIDi in its TPD.This phase is also shown in Figure3.Figure 3
Vehicle partial key and pseudo-identity generation.


## 4.4. Vehicle Key Generation and Message Signature

To ensure the integrity and validity of the messageMi, the vehicle signs the message Mi before broadcasting it.(1)
Vi randomly selects ri∈Zq∗ as its private key and computes Ri=riP.(2)
Vi computes hi=H4Mi‖PIDi‖Ti, where Ti is the current timestamp. Then Vi generates the signature σi=δi,Ri, where δi=pskVi+rihi. Finally, Vi broadcasts the message-signature tuple Mi,PIDi,σi,Ti to the vicinal RSUs and other vehicles.


## 4.5. Signature Verification

When the RSU and other vehicles receive the message broadcasted by the vehicleVi, the validity of the message is verified through the following steps:(1)
The receiver first validatesTVi of PIDi and then checks the validity of the timestamp Ti. If Ti′−Ti>ΔT, the receiver discards this message, where Ti′ is the time when the receiver receives the message and ΔT represents the difference between the clock of the vehicle Vi and the local clock. Otherwise, the receiver continues to do the next verification.(2)
The receiver computesfi=H3PIDi‖Kpub and hi=H4Mi‖PIDi‖Ti and checks whether equation (1) holds or not. If it holds, the receiver accepts the message. Otherwise, the receiver discards it.(1)δiP=fiKpub+PIDi1+hiRi.The correctness of equation (1) is proved as follows:(2)δiP=pskVi+rihiP,=fik+μi+rihiP,=fiKpub+PIDi1+hiRi.


## 4.6. Batch Verification

A vehicle may broadcast or receive multiple messages at the same time, especially in traffic-extensive areas. If the receiver verifies the messages one by one, it may cause redundant computation and a relatively long delay. In our scheme, efficient batch verification is developed, which is shown as follows:(1)
Supposen messages-signature tuples M1,PID1,σ1,T1,M2,PID2,σ2,T2,…,Mn,PIDn,σn,Tn are received. The receiver first checks the freshness of the timestamp Ti for message Mi and Tvi. If Ti or Tvi has expired, it rejects this message Mi. Otherwise, it performs the next verification.(2)
Letσii=1,…,n′ be the list of signatures that are freshly generated having valid pseudo identities. The receiver selects a random vector λ¯=λ1,λ2,…,λn′, where λi∈0,1l, l is usually 80 [24].(3)
The receiver computesfi=H3PIDi‖Kpub and hi=H4Mi‖PIDi‖Ti and inspects whether the equation (3) holds. If it holds, the receiver accepts these n′ messages.(3)∑i=1n′λiδiP=∑i=1n′λifiKpub+∑i=1n′λiPIDi1+∑i=1n′λihiRi.The correctness of equation (3) is as follows:(4)∑i=1n′λiδiP=∑i=1n′λipskVi+rihiP,=∑i=1n′λifik+μi+rihiP,=∑i=1n′λifiKpub+∑i=1n′λiPIDi1+∑i=1n′λihiRi.


## 5. Security Proof and Analysis

In this section, the security proof and analysis of our scheme proposed in Section4 are given.


### 5.1. Security Proof

This subsection shows the provable security of our new scheme by using random oracle models under the Type-I (with Game I) adversaryA1 and the Type-II (with Game II) adversary A2 as shown in Section 3.2.Theorem 1.
If a polynomial adversaryA1 can forge a valid signature by querying random oracles H3_query, H4_query, and Sign_query, then there exists a simulation algorithm Γ1 that solves the ECDLP problem with non-negligible advantage.Proof.
Suppose a polynomial adversaryA1 can crack the proposed scheme with a non-negligible probability ε > 0. Our goal is to produce an algorithm Γ1 that can use the adversary’s ability to solve the ECDLP problem with non-negligible probability. That is, Γ1 is able to compute k given two points P, Q=kP∈G. For this, Γ1 takes PID∗ as the target identity of A1 on a message M. The specific process is as follows:Setup phase: AlgorithmΓ1 sets Kpub=Q=kP and initializes system parameters params=p,q,E,P,G,Ppub,Kpub,H1⋅,H2⋅,H3⋅,H4⋅, and then Γ1 forwards params to the adversary A1 and keeps k secretly. Γ1 also maintains the lists H3list and H4list, which are initially empty.H3_query: When the adversary A1 makes H3_query query on PIDi, Γ1 checks the list H3list for PIDi,fi. If such tuple exists, Γ1 returns fi to A1. Otherwise, Γ1 randomly chooses fi∈Zq∗ and returns fi to A1. Γ1 adds the tuple PIDi,fi to H3list.H4_query: When the adversary A1 makes H4_query query on PIDi,Mi, Γ1 checks the list H4list for PIDi,Mi,hi. If such tuple exists, Γ1 returns hi to A1. Otherwise, Γ1 randomly chooses hi∈Zq∗ and returns hi to A1. Γ1 adds the tuple PIDi,Mi,hi to H4list.Sign_query: WhenA1 queries the Sign_query oracle using PIDi,Mi. If PIDi≠PID∗, Γ1 aborts the process. If PIDi=PID∗, Γ1 queries H3_query and H4_query oracles to obtain the tuples PIDi,fi and PIDi,Mi,hi, respectively. Γ1 randomly chooses δi,ri∈Zq∗ and computes Ri=riP and PIDi1=δiP−fiKpub−hiRi, let σi=δi,Ri. Next, Γ1 sends σi=δi,Ri,PIDi to A1. The signature σi=δi,Ri is valid because σi satisfies equation (1) as follows:(5)δiP=fiKpub+PIDi1+hiRi,=fiKpub+δiP−fiKpub−hiRi+hiRi,=δiP.Forgery:A1 makes Sign_query query on PIDi,Mi to get the valid signature σi=δi,Ri. By applying the forking lemma [33], when PIDi∗=PIDi, Γ1 can obtain another valid signature σi∗=δi∗,Ri if it chooses different values in H3_query random oracle with fi∗ by performing the same steps. Likewise, the signature is able to satisfy(6)δi∗P=fi∗Kpub+PIDi1+hiRi.
According to equations (5) and (6), we can deduce(7)δi−δi∗P=fi−fi∗kP.
Then by equation (7), the discrete logarithm can be computed k=δi−δi∗/fi−fi∗. Therefore, Γ1 solves the ECDLP problem by outputting k.
The probability thatΓ1 resolves the ECDLP problem can be induced through the following events:(1)
A1 can forge a valid signature(2)
There exists the casePIDi∗=PIDi in the valid signature forged by A1(3)
When the adversaryA1 makes H3_query on identity PIDi∗=PIDi, challenger Γ1 returns fi∗≠fi
Letqs denotes the number of querying Sign_query oracle. So the probability that Γ1 solves the ECDLP problem is at least 1/qs1−1/qsqs−1ε. And for large qs, this probability turns to ε/eqs, where e is the base of the natural logarithm. As a result, given the two points P,Q=kP∈G, Γ1 can resolve the ECDLP problem with a non-negligible probability ε/eqs, which causes a contradiction with the ECDLP assumption.Theorem 2.
If a polynomial adversaryA2 can forge a valid signature by querying random oracles H3_query, H4_query, Extract_query, and Sign_query, then there exists a simulation algorithm Γ2 that solves the ECDLP problem with non-negligible advantage.Proof.
Suppose a polynomial adversaryA2 can crack the proposed scheme with a non-negligible probability ε > 0. Our goal is to produce an algorithm Γ2 that can use the adversary’s ability to solve the ECDLP problem with non-negligible probability. That is, Γ2 is able to compute x given two points P and Q=xP∈G. For this, Γ2 takes PID∗ as the target identity of A2 on a message M. The specific process is as follows:Setup phase: AlgorithmΓ2 chooses k∈Zq∗, computes Kpub=kP, and initializes system parameters params=p,q,E,P,G,Ppub,Kpub,H1⋅,H2⋅,H3⋅,H4⋅, and then Γ2 forwards params and secret key k to the adversary A2. Γ2 also maintains the lists H3list, H4list, and Exlist, which are initially empty.H3_query: When the adversary A2 makes H3_query query on PIDi, Γ2 checks the list H3list for PIDi,fi. If such tuple exists, Γ2 returns fi to A2. Otherwise, Γ2 randomly chooses fi∈Zq∗ and returns fi to A2. Γ2 adds the tuple PIDi,fi to H3list.H4_query: When the adversary A2 makes H4_query query on PIDi,Mi, Γ2 checks the list H4list for PIDi,Mi,hi. If such tuple exists, Γ2 returns hi to A2. Otherwise, Γ2 randomly chooses hi∈Zq∗ and returns hi to A2. Γ2 adds the tuple PIDi,Mi,hi to H4list.Extract_query: WhenA2 queries Extract_query for PIDi1 and the partial private key pskVi using PIDi, Γ2 inspects whether the tuple PIDi,PIDi1,pskVi exists in the list Exlist. If such tuple exists, Γ2 forwards PIDi1 and pskVi to A2. Otherwise, if PIDi≠PID∗, Γ2 makes H3_query query to get the tuple PIDi,fi, then Γ2 randomly chooses μi and computes PIDi1=μiP and pskVi=fik+μi. Then Γ2 returns PIDi1 and pskVi to A2 and adds PIDi,PIDi1,pskVi to the list Exlist. If PIDi=PID∗, Γ2 aborts the process.Sign_query: WhenA2 uses PIDi,Mi to query the Sign_query oracle, if PIDi≠PID∗, Γ2 queries H4_query and Extract_query oracles to obtain the tuple PIDi,Mi,hi and PIDi,PIDi1,pskVi, respectively. Γ2 chooses a random number ri∈Zq∗ and computes Ri=riP and δi=pskVi+rihi. Next, Γ2 sends the signature σi=δi,Ri to A2. If PIDi=PID∗, Γ2 queries H3_query and H4_query oracles to obtain the tuples PIDi,fi and PIDi,Mi,hi, respectively. Γ2 randomly chooses δi∈Zq∗ and computes Ri=Q and PIDi1=δiP−fiKpub−hiRi; let σi=δi,Ri. Next, Γ2 sends σi=δi,Ri,PIDi to A2. The signature σi=δi,Ri is valid because σi satisfies equation (1) as follows:(8)δiP=fiKpub+PIDi1+hiRi=fiKpub+δiP−fiKpub−hiRi+hiRi=δiPForgery:A2 makes Sign_query query on PIDi,Mi to get the valid signature σi=δi,Ri. By applying the forking lemma [33], when PIDi∗=PIDi, Γ2 can obtain another valid signature σi∗=δi∗,Ri if it chooses different values in H4_query random oracle with hi∗ by performing the same steps. Likewise, the signature is able to satisfy(9)δi∗P=fiKpub+PIDi1+hi∗Ri.
According to equations (8) and (9), we can deduce(10)δi−δi∗P=hi−hi∗xP.
Then by equation (10), the discrete logarithm can be computed x=δi−δi∗/hi−hi∗. Therefore, Γ2 solves the ECDLP problem by outputting x.
The probability thatΓ2 resolves the ECDLP problem can be induced through the following events:(1)
A2 can forge a valid signature(2)
There exists the casePIDi∗=PIDi in the valid signature forged by A2(3)
When the adversaryA2 makes H4_query on identity PIDi∗=PIDi, challenger Γ2 returns hi∗≠hi
LetqE denotes the number of querying Extract_query oracle. So the probability that Γ2 solves the ECDLP problem is at least 1/qE1−1/qEqE−1ε. And for large qE, this probability turns to ε/eqE, where e is the base of the natural logarithm. As a result, given the two points P,Q=xP∈G, Γ2 can resolve the ECDLP problem with a non-negligible probability ε/eqE, which causes a contradiction with the ECDLP assumption.According to Definition 1 defined in Section3.2, we can see, from the above two theorems, that our authentication scheme is existentially unforgeable (i.e., provably secure).


### 5.2. Security Analysis

In this subsection, the security analysis of the scheme proposed in Section4 is discussed, which is similar to [16, 17, 21–23].(1)
Message authentication and integrity: When receiving message tupleMi,PIDi,σi,Ti, the receiver can verify message Mi through equation (1). Note that hi=H4Mi‖PIDi‖Ti will change if the message Mi is modified, which will cause a failure of verification in equation (1). As a result, the proposed scheme can guarantee message authentication and integrity.(2)
Conditional privacy-preserving or traceability: Given the vehicle’s pseudo identityPIDi=PIDi1,PIDi2,TVi, where PIDi1=μiP and PIDi2=αi⊕H2μiPpub‖TVi, the pseudo identity of the vehicle does not contain the real information, so the attacker cannot obtain any real information from the vehicle’s pseudo identity. However, once a legitimate vehicle deliberately spreads false information, TA can recover the real identity of the vehicle by computing αi=PIDi2⊕H2sPIDi1‖TVi and use αi to query the data list to get the tuple RIDi,αi. Then TA adds RIDi to the revocation list.(3)
Unthinkability: In the proposed scheme, the vehicle’s pseudo identity isPIDi=PIDi1,PIDi2,TVi, where PIDi1=μiP and PIDi2=αi⊕H2μiPpub‖TVi, and the signature is δi=pskVi+rihi. Given the randomness of μi and ri, it is impossible for an adversary to link any two pseudo identities PIDi and PIDj, or any two messages Mi and Mi′ sent from the same vehicle Vi.(4)
Resistance to impersonation attack: According to Theorem 1, it is known that an attacker cannot impersonate other legitimate vehicles to generate a signature that satisfies equation (1). Hence, the proposed scheme can resist the impersonation attack.(5)
Resistance to message modification attack: In the signing phase, the vehicleVi generates the signature δi=pskVi+rihi, where hi=H4Mi‖PIDi‖Ti involves the hash value of the traffic-related message Mi. Once Mi is maliciously modified, the hash value hi changes, thereby resulting in the failure of the verification of equation (1). Therefore, the proposed scheme can withstand the modification attack.(6)
Resistance to side-channel attack: In our scheme, the partial private keypskVi and the pseudo identity PIDi=PIDi1,PIDi2,TVi of the vehicle is stored in its TPD, where TVi is the validity period of PIDi. When the vehicle’s pseudo identity expires, the vehicle needs to reapply for a pseudo identity. KGC randomly chooses a new value μi′, computes a new pseudo identity PIDi′=PIDi1′,PIDi2′,TVi′ and a new partial private key pskVi′, where TVi is the validity period of the new pseudo identity. Regular updates of the pseudo identity and the partial private key can effectively resist side-channel attacks.(7)
Resistance to replay attack: TimestampTi is involved in the message-signature tuple Mi,PIDi,σi,Ti, where the signature is σi=δi,Ri, δi=pskVi+rihi, and hi=H4Mi‖PIDi‖Ti. Hence, the receiver can detect whether the message Mi has expired by verifying the freshness of Ti. Accordingly, the proposed scheme is able to withstand the replay attack.


### 5.3. Simulation Result Analysis

In this subsection, we use the popular AVISPA tool to simulate the proposed scheme, and the simulation results are shown in Figure4. The parts in the output format are as follows:(1)
SUMMARY: This part indicates whether the scheme is secure (safe or unsafe) or if the analysis was inconclusive(2)
DETAILS: This part provides information on the conditions in which the scheme is safe or the attack determining conditions or finally, why the analysis was inconclusive(3)
PROTOCOL: This defines the “HLPSL specification of the target protocol in IF”(4)
GOAL: It is the goal of the analysis performed by AVISPA using the HLPSL specification(5)BACKEND: It is the name of the backend used for analysis(6)
STATISTICS: This is to track possible loopholes of the target protocol and statistics of some related dataThe proposed scheme is simulated for formal security verification using the OFMC and CL-AtSe backends under the SPAN, the security protocol for AVISPA [34]. From Figure 4, it is clear that our scheme has passed the executability checking on non-trivial HLPSL specifications, replay attack checking, and Dolev–Yao model checking verifications [35]. Hence, our scheme is secure against replay and man-in-the-middle attacks.Figure 4
Analysis of simulation results under OFMC and CL-AtSe backends.


## 5.1. Security Proof

This subsection shows the provable security of our new scheme by using random oracle models under the Type-I (with Game I) adversaryA1 and the Type-II (with Game II) adversary A2 as shown in Section 3.2.Theorem 1.
If a polynomial adversaryA1 can forge a valid signature by querying random oracles H3_query, H4_query, and Sign_query, then there exists a simulation algorithm Γ1 that solves the ECDLP problem with non-negligible advantage.Proof.
Suppose a polynomial adversaryA1 can crack the proposed scheme with a non-negligible probability ε > 0. Our goal is to produce an algorithm Γ1 that can use the adversary’s ability to solve the ECDLP problem with non-negligible probability. That is, Γ1 is able to compute k given two points P, Q=kP∈G. For this, Γ1 takes PID∗ as the target identity of A1 on a message M. The specific process is as follows:Setup phase: AlgorithmΓ1 sets Kpub=Q=kP and initializes system parameters params=p,q,E,P,G,Ppub,Kpub,H1⋅,H2⋅,H3⋅,H4⋅, and then Γ1 forwards params to the adversary A1 and keeps k secretly. Γ1 also maintains the lists H3list and H4list, which are initially empty.H3_query: When the adversary A1 makes H3_query query on PIDi, Γ1 checks the list H3list for PIDi,fi. If such tuple exists, Γ1 returns fi to A1. Otherwise, Γ1 randomly chooses fi∈Zq∗ and returns fi to A1. Γ1 adds the tuple PIDi,fi to H3list.H4_query: When the adversary A1 makes H4_query query on PIDi,Mi, Γ1 checks the list H4list for PIDi,Mi,hi. If such tuple exists, Γ1 returns hi to A1. Otherwise, Γ1 randomly chooses hi∈Zq∗ and returns hi to A1. Γ1 adds the tuple PIDi,Mi,hi to H4list.Sign_query: WhenA1 queries the Sign_query oracle using PIDi,Mi. If PIDi≠PID∗, Γ1 aborts the process. If PIDi=PID∗, Γ1 queries H3_query and H4_query oracles to obtain the tuples PIDi,fi and PIDi,Mi,hi, respectively. Γ1 randomly chooses δi,ri∈Zq∗ and computes Ri=riP and PIDi1=δiP−fiKpub−hiRi, let σi=δi,Ri. Next, Γ1 sends σi=δi,Ri,PIDi to A1. The signature σi=δi,Ri is valid because σi satisfies equation (1) as follows:(5)δiP=fiKpub+PIDi1+hiRi,=fiKpub+δiP−fiKpub−hiRi+hiRi,=δiP.Forgery:A1 makes Sign_query query on PIDi,Mi to get the valid signature σi=δi,Ri. By applying the forking lemma [33], when PIDi∗=PIDi, Γ1 can obtain another valid signature σi∗=δi∗,Ri if it chooses different values in H3_query random oracle with fi∗ by performing the same steps. Likewise, the signature is able to satisfy(6)δi∗P=fi∗Kpub+PIDi1+hiRi.
According to equations (5) and (6), we can deduce(7)δi−δi∗P=fi−fi∗kP.
Then by equation (7), the discrete logarithm can be computed k=δi−δi∗/fi−fi∗. Therefore, Γ1 solves the ECDLP problem by outputting k.
The probability thatΓ1 resolves the ECDLP problem can be induced through the following events:(1)
A1 can forge a valid signature(2)
There exists the casePIDi∗=PIDi in the valid signature forged by A1(3)
When the adversaryA1 makes H3_query on identity PIDi∗=PIDi, challenger Γ1 returns fi∗≠fi
Letqs denotes the number of querying Sign_query oracle. So the probability that Γ1 solves the ECDLP problem is at least 1/qs1−1/qsqs−1ε. And for large qs, this probability turns to ε/eqs, where e is the base of the natural logarithm. As a result, given the two points P,Q=kP∈G, Γ1 can resolve the ECDLP problem with a non-negligible probability ε/eqs, which causes a contradiction with the ECDLP assumption.Theorem 2.
If a polynomial adversaryA2 can forge a valid signature by querying random oracles H3_query, H4_query, Extract_query, and Sign_query, then there exists a simulation algorithm Γ2 that solves the ECDLP problem with non-negligible advantage.Proof.
Suppose a polynomial adversaryA2 can crack the proposed scheme with a non-negligible probability ε > 0. Our goal is to produce an algorithm Γ2 that can use the adversary’s ability to solve the ECDLP problem with non-negligible probability. That is, Γ2 is able to compute x given two points P and Q=xP∈G. For this, Γ2 takes PID∗ as the target identity of A2 on a message M. The specific process is as follows:Setup phase: AlgorithmΓ2 chooses k∈Zq∗, computes Kpub=kP, and initializes system parameters params=p,q,E,P,G,Ppub,Kpub,H1⋅,H2⋅,H3⋅,H4⋅, and then Γ2 forwards params and secret key k to the adversary A2. Γ2 also maintains the lists H3list, H4list, and Exlist, which are initially empty.H3_query: When the adversary A2 makes H3_query query on PIDi, Γ2 checks the list H3list for PIDi,fi. If such tuple exists, Γ2 returns fi to A2. Otherwise, Γ2 randomly chooses fi∈Zq∗ and returns fi to A2. Γ2 adds the tuple PIDi,fi to H3list.H4_query: When the adversary A2 makes H4_query query on PIDi,Mi, Γ2 checks the list H4list for PIDi,Mi,hi. If such tuple exists, Γ2 returns hi to A2. Otherwise, Γ2 randomly chooses hi∈Zq∗ and returns hi to A2. Γ2 adds the tuple PIDi,Mi,hi to H4list.Extract_query: WhenA2 queries Extract_query for PIDi1 and the partial private key pskVi using PIDi, Γ2 inspects whether the tuple PIDi,PIDi1,pskVi exists in the list Exlist. If such tuple exists, Γ2 forwards PIDi1 and pskVi to A2. Otherwise, if PIDi≠PID∗, Γ2 makes H3_query query to get the tuple PIDi,fi, then Γ2 randomly chooses μi and computes PIDi1=μiP and pskVi=fik+μi. Then Γ2 returns PIDi1 and pskVi to A2 and adds PIDi,PIDi1,pskVi to the list Exlist. If PIDi=PID∗, Γ2 aborts the process.Sign_query: WhenA2 uses PIDi,Mi to query the Sign_query oracle, if PIDi≠PID∗, Γ2 queries H4_query and Extract_query oracles to obtain the tuple PIDi,Mi,hi and PIDi,PIDi1,pskVi, respectively. Γ2 chooses a random number ri∈Zq∗ and computes Ri=riP and δi=pskVi+rihi. Next, Γ2 sends the signature σi=δi,Ri to A2. If PIDi=PID∗, Γ2 queries H3_query and H4_query oracles to obtain the tuples PIDi,fi and PIDi,Mi,hi, respectively. Γ2 randomly chooses δi∈Zq∗ and computes Ri=Q and PIDi1=δiP−fiKpub−hiRi; let σi=δi,Ri. Next, Γ2 sends σi=δi,Ri,PIDi to A2. The signature σi=δi,Ri is valid because σi satisfies equation (1) as follows:(8)δiP=fiKpub+PIDi1+hiRi=fiKpub+δiP−fiKpub−hiRi+hiRi=δiPForgery:A2 makes Sign_query query on PIDi,Mi to get the valid signature σi=δi,Ri. By applying the forking lemma [33], when PIDi∗=PIDi, Γ2 can obtain another valid signature σi∗=δi∗,Ri if it chooses different values in H4_query random oracle with hi∗ by performing the same steps. Likewise, the signature is able to satisfy(9)δi∗P=fiKpub+PIDi1+hi∗Ri.
According to equations (8) and (9), we can deduce(10)δi−δi∗P=hi−hi∗xP.
Then by equation (10), the discrete logarithm can be computed x=δi−δi∗/hi−hi∗. Therefore, Γ2 solves the ECDLP problem by outputting x.
The probability thatΓ2 resolves the ECDLP problem can be induced through the following events:(1)
A2 can forge a valid signature(2)
There exists the casePIDi∗=PIDi in the valid signature forged by A2(3)
When the adversaryA2 makes H4_query on identity PIDi∗=PIDi, challenger Γ2 returns hi∗≠hi
LetqE denotes the number of querying Extract_query oracle. So the probability that Γ2 solves the ECDLP problem is at least 1/qE1−1/qEqE−1ε. And for large qE, this probability turns to ε/eqE, where e is the base of the natural logarithm. As a result, given the two points P,Q=xP∈G, Γ2 can resolve the ECDLP problem with a non-negligible probability ε/eqE, which causes a contradiction with the ECDLP assumption.According to Definition 1 defined in Section3.2, we can see, from the above two theorems, that our authentication scheme is existentially unforgeable (i.e., provably secure).


## 5.2. Security Analysis

In this subsection, the security analysis of the scheme proposed in Section4 is discussed, which is similar to [16, 17, 21–23].(1)
Message authentication and integrity: When receiving message tupleMi,PIDi,σi,Ti, the receiver can verify message Mi through equation (1). Note that hi=H4Mi‖PIDi‖Ti will change if the message Mi is modified, which will cause a failure of verification in equation (1). As a result, the proposed scheme can guarantee message authentication and integrity.(2)
Conditional privacy-preserving or traceability: Given the vehicle’s pseudo identityPIDi=PIDi1,PIDi2,TVi, where PIDi1=μiP and PIDi2=αi⊕H2μiPpub‖TVi, the pseudo identity of the vehicle does not contain the real information, so the attacker cannot obtain any real information from the vehicle’s pseudo identity. However, once a legitimate vehicle deliberately spreads false information, TA can recover the real identity of the vehicle by computing αi=PIDi2⊕H2sPIDi1‖TVi and use αi to query the data list to get the tuple RIDi,αi. Then TA adds RIDi to the revocation list.(3)
Unthinkability: In the proposed scheme, the vehicle’s pseudo identity isPIDi=PIDi1,PIDi2,TVi, where PIDi1=μiP and PIDi2=αi⊕H2μiPpub‖TVi, and the signature is δi=pskVi+rihi. Given the randomness of μi and ri, it is impossible for an adversary to link any two pseudo identities PIDi and PIDj, or any two messages Mi and Mi′ sent from the same vehicle Vi.(4)
Resistance to impersonation attack: According to Theorem 1, it is known that an attacker cannot impersonate other legitimate vehicles to generate a signature that satisfies equation (1). Hence, the proposed scheme can resist the impersonation attack.(5)
Resistance to message modification attack: In the signing phase, the vehicleVi generates the signature δi=pskVi+rihi, where hi=H4Mi‖PIDi‖Ti involves the hash value of the traffic-related message Mi. Once Mi is maliciously modified, the hash value hi changes, thereby resulting in the failure of the verification of equation (1). Therefore, the proposed scheme can withstand the modification attack.(6)
Resistance to side-channel attack: In our scheme, the partial private keypskVi and the pseudo identity PIDi=PIDi1,PIDi2,TVi of the vehicle is stored in its TPD, where TVi is the validity period of PIDi. When the vehicle’s pseudo identity expires, the vehicle needs to reapply for a pseudo identity. KGC randomly chooses a new value μi′, computes a new pseudo identity PIDi′=PIDi1′,PIDi2′,TVi′ and a new partial private key pskVi′, where TVi is the validity period of the new pseudo identity. Regular updates of the pseudo identity and the partial private key can effectively resist side-channel attacks.(7)
Resistance to replay attack: TimestampTi is involved in the message-signature tuple Mi,PIDi,σi,Ti, where the signature is σi=δi,Ri, δi=pskVi+rihi, and hi=H4Mi‖PIDi‖Ti. Hence, the receiver can detect whether the message Mi has expired by verifying the freshness of Ti. Accordingly, the proposed scheme is able to withstand the replay attack.


## 5.3. Simulation Result Analysis

In this subsection, we use the popular AVISPA tool to simulate the proposed scheme, and the simulation results are shown in Figure4. The parts in the output format are as follows:(1)
SUMMARY: This part indicates whether the scheme is secure (safe or unsafe) or if the analysis was inconclusive(2)
DETAILS: This part provides information on the conditions in which the scheme is safe or the attack determining conditions or finally, why the analysis was inconclusive(3)
PROTOCOL: This defines the “HLPSL specification of the target protocol in IF”(4)
GOAL: It is the goal of the analysis performed by AVISPA using the HLPSL specification(5)BACKEND: It is the name of the backend used for analysis(6)
STATISTICS: This is to track possible loopholes of the target protocol and statistics of some related dataThe proposed scheme is simulated for formal security verification using the OFMC and CL-AtSe backends under the SPAN, the security protocol for AVISPA [34]. From Figure 4, it is clear that our scheme has passed the executability checking on non-trivial HLPSL specifications, replay attack checking, and Dolev–Yao model checking verifications [35]. Hence, our scheme is secure against replay and man-in-the-middle attacks.Figure 4
Analysis of simulation results under OFMC and CL-AtSe backends.


## 6. Performance Analysis

In this section, we evaluate our scheme from the aspects of computation, communication, storage costs, and security performance by a comprehensive comparison with the state-of-the-art schemes proposed by Gayathri et al. [20] in 2018, Sutrala et al. [21] in 2020, and Mei et al. [17] in 2021. Among these three schemes, Mei et al.’s scheme uses bilinear pairings, while the other two schemes are pairing-free.


### 6.1. Computation Cost

The symbols used in the calculation and comparison with other schemes are listed below:(1)
Tbp: The execution time of bilinear pairing operation e:G1×G1⟶GT(2)
Tpm: The execution time of the scale multiplication in G1(3)
Tpa: The execution time of a point addition operation in G1(4)
Tem: The execution time of the scale multiplication operation kP in the elliptic curve, where k∈Zq∗, P∈G(5)
Tea: The execution time of the addition operation P+Q in the elliptic curve, where P,Q∈G(6)
TH: The execution time of a map-to-point hash function operation(7)
Th: The execution time of a one-way hash function operationIn order to evaluate the time cost of the above cryptographic operations, we choose a Type A pairing that uses Java pairing-based cryptography (JPBC) library [36]. It is executed on a Dell desktop computer with the operating system being Windows 10 and the processor being CPU i7-9700, 8 GB RAM. We use the average time of 1,000 executions of the algorithm. The execution times of the above cryptographic operations are shown in Table 3.Table 3
The cryptographic operations and execution times.
Cryptographic operationAbbr.TimemsOperations related to bilinear pairingTbp19.9421Tpm7.7849Tpa0.0405Operations related to ECCTem8.0940Tea0.0372Map-to-point hash functionTH17.1117One-way hash functionTh0.0022In this paper, we adopt a similar evaluation method of computation costs as proposed in reference [37]. Let PKM, SMV, and BMV, respectively, represent the phase of pseudo identity generation, private key generation and message-signature generation, the phase of single message verification, and the phase of batch message verification. We only consider the vehicle’s calculation time because the OBU’s computing power is limited.In our scheme, the vehicle needs to perform one multiplication operation and one one-way hash function operation in the PKM stage, which requiresTem+Th=8.0962 ms in time. In the SMV stage, three multiplication operations, two addition operations, and two one-way hash function operations are needed to be performed, which requires 3Tem+2Tea+2Th=24.3608 ms in time. In the BMV stage, 2n+2 multiplication operations, 2n addition operations, and 2n one-way hash function operations are needed to be performed when n messages are verified at one time, which requires 2n+2Tem+2nTea+2nTh=16.2668n+16.188 ms in time. The above computation costs of our scheme are also shown in Table 4. For comparison, we also present the computation costs of those schemes proposed by Gayathri et al. [20], Sutrala et al. [21], and Mei et al. [17] in Table 4. According to the conclusion put forward by Liu et al. [24], in Mei et al.’s scheme, n messages are authenticated at a time by checking the equation eP,∑i=1nλiTi=eMPK,∑i=1nλihiQie∑i=1nλihivepki,Ise∑i=1nλiUi,Js, where λ¯=λ1,λ2,…,λn is a random vector as defined in Section 4.6. The computation cost is 4nTem+4n−4Tea+nTh+4Tbp+2TH=32.527n+113.843 ms in time.Table 4
Comparison of computation cost.
SchemePKMSMVBMVGayathri et al. [20]3Tem+3Th=24.2886 ms5Tem+3Tea+3Th=40.5882 ms3n+2Tem+3nTea+3nTh=24.4002n+16.188msSutrala et al. [21]6Tem+3Th=48.5706 ms3Tem+2Tea+2Th=24.3608 ms3n+1Tem+3n−1Tea+2nTh=24.398n+8.0568msMei et al. [17]6Tem+2Tea+2TH+Th=82.864 ms4Tbp+2Tem+2TH+Th=130.182 ms4nTem+4n−4Tea+nTh+4Tbp+2TH=32.527n+113.843msOurTem+Th=8.0962 ms3Tem+2Tea+2Th=24.3608 ms2n+2Tem+2nTea+2nTh=16.2668n+16.188msThe percentage improvements of our scheme with respect to the related schemes are listed in Table7. For instance, it has the improvement of 24.2886−8.0962/24.2886≈66.67%, 40.5882−24.3608/40.5882≈39.98%, and 24.4002n+16.188−16.2668n+16.188/24.4002n+16.188≈33.11% in the PKM, SMV, and BMV phases, respectively, over the Gayathri et al.’s scheme, where n=100 is the number of signatures. The percentage improvements in the PKM, SMV, and BMV phases over other related schemes can be calculated in a similar manner and are also shown in Table 5. From Table 5, it can be clearly seen that our scheme outperforms much better than these three schemes in terms of computational efficiency.Table 5
Percentage improvements of our scheme with respect to the related schemes.
SchemePKMSMVBMVGayathri et al. [20]66.67%39.98%33.11%Sutrala et al. [21]83.33%032.89%Mei et al. [17]70.69%81.29%51.20%The computation costs in the PKM and SMV stages of different schemes are also represented graphically in Figure5. From Figure 5, we can see easily that in the PKM and SMV phase, our scheme is much more efficient than Gayathri et al.’s scheme, Sutrala et al.’s scheme, and Mei et al.’s scheme. The curves of computation costs in the BMV phase for different schemes for various numbers of messages are depicted in Figure 6, which shows that our scheme is much superior to the other three schemes in the BMV phase.Figure 5
Comparison of PKM and SMV computation costs.Figure 6
Comparison of BMV computation cost.


### 6.2. Communication Cost

In this subsection, we evaluate the communication costs of our scheme with that of Gayathri et al.’s scheme, Sutrala et al.’s scheme, and Mei et al.’s scheme. Since the security level provided by the 160 bit ECC is the same as that by the 1024 bit RSA public-key cryptosystem [25], 160 bit ECC is adopted for the comparison of communication costs. A point on the elliptic curve, usually denoted by Px,Py, is of length 320 bits or 40 bytes, while a point in the group over which a bilinear pairing is defined is of length 128 bytes. Then an element in Zq∗ is of length 20 bytes. Moreover, the timestamp is supposed to be of length 4 bytes.In our scheme, the vehicle sends a message-signature tupleMi,PIDi=PIDi1,PIDi2,TVi,σi=δi,Ri,Ti to the verifier, where PIDi1,Ri are two elements in the elliptic curve group G, PIDi2,δi are two elements in Zq∗, and TVi,Ti are two timestamps. So the communication cost is 2×40+2×20+2×4=128 bytes as shown in Table 6. Here, the cost of the message Mi does not included, which is a common means used in the communication cost comparison. Table 6 also shows us the communication costs of sending a single message-signature tuple by the vehicle in Gayathri et al.’s scheme, Sutra et al.’s scheme, and Mei et al.’s scheme, which are 228, 228, and 668 bytes, respectively. The communication costs for these schemes are also compared graphically in Figure 7. From Table 6 and Figure 7, it is clear that the communication cost of our scheme is significantly less than the other three schemes.Table 6
Comparison of communication cost.
SchemeMessageSending a single messageSendingn messageGayathri et al. [20]Mi,PIDi=PIDi1,PIDi2,TVi,Xi,σi=Ri,Y1i,μi,wi,Ti228 bytes228n bytesSutrala et al. [21]Mi,δi=fi,gi,Bi,Ki,Ri,PIDi=PIDi1,PIDi2,TVi,Ti228 bytes228n bytesMei et al. [17]Mi,ti,vepki,PIDi1,PIDi2,TVi,IDRs,sigi=Ui,Ti668 bytes668n bytesOurMi,PIDi=PIDi1,PIDi2,TVi,σi=δi,Ri,Ti128 bytes128n bytesFigure 7
Comparison of communication cost forn signatures.


### 6.3. Storage Cost

In this subsection, the comparison of the storage space required by the vehicle in the signature phase for different schemes is presented.In our scheme, the vehicleVi needs to store the secret αi, the pseudo identity PIDi=PIDi1,PIDi2,TVi, and the partial private key pskVi into its memory. So the required storage cost is 40+3×20+4=104 bytes as shown in Table 7. Also, shown in Table 7 are the storage costs required for Gayathri et al.’s scheme, Sutrala et al.’s scheme, and Mei et al.’s scheme, which are 184, 244, and 536 bytes, respectively. From Table 7, it can be clearly seen that the vehicle of our scheme has the smallest storage space compared with the other three schemes.Table 7
Comparison of storage cost.
SchemeStorage messageStorage costGayathri et al. [20]Xi,Ri,di,xi,PIDi=PIDi1,PIDi2,TVi184 bytesSutrala et al. [21]vti,ai,PIDi1,PIDi2,TVi,vpk1i,vpk3i,ki,Ri,Ki244 bytesMei et al. [17]PIDi1,PIDi2,TVi,pski,j,xi,vepki536 bytesOurPIDi1,PIDi2,TVi,αi,pskVi104 bytes


### 6.4. Security Comparison

In this subsection, we compare the various security and functionality features of our scheme with that of Gayathri et al.’s scheme, Sutrala et al.’s scheme, and Mei et al.’s scheme. LetSF1, SF2, SF3, SF4, SF5, SF6, SF7, and SF8 represent the goals of 1 message authentication and integrity, 2 identity privacy-preservation, 3 traceability, 4 unthinkability, 5 modification attack resistance, 6 impersonate attack resistance, 7 side-channel attack resistance, and 8 replay attack resistance, respectively. The comparison of security goals is indicated in Table 8. The symbol √ denotes that the security goal is satisfied, and the symbol × denotes that the security goal is unsatisfied.Table 8
Comparison of security.
SchemeSF1SF2SF3SF4SF5SF6SF7SF8Gayathri et al. [20]√√√√√××√Sutrala et al. [21]√√×√××√√Mei et al. [17]√√√√×√√√Our√√√√√√√√From Table8, it can be seen that our scheme provides all the mentioned necessary security features and is not vulnerable to any known attacks. In Gayathri et al.’s scheme, the vehicle can impersonate other vehicles through the pseudonym generated by itself, and a secure key update is not provided, so it is vulnerable to the impersonate attack and the side-channel attack. Sutrala et al.’s scheme is vulnerable to the modification attack and the impersonate attack, and TA cannot track the vehicle [28]. In Mei et al.’s scheme, the modification attack is possible [24]. Overall, compared with the existing related solutions in Table 8, our scheme provides a better security performance.


## 6.1. Computation Cost

The symbols used in the calculation and comparison with other schemes are listed below:(1)
Tbp: The execution time of bilinear pairing operation e:G1×G1⟶GT(2)
Tpm: The execution time of the scale multiplication in G1(3)
Tpa: The execution time of a point addition operation in G1(4)
Tem: The execution time of the scale multiplication operation kP in the elliptic curve, where k∈Zq∗, P∈G(5)
Tea: The execution time of the addition operation P+Q in the elliptic curve, where P,Q∈G(6)
TH: The execution time of a map-to-point hash function operation(7)
Th: The execution time of a one-way hash function operationIn order to evaluate the time cost of the above cryptographic operations, we choose a Type A pairing that uses Java pairing-based cryptography (JPBC) library [36]. It is executed on a Dell desktop computer with the operating system being Windows 10 and the processor being CPU i7-9700, 8 GB RAM. We use the average time of 1,000 executions of the algorithm. The execution times of the above cryptographic operations are shown in Table 3.Table 3
The cryptographic operations and execution times.
Cryptographic operationAbbr.TimemsOperations related to bilinear pairingTbp19.9421Tpm7.7849Tpa0.0405Operations related to ECCTem8.0940Tea0.0372Map-to-point hash functionTH17.1117One-way hash functionTh0.0022In this paper, we adopt a similar evaluation method of computation costs as proposed in reference [37]. Let PKM, SMV, and BMV, respectively, represent the phase of pseudo identity generation, private key generation and message-signature generation, the phase of single message verification, and the phase of batch message verification. We only consider the vehicle’s calculation time because the OBU’s computing power is limited.In our scheme, the vehicle needs to perform one multiplication operation and one one-way hash function operation in the PKM stage, which requiresTem+Th=8.0962 ms in time. In the SMV stage, three multiplication operations, two addition operations, and two one-way hash function operations are needed to be performed, which requires 3Tem+2Tea+2Th=24.3608 ms in time. In the BMV stage, 2n+2 multiplication operations, 2n addition operations, and 2n one-way hash function operations are needed to be performed when n messages are verified at one time, which requires 2n+2Tem+2nTea+2nTh=16.2668n+16.188 ms in time. The above computation costs of our scheme are also shown in Table 4. For comparison, we also present the computation costs of those schemes proposed by Gayathri et al. [20], Sutrala et al. [21], and Mei et al. [17] in Table 4. According to the conclusion put forward by Liu et al. [24], in Mei et al.’s scheme, n messages are authenticated at a time by checking the equation eP,∑i=1nλiTi=eMPK,∑i=1nλihiQie∑i=1nλihivepki,Ise∑i=1nλiUi,Js, where λ¯=λ1,λ2,…,λn is a random vector as defined in Section 4.6. The computation cost is 4nTem+4n−4Tea+nTh+4Tbp+2TH=32.527n+113.843 ms in time.Table 4
Comparison of computation cost.
SchemePKMSMVBMVGayathri et al. [20]3Tem+3Th=24.2886 ms5Tem+3Tea+3Th=40.5882 ms3n+2Tem+3nTea+3nTh=24.4002n+16.188msSutrala et al. [21]6Tem+3Th=48.5706 ms3Tem+2Tea+2Th=24.3608 ms3n+1Tem+3n−1Tea+2nTh=24.398n+8.0568msMei et al. [17]6Tem+2Tea+2TH+Th=82.864 ms4Tbp+2Tem+2TH+Th=130.182 ms4nTem+4n−4Tea+nTh+4Tbp+2TH=32.527n+113.843msOurTem+Th=8.0962 ms3Tem+2Tea+2Th=24.3608 ms2n+2Tem+2nTea+2nTh=16.2668n+16.188msThe percentage improvements of our scheme with respect to the related schemes are listed in Table7. For instance, it has the improvement of 24.2886−8.0962/24.2886≈66.67%, 40.5882−24.3608/40.5882≈39.98%, and 24.4002n+16.188−16.2668n+16.188/24.4002n+16.188≈33.11% in the PKM, SMV, and BMV phases, respectively, over the Gayathri et al.’s scheme, where n=100 is the number of signatures. The percentage improvements in the PKM, SMV, and BMV phases over other related schemes can be calculated in a similar manner and are also shown in Table 5. From Table 5, it can be clearly seen that our scheme outperforms much better than these three schemes in terms of computational efficiency.Table 5
Percentage improvements of our scheme with respect to the related schemes.
SchemePKMSMVBMVGayathri et al. [20]66.67%39.98%33.11%Sutrala et al. [21]83.33%032.89%Mei et al. [17]70.69%81.29%51.20%The computation costs in the PKM and SMV stages of different schemes are also represented graphically in Figure5. From Figure 5, we can see easily that in the PKM and SMV phase, our scheme is much more efficient than Gayathri et al.’s scheme, Sutrala et al.’s scheme, and Mei et al.’s scheme. The curves of computation costs in the BMV phase for different schemes for various numbers of messages are depicted in Figure 6, which shows that our scheme is much superior to the other three schemes in the BMV phase.Figure 5
Comparison of PKM and SMV computation costs.Figure 6
Comparison of BMV computation cost.


## 6.2. Communication Cost

In this subsection, we evaluate the communication costs of our scheme with that of Gayathri et al.’s scheme, Sutrala et al.’s scheme, and Mei et al.’s scheme. Since the security level provided by the 160 bit ECC is the same as that by the 1024 bit RSA public-key cryptosystem [25], 160 bit ECC is adopted for the comparison of communication costs. A point on the elliptic curve, usually denoted by Px,Py, is of length 320 bits or 40 bytes, while a point in the group over which a bilinear pairing is defined is of length 128 bytes. Then an element in Zq∗ is of length 20 bytes. Moreover, the timestamp is supposed to be of length 4 bytes.In our scheme, the vehicle sends a message-signature tupleMi,PIDi=PIDi1,PIDi2,TVi,σi=δi,Ri,Ti to the verifier, where PIDi1,Ri are two elements in the elliptic curve group G, PIDi2,δi are two elements in Zq∗, and TVi,Ti are two timestamps. So the communication cost is 2×40+2×20+2×4=128 bytes as shown in Table 6. Here, the cost of the message Mi does not included, which is a common means used in the communication cost comparison. Table 6 also shows us the communication costs of sending a single message-signature tuple by the vehicle in Gayathri et al.’s scheme, Sutra et al.’s scheme, and Mei et al.’s scheme, which are 228, 228, and 668 bytes, respectively. The communication costs for these schemes are also compared graphically in Figure 7. From Table 6 and Figure 7, it is clear that the communication cost of our scheme is significantly less than the other three schemes.Table 6
Comparison of communication cost.
SchemeMessageSending a single messageSendingn messageGayathri et al. [20]Mi,PIDi=PIDi1,PIDi2,TVi,Xi,σi=Ri,Y1i,μi,wi,Ti228 bytes228n bytesSutrala et al. [21]Mi,δi=fi,gi,Bi,Ki,Ri,PIDi=PIDi1,PIDi2,TVi,Ti228 bytes228n bytesMei et al. [17]Mi,ti,vepki,PIDi1,PIDi2,TVi,IDRs,sigi=Ui,Ti668 bytes668n bytesOurMi,PIDi=PIDi1,PIDi2,TVi,σi=δi,Ri,Ti128 bytes128n bytesFigure 7
Comparison of communication cost forn signatures.


## 6.3. Storage Cost

In this subsection, the comparison of the storage space required by the vehicle in the signature phase for different schemes is presented.In our scheme, the vehicleVi needs to store the secret αi, the pseudo identity PIDi=PIDi1,PIDi2,TVi, and the partial private key pskVi into its memory. So the required storage cost is 40+3×20+4=104 bytes as shown in Table 7. Also, shown in Table 7 are the storage costs required for Gayathri et al.’s scheme, Sutrala et al.’s scheme, and Mei et al.’s scheme, which are 184, 244, and 536 bytes, respectively. From Table 7, it can be clearly seen that the vehicle of our scheme has the smallest storage space compared with the other three schemes.Table 7
Comparison of storage cost.
SchemeStorage messageStorage costGayathri et al. [20]Xi,Ri,di,xi,PIDi=PIDi1,PIDi2,TVi184 bytesSutrala et al. [21]vti,ai,PIDi1,PIDi2,TVi,vpk1i,vpk3i,ki,Ri,Ki244 bytesMei et al. [17]PIDi1,PIDi2,TVi,pski,j,xi,vepki536 bytesOurPIDi1,PIDi2,TVi,αi,pskVi104 bytes


## 6.4. Security Comparison

In this subsection, we compare the various security and functionality features of our scheme with that of Gayathri et al.’s scheme, Sutrala et al.’s scheme, and Mei et al.’s scheme. LetSF1, SF2, SF3, SF4, SF5, SF6, SF7, and SF8 represent the goals of 1 message authentication and integrity, 2 identity privacy-preservation, 3 traceability, 4 unthinkability, 5 modification attack resistance, 6 impersonate attack resistance, 7 side-channel attack resistance, and 8 replay attack resistance, respectively. The comparison of security goals is indicated in Table 8. The symbol √ denotes that the security goal is satisfied, and the symbol × denotes that the security goal is unsatisfied.Table 8
Comparison of security.
SchemeSF1SF2SF3SF4SF5SF6SF7SF8Gayathri et al. [20]√√√√√××√Sutrala et al. [21]√√×√××√√Mei et al. [17]√√√√×√√√Our√√√√√√√√From Table8, it can be seen that our scheme provides all the mentioned necessary security features and is not vulnerable to any known attacks. In Gayathri et al.’s scheme, the vehicle can impersonate other vehicles through the pseudonym generated by itself, and a secure key update is not provided, so it is vulnerable to the impersonate attack and the side-channel attack. Sutrala et al.’s scheme is vulnerable to the modification attack and the impersonate attack, and TA cannot track the vehicle [28]. In Mei et al.’s scheme, the modification attack is possible [24]. Overall, compared with the existing related solutions in Table 8, our scheme provides a better security performance.


## 7. Conclusion and Discussion

In this article, we present a secure and efficient conditional privacy-preserving batch authentication scheme based on elliptic curve cryptography. In our scheme, TA is responsible for vehicle registration and generates informationα that is bound to the vehicle’s real identity for the vehicle. Then the vehicle can request KGC to generate a pseudo identity and partial private key for it through message α. This procedure of pseudo identity and partial private key generation is renewed periodically as needed, which prevents side-channel attacks on the TPD of the vehicle. After the vehicle obtains the pseudo identity and partial private key, the vehicle generates the private key and uses the private key to sign the message and then broadcasts the signature together with its pseudo identity and the message. The identity privacy of the vehicle is preserved by broadcasting its pseudo identity rather than the real identity over the IoV network, and this privacy is conditional since any entity except the TA cannot reveal the real identity from the pseudo identity. When many messages are received simultaneously at the vehicle or the RSU, a procedure of batch verification can be conducted to reduce the computation. Our scheme is shown to be secure by proof of unforgeability for the signature and a comprehensive analysis of necessary security features and resistances to various potential attacks. The cost of our scheme in terms of computation, communication, and storage is exhaustive compared to several state-of-the-art schemes that demonstrates that the overall performance of our new scheme is better.Our authentication scheme protects the vehicle’s identity privacy and meets the necessary security features, but it, similar to previous designs [15–22], has some limitations. For example, it does not resist a collusion attack. That is, if a (large) group of vehicles collude and send a bogus message by the authentication scheme, the message will pass verification, and no collusive vehicle will be revealed. As the development of the internet of things and artificial intelligence, data poisoning attacks [38], under which a large number of users may be trapped to broadcast bogus traffic-related information over the IoV network, have attracted more and more attention, which will make the (automated) vehicle fail to schedule the best route. A solution to recover this limitation is to introduce the trust mechanism [39] into the cryptographic authentication approaches, which is our future work. In addition, motivated by the three-factor authentication and key agreement technology over the users/vehicles and the servers [40], the factor of biometrics can also be introduced in the design of a CPPBA scheme to realize an effective connection between the vehicles and the users. Before the user logs in to the vehicle, the user will be recognized by its biometric, and only the legitimate user can access the vehicle. When in disputes and responsibilities, the TA can reveal not only the real identity of the vehicle but also the real identity of the user. This is also an interesting and important direction in the future.



---

*Source: 5049766-2021-12-30.xml*