# Efficient Certificateless Conditional Privacy-Preserving Authentication Scheme in VANETs

Authors: Yang Ming; Hongliang Cheng
Journal: Mobile Information Systems
 (2019)

---

## Abstract

Vehicular ad hoc networks (VANETs) are an increasing important paradigm for greatly enhancing roadway system efficiency and traffic safety. To widely deploy VANETs in real life, it is critical to deal with the security and privacy issues in VANETs. In this paper, we propose a certificateless conditional privacy preserving authentication (CCPPA) scheme based on certificateless cryptography and elliptic curve cryptography for secure vehicle-to-infrastructure communication in VANETs. In the proposed scheme, a roadside unit (RSU) can simultaneously verify plenty of received messages such that the total verification time may be sharply decreased. Furthermore, the security analysis indicates that the proposed scheme is provably secure in the random oracle model and fulfills all the requirements on security and privacy. To further improve efficiency, both map-to-point hash operation and bilinear pairing operation are not employed. Compared with previous CCPPA schemes, the proposed scheme prominently cuts down computation delay of message signing and verification by 66.9%–85.5% and 91.8%–93.4%, respectively, and reduces communication cost by 44.4%. Extensive simulations show that the proposed scheme is practicable and achieves prominent performances of very little average message delay and average message loss ratio and thus is appropriate for realistic applications.


---

## Body

## 1. Introduction

The speedy evolution of wireless technology has elevated Intelligent Transportation System (ITS) to higher levels and also made vehicular ad hoc networks (VANETs) more attractive from academia and industry [1]. VANETs, as a special application of Mobile Ad Hoc Networks (MANETs), are an important component of ITS, rapidly changing, and self-configuring and employ multiple-hops topologies on wireless links [2].A typical architecture of the VANETs is shown in Figure1. Usually, the VANETs system comprises four main components, i.e., the Trusted Authorities (TAs), the Application Servers (ASs), the Roadside Units (RSUs), and the vehicles, which is equipped with Onboard Units (OBUs). The responsibility of TAs is to maintain the whole system. The work of ASs is to provide a further data analysis. The RSUs are along the roadside deployment, which serve as transfer stations or carry out the authentication works to lighten the burden of the TAs. The OBUs are embedded in the vehicles to collect and process the traffic-related information and communicate with other entities. The communications mode in VANETs can be classified into two basic types, i.e., Vehicle-to-Infrastructure (V2I) communication and Vehicle-to-Vehicle (V2V) communication. In V2I communication, the vehicles communicate directly with the RSUs fixed in roadside. The vehicles communicate directly with each other to exchange the information in V2V communication. The vehicles (OBUs) communicate with the RUSs and other vehicles via a public wireless channel. Through the wired channel, the RSUs also connect with TAs and ASs. In VANETs, utilizing Dedicated Short Range Communications (DSRC) standard [3], each vehicle periodically broadcasts the vehicle-related condition messages (e.g., speed, turning intention, direction, and position) and traffic-related safety messages (e.g., congestion state, traffic events, and weather) every 100–300 milliseconds (ms). One side, all the messages are forwarded to the traffic control center (AS) by the RSUs through wired connection. Based on the received messages, the management strategy and optimized control can be generated by the traffic control center to improve efficiency and traffic safety through analyzing the current traffic load in each intersection. On the other side, an early response can be made by the vehicles under the specific situations such as emergent braking, traffic jams, accidents, etc.Figure 1
A typical architecture of VANETs.The appearing of VANETs stems from enhancing the safe driving conditions and road safety. As the traffic-related messages are transmitted in the wireless channel, the malicious attackers can easily eavesdrop, modify, replay, and delete the messages. Hence, for the practical applications of VANETs, the security and privacy challenges are needed to be tackled.Facing all kinds of security attacks mentioned above, the message authentication is a crucial security problem for VANETs. In practice, the messages from the vehicle (OBU) need to be integrity-checked and authenticated before depended on. The reason is that an attacker can replace or modify the original safety messages or even impersonate a vehicle to broadcast bogus messages. The message authentication, which consists of identity authentication check and the message integrity check, is implemented to allow vehicle to differentiate trustworthy messages from broadcast messages and to resist impersonation attacks and modification attacks. The digital signature technology would be used to solve this problem in VANETs, which not only allows the receiver to identify the sender, but also prevents the message contents from being altered in transmission.In addition, privacy is also a significant issue in VANETs. In real life, the vehicle-related privacy information like a vehicle’s real identity should be hidden; otherwise, the moving patterns and location of the vehicle can be traced by the attacker. For instance, the leakage of vehicle’s traveling routes information will disclose privacy of the vehicle and lead to serious consequences since the information may be utilized for crimes or traffic collisions. Therefore, the vehicles’ privacy must be ensured in VANETs. Nonetheless, sometimes there is a conflict between the security and the privacy. The former needs to know the message’s origin and integrity, while the latter requires that no entity can trace a message to its generator. Hence, conditional privacy is usually considered in VANETs. That is to say, vehicle’s privacy is normally guaranteed, but if a malicious vehicle broadcasts fake messages and causes accidents or crimes, a legal authority will be capable to trace or retrieve the messages of vehicle through revealing the vehicle’s real identity.The conditional privacy-preserving authentication (CPPA) mechanism, which is able to achieve message authentication and conditional privacy simultaneously, is fully appropriate for solving the security and privacy issues in VANETs.Several research works about privacy preserving authentication for VANETs have been proposed in recent years, which include public key infrastructure based (PKI-based) CPPA schemes [2, 4–6], identity-based (ID-based) CPPA schemes from bilinear pairing [7–19], binary authentication tree [20, 21] and elliptic curve [22–29], and certificateless CPPA schemes [30, 31]. Although certificateless conditional privacy preserving authentication (CCPPA) schemes for VANETs [30, 31] solve the public key certification management problem in PKI-based CPPA schemes and the key escrow problem in ID-based CPPA schemes, the performance of [30, 31] is not efficient owing to the need of map-to-point hash and bilinear pairing operations. We know that these two operations are more complex, which means they need more time to execute than other operations. Therefore, it is important for secure and practical VANETs to design a CCPPA scheme without map-to-point hash and bilinear pairing operations.Based on certificateless cryptography [32] and elliptic curve cryptography (ECC) [33, 34], an efficient CCPPA scheme for VANETs is proposed in this paper. The major contributions are as follows:(i)
An efficient CCPPA scheme for VANETs is proposed without employing map-to-point hash and bilinear pairing operations. The proposed scheme achieves the fast batch message verification.(ii)
The security analysis shows that the proposed scheme is provably secure under the assumption of elliptic curve discrete logarithm in the random oracle model and satisfies all security and privacy requirements.(iii)
The performances in computation delay and communication overhead are evaluated. The experimental simulations indicate that the proposed CCPPA scheme is more efficient than schemes in [30, 31] for VANETs.(iv)
An extensive simulation is conducted, and the results demonstrate that the proposed CCPPA scheme has extremely low average message delay and average message loss ratio.The remainder of this paper is organized as follows. In Section2, we provide a review of the previous related works. The system model, security requirements, and elliptic curve group are presented in Section 3. We propose a concrete CCPPA scheme for secure V2I communication in Section 4 and the security analysis for the proposed scheme in Section 5. Section 6 conducts the performance evaluation and experimental simulations of the proposed scheme with other schemes. Finally, we conclude the paper in Section 7.


## 2. Related Works

In VANETs, the security and privacy problems have attracted strong interest and research from industry and academia. Recently, lots of CPPA schemes for VANETs have been put forward and roughly classified into three categories: PKI-based schemes, ID-based schemes, and certificateless schemes.In 2004, Hubaux et al. [4] firstly pointed out the security and privacy issues in VANETs and declared that the public key infrastructure (PKI) technology could be used to protect transmitted messages in the vehicles. In 2007, based on anonymous certificates, an anonymous authentication scheme for VANETs was proposed by Raya and Hubaux [2]. They showed that the proposed scheme can provide message authentication and conditional privacy preservation. In this scheme, each vehicle requires to preload a huge quantity of anonymous public/private key pairs and corresponding public key certificates and then to sign a message using one of the private keys for anonymity in each communication. Therefore, a huge storage space is needed to store keys and corresponding certificates in all vehicles, while the certificate authority also needs to store all vehicles’ certificates. In 2008, Lu et al. [5] put forward an efficient conditional privacy preservation (ECPP) scheme for VANETs to solve the problem of a large storage space for the vehicles in [2] by employing the temporary anonymous certificates. Based on the hash message authentication code (HMAC) and k-anonymity approach, an efficient RSU-aided message authentication scheme was proposed by Zhang et al. [6] to realize the privacy preserving of the vehicles. In summary, all the PKI-based authentication schemes for VANETs have a bottleneck problem on the storage and management of certificates.To tackle the problem mentioned above, identity-based (ID-based) authentication schemes for VANETs have been proposed. Based on the ID-based cryptography [35], Zhang et al. [7, 8] proposed ID-based CPPA schemes. In their schemes, both the vehicle (OBU) and RSU use the identity information (such as license plate number, device number) as the public keys and the corresponding private keys are generated by a trusted third party, called the Private Key Generator (PKG). Therefore, these schemes can eliminate the need for certificates storage in vehicles and RSUs. Also, the technology of batch message verification can be provided to realize the function of verifying large number of messages simultaneously. In 2011, Chim et al. [9] claimed that Zhang et al.’s schemes [7, 8] are vulnerable to the impersonation attack and antitraceability attack. Using the two shared secrets, Chim et al. [9] also proposed a communication scheme for VANETs. The new scheme not only satisfies the requirements of the security and privacy and but also has lower communication overhead. In 2012, based on the pseudo-identity-based signature, an ID-based CPPA scheme for VANETs was established in [10] which provided the batch message verification. In 2013, Lee and Lai [11] showed that scheme in [7] was insecure against repudiation and relay attacks. And, an improved ID-based privacy-preserving authentication scheme for VANETs was put forward to overcome the weaknesses in [7] and maintain the efficiency. Horng et al. [12] pointed out that scheme in [9] is vulnerable to impersonation attack and gave a new scheme to remedy the security flaw mentioned in [9]. In 2014, Liu et al. [13] indicated that the underlying Shim’s identity-based signature scheme in [10] was insecure and thus the corresponding authentication mechanism suffers from modification attacks. An improved ID-based CPPA scheme was proposed in [14] to make up for the weaknesses in [11] and maintain the efficiency as scheme in [11]. In 2015, Bayat et al. [15], aiming at the security flaw in [11], proposed a new scheme. In 2016, exploring the ID-based signature with message recovery, Liu et al. [16] presented an efficient authentication scheme for VANETs that realized the anonymity of vehicles and batch message authentication. Based on bilinear pairing, a CPPA scheme for VANETs was proposed by Wang et al. [17]. This scheme is proven secure under the computational Differ–Hellman (CDH) assumption in the random oracle model. Based on HMAC and identity based signature, an anonymous batch authentication protocol for VANETs was proposed by Jiang et al. [18]. In 2017, Tzeng et al. [19] found that the scheme in [11] was exposed to some security risks in VANETs and proposed a secure scheme in the random oracle model. In 2009, Jiang et al. [20] firstly presented an ID-based authentication algorithm for V2I communication using a binary authentication tree. This scheme achieves high efficiency when verifying many signatures and filtering bogus messages. However, Shim [21] claimed that Jiang et al.’s scheme in [20] was unable to resist replay, forgery and sybil attacks, and proposed an improved scheme using aggregate signature, ID-based signature, and binary authentication tree. In 2015, by utilizing the ECC, He et al. [22] firstly proposed an ID-based CPPA scheme for VANETs without using map-to-point hash as well as bilinear pairing operations. This scheme has better performances in terms of computation and communication costs. Based on BLS short signature [36] and ECC, Xie et al. [23, 24] put forward ID-based conditional privacy preserving authentication schemes for VANETs, respectively. These schemes satisfy the security and privacy requirements in VANETs and achieve lower computation costs. For the secure communication and vehicle privacy in VANETs, Lo and Tsai [25] presented an efficient CPPA scheme, which does not need map-to-point hash and bilinear pairing operations to achieve better performances. Zhong et al. [26] proposed a provably secure CPPA scheme in the random oracle model which provides a practical service application for VANETs. In 2017, based on the ECC, Wu et al. [27] established an efficient location-based CPPA protocol for VANETs without using the bilinear pairing and tamper-proof device, which could satisfy the security and privacy requirements. Exploiting the binary search and cuckoo filter techniques, Cui et al. [28] proposed a secure privacy-preserving authentication scheme with high success rate in batch verification. In 2018, Li et al. [29] put forward an efficient and anonymous CPPA scheme, which achieves an optimal performance in terms of computation and communication costs. In the aforementioned ID-based CPPA schemes, all the entities’ private keys are generated by PKG, which eliminates the management and storage of certificates in PKI-based schemes. However, the schemes suffer from the inherent key escrow problem, i.e., PKG knows the private keys of all vehicles and RSUs and thus literally decrypts any ciphertexts and forges signatures on any messages as any entity. Therefore, it seems that ID-based schemes may not suitable for VANETs.To solve the key escrow problem of ID-based schemes as well as the certificate management problem in PKI-based schemes, Horng et al. [30] proposed a provable secure CCPPA scheme for VANETs based on the certificateless cryptography [32]. In CCPPA scheme, only the partial private key for the users (vehicles and RSUs) is generated by the trusted Key Generator Center (KGC). The user chooses a secret value itself and combines the partial private key to form the private key and hence KGC cannot obtain the private keys of the users. Note that the certificates are no longer required to guarantee the authenticity of public keys in CCPPA scheme. In 2016, Li et al. [31] pointed out that the scheme in [30] was insecure under the malicious-but-passive KGC attack, i.e., KGC can forge a signature or decrypt a ciphertext using maliciously embedded trapdoors in the public parameters. Furthermore, an improved scheme was put forward. In 2018, based on the new paradigm of certificateless signature with message signature (CLS-MR), Ming and Shen [37] proposed a CCPPA scheme for VANETs. The advantage is that the scheme achieved better communication efficiency. The only imperfection is that the maximum message length was limited to k2, where k2 is a positive integer such that k2 less than a prime number p. In this paper, the certificateless signature technology is used to design an efficient CCPPA scheme, where the length of message is arbitrary size. Hence, this scheme is more suitable for practical VANETs system.


## 3. Preliminaries

### 3.1. System Model

The system model of the proposed scheme is shown in Figure2. This model consists of two layers. The lower layer comprises OBUs installed in the vehicles and RSUs along with roadsides. The communication between RSU and OBU is based on the DSRC protocol [3]. The upper layer includes two trust authorities (TAs), i.e., Key Generator Center (KGC) and Trace Authority (TRA), and Application Servers (ASs) (data analysis center or traffic control center), where message exchange would be implemented over the secure channel provided by the transport layer security (TLS) protocol.Figure 2
System model of VANETs.KGC. The KGC is assumed to be a trusted third party and has sufficient storage space and computing power. KGC is in charge of producing public system parameters and preloading them on RSUs and OBUs in the off-line mode. Furthermore, it also generates and distributes the partial private keys for RSUs and OBUs.TRA. The TRA is assumed to be a trusted third party and has sufficient storage space and computing power. TRA is responsible for the registration of RSUs and OBUs. It can trace messages to their sources and reveal the real identities of the vehicles.AS. The AS is a safety-related application server, like a traffic-data analysis center, or a traffic manage center. AS is working for first gathering the traffic-related messages including current location, time, and traffic accidents from RSUs and then making further analysis and/or providing feedbacks to them. The AS communicates with KGC, TRA, and RSUs via the wired channel.RSU. The RSU is located along the roadside with higher computation capabilities. It can communicate with OBU of the vehicle in their coverage region by a wireless channel and communicate with KGC, TRA, and AS via a secure wired channel. In VANETs, the RSU is assumed to be a fully trusted party and is used for verifying messages and processing them locally or sending them to TA or AS when received traffic-related messages.OBU. The OBU is embedded in the vehicle to communicate with other OBUs and RSUs using Dedicated Short Range Communication (DSRC) [3] technology recognized as IEEE 802.11p (5.9 GHz). It warns the driver about jams and to avoid road accidents through periodically broadcasting the traffic-related status messages like speed, direction, and position to other vehicles.


