# Certificateless-Based Anonymous Authentication and Aggregate Signature Scheme for Vehicular Ad Hoc Networks

Authors: Xin Ye; Gencheng Xu; Xueli Cheng; Yuedi Li; Zhiguang Qin
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Development of Internet of Vehicles (IoV) has aroused extensive attention in recent years. The IoV requires an efficient communication mode when the application scenarios are complicated. To reduce the verifying time and cut the length of signature, certificateless aggregate signature (CL-AS) is used to achieve improved performance in resource-constrained environments like vehicular ad hoc networks (VANETs), which is able to make it effective in environments constrained by bandwidth and storage. However, in the real application scenarios, messages should be kept untamed, unleashed, and authentic. In addition, most of the proposed schemes tend to be easy to attack by signers or malicious entities which can be called coalition attack. In this paper, we present an improved certificateless-based authentication and aggregate signature scheme, which can properly solve the coalition attack. Moreover, the proposed scheme not only uses pseudonyms in communications to prevent vehicles from revealing their identity but also achieves considerable efficiency compared with state-of-the-art work, certificateless signature (CLS), and CL-AS schemes. Furthermore, it demonstrates that when focused on the existential forgery on adaptive chosen message attack and coalition attack, the proposed schemes can be proved secure. Also, we show that our scheme exceeds existing certification schemes in both computing and communication costs.


---

## Body

## 1. Introduction

With the rapid development of communication technology, various vehicles with powerful smart devices can communicate with each other. Therefore, such a novel application has aroused extensive interest in the society. This kind of application is commonly referred to as vehicle ad hoc networks (VANETs), which can provide guarantee for the distance between vehicles and reduce the probability of vehicle collision accidents, help car drivers navigate in real time, and improve the efficiency of traffic operation by communicating with other vehicles and network systems [1].Although VANETs have a lot of merits, it has a long way to achieve a wide application. One of the obstacles is that the privacy is violated. Without proper privacy protection, malicious adversaries can collect vehicle information, such as routes or status, to perform attacks. Fortunately, using pseudonyms in communications can avoid this problem. Then, the vehicle can communicate with each other or with roadside unit (RSU) using a pseudonym, and no one can obtain the true identity of the vehicle except for the trusted authority (TA). Even if the messages between the vehicles and the RSUs are collected by hackers, it will not reveal identity privacy. VANETs have other problems such as privacy issues and being vulnerable to attack.Recently, some novel schemes and algorithms are proposed to solve these problems. Lin et al. [2] proposed a blockchain-based protocol to reduce the verification cost and storage cost for vehicles. Kumar et al. [3] proposed an efficient scheme using path signature to resist Sybil attack. Jiang et al. [4] proposed an anonymous authentication scheme (AAAS) in VANETs, which adopts group signature mechanism to provide more efficient anonymous authentication service for vehicles. Zheng et al. [5] demonstrated a certificateless group signature anonymous authentication scheme for VANETs, which shortens the length of the signature and improves the efficiency of the signature. Among various schemes, we find that Kamil et al.’s scheme [6] has a significant efficiency. However, we find that the scheme cannot resist coalition attack which is launched by two collusive vehicles. For example, two vehicles can maliciously exchange their locations to generate their signatures which can be verified successfully so that they can hide their real locations which may lead to serious consequences. The detailed description and analysis are shown in Subsection 4.3. We make the RSU both the aggregator and the verifier and add a random list to properly solve the problem. Our main contributions in this paper are as follows:
(i)
Prove that Kamil et al.’s schemes are not secure enough to defend against attacks from malicious vehicles and propose a solution to settle the problem(ii)
Propose an improved certificateless-based authentication and aggregate signature scheme in VANETs, and prove that the scheme can perfectly resist the coalition attacks and its correctness(iii)
Use the efficiency analysis and simulation to show the superiority of our scheme in efficiency and practicalityThe rest of this paper is organized as follows. In Section2, we discuss related works of CLS and CL-AS schemes in VANETs. In Section 3, we describe related concepts and models. In Section 4, we analyze Kamil et al.’s scheme and prove that the scheme cannot resist the coalition attack. We propose our proposed scheme in Section 5 in detail. Experiments and results analysis are described in Section 6. We conclude this paper in Section 7.


## 2. Related Works

To settle the problem of security and some privacy requirements in VANETs, a number of professors and scholars [7–9] proposed a kind of new scheme called Public Key Infrastructure-based (PKI-based) authentication schemes. In their schemes, they either tried to make vehicles compute more to verify the signatures from other vehicles or assume that there exists a trusted certificate authority to issue and maintain certificates of various vehicles. However, the assumption may be unrealistic because a single node cannot afford the oceans of calculation.Later, a new kind of signature scheme called identity-based signature (IBS) scheme is widely discussed. For example, Liu et al. [10] proposed an IBS scheme which can take the user’s identity as the public key, and the private key is generated by public key generation PKG, which can reduce a single node’s burden. However, IBS has inherent problems about key escrow which is generated by user’s identity.In Al-Riyami and Paterson’s scheme [11], they firstly introduce the certificateless public key cryptography. In recent years, a lot of researches on CLS and CL-AS schemes with bilinear pairing have been carried on by relevant researchers [12–14]. In their schemes, key generation center (KGC) uses its master key and the user’s identity information to calculate a part of the private key and send it to the user, whereafter the user combines part of the private key and his/her secret value together to generate the user’s real private key which can protect the user’s privacy and make the system secure. The above scheme uses the bilinear pairing which costs relatively large computation.The elliptic curve cryptography is chosen to use in the CLS and CL-AS because of its high efficiency. In Xie et al.’s scheme [15], they proposed rigorous security proof that shows the scheme is able to resist various malicious attacks and ensure privacy protection. In the field of health care, Du et al. [16] proposed a CLAS scheme with high efficiency and low latency which can be more suitable to apply to the field of healthcare. In 2018, Cui et al. [17] demonstrated their novel CLS and CL-AS scheme with ECC, which significantly reduces computing time during sign and verification process. Kamil et al. [6] declared that the scheme proposed by Cui et al. is not secured against the signature forgery attack, and they advanced an improved signature scheme for VANETs. They claimed that their proposed scheme can address all the needs of VANETs about security and privacy. However, we will demonstrate and prove that their scheme cannot resist coalition attacks and our improved scheme can resist the attack and achieves a better performance.


## 3. Preliminaries

### 3.1. Elliptic Curve Cryptography

As widely used in the cryptographic, the elliptic curve cryptography is an excellent algorithm which has an extremely high efficiency and a relatively excellent security. It can use much fewer bits to encrypt messages of the same length than the RSA algorithm in the field of public key cryptography. Because of its fewer calculation parameters, shorter bond length, and less time cost, the elliptic curve cryptography can be perfectly applied to application scenarios of VANETs. We will give the following three definitions to describe the elliptic curve cryptography.Definition 1 (Elliptic curve definition).
Our scheme uses an elliptical encryption algorithm with 160 bits. Assume thatFq is a finite field of the module q, where q is a large prime number. The elliptic curve over a finite field Fq can be defined as follows: E:y2=x3+ax+b (mod p), where a,b,x,y∈Fq and Δ=4a3+27b2≠0 (mod p).Definition 2 (Addition of elliptic curves).
Assume thatP=x1,y1∈E, where P is a point of the elliptic curve E and −P=x1,−y1 (mod p) is the negative point of P. Suppose Q=x2,y2∈E, Q≠−P; we can define a line l passes through P and Q, and intersects the elliptic curve at a point R′=x3,y3, The symmetrical point about the x-axis with R′ is R=x3,−y3; then we can define R=P+Q. In addition, scalar multiplication operation on the elliptic curve can be described as follows:
(1)k·P=P+P+P+⋯+Pk∈Zq∗.Definition 3 (Elliptic curve discrete logarithm problem).
Assume thatP1 is a point on the elliptic curve E on the finite field Fq, and select a random number k∈Zq∗. Then, we can calculate P2=k·P1. In this case, there is the feasibility of the calculation of P2 according to Definition 2. According to the elliptic curve discrete logarithm problem (ECDLP), however, it is hardly possible to get k according the above equation.


### 3.2. Forking Lemma

Definition 4 (Forking lemma [18]).
Suppose thatA is a probabilistic polynomial time turing machine, and its input includes public data. We use Q and R to symbolize the number of queries that A can ask to the random oracle and the number of queries that A can ask to the signer, respectively. Suppose that over a period of time T, A can generate a legitimate signature m,σ1,h,σ2 within probability ε≥10R+1R+Q/2k. If someone do not know the private key, but successfully forge the signature σ1,h,σ2 with an indistinguishable distribution probability, then we can imagine a machine, which can get the secret information from the machine and obtain and replace the interaction with the signer by simulation. Eventually, it can generate two legitimate signatures m,σ1,h,σ2 and m,σ1,h′,σ2′ such that h≠h′ in expected time T′≥120686QT/ε.


### 3.3. Certificateless (Aggregate) Signature Scheme

Generally, a certificateless signature (CLS) scheme and a certificateless aggregate signature (CL-AS) scheme consist of the following seven algorithms.(1)
Setup: the KGC and TA will execute this probabilistic algorithm, which needs a security parameterλ, then generates a elliptic curve E, public keys PKTA and PKKGC, and master secrets key α,β, respectively, then publishes a number of system parameters which is used for ensuring the system in order.(2)
ParitialPrivateKeyGeneration: in this algorithm, firstly, the entityVi transmits a tuple which includes its real identity and partial pseudo identity to TA. Then TA sends a whole pseudo identity to KGC with calculation. Eventually, KGC transmits the paitial private key to entity Vi in a secure channel.(3)
VehicleKeyGeneration: the entityVi selects random ρi∈Zq∗ as its secret key and calculates its public key PKVi.(4)
IndividualSign: this algorithm is used by each entityVi; after generating a message mi, the entity Vi tries to calculate a set of varieables. Then it sends the signature σ to the verifier.(5)
IndividualVerify: this algorithm is executed by the verifier such as RSU. When receiving input including signatureσ, pseudo identity PIDi and current time Tcur, the RSU will check the time validity firstly. Then the algorithm will output true if the signature is valid or false otherwise.(6)
AggregateSign: in this algorithm, generally the aggregate signature generator is RSU in our system. For an aggregating setV of n entities V1,V2,⋯,Vn, the pseudo identity PIDi of each vehicle Vi as list PID, the corresponding public key PKVi of Vi, and message signature tuples m1,σ1,m2,σ2,⋯,mn,σn from Vi, respectively. The aggregate signature generator will generate signature σ; then it will transmit the tuple including the signature, the list PID, and time list T to the verifier.(7)
AggregateVerify: in general, this algorithm is executed by another RSU. It takes an aggregating setV of n entities V1,V2,⋯,Vn, the pseudo identity PIDi of each entity Vi. The verifier will check the time validity for each entity firstly. Then it will output true if the signature is valid or false otherwise.


### 3.4. Security Model

