# A Privacy-Preserving Authentication Scheme for VANETs with Exculpability

Authors: Shangle Li; Ruili Yang; Jiageng Chen
Journal: Security and Communication Networks
 (2023)

---

## Abstract

Message authentication and conditional privacy preservation are two critical security issues in VANETs (vehicular ad hoc networks). To achieve the corresponding security goals, many security technologies have been proposed so far. Identity-based pseudonyms and group signature-based schemes are two of the main technologies in recently published literature. However, the key escrow is difficult to achieve and pseudonym identities may reveal the physical location of the vehicle in the identity-based scheme. The global manager TA of VANETs knows the full keys given to the vehicles and can forge signatures under the vehicle’s key. Therefore, the exculpability cannot be satisfied in the group signature scheme. To address these security issues, a privacy-preserving authentication scheme for VANETs with exculpability is proposed in this paper, which applies double key approach to realize the trusted communication between vehicle and road side units and TA by combining the advantage of group-based methods and identity-based methods. Security analysis shows that the security of our scheme can resist stronger attacks than previous schemes.


---

## Body

## 1. Introduction

The application of vehicular ad hoc networks (VANETs) has become a hot topic in the smart city [1]. A typical VANETs system consists of three parts: TA (trusted authority), RSUs (road-side units), and vehicles. The global manager TA of VANETs controls the system to ensure normal operation. The RSUs are distributed on the road and forward messages between vehicles and TA. The vehicles are equipped with OBU (on-board units).There are two types of communication in VANETs: V2V communication and V2I communication. The V2V communication has taken place between vehicles. The vehicle broadcasts messages to nearby vehicles. The communication between vehicles and RSUs is called V2I communication. However, according to DSRC protocol [2], various attacks exist in the wireless communication environment [1, 3]. Thus, it is very important to protect the privacy of the vehicles.To prevent message spoofing, all messages are signed by secret keys generated by a tamper-proof device (TPD) [4, 5], but the TPD is very expensive. Even worse, a signing key can be revoked if the TPD of a car is compromised. Nevertheless, many previous identity-based signature (IBS) schemes [5] for VANETs rely on the TPD to store the signing key.In many IBS schemes, the real identity of the vehicle is coded as the pseudo-ID (PID) to protect the privacy of the vehicle. But the real identity of the vehicle might be recovered from the PID [6]. In addition, attackers may track the PID of the vehicle directly without recovering the real identity of the vehicle. Even worse, many schemes do not update the key for a long time, and attackers locate the vehicle by continuously tracking the single public key or PID of a vehicle without decrypting the message.In many previous short group signature schemes [6, 7] for VANETs, the secret key of the vehicle used to sign messages cannot be hidden from the group managers, say TA, which has no exculpability property for the vehicle. The exculpability [8] asks that the key issuer cannot know the full secret key given to the vehicle and so cannot produce signatures under the vehicle’s key [9].The BV-CLRS scheme [10] proposed by Bouakkaza and Semchedineb is based on traceable certificate-less ring signature with exculpability. Exculpability means that no member in the group can forge the signatures of other members, even the administrator. Then, the computation and communication overhead are optimized in the CLA-TRS scheme [11]. In the earlier short group signature scheme [9], Dan Boneh proposed the idea of applying strong exculpability in VANETs.Due to the special topology of VANETs that vehicles are moving at high speed, and the network connection is frequently changing, vehicles broadcast message approximately every 100 milliseconds [10, 12]. Therefore, the length of signature should be under 250 bytes [9] for the efficiency purpose.In this paper, we propose and develop a privacy-preserving authentication scheme for VANETs. In our scheme, TA generates a partial key for the vehicle, as the key generation algorithm of short group signature [9] does using the vehicle’s public key. Therefore, the full signing key of the vehicle is no longer shared with TA so that the vehicle cannot deny the signature signed by itself with its signing key. The vehicle signs message with full signing key and broadcasts the signature to vehicles and RSUs nearby. The length of the signature which is signed by short group signature algorithm is not more than 250 bytes. More precisely, the PID of a vehicle is not included in the signature as the IBS scheme [5] did. The attacker cannot locate the vehicle by tracking the PID, and the PID is hidden in a private parameter saved by the TA. The RSU which is semitrusted forwards messages between TA and vehicles.In summary, this paper has four-fold main contributions:(i)
We propose a privacy-preserving authentication scheme for VANETs with exculpability. The advantage of our scheme is that the signature of the vehicle has strong exculpability. No vehicle can deny the signature signed by itself, and the TA cannot sign in place of the vehicle.(ii)
In our scheme, the vehicle has the full signing key and will update keys online by itself easily. The vehicle can automatically update the key online periodically without relying on the TA.(iii)
The signature of messages does not contain any information about the real identity of the vehicle, and the attackers cannot locate the vehicle by tracking the PID of the vehicle. No one can track the vehicle except the TA.(iv)
We analyze the security of the proposed scheme and compare the security strength of the related schemes which shows our advantage. Finally, The performance of each scheme is analyzed and compared theoretically and practically.The remainder of this paper is organized as follows. In Section2, we briefly reviewed the related works. The preparatory knowledge related to this paper is shown in Section 3. In Section 4, we presented the authentication scheme for VANETs and analyzed the security in Section 5. In Section 6, we analyzed the performance of the scheme and simulate the protocol. We summarized this paper in the last Section.


## 2. Related Work

In wireless communication of VANETs, there exists various kinds of attacks [3]. Message authentication and privacy preservation are two critical security issues in VANETs.Identity-based and group signature-based are two of the main technologies to realize the security requirements for VANETs. An identity-based conditional privacy-preserving authentication (CPPA) scheme was proposed by He et al. [5]. In CPPA scheme, the TA presets secret keys for vehicles and publishes the corresponding public keys. The tamper-proof device (TPD) of the vehicle generates the pseudonymous identity (PID) and session key for the vehicle. However, the PID of the vehicle is exposed to the wireless environment and may be tracked. In group signature-based schemes [6, 7, 13], the group manager issues the private key to the vehicle, and the vehicle signs the message with the private key. So the vehicles would deny the signature signed by themselves and strong exculpability cannot be satisfied.Key distribution and update for the vehicles are not efficient in some ID-based or group signature-based schemes. In CPPA scheme [5], the TA presets the secret key for the vehicles and the key cannot be updated online. Solutions [13, 14] tried to solve the problem of key allocation but the key update is not very efficient. The common feature is that the key of the vehicle fully depends on the administrator distribution.Bilinear-pairing is a common cryptography primitive used for message authentication in VANETs, but its computational complexity is relatively high. To encoded the real identity of a vehicle, two different pseudo-IDs are generated for the same session in the scheme proposed by Zhang et al. [15], but the scheme cannot defend the denial-of-service (DoS) attack. The implementation of the ID-based CPPA scheme [5] removes the bilinear-pairing, but the PID of the vehicle is exposed.In ID-based scheme, the TPD where the secret key of the vehicle is memorized is always used as a necessary module of the vehicle to protect the security of the secret key [4, 5, 15], but the device is not cheap. If the TPD is attacked, such as a side-channel attack, the forward security of the protocol will be threatened.Due to the special topology of VANETs, the protocols require minimizing the overhead of the message signature broadcasted by the vehicle. The pseudo-ID of the vehicle is used as a public key in reducing the size of the signature in an ID-based scheme [5]. Some group signature-based schemes [14] use the short group signatures of Dan et al. [9] to minimize the signature size.The BV-CLRS scheme [10] based on ring signature compresses the length of the signature to a certain extent. The scheme emphasizes the security of exculpability of the vehicle. Subsequently, Samra and Fouzi [11] further compressed the computation and communication overhead based on ring signatures.Batch verification technology is used to improve the efficiency of message verification in many schemes [5, 10, 11]. But if the batch verification of messages fails, it may cause more delay. So some group testing methods are proposed to detect the negative samples of the signatures.An ideal protocol for VANETs should preserve the privacy of the vehicle, prevent the tracking of the vehicle, authenticate the message of the sender, and so on. Unfortunately, the schemes discussed above lack one or more of the required features, which motivates our proposal.


## 3. Preliminaries

### 3.1. Bilinear Pairing

We first review the definition of bilinear maps [9].(i)
G0 and G1 are two cyclic groups of prime order p;(ii)
g0 and g1 are two generators of G0 and G1, respectively;(iii)
φ is a computable isomorphism from G1 to G0, as g0=φg1;(iv)
e is a computable map e:G0×G1⟶GT and satisfies the following properties:(i)
Bilinearity: for allu∈G0, v∈G1, and α,β∈Z, such that euα,vβ=eu,vαβ.(ii)
Nondegeneracy:eg0,g1≠1.In this paper, we considerG0=G1=G. To achieve the same level of security as a standard 1024-bit RSA signature [9], we used the fact that G can be of size 22-byte whose elements are 171-bit string, and the DL problem in G is as hard as the one in Zq∗, where q is 1020 bits in length. For convenience, we assumed that isomorphism φ exists and is computable efficiently.


### 3.2. A ZK Protocol for SDH

We follow the ZKPK protocol [9] and JOIN protocol [8] to present the underlying building block for our scheme.


#### 3.2.1. Key Generation

Given the public valuesg0,g1,u,v∈G and selected α,β∈Zp such that uα=vβ=h, where h∈G/1G. The pair α,β∈Zp is the tracing key.Select private keyγ∈Zp and set μ=g1γ. Select private keys x,y∈Zp, generate pair A,x,y for each user where A∈G, such that Aγ+x⋅hy=g0.The pairA,x,y satisfies eA,μg1x⋅eh,g1y=eg0,g1, and the pair x,y is a private key with two keys. Moreover, the partial key x is generated from a q+2-tuple g0,g1,g1γ,g1γ2,…,g1γq with private key γ under the SDH assumption, and output a pair g0/hy1/γ+x,x.


#### 3.2.2. Sign