### 3.2. Security Requirements

In V2I communication scenario, the following security requirements are needed to be satisfied in the proposed CCPPA scheme.Message Authentication. The receiver should be able to verify the traffic-related messages and appended signatures in VANETs in order to preserve the integrity of messages sent by the vehicle.Identity Privacy Preserving. The real identity of each vehicle should be kept secret from other entities in VANETs. Any entity ought not break the vehicle’s privacy and disclose the real identity of the vehicle by analyzing transmitted messages.Traceability. The TRA, as a trusted party must have the capability to expose the real identity of any malicious vehicle, which has broadcasted forged messages to other vehicles in order to disrupt the traffic.Unlinkability. In addition to TRA, it is difficult to determine for anyone whether two messages are sent by the same vehicle.Role Separation. Two trusted authorities TRA and KGC are involved in VANETs. TRA is in charge of constructing pseudo identities of the vehicle and if necessary, tracing the vehicle’s real identity. KGC is for creating the vehicle’s partial private key on the pseudo identity.Key Escrow Resilience. In VANETs, KGC is normally a semitrusted commercial organization rather than full-trusted and trustworthy entity. Therefore, it is required that KGC cannot impersonate the legitimate vehicle and to generate a valid signature using the vehicle’s private key.Resistance to Attack. Apart from the conventional security and privacy requirements, the CCPPA scheme must be capable to resist various common attacks in the lower layer communication, for example, the impersonation attack, modification attack, replay attack, and man-in-the-middle attack.


### 3.3. Elliptic Curve Group

The elliptic curve cryptography (ECC) was initially introduced by Miller [33] and Koblitz [34].An elliptic curveE over a finite field Fp, where p is a large prime, is defined by the following equation:(1)y2=x3+ax+bmodpa,b∈Fp,where 4a3+27b2modp≠0.An infinity pointO and all points x,y∈E form an additive cyclic group G. Scalar multiplication over G is defines as(2)kP=P+P+⋯+Pktimes,where P∈G.Elliptic curve discrete logarithm (ECDL) problem [22, 37]: given two random points P and Q on the elliptic curve E, find an integer x, such that Q=xP.Elliptic curve discrete logarithm (ECDL) assumption [22, 37]: the ECDL assumption means that there are no know polynomial-time algorithms to solve the ECDL problem with non-negligible probability.Elliptic curve computational Differ–Hellman (ECCDH) problem [22, 37]: given two random points R=xP and Q=yP on the elliptic curve E, where x,y are two unknown integers, compute the point xyP.Elliptic curve computational Differ–Hellman (ECCDH) assumption [22, 37]: the ECCDH assumption means that there are no know polynomial-time algorithms to solve the ECCDH problem with non-negligible probability.


## 3.1. System Model

The system model of the proposed scheme is shown in Figure2. This model consists of two layers. The lower layer comprises OBUs installed in the vehicles and RSUs along with roadsides. The communication between RSU and OBU is based on the DSRC protocol [3]. The upper layer includes two trust authorities (TAs), i.e., Key Generator Center (KGC) and Trace Authority (TRA), and Application Servers (ASs) (data analysis center or traffic control center), where message exchange would be implemented over the secure channel provided by the transport layer security (TLS) protocol.Figure 2
System model of VANETs.KGC. The KGC is assumed to be a trusted third party and has sufficient storage space and computing power. KGC is in charge of producing public system parameters and preloading them on RSUs and OBUs in the off-line mode. Furthermore, it also generates and distributes the partial private keys for RSUs and OBUs.TRA. The TRA is assumed to be a trusted third party and has sufficient storage space and computing power. TRA is responsible for the registration of RSUs and OBUs. It can trace messages to their sources and reveal the real identities of the vehicles.AS. The AS is a safety-related application server, like a traffic-data analysis center, or a traffic manage center. AS is working for first gathering the traffic-related messages including current location, time, and traffic accidents from RSUs and then making further analysis and/or providing feedbacks to them. The AS communicates with KGC, TRA, and RSUs via the wired channel.RSU. The RSU is located along the roadside with higher computation capabilities. It can communicate with OBU of the vehicle in their coverage region by a wireless channel and communicate with KGC, TRA, and AS via a secure wired channel. In VANETs, the RSU is assumed to be a fully trusted party and is used for verifying messages and processing them locally or sending them to TA or AS when received traffic-related messages.OBU. The OBU is embedded in the vehicle to communicate with other OBUs and RSUs using Dedicated Short Range Communication (DSRC) [3] technology recognized as IEEE 802.11p (5.9 GHz). It warns the driver about jams and to avoid road accidents through periodically broadcasting the traffic-related status messages like speed, direction, and position to other vehicles.


## 3.2. Security Requirements

In V2I communication scenario, the following security requirements are needed to be satisfied in the proposed CCPPA scheme.Message Authentication. The receiver should be able to verify the traffic-related messages and appended signatures in VANETs in order to preserve the integrity of messages sent by the vehicle.Identity Privacy Preserving. The real identity of each vehicle should be kept secret from other entities in VANETs. Any entity ought not break the vehicle’s privacy and disclose the real identity of the vehicle by analyzing transmitted messages.Traceability. The TRA, as a trusted party must have the capability to expose the real identity of any malicious vehicle, which has broadcasted forged messages to other vehicles in order to disrupt the traffic.Unlinkability. In addition to TRA, it is difficult to determine for anyone whether two messages are sent by the same vehicle.Role Separation. Two trusted authorities TRA and KGC are involved in VANETs. TRA is in charge of constructing pseudo identities of the vehicle and if necessary, tracing the vehicle’s real identity. KGC is for creating the vehicle’s partial private key on the pseudo identity.Key Escrow Resilience. In VANETs, KGC is normally a semitrusted commercial organization rather than full-trusted and trustworthy entity. Therefore, it is required that KGC cannot impersonate the legitimate vehicle and to generate a valid signature using the vehicle’s private key.Resistance to Attack. Apart from the conventional security and privacy requirements, the CCPPA scheme must be capable to resist various common attacks in the lower layer communication, for example, the impersonation attack, modification attack, replay attack, and man-in-the-middle attack.


## 3.3. Elliptic Curve Group

The elliptic curve cryptography (ECC) was initially introduced by Miller [33] and Koblitz [34].An elliptic curveE over a finite field Fp, where p is a large prime, is defined by the following equation:(1)y2=x3+ax+bmodpa,b∈Fp,where 4a3+27b2modp≠0.An infinity pointO and all points x,y∈E form an additive cyclic group G. Scalar multiplication over G is defines as(2)kP=P+P+⋯+Pktimes,where P∈G.Elliptic curve discrete logarithm (ECDL) problem [22, 37]: given two random points P and Q on the elliptic curve E, find an integer x, such that Q=xP.Elliptic curve discrete logarithm (ECDL) assumption [22, 37]: the ECDL assumption means that there are no know polynomial-time algorithms to solve the ECDL problem with non-negligible probability.Elliptic curve computational Differ–Hellman (ECCDH) problem [22, 37]: given two random points R=xP and Q=yP on the elliptic curve E, where x,y are two unknown integers, compute the point xyP.Elliptic curve computational Differ–Hellman (ECCDH) assumption [22, 37]: the ECCDH assumption means that there are no know polynomial-time algorithms to solve the ECCDH problem with non-negligible probability.


## 4. The Proposed Scheme

This section describes a CCPPA scheme for V2I communication. The proposed CCPPA scheme includes the following four phases: system initialization, pseudo identity generation and partial private key extraction, private key generation and message signing, and message verification. The definition of notations used in the present paper is listed in Table1.Table 1
Notations.
Symbol
Description
V
i
Theith vehicle
RSU
A roadside unit
OBU
A onboard unit
KGC
A key generation center
TRA
A trace authority
p
,
q
Two large prime numbers
F
p
The finite field overp
G
An additive group with the orderq on the elliptic curve E over Fp
P
A generator ofG
RID
i
TheVi’s real identity
PID
i
TheVi’s pseudo identity
H
1
⋅
,
H
2
⋅
,
H
3
⋅
,
H
4
⋅
Four one-way hash functions,H1,H2,H3,H4:0,1∗⟶ℤq∗
P
pub
,
s
The KGC’s public key and private key
T
pub
,
t
The TRA’s public key and private key
P
i
,
x
i
TheVi’s public key and secret value
d
i
TheVi’s partial private key
⊕
The exclusive OR operation
t
i
The current timestamp
T
i
The valid period of the pseudo identity


### 4.1. System Initialization

This phase is executed by the two TAs (KGC and TRA) to generate system parameters for all RSUs and OBUs. The following steps are performed in this phase:(1)
The TAs randomly choose two large prime numbersp and q. Then TAs select a non-singular elliptic curve E defined by the equation y2=x3+ax+bmodp, where a,b∈Fp.(2)
The TAs pick a groupG of elliptic curve points with prime order q and a generator P of G.(3)
The KGC randomly choosess∈ℤq∗ as the master key for partial private key extraction and computes Ppub=sP.(4)
The TRA randomly selectst∈Zq∗ as the master key for identity traceability and computes Tpub=tP.(5)
The TAs choose four one-way hash functions:H1:0,1∗⟶ℤq∗, H2:0,1∗⟶ℤq∗, H3:0,1∗⟶ℤq∗ and H4:0,1∗⟶ℤq∗.The TAs publishparams=p,q,G,P,Ppub,Tpub,H1,H2,H3,H4 as the public system parameters and send them to all RSUs and vehicles (OBUs). The master keys s and t are kept secretly by KGC and TRA, respectively. Here, the system parameters params are preloaded into the tamper-proof devices (TPD) of all vehicles in VANETs.


### 4.2. Pseudo Identity Generation and Partial Private Key Extraction

This phase is executed between the vehicles and the TAs (TRA, KGC). The TRA calculates the pseudo identities for the vehicleVi, and then the KGC generates the partial private keys corresponding to the pseudo identities, when TRA receiving the real identity RIDi from Vi, where RIDi uniquely identifies the vehicle Vi. Based on this fact, the TRA and KGC preload the pseudo identities and partial private keys in TPD of vehicle Vi after successful completion of own offline registration. The following steps are executed in this phase:(1)
The vehicleVi transmits the real identity RIDi to the TRA in a secure manner.(2)
After confirming the real identityRIDi, the TRA randomly chooses wi∈ℤq∗ and computes(3)PIDi,1=wiP,PIDi,2=RIDi⊕H1wiTpub,Ti,where Ti defines the valid period of this pseudo identity. Then, a pseudo identity PIDi=PIDi,1,PIDi,2,Ti is delivered to the KGC in a secure channel.(3)
For a given pseudo identityPIDi=PIDi,1,PIDi,2,Ti, the KGC randomly chooses di∈ℤq∗ and computes the partial private key (Di,ki), where(4)Di=diP,ki=di+sH2PIDi,Di,Tpub,Ppub.The KGC sends the pseudo identity and partial private keyPIDi,Di,ki to the vehicle Vi.


### 4.3. Private Key Generation and Message Signing

At the private key generation and message signing phase, the vehicleVi generates private key and signs messages. Then, the vehicle Vi broadcasts a message including the pseudo identity, traffic-related message and signature, public key, and timestamp, to nearby RUSs. This phase is depicted as follows:(1)
The vehicleVi randomly picks xi∈Zq∗ and sets xi as the secret value and computes Pi=xiP. Then, the vehicle Vi’s private key is Di,ki,xi and the public key is Pi.(2)
The vehicleVi randomly chooses a pseudo identity PIDi from its storage and a current timestamp ti, which supports the freshness of message so as to resist the replay attack. Given a traffic-related message Mi, the vehicle Vi randomly selects ri∈ℤq∗ and computes(5)Ri=riP,σi=ki+xiH3Mi,PIDi,Di,Pi,ti+riH4Mi,PIDi,Di,Ri,ti.The signature of a traffic-related messageMi is Di,Ri,σi. Then, the vehicle Vi issues the message Mi,PIDi,ti,Pi,Di,Ri,σi to nearby RSUs.


### 4.4. Message Verification

The verifier (RSU) performs a validity check on the received traffic-related messages in this phase, who can verify the correctness of the signature to ensure that the corresponding vehicle is not attempting to impersonate any other legitimate vehicles or disseminate false messages. The single message verification and batch message verification are as follows, respectively.


#### 4.4.1. Single Message Verification

The verifier receives the messageMi,PIDi,ti,Pi,Di,Ri,σi to verify the validity of the message by the performing the following steps:(1)
The verifier checks whetherTi is valid and ti is fresh. If Ti is not valid or ti is not fresh, the message will be dropped.(2)
The verifier checks whether the equation(6)σiP=Di+H2PIDi,Di,Tpub,PpubPpub+H3Mi,PIDi,Di,Pi,tiPi+H4Mi,PIDi,Di,Ri,tiRi,holds or not. If it holds, accept the message.


#### 4.4.2. Batch Message Verification

The batch message verification can be used to verify multiple messages simultaneously in order to enhance the efficiency of verification. When receiving the distinctn messages M1,PID1,t1,P1,D1,R1,σ1,M2,PID2,t2,P2,D2,R2,σ2,…,Mn,PIDn,tn,Pn,Dn,Rn,σn generated by the different vehicles, respectively, the verifier checks the validity of the messages as follows:(1)
The verifier checks whetherTi is valid and ti is fresh, where i=1,2,…,n. If any Ti is not valid or ti is not fresh, the messages will be dropped.(2)
The verifier checks whether the equation(7)∑i=1nσiP=∑i=1nDi+∑i=1nH2PIDi,Di,Tpub,PpubPpub+∑i=1nH3Mi,PIDi,Di,Pi,tiPi+∑i=1nH4Mi,PIDi,Di,Ri,tiRi,holds or not. If it holds, accept the messages.To detect any invalid signature in batch message verification ofn messages, we use the small exponent test technology [14, 16] to realize batch message verification. The verifier checks whether the following equation(8)∑i=1nvi⋅σiPi=∑i=1nvi⋅Di+∑i=1nvi⋅H2PIDi,Di,Tpub,PpubPpub+∑i=1nvi⋅H3Mi,PIDi,Di,Pi,tiPi+∑i=1nvi⋅H4Mi,PIDi,Di,Ri,tiRi,holds or not. If it holds, accept the messages, where vi∈1,2l and l is a small integer.


## 4.1. System Initialization