In this section, we will demonstrate the security model of CLS and CL-AS schemes. We consider two different types of adversaries: Type1A1 and Type 2A2. To be specific, adversary A1 is able to replace a user’s public key or private key but cannot access or even replace the master secret key of KGC. And adversary A2 is able to access the master secret key of KGC, which can be called an internal attacker. However, it cannot replace or access the public key of a certain user.Generally, we use two games to model the security of CLS and CL-AS schemes, which is played between an adversaryA∈A1,A2 and a challenger C. A can access five oracles to get what he needs. The details are as follows:
(1)
GenerateUser: given a user’s IDPIDi and request for its public key PKVi, C returns the public key PKVi of PIDi.(2)
RevealPartialPrivateKey: given a user’s pseudo identityPIDi, C outputs the corresponding partial secret key PPKi.(3)
RevealSecretKey: given a user’s pseudo identityPIDi, C submits the user’s secret key ρi.(4)
ReplaceKey: given a user’s pseudo identityPIDi and the public key PKVi∗, C will replace the public key PKVi with PKVi∗.(5)
Sign: given a messagemi∈0,1∗, C uses the algorithm to generate a signature σi corresponding to user PIDi on message mi and submits it to A.We construct the following two games, Game I and Game II, for our schemes:(Game I)
A Type1 adversary A1 and a challenger C will try to play the game as follows:Step 1.
C runs the Setup algorithm to generate a master secret key β, a list of system parameters, and the system public key PKKGC. It then sends the system parameters to A1 and keeps β secret.Step 2.
A1 queries the GenerateUser, RevealPartialSecretKey, RevealSecretKey, and Sign oracles in order.Step 3.
A1 generates the corresponding public key PKVi∗ and a signature σi∗ of a user with identity PIDi∗.A1 will win the game if the following conditions are met:
(i)
It neither usesPIDi∗ to access the RevealPartialSecretKey query nor obtains the partial private key(ii)
σ∗ is a valid signature of the user with the identity PIDi∗ and the corresponding public key PKVi∗(iii)
It never usesPIDi∗,mi∗ to query the Sign oracle(Game II)
A Type2 adversary A2 and a challenger C will try to play the game as follows:Step 1.
C runs the Setup algorithm to generate a master secret key β, a list of system parameters, and the system public key PKTA. It then sends the system parameters, β, and PKTA to A2.Step 2.
A2 queries the GenerateUser, RevealPartialSecretKey, RevealSecretKey, and Sign oracles in order.Step 3.
A2 generates the corresponding public key PKVi∗ and a signature σi∗ of a user with identity PIDi∗.A2 will win the game if the following conditions are satisfied:
(i)
It never usePIDi∗ to access the RevealSecretKey or ReplaceKey query to obtain the partial private key(ii)
σ∗ is a valid signature of user with identity PIDi∗ and the corresponding public key PKVi∗(iii)
It never usesPIDi∗,mi∗ to query the Sign oracleDefinition 5.
The CLS scheme is provably secure, if neither polynomial time adversaryA1 or A2 is able to win Game I and Game II, respectively with a non-negligible advantage.We construct the following two games, Game III and Game IV, for our CL-AS scheme.(Game III)
A Type1 adversary A1 and a challenger C will try to play the game as follows:Step 1.
C runs the Setup algorithm to generate the master secret key β, system parameter, and the system public key PKTA. It then sends the system parameter to A1 and keeps β secret.Step 2.
A1 queries the GenerateUser, RevealPartialSecretKey, RevealSecretKey, and Sign oracles in order.Step 3.
A1 outputs an aggregate signature σ∗ of n users with identity PID∗=PID1∗,PID2∗,⋯,PIDn∗ and the corresponding public key PKV∗=PKV1∗,PKV2∗,⋯,PKVn∗ on messages m∗=m1∗,m2∗,⋯,mn∗.A1 wins the game if the following conditions are satisfied:
(i)
At least one of the identities has not been submitted to the RevealPartialSecretKey query to obtain the partial secret key(ii)
σ∗ is a valid signature on n messages M∗=m1∗,m2∗,⋯,mn∗ of n users with identities PID∗=PID1∗,PID2∗,⋯,PIDn∗ and the corresponding public key PKV∗=PKV1∗,PKV2∗,⋯,PKVn∗.(iii)
It never usesPIDi∗,mi∗ to query the Sign oracle(Game IV)
A Type2 adversary A2 and a challenger C will try to play the game as follows:Step 1.
C runs the Setup algorithm to generate the master secret key β, system parameter, and the system public key PKTA. It then sends the system parameter, β, PKTA to A2.Step 2.
A2 queries the GenerateUser, RevealPartialSecretKey, RevealSecretKey, and Sign oracles in order.Step 3.
A2 outputs an aggregate signature σ∗ of n users with identity ID∗=ID1∗,ID2∗,⋯,IDn∗ and the corresponding public key PKV∗=PKV1∗,PKV2∗,⋯,PKVn∗ on messages M∗=m1∗,m2∗,⋯,mn∗.A2 will win the game if the following conditions are satisfied:
(i)
It has not used all of the identities to access the RevealPartialSecretKey query to obtain the partial private key.(ii)
σ∗ is a legitimate signature on n messages m∗=m1∗,m2∗,⋯,mn∗ of n users with identities PID∗=PID1∗,PID2∗,⋯,PIDn∗ and the corresponding public key PKV∗=PKV1∗,PKV2∗,⋯,PKVn∗.(iii)
It never usesIDi∗,mi∗ to query the Sign oracleDefinition 6.
The CL-AS scheme is provably secure, if neither polynomial time adversaryA1 or A2 is able to win Game III and Game IV, respectively, with a nonnegligible advantage.


## 3.1. Elliptic Curve Cryptography

As widely used in the cryptographic, the elliptic curve cryptography is an excellent algorithm which has an extremely high efficiency and a relatively excellent security. It can use much fewer bits to encrypt messages of the same length than the RSA algorithm in the field of public key cryptography. Because of its fewer calculation parameters, shorter bond length, and less time cost, the elliptic curve cryptography can be perfectly applied to application scenarios of VANETs. We will give the following three definitions to describe the elliptic curve cryptography.Definition 1 (Elliptic curve definition).
Our scheme uses an elliptical encryption algorithm with 160 bits. Assume thatFq is a finite field of the module q, where q is a large prime number. The elliptic curve over a finite field Fq can be defined as follows: E:y2=x3+ax+b (mod p), where a,b,x,y∈Fq and Δ=4a3+27b2≠0 (mod p).Definition 2 (Addition of elliptic curves).
Assume thatP=x1,y1∈E, where P is a point of the elliptic curve E and −P=x1,−y1 (mod p) is the negative point of P. Suppose Q=x2,y2∈E, Q≠−P; we can define a line l passes through P and Q, and intersects the elliptic curve at a point R′=x3,y3, The symmetrical point about the x-axis with R′ is R=x3,−y3; then we can define R=P+Q. In addition, scalar multiplication operation on the elliptic curve can be described as follows:
(1)k·P=P+P+P+⋯+Pk∈Zq∗.Definition 3 (Elliptic curve discrete logarithm problem).
Assume thatP1 is a point on the elliptic curve E on the finite field Fq, and select a random number k∈Zq∗. Then, we can calculate P2=k·P1. In this case, there is the feasibility of the calculation of P2 according to Definition 2. According to the elliptic curve discrete logarithm problem (ECDLP), however, it is hardly possible to get k according the above equation.


## 3.2. Forking Lemma

Definition 4 (Forking lemma [18]).
Suppose thatA is a probabilistic polynomial time turing machine, and its input includes public data. We use Q and R to symbolize the number of queries that A can ask to the random oracle and the number of queries that A can ask to the signer, respectively. Suppose that over a period of time T, A can generate a legitimate signature m,σ1,h,σ2 within probability ε≥10R+1R+Q/2k. If someone do not know the private key, but successfully forge the signature σ1,h,σ2 with an indistinguishable distribution probability, then we can imagine a machine, which can get the secret information from the machine and obtain and replace the interaction with the signer by simulation. Eventually, it can generate two legitimate signatures m,σ1,h,σ2 and m,σ1,h′,σ2′ such that h≠h′ in expected time T′≥120686QT/ε.


## 3.3. Certificateless (Aggregate) Signature Scheme

Generally, a certificateless signature (CLS) scheme and a certificateless aggregate signature (CL-AS) scheme consist of the following seven algorithms.(1)
Setup: the KGC and TA will execute this probabilistic algorithm, which needs a security parameterλ, then generates a elliptic curve E, public keys PKTA and PKKGC, and master secrets key α,β, respectively, then publishes a number of system parameters which is used for ensuring the system in order.(2)
ParitialPrivateKeyGeneration: in this algorithm, firstly, the entityVi transmits a tuple which includes its real identity and partial pseudo identity to TA. Then TA sends a whole pseudo identity to KGC with calculation. Eventually, KGC transmits the paitial private key to entity Vi in a secure channel.(3)
VehicleKeyGeneration: the entityVi selects random ρi∈Zq∗ as its secret key and calculates its public key PKVi.(4)
IndividualSign: this algorithm is used by each entityVi; after generating a message mi, the entity Vi tries to calculate a set of varieables. Then it sends the signature σ to the verifier.(5)
IndividualVerify: this algorithm is executed by the verifier such as RSU. When receiving input including signatureσ, pseudo identity PIDi and current time Tcur, the RSU will check the time validity firstly. Then the algorithm will output true if the signature is valid or false otherwise.(6)
AggregateSign: in this algorithm, generally the aggregate signature generator is RSU in our system. For an aggregating setV of n entities V1,V2,⋯,Vn, the pseudo identity PIDi of each vehicle Vi as list PID, the corresponding public key PKVi of Vi, and message signature tuples m1,σ1,m2,σ2,⋯,mn,σn from Vi, respectively. The aggregate signature generator will generate signature σ; then it will transmit the tuple including the signature, the list PID, and time list T to the verifier.(7)
AggregateVerify: in general, this algorithm is executed by another RSU. It takes an aggregating setV of n entities V1,V2,⋯,Vn, the pseudo identity PIDi of each entity Vi. The verifier will check the time validity for each entity firstly. Then it will output true if the signature is valid or false otherwise.


## 3.4. Security Model

In this section, we will demonstrate the security model of CLS and CL-AS schemes. We consider two different types of adversaries: Type1A1 and Type 2A2. To be specific, adversary A1 is able to replace a user’s public key or private key but cannot access or even replace the master secret key of KGC. And adversary A2 is able to access the master secret key of KGC, which can be called an internal attacker. However, it cannot replace or access the public key of a certain user.Generally, we use two games to model the security of CLS and CL-AS schemes, which is played between an adversaryA∈A1,A2 and a challenger C. A can access five oracles to get what he needs. The details are as follows:
(1)
GenerateUser: given a user’s IDPIDi and request for its public key PKVi, C returns the public key PKVi of PIDi.(2)
RevealPartialPrivateKey: given a user’s pseudo identityPIDi, C outputs the corresponding partial secret key PPKi.(3)
RevealSecretKey: given a user’s pseudo identityPIDi, C submits the user’s secret key ρi.(4)
ReplaceKey: given a user’s pseudo identityPIDi and the public key PKVi∗, C will replace the public key PKVi with PKVi∗.(5)
Sign: given a messagemi∈0,1∗, C uses the algorithm to generate a signature σi corresponding to user PIDi on message mi and submits it to A.We construct the following two games, Game I and Game II, for our schemes:(Game I)
A Type1 adversary A1 and a challenger C will try to play the game as follows:Step 1.
C runs the Setup algorithm to generate a master secret key β, a list of system parameters, and the system public key PKKGC. It then sends the system parameters to A1 and keeps β secret.Step 2.
A1 queries the GenerateUser, RevealPartialSecretKey, RevealSecretKey, and Sign oracles in order.Step 3.
A1 generates the corresponding public key PKVi∗ and a signature σi∗ of a user with identity PIDi∗.A1 will win the game if the following conditions are met:
(i)
It neither usesPIDi∗ to access the RevealPartialSecretKey query nor obtains the partial private key(ii)
σ∗ is a valid signature of the user with the identity PIDi∗ and the corresponding public key PKVi∗(iii)
It never usesPIDi∗,mi∗ to query the Sign oracle(Game II)
A Type2 adversary A2 and a challenger C will try to play the game as follows:Step 1.
C runs the Setup algorithm to generate a master secret key β, a list of system parameters, and the system public key PKTA. It then sends the system parameters, β, and PKTA to A2.Step 2.
A2 queries the GenerateUser, RevealPartialSecretKey, RevealSecretKey, and Sign oracles in order.Step 3.
A2 generates the corresponding public key PKVi∗ and a signature σi∗ of a user with identity PIDi∗.A2 will win the game if the following conditions are satisfied:
(i)
It never usePIDi∗ to access the RevealSecretKey or ReplaceKey query to obtain the partial private key(ii)
σ∗ is a valid signature of user with identity PIDi∗ and the corresponding public key PKVi∗(iii)
It never usesPIDi∗,mi∗ to query the Sign oracleDefinition 5.
The CLS scheme is provably secure, if neither polynomial time adversaryA1 or A2 is able to win Game I and Game II, respectively with a non-negligible advantage.We construct the following two games, Game III and Game IV, for our CL-AS scheme.(Game III)
A Type1 adversary A1 and a challenger C will try to play the game as follows:Step 1.
C runs the Setup algorithm to generate the master secret key β, system parameter, and the system public key PKTA. It then sends the system parameter to A1 and keeps β secret.Step 2.
A1 queries the GenerateUser, RevealPartialSecretKey, RevealSecretKey, and Sign oracles in order.Step 3.
A1 outputs an aggregate signature σ∗ of n users with identity PID∗=PID1∗,PID2∗,⋯,PIDn∗ and the corresponding public key PKV∗=PKV1∗,PKV2∗,⋯,PKVn∗ on messages m∗=m1∗,m2∗,⋯,mn∗.A1 wins the game if the following conditions are satisfied:
(i)
At least one of the identities has not been submitted to the RevealPartialSecretKey query to obtain the partial secret key(ii)
σ∗ is a valid signature on n messages M∗=m1∗,m2∗,⋯,mn∗ of n users with identities PID∗=PID1∗,PID2∗,⋯,PIDn∗ and the corresponding public key PKV∗=PKV1∗,PKV2∗,⋯,PKVn∗.(iii)
It never usesPIDi∗,mi∗ to query the Sign oracle(Game IV)
A Type2 adversary A2 and a challenger C will try to play the game as follows:Step 1.
C runs the Setup algorithm to generate the master secret key β, system parameter, and the system public key PKTA. It then sends the system parameter, β, PKTA to A2.Step 2.
A2 queries the GenerateUser, RevealPartialSecretKey, RevealSecretKey, and Sign oracles in order.Step 3.
A2 outputs an aggregate signature σ∗ of n users with identity ID∗=ID1∗,ID2∗,⋯,IDn∗ and the corresponding public key PKV∗=PKV1∗,PKV2∗,⋯,PKVn∗ on messages M∗=m1∗,m2∗,⋯,mn∗.A2 will win the game if the following conditions are satisfied:
(i)
It has not used all of the identities to access the RevealPartialSecretKey query to obtain the partial private key.(ii)
σ∗ is a legitimate signature on n messages m∗=m1∗,m2∗,⋯,mn∗ of n users with identities PID∗=PID1∗,PID2∗,⋯,PIDn∗ and the corresponding public key PKV∗=PKV1∗,PKV2∗,⋯,PKVn∗.(iii)
It never usesIDi∗,mi∗ to query the Sign oracleDefinition 6.
The CL-AS scheme is provably secure, if neither polynomial time adversaryA1 or A2 is able to win Game III and Game IV, respectively, with a nonnegligible advantage.