The user signs messagem with private keys x,y and outputs signature σ.(1)σ⟵T1,T2,T3,c,sα,sβ,sx,sy,sδ1,sδ2.The private key of user is the exponentsx,y. The user randomly chooses a,b∈Zp and encrypts the message m∈G, and output T1,T2,T3=ua,vb,m⋅ha+b of signature σ. The Linear encryption T1,T2,T3 of A under public key u,v,h, and corresponds tracing key α,β. The message m can be derived from T1,T2,T3 by computing T3/T1a⋅T2b.(2)T1⟵ua,T2⟵vb,T3⟵Aha+b,δ1⟵xa,δ2⟵xb,R1⟵ura,R2⟵vrb,R3⟵eT3,g1rx⋅eh,μ−ra−rb⋅eh,g1−rδ1−rδ2⋅eh,g1ry,R4⟵T1rx⋅u−rδ1,R5⟵T2rx⋅v−rδ2,c⟵Hm,T1,T2,T3,R1,R2,R3,R4,R5,sa=ra+ca,sb=rb+cb,sx=rx+cx,sy=ry+cy,sδ1=rδ1+cδ1,sδ2=rδ2+cδ2,where ra,rb,rx,ry,rδ1,rδ2∈Zp.The advantage of an efficient algorithmA in deciding the DL (decision linear) problem [9] in G is shown in the following equation:(3)AdvAdl≔=PrAu,v,h,ua,vb,ha+b=true:u,v,h∈RG,a,b∈RZp−PrAu,v,h,ua,vb,η=true:u,v,η∈RG,a,b∈RZp.Definition 1.
The linear encryption (LE) scheme is semantically secure against a chosen-plaintext attack, assuming decision linear assumption holds inG if no t-time algorithm has advantage at least ε in solving the decision linear problem in G.Theorem 1.
The ZK protocol is CPA-fully-anonymous if linear encryption (LE) scheme is semantically secure onG.Theorem 2.
Assuming decision linear assumption holds inG, then the ZK protocol is fully-traceable.The ZK protocol is fully-anonymous and fully-traceable under the Theorems1 and 2.(i)
Fully-anonymous: the user’s private key is only known to herself, and no one, including the group manager, knows about it.(ii)
Fully-traceable: the group manager can recover the user identity information by using the tracing key.Definition 2.
Exculpability is informally defined as not a member of the group and not even the group manager given the tracing key can produce signatures on behalf of other users [9, 16].
The ZK protocol has the exculpability property. The signing keysx,y are generated by the manager and the user. But only the user knows the full keys x,y, the manager only knows the partial key x which is an exponent of the SDH tuple.


## 3.1. Bilinear Pairing

We first review the definition of bilinear maps [9].(i)
G0 and G1 are two cyclic groups of prime order p;(ii)
g0 and g1 are two generators of G0 and G1, respectively;(iii)
φ is a computable isomorphism from G1 to G0, as g0=φg1;(iv)
e is a computable map e:G0×G1⟶GT and satisfies the following properties:(i)
Bilinearity: for allu∈G0, v∈G1, and α,β∈Z, such that euα,vβ=eu,vαβ.(ii)
Nondegeneracy:eg0,g1≠1.In this paper, we considerG0=G1=G. To achieve the same level of security as a standard 1024-bit RSA signature [9], we used the fact that G can be of size 22-byte whose elements are 171-bit string, and the DL problem in G is as hard as the one in Zq∗, where q is 1020 bits in length. For convenience, we assumed that isomorphism φ exists and is computable efficiently.


## 3.2. A ZK Protocol for SDH

We follow the ZKPK protocol [9] and JOIN protocol [8] to present the underlying building block for our scheme.


### 3.2.1. Key Generation

Given the public valuesg0,g1,u,v∈G and selected α,β∈Zp such that uα=vβ=h, where h∈G/1G. The pair α,β∈Zp is the tracing key.Select private keyγ∈Zp and set μ=g1γ. Select private keys x,y∈Zp, generate pair A,x,y for each user where A∈G, such that Aγ+x⋅hy=g0.The pairA,x,y satisfies eA,μg1x⋅eh,g1y=eg0,g1, and the pair x,y is a private key with two keys. Moreover, the partial key x is generated from a q+2-tuple g0,g1,g1γ,g1γ2,…,g1γq with private key γ under the SDH assumption, and output a pair g0/hy1/γ+x,x.


### 3.2.2. Sign

The user signs messagem with private keys x,y and outputs signature σ.(1)σ⟵T1,T2,T3,c,sα,sβ,sx,sy,sδ1,sδ2.The private key of user is the exponentsx,y. The user randomly chooses a,b∈Zp and encrypts the message m∈G, and output T1,T2,T3=ua,vb,m⋅ha+b of signature σ. The Linear encryption T1,T2,T3 of A under public key u,v,h, and corresponds tracing key α,β. The message m can be derived from T1,T2,T3 by computing T3/T1a⋅T2b.(2)T1⟵ua,T2⟵vb,T3⟵Aha+b,δ1⟵xa,δ2⟵xb,R1⟵ura,R2⟵vrb,R3⟵eT3,g1rx⋅eh,μ−ra−rb⋅eh,g1−rδ1−rδ2⋅eh,g1ry,R4⟵T1rx⋅u−rδ1,R5⟵T2rx⋅v−rδ2,c⟵Hm,T1,T2,T3,R1,R2,R3,R4,R5,sa=ra+ca,sb=rb+cb,sx=rx+cx,sy=ry+cy,sδ1=rδ1+cδ1,sδ2=rδ2+cδ2,where ra,rb,rx,ry,rδ1,rδ2∈Zp.The advantage of an efficient algorithmA in deciding the DL (decision linear) problem [9] in G is shown in the following equation:(3)AdvAdl≔=PrAu,v,h,ua,vb,ha+b=true:u,v,h∈RG,a,b∈RZp−PrAu,v,h,ua,vb,η=true:u,v,η∈RG,a,b∈RZp.Definition 1.
The linear encryption (LE) scheme is semantically secure against a chosen-plaintext attack, assuming decision linear assumption holds inG if no t-time algorithm has advantage at least ε in solving the decision linear problem in G.Theorem 1.
The ZK protocol is CPA-fully-anonymous if linear encryption (LE) scheme is semantically secure onG.Theorem 2.
Assuming decision linear assumption holds inG, then the ZK protocol is fully-traceable.The ZK protocol is fully-anonymous and fully-traceable under the Theorems1 and 2.(i)
Fully-anonymous: the user’s private key is only known to herself, and no one, including the group manager, knows about it.(ii)
Fully-traceable: the group manager can recover the user identity information by using the tracing key.Definition 2.
Exculpability is informally defined as not a member of the group and not even the group manager given the tracing key can produce signatures on behalf of other users [9, 16].
The ZK protocol has the exculpability property. The signing keysx,y are generated by the manager and the user. But only the user knows the full keys x,y, the manager only knows the partial key x which is an exponent of the SDH tuple.


## 3.2.1. Key Generation

Given the public valuesg0,g1,u,v∈G and selected α,β∈Zp such that uα=vβ=h, where h∈G/1G. The pair α,β∈Zp is the tracing key.Select private keyγ∈Zp and set μ=g1γ. Select private keys x,y∈Zp, generate pair A,x,y for each user where A∈G, such that Aγ+x⋅hy=g0.The pairA,x,y satisfies eA,μg1x⋅eh,g1y=eg0,g1, and the pair x,y is a private key with two keys. Moreover, the partial key x is generated from a q+2-tuple g0,g1,g1γ,g1γ2,…,g1γq with private key γ under the SDH assumption, and output a pair g0/hy1/γ+x,x.


## 3.2.2. Sign

The user signs messagem with private keys x,y and outputs signature σ.(1)σ⟵T1,T2,T3,c,sα,sβ,sx,sy,sδ1,sδ2.The private key of user is the exponentsx,y. The user randomly chooses a,b∈Zp and encrypts the message m∈G, and output T1,T2,T3=ua,vb,m⋅ha+b of signature σ. The Linear encryption T1,T2,T3 of A under public key u,v,h, and corresponds tracing key α,β. The message m can be derived from T1,T2,T3 by computing T3/T1a⋅T2b.(2)T1⟵ua,T2⟵vb,T3⟵Aha+b,δ1⟵xa,δ2⟵xb,R1⟵ura,R2⟵vrb,R3⟵eT3,g1rx⋅eh,μ−ra−rb⋅eh,g1−rδ1−rδ2⋅eh,g1ry,R4⟵T1rx⋅u−rδ1,R5⟵T2rx⋅v−rδ2,c⟵Hm,T1,T2,T3,R1,R2,R3,R4,R5,sa=ra+ca,sb=rb+cb,sx=rx+cx,sy=ry+cy,sδ1=rδ1+cδ1,sδ2=rδ2+cδ2,where ra,rb,rx,ry,rδ1,rδ2∈Zp.The advantage of an efficient algorithmA in deciding the DL (decision linear) problem [9] in G is shown in the following equation:(3)AdvAdl≔=PrAu,v,h,ua,vb,ha+b=true:u,v,h∈RG,a,b∈RZp−PrAu,v,h,ua,vb,η=true:u,v,η∈RG,a,b∈RZp.Definition 1.
The linear encryption (LE) scheme is semantically secure against a chosen-plaintext attack, assuming decision linear assumption holds inG if no t-time algorithm has advantage at least ε in solving the decision linear problem in G.Theorem 1.
The ZK protocol is CPA-fully-anonymous if linear encryption (LE) scheme is semantically secure onG.Theorem 2.
Assuming decision linear assumption holds inG, then the ZK protocol is fully-traceable.The ZK protocol is fully-anonymous and fully-traceable under the Theorems1 and 2.(i)
Fully-anonymous: the user’s private key is only known to herself, and no one, including the group manager, knows about it.(ii)
Fully-traceable: the group manager can recover the user identity information by using the tracing key.Definition 2.
Exculpability is informally defined as not a member of the group and not even the group manager given the tracing key can produce signatures on behalf of other users [9, 16].
The ZK protocol has the exculpability property. The signing keysx,y are generated by the manager and the user. But only the user knows the full keys x,y, the manager only knows the partial key x which is an exponent of the SDH tuple.


## 4. The System Model