This phase is executed by the two TAs (KGC and TRA) to generate system parameters for all RSUs and OBUs. The following steps are performed in this phase:(1)
The TAs randomly choose two large prime numbersp and q. Then TAs select a non-singular elliptic curve E defined by the equation y2=x3+ax+bmodp, where a,b∈Fp.(2)
The TAs pick a groupG of elliptic curve points with prime order q and a generator P of G.(3)
The KGC randomly choosess∈ℤq∗ as the master key for partial private key extraction and computes Ppub=sP.(4)
The TRA randomly selectst∈Zq∗ as the master key for identity traceability and computes Tpub=tP.(5)
The TAs choose four one-way hash functions:H1:0,1∗⟶ℤq∗, H2:0,1∗⟶ℤq∗, H3:0,1∗⟶ℤq∗ and H4:0,1∗⟶ℤq∗.The TAs publishparams=p,q,G,P,Ppub,Tpub,H1,H2,H3,H4 as the public system parameters and send them to all RSUs and vehicles (OBUs). The master keys s and t are kept secretly by KGC and TRA, respectively. Here, the system parameters params are preloaded into the tamper-proof devices (TPD) of all vehicles in VANETs.


## 4.2. Pseudo Identity Generation and Partial Private Key Extraction

This phase is executed between the vehicles and the TAs (TRA, KGC). The TRA calculates the pseudo identities for the vehicleVi, and then the KGC generates the partial private keys corresponding to the pseudo identities, when TRA receiving the real identity RIDi from Vi, where RIDi uniquely identifies the vehicle Vi. Based on this fact, the TRA and KGC preload the pseudo identities and partial private keys in TPD of vehicle Vi after successful completion of own offline registration. The following steps are executed in this phase:(1)
The vehicleVi transmits the real identity RIDi to the TRA in a secure manner.(2)
After confirming the real identityRIDi, the TRA randomly chooses wi∈ℤq∗ and computes(3)PIDi,1=wiP,PIDi,2=RIDi⊕H1wiTpub,Ti,where Ti defines the valid period of this pseudo identity. Then, a pseudo identity PIDi=PIDi,1,PIDi,2,Ti is delivered to the KGC in a secure channel.(3)
For a given pseudo identityPIDi=PIDi,1,PIDi,2,Ti, the KGC randomly chooses di∈ℤq∗ and computes the partial private key (Di,ki), where(4)Di=diP,ki=di+sH2PIDi,Di,Tpub,Ppub.The KGC sends the pseudo identity and partial private keyPIDi,Di,ki to the vehicle Vi.


## 4.3. Private Key Generation and Message Signing

At the private key generation and message signing phase, the vehicleVi generates private key and signs messages. Then, the vehicle Vi broadcasts a message including the pseudo identity, traffic-related message and signature, public key, and timestamp, to nearby RUSs. This phase is depicted as follows:(1)
The vehicleVi randomly picks xi∈Zq∗ and sets xi as the secret value and computes Pi=xiP. Then, the vehicle Vi’s private key is Di,ki,xi and the public key is Pi.(2)
The vehicleVi randomly chooses a pseudo identity PIDi from its storage and a current timestamp ti, which supports the freshness of message so as to resist the replay attack. Given a traffic-related message Mi, the vehicle Vi randomly selects ri∈ℤq∗ and computes(5)Ri=riP,σi=ki+xiH3Mi,PIDi,Di,Pi,ti+riH4Mi,PIDi,Di,Ri,ti.The signature of a traffic-related messageMi is Di,Ri,σi. Then, the vehicle Vi issues the message Mi,PIDi,ti,Pi,Di,Ri,σi to nearby RSUs.


## 4.4. Message Verification

The verifier (RSU) performs a validity check on the received traffic-related messages in this phase, who can verify the correctness of the signature to ensure that the corresponding vehicle is not attempting to impersonate any other legitimate vehicles or disseminate false messages. The single message verification and batch message verification are as follows, respectively.


### 4.4.1. Single Message Verification

The verifier receives the messageMi,PIDi,ti,Pi,Di,Ri,σi to verify the validity of the message by the performing the following steps:(1)
The verifier checks whetherTi is valid and ti is fresh. If Ti is not valid or ti is not fresh, the message will be dropped.(2)
The verifier checks whether the equation(6)σiP=Di+H2PIDi,Di,Tpub,PpubPpub+H3Mi,PIDi,Di,Pi,tiPi+H4Mi,PIDi,Di,Ri,tiRi,holds or not. If it holds, accept the message.


### 4.4.2. Batch Message Verification

The batch message verification can be used to verify multiple messages simultaneously in order to enhance the efficiency of verification. When receiving the distinctn messages M1,PID1,t1,P1,D1,R1,σ1,M2,PID2,t2,P2,D2,R2,σ2,…,Mn,PIDn,tn,Pn,Dn,Rn,σn generated by the different vehicles, respectively, the verifier checks the validity of the messages as follows:(1)
The verifier checks whetherTi is valid and ti is fresh, where i=1,2,…,n. If any Ti is not valid or ti is not fresh, the messages will be dropped.(2)
The verifier checks whether the equation(7)∑i=1nσiP=∑i=1nDi+∑i=1nH2PIDi,Di,Tpub,PpubPpub+∑i=1nH3Mi,PIDi,Di,Pi,tiPi+∑i=1nH4Mi,PIDi,Di,Ri,tiRi,holds or not. If it holds, accept the messages.To detect any invalid signature in batch message verification ofn messages, we use the small exponent test technology [14, 16] to realize batch message verification. The verifier checks whether the following equation(8)∑i=1nvi⋅σiPi=∑i=1nvi⋅Di+∑i=1nvi⋅H2PIDi,Di,Tpub,PpubPpub+∑i=1nvi⋅H3Mi,PIDi,Di,Pi,tiPi+∑i=1nvi⋅H4Mi,PIDi,Di,Ri,tiRi,holds or not. If it holds, accept the messages, where vi∈1,2l and l is a small integer.


## 4.4.1. Single Message Verification

The verifier receives the messageMi,PIDi,ti,Pi,Di,Ri,σi to verify the validity of the message by the performing the following steps:(1)
The verifier checks whetherTi is valid and ti is fresh. If Ti is not valid or ti is not fresh, the message will be dropped.(2)
The verifier checks whether the equation(6)σiP=Di+H2PIDi,Di,Tpub,PpubPpub+H3Mi,PIDi,Di,Pi,tiPi+H4Mi,PIDi,Di,Ri,tiRi,holds or not. If it holds, accept the message.


## 4.4.2. Batch Message Verification

The batch message verification can be used to verify multiple messages simultaneously in order to enhance the efficiency of verification. When receiving the distinctn messages M1,PID1,t1,P1,D1,R1,σ1,M2,PID2,t2,P2,D2,R2,σ2,…,Mn,PIDn,tn,Pn,Dn,Rn,σn generated by the different vehicles, respectively, the verifier checks the validity of the messages as follows:(1)
The verifier checks whetherTi is valid and ti is fresh, where i=1,2,…,n. If any Ti is not valid or ti is not fresh, the messages will be dropped.(2)
The verifier checks whether the equation(7)∑i=1nσiP=∑i=1nDi+∑i=1nH2PIDi,Di,Tpub,PpubPpub+∑i=1nH3Mi,PIDi,Di,Pi,tiPi+∑i=1nH4Mi,PIDi,Di,Ri,tiRi,holds or not. If it holds, accept the messages.To detect any invalid signature in batch message verification ofn messages, we use the small exponent test technology [14, 16] to realize batch message verification. The verifier checks whether the following equation(8)∑i=1nvi⋅σiPi=∑i=1nvi⋅Di+∑i=1nvi⋅H2PIDi,Di,Tpub,PpubPpub+∑i=1nvi⋅H3Mi,PIDi,Di,Pi,tiPi+∑i=1nvi⋅H4Mi,PIDi,Di,Ri,tiRi,holds or not. If it holds, accept the messages, where vi∈1,2l and l is a small integer.


## 5. Security Proof and Analysis

In this section, the security analysis of the proposed CCPPA scheme for VANETs is provided. We describe the security model and prove the security of the proposed scheme under the random oracle model. Then, an evaluation on the security requirements of the proposed scheme as well as its comparison with other schemes in [22, 25, 27, 30, 31] is conducted.


### 5.1. Security Model

According to certificateless cryptography [32, 38–41], there are two types of adversaries with different capabilities: Type I adversary A1 and Type II adversary A2. The adversary A1 models an outside adversary and acts as a malicious third party while the adversary A2 models an inside adversary and serves as a malicious-but-passive KGC.(i)
Type I adversary A1. The adversary A1 cannot access the master key, but has the ability to replace the vehicle’s public key with a value chosen by itself.(ii)
Type II adversary A2. The adversary A2 can access the master key, but cannot replace the vehicle’s public key.The following queries can be made byA1 and A2 adversaries.(i)
Hash H1,H2,H3,H4 queries. Given a query, output a random value.(ii)
Create vehicle queries. Given a query on the pseudo identity PIDi of the vehicle, output the vehicle’s public key Pi.(iii)
Partial private key queries. Given a query on the pseudo identity PIDi of the vehicle, output the vehicle’s partial private key Di,ki.(iv)
Secret value queries. Given a query on the pseudo identity PIDi of the vehicle, output the vehicle’s secret value xi if the public key has not been replaced; otherwise, output symbol ⊥.(v)
Vehicle public key replacement queries. Given a query on the pseudo identity PIDi of the vehicle and a new vehicle’s public key Pi′, replace the corresponding vehicle’s public key with a new public key Pi′.(vi)
Sign queries. Given a query on the traffic-related message Mi under PIDi,ti,Pi, output a signature Di,Ri,σi.The security of the proposed CCPPA scheme is defined by the following two interaction games: Game 1 and Game 2 between the adversaryA1 or A2 and a challenger C.Game 1. Security against the Adversary A1. This game is played between the adversary A1 and the challenger C for the proposed CCPPA scheme as follows:(i)
Initialization. The challenger C runs the algorithm System Initialization to generate master key and the system parameters params. Then C returns params to A1.(ii)
Queries. The adversary A1 can adaptively issue H1,H2,H3,H4 and create vehicle, partial private key, secret value, vehicle public key replacement, and sign queries to C.(iii)
Forgery. Eventually, A1 outputs the signature Di∗,Ri∗,σi∗ on Mi∗ under PIDi∗,ti∗,Pi∗ such that(a)
Di∗,Ri∗,σi∗ is a valid signature on Mi∗ under PIDi∗,ti∗,Pi∗.(b)
Mi∗,PIDi∗,ti∗,Pi∗ has not been requested as one of the sign queries.(c)
PIDi∗ has not been requested as one of the secret value queries and the partial private key queries.The success probability of the adversaryA1 wins in Game 1 is defined as SuccA1AUTH.Definition 1.
A CCPPA scheme for VANETs is secure against Type I adversaryA1 if SuccA1AUTH is negligible.Game 2. Security against the Adversary A2. This game is played between the adversary A2 and the challenger C for the proposed CCPPA scheme as follows:(i)
Initialization. The challenger C runs the algorithm System Initialization to generate the master key and system parameters params. Then, C returns the master key and params to A2.(ii)
Queries. A2 can adaptively issue H1,H2,H3,H4, create vehicle, secret value, and sign queries to C. Note that here A2 does not need to issue any partial private key queries, because he has known the master key and has the ability to compute the partial private keys of any vehicles. A2 also cannot replace any public keys of the vehicles.(iii)
Forgery. Eventually, A2 outputs the signature Di∗,Ri∗,σi∗ on Mi∗ under PIDi∗,ti∗,Pi∗ such that(a)
Di∗,Ri∗,σi∗ is a valid signature on Mi∗ under PIDi∗,ti∗,Pi∗.(b)
Mi∗,PIDi∗,ti∗,Pi∗ has not been requested as one of the sign queries.The success probability of the adversaryA2 wins in Game 2 is defined as SuccA2AUTH.Definition 2.
A CCPPA scheme for VANETs is secure against Type II adversaryA2 if SuccA2AUTH is negligible.


### 5.2. Provable Security

