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.

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 Figure 1. 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 Section 2, 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 , where is a positive integer such that less than a prime number . 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 Figure 2. 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 curve E over a finite field , where is a large prime, is defined by the following equation:where .

An infinity point O and all points form an additive cyclic group . Scalar multiplication over is defines aswhere .

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 .

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 and on the elliptic curve E, where are two unknown integers, compute the point .

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 Table 1.

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 numbers p and q. Then TAs select a non-singular elliptic curve E defined by the equation , where .(2)The TAs pick a group of elliptic curve points with prime order q and a generator P of .(3)The KGC randomly chooses as the master key for partial private key extraction and computes .(4)The TRA randomly selects as the master key for identity traceability and computes .(5)The TAs choose four one-way hash functions: , , and .

The TAs publish 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 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 vehicle , and then the KGC generates the partial private keys corresponding to the pseudo identities, when TRA receiving the real identity from , where uniquely identifies the vehicle . Based on this fact, the TRA and KGC preload the pseudo identities and partial private keys in TPD of vehicle after successful completion of own offline registration. The following steps are executed in this phase:(1)The vehicle transmits the real identity to the TRA in a secure manner.(2)After confirming the real identity , the TRA randomly chooses and computeswhere defines the valid period of this pseudo identity. Then, a pseudo identity is delivered to the KGC in a secure channel.(3)For a given pseudo identity , the KGC randomly chooses and computes the partial private key (), where

The KGC sends the pseudo identity and partial private key to the vehicle .

4.3. Private Key Generation and Message Signing

At the private key generation and message signing phase, the vehicle generates private key and signs messages. Then, the vehicle 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 vehicle randomly picks and sets as the secret value and computes . Then, the vehicle ’s private key is and the public key is .(2)The vehicle randomly chooses a pseudo identity from its storage and a current timestamp , which supports the freshness of message so as to resist the replay attack. Given a traffic-related message , the vehicle randomly selects and computes

The signature of a traffic-related message is . Then, the vehicle issues the message 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 message to verify the validity of the message by the performing the following steps:(1)The verifier checks whether is valid and is fresh. If is not valid or is not fresh, the message will be dropped.(2)The verifier checks whether the equationholds 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 distinct n messages generated by the different vehicles, respectively, the verifier checks the validity of the messages as follows:(1)The verifier checks whether is valid and is fresh, where . If any is not valid or is not fresh, the messages will be dropped.(2)The verifier checks whether the equationholds or not. If it holds, accept the messages.

To detect any invalid signature in batch message verification of n messages, we use the small exponent test technology [14, 16] to realize batch message verification. The verifier checks whether the following equationholds or not. If it holds, accept the messages, where 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 and Type II adversary . The adversary models an outside adversary and acts as a malicious third party while the adversary models an inside adversary and serves as a malicious-but-passive KGC.(i)Type I adversary . The adversary 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 . The adversary can access the master key, but cannot replace the vehicle’s public key.

The following queries can be made by and adversaries.(i)Hash queries. Given a query, output a random value.(ii)Create vehicle queries. Given a query on the pseudo identity of the vehicle, output the vehicle’s public key .(iii)Partial private key queries. Given a query on the pseudo identity of the vehicle, output the vehicle’s partial private key .(iv)Secret value queries. Given a query on the pseudo identity of the vehicle, output the vehicle’s secret value if the public key has not been replaced; otherwise, output symbol .(v)Vehicle public key replacement queries. Given a query on the pseudo identity of the vehicle and a new vehicle’s public key , replace the corresponding vehicle’s public key with a new public key .(vi)Sign queries. Given a query on the traffic-related message under , output a signature .

The security of the proposed CCPPA scheme is defined by the following two interaction games: Game 1 and Game 2 between the adversary or and a challenger .

Game 1. Security against the Adversary . This game is played between the adversary and the challenger for the proposed CCPPA scheme as follows:(i)Initialization. The challenger runs the algorithm System Initialization to generate master key and the system parameters . Then returns to .(ii)Queries. The adversary can adaptively issue and create vehicle, partial private key, secret value, vehicle public key replacement, and sign queries to .(iii)Forgery. Eventually, outputs the signature on under such that(a) is a valid signature on under .(b) has not been requested as one of the sign queries.(c) has not been requested as one of the secret value queries and the partial private key queries.

The success probability of the adversary wins in Game 1 is defined as .

Definition 1. A CCPPA scheme for VANETs is secure against Type I adversary if is negligible.