In this section, we propose our privacy-preserving authentication scheme for VATENs. We define the notations used as shown in Table1.Table 1
The notations of the execution time of cryptography operations.
NotationsDescriptionGTwo cyclic groupsG0=G1 of prime order p, denoted as Gg0,g1Two generators ofGu,v,hThree generators ofGγThe private key of the TAα,βTwo integers ofZp∗HA hash function:0,1∗⟶ZpyiThe partial private key of vehicleVi generated by VixiThe partial private key of vehicleVi generated by TAPKiThe public key of vehicleViskiThe full-private key of vehicleViσThe signature of messageMAiThe private value of vehicle which is bound to the real identity


### 4.1. Architecture

In our scheme, the architecture (as illustrated in Figure1) consists of three entities: fully trusted TA, RSU, and vehicles.Figure 1
System model.TA interacts with RSUs directly. But the interaction between the TA and vehicles is through RSUs.The RSU periodically broadcasts public values to vehicles.V2V communication: the vehicle broadcasts message to vehicles nearby. V2I communication: the vehicle broadcasts message to RSU nearby.


#### 4.1.1. TA

The TA (trusted authority) is the global manager of the system and is fully trusted. The TA initiates and generates system parameters. The RSUs and vehicles will register at TA and are given certificates and public keys. The TA interacts with RSUs directly, and the interaction with vehicles through RSUs. The TA is also responsible for the revocation of malicious vehicles.


#### 4.1.2. RSU

The RSUs (road-side units) are roadside infrastructures distributed evenly on both sides of the road and considered untrusted which are vulnerable to geographic attacks. RSUs interact directly with the TA and are in charge of monitoring vehicles for suspicious activity and reporting back to it and forward messages between the TA and vehicles. The RSU periodically broadcasts public values to vehicles in its radiation region. The communication between RSUs and vehicles is called V2I communication. The TA will broadcast revocation list to RSUs to revoke the malicious vehicle from the system.


#### 4.1.3. Vehicle

The vehicles are instances of on-board units (OBUs) moving on the road. The vehicles will broadcast useful messages (speed, traffic accident, etc.) to nearby vehicles and RSUs. The communication between vehicle to vehicles is called V2V communication. The vehicles are vulnerable entities in the system. Therefore, the privacy of vehicles must be protected.


### 4.2. Security Requirements

The survey of Sheikh et al. [3] lists various attacks in VANETs. According to the specifications of DSRC protocol [2] and VANET security services in traffic management system [1], various security requirements should be considered.(i)
Authentication: To ensure the security of the system, the identity of vehicles must be authenticated. The message receiver can detect invalid messages from suspicious vehicles. The TA is able to reveal malicious vehicles, and RSUs can execute the order from the TA to remove the bad ones from the group.(ii)
Privacy: The identities and locations of the vehicles are sensitive information for users that may reveal the habits of drivers. The message receivers (say, RSUs and vehicles) should not know the sensitive information. The other parties should not be able to derive private messages from transcripts between V2V communication and V2I communication. TA can extract the privacy information from vehicles.(iii)
Tracing: In order to prevent malicious vehicles from releasing false information to evade responsibility, TA has the right to track vehicles. The TA extracts the vehicle’s real identity by deciphering the messages when it is necessary. As for other entities, they have no ability to achieve it.(iv)
Unlikability: RSUs and malicious vehicles cannot link two messages from the same vehicle. For example, RSUs cannot identify if two signatures are from the same vehicle or not.While achieving the above security properties, our scheme can provide a stronger security requirement, namely, the exculpability property. As introduced by Ateniese and Tsudik [16] and Bellare et al. [17], no member of the group and not even the group manager can produce signatures on behalf of other users. As stronger exculpability requires that even the entity that issues user keys cannot forge signatures on behalf of users [18]. The security requirements listed below are satisfied if the security of exculpability is applied.(i)
The vehicle cannot deny the signature signed by itself, because only the vehicle has a complete private key. The attacker cannot generate a valid signature.(ii)
No one in the group can forge member signatures, including the group administrator, let alone the adversary. The TA or the attacker can ask the private key of the vehicle, but cannot generate a valid signature.(iii)
The vehicle can periodically update the session key online. Except for the TA, no one can get the sensitive information of the vehicle through the communication transcript. The private key update of the vehicle does not need to rely on TA. During the key update process, the attacker cannot forge the private key of the vehicle.(iv)
Except for the TA, no one can associate the PID and position information of the vehicle to locate the vehicle. The PID of the vehicle will be completely hidden. The attacker can intercept all communication transcript, but cannot analyze the vehicle’s action trajectory through the PID.(v)
Even if the RSU is coerced, it will not threaten the privacy and safety of the vehicle. The private key used for signing is generated by the vehicle itself and can be updated at any time. An attacker can hijack the RSU, but the privacy of the vehicle will not be compromised.


### 4.3. Algorithms

In this paper, the privacy-preserving authentication scheme for VANETs proposed by us include five algorithms: initiation, registration, signing, verification, and update algorithm. The detailed description of the algorithm is as follows:


#### 4.3.1. Initiation

TA selects generatorsu,v,h and g0,g1 from cyclic group G, picks system private key γ and tracing key α,β∈RZp∗, computes μ=g1γ, and then employs secure hash function H. TA publishes the public parameters g0,g1,u,v,μ,h,H.


#### 4.3.2. Registration

The vehicleVi selects a partial private key yi, computes PKi=hyi, and sends PKi to TA, which generates and sends back a secret key xi and private value Ai. The Vi gets secret key ski:=xi,yi and private value Ai.


#### 4.3.3. Signing

Given public keyg0,g1,u,v,μ,h, secret key xi,yi, Ai, and a message M, compute and output a signature(4)σ⟵T1,T2,T3,T4,c,sα,sβ,sx,sy,sδ1,sδ2,where c is a challenger value.


#### 4.3.4. Verification

The receiver verifies the validity of the signature and verifies the revocation of revoked vehicle. Given signatureσ and public key g0,g1,u,v,μ,h to compute R˜1,R˜2,R˜3,R˜4,R˜5,R˜6, and then check the following relation:(5)c=?HM,T1,T2,T3,T4,R˜1,R˜2,R˜3,R˜4,R˜5,R˜6,where c is a challenge value generated by the signer. If the signature is valid, then verify whether A is encoded in T3,T4 by testing eT3/A,u=?eT4,h, where A∈RL=A1∗,…,An∗,. If no element A of RL is encoded in T3,T4, the signer of σ has not been revoked.


#### 4.3.5. Tracing

Using the tracing keyα,β and T1,T2,T3 which is in the signature σ, the TA can reveal the signer’s identity by computing Ai.


#### 4.3.6. Update

Given new public keyPK^i to TA, TA returns A^i∗,x^i, the vehicle updates public key g0,g1,u,v,μ,h to the new public key g^0,g^1,u,v,μ^,h, update secret key xi,yi to x^i,y^i, and Ai update to A^i∗. The TA broadcasts the new public key g^0,g^1,u,v,μ^,h.


### 4.4. System Construction

In this subsection, we provide detailed description of the process of our scheme as follows:


#### 4.4.1. System Initialization

In this phase, TA initiates the system. TA picks the private keyγ which is selected randomly from Zp∗, and then computes μ=g1γ, where g1 is a generator of multiplicative cyclic group G. TA selects h∈RG/1G and α,β∈RZp∗, and sets u,v,h∈G such that uα=vβ=h, where u,v are generators of multiplicative cyclic group G, and α,β is a tracing key. TA employs a secure hash function H:0,1∗⟶Zp which is used as a random oracle in the proof of security. TA publishes the public parameters g0,g1,u,v,μ,h,H.


#### 4.4.2. The Registration of Vehicles

In this phase, the vehicle registers at TA through secure channel. The vehicleVi selects yi∈RZp∗ as a partial private key and computes PKi=hyi∈G and sends PKi to the TA. The TA generates and sends back a SDH tuple Ai,xi by picking xi∈RZp∗ and setting Ai⟵g0/PKi1/γ+xi, where Ai regards as pseudo-ID of the vehicle Vi. In addition, the value Ai is bound to the real identity of the vehicle Vi, and Ai can be derived by the TA. The secret key of vehicle Vi is ski:=xi,yi.The public keyPKi of vehicle is used to register to TA. The private key ski consists of two partial keys xi and yi. The partial key yi is generated by the vehicle and updated periodically or deliberately. The partial key xi is generated by TA under the public key pki corresponding to yi. Both private keys xi and yi are used for the signature.The vehicleVi will get secret key ski:=xi,yi and private value Ai after this phase.


#### 4.4.3. Message Signing

In this phase, the vehicle signs messages before broadcasting them. Given public keyg0,g1,u,v,μ,h, secret key xi,yi, Ai, and a message M∈0,1∗, the vehicle computes and outputs a signature σ as follows:(6)σ⟵T1,T2,T3,T4,c,sα,sβ,sx,sy,sδ1,sδ2.(i)
Select randomnessa,b∈RZp as session keys and compute T1⟵ua,T2⟵vb,T3⟵Aiha+b,T4⟵ua+b and δ1⟵xia,δ2⟵xib.(ii)
Pick random valuesrα,rβ,rx,ry,rδ1,rδ2∈RZp∗, and then compute R1,R2,R3,R4,R5,R6 as follows:(7)R1⟵urα,R2⟵vrβ,R3⟵eT3,g1rx⋅eh,μ−rα−rβ⋅eh,g1−rδ1−rδ2⋅eh,g1ry,R4⟵T1rx⋅u−rδ1,R5⟵T2rx⋅v−rδ2,R6⟵T4rxu−rδ1−rδ2.(iii)
Compute challenge value as follows:(8)c⟵HM,T1,T2,T3,T4,R1,R2,R3,R4,R5,R6.(iv)
Compute helper valuessα,sβ,sx,sy,sδ1,sδ2 as follows:(9)sα=rα+ca,sβ=rβ+cb,sx=rx+cxi,sy=ry+cyisδ1=rδ1+cδ1,sδ2=rδ2+cδ2.(v)
Broadcast signatureσ.Note that,G is of size 22-byte and elements in G are 171-bit strings and p is a 170-bit prime. The signature of our scheme is formed as follows:(10)T1,T2,T3,T4,c,sα,sβ,sx,sy,sδ1,sδ2,where c,sα,sβ,sx,sy,sδ1,sδ2∈Zp and T1,T2,T3,T4∈G. So, the total length of the signature is 171×4+170×7=1874 bits = 235 bytes.