Theorem 1.
The proposed CCPPA scheme for VANETs is existentially unforgeable under the ECDL assumption in the random oracle model.Proof.
This theorem is proved based onLemma 1 and Lemma 2.Lemma 1.
The proposed CCPPA scheme for VANETs is existential unforgeable against Type I adversaryA1 under the ECDL assumption in the random oracle model.Proof.
Assuming that polynomially bounded Type I adversaryA1, who can break our proposed scheme with probability ε in time t, there exists an algorithm B that can compute x with a non-negligible probability when receiving a random ECDL problem instance P,xP=Q. The algorithm B runs A1 as subroutine and acts as the challenger C in Game 1 and interacts with A1 as described below.
Initialization. The algorithm B sets Ppub=Q and sends system parameters params=p,q,G,P,Ppub,Tpub,H1,H2,H3,H4 to A1. Here, hash functions H1,H2,H3,H4 are considered as random oracles in the proof.
To keep the consistency and rapidly response,B maintains the initially empty lists as follows:(i)
H1 list LH1list. This list consists of tuples Δi,Ti,τi.(ii)
H2 list LH2list. This list consists of tuples PIDi,Di,Tpub,Ppub,li.(iii)
H3 list LH3list. This list consists of tuples Mi,PIDi,Di,Pi,ti,hi.(iv)
H4 list LH4list. This list consists of tuples Mi,PIDi,Di,Ri,ti,γi.(v)
LPIDlist. This list consists of tuples PIDi,Pi,Di,ki,xi.
H
1 Queries. Suppose A1 submits a query on Δi,Ti, B checks the list LH1list and executes as follows:(i)
If the listLH1list includes Δi,Ti,τi, B responds with previous value τi=H1Δi,Ti to A1.(ii)
If the listLH1list does not include Δi,Ti,τi, B chooses a random number τi∈ℤq, adds Δi,Ti,τi in LH1list and returns τi=H1Δi,Ti to A1.
H
2 Queries. Suppose A1 submits a query on PIDi,Di,Tpub,Ppub, B checks the list LH2list and executes as follows:(i)
If the listLH2list includes PIDi,Di,Tpub,Ppub,li, B responds with previous value li=H2PIDi,Di,Tpub,Ppub to A1.(ii)
If the listLH2list does not include PIDi,Di,Tpub,Ppub,li, B chooses a random number li∈ℤq, adds PIDi,Di,Tpub,Ppub,li in LH2list, and returns li=H2PIDi,Di,Tpub,Ppub to A1.
H
3 Queries. Suppose A1 submits a query on Mi,PIDi,Di,Pi,ti, B checks the list LH3list, and executes as follows:(i)
If the listLH3list includes Mi,PIDi,Di,Pi,ti,hi, B responds with previous value hi=H3Mi,PIDi,Di,Pi,ti to A1.(ii)
If the listLH3list does not include Mi,PIDi,Di,Pi,ti,hi, B chooses a random number hi∈Zq, adds Mi,PIDi,Di,Pi,ti,hi in LH3list, and returns hi=H3Mi,PIDi,Di,Pi,ti to A1.
H
4 Queries. Suppose A1 submits a query on Mi,PIDi,Di,Ri,ti, B checks the list LH4list, and executes as follows:(i)
If the listLH4list includes Mi,PIDi,Di,Ri,ti,γi, B responds with previous value γi=H4Mi,PIDi,Di,Ri,ti to A1.(ii)
If the listLH4list does not include Mi,PIDi,Di,Ri,ti,γi, B chooses a random number γi∈Zq, adds Mi,PIDi,Di,Ri,ti,γi in LH4list, and returns γi=H4Mi,PIDi,Di,Ri,ti to A1.
Create Vehicle Queries. Suppose A1 submits a public key query on a pseudo identity PIDi of the vehicle, B checks the list LPIDlist and executes as follows:(i)
If the listLPIDlist includes PIDi,Pi,Di,ki,xi, B responds with previous value Pi to A1.(ii)
If the listLPIDlist does not include PIDi,Pi,Di,ki,xi, B randomly chooses xi∈Zq, and computes Pi=xiP. Finally, B returns Pi to A1, and inserts PIDi,Pi,Di,ki,xi to LPIDlist.
Partial Private Key Queries. Suppose A1 submits a partial private key query on a pseudo identity PIDi of the vehicle, B checks the list LPIDlist, and executes as follows:(i)
If the listLPIDlist includes PIDi,Pi,Di,ki,xi, B responds with previous value Di,ki to A1.(ii)
If the listLPIDlist does not include PIDi,Pi,Di,ki,xi, B picks random numbers ki,li∈ℤq, and sets li=H2PIDi,Di,Tpub,Ppub and Di=kiP−liPpub. Finally, B returns Di,ki to A1, and inserts PIDi,Di,Tpub,Ppub,li and PIDi,Pi,Di,ki,xi to LH2list and LPIDlist, respectively.
Secret Value Queries. Suppose A1 submits a secret value query on a pseudo identity PIDi of the vehicle, B checks the list LPIDlist, and executes as follows: (i)
If the listLPIDlist includes PIDi,Pi,Di,ki,xi, B responds with previous value xi to A1.(ii)
If the listLPIDlist does not include PIDi,Pi,Di,ki,xi, B makes a create vehicle query itself to generate Pi,xi. Finally, B returns xi to A1 and inserts PIDi,Pi,Di,ki,xi to LPIDlist.
Vehicle Public Key Replacement Queries. Suppose A1 submits a public key replacement query on PIDi,Pi′, B checks the list LPIDlist, and executes as follows:(i)
If the listLPIDlist includes PIDi,Pi,Di,ki,xi, B sets Pi=Pi′ and xi=⊥ and updates PIDi,Pi,Di,ki,xi to LPIDlist.(ii)
If the listLPIDlist does not include PIDi,Pi,Di,ki,xi, B sets Pi=Pi′ and xi=⊥ and inserts PIDi,Pi,Di,ki,xi to LPIDlist.
Sign Queries. Suppose A1 submits a sign query on Mi,PIDi,ti,Pi, B firstly conducts a partial private key query itself to generate Di,ki. B chooses a random value σi∈Zq∗ and computes Ri=γi−1σiP−Di−liPpub−hiPi. If the tuple including γi already appear on the list LH4list, B picks another σi∈Zq∗, and tries again. Finally, B returns Di,Ri,σi to A1.
Forgery. A1 outputs a valid signature Di∗,Ri∗,σi∗ on Mi∗ under PIDi∗,ti∗,Pi∗. Based on the Forking Lemma [42], B can obtain another valid signature Di∗,Ri∗,σi∗′ on Mi∗ under PIDi∗,ti∗,Pi∗ by replaying procedure with the same random tape but a different choice of H2. Then we have(9)σi∗P=Di∗+Li∗Ppub+hi∗Pi∗+γi∗Ri∗,(10)σi∗′P=Di∗+Li∗′Ppub+hi∗Pi∗+γi∗Ri∗.
Following equations (9) and (10), we can obtain(11)σi∗−σi∗′P=σi∗P−σi∗′P=Li∗Ppub−Li∗′Ppub=Li∗−Li∗′Ppub=Li∗−Li∗′xP.
Finally,B outputs x=Li∗−Li∗′−1σi∗−σi∗′, which is the solution to the ECDL problem.
After completing the above simulation, we will analyze the probability and time ofB to solve the ECDL problem instance.
Assuming thatA1 can make at most qHi times Hii=1,2,3,4 queries, qcv times create vehicle queries, qpp times partial private key queries, qsv times secret value queries, qvp times vehicle public key replacement queries, and qs times sign queries.
The probability of failure in handling a partial private key query resulted from a conflict onH2 is at most qH2qpp/q. The probability of failure in handling a sign query caused by a conflict on H4 is at most qsqH4+qs/q. In addition, the probability of A1 outputs a valid forgery without asking the corresponding H2,H3,H4 is at most 3/q. B guesses it correctly as the point of rewind, with probability at least 1/qH2. Therefore, the probability of success of B to solve the ECDL problem is at least ε−qH2qpp+qsqH4+qs+3/q/qH2.
The running time ofB is equal to the running time of A1 plus the time it takes to respond to qcv create vehicle queries, qpp partial private key queries, qsv secret value queries, and qs sign queries. Each create vehicle query requires 1 scale multiplication operation in G. Each partial private key query requires 2 scale multiplication operations in G. Each secret value query requires 1 scale multiplication operation in G. Each sign query requires 2 scale multiplication operations in G. Assuming that each scale multiplication in G needs time tsm, the total running time of B is at most t+2qpp+qcv+qsv+2qstsm.Lemma 2.
The proposed CCPPA scheme for VANETs is existential unforgeable against Type II adversaryA2 under the ECDL assumption in the random oracle model.Proof.
Assuming that a polynomially bounded Type II adversaryA2, who can break our proposed scheme with probability ε in time t, there exists an algorithm B that can compute x with a non-negligible probability when receiving a random ECDL problem instance P,xP=Q. The algorithm B runs A2 as subroutine and acts as the challenger C in Game 2 and interacts with A2 as described below:
Initialization. The algorithm B randomly chooses θ∈ℤq and sets θP=Ppub, then B sends master key θ and system parameters params=p,q,G,P,Ppub,Tpub,H1,H2,H3,H4 to A2. It should be pointed out A2 has the master key and does not require to issue any partial private key query. Similar to Lemma 1, the lists LH1list, LH2list, LH3list, and LH4list are maintained by B. B also keeps a list LPIDlist=PIDi,Pi,Di,ki,xi,ci, which is initial-empty.
Hash H1, H2, H3, H4 queries. It is same to Lemma 1.
Create Vehicle Queries. Suppose A2 submits a public key query on a pseudo identity PIDi of the vehicle, B checks the list LPIDlist, and executes as follows: (i)
If the listLPIDlist includes PIDi,Pi,Di,ki,xi,ci, B responds with previous value Pi to A2.(ii)
If the listLPIDlist does not include PIDi,Pi,Di,ki,xi,ci, using Coron’s technique [43], B tosses a coin ci∈0,1 that yields 1 with probability 1−δ and 0 with probability δ. B randomly chooses a value ki∈Zq. If ci=0, B sets Pi=kiQ; if ci=1, B sets Pi=kiP. Finally, B returns Pi to A2 and inserts PIDi,Pi,Di,ki,xi,ci to LPIDlist.
Secret Value Queries. Suppose A2 submits a secret value query on a pseudo identity PIDi of the vehicle, B checks the list LPIDlist, and executes as follows:(i)
If the listLPIDlist includes PIDi,Pi,Di,ki,xi,ci, if ci=0, B halts; if ci=1, B responds with previous value xi to A2.(ii)
If the listLPIDlist does not include PIDi,Pi,Di,ki,xi,ci, B submits a create vehicle query itself, and inserts PIDi,Pi,Di,ki,xi,ci to LPIDlist. If ci=0, B halts; if ci=1, B returns xi to A2.
Sign Queries. It is the same to Lemma 1.
Forgery. A2 outputs a valid signature Di∗,Ri∗,σi∗ on Mi∗ under PIDi∗,ti∗,Pi∗. Based on the Forking Lemma [42], B can obtain another valid signature Di∗,Ri∗,σi∗′ on Mi∗ under PIDi∗,ti∗,Pi∗ by replaying process with the same random tape but a different choice of H3. Then we have(12)σi∗P=Di∗+Li∗Ppub+hi∗Pi∗+γi∗Ri∗,(13)σi∗′P=Di∗+Li∗Ppub+hi∗′Pi∗+γi∗Ri∗,B checks the LPIDlist, if ci∗=1, B aborts; if ci∗=0, according to equations (12) and (13), we have(14)σi∗−σi∗′P=σi∗P−σi∗′P=hi∗Pi∗−hi∗′Pi∗=hi∗−hi∗′Pi∗=hi∗−hi∗′ki∗xP.
Finally,B outputs hi∗−hi∗′−1ki∗−1σi∗−σi∗′, which is the solution to the ECDL problem.
Same toLemma 1, the analysis on the probability and time of B is as follows.
Assuming thatA2 can make at most qHi times Hii=1,2,3,4 queries, qcv times create vehicle queries, qsv times secret value queries, and qs times sign queries.
The probability of failure in handing a sign query because of a conflict onH4 is at most qsqH4+qs/q. In a secret value query and forgery phase, the probability of success is 1−δqsvδ according to Coron’s technique [43]. When the optimal probability is δ=1/qsv+1, it is greater than 1/eqsv+1. The probability of A2 outputs a valid forgery signature without asking the corresponding H2 or H3 or H4 is at most 3/q. B guesses it correctly as the point of rewind, with probability at least 1/qH3. Therefore, the probability of success of B to solve the ECDL problem is at least ε−qsqH4+qs+3/q/eqsv+1qH3.
The running time ofB is equal to the running time of A2 plus the time it takes to respond to qcv create vehicle queries, qsv secret value queries, and qs sign queries. Each create vehicle query requires 1 scale multiplication operation in G. Each secret value query requires 1 scale multiplication operation in G. Each sign query requires 2 scale multiplication operations in G. Assuming that each scale multiplication in G needs time tsm, the total running time of B is at most t+qcv+qsv+2qstsm.


### 5.3. Analysis and Comparison of Security Requirements

An evaluation on the security of the proposed scheme as well as its comparison with other schemes is conducted in this subsection.Message Authentication. As Theorem 1, any polynomial-time adversary cannot be able to forge a valid signature due to the assumption that the ECDL problem is hard. By verifying whether equation (6) holds, a verifier (RSU) can confirm the validity and integrity of a message Mi,PIDi,ti,Pi,Di,Ri,σi. Therefore, the message authentication can be ensured in the proposed CCPPA scheme.Identity Privacy Preserving. In the proposed scheme, the vehicle broadcasts the message Mi,PIDi,ti,Pi,Di,Ri,σi, by PIDi,1=wiP and PIDi,2=RIDi⊕H1wiTpub,Ti, where the real identity RIDi of the vehicle Vi is perfectly hidden in random pseudo identity PIDi. To extract the vehicle Vi’s real identity RIDi, the adversary should compute PIDi,2=RIDi⊕H1wiTpub,Ti=RIDi⊕H1wi⋅t⋅P,Ti. However, without knowing wi and t, it is impossible for any adversary to obtain RIDi because it is an instance of ECCDH problem to solve wi⋅t⋅P. Hence, any adversary is not able to obtain the real identity RIDi of the vehicle, even if he/or she knows the pseudo identity PIDi. Therefore, the identity preserving can be ensured in the proposed CCPPA scheme.Traceability. The real identity RIDi of the vehicle Vi is involved in a pseudo identity PIDi, where Tpub=tP, PIDi,1=wiP, PIDi,2=RIDi⊕H1wiTpub,Ti, and PIDi=PIDi,1,PIDi,2,Ti. By computing t⋅PIDi,1=t⋅wi⋅P=wi⋅t⋅P=wi⋅Tpub and RIDi=PIDi,2⊕H1wiTpub,Ti, the TRA can extract the real identity RIDi using its own master key t. Therefore, the proposed CCPPA scheme satisfies the traceability.Unlinkability. In the proposed scheme, the TRA, KGC, and the vehicle randomly select wi∈Zq∗, di∈Zq∗ and ri∈Zq∗, respectively, and generate a message Mi,PIDi,ti,Pi,Di,Ri,σi, where PIDi,1=wiP, PIDi,2=RIDi⊕H1wiTpub,Ti, PIDi=PIDi,1,PIDi,2,Ti, Di=diP, ki=di+sH2PIDi,Di,Tpub,Ppub, Ri=riP, and σi=ki+xiH3Mi,PIDi,Di,Pi,ti+riH4Mi,PIDi,Di,Ri,ti. Owning to the randomness of wi, di, and ri, any adversary is unable to link two messages sent from the same vehicle or two anonymous pseudo identities. Therefore, the proposed CCPPA scheme realizes the unlinkability.Role Separation. There are two trusted authorities, namely, KGC and TRA, in the proposed scheme. The real identity of a vehicle can be only revealed by TRA, even if KGC cannot have the capability to do this. Here, t must be strongly protected in order to achieve the vehicle’s anonymous, in which the threshold cryptography [44] would be a better candidate. But, the master key s of KGC should not be strongly protected, because no adversaries can generate a valid message under only knowing s without the vehicle’s secret value.Key Escrow Resilience. In the proposed scheme, the private key of the vehicle Vi includes the secret value xi and partial private key Di,ki, where the vehicle Vi calculates the secret value xi itself, and it cannot be accessed by the KGC. Hence, the malicious KGC cannot impersonate a vehicle to generate a valid signature without knowing the secret value xi. The key escrow resilience is satisfied in the proposed CCPPA scheme.Resistance to Attacks. The proposed CCPPA scheme can resist the main security attacks of VANETs as follows:(i)
Replay attack. Replay attack is a class of network attack with repeating valid messages fraudulently. In the proposed scheme, the timestamp ti is involved in a message Mi,PIDi,ti,Pi,Di,Ri,σi. By checking freshness of ti, the verifier (RSU) can withstand any replay attacks.(ii)
Modification attack. In the proposed CCPPA scheme, a digital signature on the traffic-related message Mi under PIDi,ti,Pi is the tuples Di,Ri,σi. According to Theorem 1, any modified message Mi,PIDi,ti,Pi,Di,Ri,σi made by an adversary cannot satisfy equations (6).(iii)
Impersonation attack. To launch an impersonation attack, an adversary needs to generate a fake message Mi,PIDi,ti,Pi,Di,Ri,σi that satisfies equations (6). However, according to Theorem 1, the probability of the forged message for the adversary to satisfy equation (6) can be negligible.(iv)
Man-in-the-middle attack. Based on the aforementioned analysis for message authentication and modification attack, any modification about message in transmitting can be found by verifying equation (6).Table2 shows the security comparisons of the proposed scheme with related schemes in [22, 25, 27, 30, 31], in which ✔ indicates “satisfy” and ✘ means “not satisfy”.Table 2
Security comparisons.
Security
[22]
[25]
[27]
[30]
[31]
The proposed scheme
Message authentication
✔
✔
✔
✘
✔
✔
Identity privacy preserving
✔
✔
✔
✔
✔
✔
Traceability
✔
✔
✔
✔
✔
✔
Unlinkability
✔
✔
✔
✔
✔
✔
Role separation
✘
✘
✘
✔
✔
✔
Key escrow resilience
✘
✘
✘
✔
✔
✔
Resistance to replay attack
✔
✔
✔
✔
✔
✔
Resistance to modification attack
✔
✔
✔
✘
✔
✔
Resistance to impersonation attack
✔
✔
✔
✘
✔
✔
Resistance to man-in-the-middle attack
✔
✔
✔
✘
✔
✔According to Table2, He et al.’s scheme [22], Lo and Tsai’s scheme [25], and Wu et al.’s scheme [27] cannot provide key escrow resilience, i.e., the vehicles’ private key is entirely generated by the KGC, and it is not fully trusted, it can impersonate any legal vehicle whenever it wants. This may be a strong assumption in VANETs that the KGC is fully trusted for solving key escrow problem. In addition, Horng et al.’s scheme [30] cannot achieve message authentication and resist modification attack, impersonation attack and man-in-the-middle attack. In contrast, the proposed scheme can satisfy all security requirements. Therefore, the proposed scheme has better security than the schemes in [22, 25, 27, 30].


## 5.1. Security Model