## 4. Overview of Kamil et al.’s CLS and CL-AS Scheme

In the scheme proposed by Kamil et al. [6], there mainly exist four entities including TA, regional transport management authority (RTMA), which is a trusted party responsible for partial secret key generation, RSU, and vehicle. The scheme is reviewed as follows:


### 4.1. Overview of Kamil et al.’s CLS Scheme

(1)
Setup: the TA selects a security parameterk, two secure primes p and q, an elliptic curve E which can be defined by the equation y2=x3+ax+b mod p, where a,b∈Fq, a generator P with order q of additive group G consisting of all the points on E, and five hash functions, h0, h1, h2, h3, and h4. Then, it picks x∈ℤq∗ as its master secret key and calculates its public key Ppub. Also, TA defines a time-function fti, where ti is the current time. TA publishes the param=p,q,a,b,P,Ppub,h0,h1,h2,h3,h4,fti.(2)
UserRegistration: the RTMA executes the following algorithm to register a vehicle with an identityIDk. Firstly, vehicle sends its identity IDk to the RTMA. Then RTMA randomly selects ℏ1,k∈ℤq∗ and calculates hash chain set ℏy,k=ℏ2,k,ℏ3,k,⋯,ℏn,k, 1≤y≤n, where ℏy,k=h0ℏy−1,k.(3)
PartialSecretKeyGeneration: after receivingparam and a vehicle with identity IDk, RTMA runs as follows:(4)
PseudonymGeneration: after receiving the tupleℏy,k,Ak,xk from the RTMA, the vehicle executes the following algorithm:(5)
UserKeyGeneration: vehicle withIDk uses the algorithm to generate its private key:(6)
Sign: after receivingparam, PSKk, SKk, and PKk, a vehicle with pseudo identity PIDy,k can sign on a message mk as follows:(7)
Verify: after receiving the tuplePIDy,k,mk,PKk,ωk,σk,Tk, verifier can use the algorithm to verify any signature with following steps:Step 1.
The RTMA generates its public keyPKRTMA=s·P, where secret key s∈ℤq∗ is randomly selected.Step 2.
Calculateαk=h2param∥Ppub∥IDk, βk=h2IDk∥IDRTMA∥s∥∇, t=h2∇, and ξk=h2IDk∥PKRTMA.Step 3.
ComputeAk=tβk·P and xk=tβk+ξkαks.Step 4.
PublishPKRTMA, send PSKk=Ak,xk,ℏy,k to the vehicle and ℏ1,k,IDk to TA.Step 1.
Computeαk=h2param∥Ppub∥IDk, t=h2∇ and ξk=h2IDk∥PKRTMA.Step 2.
CheckPSKk is valid or not with the equation holds.
(2)xk·P=Ak+ξkαk·PKRTMA.Step 3.
Compute its pseudonym set asPID1,k,PID2,k,⋯,PIDn,k at timeslot tscur, where PIDy,k=h1IDk∥ℏy,k∥∇∥tscur.Step 1.
Chooseak,rk1,rk2∈ℤq∗ in random.Step 2.
CalculateSKk1=h3rk1∥Ak∥PIDy,k and SKk2=h3rk2∥xk∥PIDy,k.Step 3.
OutputSKk=akSKk1+SKk2 and PKk=SKk·P as its private and public keys, respectively.Step 1.
Randomly pickdk∈ℤq∗ and calculate ωk=ξkαk.Step 2.
Calculatevk=h4PIDy,k∥mk∥SKk1∥SKk2∥Tk, hk=h4PIDy,k∥mk∥ωk∥PKk∥PKRTMA∥Ppub∥Tk, and δk=h4mk∥PKk∥∇∥Tk.Step 3.
Calculateyk=dkvk, Ωk=yk·P, Rk=δk·PKk+hk·Ak+Ωk, and Vk=δkSKk+hkxk+dkvk.Step 4.
Output signatureσk=Rk,Vk on message mK and transmits PIDy,k,mk,PKk,ωk,σk,Tk, where Tk is the current timestamp.Step 1.
Check whether the time delay equation holds. If it holds, thenTk is valid and it will accept the signature; otherwise, it will reject it.Step 2.
Calculatehk=h4PIDy,k∥mk∥ωk∥PKk∥PKRTMA∥Ppub∥Tk.Step 3.
Check whether the following equation holds.(3)Vk·P=Rk+hkωk·PKRTMA,if this equation holds, then the signature is valid; otherwise, it will be discarded.


### 4.2. Overview of Kamil et al.’s CL-AS Scheme

The Setup, UserRegistration, PartialPrivateKeyGeneration, PseudonymGeneration, VehicleKeyGeneration, Sign, and Verify algorithms are the same as the above CLS scheme. In addition, the Aggregate and AggregateVerify algorithms are described as follows:(1)
Aggregate: in general, the roadside unit (RSU) acts as the aggregator. When receivingn certificateless signatures σ1=R1,V1,σ2=R2,V2,⋯,σn=Rn,Vn on messages m1∥T1,m2∥T2,⋯,mn∥Tn from n pseudo identities PIDy,1,PIDy,2,⋯,PIDy,n under the state information ∇, the RSU calculates V=∑k=1n‍Vk and R=∑k=1n‍Rk, then outputs an aggregate certificateless signature σT=R,V.(2)
AggregateVerify: generally another RSU or AS acts as the verifier. When receiving a certificateless aggregate signatureσT=R,V signed by n vehicles. Then it will run as follows:Step 1.
Check whether the timestampTk is valid, if not, it aborts, and if it holds, it runs the following steps.Step 2.
Computehk=h4PIDy,k∥mk∥ωk∥PKk∥PKRTMA∥Ppub∥Tk.Step 3.
Check whether the following equation holds.(4)V·P=R+∑k=1nhkωk·PKRTMA,if it holds, it receives all the signatures; otherwise, the signature is rejected.


### 4.3. Cryptanalysis of Kamil et al.’s CL-AS Scheme

The security problem in the scheme proposed by Kamil et al. [6] mainly lies in the coalition attack, which is a kind of attack by a number of collusive vehicles.As is described in Figure1, in the coalition attack, two or more vehicles secretly change a part of their messages such as locations to hide their real locations and routes since the RSU (verifier) receives the exchanged signature. Then something of the collusive vehicles is exchanged officially. Which will definitely harm the system and even worse cause a serious accident.Figure 1
Coalition attack diagram.We describe the coalition attack on Kamil et al.’s CL-AS scheme to illustrate its security flaws.Assume that two usersU1,U2 have pseudonym PIDy,1,PIDy,2 and message m1,m2, respectively. We show that two users can cooperate to generate valid aggregate signatures even if their individual signature is invalid. Two users can implement the coalition attack by executing the following algorithms.Step 1.
The userUii∈1,2 randomly picks di∈ℤq∗ and calculates ωi=ξiαi.Step 2.
Calculateβi=h2IDi∥IDRTMA∥s∥∇, t=h2∇, ξk=h2IDi∥PKRTMA, xi=tβi+ξiαis, vi=h4PIDy,i∥mi∥Ski1∥SKi2∥Ti, hi=h4PIDy,i∥mi∥ωi∥PKi∥PKRTMA∥Ppub∥Ti, δi=h4mi∥PKi∥∇∥Ti, yi=divi, Ω=yi·P, and Ri=δi·PKi+hi·Ai+Ω.Step 3.
Then,U1 sends h1x1 to U2; likewise, U2 sends h2x2 to U1 in a secure channel. Then U1 calculates V1=δ1SK1+h2x2+d1v1; likewise, U2 calculates V2=δ2SK2+h1x1+d2v2.Step 4.
Eventually, they can output signatureσi=Ri,Vk and transmits PIDy,i,mi,PKi,ωi,σi,Ti.
(5)V·P=V1+V2·P=δ1SK1+h2x2+d1v1+δ2SK2+h1x1+d2v2·P=∑k=12δkSKk+hktβk+ξkαks+dkvk·P=∑k=12δk·PKk+hk·Ak+ωk+∑k=12hkωk·PKRTMA=R+∑k=12hkωk·PKRTMAObviously, the signatureσi=Ri,Vi is not a valid signature. However, when the RSU or AS aggregates the signature as σ=R=R1+R2,V=V1+V2, it will be a valid signature which satisfies the following equation.Therefore, the above analysis shows that two malicious users can collude with each other to forge an aggregate signature. Actually, the coalition attack is originally caused by commutative law of addition. Similarly,n users can also forge an aggregate signature with the same algorithms. Hence, Kamil et al.’s CL-AS scheme cannot resist coalition attacks.


## 4.1. Overview of Kamil et al.’s CLS Scheme