#### 4.4.4. Message Verification

In this phase, the receiver verifies the validity of the signature from the vehicles as well as the revocation status of the revoked vehicle.(i)
Signature verification: given signatureσ and public key g0,g1,u,v,μ,h to compute R˜1,R˜2,R˜3,R˜4,R˜5,R˜6 as follows:(11)R˜1⟵usαT1−c,R˜2⟵vsβT2−c,R˜3⟵eT3,g1sx⋅eh,μ−sα−sβ⋅eh,g1−sδ1−sδ2⋅eh,g1syeT3,μeg0,g1c,R˜4⟵T1sxu−sδ1,R˜5⟵T2sxv−sδ2,R˜6⟵T4sxu−sδ1−sδ2.The receiver checks the challenge valuec by testing as follows:(12)c=?HM,T1,T2,T3,T4,R˜1,R˜2,R˜3,R˜4,R˜5,R˜6.The receiver will proceed if the relation holds. Otherwise, she will report the suspicious vehicle to TA.(13)eT3,g1sx⋅eh,μ−sα−sβ⋅eh,g1−sδ1−sδ2⋅eh,g1sy=eT3,g1rx+cxi⋅eh,μ−rα−ca−rβ−cb⋅eh,g1−rδ1−cδ1−rδ2−cδ2⋅eh,g1ry+cyi=eT3,g1xic⋅eT3,g1rx⋅eh−a−b,μc⋅eh,μ−rα−rβ⋅eh,g1−rδ1−rδ2⋅eh−a−b,g1xic⋅eh,g1ry⋅eh,g1yic=eT3,g1xic⋅eh−a−b,μc⋅eh−a−b,g1xic⋅eh,g1yic⋅R3=eT3h−a−b,μg1xic⋅eT3,μ−c⋅eh,g1yic⋅R3=eAi,μg1xi⋅eh,g1yi/eT3,μc⋅R3=eg0,g1/eT3,μc⋅R3.The calculation process ofR˜3 of the equation (11) is shown in equation (13), where T3=Aiha+b and Ai⟵g0/hyi1/γ+xi, μ=g1γ, and the expression is valid(14)eAi,μg1xi⋅eh,g1yi=eg0,g1.The calculation process ofR˜6 of the equation (11) is shown in the following equation:(15)T4sxu−sδ1−sδ2=ua+brx+cxiu−rδ1+cδ1−rδ2+cδ2,=ua+brx+cxiu−rδ1+caxi−rδ2+cbxi,=ua+brxu−rδ1−rδ2,=R6.The verification process ofR˜1,R˜2,R˜4,R˜5 is similar to R˜6 and we omit it here.(ii)
Revocation verification: We refer to the VLR (verifier-local revocation) mechanism proposed by Boneh and Shacham [19]. Suppose revocation list (RL) contains the private value of all revoked vehicles. More precisely,(16)RL=A1∗,…,An∗,.whereAi∗ is traced by TA. For each element A∈RL, check whether A is encoded in T3,T4 by testing if(17)eT3/A,u=?eT4,h.If no elementA of RL is encoded in T3,T4, then the signer has not been revoked. Otherwise, some Ai∗=A indicates that the vehicle Vi has been revoked.The signatureσ is valid if it passes both verifications.


#### 4.4.5. Vehicles Tracing

In this phase, TA has the ability to trace the signer of the messages. Using the tracing key and valuesT1,T2,T3 in the signature σ, TA can reveal the signer’s identity which is related to Ai by computing Ai⟵T3/T1α⋅T2β. To hide the identity of the vehicle, the parameter Ai related to the real identity of a vehicle is a private value saved by TA.Since the TA holds tracing keyα,β, uα=vβ=h, and T1⟵ua,T2⟵vb,T3⟵Aiha+b, then(18)T3T1α⋅T2β=Aiha+buaα⋅vbβ,=Aiha+bha⋅hb,=Ai.TheAi is derived from T1,T2,T3 with tracing key α,β.


#### 4.4.6. Key Update

In this phase, the vehicles can update their secret keys online by themselves. For example, the vehicleVi sends the new public key PK^i through some authenticated channel, where PK^i=hy^i. TA will compute new SDH pair A^i∗,x^i, and then send back A^i∗,x^i, where A^i∗=g1/PK^i1/γ+x^i. The vehicle will update its public key and secret key as follows.Note thatg0=φg1 and Ai=φA^i∗. Given public key PK^i, TA will use private key γ to compute the A^i∗ and send back A^i,x^i. The vehicle with old public key g0,g1,u,v,μ,h and secret key x^i,y^i construct new public key g^0,g^1,u,v,μ^,h, where g^0=g01/γ+x^i, g^1=g1/PK^i1/γ+x^i, μ^=g^1γ, and g0,g1∈G. More precisely,(19)g^0⟵φA^i∗=g01/γ+x^i,g^1⟵A^i∗=g1PK^i1/γ+x^i,μ^⟵g1PK^i⋅A^i∗−x^i=g1PK^i1−x^i/γ+x^i,=A^i∗γ,=g^1γ.Hence, the new secret key of the vehicle isx^i,y^i, and Ai updates to A^i∗. The new public key g^0,g^1,u,v,μ^,h is broadcast by TA.


## 4.1. Architecture

In our scheme, the architecture (as illustrated in Figure1) consists of three entities: fully trusted TA, RSU, and vehicles.Figure 1
System model.TA interacts with RSUs directly. But the interaction between the TA and vehicles is through RSUs.The RSU periodically broadcasts public values to vehicles.V2V communication: the vehicle broadcasts message to vehicles nearby. V2I communication: the vehicle broadcasts message to RSU nearby.


### 4.1.1. TA

The TA (trusted authority) is the global manager of the system and is fully trusted. The TA initiates and generates system parameters. The RSUs and vehicles will register at TA and are given certificates and public keys. The TA interacts with RSUs directly, and the interaction with vehicles through RSUs. The TA is also responsible for the revocation of malicious vehicles.


### 4.1.2. RSU

The RSUs (road-side units) are roadside infrastructures distributed evenly on both sides of the road and considered untrusted which are vulnerable to geographic attacks. RSUs interact directly with the TA and are in charge of monitoring vehicles for suspicious activity and reporting back to it and forward messages between the TA and vehicles. The RSU periodically broadcasts public values to vehicles in its radiation region. The communication between RSUs and vehicles is called V2I communication. The TA will broadcast revocation list to RSUs to revoke the malicious vehicle from the system.


### 4.1.3. Vehicle

The vehicles are instances of on-board units (OBUs) moving on the road. The vehicles will broadcast useful messages (speed, traffic accident, etc.) to nearby vehicles and RSUs. The communication between vehicle to vehicles is called V2V communication. The vehicles are vulnerable entities in the system. Therefore, the privacy of vehicles must be protected.


## 4.1.1. TA

The TA (trusted authority) is the global manager of the system and is fully trusted. The TA initiates and generates system parameters. The RSUs and vehicles will register at TA and are given certificates and public keys. The TA interacts with RSUs directly, and the interaction with vehicles through RSUs. The TA is also responsible for the revocation of malicious vehicles.


## 4.1.2. RSU

The RSUs (road-side units) are roadside infrastructures distributed evenly on both sides of the road and considered untrusted which are vulnerable to geographic attacks. RSUs interact directly with the TA and are in charge of monitoring vehicles for suspicious activity and reporting back to it and forward messages between the TA and vehicles. The RSU periodically broadcasts public values to vehicles in its radiation region. The communication between RSUs and vehicles is called V2I communication. The TA will broadcast revocation list to RSUs to revoke the malicious vehicle from the system.


## 4.1.3. Vehicle

The vehicles are instances of on-board units (OBUs) moving on the road. The vehicles will broadcast useful messages (speed, traffic accident, etc.) to nearby vehicles and RSUs. The communication between vehicle to vehicles is called V2V communication. The vehicles are vulnerable entities in the system. Therefore, the privacy of vehicles must be protected.


## 4.2. Security Requirements

The survey of Sheikh et al. [3] lists various attacks in VANETs. According to the specifications of DSRC protocol [2] and VANET security services in traffic management system [1], various security requirements should be considered.(i)
Authentication: To ensure the security of the system, the identity of vehicles must be authenticated. The message receiver can detect invalid messages from suspicious vehicles. The TA is able to reveal malicious vehicles, and RSUs can execute the order from the TA to remove the bad ones from the group.(ii)
Privacy: The identities and locations of the vehicles are sensitive information for users that may reveal the habits of drivers. The message receivers (say, RSUs and vehicles) should not know the sensitive information. The other parties should not be able to derive private messages from transcripts between V2V communication and V2I communication. TA can extract the privacy information from vehicles.(iii)
Tracing: In order to prevent malicious vehicles from releasing false information to evade responsibility, TA has the right to track vehicles. The TA extracts the vehicle’s real identity by deciphering the messages when it is necessary. As for other entities, they have no ability to achieve it.(iv)
Unlikability: RSUs and malicious vehicles cannot link two messages from the same vehicle. For example, RSUs cannot identify if two signatures are from the same vehicle or not.While achieving the above security properties, our scheme can provide a stronger security requirement, namely, the exculpability property. As introduced by Ateniese and Tsudik [16] and Bellare et al. [17], no member of the group and not even the group manager can produce signatures on behalf of other users. As stronger exculpability requires that even the entity that issues user keys cannot forge signatures on behalf of users [18]. The security requirements listed below are satisfied if the security of exculpability is applied.(i)
The vehicle cannot deny the signature signed by itself, because only the vehicle has a complete private key. The attacker cannot generate a valid signature.(ii)
No one in the group can forge member signatures, including the group administrator, let alone the adversary. The TA or the attacker can ask the private key of the vehicle, but cannot generate a valid signature.(iii)
The vehicle can periodically update the session key online. Except for the TA, no one can get the sensitive information of the vehicle through the communication transcript. The private key update of the vehicle does not need to rely on TA. During the key update process, the attacker cannot forge the private key of the vehicle.(iv)
Except for the TA, no one can associate the PID and position information of the vehicle to locate the vehicle. The PID of the vehicle will be completely hidden. The attacker can intercept all communication transcript, but cannot analyze the vehicle’s action trajectory through the PID.(v)
Even if the RSU is coerced, it will not threaten the privacy and safety of the vehicle. The private key used for signing is generated by the vehicle itself and can be updated at any time. An attacker can hijack the RSU, but the privacy of the vehicle will not be compromised.