According to certificateless cryptography [32, 38–41], there are two types of adversaries with different capabilities: Type I adversary A1 and Type II adversary A2. The adversary A1 models an outside adversary and acts as a malicious third party while the adversary A2 models an inside adversary and serves as a malicious-but-passive KGC.(i)
Type I adversary A1. The adversary A1 cannot access the master key, but has the ability to replace the vehicle’s public key with a value chosen by itself.(ii)
Type II adversary A2. The adversary A2 can access the master key, but cannot replace the vehicle’s public key.The following queries can be made byA1 and A2 adversaries.(i)
Hash H1,H2,H3,H4 queries. Given a query, output a random value.(ii)
Create vehicle queries. Given a query on the pseudo identity PIDi of the vehicle, output the vehicle’s public key Pi.(iii)
Partial private key queries. Given a query on the pseudo identity PIDi of the vehicle, output the vehicle’s partial private key Di,ki.(iv)
Secret value queries. Given a query on the pseudo identity PIDi of the vehicle, output the vehicle’s secret value xi if the public key has not been replaced; otherwise, output symbol ⊥.(v)
Vehicle public key replacement queries. Given a query on the pseudo identity PIDi of the vehicle and a new vehicle’s public key Pi′, replace the corresponding vehicle’s public key with a new public key Pi′.(vi)
Sign queries. Given a query on the traffic-related message Mi under PIDi,ti,Pi, output a signature Di,Ri,σi.The security of the proposed CCPPA scheme is defined by the following two interaction games: Game 1 and Game 2 between the adversaryA1 or A2 and a challenger C.Game 1. Security against the Adversary A1. This game is played between the adversary A1 and the challenger C for the proposed CCPPA scheme as follows:(i)
Initialization. The challenger C runs the algorithm System Initialization to generate master key and the system parameters params. Then C returns params to A1.(ii)
Queries. The adversary A1 can adaptively issue H1,H2,H3,H4 and create vehicle, partial private key, secret value, vehicle public key replacement, and sign queries to C.(iii)
Forgery. Eventually, A1 outputs the signature Di∗,Ri∗,σi∗ on Mi∗ under PIDi∗,ti∗,Pi∗ such that(a)
Di∗,Ri∗,σi∗ is a valid signature on Mi∗ under PIDi∗,ti∗,Pi∗.(b)
Mi∗,PIDi∗,ti∗,Pi∗ has not been requested as one of the sign queries.(c)
PIDi∗ has not been requested as one of the secret value queries and the partial private key queries.The success probability of the adversaryA1 wins in Game 1 is defined as SuccA1AUTH.Definition 1.
A CCPPA scheme for VANETs is secure against Type I adversaryA1 if SuccA1AUTH is negligible.Game 2. Security against the Adversary A2. This game is played between the adversary A2 and the challenger C for the proposed CCPPA scheme as follows:(i)
Initialization. The challenger C runs the algorithm System Initialization to generate the master key and system parameters params. Then, C returns the master key and params to A2.(ii)
Queries. A2 can adaptively issue H1,H2,H3,H4, create vehicle, secret value, and sign queries to C. Note that here A2 does not need to issue any partial private key queries, because he has known the master key and has the ability to compute the partial private keys of any vehicles. A2 also cannot replace any public keys of the vehicles.(iii)
Forgery. Eventually, A2 outputs the signature Di∗,Ri∗,σi∗ on Mi∗ under PIDi∗,ti∗,Pi∗ such that(a)
Di∗,Ri∗,σi∗ is a valid signature on Mi∗ under PIDi∗,ti∗,Pi∗.(b)
Mi∗,PIDi∗,ti∗,Pi∗ has not been requested as one of the sign queries.The success probability of the adversaryA2 wins in Game 2 is defined as SuccA2AUTH.Definition 2.
A CCPPA scheme for VANETs is secure against Type II adversaryA2 if SuccA2AUTH is negligible.


## 5.2. Provable Security

Theorem 1.
The proposed CCPPA scheme for VANETs is existentially unforgeable under the ECDL assumption in the random oracle model.Proof.
This theorem is proved based onLemma 1 and Lemma 2.Lemma 1.
The proposed CCPPA scheme for VANETs is existential unforgeable against Type I adversaryA1 under the ECDL assumption in the random oracle model.Proof.
Assuming that polynomially bounded Type I adversaryA1, who can break our proposed scheme with probability ε in time t, there exists an algorithm B that can compute x with a non-negligible probability when receiving a random ECDL problem instance P,xP=Q. The algorithm B runs A1 as subroutine and acts as the challenger C in Game 1 and interacts with A1 as described below.
Initialization. The algorithm B sets Ppub=Q and sends system parameters params=p,q,G,P,Ppub,Tpub,H1,H2,H3,H4 to A1. Here, hash functions H1,H2,H3,H4 are considered as random oracles in the proof.
To keep the consistency and rapidly response,B maintains the initially empty lists as follows:(i)
H1 list LH1list. This list consists of tuples Δi,Ti,τi.(ii)
H2 list LH2list. This list consists of tuples PIDi,Di,Tpub,Ppub,li.(iii)
H3 list LH3list. This list consists of tuples Mi,PIDi,Di,Pi,ti,hi.(iv)
H4 list LH4list. This list consists of tuples Mi,PIDi,Di,Ri,ti,γi.(v)
LPIDlist. This list consists of tuples PIDi,Pi,Di,ki,xi.
H
1 Queries. Suppose A1 submits a query on Δi,Ti, B checks the list LH1list and executes as follows:(i)
If the listLH1list includes Δi,Ti,τi, B responds with previous value τi=H1Δi,Ti to A1.(ii)
If the listLH1list does not include Δi,Ti,τi, B chooses a random number τi∈ℤq, adds Δi,Ti,τi in LH1list and returns τi=H1Δi,Ti to A1.
H
2 Queries. Suppose A1 submits a query on PIDi,Di,Tpub,Ppub, B checks the list LH2list and executes as follows:(i)
If the listLH2list includes PIDi,Di,Tpub,Ppub,li, B responds with previous value li=H2PIDi,Di,Tpub,Ppub to A1.(ii)
If the listLH2list does not include PIDi,Di,Tpub,Ppub,li, B chooses a random number li∈ℤq, adds PIDi,Di,Tpub,Ppub,li in LH2list, and returns li=H2PIDi,Di,Tpub,Ppub to A1.
H
3 Queries. Suppose A1 submits a query on Mi,PIDi,Di,Pi,ti, B checks the list LH3list, and executes as follows:(i)
If the listLH3list includes Mi,PIDi,Di,Pi,ti,hi, B responds with previous value hi=H3Mi,PIDi,Di,Pi,ti to A1.(ii)
If the listLH3list does not include Mi,PIDi,Di,Pi,ti,hi, B chooses a random number hi∈Zq, adds Mi,PIDi,Di,Pi,ti,hi in LH3list, and returns hi=H3Mi,PIDi,Di,Pi,ti to A1.
H
4 Queries. Suppose A1 submits a query on Mi,PIDi,Di,Ri,ti, B checks the list LH4list, and executes as follows:(i)
If the listLH4list includes Mi,PIDi,Di,Ri,ti,γi, B responds with previous value γi=H4Mi,PIDi,Di,Ri,ti to A1.(ii)
If the listLH4list does not include Mi,PIDi,Di,Ri,ti,γi, B chooses a random number γi∈Zq, adds Mi,PIDi,Di,Ri,ti,γi in LH4list, and returns γi=H4Mi,PIDi,Di,Ri,ti to A1.
Create Vehicle Queries. Suppose A1 submits a public key query on a pseudo identity PIDi of the vehicle, B checks the list LPIDlist and executes as follows:(i)
If the listLPIDlist includes PIDi,Pi,Di,ki,xi, B responds with previous value Pi to A1.(ii)
If the listLPIDlist does not include PIDi,Pi,Di,ki,xi, B randomly chooses xi∈Zq, and computes Pi=xiP. Finally, B returns Pi to A1, and inserts PIDi,Pi,Di,ki,xi to LPIDlist.
Partial Private Key Queries. Suppose A1 submits a partial private key query on a pseudo identity PIDi of the vehicle, B checks the list LPIDlist, and executes as follows:(i)
If the listLPIDlist includes PIDi,Pi,Di,ki,xi, B responds with previous value Di,ki to A1.(ii)
If the listLPIDlist does not include PIDi,Pi,Di,ki,xi, B picks random numbers ki,li∈ℤq, and sets li=H2PIDi,Di,Tpub,Ppub and Di=kiP−liPpub. Finally, B returns Di,ki to A1, and inserts PIDi,Di,Tpub,Ppub,li and PIDi,Pi,Di,ki,xi to LH2list and LPIDlist, respectively.
Secret Value Queries. Suppose A1 submits a secret value query on a pseudo identity PIDi of the vehicle, B checks the list LPIDlist, and executes as follows: (i)
If the listLPIDlist includes PIDi,Pi,Di,ki,xi, B responds with previous value xi to A1.(ii)
If the listLPIDlist does not include PIDi,Pi,Di,ki,xi, B makes a create vehicle query itself to generate Pi,xi. Finally, B returns xi to A1 and inserts PIDi,Pi,Di,ki,xi to LPIDlist.
Vehicle Public Key Replacement Queries. Suppose A1 submits a public key replacement query on PIDi,Pi′, B checks the list LPIDlist, and executes as follows:(i)
If the listLPIDlist includes PIDi,Pi,Di,ki,xi, B sets Pi=Pi′ and xi=⊥ and updates PIDi,Pi,Di,ki,xi to LPIDlist.(ii)
If the listLPIDlist does not include PIDi,Pi,Di,ki,xi, B sets Pi=Pi′ and xi=⊥ and inserts PIDi,Pi,Di,ki,xi to LPIDlist.
Sign Queries. Suppose A1 submits a sign query on Mi,PIDi,ti,Pi, B firstly conducts a partial private key query itself to generate Di,ki. B chooses a random value σi∈Zq∗ and computes Ri=γi−1σiP−Di−liPpub−hiPi. If the tuple including γi already appear on the list LH4list, B picks another σi∈Zq∗, and tries again. Finally, B returns Di,Ri,σi to A1.
Forgery. A1 outputs a valid signature Di∗,Ri∗,σi∗ on Mi∗ under PIDi∗,ti∗,Pi∗. Based on the Forking Lemma [42], B can obtain another valid signature Di∗,Ri∗,σi∗′ on Mi∗ under PIDi∗,ti∗,Pi∗ by replaying procedure with the same random tape but a different choice of H2. Then we have(9)σi∗P=Di∗+Li∗Ppub+hi∗Pi∗+γi∗Ri∗,(10)σi∗′P=Di∗+Li∗′Ppub+hi∗Pi∗+γi∗Ri∗.
Following equations (9) and (10), we can obtain(11)σi∗−σi∗′P=σi∗P−σi∗′P=Li∗Ppub−Li∗′Ppub=Li∗−Li∗′Ppub=Li∗−Li∗′xP.
Finally,B outputs x=Li∗−Li∗′−1σi∗−σi∗′, which is the solution to the ECDL problem.
After completing the above simulation, we will analyze the probability and time ofB to solve the ECDL problem instance.
Assuming thatA1 can make at most qHi times Hii=1,2,3,4 queries, qcv times create vehicle queries, qpp times partial private key queries, qsv times secret value queries, qvp times vehicle public key replacement queries, and qs times sign queries.
The probability of failure in handling a partial private key query resulted from a conflict onH2 is at most qH2qpp/q. The probability of failure in handling a sign query caused by a conflict on H4 is at most qsqH4+qs/q. In addition, the probability of A1 outputs a valid forgery without asking the corresponding H2,H3,H4 is at most 3/q. B guesses it correctly as the point of rewind, with probability at least 1/qH2. Therefore, the probability of success of B to solve the ECDL problem is at least ε−qH2qpp+qsqH4+qs+3/q/qH2.
The running time ofB is equal to the running time of A1 plus the time it takes to respond to qcv create vehicle queries, qpp partial private key queries, qsv secret value queries, and qs sign queries. Each create vehicle query requires 1 scale multiplication operation in G. Each partial private key query requires 2 scale multiplication operations in G. Each secret value query requires 1 scale multiplication operation in G. Each sign query requires 2 scale multiplication operations in G. Assuming that each scale multiplication in G needs time tsm, the total running time of B is at most t+2qpp+qcv+qsv+2qstsm.Lemma 2.
The proposed CCPPA scheme for VANETs is existential unforgeable against Type II adversaryA2 under the ECDL assumption in the random oracle model.Proof.
Assuming that a polynomially bounded Type II adversaryA2, who can break our proposed scheme with probability ε in time t, there exists an algorithm B that can compute x with a non-negligible probability when receiving a random ECDL problem instance P,xP=Q. The algorithm B runs A2 as subroutine and acts as the challenger C in Game 2 and interacts with A2 as described below:
Initialization. The algorithm B randomly chooses θ∈ℤq and sets θP=Ppub, then B sends master key θ and system parameters params=p,q,G,P,Ppub,Tpub,H1,H2,H3,H4 to A2. It should be pointed out A2 has the master key and does not require to issue any partial private key query. Similar to Lemma 1, the lists LH1list, LH2list, LH3list, and LH4list are maintained by B. B also keeps a list LPIDlist=PIDi,Pi,Di,ki,xi,ci, which is initial-empty.
Hash H1, H2, H3, H4 queries. It is same to Lemma 1.
Create Vehicle Queries. Suppose A2 submits a public key query on a pseudo identity PIDi of the vehicle, B checks the list LPIDlist, and executes as follows: (i)
If the listLPIDlist includes PIDi,Pi,Di,ki,xi,ci, B responds with previous value Pi to A2.(ii)
If the listLPIDlist does not include PIDi,Pi,Di,ki,xi,ci, using Coron’s technique [43], B tosses a coin ci∈0,1 that yields 1 with probability 1−δ and 0 with probability δ. B randomly chooses a value ki∈Zq. If ci=0, B sets Pi=kiQ; if ci=1, B sets Pi=kiP. Finally, B returns Pi to A2 and inserts PIDi,Pi,Di,ki,xi,ci to LPIDlist.
Secret Value Queries. Suppose A2 submits a secret value query on a pseudo identity PIDi of the vehicle, B checks the list LPIDlist, and executes as follows:(i)
If the listLPIDlist includes PIDi,Pi,Di,ki,xi,ci, if ci=0, B halts; if ci=1, B responds with previous value xi to A2.(ii)
If the listLPIDlist does not include PIDi,Pi,Di,ki,xi,ci, B submits a create vehicle query itself, and inserts PIDi,Pi,Di,ki,xi,ci to LPIDlist. If ci=0, B halts; if ci=1, B returns xi to A2.
Sign Queries. It is the same to Lemma 1.
Forgery. A2 outputs a valid signature Di∗,Ri∗,σi∗ on Mi∗ under PIDi∗,ti∗,Pi∗. Based on the Forking Lemma [42], B can obtain another valid signature Di∗,Ri∗,σi∗′ on Mi∗ under PIDi∗,ti∗,Pi∗ by replaying process with the same random tape but a different choice of H3. Then we have(12)σi∗P=Di∗+Li∗Ppub+hi∗Pi∗+γi∗Ri∗,(13)σi∗′P=Di∗+Li∗Ppub+hi∗′Pi∗+γi∗Ri∗,B checks the LPIDlist, if ci∗=1, B aborts; if ci∗=0, according to equations (12) and (13), we have(14)σi∗−σi∗′P=σi∗P−σi∗′P=hi∗Pi∗−hi∗′Pi∗=hi∗−hi∗′Pi∗=hi∗−hi∗′ki∗xP.
Finally,B outputs hi∗−hi∗′−1ki∗−1σi∗−σi∗′, which is the solution to the ECDL problem.
Same toLemma 1, the analysis on the probability and time of B is as follows.
Assuming thatA2 can make at most qHi times Hii=1,2,3,4 queries, qcv times create vehicle queries, qsv times secret value queries, and qs times sign queries.
The probability of failure in handing a sign query because of a conflict onH4 is at most qsqH4+qs/q. In a secret value query and forgery phase, the probability of success is 1−δqsvδ according to Coron’s technique [43]. When the optimal probability is δ=1/qsv+1, it is greater than 1/eqsv+1. The probability of A2 outputs a valid forgery signature without asking the corresponding H2 or H3 or H4 is at most 3/q. B guesses it correctly as the point of rewind, with probability at least 1/qH3. Therefore, the probability of success of B to solve the ECDL problem is at least ε−qsqH4+qs+3/q/eqsv+1qH3.
The running time ofB is equal to the running time of A2 plus the time it takes to respond to qcv create vehicle queries, qsv secret value queries, and qs sign queries. Each create vehicle query requires 1 scale multiplication operation in G. Each secret value query requires 1 scale multiplication operation in G. Each sign query requires 2 scale multiplication operations in G. Assuming that each scale multiplication in G needs time tsm, the total running time of B is at most t+qcv+qsv+2qstsm.