Game 2. Security against the Adversary . This game is played between the adversary and the challenger for the proposed CCPPA scheme as follows:(i)Initialization. The challenger runs the algorithm System Initialization to generate the master key and system parameters . Then, returns the master key and to .(ii)Queries. can adaptively issue , create vehicle, secret value, and sign queries to . Note that here 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. also cannot replace any public keys of the vehicles.(iii)Forgery. Eventually, outputs the signature on under such that(a) is a valid signature on under .(b) has not been requested as one of the sign queries.

The success probability of the adversary wins in Game 2 is defined as .

Definition 2. A CCPPA scheme for VANETs is secure against Type II adversary if 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 on Lemma 1 and Lemma 2.

Lemma 1. The proposed CCPPA scheme for VANETs is existential unforgeable against Type I adversary under the ECDL assumption in the random oracle model.

Proof. Assuming that polynomially bounded Type I adversary , who can break our proposed scheme with probability ε in time t, there exists an algorithm that can compute x with a non-negligible probability when receiving a random ECDL problem instance . The algorithm runs as subroutine and acts as the challenger in Game 1 and interacts with as described below.
Initialization. The algorithm sets and sends system parameters to . Here, hash functions are considered as random oracles in the proof.
To keep the consistency and rapidly response, maintains the initially empty lists as follows:(i) list . This list consists of tuples .(ii) list . This list consists of tuples .(iii) list . This list consists of tuples .(iv) list . This list consists of tuples .(v). This list consists of tuples . Queries. Suppose submits a query on , checks the list and executes as follows:(i)If the list includes , responds with previous value to .(ii)If the list does not include , chooses a random number , adds in and returns to . Queries. Suppose submits a query on , checks the list and executes as follows:(i)If the list includes , responds with previous value to .(ii)If the list does not include , chooses a random number , adds in , and returns to . Queries. Suppose submits a query on , checks the list , and executes as follows:(i)If the list includes , responds with previous value to .(ii)If the list does not include , chooses a random number , adds in , and returns to . Queries. Suppose submits a query on , checks the list , and executes as follows:(i)If the list includes , responds with previous value to .(ii)If the list does not include , chooses a random number , adds in , and returns to .Create Vehicle Queries. Suppose submits a public key query on a pseudo identity of the vehicle, checks the list and executes as follows:(i)If the list includes , responds with previous value to .(ii)If the list does not include , randomly chooses , and computes . Finally, returns to , and inserts to .Partial Private Key Queries. Suppose submits a partial private key query on a pseudo identity of the vehicle, checks the list , and executes as follows:(i)If the list includes , responds with previous value to .(ii)If the list does not include , picks random numbers , and sets and . Finally, returns to , and inserts and to and , respectively.Secret Value Queries. Suppose submits a secret value query on a pseudo identity of the vehicle, checks the list , and executes as follows: (i)If the list includes , responds with previous value to .(ii)If the list does not include , makes a create vehicle query itself to generate . Finally, returns to and inserts to .Vehicle Public Key Replacement Queries. Suppose submits a public key replacement query on , checks the list , and executes as follows:(i)If the list includes , sets and and updates to .(ii)If the list does not include , sets and and inserts to .Sign Queries. Suppose submits a sign query on , firstly conducts a partial private key query itself to generate . chooses a random value and computes . If the tuple including already appear on the list , picks another , and tries again. Finally, returns to .
Forgery. outputs a valid signature on under . Based on the Forking Lemma [42], can obtain another valid signature on under by replaying procedure with the same random tape but a different choice of . Then we haveFollowing equations (9) and (10), we can obtainFinally, outputs , which is the solution to the ECDL problem.
After completing the above simulation, we will analyze the probability and time of to solve the ECDL problem instance.
Assuming that can make at most times queries, times create vehicle queries, times partial private key queries, times secret value queries, times vehicle public key replacement queries, and times sign queries.
The probability of failure in handling a partial private key query resulted from a conflict on is at most . The probability of failure in handling a sign query caused by a conflict on is at most . In addition, the probability of outputs a valid forgery without asking the corresponding is at most . guesses it correctly as the point of rewind, with probability at least . Therefore, the probability of success of to solve the ECDL problem is at least .
The running time of is equal to the running time of plus the time it takes to respond to create vehicle queries, partial private key queries, secret value queries, and sign queries. Each create vehicle query requires 1 scale multiplication operation in . Each partial private key query requires 2 scale multiplication operations in . Each secret value query requires 1 scale multiplication operation in . Each sign query requires 2 scale multiplication operations in . Assuming that each scale multiplication in needs time , the total running time of is at most .

Lemma 2. The proposed CCPPA scheme for VANETs is existential unforgeable against Type II adversary under the ECDL assumption in the random oracle model.