## 4.3. Algorithms

In this paper, the privacy-preserving authentication scheme for VANETs proposed by us include five algorithms: initiation, registration, signing, verification, and update algorithm. The detailed description of the algorithm is as follows:


### 4.3.1. Initiation

TA selects generatorsu,v,h and g0,g1 from cyclic group G, picks system private key γ and tracing key α,β∈RZp∗, computes μ=g1γ, and then employs secure hash function H. TA publishes the public parameters g0,g1,u,v,μ,h,H.


### 4.3.2. Registration

The vehicleVi selects a partial private key yi, computes PKi=hyi, and sends PKi to TA, which generates and sends back a secret key xi and private value Ai. The Vi gets secret key ski:=xi,yi and private value Ai.


### 4.3.3. Signing

Given public keyg0,g1,u,v,μ,h, secret key xi,yi, Ai, and a message M, compute and output a signature(4)σ⟵T1,T2,T3,T4,c,sα,sβ,sx,sy,sδ1,sδ2,where c is a challenger value.


### 4.3.4. Verification

The receiver verifies the validity of the signature and verifies the revocation of revoked vehicle. Given signatureσ and public key g0,g1,u,v,μ,h to compute R˜1,R˜2,R˜3,R˜4,R˜5,R˜6, and then check the following relation:(5)c=?HM,T1,T2,T3,T4,R˜1,R˜2,R˜3,R˜4,R˜5,R˜6,where c is a challenge value generated by the signer. If the signature is valid, then verify whether A is encoded in T3,T4 by testing eT3/A,u=?eT4,h, where A∈RL=A1∗,…,An∗,. If no element A of RL is encoded in T3,T4, the signer of σ has not been revoked.


### 4.3.5. Tracing

Using the tracing keyα,β and T1,T2,T3 which is in the signature σ, the TA can reveal the signer’s identity by computing Ai.


### 4.3.6. Update

Given new public keyPK^i to TA, TA returns A^i∗,x^i, the vehicle updates public key g0,g1,u,v,μ,h to the new public key g^0,g^1,u,v,μ^,h, update secret key xi,yi to x^i,y^i, and Ai update to A^i∗. The TA broadcasts the new public key g^0,g^1,u,v,μ^,h.


## 4.3.1. Initiation

TA selects generatorsu,v,h and g0,g1 from cyclic group G, picks system private key γ and tracing key α,β∈RZp∗, computes μ=g1γ, and then employs secure hash function H. TA publishes the public parameters g0,g1,u,v,μ,h,H.


## 4.3.2. Registration

The vehicleVi selects a partial private key yi, computes PKi=hyi, and sends PKi to TA, which generates and sends back a secret key xi and private value Ai. The Vi gets secret key ski:=xi,yi and private value Ai.


## 4.3.3. Signing

Given public keyg0,g1,u,v,μ,h, secret key xi,yi, Ai, and a message M, compute and output a signature(4)σ⟵T1,T2,T3,T4,c,sα,sβ,sx,sy,sδ1,sδ2,where c is a challenger value.


## 4.3.4. Verification

The receiver verifies the validity of the signature and verifies the revocation of revoked vehicle. Given signatureσ and public key g0,g1,u,v,μ,h to compute R˜1,R˜2,R˜3,R˜4,R˜5,R˜6, and then check the following relation:(5)c=?HM,T1,T2,T3,T4,R˜1,R˜2,R˜3,R˜4,R˜5,R˜6,where c is a challenge value generated by the signer. If the signature is valid, then verify whether A is encoded in T3,T4 by testing eT3/A,u=?eT4,h, where A∈RL=A1∗,…,An∗,. If no element A of RL is encoded in T3,T4, the signer of σ has not been revoked.


## 4.3.5. Tracing

Using the tracing keyα,β and T1,T2,T3 which is in the signature σ, the TA can reveal the signer’s identity by computing Ai.


## 4.3.6. Update

Given new public keyPK^i to TA, TA returns A^i∗,x^i, the vehicle updates public key g0,g1,u,v,μ,h to the new public key g^0,g^1,u,v,μ^,h, update secret key xi,yi to x^i,y^i, and Ai update to A^i∗. The TA broadcasts the new public key g^0,g^1,u,v,μ^,h.


## 4.4. System Construction

In this subsection, we provide detailed description of the process of our scheme as follows:


### 4.4.1. System Initialization

In this phase, TA initiates the system. TA picks the private keyγ which is selected randomly from Zp∗, and then computes μ=g1γ, where g1 is a generator of multiplicative cyclic group G. TA selects h∈RG/1G and α,β∈RZp∗, and sets u,v,h∈G such that uα=vβ=h, where u,v are generators of multiplicative cyclic group G, and α,β is a tracing key. TA employs a secure hash function H:0,1∗⟶Zp which is used as a random oracle in the proof of security. TA publishes the public parameters g0,g1,u,v,μ,h,H.


### 4.4.2. The Registration of Vehicles

In this phase, the vehicle registers at TA through secure channel. The vehicleVi selects yi∈RZp∗ as a partial private key and computes PKi=hyi∈G and sends PKi to the TA. The TA generates and sends back a SDH tuple Ai,xi by picking xi∈RZp∗ and setting Ai⟵g0/PKi1/γ+xi, where Ai regards as pseudo-ID of the vehicle Vi. In addition, the value Ai is bound to the real identity of the vehicle Vi, and Ai can be derived by the TA. The secret key of vehicle Vi is ski:=xi,yi.The public keyPKi of vehicle is used to register to TA. The private key ski consists of two partial keys xi and yi. The partial key yi is generated by the vehicle and updated periodically or deliberately. The partial key xi is generated by TA under the public key pki corresponding to yi. Both private keys xi and yi are used for the signature.The vehicleVi will get secret key ski:=xi,yi and private value Ai after this phase.


### 4.4.3. Message Signing

In this phase, the vehicle signs messages before broadcasting them. Given public keyg0,g1,u,v,μ,h, secret key xi,yi, Ai, and a message M∈0,1∗, the vehicle computes and outputs a signature σ as follows:(6)σ⟵T1,T2,T3,T4,c,sα,sβ,sx,sy,sδ1,sδ2.(i)
Select randomnessa,b∈RZp as session keys and compute T1⟵ua,T2⟵vb,T3⟵Aiha+b,T4⟵ua+b and δ1⟵xia,δ2⟵xib.(ii)
Pick random valuesrα,rβ,rx,ry,rδ1,rδ2∈RZp∗, and then compute R1,R2,R3,R4,R5,R6 as follows:(7)R1⟵urα,R2⟵vrβ,R3⟵eT3,g1rx⋅eh,μ−rα−rβ⋅eh,g1−rδ1−rδ2⋅eh,g1ry,R4⟵T1rx⋅u−rδ1,R5⟵T2rx⋅v−rδ2,R6⟵T4rxu−rδ1−rδ2.(iii)
Compute challenge value as follows:(8)c⟵HM,T1,T2,T3,T4,R1,R2,R3,R4,R5,R6.(iv)
Compute helper valuessα,sβ,sx,sy,sδ1,sδ2 as follows:(9)sα=rα+ca,sβ=rβ+cb,sx=rx+cxi,sy=ry+cyisδ1=rδ1+cδ1,sδ2=rδ2+cδ2.(v)
Broadcast signatureσ.Note that,G is of size 22-byte and elements in G are 171-bit strings and p is a 170-bit prime. The signature of our scheme is formed as follows:(10)T1,T2,T3,T4,c,sα,sβ,sx,sy,sδ1,sδ2,where c,sα,sβ,sx,sy,sδ1,sδ2∈Zp and T1,T2,T3,T4∈G. So, the total length of the signature is 171×4+170×7=1874 bits = 235 bytes.


### 4.4.4. Message Verification

In this phase, the receiver verifies the validity of the signature from the vehicles as well as the revocation status of the revoked vehicle.(i)
Signature verification: given signatureσ and public key g0,g1,u,v,μ,h to compute R˜1,R˜2,R˜3,R˜4,R˜5,R˜6 as follows:(11)R˜1⟵usαT1−c,R˜2⟵vsβT2−c,R˜3⟵eT3,g1sx⋅eh,μ−sα−sβ⋅eh,g1−sδ1−sδ2⋅eh,g1syeT3,μeg0,g1c,R˜4⟵T1sxu−sδ1,R˜5⟵T2sxv−sδ2,R˜6⟵T4sxu−sδ1−sδ2.The receiver checks the challenge valuec by testing as follows:(12)c=?HM,T1,T2,T3,T4,R˜1,R˜2,R˜3,R˜4,R˜5,R˜6.The receiver will proceed if the relation holds. Otherwise, she will report the suspicious vehicle to TA.(13)eT3,g1sx⋅eh,μ−sα−sβ⋅eh,g1−sδ1−sδ2⋅eh,g1sy=eT3,g1rx+cxi⋅eh,μ−rα−ca−rβ−cb⋅eh,g1−rδ1−cδ1−rδ2−cδ2⋅eh,g1ry+cyi=eT3,g1xic⋅eT3,g1rx⋅eh−a−b,μc⋅eh,μ−rα−rβ⋅eh,g1−rδ1−rδ2⋅eh−a−b,g1xic⋅eh,g1ry⋅eh,g1yic=eT3,g1xic⋅eh−a−b,μc⋅eh−a−b,g1xic⋅eh,g1yic⋅R3=eT3h−a−b,μg1xic⋅eT3,μ−c⋅eh,g1yic⋅R3=eAi,μg1xi⋅eh,g1yi/eT3,μc⋅R3=eg0,g1/eT3,μc⋅R3.The calculation process ofR˜3 of the equation (11) is shown in equation (13), where T3=Aiha+b and Ai⟵g0/hyi1/γ+xi, μ=g1γ, and the expression is valid(14)eAi,μg1xi⋅eh,g1yi=eg0,g1.The calculation process ofR˜6 of the equation (11) is shown in the following equation:(15)T4sxu−sδ1−sδ2=ua+brx+cxiu−rδ1+cδ1−rδ2+cδ2,=ua+brx+cxiu−rδ1+caxi−rδ2+cbxi,=ua+brxu−rδ1−rδ2,=R6.The verification process ofR˜1,R˜2,R˜4,R˜5 is similar to R˜6 and we omit it here.(ii)
Revocation verification: We refer to the VLR (verifier-local revocation) mechanism proposed by Boneh and Shacham [19]. Suppose revocation list (RL) contains the private value of all revoked vehicles. More precisely,(16)RL=A1∗,…,An∗,.whereAi∗ is traced by TA. For each element A∈RL, check whether A is encoded in T3,T4 by testing if(17)eT3/A,u=?eT4,h.If no elementA of RL is encoded in T3,T4, then the signer has not been revoked. Otherwise, some Ai∗=A indicates that the vehicle Vi has been revoked.The signatureσ is valid if it passes both verifications.