## 5.3. Analysis and Comparison of Security Requirements

An evaluation on the security of the proposed scheme as well as its comparison with other schemes is conducted in this subsection.Message Authentication. As Theorem 1, any polynomial-time adversary cannot be able to forge a valid signature due to the assumption that the ECDL problem is hard. By verifying whether equation (6) holds, a verifier (RSU) can confirm the validity and integrity of a message Mi,PIDi,ti,Pi,Di,Ri,σi. Therefore, the message authentication can be ensured in the proposed CCPPA scheme.Identity Privacy Preserving. In the proposed scheme, the vehicle broadcasts the message Mi,PIDi,ti,Pi,Di,Ri,σi, by PIDi,1=wiP and PIDi,2=RIDi⊕H1wiTpub,Ti, where the real identity RIDi of the vehicle Vi is perfectly hidden in random pseudo identity PIDi. To extract the vehicle Vi’s real identity RIDi, the adversary should compute PIDi,2=RIDi⊕H1wiTpub,Ti=RIDi⊕H1wi⋅t⋅P,Ti. However, without knowing wi and t, it is impossible for any adversary to obtain RIDi because it is an instance of ECCDH problem to solve wi⋅t⋅P. Hence, any adversary is not able to obtain the real identity RIDi of the vehicle, even if he/or she knows the pseudo identity PIDi. Therefore, the identity preserving can be ensured in the proposed CCPPA scheme.Traceability. The real identity RIDi of the vehicle Vi is involved in a pseudo identity PIDi, where Tpub=tP, PIDi,1=wiP, PIDi,2=RIDi⊕H1wiTpub,Ti, and PIDi=PIDi,1,PIDi,2,Ti. By computing t⋅PIDi,1=t⋅wi⋅P=wi⋅t⋅P=wi⋅Tpub and RIDi=PIDi,2⊕H1wiTpub,Ti, the TRA can extract the real identity RIDi using its own master key t. Therefore, the proposed CCPPA scheme satisfies the traceability.Unlinkability. In the proposed scheme, the TRA, KGC, and the vehicle randomly select wi∈Zq∗, di∈Zq∗ and ri∈Zq∗, respectively, and generate a message Mi,PIDi,ti,Pi,Di,Ri,σi, where PIDi,1=wiP, PIDi,2=RIDi⊕H1wiTpub,Ti, PIDi=PIDi,1,PIDi,2,Ti, Di=diP, ki=di+sH2PIDi,Di,Tpub,Ppub, Ri=riP, and σi=ki+xiH3Mi,PIDi,Di,Pi,ti+riH4Mi,PIDi,Di,Ri,ti. Owning to the randomness of wi, di, and ri, any adversary is unable to link two messages sent from the same vehicle or two anonymous pseudo identities. Therefore, the proposed CCPPA scheme realizes the unlinkability.Role Separation. There are two trusted authorities, namely, KGC and TRA, in the proposed scheme. The real identity of a vehicle can be only revealed by TRA, even if KGC cannot have the capability to do this. Here, t must be strongly protected in order to achieve the vehicle’s anonymous, in which the threshold cryptography [44] would be a better candidate. But, the master key s of KGC should not be strongly protected, because no adversaries can generate a valid message under only knowing s without the vehicle’s secret value.Key Escrow Resilience. In the proposed scheme, the private key of the vehicle Vi includes the secret value xi and partial private key Di,ki, where the vehicle Vi calculates the secret value xi itself, and it cannot be accessed by the KGC. Hence, the malicious KGC cannot impersonate a vehicle to generate a valid signature without knowing the secret value xi. The key escrow resilience is satisfied in the proposed CCPPA scheme.Resistance to Attacks. The proposed CCPPA scheme can resist the main security attacks of VANETs as follows:(i)
Replay attack. Replay attack is a class of network attack with repeating valid messages fraudulently. In the proposed scheme, the timestamp ti is involved in a message Mi,PIDi,ti,Pi,Di,Ri,σi. By checking freshness of ti, the verifier (RSU) can withstand any replay attacks.(ii)
Modification attack. In the proposed CCPPA scheme, a digital signature on the traffic-related message Mi under PIDi,ti,Pi is the tuples Di,Ri,σi. According to Theorem 1, any modified message Mi,PIDi,ti,Pi,Di,Ri,σi made by an adversary cannot satisfy equations (6).(iii)
Impersonation attack. To launch an impersonation attack, an adversary needs to generate a fake message Mi,PIDi,ti,Pi,Di,Ri,σi that satisfies equations (6). However, according to Theorem 1, the probability of the forged message for the adversary to satisfy equation (6) can be negligible.(iv)
Man-in-the-middle attack. Based on the aforementioned analysis for message authentication and modification attack, any modification about message in transmitting can be found by verifying equation (6).Table2 shows the security comparisons of the proposed scheme with related schemes in [22, 25, 27, 30, 31], in which ✔ indicates “satisfy” and ✘ means “not satisfy”.Table 2
Security comparisons.
Security
[22]
[25]
[27]
[30]
[31]
The proposed scheme
Message authentication
✔
✔
✔
✘
✔
✔
Identity privacy preserving
✔
✔
✔
✔
✔
✔
Traceability
✔
✔
✔
✔
✔
✔
Unlinkability
✔
✔
✔
✔
✔
✔
Role separation
✘
✘
✘
✔
✔
✔
Key escrow resilience
✘
✘
✘
✔
✔
✔
Resistance to replay attack
✔
✔
✔
✔
✔
✔
Resistance to modification attack
✔
✔
✔
✘
✔
✔
Resistance to impersonation attack
✔
✔
✔
✘
✔
✔
Resistance to man-in-the-middle attack
✔
✔
✔
✘
✔
✔According to Table2, He et al.’s scheme [22], Lo and Tsai’s scheme [25], and Wu et al.’s scheme [27] cannot provide key escrow resilience, i.e., the vehicles’ private key is entirely generated by the KGC, and it is not fully trusted, it can impersonate any legal vehicle whenever it wants. This may be a strong assumption in VANETs that the KGC is fully trusted for solving key escrow problem. In addition, Horng et al.’s scheme [30] cannot achieve message authentication and resist modification attack, impersonation attack and man-in-the-middle attack. In contrast, the proposed scheme can satisfy all security requirements. Therefore, the proposed scheme has better security than the schemes in [22, 25, 27, 30].


## 6. Performance Evaluation and Simulation

In this section, the computation delay and communication overhead of the proposed CCPPA scheme are compared with the identity-based CPPA schemes [22, 25, 27] and the certificateless CCPPA schemes [30, 31]. In addition, an extensive simulation is performed using ns-3.26 simulator [45] and the simulation of urban mobility (SUMO) [46]. The ns-3.26 simulator is used for wireless network simulation and SUMO, a traffic simulation tool, provides the realistic traffic mobility model. The simulations are evaluating the average message delay and average message loss ratio in real scenario.


### 6.1. Computation Delay

The computation delay for the message signing and message verification is evaluated. For computation complexity estimation, the time cost for performing the cryptographic operations is defined below. LetTp be the time for performing a bilinear pairing operation, Tmtp be the time for performing a map-to-point hash function operation. The time for performing a scale multiplication operation in bilinear pairing and ECC are denoted as Tm and Tm−ecc, respectively. Because the vi used in batch verification is very small, the computation cost can be negligible. Other lightweight operations (one-way hash function and point addition) are not taken into account.In terms of the proposed CCPPA scheme, He et al.’s scheme [22], Lo and Tsai’s scheme [25], and Wu et al.’s scheme [27], the ECC for the security level of 80 bits can be established as follows: G is an additive group generated by a point P on a non-singular elliptic curve E:y2=x3+ax+bmodp, the order of it is q, where a=−3, b is a random 160-bit prime number and p and q are two 160-bit prime numbers. For the CCPPA schemes in [30, 31], the symmetric bilinear pairing for the security level of 80 bits can be constructed as follows: e:G1×G1⟶GT, where G1 is an additive group formed by a generator P with the order q on a super singular elliptic curve E:y2=x3+xmodp with embedding degree 2. p is 512-bit prime number, and q is 160-bit Solinas prime number, which satisfy q⋅12⋅r=p+1.To quantify the running time of the cryptographic operations, the MIRACL Crypto SDK [47] is used in this paper. The experiment is performed on Intel Corei5-4590, 3.3 GHz CPU, 8 gigabytes memory with Windows 7. The average execution times of Tp, Tmtp, Tm, and Tm−ecc are listed in Table 3.Table 3
Execution time of cryptographic operation (in milliseconds).
Cryptographic operation
Execution time
Bilinear pairingTp
9.0791
Map-to-point hash function in bilinear pairingTmtp
9.7052
Scalar multiplication in bilinear pairingTm
3.7770
Scalar multiplication in ECCTm−ecc
0.8310Based on the experiment results, the computation delay of the proposed CCPPA scheme, He et al.’s scheme [22], Lo and Tsai’s scheme [25], Wu et al.’s scheme [27], Horng et al.’s scheme [30], and Li et al.’s scheme [31] are summarized and shown in Table 4.Table 4
Comparison of computation delay.
Scheme
A message signing
A message verification
n message signing
n message batch verification
[22]
2Tm−ecc = 1.6620 ms
3Tm−ecc = 2.4930 ms
2nTm−ecc = 1.6620n ms
(n+2)Tm−ecc = 0.8310n + 1.6620 ms
[25]
2Tm−ecc = 1.6620 ms
3Tm−ecc = 2.4930 ms
2nTm−ecc = 1.6620n ms
(n+2)Tm−ecc = 0.8310n + 1.6620 ms
[27]
2Tm−ecc = 1.6620 ms
4Tm−ecc = 3.3240 ms
2nTm−ecc = 1.6620n ms
(2n+2)Tm−ecc = 1.6620n + 1.6620 ms
[30]
2Tm = 7.5540 ms
3Tp + Tm + Tmtp = 40.7195 ms
2nTm = 7.5540n ms
3Tp + nTm + nTmtp = 13.4822n + 27.2373 ms
[31]
2Tm + Tmtp = 17.2592 ms
3Tp + Tm + 2Tmtp = 50.4247 ms
2nTm+nTmtp = 17.2592n ms
3Tp + nTm + (n + 1)Tmtp = 13.4822n + 36.9425 ms
The proposed scheme
3Tm−ecc = 2.4930 ms
4Tm−ecc = 3.3240 ms
3nTm−ecc = 2.4930n ms
(2n+2)Tm−ecc = 1.6620n + 1.6620 msIn terms of the computation delay of one message signing, He et al.’s scheme [22], Lo and Tsai’s scheme [25], and Wu et al.’s scheme [27] require two scalar multiplication operations in ECC. Therefore, the total signing time is 2Tm−ecc = 1.6620 ms. Horng et al.’s scheme [30] requires two scalar multiplication operations in bilinear pairing. Therefore, the total signing time is 2Tm = 7.5540 ms. Li et al.’s scheme [31] requires two scalar multiplication operations in bilinear pairing and one map-to-point hash operation. Therefore, the total signing time is 2Tm + Tmtp = 17.2592 ms. The proposed scheme requires three scalar multiplication operations in ECC. Therefore, the total signing time is 3Tm−ecc = 2.4930 ms.In terms of the computation delay of one message verification, He et al.’s scheme [22] and Lo and Tsai’s scheme [25] require three scalar multiplication operations in ECC. Therefore, the total verification time is 3Tm−ecc = 2.4930 ms. Wu et al.’s scheme [27] requires four scalar multiplication operations in ECC. Therefore, the total verification time is 4Tm−ecc = 3.3240 ms. Horng et al.’s scheme [30] requires three bilinear pairing operations, one scalar multiplication operation in bilinear pairing and one map-to-point hash operation. Therefore, the total verification time is 3Tp + Tm + Tmtp = 40.7195 ms. Li et al.’s scheme [31] requires three bilinear pairing operations, one scalar multiplication operation in bilinear pairing, and two map-to-point hash operations. Therefore, the total verification time is 3Tp + Tm + 2Tmtp = 50.4247 ms. The proposed scheme requires four scalar multiplication operations in ECC. Therefore, the total verification time is 4Tm−ecc = 3.3240 ms.The computation delay for one message and its correlation with the number of messages (n) are shown in Figure 3. It is known from Table 4 and Figure 3(a), the computation delay of a message signing is 2.4930 ms in the proposed scheme, which decreases by 66.9% and 85.5% compared with those in Horng et al.’s scheme [30] and Li et al.’s scheme [31], respectively. In terms of computation delay of a message verification, the proposed scheme needs 3.3240 ms, which decreases by 91.8% and 93.4% compared with those in Horng et al.’s scheme [30] and Li et al.’s scheme [31], respectively.Figure 3
Computation delay. (a) Computation delay in one message signing and verification. (b) Signing delay vs number of messages. (c) Verification delay vs number of messages.
(a)
(b)
(c)To obtain computation delay of multiple (n) messages signing, the computation delay of one message signing should be repeated n times. Therefore, the total n messages signing times in the proposed scheme, He et al.’s scheme [22], Lo and Tsai’s scheme [25], Wu et al.’s scheme [27], Horng et al.’s scheme [30], and Li et al.’s scheme [31] are 2.4930n ms, 1.6620n ms, 1.6620n ms, 1.6620n ms, 7.5540n ms, and 17.2592n ms, respectively. To obtain the computation delay of multiple (n) messages verification, He et al.’s scheme [22] and Lo and Tsai’s scheme [25] require (n+2) scalar multiplication operations in ECC. Therefore, the total verification time is (n+2)Tm−ecc = 0.8310n + 1.6620 ms. Wu et al.’s scheme [27] requires (2n+2) scalar multiplication operations in ECC. Therefore, the total verification time is (2n+2)Tm−ecc = 1.6620n + 1.6620 ms. Horng et al.’s scheme [30] requires three bilinear pairing operations, n scalar multiplication operations in bilinear pairing, and n map-to-point hash operations. Therefore, the total verification time is 3Tp + nTm + nTmtp = 13.4822n + 27.2373 ms. Li et al.’s scheme [31] requires three bilinear pairing operations, n scalar multiplication operations in bilinear pairing, and (n+1) map-to-point hash operations. Therefore, the total verification time is 3Tp + nTm + n+1Tmtp = 13.4822n + 36.9425 ms. The proposed scheme requires (2n+2) scalar multiplication operations in ECC. Therefore, the total verification time is (2n+2)Tm−ecc = 1.6620n + 1.6620 ms.As is shown in Figure3(b) and Figure 3(c), that with the increase of number of messages, the signing delay and verification delay grows linearly in all schemes. And the proposed scheme has the lowest slope compared with schemes [30, 31]. It is shown in Figure 3(c), the verification delay of the schemes in [22, 25, 27, 30] and [31] and the proposed scheme, respectively, is 9.9720 ms, 9.9720 ms, 18.2820 ms, 162.0593 ms, 171.7645 ms, and 18.2820 ms when n = 10, and 51.5520 ms, 51.5520 ms, 101.3830 ms, 836.1693 ms, 845.8745 ms, and 101.3830 ms when n = 60. Apparently, the proposed scheme achieves the lowest verification delay as the number of messages grows in all CCPPA schemes.Therefore, the proposed scheme has much more superiority than other CCPPA schemes in [30, 31] in the signing and verification process, regardless of the number of messages, and is more suitable for VANETs. The proposed CCPPA scheme is slightly less efficient than He et al.’s scheme [22], Lo and Tsai’s scheme [25], and Wu et al.’s scheme [27]. This degradation is forgivable due to the fact that the proposed scheme is a certificateless system and provides key escrow resilience, however, is not the case in [22, 25, 27].