(1)
Setup: the TA selects a security parameterk, two secure primes p and q, an elliptic curve E which can be defined by the equation y2=x3+ax+b mod p, where a,b∈Fq, a generator P with order q of additive group G consisting of all the points on E, and five hash functions, h0, h1, h2, h3, and h4. Then, it picks x∈ℤq∗ as its master secret key and calculates its public key Ppub. Also, TA defines a time-function fti, where ti is the current time. TA publishes the param=p,q,a,b,P,Ppub,h0,h1,h2,h3,h4,fti.(2)
UserRegistration: the RTMA executes the following algorithm to register a vehicle with an identityIDk. Firstly, vehicle sends its identity IDk to the RTMA. Then RTMA randomly selects ℏ1,k∈ℤq∗ and calculates hash chain set ℏy,k=ℏ2,k,ℏ3,k,⋯,ℏn,k, 1≤y≤n, where ℏy,k=h0ℏy−1,k.(3)
PartialSecretKeyGeneration: after receivingparam and a vehicle with identity IDk, RTMA runs as follows:(4)
PseudonymGeneration: after receiving the tupleℏy,k,Ak,xk from the RTMA, the vehicle executes the following algorithm:(5)
UserKeyGeneration: vehicle withIDk uses the algorithm to generate its private key:(6)
Sign: after receivingparam, PSKk, SKk, and PKk, a vehicle with pseudo identity PIDy,k can sign on a message mk as follows:(7)
Verify: after receiving the tuplePIDy,k,mk,PKk,ωk,σk,Tk, verifier can use the algorithm to verify any signature with following steps:Step 1.
The RTMA generates its public keyPKRTMA=s·P, where secret key s∈ℤq∗ is randomly selected.Step 2.
Calculateαk=h2param∥Ppub∥IDk, βk=h2IDk∥IDRTMA∥s∥∇, t=h2∇, and ξk=h2IDk∥PKRTMA.Step 3.
ComputeAk=tβk·P and xk=tβk+ξkαks.Step 4.
PublishPKRTMA, send PSKk=Ak,xk,ℏy,k to the vehicle and ℏ1,k,IDk to TA.Step 1.
Computeαk=h2param∥Ppub∥IDk, t=h2∇ and ξk=h2IDk∥PKRTMA.Step 2.
CheckPSKk is valid or not with the equation holds.
(2)xk·P=Ak+ξkαk·PKRTMA.Step 3.
Compute its pseudonym set asPID1,k,PID2,k,⋯,PIDn,k at timeslot tscur, where PIDy,k=h1IDk∥ℏy,k∥∇∥tscur.Step 1.
Chooseak,rk1,rk2∈ℤq∗ in random.Step 2.
CalculateSKk1=h3rk1∥Ak∥PIDy,k and SKk2=h3rk2∥xk∥PIDy,k.Step 3.
OutputSKk=akSKk1+SKk2 and PKk=SKk·P as its private and public keys, respectively.Step 1.
Randomly pickdk∈ℤq∗ and calculate ωk=ξkαk.Step 2.
Calculatevk=h4PIDy,k∥mk∥SKk1∥SKk2∥Tk, hk=h4PIDy,k∥mk∥ωk∥PKk∥PKRTMA∥Ppub∥Tk, and δk=h4mk∥PKk∥∇∥Tk.Step 3.
Calculateyk=dkvk, Ωk=yk·P, Rk=δk·PKk+hk·Ak+Ωk, and Vk=δkSKk+hkxk+dkvk.Step 4.
Output signatureσk=Rk,Vk on message mK and transmits PIDy,k,mk,PKk,ωk,σk,Tk, where Tk is the current timestamp.Step 1.
Check whether the time delay equation holds. If it holds, thenTk is valid and it will accept the signature; otherwise, it will reject it.Step 2.
Calculatehk=h4PIDy,k∥mk∥ωk∥PKk∥PKRTMA∥Ppub∥Tk.Step 3.
Check whether the following equation holds.(3)Vk·P=Rk+hkωk·PKRTMA,if this equation holds, then the signature is valid; otherwise, it will be discarded.


## 4.2. Overview of Kamil et al.’s CL-AS Scheme

The Setup, UserRegistration, PartialPrivateKeyGeneration, PseudonymGeneration, VehicleKeyGeneration, Sign, and Verify algorithms are the same as the above CLS scheme. In addition, the Aggregate and AggregateVerify algorithms are described as follows:(1)
Aggregate: in general, the roadside unit (RSU) acts as the aggregator. When receivingn certificateless signatures σ1=R1,V1,σ2=R2,V2,⋯,σn=Rn,Vn on messages m1∥T1,m2∥T2,⋯,mn∥Tn from n pseudo identities PIDy,1,PIDy,2,⋯,PIDy,n under the state information ∇, the RSU calculates V=∑k=1n‍Vk and R=∑k=1n‍Rk, then outputs an aggregate certificateless signature σT=R,V.(2)
AggregateVerify: generally another RSU or AS acts as the verifier. When receiving a certificateless aggregate signatureσT=R,V signed by n vehicles. Then it will run as follows:Step 1.
Check whether the timestampTk is valid, if not, it aborts, and if it holds, it runs the following steps.Step 2.
Computehk=h4PIDy,k∥mk∥ωk∥PKk∥PKRTMA∥Ppub∥Tk.Step 3.
Check whether the following equation holds.(4)V·P=R+∑k=1nhkωk·PKRTMA,if it holds, it receives all the signatures; otherwise, the signature is rejected.


## 4.3. Cryptanalysis of Kamil et al.’s CL-AS Scheme

The security problem in the scheme proposed by Kamil et al. [6] mainly lies in the coalition attack, which is a kind of attack by a number of collusive vehicles.As is described in Figure1, in the coalition attack, two or more vehicles secretly change a part of their messages such as locations to hide their real locations and routes since the RSU (verifier) receives the exchanged signature. Then something of the collusive vehicles is exchanged officially. Which will definitely harm the system and even worse cause a serious accident.Figure 1
Coalition attack diagram.We describe the coalition attack on Kamil et al.’s CL-AS scheme to illustrate its security flaws.Assume that two usersU1,U2 have pseudonym PIDy,1,PIDy,2 and message m1,m2, respectively. We show that two users can cooperate to generate valid aggregate signatures even if their individual signature is invalid. Two users can implement the coalition attack by executing the following algorithms.Step 1.
The userUii∈1,2 randomly picks di∈ℤq∗ and calculates ωi=ξiαi.Step 2.
Calculateβi=h2IDi∥IDRTMA∥s∥∇, t=h2∇, ξk=h2IDi∥PKRTMA, xi=tβi+ξiαis, vi=h4PIDy,i∥mi∥Ski1∥SKi2∥Ti, hi=h4PIDy,i∥mi∥ωi∥PKi∥PKRTMA∥Ppub∥Ti, δi=h4mi∥PKi∥∇∥Ti, yi=divi, Ω=yi·P, and Ri=δi·PKi+hi·Ai+Ω.Step 3.
Then,U1 sends h1x1 to U2; likewise, U2 sends h2x2 to U1 in a secure channel. Then U1 calculates V1=δ1SK1+h2x2+d1v1; likewise, U2 calculates V2=δ2SK2+h1x1+d2v2.Step 4.
Eventually, they can output signatureσi=Ri,Vk and transmits PIDy,i,mi,PKi,ωi,σi,Ti.
(5)V·P=V1+V2·P=δ1SK1+h2x2+d1v1+δ2SK2+h1x1+d2v2·P=∑k=12δkSKk+hktβk+ξkαks+dkvk·P=∑k=12δk·PKk+hk·Ak+ωk+∑k=12hkωk·PKRTMA=R+∑k=12hkωk·PKRTMAObviously, the signatureσi=Ri,Vi is not a valid signature. However, when the RSU or AS aggregates the signature as σ=R=R1+R2,V=V1+V2, it will be a valid signature which satisfies the following equation.Therefore, the above analysis shows that two malicious users can collude with each other to forge an aggregate signature. Actually, the coalition attack is originally caused by commutative law of addition. Similarly,n users can also forge an aggregate signature with the same algorithms. Hence, Kamil et al.’s CL-AS scheme cannot resist coalition attacks.


## 5. Our Proposed CLS and CL-AS Schemes

### 5.1. System Model

In this section, we will try to describe our system model in detail including specific explanations. In order to be more specific, the system model is shown in Figure2. There are four participants in total: trusted authority (TA), key generation center (KGC), road-side unit (RSU), and vehicle, which can be divided into two layers: the upper layer includes TA and KGC, and the lower layer consists of RSUs and vehicles. The demonstration of each participant is as follows:
(1)
TA: it is a fully trusted third party that is responsible for system initialization, user registration, system parameter generation, and system security implementation. If necessary, it can track malicious behavior and catch malicious nodes. In addition, it also has enough computing power and storage capacity.(2)
KGC: it is a partially trusted party used for generating partial private key. It can help a vehicle generate partial secret key which contribute to its privacy security. Like the TA, it also has sufficient memory, processing, and computing capabilities.(3)
RSU: it is a smart application device installed in the roadside, which is able to transmit and submit information to TA, KGC, vehicles, or other RSUs in a secure wired connection. In addition, RSU commonly has limited computing power and storage capacity.(4)
Vehicle: it is the major and basic member in VANETs, which is generally equipped with a smart device which can perform the basic function such as transmitting the vehicle’s message and performing simple calculation. In addition, vehicle commonly has limited computing power and storage capacity.Figure 2
Certificateless aggregate signature system model.Note that TA and KGC are functionally two completely different entities that can be deployed on a single server during deployment.


### 5.2. Design Requirements

For the safety of communication in VANETs, security and privacy are crucial. According to the latest research in this field, the proposed scheme for VANETs must satisfy the following security requirements:(1)
Message Integrity and Authentication: an eligible vehicle should be able to check that whether a message is sent and signed by a legitimate vehicle and is not forged or modified by the malicious entity.(2)
Identity Privacy Preservation: a vehicle should remain anonymous in all circumstances, which means that other malicious entities cannot infer its identity by taking and analyzing multiple pieces of messages about it.(3)
Traceability: the TA must have the ability to trace and obtain the vehicle’s real identity, even if the vehicle’s identity is anonymous.(4)
Unlinkability: a potentially malicious vehicle must not cross-link two messages sent by the same vehicle to prevent them from extrapolating the route of the vehicle from the information.(5)
Resistance to Attacks: a reasonable scheme should have the ability to withstand various general attacks such as the coalition attack, the impersonation attack, the modification attack, and the replay attack.


### 5.3. Our Proposed CLS Scheme

Our proposed CLS scheme includes five algorithms: Setup, PartialPrivateKeyGeneration, VehicleKeyGeneration, Sign, and Verify. The Notation to be used is listed in Table1, and descriptions for algorithms are vividly shown in Figure 3 and described as follows:
(1)
Setup: when given an appropriate security parameterλ, TA will use the λ to generate and output the param by executing the following algorithms:(2)
PartialPrivateKeyGeneration: the algorithm will eventually generate the vehicle’s partial private key through the algorithms as follows:(3)
VehicleKeyGeneration: after receiving the partial private keyPPKi, the vehicle Vi check if the equation PPKi·P=Qi+ni·PKKGC holds. If it holds, the partial private key PPKi is valid. The vehicle randomly selects its private key ρi∈ℤq∗, then calculates its public key PKVi=ρi·P.(4)
Sign: in order to achieve authentication and message integrity, when the message is received by any entity, it has to be signed and verified. A vehicleVi uses its pseudo identity PIDi and picks the latest timestamp TS. The updated timestamp TS protects a signed message against replay attacks. Given the signing key PPKi,PKVi and a traffic related message mi, the vehicle Vi performs the following steps, which are repeated every 100−300 ms in accordance with DSRC protocol [20]:(5)
Verify: when an RSU or other entity receives the signatureσ and the tuple Qi,PIDi,mi,PKVi,TS from the vehicle Vi, it can execute the algorithms to verify the message as follows:Step 1.
Firstly, select two secure prime numbersp and q, then choose a,b∈Fp, which generate an ellipic curve E defined by the equation y2=x3+ax+b mod p, where Δ=4a3+27b2≠0 (mod p) and generator P of the additive group G consisting of all the points on E.Step 2.
Chooseα∈ℤq∗ in random, which serves as the master secret key and computes master public key PKTA=α·P. KGC selects β∈ℤq∗ in random, then calculates PKKGC=β·P which is the public key of KGC.Step 3.
Select three secure hash functions in random:h1:G×0,1∗×0,1∗×G×0,1∗→ℤq∗,h2:0,1∗×G×0,1∗→ℤq∗,h3:0,1∗×0,1∗×0,1∗×G×G×0,1∗→ℤq∗.Step 4.
Store its master secret keyα in its repository and keep it safe. Then publish all the system parameter:
(6)param=p,q,a,b,P,PKTA,PKKGC,h1,h2,h3.Step 1.
The vehicleVi with its real identity RIDi randomly selects xi∈ℤq∗ as its private key and calculates its partial pseudo identity PIDi1=xi·P. Then vehicle Vi transmits (RIDi, PIDi1) to TA.Step 2.
After receiving the tuple, TA calculates another pseudo identityPIDi2=RIDi⊕h1αPIDi1∥Tcur∥PKTA∥∇, where ∇ is the system state information [19]; then TA sends the vehicle’s pseudo identity PIDi=PIDi1,PIDi2,Tcur to KGC in a secure way.Step 3.
KGC calculatesQi=yi·P, ni=h2PIDi∥Qi∥∇ and the vehicle’s partial private key PPKi=yi+h2PIDi∥Qi∥∇×β (mod p). At last, KGC transmits the tuple Qi,PPKi to vehicle Vi.Step 1.
Choose a random numberli∈ℤq∗ and calculate Li=li·P.Step 2.
Calculateri=h3mi∥PIDi∥∇∥PKVi∥Li∥TS, where timestamp TS is used to confirm time, and Si=rili+ρi+PPKi mod p.Step 3.
The signature on messagemi is σ=Li,Si; then the vehicle transmits the signature σ and Qi,PIDi,mi,PKVi,TS to the verifier.Step 1.
Check whether the TS is valid, if not, the algorithm aborts; otherwise, execute the next step.Step 2.
Calculateri=h3mi∥PIDi∥∇∥PKVi∥Li∥TS and ni=h2PIDi∥Qi∥∇Step 3.
Check whether the following equation(7)Si·P=ri·Li+PKVi+Qi+ni·PKKGCholds or not; if it holds, then the RSU or other entity will accept the signature and the massage; otherwise, it will reject the message.Table 1
List of notations.
NotationDescriptionTATrusted authorityKGCKey generation centerRSURoad-side unithi.,i=1,2,3One-way collision-resistant hash functionp,qTwo secure prime numbersEAn elliptic curve:y2=x3+ax+b mod pGAn additive group, the order of which isqPA generator of the groupGPKTA,αThe public key and private key of the TAPKKGC,βThe public key and private key of the KGCPKVi,ρiThe public key and private key of the vehiclePPKiPartial private key of the vehicleViPIDiPseudo identity of the vehicleViTSThe latest timestamp∇State informationFigure 3
The algorithm procedure.