### 4.4.5. Vehicles Tracing

In this phase, TA has the ability to trace the signer of the messages. Using the tracing key and valuesT1,T2,T3 in the signature σ, TA can reveal the signer’s identity which is related to Ai by computing Ai⟵T3/T1α⋅T2β. To hide the identity of the vehicle, the parameter Ai related to the real identity of a vehicle is a private value saved by TA.Since the TA holds tracing keyα,β, uα=vβ=h, and T1⟵ua,T2⟵vb,T3⟵Aiha+b, then(18)T3T1α⋅T2β=Aiha+buaα⋅vbβ,=Aiha+bha⋅hb,=Ai.TheAi is derived from T1,T2,T3 with tracing key α,β.


### 4.4.6. Key Update

In this phase, the vehicles can update their secret keys online by themselves. For example, the vehicleVi sends the new public key PK^i through some authenticated channel, where PK^i=hy^i. TA will compute new SDH pair A^i∗,x^i, and then send back A^i∗,x^i, where A^i∗=g1/PK^i1/γ+x^i. The vehicle will update its public key and secret key as follows.Note thatg0=φg1 and Ai=φA^i∗. Given public key PK^i, TA will use private key γ to compute the A^i∗ and send back A^i,x^i. The vehicle with old public key g0,g1,u,v,μ,h and secret key x^i,y^i construct new public key g^0,g^1,u,v,μ^,h, where g^0=g01/γ+x^i, g^1=g1/PK^i1/γ+x^i, μ^=g^1γ, and g0,g1∈G. More precisely,(19)g^0⟵φA^i∗=g01/γ+x^i,g^1⟵A^i∗=g1PK^i1/γ+x^i,μ^⟵g1PK^i⋅A^i∗−x^i=g1PK^i1−x^i/γ+x^i,=A^i∗γ,=g^1γ.Hence, the new secret key of the vehicle isx^i,y^i, and Ai updates to A^i∗. The new public key g^0,g^1,u,v,μ^,h is broadcast by TA.


## 4.4.1. System Initialization

In this phase, TA initiates the system. TA picks the private keyγ which is selected randomly from Zp∗, and then computes μ=g1γ, where g1 is a generator of multiplicative cyclic group G. TA selects h∈RG/1G and α,β∈RZp∗, and sets u,v,h∈G such that uα=vβ=h, where u,v are generators of multiplicative cyclic group G, and α,β is a tracing key. TA employs a secure hash function H:0,1∗⟶Zp which is used as a random oracle in the proof of security. TA publishes the public parameters g0,g1,u,v,μ,h,H.


## 4.4.2. The Registration of Vehicles

In this phase, the vehicle registers at TA through secure channel. The vehicleVi selects yi∈RZp∗ as a partial private key and computes PKi=hyi∈G and sends PKi to the TA. The TA generates and sends back a SDH tuple Ai,xi by picking xi∈RZp∗ and setting Ai⟵g0/PKi1/γ+xi, where Ai regards as pseudo-ID of the vehicle Vi. In addition, the value Ai is bound to the real identity of the vehicle Vi, and Ai can be derived by the TA. The secret key of vehicle Vi is ski:=xi,yi.The public keyPKi of vehicle is used to register to TA. The private key ski consists of two partial keys xi and yi. The partial key yi is generated by the vehicle and updated periodically or deliberately. The partial key xi is generated by TA under the public key pki corresponding to yi. Both private keys xi and yi are used for the signature.The vehicleVi will get secret key ski:=xi,yi and private value Ai after this phase.


## 4.4.3. Message Signing

In this phase, the vehicle signs messages before broadcasting them. Given public keyg0,g1,u,v,μ,h, secret key xi,yi, Ai, and a message M∈0,1∗, the vehicle computes and outputs a signature σ as follows:(6)σ⟵T1,T2,T3,T4,c,sα,sβ,sx,sy,sδ1,sδ2.(i)
Select randomnessa,b∈RZp as session keys and compute T1⟵ua,T2⟵vb,T3⟵Aiha+b,T4⟵ua+b and δ1⟵xia,δ2⟵xib.(ii)
Pick random valuesrα,rβ,rx,ry,rδ1,rδ2∈RZp∗, and then compute R1,R2,R3,R4,R5,R6 as follows:(7)R1⟵urα,R2⟵vrβ,R3⟵eT3,g1rx⋅eh,μ−rα−rβ⋅eh,g1−rδ1−rδ2⋅eh,g1ry,R4⟵T1rx⋅u−rδ1,R5⟵T2rx⋅v−rδ2,R6⟵T4rxu−rδ1−rδ2.(iii)
Compute challenge value as follows:(8)c⟵HM,T1,T2,T3,T4,R1,R2,R3,R4,R5,R6.(iv)
Compute helper valuessα,sβ,sx,sy,sδ1,sδ2 as follows:(9)sα=rα+ca,sβ=rβ+cb,sx=rx+cxi,sy=ry+cyisδ1=rδ1+cδ1,sδ2=rδ2+cδ2.(v)
Broadcast signatureσ.Note that,G is of size 22-byte and elements in G are 171-bit strings and p is a 170-bit prime. The signature of our scheme is formed as follows:(10)T1,T2,T3,T4,c,sα,sβ,sx,sy,sδ1,sδ2,where c,sα,sβ,sx,sy,sδ1,sδ2∈Zp and T1,T2,T3,T4∈G. So, the total length of the signature is 171×4+170×7=1874 bits = 235 bytes.


## 4.4.4. Message Verification

In this phase, the receiver verifies the validity of the signature from the vehicles as well as the revocation status of the revoked vehicle.(i)
Signature verification: given signatureσ and public key g0,g1,u,v,μ,h to compute R˜1,R˜2,R˜3,R˜4,R˜5,R˜6 as follows:(11)R˜1⟵usαT1−c,R˜2⟵vsβT2−c,R˜3⟵eT3,g1sx⋅eh,μ−sα−sβ⋅eh,g1−sδ1−sδ2⋅eh,g1syeT3,μeg0,g1c,R˜4⟵T1sxu−sδ1,R˜5⟵T2sxv−sδ2,R˜6⟵T4sxu−sδ1−sδ2.The receiver checks the challenge valuec by testing as follows:(12)c=?HM,T1,T2,T3,T4,R˜1,R˜2,R˜3,R˜4,R˜5,R˜6.The receiver will proceed if the relation holds. Otherwise, she will report the suspicious vehicle to TA.(13)eT3,g1sx⋅eh,μ−sα−sβ⋅eh,g1−sδ1−sδ2⋅eh,g1sy=eT3,g1rx+cxi⋅eh,μ−rα−ca−rβ−cb⋅eh,g1−rδ1−cδ1−rδ2−cδ2⋅eh,g1ry+cyi=eT3,g1xic⋅eT3,g1rx⋅eh−a−b,μc⋅eh,μ−rα−rβ⋅eh,g1−rδ1−rδ2⋅eh−a−b,g1xic⋅eh,g1ry⋅eh,g1yic=eT3,g1xic⋅eh−a−b,μc⋅eh−a−b,g1xic⋅eh,g1yic⋅R3=eT3h−a−b,μg1xic⋅eT3,μ−c⋅eh,g1yic⋅R3=eAi,μg1xi⋅eh,g1yi/eT3,μc⋅R3=eg0,g1/eT3,μc⋅R3.The calculation process ofR˜3 of the equation (11) is shown in equation (13), where T3=Aiha+b and Ai⟵g0/hyi1/γ+xi, μ=g1γ, and the expression is valid(14)eAi,μg1xi⋅eh,g1yi=eg0,g1.The calculation process ofR˜6 of the equation (11) is shown in the following equation:(15)T4sxu−sδ1−sδ2=ua+brx+cxiu−rδ1+cδ1−rδ2+cδ2,=ua+brx+cxiu−rδ1+caxi−rδ2+cbxi,=ua+brxu−rδ1−rδ2,=R6.The verification process ofR˜1,R˜2,R˜4,R˜5 is similar to R˜6 and we omit it here.(ii)
Revocation verification: We refer to the VLR (verifier-local revocation) mechanism proposed by Boneh and Shacham [19]. Suppose revocation list (RL) contains the private value of all revoked vehicles. More precisely,(16)RL=A1∗,…,An∗,.whereAi∗ is traced by TA. For each element A∈RL, check whether A is encoded in T3,T4 by testing if(17)eT3/A,u=?eT4,h.If no elementA of RL is encoded in T3,T4, then the signer has not been revoked. Otherwise, some Ai∗=A indicates that the vehicle Vi has been revoked.The signatureσ is valid if it passes both verifications.