### 6.2. Communication Cost

In this subsection, the proposed scheme is compared with He et al.’s scheme [22], Lo and Tsai’s scheme [25], Wu et al.’s scheme [27], Horng et al.’s scheme [30], and Li et al.’s scheme [31] in terms of the communication cost. In V2I communication, the communication cost refers to the size of message transmitted from a vehicle (OBU) to an RSU. Just as the before analysis, the length of p is 512 bits (64 bytes) and that of q is 160 bits (20 bytes), so the length of elements in G1 and G, respectively, are 64 bytes and 20 bytes. Assuming the length of output of general one-way hash function is 160 bits (20 bytes), and the length of a timestamp is 32 bits (4 bytes). According to the IEEE Trial-Use standard [48] for VANET security, the length of message is defined as 67 bytes. Table 5 illustrates the comparison of communication costs.Table 5
Comparison of communication cost.
Scheme
Send a message
Sendn messages
[22]
155 bytes
155n bytes
[25]
175 bytes
175n bytes
[27]
175 bytes
175n bytes
[30]
351 bytes
351n bytes
[31]
351 bytes
351n bytes
The proposed scheme
195 bytes
195n bytesIn He et al.’s scheme [22], the message Mi,PIDi,ti,Ri,σi is sent from the vehicle to a RSU, where PIDi=PIDi,1,PIDi,2,Ti, PIDi,1∈G, PIDi,2∈Zq, and Ti is the timestamp. Thus, the communication cost of He et al.’s scheme is 155 bytes as(15)Mi+PIDi+ti+Ri+σi=67+44+4+20+20=155bytes.In Lo and Tsai’s scheme [25], the message Mi,PIDi,tti,Ki,Ri,Vi is sent from the vehicle to a RSU, where PIDi=PIDi,1,PIDi,2,ti, PIDi,1∈G, PIDi,2∈Zq and ti is the timestamp. Thus, the communication cost of Lo and Tsai’s scheme is 175 bytes as(16)Mi+PIDi+tti+Ki+Ri+Vi=67+44+4+20+20+20=175bytes.In Wu et al.’s scheme [27], the message Mi,PIDi,Ti,hi,Ri,δi is sent from the vehicle to a RSU, where PIDi=PIDvi,kvi,Tvi, PIDvi∈G, kvi∈Zq, and Tvi is the timestamp. Thus, the communication cost of Wu et al.’s scheme is 175 bytes as(17)Mi+PIDi+Ti+hi+Ri+δi=67+44+4+20+20+20=175bytes.In Horng et al.’s scheme [30] and Li et al.’s scheme [31], the message Mi,PIDi,ti,Pi,Ri,Si is sent from the vehicle to a RSU, where PIDi=PIDi,1,PIDi,2,Ti, PIDi,1∈G1, PIDi,2∈Zq, and Ti is the timestamp. Thus, the communication cost of these two schemes is 351 bytes as(18)Mi+PIDi+ti+Pi+Ri+Si=67+88+4+64+64+64=351bytes.In the proposed scheme, the messageMi,PIDi,ti,Pi,Di,Ri,σi is sent from the vehicle to a RSU, where PIDi is the same one as [22]. Thus, the communication cost of the proposed scheme is 195 bytes as(19)Mi+PIDi+ti+Pi+Di+Ri+σi=67+44+4+20+20+20+20=195bytes.The comparison on the communication costs of one message and multiple messages is shown in Figure4. Clearly, the communication costs increase linearly as the number of messages increases in six schemes. The same communication costs exist in the ID-based schemes [25, 27] and the certificateless schemes [30, 31], whether one message or multiple messages are transmitted. The communication cost of the proposed scheme is the lowest in the CCPPA schemes, which significantly decreases by 44.44%. When the number of messages rises to 30 000, the proposed scheme can save 4.46 MB of bandwidth compared with the schemes in [30, 31]. The communication cost of the proposed scheme is slightly larger than that of He et al.’s scheme [22], Lo and Tsai’s scheme [25], and Wu et al.’s scheme [27]. The reason is that the proposed scheme is a certificatless scheme, in which an additional user’s public key is needed to transmit.Figure 4
Communication cost. (a) Communication cost of one message. (b) Communication cost vs number of messages.
(a)
(b)


### 6.3. Simulations

The popular network simulator ns-3.26 [45] on a Ubuntu platform is adopted to evaluate the performances of the proposed CCPPA scheme by comparing with those of He et al.’s scheme [22], Lo and Tsai’s scheme [25], Wu et al.’s scheme [27], Horng et al.’s scheme [30], and Li et al.’s scheme [31]. In addition, a road traffic simulator SUMO [46] is used to generate a realistic traffic mobility trace for the road scenario shown in Figure 5.Figure 5
Road scenario for simulation.In our road scenario, the RSUs are assigned every 500 m along each road, and each vehicle broadcasts traffic-related messages every 300 ms. The vehicles are distributed at random on the road and move toward randomly selected intersections. The important simulation parameters are summarized in Table6.Table 6
Simulation parameters.
Parameters
Values
Wireless protocol
802.11p
Channel bandwidth
6 mbs
Buffer size
1 M bytes
Simulation area
1000 m× 1000 m
Number of RSU
9
Simulation time
200 s
Network simulation tool
ns-3.26
Traffic simulation tool
SUMO
Vehicle speed
10–50 m/sGenerally, the average message delayavgMD and average message loss ratio avgMLR in RSUs are adopted to estimate the performances.TheavgMD is defined as(20)avgMD=∑i=1NV∑​j=1NR∑​k=1NMiTVi⟶Rj,MkRecv−TVi⟶Rj,MkSend∑​i=1NVNMi+TavgVerify,where NV and NR indicates the number of vehicles and RSUs in simulation area, respectively. NMi represents the number of messages that sent from vehicle Vi. TVi⟶Rj,MkRecv is the time for Rj (a RSU) receiving a message Mk from Vi and TVi⟶Rj,MkSend is the time for Vi sending a message Mk to Rj (a RSU). TavgVerify means the average verification time for each message.TheavgMLR refers to the ratio of the number of messages dropped over the total number of messages received by the RSUs, which is defined as(21)avgMLR=1NR∑j=1NRNDroppedjNReceivedj,where NDroppedj indicates the number of messages dropped by Rj (a RSU) in the application layer and NReceivedj represents the number of messages received by Rj (a RSU) in MAC layer. We emphasize that the avgMLR occurs by the security protocol and the buffer space of the RSU, rather than the wireless transmission channel.


#### 6.3.1. Impact of Vehicle Density

Two experiments are conducted to analyze the influence of the vehicle density onavgMD and avgMLR. The number of vehicles varies from 20 to 100, and the average speed of vehicles is approximately 20 m/s (72 km/h). The simulation results under the different vehicle densities are shown in Figure 6.Figure 6
Average message delay and message loss ratio under different number of vehicles. (a) Average message delay vs number of vehicles. (b) Average message loss ratio vs number of vehicles.
(a)
(b)Figure6(a) reveals the relationship between avgMD and the number of vehicles. The avgMD for RSUs increases with the number of vehicles. The avgMD is 0.005 s, 0.004 s, 0.006 s, 2.94 s, 2.98 s, and 0.006 s in He et al.’s scheme [22], Lo and Tsai’s scheme [25], Wu et al.’s scheme [27], Horng et al.’s scheme [30], Li et al.’s scheme [31], and the proposed scheme, respectively. Clearly, the avgMD of the proposed scheme and schemes in [22, 25, 27] is very low and hardly affected by vehicle density.Figure6(b) describes the relationship between avgMLR and the number of vehicles. While the number of vehicles in the communication range is larger than 20, the avgMLR increases along with the number of vehicles in Horng et al.’s scheme [30] and Li et al.’s scheme [31] and reaches as high as 57% when the number of vehicles is 100. However, for the proposed scheme and schemes in [22, 25, 27], the avgMLR remains nearly 0 regardless of the vehicle density.


#### 6.3.2. Impact of Vehicle Speed

Two experiments are conducted to evaluate the impact of speed of vehicles onavgMD and avgMLR. The average vehicle speed is varies from 10 to 50 m/s (36 to 180 km/h) and the number of vehicles is 50. The results obtained from the simulation under varying speed of vehicles are depicted in Figure 7.Figure 7
Average message delay and message loss ratio under different speed of vehicles. (a) Average message delay vs speed of vehicles. (b) Average message loss ratio vs speed of vehicles.
(a)
(b)Figure7(a) shows the relationship between avgMD and the speed of vehicles. Obviously, when the vehicle density is constant, the avgMD hardly changes, showing that it is merely little influenced by the speed of vehicles.Figure7(b) depicts the relationship between avgMLR and the speed of vehicles. When the speed of vehicles is higher than 20 m/s, the avgMLRs in Horng et al.’s scheme [30] and Li et al.’s scheme [31] are slightly influenced. As speed of vehicles gets larger, the avgMLR of the proposed scheme and schemes in [22, 25, 27] has been steady at a very low level.


## 6.1. Computation Delay

The computation delay for the message signing and message verification is evaluated. For computation complexity estimation, the time cost for performing the cryptographic operations is defined below. LetTp be the time for performing a bilinear pairing operation, Tmtp be the time for performing a map-to-point hash function operation. The time for performing a scale multiplication operation in bilinear pairing and ECC are denoted as Tm and Tm−ecc, respectively. Because the vi used in batch verification is very small, the computation cost can be negligible. Other lightweight operations (one-way hash function and point addition) are not taken into account.In terms of the proposed CCPPA scheme, He et al.’s scheme [22], Lo and Tsai’s scheme [25], and Wu et al.’s scheme [27], the ECC for the security level of 80 bits can be established as follows: G is an additive group generated by a point P on a non-singular elliptic curve E:y2=x3+ax+bmodp, the order of it is q, where a=−3, b is a random 160-bit prime number and p and q are two 160-bit prime numbers. For the CCPPA schemes in [30, 31], the symmetric bilinear pairing for the security level of 80 bits can be constructed as follows: e:G1×G1⟶GT, where G1 is an additive group formed by a generator P with the order q on a super singular elliptic curve E:y2=x3+xmodp with embedding degree 2. p is 512-bit prime number, and q is 160-bit Solinas prime number, which satisfy q⋅12⋅r=p+1.To quantify the running time of the cryptographic operations, the MIRACL Crypto SDK [47] is used in this paper. The experiment is performed on Intel Corei5-4590, 3.3 GHz CPU, 8 gigabytes memory with Windows 7. The average execution times of Tp, Tmtp, Tm, and Tm−ecc are listed in Table 3.Table 3
Execution time of cryptographic operation (in milliseconds).
Cryptographic operation
Execution time
Bilinear pairingTp
9.0791
Map-to-point hash function in bilinear pairingTmtp
9.7052
Scalar multiplication in bilinear pairingTm
3.7770
Scalar multiplication in ECCTm−ecc
0.8310Based on the experiment results, the computation delay of the proposed CCPPA scheme, He et al.’s scheme [22], Lo and Tsai’s scheme [25], Wu et al.’s scheme [27], Horng et al.’s scheme [30], and Li et al.’s scheme [31] are summarized and shown in Table 4.Table 4
Comparison of computation delay.
Scheme
A message signing
A message verification
n message signing
n message batch verification
[22]
2Tm−ecc = 1.6620 ms
3Tm−ecc = 2.4930 ms
2nTm−ecc = 1.6620n ms
(n+2)Tm−ecc = 0.8310n + 1.6620 ms
[25]
2Tm−ecc = 1.6620 ms
3Tm−ecc = 2.4930 ms
2nTm−ecc = 1.6620n ms
(n+2)Tm−ecc = 0.8310n + 1.6620 ms
[27]
2Tm−ecc = 1.6620 ms
4Tm−ecc = 3.3240 ms
2nTm−ecc = 1.6620n ms
(2n+2)Tm−ecc = 1.6620n + 1.6620 ms
[30]
2Tm = 7.5540 ms
3Tp + Tm + Tmtp = 40.7195 ms
2nTm = 7.5540n ms
3Tp + nTm + nTmtp = 13.4822n + 27.2373 ms
[31]
2Tm + Tmtp = 17.2592 ms
3Tp + Tm + 2Tmtp = 50.4247 ms
2nTm+nTmtp = 17.2592n ms
3Tp + nTm + (n + 1)Tmtp = 13.4822n + 36.9425 ms
The proposed scheme
3Tm−ecc = 2.4930 ms
4Tm−ecc = 3.3240 ms
3nTm−ecc = 2.4930n ms
(2n+2)Tm−ecc = 1.6620n + 1.6620 msIn terms of the computation delay of one message signing, He et al.’s scheme [22], Lo and Tsai’s scheme [25], and Wu et al.’s scheme [27] require two scalar multiplication operations in ECC. Therefore, the total signing time is 2Tm−ecc = 1.6620 ms. Horng et al.’s scheme [30] requires two scalar multiplication operations in bilinear pairing. Therefore, the total signing time is 2Tm = 7.5540 ms. Li et al.’s scheme [31] requires two scalar multiplication operations in bilinear pairing and one map-to-point hash operation. Therefore, the total signing time is 2Tm + Tmtp = 17.2592 ms. The proposed scheme requires three scalar multiplication operations in ECC. Therefore, the total signing time is 3Tm−ecc = 2.4930 ms.In terms of the computation delay of one message verification, He et al.’s scheme [22] and Lo and Tsai’s scheme [25] require three scalar multiplication operations in ECC. Therefore, the total verification time is 3Tm−ecc = 2.4930 ms. Wu et al.’s scheme [27] requires four scalar multiplication operations in ECC. Therefore, the total verification time is 4Tm−ecc = 3.3240 ms. Horng et al.’s scheme [30] requires three bilinear pairing operations, one scalar multiplication operation in bilinear pairing and one map-to-point hash operation. Therefore, the total verification time is 3Tp + Tm + Tmtp = 40.7195 ms. Li et al.’s scheme [31] requires three bilinear pairing operations, one scalar multiplication operation in bilinear pairing, and two map-to-point hash operations. Therefore, the total verification time is 3Tp + Tm + 2Tmtp = 50.4247 ms. The proposed scheme requires four scalar multiplication operations in ECC. Therefore, the total verification time is 4Tm−ecc = 3.3240 ms.The computation delay for one message and its correlation with the number of messages (n) are shown in Figure 3. It is known from Table 4 and Figure 3(a), the computation delay of a message signing is 2.4930 ms in the proposed scheme, which decreases by 66.9% and 85.5% compared with those in Horng et al.’s scheme [30] and Li et al.’s scheme [31], respectively. In terms of computation delay of a message verification, the proposed scheme needs 3.3240 ms, which decreases by 91.8% and 93.4% compared with those in Horng et al.’s scheme [30] and Li et al.’s scheme [31], respectively.Figure 3
Computation delay. (a) Computation delay in one message signing and verification. (b) Signing delay vs number of messages. (c) Verification delay vs number of messages.
(a)
(b)
(c)To obtain computation delay of multiple (n) messages signing, the computation delay of one message signing should be repeated n times. Therefore, the total n messages signing times in the proposed scheme, He et al.’s scheme [22], Lo and Tsai’s scheme [25], Wu et al.’s scheme [27], Horng et al.’s scheme [30], and Li et al.’s scheme [31] are 2.4930n ms, 1.6620n ms, 1.6620n ms, 1.6620n ms, 7.5540n ms, and 17.2592n ms, respectively. To obtain the computation delay of multiple (n) messages verification, He et al.’s scheme [22] and Lo and Tsai’s scheme [25] require (n+2) scalar multiplication operations in ECC. Therefore, the total verification time is (n+2)Tm−ecc = 0.8310n + 1.6620 ms. Wu et al.’s scheme [27] requires (2n+2) scalar multiplication operations in ECC. Therefore, the total verification time is (2n+2)Tm−ecc = 1.6620n + 1.6620 ms. Horng et al.’s scheme [30] requires three bilinear pairing operations, n scalar multiplication operations in bilinear pairing, and n map-to-point hash operations. Therefore, the total verification time is 3Tp + nTm + nTmtp = 13.4822n + 27.2373 ms. Li et al.’s scheme [31] requires three bilinear pairing operations, n scalar multiplication operations in bilinear pairing, and (n+1) map-to-point hash operations. Therefore, the total verification time is 3Tp + nTm + n+1Tmtp = 13.4822n + 36.9425 ms. The proposed scheme requires (2n+2) scalar multiplication operations in ECC. Therefore, the total verification time is (2n+2)Tm−ecc = 1.6620n + 1.6620 ms.As is shown in Figure3(b) and Figure 3(c), that with the increase of number of messages, the signing delay and verification delay grows linearly in all schemes. And the proposed scheme has the lowest slope compared with schemes [30, 31]. It is shown in Figure 3(c), the verification delay of the schemes in [22, 25, 27, 30] and [31] and the proposed scheme, respectively, is 9.9720 ms, 9.9720 ms, 18.2820 ms, 162.0593 ms, 171.7645 ms, and 18.2820 ms when n = 10, and 51.5520 ms, 51.5520 ms, 101.3830 ms, 836.1693 ms, 845.8745 ms, and 101.3830 ms when n = 60. Apparently, the proposed scheme achieves the lowest verification delay as the number of messages grows in all CCPPA schemes.Therefore, the proposed scheme has much more superiority than other CCPPA schemes in [30, 31] in the signing and verification process, regardless of the number of messages, and is more suitable for VANETs. The proposed CCPPA scheme is slightly less efficient than He et al.’s scheme [22], Lo and Tsai’s scheme [25], and Wu et al.’s scheme [27]. This degradation is forgivable due to the fact that the proposed scheme is a certificateless system and provides key escrow resilience, however, is not the case in [22, 25, 27].