### 5.4. Our Proposed CL-AS Scheme

The Setup, PartialPrivateKeyGeneration, VehicleKeyGeneration, Sign, and Verify algorithms of CL-AS are similar to the proposed CLS scheme. In addition, the Aggregate and AggregateVerify are described as follows. Note that the Aggregate and AggregateVerify algorithms are usually executed by the same RSU to transmit less data in the communication process.(1)
Aggregate: when an aggregator such as a RSU receivesn vehicles’ messages M=m1,m2,⋯,mn, signatures σ=σ1,σ2,⋯,σn, timestamps TS=TS1,TS2,⋯,TSn, Q=Q1,Q2,⋯,Qn, public key of each vehicle PKV=PKV1,PKV2,⋯,PKVn, L=L1,L2,⋯,Ln, and pseudo identities PID=PID1,PID2,⋯,PIDn. It can execute the following algorithms to aggregate the signature:(2)
AggregateVerify: after aggregatingn vehicles’ messages, the same RSU will execute the following algorithms to verify the aggregate signature as follows:Step 1.
Randomly choose a random listRL=a1,a2,⋯,an, where ai∈ℤq∗,1≤i≤n. Note that the random list RL is firstly introduced in [21, 22] and used for resisting coalition attacks here.Step 2.
CalculateS=∑i=1naiSi and Z=∑i=1naiQi+PKVi.Step 3.
Outputs the signatureσ=L,S and transmits M,σ,Z,RL,PID,Q,TS to the verifier.Step 1.
Check whether the timestamp listTS is valid, if not, the algorithm aborts; otherwise, it executes next step.Step 2.
For every vehicle, calculateri=h3mi∥PIDi∥∇∥PKVi∥Li∥TS and ni=h2PIDi∥Qi∥∇.Step 3.
Check whether the following equation(8)S·P=∑i=1nairi·Li+Z+∑i=1naini·PKKGCholds or not, if it holds, then the RSU or other entity will accept the signature and the message, then the RSU can transmit them to other entities; otherwise, it will reject the message.


### 5.5. Correctness of Individual Message Verification

The individual verification in the proposed scheme is correct. The correctness proof is as follows:(9)Si·P=rili+ρi+PPKi·P=rili+ρi+yi+niβ·P=rili·P+ρi·P+yi·P+niβ·P=ri·Li+PKVi+Qi+niPKKGC.


### 5.6. Correctness of Aggregate Message Verification

The aggregate verification in the proposed scheme is correct. The correctness proof is as follows:(10)S·P=∑i=1naiSi·P=∑i=1nairili+aiρi+aiPPKi·P=∑i=1nairili·P+ρi·P+yi·P+niβ·P=∑i=1nairi·Li+Z+∑i=1naini·PKKGC.


### 5.7. Security Proof of the Proposed CLS Scheme

According to Definition3, it is extremely hard to solve ECDLP. Therefore, we can prove that our CLS scheme is able to enforce nonforgery.On the basis of Definition4, assume that a probabilistic polynomial-time forger A1 can forge a signature with an advantage ε. In addition, qhi denotes random oracles hi for i=2,3, qGU denotes the Generate-User oracle, qPPK denotes Partial-Private-Key oracle, and qSK denotes the Secret-Key oracle. Then, we can know that a challenger C1 can solve ECDLP during a time scope T, where T≤120686QT/ε, if ε≥10qS+1qh2+qh3+qPPK+qGU+qSK+qS/q.
(1)
Setup:C1 chooses α and calculates PKTA=α·P which serves as its private key and master public key. Then, C1 will generate the system parameters param=P,p,q,E,G,h1,h2,h3,PKTA,PKKGC, and transmit it to A1.(i)
h2 Hash Query: C1 will examine whether the hash list Lh2 has the corresponding tuple if it receives the query with parameter PIDi,Qi from A1. If not, C1 will select a random number τh2∈ℤq∗ and put it in the list Lh2. If so, it needs to transmit τh2=h2PIDi∥Qi∥∇ to A1.(ii)
h3 Hash Query: C1 will examine whether the hash list Lh3 has the corresponding tuple mi,PIDi,PKVi,Zi,TS,τh3 if it receives the query with parameter param=mi,PIDi,PKVi,Li,TS from A1. If not, C1 will choose a random number τh3∈ℤq∗ and put the tuple mi,PIDi,PKVi,Li,TS,τh3 in the list Lh3. If so, it will transmit τh3=h3mi∥PIDi∥∇∥PKVi∥Li∥TS to A1. Eventually, C1 will transmit τh3=h3mi∥PIDi∥∇∥PKVi∥Li∥TS to A1.(2)
Partial-Private-Key Query: after receiving a query about the identityPIDi from A1, C1 will calculate Qi=yi·P, where yi is randomly selected, and check whether the hash list Lh2 has the corresponding tuple PIDi,Qi,τh2. If so, C1 will calculate PPKi=yi+h2PIDi∥Qi∥∇×α mod p and transmit the pairial private key of vehicle ViPPKi to A1. If not, it will halt.(3)
User-Generation Query: suppose that the query is on the basis of the pseudo identityPIDi(i)
C1 will check whether PKVi exists in the list L, if the list L includes PIDi,PKVi,ρi. If not, a random number ρi∈ℤq∗ will be selected and C1 will calculate PKVi=ρi·P. If so, it will transmit PKVi to A1. Eventually, the chanllenger C1 will transmit PKVi to A1 and update the list(ii)
C1 will set PKVi=⊥ if the tuple PIDi,PKVi,ρi does not exist in the list L. Then, a random number ρi∈ℤq∗ will be chosen and PKVi=ρi·P will be calculated and ρi will be regarded as a private key. Eventually, C1 will transmit PKVi to A1 and put the tuple PIDi,PKVi,ρi to the list L(4)
Private-Key Query:(i)
C1 will check whether ρi exists in the list L, if the list L includes PIDi,PKVi,ρi. If not, it will access a UserGeneration query to output the public key PKVi=ρi·P. Eventually, the chanllenger C1 will transmit ρi to A1 and update the list(ii)
C1 will access a User-Generation query if the tuple PIDi,PKVi,ρi does not exist int he list L. Eventually, C1 will transmit ρi to A1 and put the tuple PIDi,PKVi,ρi to the list L(5)
Sign Query: after receiving a legitimate query about the messagemi of pseudo identity PIDi, C1 will check the tuple PIDi,Qi,τh2 in the hash list Lh2. Hence, it can easily get the value τh2 from the tuple and select two random numbers li and ri. Then, C1 will choose another two random numbers si and ni. Furthermore, C1 will calculate Zi=si·P−ni·PKKGC and Si=si. Eventually, it will transmit Li,Si to A1 and put the tuple mi,PIDi,PKVi,Li,TS,τh3 in the list Lh3.Theorem 7.
According to the random oracle, when faced with an adaptive chosen message attack, our proposed scheme has the capacity of unforgeability.Proof.
Assume that an ECDLP sampleP,Q=x·P is given, the elliptic curve E holds two points P and Q, and an adversary A1 is able to forge message PIDi,PKVi,mi,TS,σi. Hence, we start a game between a challenger C1 and the adversary A1, which can execute and manipulate A1 to solve ECDLP with a nonnegligible probability.We know the forking lemma in Definition4 and apply it to our proposed scheme. After using the same random elements to replay A1, C1 succeeds in getting two legitimate signatures σi=Zi,Si and σ′i=L′i,S′i during a polynomial time period, where Si=ri·Li+Qi+PKVi (mod p) and S′i=t′i·Li+Qi+PKVi (mod p) by computing.
(11)t′iSi−riS′it′i−rimodp=t′irili+t′iQi+t′iPKVi−rit′ili−riPPKi−riQi+riPKVit′i−rimodp=Qi+PKVi.In conclusion, ifε≥10qS+1qh2+qh3+qPPK+qUG+qSK+qS/q, then C1 is able to break the ECDLP during a time period which is less than 120686QT/ε. However, this conclusion is inconsistent with the difficulty of solving the ECDLP. Therefore, we can define that our proposed CLS scheme can resist a forgery attack.


### 5.8. Security Proof of the Proposed CL-AS Scheme