## 4.4.5. Vehicles Tracing

In this phase, TA has the ability to trace the signer of the messages. Using the tracing key and valuesT1,T2,T3 in the signature σ, TA can reveal the signer’s identity which is related to Ai by computing Ai⟵T3/T1α⋅T2β. To hide the identity of the vehicle, the parameter Ai related to the real identity of a vehicle is a private value saved by TA.Since the TA holds tracing keyα,β, uα=vβ=h, and T1⟵ua,T2⟵vb,T3⟵Aiha+b, then(18)T3T1α⋅T2β=Aiha+buaα⋅vbβ,=Aiha+bha⋅hb,=Ai.TheAi is derived from T1,T2,T3 with tracing key α,β.


## 4.4.6. Key Update

In this phase, the vehicles can update their secret keys online by themselves. For example, the vehicleVi sends the new public key PK^i through some authenticated channel, where PK^i=hy^i. TA will compute new SDH pair A^i∗,x^i, and then send back A^i∗,x^i, where A^i∗=g1/PK^i1/γ+x^i. The vehicle will update its public key and secret key as follows.Note thatg0=φg1 and Ai=φA^i∗. Given public key PK^i, TA will use private key γ to compute the A^i∗ and send back A^i,x^i. The vehicle with old public key g0,g1,u,v,μ,h and secret key x^i,y^i construct new public key g^0,g^1,u,v,μ^,h, where g^0=g01/γ+x^i, g^1=g1/PK^i1/γ+x^i, μ^=g^1γ, and g0,g1∈G. More precisely,(19)g^0⟵φA^i∗=g01/γ+x^i,g^1⟵A^i∗=g1PK^i1/γ+x^i,μ^⟵g1PK^i⋅A^i∗−x^i=g1PK^i1−x^i/γ+x^i,=A^i∗γ,=g^1γ.Hence, the new secret key of the vehicle isx^i,y^i, and Ai updates to A^i∗. The new public key g^0,g^1,u,v,μ^,h is broadcast by TA.


## 5. Security Analysis and Comparison

In this section, we will show that the proposed scheme satisfies the security requirements of VANETs and compare the security with other schemes.


### 5.1. Security Analysis

#### 5.1.1. Authentication

The receiver can identify the invalid vehicles by verifying the signature of the messages. The generation of signature requires the secret keyxi,yi and Ai of the sender, where Ai,xi is an SDH pair.Given the public parametersg0,g1,u,v,μ,h,H, and for any vehicle with secret key xi,yi and Ai, the registration algorithm employed in the TA guarantees that Aiγ+xi⋅PKi=g0, so Ai,xi is an SDH tuple for μ=g1γ. A correct group signature σ of message M signed with secret key xi,yi and Ai as equation (6) is proved to be correct by testing equation (12).Our protocol is supported by honest-verifier zero-knowledge proof of an SDH pair under the DL assumption. Due to the fact that SDH problem is hard, the adversary cannot getxi,yi and generate a valid signature.


#### 5.1.2. Privacy

The identity of the vehicle is fully-anonymous. The vehicle only broadcasts the signatureσ of messages and publishes public key g0,g1,u,v,μ,h, and the signature or public key does not carry any information concerning the identity of the sender. The private key xi,yi is computationally hard to derive from Ai or the transcript under SDH problem. It is computationally hard to derive identity information of the message sender from the signature σ. In addition, the real identity of the vehicle is bound to Ai (updated as partial secret key yi is updated) and managed by the TA, which is of very high security. Therefore, the privacy information of the vehicle is protected.


#### 5.1.3. Traceability

The real identity of the vehicle is fully-traceable. The vehicle can be tracked by the tracing key. As equation (18) does, TA can reveal the vehicle’s identity by computing Ai=T3/T1α⋅T2β, which is bound to the real identity of the vehicle using the tracing key α,β. The adversary cannot track the vehicles by analyzing the signature, as for the tracing key α,β cannot be derived under the decision linear problem.


#### 5.1.4. Unlinkability

The vehicle signs message with private keysx,y which cannot be derived from the public key under SDH assumption. Each signature is generated by session keys a,b∈RZp and private keys x,y. Even the public key has not been updated for a long time, each signature will not be the same because of the helper value sα,sβ,sx,sy,sδ1,sδ2 generated by session keys. The security of the session key is guaranteed by the linear encryption. The receiver cannot derive Ai related to the real identity of a vehicle from the signature. Due to the randomness of session keys a,b, no adversary could link two anonymous identifiers or two different signatures σ1≠σ2 generated by the same vehicle. Furthermore, vehicle can regularly update its partial secret key yi locally, so the identity binder Ai gets updated as well.


#### 5.1.5. Exculpability

Exculpability requests that the private key is only known to herself.TA generates a tracing keyα,β and a partial key xi for the vehicle in the system initialization phase and vehicle registration phase, respectively. The vehicle generates partial key yi for herself. The partial key xi is an exponent of SDH tuple Ai,xi. The partial key yi is an exponent of public key PKi.TA cannot derive the secret keyyi of vehicle from PKi under DL assumption. So TA does not have the signing key xi,yi of vehicle to sign the message for it. The strong exculpability is thus achieved.


### 5.2. Comparison

In this subsection, we compare the security of our scheme with other schemes from the following aspects and are listed in Table2.Table 2
Comparison of our scheme to others.
Schemes[4][5][10][20][7][6]OursReal ID exposure levelTRATATRCLeader-RSUGMTATAPseudo-ID untraceableNoNo—YesYesYesYesUntrusted RSUsNoNoNoNoNoSemiYesUnlinkabilityNoYesYesYesYesYesYesPrivate key update onlineNoNoYes (TRC)Yes (GM)Yes (GM)Yes (TA)Yes (V)TracingYesYesYesYesYesYesYesMember revocationPKGTATAPartialGMTATAExculpabilityNoNoYesNoNoNoYesWe reduce the credibility of RSUs in our scheme. As external devices, RSUs are vulnerable to geographic attacks. But the scheme of Funderburg and Lee [6] set the RSUs to be semitrusted devices, the leader-RSU would know the real identity of the vehicle in Lim et al.‘s scheme [20], and Shim’s scheme [4] also treats RSUs as trusted devices and exposes the real identity of the vehicle to the trace authority (TRA).To prevent malicious tracking of vehicles by pseudo-identity, we implemented our protocol by short group signature technology. The ID-based schemes [4, 5] will expose the PID of the vehicle in the wireless environment. As for [10], the real-ID of vehicle is bound to public key.The manager of vehicle’s key decides when the key gets updated and the revocation of the group members. In our scheme, the signing key of the vehicle consists of two parts: the partial key distributed by TA and the partial key generated by the vehicle itself. The group signature-based schemes [6, 7, 20] cannot update the signing key by the vehicle instead by the group manager (GM) or TA. The ID-based schemes [4, 5] would update the key of the vehicle offline or by a secure channel. Unfortunately, Lim et al.’s [20] scheme cannot revoke the new member of a group. The scheme [10] entrusts the task of a session key update to the TRC (transportation regulation centre), which has great burden, and it is difficult to update the vehicle key in real-time.Our scheme is designed by applying double key approach, so the global manager TA does not know the full signing key of the vehicle. The strong exculpability is met in this paper and the vehicle cannot deny the signature signed by itself, while other schemes [4–7, 20] cannot achieve this goal.


## 5.1. Security Analysis

### 5.1.1. Authentication

The receiver can identify the invalid vehicles by verifying the signature of the messages. The generation of signature requires the secret keyxi,yi and Ai of the sender, where Ai,xi is an SDH pair.Given the public parametersg0,g1,u,v,μ,h,H, and for any vehicle with secret key xi,yi and Ai, the registration algorithm employed in the TA guarantees that Aiγ+xi⋅PKi=g0, so Ai,xi is an SDH tuple for μ=g1γ. A correct group signature σ of message M signed with secret key xi,yi and Ai as equation (6) is proved to be correct by testing equation (12).Our protocol is supported by honest-verifier zero-knowledge proof of an SDH pair under the DL assumption. Due to the fact that SDH problem is hard, the adversary cannot getxi,yi and generate a valid signature.


### 5.1.2. Privacy

The identity of the vehicle is fully-anonymous. The vehicle only broadcasts the signatureσ of messages and publishes public key g0,g1,u,v,μ,h, and the signature or public key does not carry any information concerning the identity of the sender. The private key xi,yi is computationally hard to derive from Ai or the transcript under SDH problem. It is computationally hard to derive identity information of the message sender from the signature σ. In addition, the real identity of the vehicle is bound to Ai (updated as partial secret key yi is updated) and managed by the TA, which is of very high security. Therefore, the privacy information of the vehicle is protected.


### 5.1.3. Traceability

The real identity of the vehicle is fully-traceable. The vehicle can be tracked by the tracing key. As equation (18) does, TA can reveal the vehicle’s identity by computing Ai=T3/T1α⋅T2β, which is bound to the real identity of the vehicle using the tracing key α,β. The adversary cannot track the vehicles by analyzing the signature, as for the tracing key α,β cannot be derived under the decision linear problem.


### 5.1.4. Unlinkability

The vehicle signs message with private keysx,y which cannot be derived from the public key under SDH assumption. Each signature is generated by session keys a,b∈RZp and private keys x,y. Even the public key has not been updated for a long time, each signature will not be the same because of the helper value sα,sβ,sx,sy,sδ1,sδ2 generated by session keys. The security of the session key is guaranteed by the linear encryption. The receiver cannot derive Ai related to the real identity of a vehicle from the signature. Due to the randomness of session keys a,b, no adversary could link two anonymous identifiers or two different signatures σ1≠σ2 generated by the same vehicle. Furthermore, vehicle can regularly update its partial secret key yi locally, so the identity binder Ai gets updated as well.


### 5.1.5. Exculpability