## 6.2. Communication Cost

In this subsection, the proposed scheme is compared with He et al.’s scheme [22], Lo and Tsai’s scheme [25], Wu et al.’s scheme [27], Horng et al.’s scheme [30], and Li et al.’s scheme [31] in terms of the communication cost. In V2I communication, the communication cost refers to the size of message transmitted from a vehicle (OBU) to an RSU. Just as the before analysis, the length of p is 512 bits (64 bytes) and that of q is 160 bits (20 bytes), so the length of elements in G1 and G, respectively, are 64 bytes and 20 bytes. Assuming the length of output of general one-way hash function is 160 bits (20 bytes), and the length of a timestamp is 32 bits (4 bytes). According to the IEEE Trial-Use standard [48] for VANET security, the length of message is defined as 67 bytes. Table 5 illustrates the comparison of communication costs.Table 5
Comparison of communication cost.
Scheme
Send a message
Sendn messages
[22]
155 bytes
155n bytes
[25]
175 bytes
175n bytes
[27]
175 bytes
175n bytes
[30]
351 bytes
351n bytes
[31]
351 bytes
351n bytes
The proposed scheme
195 bytes
195n bytesIn He et al.’s scheme [22], the message Mi,PIDi,ti,Ri,σi is sent from the vehicle to a RSU, where PIDi=PIDi,1,PIDi,2,Ti, PIDi,1∈G, PIDi,2∈Zq, and Ti is the timestamp. Thus, the communication cost of He et al.’s scheme is 155 bytes as(15)Mi+PIDi+ti+Ri+σi=67+44+4+20+20=155bytes.In Lo and Tsai’s scheme [25], the message Mi,PIDi,tti,Ki,Ri,Vi is sent from the vehicle to a RSU, where PIDi=PIDi,1,PIDi,2,ti, PIDi,1∈G, PIDi,2∈Zq and ti is the timestamp. Thus, the communication cost of Lo and Tsai’s scheme is 175 bytes as(16)Mi+PIDi+tti+Ki+Ri+Vi=67+44+4+20+20+20=175bytes.In Wu et al.’s scheme [27], the message Mi,PIDi,Ti,hi,Ri,δi is sent from the vehicle to a RSU, where PIDi=PIDvi,kvi,Tvi, PIDvi∈G, kvi∈Zq, and Tvi is the timestamp. Thus, the communication cost of Wu et al.’s scheme is 175 bytes as(17)Mi+PIDi+Ti+hi+Ri+δi=67+44+4+20+20+20=175bytes.In Horng et al.’s scheme [30] and Li et al.’s scheme [31], the message Mi,PIDi,ti,Pi,Ri,Si is sent from the vehicle to a RSU, where PIDi=PIDi,1,PIDi,2,Ti, PIDi,1∈G1, PIDi,2∈Zq, and Ti is the timestamp. Thus, the communication cost of these two schemes is 351 bytes as(18)Mi+PIDi+ti+Pi+Ri+Si=67+88+4+64+64+64=351bytes.In the proposed scheme, the messageMi,PIDi,ti,Pi,Di,Ri,σi is sent from the vehicle to a RSU, where PIDi is the same one as [22]. Thus, the communication cost of the proposed scheme is 195 bytes as(19)Mi+PIDi+ti+Pi+Di+Ri+σi=67+44+4+20+20+20+20=195bytes.The comparison on the communication costs of one message and multiple messages is shown in Figure4. Clearly, the communication costs increase linearly as the number of messages increases in six schemes. The same communication costs exist in the ID-based schemes [25, 27] and the certificateless schemes [30, 31], whether one message or multiple messages are transmitted. The communication cost of the proposed scheme is the lowest in the CCPPA schemes, which significantly decreases by 44.44%. When the number of messages rises to 30 000, the proposed scheme can save 4.46 MB of bandwidth compared with the schemes in [30, 31]. The communication cost of the proposed scheme is slightly larger than that of He et al.’s scheme [22], Lo and Tsai’s scheme [25], and Wu et al.’s scheme [27]. The reason is that the proposed scheme is a certificatless scheme, in which an additional user’s public key is needed to transmit.Figure 4
Communication cost. (a) Communication cost of one message. (b) Communication cost vs number of messages.
(a)
(b)


## 6.3. Simulations

The popular network simulator ns-3.26 [45] on a Ubuntu platform is adopted to evaluate the performances of the proposed CCPPA scheme by comparing with those of He et al.’s scheme [22], Lo and Tsai’s scheme [25], Wu et al.’s scheme [27], Horng et al.’s scheme [30], and Li et al.’s scheme [31]. In addition, a road traffic simulator SUMO [46] is used to generate a realistic traffic mobility trace for the road scenario shown in Figure 5.Figure 5
Road scenario for simulation.In our road scenario, the RSUs are assigned every 500 m along each road, and each vehicle broadcasts traffic-related messages every 300 ms. The vehicles are distributed at random on the road and move toward randomly selected intersections. The important simulation parameters are summarized in Table6.Table 6
Simulation parameters.
Parameters
Values
Wireless protocol
802.11p
Channel bandwidth
6 mbs
Buffer size
1 M bytes
Simulation area
1000 m× 1000 m
Number of RSU
9
Simulation time
200 s
Network simulation tool
ns-3.26
Traffic simulation tool
SUMO
Vehicle speed
10–50 m/sGenerally, the average message delayavgMD and average message loss ratio avgMLR in RSUs are adopted to estimate the performances.TheavgMD is defined as(20)avgMD=∑i=1NV∑​j=1NR∑​k=1NMiTVi⟶Rj,MkRecv−TVi⟶Rj,MkSend∑​i=1NVNMi+TavgVerify,where NV and NR indicates the number of vehicles and RSUs in simulation area, respectively. NMi represents the number of messages that sent from vehicle Vi. TVi⟶Rj,MkRecv is the time for Rj (a RSU) receiving a message Mk from Vi and TVi⟶Rj,MkSend is the time for Vi sending a message Mk to Rj (a RSU). TavgVerify means the average verification time for each message.TheavgMLR refers to the ratio of the number of messages dropped over the total number of messages received by the RSUs, which is defined as(21)avgMLR=1NR∑j=1NRNDroppedjNReceivedj,where NDroppedj indicates the number of messages dropped by Rj (a RSU) in the application layer and NReceivedj represents the number of messages received by Rj (a RSU) in MAC layer. We emphasize that the avgMLR occurs by the security protocol and the buffer space of the RSU, rather than the wireless transmission channel.


### 6.3.1. Impact of Vehicle Density

Two experiments are conducted to analyze the influence of the vehicle density onavgMD and avgMLR. The number of vehicles varies from 20 to 100, and the average speed of vehicles is approximately 20 m/s (72 km/h). The simulation results under the different vehicle densities are shown in Figure 6.Figure 6
Average message delay and message loss ratio under different number of vehicles. (a) Average message delay vs number of vehicles. (b) Average message loss ratio vs number of vehicles.
(a)
(b)Figure6(a) reveals the relationship between avgMD and the number of vehicles. The avgMD for RSUs increases with the number of vehicles. The avgMD is 0.005 s, 0.004 s, 0.006 s, 2.94 s, 2.98 s, and 0.006 s in He et al.’s scheme [22], Lo and Tsai’s scheme [25], Wu et al.’s scheme [27], Horng et al.’s scheme [30], Li et al.’s scheme [31], and the proposed scheme, respectively. Clearly, the avgMD of the proposed scheme and schemes in [22, 25, 27] is very low and hardly affected by vehicle density.Figure6(b) describes the relationship between avgMLR and the number of vehicles. While the number of vehicles in the communication range is larger than 20, the avgMLR increases along with the number of vehicles in Horng et al.’s scheme [30] and Li et al.’s scheme [31] and reaches as high as 57% when the number of vehicles is 100. However, for the proposed scheme and schemes in [22, 25, 27], the avgMLR remains nearly 0 regardless of the vehicle density.


### 6.3.2. Impact of Vehicle Speed

Two experiments are conducted to evaluate the impact of speed of vehicles onavgMD and avgMLR. The average vehicle speed is varies from 10 to 50 m/s (36 to 180 km/h) and the number of vehicles is 50. The results obtained from the simulation under varying speed of vehicles are depicted in Figure 7.Figure 7
Average message delay and message loss ratio under different speed of vehicles. (a) Average message delay vs speed of vehicles. (b) Average message loss ratio vs speed of vehicles.
(a)
(b)Figure7(a) shows the relationship between avgMD and the speed of vehicles. Obviously, when the vehicle density is constant, the avgMD hardly changes, showing that it is merely little influenced by the speed of vehicles.Figure7(b) depicts the relationship between avgMLR and the speed of vehicles. When the speed of vehicles is higher than 20 m/s, the avgMLRs in Horng et al.’s scheme [30] and Li et al.’s scheme [31] are slightly influenced. As speed of vehicles gets larger, the avgMLR of the proposed scheme and schemes in [22, 25, 27] has been steady at a very low level.


## 6.3.1. Impact of Vehicle Density

Two experiments are conducted to analyze the influence of the vehicle density onavgMD and avgMLR. The number of vehicles varies from 20 to 100, and the average speed of vehicles is approximately 20 m/s (72 km/h). The simulation results under the different vehicle densities are shown in Figure 6.Figure 6
Average message delay and message loss ratio under different number of vehicles. (a) Average message delay vs number of vehicles. (b) Average message loss ratio vs number of vehicles.
(a)
(b)Figure6(a) reveals the relationship between avgMD and the number of vehicles. The avgMD for RSUs increases with the number of vehicles. The avgMD is 0.005 s, 0.004 s, 0.006 s, 2.94 s, 2.98 s, and 0.006 s in He et al.’s scheme [22], Lo and Tsai’s scheme [25], Wu et al.’s scheme [27], Horng et al.’s scheme [30], Li et al.’s scheme [31], and the proposed scheme, respectively. Clearly, the avgMD of the proposed scheme and schemes in [22, 25, 27] is very low and hardly affected by vehicle density.Figure6(b) describes the relationship between avgMLR and the number of vehicles. While the number of vehicles in the communication range is larger than 20, the avgMLR increases along with the number of vehicles in Horng et al.’s scheme [30] and Li et al.’s scheme [31] and reaches as high as 57% when the number of vehicles is 100. However, for the proposed scheme and schemes in [22, 25, 27], the avgMLR remains nearly 0 regardless of the vehicle density.


## 6.3.2. Impact of Vehicle Speed

Two experiments are conducted to evaluate the impact of speed of vehicles onavgMD and avgMLR. The average vehicle speed is varies from 10 to 50 m/s (36 to 180 km/h) and the number of vehicles is 50. The results obtained from the simulation under varying speed of vehicles are depicted in Figure 7.Figure 7
Average message delay and message loss ratio under different speed of vehicles. (a) Average message delay vs speed of vehicles. (b) Average message loss ratio vs speed of vehicles.
(a)
(b)Figure7(a) shows the relationship between avgMD and the speed of vehicles. Obviously, when the vehicle density is constant, the avgMD hardly changes, showing that it is merely little influenced by the speed of vehicles.Figure7(b) depicts the relationship between avgMLR and the speed of vehicles. When the speed of vehicles is higher than 20 m/s, the avgMLRs in Horng et al.’s scheme [30] and Li et al.’s scheme [31] are slightly influenced. As speed of vehicles gets larger, the avgMLR of the proposed scheme and schemes in [22, 25, 27] has been steady at a very low level.


## 7. Conclusion

This paper has presented a novel and efficient CCPPA scheme in V2I communication for VANETs. Our proposed scheme is not only provably secure in the random oracle model under the ECDL assumption, but also satisfies all security requirements such as message authentication and conditional privacy preserving. Furthermore, the proposed scheme does not need any map-to-point hash operations and bilinear pairing operations. The performance evaluation demonstrates that the proposed scheme has higher efficient in terms of computation delay and communication cost than that of two recently proposed CCPPA schemes. Extensive simulation results indicate that the proposed scheme is feasible in the average message delay and average message loss ratio, and thus the proposed scheme is extremely appropriate in realistic VANETs.



---

*Source: 7593138-2019-02-03.xml*