According to Definition3, it is extremely hard to solve ECDLP. Therefore, we can prove that our scheme is able to enforce nonforgery. Furthermore, we will prove that our CL-AS scheme can also resist coalition attack.
(1)
Setup: a random numberα is selected as the master secret key, and the public key can also be calculated as PKTA=α·P. Then, the oracle simulation is ready to run. In this whole game, C2 maintains a list L=PIDi,PPKi,PKVi,,ρi and responds to A2’s oracle as follows.(i)
h2 Query: after receiving a pseudo identity PIDi, C2 will throw a coin ci∈0,1, where 0 holds a probability ε, and 1 holds a probability 1−ε, then C2 will select wi1∈ℤq∗. If ci=1, C2 will output Qi=wi1·P. Otherwise, it will define Qi=ωi1·P. C2 will put the tuple PIDi,wi1,ci,Qi in a list Lh2=PIDi,wi1,ci,Qi to trace what the queries respond no mather what the value ci is.Theorem 8.
According to the random oracle, when faced with an adaptive chosen message attack, our proposed CL-AS scheme has the capacity of unforgeability.Proof.
Suppose that our CL-AS scheme can be broken by forgerA2. We can construct a challenger C2 using forgery algorithm A2. Challenger C2 is able to execute the following steps by interacting with A2.Then,A2 will transmit n vehicles with identities from the list LPID∗=PID1∗,PID2∗,⋯,PIDn∗, public keys from the list LPKV∗=PKV1∗,PKV2∗,⋯,PKVn∗, n messages LM∗=m1∗,m2∗,⋯,mn∗, a random list RL∗=a1∗,a2∗,⋯,an∗, and a certificateless aggregate signature σ∗=L∗,S∗. At the beginning, C2 will select the n tuples PIDi∗,wi1∗,ci∗,Qi∗ for i=1,2,⋯,n in the list Lh2 and precede only ck=1 and cj=0 for j=1,2,⋯,n,j≠k. Note that the Sign oracle has not received the tuple PIDk∗,PKVk∗,mk∗. Otherwise, C2 will halt and fail. This success case signifies that Qk=wk1·PKTA and Qj=wj1·P for j=1,2,⋯,n,j≠k. In addition, the aggregate signature σ∗=L∗,S∗ is supposed to satisfy the aggregate verification equation S·P=∑i=1nairi·Li+Z+∑i=1naini·PKKGC.Accordingly,C2 checks the tuples mi∗,PIDi∗,PKVi∗,Zi∗,wi2∗ in the list Lh3 and the tuple PIDi∗,PPKi∗,PKVi∗,ρi from L. Later, it calculates Si∗=wi1∗·α mod p, which will satisfy Si∗·P=wi1∗·PKTA=Qi∗ for i=1,2,⋯,n,i≠k. Eventually, C2 constructs S′∗ as S′∗=S∗−∑i=1,i≠knaiSi∗, S′∗=PPKi∗+∑i=1nwi2∗ri∗modp for L∗=li∗ and li∗∈ℤq∗ for 1≤i≤n. C2 will select a random number hk∗∈ℤq∗ and calculate Z∗=hk∗−1∑i=1nwi2∗airi·Li+Qi+PKVi.Hence, the hash valueh3mk∗,PIDk∗,PKVi∗,Zk∗ is defined as hk∗. It will use hk∗ until it does not repeat if the list Lh3 holds the tuple h3mk∗,PIDk∗,PKVk∗,Zk∗. Consequently, the signature L′∗,S′∗ is a legitimate certificateless signature on message mk∗ for the reason that the equation below:
(12)Qvk∗∗+hk,0∗+hk∗Z′∗=Qvk∗∗+hk,0∗+hk∗hk∗−1∑i=1nwi2∗airi·Li+Qi+PKVi=Qvk∗∗+hk,0∗+∑i=1nwi2∗airi·Li+Qi+PKVi=PPKk∗·P+∑i=1nwi2∗airi·Li+Qi+PKVi=S′∗·P.Eventually,S can get the signature L′∗,S′∗ as a forgery of the certificateless signature scheme. However, this conclusion is inconsistent with the difficulty of solving the ECDLP. Therefore, we can define that our proposed CLS scheme can resist a forgery attack.Theorem 9.
The proposed certificateless aggregate signature (CL-AS) scheme can resist coalition attacks.Proof.
Assume that there are two malicious vehiclesV1 and V2 with pseudonyms PID1 and PID2 and messages m1 and m2, respectively, and that all other system params are published by TA and KGC. According to the description in Subsection 4.3, two vehicles V1 and V2 would like to execute similar algorithms to forge valid signatures. However, our proposed scheme can perfectly resist the coalition attacks; the detailed descriptions are as follows:
To begin with, two vehiclesVii∈1,2 pick their own private key ρi and calculate their corresponding public key PKVi=ρi·P.According to the aforementioned algorithms in Subsection5.7, two malicious vehicles execute the algorithms in order but secretly exchange their riLi, which is a part of the signature. Eventually, two vehicles transmit their messages mi, signatures σi, timestamp TSi, and pseudo identity PIDi to the aggregator.When the aggregator receives the above information, it will aggregate the signature as follows: firstly choose a random listRL=a1,a2, where ai∈ℤq∗,1≤i≤n, then calculate S=∑i=12aiSi and Z=∑i=12aiQi+PKVi. Finally, the aggregator will output the signature σ=L,S and transmits M,σ,Z,RL,PID,Q,T to the verifier.In the last step, the verifier will check the equationS·P=∑i=12airi·Li+Z+∑i=1naini·PKKGC holds or not. Unfortunately, the equation is impossible as follows:
(13)S·P=a1r2l2+a1ρi+a1PPK1+a2t1l1+a2ρi+a2PPK2·P=a1t2·L2+a1·PKV1+a1·Q1+a1n1·PKKGC+a2t1·L1+a2·PKV2+a2·Q2+a2n2·PKKGC=a1t2·L2+a2·t1L1+Z+∑n=12aini·PKKGC≠∑i=12airi·Li+Z+∑n=12aini·PKKGC.One can find that the random list plays an important role in resisting the coalition attacks. And the 2-vehicle situation can also be developed ton vehicles simply with a fully the same method and algorithm, which can prove that our proposed certificateless aggregate signature (CL-AS) scheme can resist coalition attacks.


## 5.1. System Model

In this section, we will try to describe our system model in detail including specific explanations. In order to be more specific, the system model is shown in Figure2. There are four participants in total: trusted authority (TA), key generation center (KGC), road-side unit (RSU), and vehicle, which can be divided into two layers: the upper layer includes TA and KGC, and the lower layer consists of RSUs and vehicles. The demonstration of each participant is as follows:
(1)
TA: it is a fully trusted third party that is responsible for system initialization, user registration, system parameter generation, and system security implementation. If necessary, it can track malicious behavior and catch malicious nodes. In addition, it also has enough computing power and storage capacity.(2)
KGC: it is a partially trusted party used for generating partial private key. It can help a vehicle generate partial secret key which contribute to its privacy security. Like the TA, it also has sufficient memory, processing, and computing capabilities.(3)
RSU: it is a smart application device installed in the roadside, which is able to transmit and submit information to TA, KGC, vehicles, or other RSUs in a secure wired connection. In addition, RSU commonly has limited computing power and storage capacity.(4)
Vehicle: it is the major and basic member in VANETs, which is generally equipped with a smart device which can perform the basic function such as transmitting the vehicle’s message and performing simple calculation. In addition, vehicle commonly has limited computing power and storage capacity.Figure 2
Certificateless aggregate signature system model.Note that TA and KGC are functionally two completely different entities that can be deployed on a single server during deployment.


## 5.2. Design Requirements

For the safety of communication in VANETs, security and privacy are crucial. According to the latest research in this field, the proposed scheme for VANETs must satisfy the following security requirements:(1)
Message Integrity and Authentication: an eligible vehicle should be able to check that whether a message is sent and signed by a legitimate vehicle and is not forged or modified by the malicious entity.(2)
Identity Privacy Preservation: a vehicle should remain anonymous in all circumstances, which means that other malicious entities cannot infer its identity by taking and analyzing multiple pieces of messages about it.(3)
Traceability: the TA must have the ability to trace and obtain the vehicle’s real identity, even if the vehicle’s identity is anonymous.(4)
Unlinkability: a potentially malicious vehicle must not cross-link two messages sent by the same vehicle to prevent them from extrapolating the route of the vehicle from the information.(5)
Resistance to Attacks: a reasonable scheme should have the ability to withstand various general attacks such as the coalition attack, the impersonation attack, the modification attack, and the replay attack.


## 5.3. Our Proposed CLS Scheme

Our proposed CLS scheme includes five algorithms: Setup, PartialPrivateKeyGeneration, VehicleKeyGeneration, Sign, and Verify. The Notation to be used is listed in Table1, and descriptions for algorithms are vividly shown in Figure 3 and described as follows:
(1)
Setup: when given an appropriate security parameterλ, TA will use the λ to generate and output the param by executing the following algorithms:(2)
PartialPrivateKeyGeneration: the algorithm will eventually generate the vehicle’s partial private key through the algorithms as follows:(3)
VehicleKeyGeneration: after receiving the partial private keyPPKi, the vehicle Vi check if the equation PPKi·P=Qi+ni·PKKGC holds. If it holds, the partial private key PPKi is valid. The vehicle randomly selects its private key ρi∈ℤq∗, then calculates its public key PKVi=ρi·P.(4)
Sign: in order to achieve authentication and message integrity, when the message is received by any entity, it has to be signed and verified. A vehicleVi uses its pseudo identity PIDi and picks the latest timestamp TS. The updated timestamp TS protects a signed message against replay attacks. Given the signing key PPKi,PKVi and a traffic related message mi, the vehicle Vi performs the following steps, which are repeated every 100−300 ms in accordance with DSRC protocol [20]:(5)
Verify: when an RSU or other entity receives the signatureσ and the tuple Qi,PIDi,mi,PKVi,TS from the vehicle Vi, it can execute the algorithms to verify the message as follows:Step 1.
Firstly, select two secure prime numbersp and q, then choose a,b∈Fp, which generate an ellipic curve E defined by the equation y2=x3+ax+b mod p, where Δ=4a3+27b2≠0 (mod p) and generator P of the additive group G consisting of all the points on E.Step 2.
Chooseα∈ℤq∗ in random, which serves as the master secret key and computes master public key PKTA=α·P. KGC selects β∈ℤq∗ in random, then calculates PKKGC=β·P which is the public key of KGC.Step 3.
Select three secure hash functions in random:h1:G×0,1∗×0,1∗×G×0,1∗→ℤq∗,h2:0,1∗×G×0,1∗→ℤq∗,h3:0,1∗×0,1∗×0,1∗×G×G×0,1∗→ℤq∗.Step 4.
Store its master secret keyα in its repository and keep it safe. Then publish all the system parameter:
(6)param=p,q,a,b,P,PKTA,PKKGC,h1,h2,h3.Step 1.
The vehicleVi with its real identity RIDi randomly selects xi∈ℤq∗ as its private key and calculates its partial pseudo identity PIDi1=xi·P. Then vehicle Vi transmits (RIDi, PIDi1) to TA.Step 2.
After receiving the tuple, TA calculates another pseudo identityPIDi2=RIDi⊕h1αPIDi1∥Tcur∥PKTA∥∇, where ∇ is the system state information [19]; then TA sends the vehicle’s pseudo identity PIDi=PIDi1,PIDi2,Tcur to KGC in a secure way.Step 3.
KGC calculatesQi=yi·P, ni=h2PIDi∥Qi∥∇ and the vehicle’s partial private key PPKi=yi+h2PIDi∥Qi∥∇×β (mod p). At last, KGC transmits the tuple Qi,PPKi to vehicle Vi.Step 1.
Choose a random numberli∈ℤq∗ and calculate Li=li·P.Step 2.
Calculateri=h3mi∥PIDi∥∇∥PKVi∥Li∥TS, where timestamp TS is used to confirm time, and Si=rili+ρi+PPKi mod p.Step 3.
The signature on messagemi is σ=Li,Si; then the vehicle transmits the signature σ and Qi,PIDi,mi,PKVi,TS to the verifier.Step 1.
Check whether the TS is valid, if not, the algorithm aborts; otherwise, execute the next step.Step 2.
Calculateri=h3mi∥PIDi∥∇∥PKVi∥Li∥TS and ni=h2PIDi∥Qi∥∇Step 3.
Check whether the following equation(7)Si·P=ri·Li+PKVi+Qi+ni·PKKGCholds or not; if it holds, then the RSU or other entity will accept the signature and the massage; otherwise, it will reject the message.Table 1
List of notations.
NotationDescriptionTATrusted authorityKGCKey generation centerRSURoad-side unithi.,i=1,2,3One-way collision-resistant hash functionp,qTwo secure prime numbersEAn elliptic curve:y2=x3+ax+b mod pGAn additive group, the order of which isqPA generator of the groupGPKTA,αThe public key and private key of the TAPKKGC,βThe public key and private key of the KGCPKVi,ρiThe public key and private key of the vehiclePPKiPartial private key of the vehicleViPIDiPseudo identity of the vehicleViTSThe latest timestamp∇State informationFigure 3
The algorithm procedure.


## 5.4. Our Proposed CL-AS Scheme

The Setup, PartialPrivateKeyGeneration, VehicleKeyGeneration, Sign, and Verify algorithms of CL-AS are similar to the proposed CLS scheme. In addition, the Aggregate and AggregateVerify are described as follows. Note that the Aggregate and AggregateVerify algorithms are usually executed by the same RSU to transmit less data in the communication process.(1)
Aggregate: when an aggregator such as a RSU receivesn vehicles’ messages M=m1,m2,⋯,mn, signatures σ=σ1,σ2,⋯,σn, timestamps TS=TS1,TS2,⋯,TSn, Q=Q1,Q2,⋯,Qn, public key of each vehicle PKV=PKV1,PKV2,⋯,PKVn, L=L1,L2,⋯,Ln, and pseudo identities PID=PID1,PID2,⋯,PIDn. It can execute the following algorithms to aggregate the signature:(2)
AggregateVerify: after aggregatingn vehicles’ messages, the same RSU will execute the following algorithms to verify the aggregate signature as follows:Step 1.
Randomly choose a random listRL=a1,a2,⋯,an, where ai∈ℤq∗,1≤i≤n. Note that the random list RL is firstly introduced in [21, 22] and used for resisting coalition attacks here.Step 2.
CalculateS=∑i=1naiSi and Z=∑i=1naiQi+PKVi.Step 3.
Outputs the signatureσ=L,S and transmits M,σ,Z,RL,PID,Q,TS to the verifier.Step 1.
Check whether the timestamp listTS is valid, if not, the algorithm aborts; otherwise, it executes next step.Step 2.
For every vehicle, calculateri=h3mi∥PIDi∥∇∥PKVi∥Li∥TS and ni=h2PIDi∥Qi∥∇.Step 3.
Check whether the following equation(8)S·P=∑i=1nairi·Li+Z+∑i=1naini·PKKGCholds or not, if it holds, then the RSU or other entity will accept the signature and the message, then the RSU can transmit them to other entities; otherwise, it will reject the message.


## 5.5. Correctness of Individual Message Verification