Exculpability requests that the private key is only known to herself.TA generates a tracing keyα,β and a partial key xi for the vehicle in the system initialization phase and vehicle registration phase, respectively. The vehicle generates partial key yi for herself. The partial key xi is an exponent of SDH tuple Ai,xi. The partial key yi is an exponent of public key PKi.TA cannot derive the secret keyyi of vehicle from PKi under DL assumption. So TA does not have the signing key xi,yi of vehicle to sign the message for it. The strong exculpability is thus achieved.


## 5.1.1. Authentication

The receiver can identify the invalid vehicles by verifying the signature of the messages. The generation of signature requires the secret keyxi,yi and Ai of the sender, where Ai,xi is an SDH pair.Given the public parametersg0,g1,u,v,μ,h,H, and for any vehicle with secret key xi,yi and Ai, the registration algorithm employed in the TA guarantees that Aiγ+xi⋅PKi=g0, so Ai,xi is an SDH tuple for μ=g1γ. A correct group signature σ of message M signed with secret key xi,yi and Ai as equation (6) is proved to be correct by testing equation (12).Our protocol is supported by honest-verifier zero-knowledge proof of an SDH pair under the DL assumption. Due to the fact that SDH problem is hard, the adversary cannot getxi,yi and generate a valid signature.


## 5.1.2. Privacy

The identity of the vehicle is fully-anonymous. The vehicle only broadcasts the signatureσ of messages and publishes public key g0,g1,u,v,μ,h, and the signature or public key does not carry any information concerning the identity of the sender. The private key xi,yi is computationally hard to derive from Ai or the transcript under SDH problem. It is computationally hard to derive identity information of the message sender from the signature σ. In addition, the real identity of the vehicle is bound to Ai (updated as partial secret key yi is updated) and managed by the TA, which is of very high security. Therefore, the privacy information of the vehicle is protected.


## 5.1.3. Traceability

The real identity of the vehicle is fully-traceable. The vehicle can be tracked by the tracing key. As equation (18) does, TA can reveal the vehicle’s identity by computing Ai=T3/T1α⋅T2β, which is bound to the real identity of the vehicle using the tracing key α,β. The adversary cannot track the vehicles by analyzing the signature, as for the tracing key α,β cannot be derived under the decision linear problem.


## 5.1.4. Unlinkability

The vehicle signs message with private keysx,y which cannot be derived from the public key under SDH assumption. Each signature is generated by session keys a,b∈RZp and private keys x,y. Even the public key has not been updated for a long time, each signature will not be the same because of the helper value sα,sβ,sx,sy,sδ1,sδ2 generated by session keys. The security of the session key is guaranteed by the linear encryption. The receiver cannot derive Ai related to the real identity of a vehicle from the signature. Due to the randomness of session keys a,b, no adversary could link two anonymous identifiers or two different signatures σ1≠σ2 generated by the same vehicle. Furthermore, vehicle can regularly update its partial secret key yi locally, so the identity binder Ai gets updated as well.


## 5.1.5. Exculpability

Exculpability requests that the private key is only known to herself.TA generates a tracing keyα,β and a partial key xi for the vehicle in the system initialization phase and vehicle registration phase, respectively. The vehicle generates partial key yi for herself. The partial key xi is an exponent of SDH tuple Ai,xi. The partial key yi is an exponent of public key PKi.TA cannot derive the secret keyyi of vehicle from PKi under DL assumption. So TA does not have the signing key xi,yi of vehicle to sign the message for it. The strong exculpability is thus achieved.


## 5.2. Comparison

In this subsection, we compare the security of our scheme with other schemes from the following aspects and are listed in Table2.Table 2
Comparison of our scheme to others.
Schemes[4][5][10][20][7][6]OursReal ID exposure levelTRATATRCLeader-RSUGMTATAPseudo-ID untraceableNoNo—YesYesYesYesUntrusted RSUsNoNoNoNoNoSemiYesUnlinkabilityNoYesYesYesYesYesYesPrivate key update onlineNoNoYes (TRC)Yes (GM)Yes (GM)Yes (TA)Yes (V)TracingYesYesYesYesYesYesYesMember revocationPKGTATAPartialGMTATAExculpabilityNoNoYesNoNoNoYesWe reduce the credibility of RSUs in our scheme. As external devices, RSUs are vulnerable to geographic attacks. But the scheme of Funderburg and Lee [6] set the RSUs to be semitrusted devices, the leader-RSU would know the real identity of the vehicle in Lim et al.‘s scheme [20], and Shim’s scheme [4] also treats RSUs as trusted devices and exposes the real identity of the vehicle to the trace authority (TRA).To prevent malicious tracking of vehicles by pseudo-identity, we implemented our protocol by short group signature technology. The ID-based schemes [4, 5] will expose the PID of the vehicle in the wireless environment. As for [10], the real-ID of vehicle is bound to public key.The manager of vehicle’s key decides when the key gets updated and the revocation of the group members. In our scheme, the signing key of the vehicle consists of two parts: the partial key distributed by TA and the partial key generated by the vehicle itself. The group signature-based schemes [6, 7, 20] cannot update the signing key by the vehicle instead by the group manager (GM) or TA. The ID-based schemes [4, 5] would update the key of the vehicle offline or by a secure channel. Unfortunately, Lim et al.’s [20] scheme cannot revoke the new member of a group. The scheme [10] entrusts the task of a session key update to the TRC (transportation regulation centre), which has great burden, and it is difficult to update the vehicle key in real-time.Our scheme is designed by applying double key approach, so the global manager TA does not know the full signing key of the vehicle. The strong exculpability is met in this paper and the vehicle cannot deny the signature signed by itself, while other schemes [4–7, 20] cannot achieve this goal.


## 6. Performance

In this section, we analyze the performance of our scheme along with the existing relevant schemes [4–7, 10, 20].Firstly, we define some notations of cryptography operations, as shown in the Table3.Table 3
The notation of the execution time of cryptography operations.
NotationDescriptionTbpA bilinear pairing operationeP,Q, where P,Q∈GTsmbpPairing-based scale multiplication operations⋅P, where s∈Zq∗,P∈GTpmbpPairing multiplication operationeP1,Q1eP2,Q2, where P1,P2,Q1,Q2∈GTpabpPairing-based point addition operationP+Q, where P,Q∈GThtpParing-based hash-to-point operation whereH:0,1∗⟶GTsmeccECC-based scale multiplication operationx⋅P where x∈Zq∗,P∈GTpaeccECC-based point addition operationP+Q where P,Q∈GThOne-way hash function operationWe compute the execution time of the cryptographic operations shown in Table3 using a well-known library MIRACL [21]. The high-level interface to pairing functions is Type 1 pairings whose parameter of pairing-friendly curve (PFC) is defined in the class PFC.The hardware platform is on the windows 10 operating system, and its CPU is Intel (R) Core (TM) i7-5500u with 8 gigabytes of memory. The measurement results are listed in Table4, which is the average of 1000 times for every operation.Table 4
The execution time of cryptography operations, which is the average of 1000 times for every operation. The hardware platform is on the windows 10 operating system, and its CPU is Intel (R) Core (TM) i7-5500u with 8 gigabytes of memory.
Cryptography operationsExecution time (milliseconds)Tbp11.1991Tsmbp3.5039Tpmbp11.6208Tpabp0.0295Thtp0.1202Tsmecc0.0010Tpaecc0.0011Th0.0017The computation cost of the message signing, the single verification of a message, and the batch verification of multiple messages with relevant schemes [4–7, 10, 20] are compared in Table 5.Table 5
The computation cost of the routine.
SchemesSigningSingle verificationBatch verification[4]3Tsmbp+2Tpabp+Th≈10.5724ms3Tbp+2Tsmbp+Tpabp+2Th≈40.6380ms3Tbp+n+1Tsmbp+3n−1Tpabp+2nTh≈3.5958n+37.0127ms[5]3Tsmecc+3Th≈0.0041ms3Tsmecc+2Th+2Tpaecc≈0.0086msn+2Tsmecc+3n−1Th+2nTpaecc≈0.0083n+0.0003ms[10]4Tsmbp+Tpabp≈14.0451ms2Tbp+Tsmbp+Tpabp≈25.9316ms2Tbp+Tsmbp+2n+1Tpabp≈0.059n+25.9316ms[6]2Tpmbp+Thtp≈23.3618ms4Tpmbp+Thtp≈46.6035ms4nTpmbp+nThtp≈46.6035nms[7]2Tpmbp+2Thtp≈23.4820ms4Tpmbp+2Thtp≈46.7237ms4nTpmbp+2nThtp≈46.7237nms[20]2Tpmbp+Thtp≈23.3618ms4Tpmbp+Thtp≈46.6035ms4nTpmbp+nThtp≈46.6035nmsOurs3Tpmbp+Thtp≈34.9826ms5Tpmbp+Thtp≈58.2243ms5nTpmbp+nThtp≈58.2243nmsAs illustrated in Table5, due to the high time complexity of bilinear pairing, the rate [4, 6, 7, 20] is generally lower than that of ID-based schemes [5, 10]. But compared with other relevant schemes, the rate of our scheme is almost the same as that of other schemes [6, 7, 20], which is based on short group signatures [9]. It is worth mentioning that our scheme meets higher security requirements. The security of exculpability cannot be achieved in [6, 7, 20] which were based on short group signatures.Our protocol is simulated on the windows 10 operating system, and its CPU is Intel (R) Core (TM) i7-5500u with 8 gigabytes of memory. We compute the execution time of the routine of the signature process, verification process, and key update process using cryptographic library MIRACL and the performance is shown in Figure2.Figure 2
Approximate time required for signature, verification, and update processes.As illustrated in Figure2, each signature signed by vehicle takes less than 32 ms. The process of message verification takes about 25 ms, and the keys can be updated within 21 ms approximately.


## 7. Conclusion

In this paper, we propose a privacy-preserving authentication scheme for VANETs with strong exculpability. By using the double key approach and short group signature, vehicles update their private key online and establish trusted communication with TA and RSUs. We also showed the strong security property of our scheme regarding the message authentication, anonymity, traceability, unlinkability, and strong exculpability. We further compared with other relative schemes and showed our advantages, regarding the execution efficiency and the security properties.



---

*Source: 8676929-2023-02-07.xml*