The individual verification in the proposed scheme is correct. The correctness proof is as follows:(9)Si·P=rili+ρi+PPKi·P=rili+ρi+yi+niβ·P=rili·P+ρi·P+yi·P+niβ·P=ri·Li+PKVi+Qi+niPKKGC.


## 5.6. Correctness of Aggregate Message Verification

The aggregate verification in the proposed scheme is correct. The correctness proof is as follows:(10)S·P=∑i=1naiSi·P=∑i=1nairili+aiρi+aiPPKi·P=∑i=1nairili·P+ρi·P+yi·P+niβ·P=∑i=1nairi·Li+Z+∑i=1naini·PKKGC.


## 5.7. Security Proof of the Proposed CLS Scheme

According to Definition3, it is extremely hard to solve ECDLP. Therefore, we can prove that our CLS scheme is able to enforce nonforgery.On the basis of Definition4, assume that a probabilistic polynomial-time forger A1 can forge a signature with an advantage ε. In addition, qhi denotes random oracles hi for i=2,3, qGU denotes the Generate-User oracle, qPPK denotes Partial-Private-Key oracle, and qSK denotes the Secret-Key oracle. Then, we can know that a challenger C1 can solve ECDLP during a time scope T, where T≤120686QT/ε, if ε≥10qS+1qh2+qh3+qPPK+qGU+qSK+qS/q.
(1)
Setup:C1 chooses α and calculates PKTA=α·P which serves as its private key and master public key. Then, C1 will generate the system parameters param=P,p,q,E,G,h1,h2,h3,PKTA,PKKGC, and transmit it to A1.(i)
h2 Hash Query: C1 will examine whether the hash list Lh2 has the corresponding tuple if it receives the query with parameter PIDi,Qi from A1. If not, C1 will select a random number τh2∈ℤq∗ and put it in the list Lh2. If so, it needs to transmit τh2=h2PIDi∥Qi∥∇ to A1.(ii)
h3 Hash Query: C1 will examine whether the hash list Lh3 has the corresponding tuple mi,PIDi,PKVi,Zi,TS,τh3 if it receives the query with parameter param=mi,PIDi,PKVi,Li,TS from A1. If not, C1 will choose a random number τh3∈ℤq∗ and put the tuple mi,PIDi,PKVi,Li,TS,τh3 in the list Lh3. If so, it will transmit τh3=h3mi∥PIDi∥∇∥PKVi∥Li∥TS to A1. Eventually, C1 will transmit τh3=h3mi∥PIDi∥∇∥PKVi∥Li∥TS to A1.(2)
Partial-Private-Key Query: after receiving a query about the identityPIDi from A1, C1 will calculate Qi=yi·P, where yi is randomly selected, and check whether the hash list Lh2 has the corresponding tuple PIDi,Qi,τh2. If so, C1 will calculate PPKi=yi+h2PIDi∥Qi∥∇×α mod p and transmit the pairial private key of vehicle ViPPKi to A1. If not, it will halt.(3)
User-Generation Query: suppose that the query is on the basis of the pseudo identityPIDi(i)
C1 will check whether PKVi exists in the list L, if the list L includes PIDi,PKVi,ρi. If not, a random number ρi∈ℤq∗ will be selected and C1 will calculate PKVi=ρi·P. If so, it will transmit PKVi to A1. Eventually, the chanllenger C1 will transmit PKVi to A1 and update the list(ii)
C1 will set PKVi=⊥ if the tuple PIDi,PKVi,ρi does not exist in the list L. Then, a random number ρi∈ℤq∗ will be chosen and PKVi=ρi·P will be calculated and ρi will be regarded as a private key. Eventually, C1 will transmit PKVi to A1 and put the tuple PIDi,PKVi,ρi to the list L(4)
Private-Key Query:(i)
C1 will check whether ρi exists in the list L, if the list L includes PIDi,PKVi,ρi. If not, it will access a UserGeneration query to output the public key PKVi=ρi·P. Eventually, the chanllenger C1 will transmit ρi to A1 and update the list(ii)
C1 will access a User-Generation query if the tuple PIDi,PKVi,ρi does not exist int he list L. Eventually, C1 will transmit ρi to A1 and put the tuple PIDi,PKVi,ρi to the list L(5)
Sign Query: after receiving a legitimate query about the messagemi of pseudo identity PIDi, C1 will check the tuple PIDi,Qi,τh2 in the hash list Lh2. Hence, it can easily get the value τh2 from the tuple and select two random numbers li and ri. Then, C1 will choose another two random numbers si and ni. Furthermore, C1 will calculate Zi=si·P−ni·PKKGC and Si=si. Eventually, it will transmit Li,Si to A1 and put the tuple mi,PIDi,PKVi,Li,TS,τh3 in the list Lh3.Theorem 7.
According to the random oracle, when faced with an adaptive chosen message attack, our proposed scheme has the capacity of unforgeability.Proof.
Assume that an ECDLP sampleP,Q=x·P is given, the elliptic curve E holds two points P and Q, and an adversary A1 is able to forge message PIDi,PKVi,mi,TS,σi. Hence, we start a game between a challenger C1 and the adversary A1, which can execute and manipulate A1 to solve ECDLP with a nonnegligible probability.We know the forking lemma in Definition4 and apply it to our proposed scheme. After using the same random elements to replay A1, C1 succeeds in getting two legitimate signatures σi=Zi,Si and σ′i=L′i,S′i during a polynomial time period, where Si=ri·Li+Qi+PKVi (mod p) and S′i=t′i·Li+Qi+PKVi (mod p) by computing.
(11)t′iSi−riS′it′i−rimodp=t′irili+t′iQi+t′iPKVi−rit′ili−riPPKi−riQi+riPKVit′i−rimodp=Qi+PKVi.In conclusion, ifε≥10qS+1qh2+qh3+qPPK+qUG+qSK+qS/q, then C1 is able to break the ECDLP during a time period which is less than 120686QT/ε. However, this conclusion is inconsistent with the difficulty of solving the ECDLP. Therefore, we can define that our proposed CLS scheme can resist a forgery attack.


## 5.8. Security Proof of the Proposed CL-AS Scheme

According to Definition3, it is extremely hard to solve ECDLP. Therefore, we can prove that our scheme is able to enforce nonforgery. Furthermore, we will prove that our CL-AS scheme can also resist coalition attack.
(1)
Setup: a random numberα is selected as the master secret key, and the public key can also be calculated as PKTA=α·P. Then, the oracle simulation is ready to run. In this whole game, C2 maintains a list L=PIDi,PPKi,PKVi,,ρi and responds to A2’s oracle as follows.(i)
h2 Query: after receiving a pseudo identity PIDi, C2 will throw a coin ci∈0,1, where 0 holds a probability ε, and 1 holds a probability 1−ε, then C2 will select wi1∈ℤq∗. If ci=1, C2 will output Qi=wi1·P. Otherwise, it will define Qi=ωi1·P. C2 will put the tuple PIDi,wi1,ci,Qi in a list Lh2=PIDi,wi1,ci,Qi to trace what the queries respond no mather what the value ci is.Theorem 8.
According to the random oracle, when faced with an adaptive chosen message attack, our proposed CL-AS scheme has the capacity of unforgeability.Proof.
Suppose that our CL-AS scheme can be broken by forgerA2. We can construct a challenger C2 using forgery algorithm A2. Challenger C2 is able to execute the following steps by interacting with A2.Then,A2 will transmit n vehicles with identities from the list LPID∗=PID1∗,PID2∗,⋯,PIDn∗, public keys from the list LPKV∗=PKV1∗,PKV2∗,⋯,PKVn∗, n messages LM∗=m1∗,m2∗,⋯,mn∗, a random list RL∗=a1∗,a2∗,⋯,an∗, and a certificateless aggregate signature σ∗=L∗,S∗. At the beginning, C2 will select the n tuples PIDi∗,wi1∗,ci∗,Qi∗ for i=1,2,⋯,n in the list Lh2 and precede only ck=1 and cj=0 for j=1,2,⋯,n,j≠k. Note that the Sign oracle has not received the tuple PIDk∗,PKVk∗,mk∗. Otherwise, C2 will halt and fail. This success case signifies that Qk=wk1·PKTA and Qj=wj1·P for j=1,2,⋯,n,j≠k. In addition, the aggregate signature σ∗=L∗,S∗ is supposed to satisfy the aggregate verification equation S·P=∑i=1nairi·Li+Z+∑i=1naini·PKKGC.Accordingly,C2 checks the tuples mi∗,PIDi∗,PKVi∗,Zi∗,wi2∗ in the list Lh3 and the tuple PIDi∗,PPKi∗,PKVi∗,ρi from L. Later, it calculates Si∗=wi1∗·α mod p, which will satisfy Si∗·P=wi1∗·PKTA=Qi∗ for i=1,2,⋯,n,i≠k. Eventually, C2 constructs S′∗ as S′∗=S∗−∑i=1,i≠knaiSi∗, S′∗=PPKi∗+∑i=1nwi2∗ri∗modp for L∗=li∗ and li∗∈ℤq∗ for 1≤i≤n. C2 will select a random number hk∗∈ℤq∗ and calculate Z∗=hk∗−1∑i=1nwi2∗airi·Li+Qi+PKVi.Hence, the hash valueh3mk∗,PIDk∗,PKVi∗,Zk∗ is defined as hk∗. It will use hk∗ until it does not repeat if the list Lh3 holds the tuple h3mk∗,PIDk∗,PKVk∗,Zk∗. Consequently, the signature L′∗,S′∗ is a legitimate certificateless signature on message mk∗ for the reason that the equation below:
(12)Qvk∗∗+hk,0∗+hk∗Z′∗=Qvk∗∗+hk,0∗+hk∗hk∗−1∑i=1nwi2∗airi·Li+Qi+PKVi=Qvk∗∗+hk,0∗+∑i=1nwi2∗airi·Li+Qi+PKVi=PPKk∗·P+∑i=1nwi2∗airi·Li+Qi+PKVi=S′∗·P.Eventually,S can get the signature L′∗,S′∗ as a forgery of the certificateless signature scheme. However, this conclusion is inconsistent with the difficulty of solving the ECDLP. Therefore, we can define that our proposed CLS scheme can resist a forgery attack.Theorem 9.
The proposed certificateless aggregate signature (CL-AS) scheme can resist coalition attacks.Proof.
Assume that there are two malicious vehiclesV1 and V2 with pseudonyms PID1 and PID2 and messages m1 and m2, respectively, and that all other system params are published by TA and KGC. According to the description in Subsection 4.3, two vehicles V1 and V2 would like to execute similar algorithms to forge valid signatures. However, our proposed scheme can perfectly resist the coalition attacks; the detailed descriptions are as follows:
To begin with, two vehiclesVii∈1,2 pick their own private key ρi and calculate their corresponding public key PKVi=ρi·P.According to the aforementioned algorithms in Subsection5.7, two malicious vehicles execute the algorithms in order but secretly exchange their riLi, which is a part of the signature. Eventually, two vehicles transmit their messages mi, signatures σi, timestamp TSi, and pseudo identity PIDi to the aggregator.When the aggregator receives the above information, it will aggregate the signature as follows: firstly choose a random listRL=a1,a2, where ai∈ℤq∗,1≤i≤n, then calculate S=∑i=12aiSi and Z=∑i=12aiQi+PKVi. Finally, the aggregator will output the signature σ=L,S and transmits M,σ,Z,RL,PID,Q,T to the verifier.In the last step, the verifier will check the equationS·P=∑i=12airi·Li+Z+∑i=1naini·PKKGC holds or not. Unfortunately, the equation is impossible as follows:
(13)S·P=a1r2l2+a1ρi+a1PPK1+a2t1l1+a2ρi+a2PPK2·P=a1t2·L2+a1·PKV1+a1·Q1+a1n1·PKKGC+a2t1·L1+a2·PKV2+a2·Q2+a2n2·PKKGC=a1t2·L2+a2·t1L1+Z+∑n=12aini·PKKGC≠∑i=12airi·Li+Z+∑n=12aini·PKKGC.One can find that the random list plays an important role in resisting the coalition attacks. And the 2-vehicle situation can also be developed ton vehicles simply with a fully the same method and algorithm, which can prove that our proposed certificateless aggregate signature (CL-AS) scheme can resist coalition attacks.


## 6. Performance and Security Analysis

### 6.1. Security Analysis

(1)
Traceability: in the proposed scheme, only TA has the real identity of the certain vehicle. After submitting the pseudo identityPIDi=PIDi1,PIDi2,Tcur, TA can easily trace back to the vehicle’s real identity RIDi in accordance with the equation PIDi2=RIDi⊕h1αPIDi1∥Tcur∥PKTA∥∇. Therefore, according to the RID list, TA can trace back to the certain vehicle Vi, even revoke it. (RIDi,PIDi1)(2)
Message integrity and authentication: according to Definition3, the ECDLP problem is hard, so that no polynomial adversary can forge a valid message. Therefore, the verifier can verify the validity and integrity of the message Qi,PIDi,PKVi,mi,TS,σi by verifying whether the equation Si·P=riLi+PKVi+Qi+ni·PKKGC holds or not. Therefore, our proposed scheme for VANETs provides message authentication and integrity.(3)
Resistance to replay attacks: the proposed scheme can resist the replay attack for the reason that the tupleQi,PIDi,PKVi,mi,TS,σi includes the timestamp TS. RSU and other vehicles will check the validity of the signature, so they are able to detect the replay of the message. Hence, our proposed scheme for VANETs can resist replay attacks.(4)
Resistance to coalition attacks: our proposed scheme can resist the coalition attacks, because we improve the signature generation process. To be specific, we choose a random list to change the ratio in the equationS=∑i=1naiSi. Therefore, our scheme uses this method to resist the coalition attacks.(5)
Resistance to stealing of the check table: in the proposed scheme, TA, KGC, vehicles, and RSUs do not require a check list. Therefore, an attacker cannot complete an attack by stealing any checklist. Hence, the proposed scheme can resist the attack of the checklist.


### 6.2. Performance Analysis

In this section, we will discuss the performance of the proposed scheme and related schemes and make a comparison in detail. We adopt the method of computation evaluation where the bilinear pairing on the security level of 80 bits is created as follows:e¯:G1×G2→GT, where G1 is an additive group generated by a point P¯ with order q¯ on a super singular elliptic curve E¯:y2=x3+x mod p¯ with embedding degree 2, p¯ is a 512-bit prime number, q¯ is a 160-bit prime number [25]. The ECC on the security of 80 bits is constructed as follows: G is an additive group with order q that is generated on a nonsingular elliptic curve E:y2=x3+ax+b mod p, where p,q are 160-bit primes and a, b∈ℤq∗. The experiment is conducted using the well-known python cryptographic library PyCryptodome on a desktop running Intel I5-9400 @ 2.90 GHz processor, with 16 GB memory running Windows 10 operating system. The notations of the cryptographic operations used in this paper and their running times are given in Table 2. Table 3 shows the summary of the computation costs in terms of signing a message, verifying a single message, and verifying n messages.Table 2
Cryptographic operation notations and executing time.
OperationDescriptionTime (ms)TbpBilinear pairing operation4.1603Tbp−mScalar multiplication in bilinear pairing operation1.6722Tbp−aAddition in bilinear pairing operation0.0069Te−mScalar multiplication in ECC operation1.1280Te−aAddition in ECC operation0.0339ThOne-way hash function0.0360Table 3
Comparison of our proposed scheme with other related schemes.
SchemeIndividual signIndividual verifyAggregate verifyCoalition attacks resistanceWith pairingKamil et al. [6]3Te−m+2Te−a+3Th=3.5598ms2Te−m+Te−a+Th=2.6988ms2Te−m+nTe−a+nTh=0.0699n+2.2899msNoNoKumar et al. [12]4Te−m+2Te−a+3Th=4.6878ms4Te−m+3Te−a+4Th=4.7577ms4Te−m+3nTe−a+4nTh=0.2457n+4.512msNoYesYang et al. [13]4Tbp−m+2Tbp−a+3Th=6.9582ms3Tbp+3Tbp−m+Tbp−a+4Th=17.9111ms2nTbp+3nTbp−m+nTbp−a+4nTh=13.7001nmsYesYesCui et al. [17]Te−m+Te−a+Th=1.1979ms3Te−m+2Te−a+2Th=3.5238msn+2Te−m+n+2Te−a+2nTh=1.2339n+2.3238msNoNoZhao et al. [23]Te−m+2Th=1.2ms4Te−m+3Te−a+Th=4.6497msn+2Te−m+n+3Te−a+nTh=1.1979n+2.3577msNoNoMalhi et al. [24]4Tbp−m+2Tbp−a+Th=6.8862ms3Tbp+3Tbp−m+Tbp−a+2Th=17.8391ms3Tbp+3nTbp−m+nTbp−a+2nTh=5.2061n+12.633msNoYesOur schemeTe−m+Th=1.164ms2Te−m+3Te−a+3Th=3.5577msn+1Te−m+2Te−a+2nTh=1.2n+1.1958msYesNoIn [13, 24], their schemes choose to use bilinear pairing, which significantly increases their operation time. As a contrast, other four schemes [6, 12, 17, 23] do not use bilinear pairing, which can substantially reduce computation time.In our scheme,Li=li·P uses a scalar multiplication in ECC operation and the calculation of ri uses a one-way hash function during the individual sign process. In individual verification, we use three scalar multiplication operations for Si·P, ri·Li, and ni·PKKGC, three addition operations, and two one-way hash function operations for the calculations of ri and ni. In aggregate verification process, we use n+2 scalar multiplication operations for ∑i=1nairi·Li, S·P, and ∑i=1naini·PKKGC, two addition operations, and 2n one-way hash function operations for each ni and ri. By comprision, our scheme has low time complexity and high efficiency. In addition, our scheme can resist coalition attacks, which are a special and security feature that no other scheme has.We use the data in Table3 to generate three figures, which can intuitively compare other related schemes with our scheme. In Figures 4(a)–4(c), we can get the conclusion that our scheme has a considerably low delay in sign and verification procedure, which reveals that our scheme has a much higher efficiency.Figure 4
Time cost of different schemes in three cases.
(a)
Individual sign cost(b)
Individual verification cost(c)
Aggregate verification cost


## 6.1. Security Analysis

(1)
Traceability: in the proposed scheme, only TA has the real identity of the certain vehicle. After submitting the pseudo identityPIDi=PIDi1,PIDi2,Tcur, TA can easily trace back to the vehicle’s real identity RIDi in accordance with the equation PIDi2=RIDi⊕h1αPIDi1∥Tcur∥PKTA∥∇. Therefore, according to the RID list, TA can trace back to the certain vehicle Vi, even revoke it. (RIDi,PIDi1)(2)
Message integrity and authentication: according to Definition3, the ECDLP problem is hard, so that no polynomial adversary can forge a valid message. Therefore, the verifier can verify the validity and integrity of the message Qi,PIDi,PKVi,mi,TS,σi by verifying whether the equation Si·P=riLi+PKVi+Qi+ni·PKKGC holds or not. Therefore, our proposed scheme for VANETs provides message authentication and integrity.(3)
Resistance to replay attacks: the proposed scheme can resist the replay attack for the reason that the tupleQi,PIDi,PKVi,mi,TS,σi includes the timestamp TS. RSU and other vehicles will check the validity of the signature, so they are able to detect the replay of the message. Hence, our proposed scheme for VANETs can resist replay attacks.(4)
Resistance to coalition attacks: our proposed scheme can resist the coalition attacks, because we improve the signature generation process. To be specific, we choose a random list to change the ratio in the equationS=∑i=1naiSi. Therefore, our scheme uses this method to resist the coalition attacks.(5)
Resistance to stealing of the check table: in the proposed scheme, TA, KGC, vehicles, and RSUs do not require a check list. Therefore, an attacker cannot complete an attack by stealing any checklist. Hence, the proposed scheme can resist the attack of the checklist.


## 6.2. Performance Analysis

In this section, we will discuss the performance of the proposed scheme and related schemes and make a comparison in detail. We adopt the method of computation evaluation where the bilinear pairing on the security level of 80 bits is created as follows:e¯:G1×G2→GT, where G1 is an additive group generated by a point P¯ with order q¯ on a super singular elliptic curve E¯:y2=x3+x mod p¯ with embedding degree 2, p¯ is a 512-bit prime number, q¯ is a 160-bit prime number [25]. The ECC on the security of 80 bits is constructed as follows: G is an additive group with order q that is generated on a nonsingular elliptic curve E:y2=x3+ax+b mod p, where p,q are 160-bit primes and a, b∈ℤq∗. The experiment is conducted using the well-known python cryptographic library PyCryptodome on a desktop running Intel I5-9400 @ 2.90 GHz processor, with 16 GB memory running Windows 10 operating system. The notations of the cryptographic operations used in this paper and their running times are given in Table 2. Table 3 shows the summary of the computation costs in terms of signing a message, verifying a single message, and verifying n messages.Table 2
Cryptographic operation notations and executing time.
OperationDescriptionTime (ms)TbpBilinear pairing operation4.1603Tbp−mScalar multiplication in bilinear pairing operation1.6722Tbp−aAddition in bilinear pairing operation0.0069Te−mScalar multiplication in ECC operation1.1280Te−aAddition in ECC operation0.0339ThOne-way hash function0.0360Table 3
Comparison of our proposed scheme with other related schemes.
SchemeIndividual signIndividual verifyAggregate verifyCoalition attacks resistanceWith pairingKamil et al. [6]3Te−m+2Te−a+3Th=3.5598ms2Te−m+Te−a+Th=2.6988ms2Te−m+nTe−a+nTh=0.0699n+2.2899msNoNoKumar et al. [12]4Te−m+2Te−a+3Th=4.6878ms4Te−m+3Te−a+4Th=4.7577ms4Te−m+3nTe−a+4nTh=0.2457n+4.512msNoYesYang et al. [13]4Tbp−m+2Tbp−a+3Th=6.9582ms3Tbp+3Tbp−m+Tbp−a+4Th=17.9111ms2nTbp+3nTbp−m+nTbp−a+4nTh=13.7001nmsYesYesCui et al. [17]Te−m+Te−a+Th=1.1979ms3Te−m+2Te−a+2Th=3.5238msn+2Te−m+n+2Te−a+2nTh=1.2339n+2.3238msNoNoZhao et al. [23]Te−m+2Th=1.2ms4Te−m+3Te−a+Th=4.6497msn+2Te−m+n+3Te−a+nTh=1.1979n+2.3577msNoNoMalhi et al. [24]4Tbp−m+2Tbp−a+Th=6.8862ms3Tbp+3Tbp−m+Tbp−a+2Th=17.8391ms3Tbp+3nTbp−m+nTbp−a+2nTh=5.2061n+12.633msNoYesOur schemeTe−m+Th=1.164ms2Te−m+3Te−a+3Th=3.5577msn+1Te−m+2Te−a+2nTh=1.2n+1.1958msYesNoIn [13, 24], their schemes choose to use bilinear pairing, which significantly increases their operation time. As a contrast, other four schemes [6, 12, 17, 23] do not use bilinear pairing, which can substantially reduce computation time.In our scheme,Li=li·P uses a scalar multiplication in ECC operation and the calculation of ri uses a one-way hash function during the individual sign process. In individual verification, we use three scalar multiplication operations for Si·P, ri·Li, and ni·PKKGC, three addition operations, and two one-way hash function operations for the calculations of ri and ni. In aggregate verification process, we use n+2 scalar multiplication operations for ∑i=1nairi·Li, S·P, and ∑i=1naini·PKKGC, two addition operations, and 2n one-way hash function operations for each ni and ri. By comprision, our scheme has low time complexity and high efficiency. In addition, our scheme can resist coalition attacks, which are a special and security feature that no other scheme has.We use the data in Table3 to generate three figures, which can intuitively compare other related schemes with our scheme. In Figures 4(a)–4(c), we can get the conclusion that our scheme has a considerably low delay in sign and verification procedure, which reveals that our scheme has a much higher efficiency.Figure 4
Time cost of different schemes in three cases.
(a)
Individual sign cost(b)
Individual verification cost(c)
Aggregate verification cost


## 7. Conclusion

Since real application scenarios of VANETs require high efficiency, an efficient certificateless-based anonymous authentication and aggregate signature scheme are proposed. The proposed CLS and its improved scheme CL-AS are appropriate for VANETs duo to analysis and testing. In addition, there is still some work to do in the future such as the low efficiency caused by the illegitimate signature in the aggregate verification process.



---

*Source: 6677137-2021-03-16.xml*