# A Practical Authentication Framework for VANETs

Authors: Baosheng Wang; Yi Wang; Rongmao Chen
Journal: Security and Communication Networks
 (2019)

---

## Abstract

In vehicular ad hoc networks (VANETs), conditional privacy preserving authentication (CPPA) scheme is widely deployed to solve security and privacy issues. Existing CPPA schemes usually require ideal tamper-proof devices (TPDs) on vehicles which, however, might be infeasible or do not exist in reality due to high security requirements. To address this problem, we propose a practical framework of CPPA scheme that supports more realistic TPDs which are less secure correspondingly. We demonstrate that this framework also manages to achieve nonframeability in addition to other security objectives including nonrepudiation, conditional privacy preserving, and unlinkability. Moreover, performance analysis shows that our framework has better efficiency in authentication. All these features make our framework practical for VANETs.


---

## Body

## 1. Introduction

As one form of mobile ad hoc network in the domain of vehicles, vehicular ad hoc network (VANET) is a promising solution for improving road safety and driving experience. Generally, a VANET is composed of roadside units (RSUs) and vehicles equipped with electronic components such as wheel rotation sensors, radars, and on-broad units (OBUs). Various sensors on vehicle provide continuous monitoring of driving information, such as speed, direction, and position. OBUs enable vehicles to communicate with not only each other but also RSUs via Dedicated Short Range Communications (DSRC) technique. Thus, there are plenty of potential applications on VANETs which can be categorized into safety-related, such as collision avoidance and automatic driving, and other applications, such as traffic navigation and infotainment.For the security of VANET and its applications, especially safety-related applications, it is crucial to authenticate transmitted messages and identities of their senders; otherwise any unauthorized vehicle could disseminate bogus messages easily or conduct other malicious behaviours without being caught, which might cause great damages to urban transportation systems and even endanger the lives of drivers and pedestrians. To authenticate itself to other entities, vehicle might have to prove the possession of secret information which is usually saved in tamper-proof device (TPD) on vehicle. In addition to storage of secret data, TPD also provides computation service where secret information is involved. For instance, the simplest way to achieve authentication is using digital signature. Every vehicle is assigned to a public/private key pair, and TPD is responsible for storing private keys and generating signatures. Many authentication schemes [1–8] are designed under the assumption of using ideal TPD that can never be compromised by adversary to securely store secrets and to perform related calculations. However, this assumption might be too strong to be realistic in practice. Specifically, in VANET conditions, TPD might mistake normal shocks of vehicle caused by uneven road surface for malicious tampering and erase all the secrets [9]. Moreover, it is possible for adversary to collect sufficient information about secrets in TPD through side-channel attacks such as electromagnetic radiation [10] and power consumption analysis [11].To address this problem, we loosen the security requirements on ideal TPD and consider a more realistic TPD for practical use. Comparing to ideal TPD, realistic TPD is less sensitive to vehicle shocks but might be compromised by sophisticated hardware tampering. To cope with such hardware tampering as well as aforementioned side-channel attacks, we assume that realistic TPD offers temporary storage of secrets and erases them regularly before adversary obtains substantial information about them. In this work, we propose an efficient framework of CPPA scheme based on identity-based cryptography (IBC) that only requires realistic TPD.Our framework also aims at achieving nonframeability [12]. That is, trusted authority (TA) that serves particular region as certification authority and RSUs cannot forge messages to frame an innocent vehicle. TA in existing works (e.g., [6, 13]) usually holds all the secrets of vehicles, so it is quite simple for unrestricted TA to impersonate any vehicle and forge its signature. In our framework, the key used for authentication is independently generated by vehicle itself and stored in TPD. TA that does not possess the authentication key of vehicle cannot impersonate vehicle and successfully authenticate itself to RSU. Meanwhile, RSU’s master key which is used to generate the signatures of messages sent by vehicles in our framework is unknown to TA. Thus, TA also cannot forge the signature of vehicle. Besides, RSU cannot forge it either as the pseudo-identity generation also requires vehicle’s authentication key.We design our framework with an objective of improving the efficiency of mutual authentication between vehicle and RSU. Since the location and identity of RSU are relatively fixed, RSU-to-vehicle (R2V) authentication is rather trivial and can be efficiently achieved by periodically broadcasting signed messages. However, vehicle-to-RSU (V2R) authentication in existing works (e.g., [13, 14]) needs the cooperation of TA. In contrast, V2R authentication in our framework does not require real-time interactions between RSUs and TA. Precisely, TA maintains a dynamic list that contains authentication-related information of vehicles, and every RSU is asked to store a latest copy of this list in the background. This list enables RSUs to complete the anonymous authentication of vehicles by themselves, which reduces the workload of TA and promotes the efficiency of authentication. Generally, the main contributions of our work are as follows.(i)
We propose an efficient IBC-based framework of CPPA scheme to solve security and privacy issues in VANETs. Due to the support of realistic TPD, our framework is a practical authentication solution in reality.(ii)
Our framework has achieved nonframeability. The authentication of vehicle and the generation of a valid signature both require vehicle’s self-chosen authentication key, which prevents TA and RSUs from framing an innocent vehicle.(iii)
In our framework, we design a mechanism to improve the efficiency of authentication. The overall workload of authentication is distributed to every RSU. Instead of participating in the process of authentication directly, TA just needs to maintain the latest information list for RSUs.(iv)
We give a specific analysis of our framework in terms of security and performance. We prove that this framework has achieved all the security objectives in Section3. Theoretical analysis on performance indicates that this framework provides excellent authentication efficiency.The rest of the paper is organized as follows. Section2 summarizes the related work on authentication schemes for VANETs. Section 3 introduces the architecture of VANETs and our design goals. Preliminary background of cryptographic primitives is provided in Section 4. In Section 5, we present our framework of CPPA scheme. Sections 6 and 7 give the comprehensive security analysis and performance evaluation of our framework, respectively. Section 8 concludes the paper.


## 2. Related Work

A number of related studies have been reported on authentication issue in VANETs, and their proposed authentication schemes can be categorized into following four types.Schemes based on Public Key Infrastructure (PKI) [9, 15]. PKI issues a bunch of public/private key pairs and public key certificates to vehicles. Before sending a message, vehicle has to attach a digital signature and a certificate to it, which might increase the communication overhead significantly. To achieve identity privacy and conditional anonymity, anonymous public keys are required for PKI and vehicles. The management of certificates including revocation could be a heavy burden to PKI.Schemes based on symmetric cryptosystem [12, 16, 17]. Message authentication code (MAC) can be adopted to authenticate message and the verification of the message can be completed in extremely short time. However, the process of message authentication might need the aid of RSUs, and vehicle cannot authenticate received message independently. TESLA [18] is an efficient broadcast authentication protocol based on MAC and loose time synchronization between network nodes. Based on TESLA and the prediction of vehicle direction, it is possible to achieve instant verification of beacon messages sent by vehicles. Unfortunately, this protocol allows adversary to trace the trajectory of vehicle.Schemes based on group signature [1, 4, 19–22]: group signature naturally provides privacy to group members because every member signs message on behalf the group. The group manager owns the master key of group and is able to learn the real identities of group members, which satisfies the requirement of conditional privacy preservation. However, the verification of group signature usually costs more time than that of traditional signature. Also, revoking compromised group members properly is still a problem.Schemes based on IBC [2, 6, 7, 13, 14, 23–25]. In identity-based signature (IBS) scheme, the identity of vehicle could be used as the public key, and the corresponding private key is generated by the private key generator (PKG) using master key. Comparing to PKI, it avoids the management of certificates. To achieve conditional privacy, vehicles communicate with other entities using pseudo-identities that are retrievable to authorities. Unfortunately, due to bilinear pairing operations, the time efficiency of IBS schemes is relatively lower than other traditional signature schemes. To improve the performance, batch verification is adopted to verify multiple signatures at the same time. Moreover, efficient one-time IBS [6, 13], identity-based online/offline signature (IBOOS) [7], and IBS without bilinear pairing [6] also are used in authentication schemes.


## 3. Background

### 3.1. Network Architecture

A VANET commonly consists of vehicles, RSUs, and TA, as shown in Figure1.Figure 1
The network architecture of VANET.TA plays the role of administrator in VANET and manages the authentication of network nodes including vehicles and RSUs. To join the VANET, all the nodes must register themselves at TA in advance. Due to the mobility of vehicles, we consider a frequently changing group of vehicles that requires TA to provide real-time registration service via secure network infrastructure. In contrast, the locations and total number of RSUs usually stay unchanged for a relatively long period of time. The registration of RSUs can be finished during initialization phase. Also, TA maintains a list of registered vehicles and has responsibility for revealing real identities of misbehaving vehicles and revoking licenses of these vehicles in time.RSUs as roadside infrastructure are scattered all over the region of TA. Communication between RSU and TA relies on wired channel while RSU communicates with vehicles via wireless channel using DSRC protocol. RSUs forward messages not only between TA and vehicles but also from one vehicle to another. A RSU and vehicles enrolled by it form a subgroup of VANET. Vehicles that newly enter the transmission range of RSU have to be authenticated by RSU.Every vehicle is equipped with OBU to communicate with other entities in VANET and support DSRC protocol. Realistic TPD is also embedded in vehicle. It provides temporary storage of secret information and related computation service, which is more feasible than ideal TPD that never discloses any secrets. Therefore, secrets stored in TPD needs to be updated regularly with the assistance of TA.


### 3.2. Design Goals

As a framework of CPPA scheme, our framework should satisfy basic requirements: authentication, nonrepudiation, identity privacy preserving, and conditional traceability.(i)
Authentication: there are two kinds of authentication: message and entity authentication. Message authentication is confirming that received messages are generated by valid vehicles and unmodified during transmission. Entity authentication, also called mutual authentication, requires that two entities into a session are able to identify each other.(ii)
Nonrepudiation: this property refers to a situation where a receiver is able to prove to a third party that sender cannot deny its responsibility for generating messages. It prevents adversary from forging messages in other identities.(iii)
Identity privacy preserving: vehicles on the roads are required to frequently broadcast messages including position, speed, direction, and driving status. Identity privacy preservation means that nobody could discover the binding between messages and real identities of vehicles.(iv)
Conditional traceability: in certain circumstances (e.g., traffic accidents), the real identities of vehicles should be retrievable. Conditional traceability enables TA only to recover the real identities of vehicles from saved messages.Considering the particular scenario of VANET, we also attempt to achieve other meaningful properties at the same time.(i)
Nonframeability: this property requires no entities in VANETs including TA and RSUs could frame an innocent vehicle or accuse an honest vehicle for having misbehaved. To achieve this security goal, we assume that TA does not collude with RSUs.(ii)
Ideal TPD freeness: under the premise of ensuring system security, this property proposed by Zhang et al. [13] permits the usage of realistic TPD or one with sufficient security level embedded in vehicle, instead of ideal one which can never be compromised by adversary.(iii)
Unlinkability: let m1 and m2 be two messages sent by one vehicle; this property means that one cannot determine whether m1 and m2 originate from the same vehicle or not. Unlinkability prevents adversary from tracking vehicles and profiling drivers.(iv)
Message confidentiality: in particular applications, messages should be transmitted to receivers in encrypted form and cannot be decoded by unauthorized entities.(v)
Attack resistance: this property requires that proposed framework can withstand common attacks, such as replay attack, impersonation attack, modification attack, and side-channel attack.


## 3.1. Network Architecture

A VANET commonly consists of vehicles, RSUs, and TA, as shown in Figure1.Figure 1
The network architecture of VANET.TA plays the role of administrator in VANET and manages the authentication of network nodes including vehicles and RSUs. To join the VANET, all the nodes must register themselves at TA in advance. Due to the mobility of vehicles, we consider a frequently changing group of vehicles that requires TA to provide real-time registration service via secure network infrastructure. In contrast, the locations and total number of RSUs usually stay unchanged for a relatively long period of time. The registration of RSUs can be finished during initialization phase. Also, TA maintains a list of registered vehicles and has responsibility for revealing real identities of misbehaving vehicles and revoking licenses of these vehicles in time.RSUs as roadside infrastructure are scattered all over the region of TA. Communication between RSU and TA relies on wired channel while RSU communicates with vehicles via wireless channel using DSRC protocol. RSUs forward messages not only between TA and vehicles but also from one vehicle to another. A RSU and vehicles enrolled by it form a subgroup of VANET. Vehicles that newly enter the transmission range of RSU have to be authenticated by RSU.Every vehicle is equipped with OBU to communicate with other entities in VANET and support DSRC protocol. Realistic TPD is also embedded in vehicle. It provides temporary storage of secret information and related computation service, which is more feasible than ideal TPD that never discloses any secrets. Therefore, secrets stored in TPD needs to be updated regularly with the assistance of TA.


## 3.2. Design Goals

As a framework of CPPA scheme, our framework should satisfy basic requirements: authentication, nonrepudiation, identity privacy preserving, and conditional traceability.(i)
Authentication: there are two kinds of authentication: message and entity authentication. Message authentication is confirming that received messages are generated by valid vehicles and unmodified during transmission. Entity authentication, also called mutual authentication, requires that two entities into a session are able to identify each other.(ii)
Nonrepudiation: this property refers to a situation where a receiver is able to prove to a third party that sender cannot deny its responsibility for generating messages. It prevents adversary from forging messages in other identities.(iii)
Identity privacy preserving: vehicles on the roads are required to frequently broadcast messages including position, speed, direction, and driving status. Identity privacy preservation means that nobody could discover the binding between messages and real identities of vehicles.(iv)
Conditional traceability: in certain circumstances (e.g., traffic accidents), the real identities of vehicles should be retrievable. Conditional traceability enables TA only to recover the real identities of vehicles from saved messages.Considering the particular scenario of VANET, we also attempt to achieve other meaningful properties at the same time.(i)
Nonframeability: this property requires no entities in VANETs including TA and RSUs could frame an innocent vehicle or accuse an honest vehicle for having misbehaved. To achieve this security goal, we assume that TA does not collude with RSUs.(ii)
Ideal TPD freeness: under the premise of ensuring system security, this property proposed by Zhang et al. [13] permits the usage of realistic TPD or one with sufficient security level embedded in vehicle, instead of ideal one which can never be compromised by adversary.(iii)
Unlinkability: let m1 and m2 be two messages sent by one vehicle; this property means that one cannot determine whether m1 and m2 originate from the same vehicle or not. Unlinkability prevents adversary from tracking vehicles and profiling drivers.(iv)
Message confidentiality: in particular applications, messages should be transmitted to receivers in encrypted form and cannot be decoded by unauthorized entities.(v)
Attack resistance: this property requires that proposed framework can withstand common attacks, such as replay attack, impersonation attack, modification attack, and side-channel attack.


## 4. Preliminaries

### 4.1. Cryptographic Schemes

A symmetric encryption scheme consists of three algorithms which are described as follows.(i)
KeyGen1n: this algorithm takes as input security parameter 1n and outputs key K∈K, where K is the key space.(ii)
EncK,m: this algorithm takes as input key K and message m and outputs ciphertext c.(iii)
DecK,c: this algorithm takes as input key K and ciphertext c and outputs message m.An identity-based signature (IBS) scheme is composed of four algorithms which are described as follows.(i)
Setup1n: this algorithm takes as input security parameter 1n and generates the public parameters PP and master key msk∈MK for private key generator (PKG). Note that msk is kept secret.(ii)
Extract(msk,ID): this algorithm takes as input master key msk and an identity and outputs a private key skID∈SK.(iii)
Sign(skID,m): this algorithm takes as input private key skID and message m and generates a signature Sign of message m.(iv)
Verify(PP,ID,m,Sign): this algorithm outputs “accept” if Sign is valid signature of message m and outputs “reject” otherwise.An identity-based online/offline signature (IBOOS) scheme is an IBS scheme where the process of generating signature can be divided into offline and online phases:(i)
Signoff⁡(PP): based on public parameters PP, this algorithm generates an offline signature Sign¯.(ii)
Signon(skID,Sign¯,m): based on private key skID, offline signature Sign¯, and message m, this algorithm generates a signature Sign of message m.An one-time identity-based signature (OT-IBS) scheme is an IBS scheme with one-time private keyskID. Similar to signing key in one-time signature scheme, every private key in OT-IBS can be used only once.


### 4.2. Cryptographic Hardness Assumption

Computational Diffie-Hellman (CDH) assumption: letG be a group with prime order p and g∈G is a random generator of G, and A is a probabilistic polynomial-time (PPT) algorithm that takes as input a tuple (g,ga,gb) and outputs gc. We define the CDH-advantage of A to be AdvACDHn=Pr⁡[Ag,ga,gb=gab]. The CDH assumption is that there is no PPT algorithm A that can compute gab with nonnegligible CDH-advantage.


## 4.1. Cryptographic Schemes

A symmetric encryption scheme consists of three algorithms which are described as follows.(i)
KeyGen1n: this algorithm takes as input security parameter 1n and outputs key K∈K, where K is the key space.(ii)
EncK,m: this algorithm takes as input key K and message m and outputs ciphertext c.(iii)
DecK,c: this algorithm takes as input key K and ciphertext c and outputs message m.An identity-based signature (IBS) scheme is composed of four algorithms which are described as follows.(i)
Setup1n: this algorithm takes as input security parameter 1n and generates the public parameters PP and master key msk∈MK for private key generator (PKG). Note that msk is kept secret.(ii)
Extract(msk,ID): this algorithm takes as input master key msk and an identity and outputs a private key skID∈SK.(iii)
Sign(skID,m): this algorithm takes as input private key skID and message m and generates a signature Sign of message m.(iv)
Verify(PP,ID,m,Sign): this algorithm outputs “accept” if Sign is valid signature of message m and outputs “reject” otherwise.An identity-based online/offline signature (IBOOS) scheme is an IBS scheme where the process of generating signature can be divided into offline and online phases:(i)
Signoff⁡(PP): based on public parameters PP, this algorithm generates an offline signature Sign¯.(ii)
Signon(skID,Sign¯,m): based on private key skID, offline signature Sign¯, and message m, this algorithm generates a signature Sign of message m.An one-time identity-based signature (OT-IBS) scheme is an IBS scheme with one-time private keyskID. Similar to signing key in one-time signature scheme, every private key in OT-IBS can be used only once.


## 4.2. Cryptographic Hardness Assumption

Computational Diffie-Hellman (CDH) assumption: letG be a group with prime order p and g∈G is a random generator of G, and A is a probabilistic polynomial-time (PPT) algorithm that takes as input a tuple (g,ga,gb) and outputs gc. We define the CDH-advantage of A to be AdvACDHn=Pr⁡[Ag,ga,gb=gab]. The CDH assumption is that there is no PPT algorithm A that can compute gab with nonnegligible CDH-advantage.


## 5. Proposed Framework of CPPA Scheme

### 5.1. Overview

In initialization phase of our framework, TA generates parameters for the whole system. RSUs and vehicles are allowed to join VANET after registration. For vehicle that drives into a new RSU region, it also needs to conduct mutual authentication with RSU. To conceal the real identity of vehicle from RSU, V2R authentication needs the assistance of a list maintained by TA that consists of authentication-related information of vehicles. If this authentication succeeds, vehicle would receive the master key of RSU and be able to sign messages in pseudo-identities. Only TA can recover the real identity of vehicle from its pseudo-identities. There also is an efficient and secure mechanism of updating secrets (i.e., authentication key of vehicle and master key of RSU) in TPD before adversary has collected sufficient information via side-channel attacks. Notations used in our framework are defined as follows.(i)
IBS=(Setup, Extract, Sign, Verify): an IBS scheme that supports batch verification of multiple signatures.(ii)
SE=(KeyGen, Enc, Dec): a symmetric encryption scheme with message space 0,1∗ and key space K.(iii)
G1,G2: two cyclic groups with prime order q.(iv)
g1,g2: two generators of G1,G2.(v)
H1,H2,H3,H4: four hash functions H1:0,1∗→G1, H2:G2→K, H3:0,1∗→0,1l, and H4:0,1∗→Zq∗.(vi)
IDUi/IDVj: real identity of RSU Ui or vehicle Vj.(vii)
PIDVj: pseudo-identity of vehicle Vj.


### 5.2. System Initialization

In initialization phase, TA generates parameters for the whole system and all the RSUs and vehicles have to register themselves to TA before joining the VANET. Precisely, the system is initialized as follows.TA Setup: TA runs algorithmSetup to generate public parameters PPs and system master key msks. TA also generates two cyclic groups G1,G2with prime order q and picks generators g1∈G1,g2∈G2. Then it picks x,y,z∈Zq∗ and computes X=g1x,Y=g1y,Z=g1z which are used to generate pseudo-identities for vehicle. Hash functions H1:0,1∗→G1, H2:G2→K, H3:0,1∗→0,1l, and H4:0,1∗→Zq∗ are chosen by TA. The system public parameters are PP=(PPs,q,G1,G2,g1,g2,X,Y,Z,H1,H2,H3,H4). TA also maintains a private list L to record authentication information of registered vehicles as well as list Lpub that is only accessible to registered RSUs. The details of these lists are described later.RSU Setup: since TA is the only party that ownsmsks in current system, RSU Ui with identity IDUi obtains its private key skUi←Extract(msks,IDUi) from TA. Besides, each RSU Ui has to generate their own public parameters PPUi and master key mskUi by running algorithm Setup. For the sake of system security, we require RSU to update its public parameters and master key regularly and share its latest public parameters among all the registered RSUs.Vehicle Setup: vehicle should register itself to local TA via secure network infrastructure as soon as it enters a new TA region. TPD on vehicle is initialized to preload system public parametersPP and all the identities of registered RSUs. Let Vj be a vehicle with identity IDVj. Supposing that Vj randomly picks aj′∈Zq∗ at time tj, then its authentication key is aj=H4(aj′,tj)∈Zq∗. Vehicle Vj computes Hj=H1(IDVj,aj),Aj=g1aj and submits (IDVj,Hj,Aj) to TA. Then, TA picks rj∈Zq∗ and generates challenge Rj←g1rj and dynamic password Pj=Ajrj for Vj. Authentication key aj and challenge Rj are saved in TPD on vehicle Vj. Meanwhile, TA inserts tuple {IDVj,Hj,Aj,rj,Pj,Tj} into list L and tuple {Aj,Pj,Tj} into list Lpub, where Tj is the expiration date of these two tuples. When tuples in both lists have expired, TA forces corresponding vehicles to update their authentication keys.


### 5.3. Mutual Authentication

Mutual authentication between vehicleVj and RSU Ui happens when vehicle Vj is in the transmission range of RSU Ui but does not possess its latest master key. The whole process consists of two stages.R2V authentication: RSUUi broadcasts message (IDUi,PPUi,Ri,Ei,ti,σUi) periodically to authenticate itself to newly entered vehicles, where timestamp ti provides freshness, challenge Ri=g1ri that changes along with ti is used to authenticate vehicle in next stage, element Ei=g2ei is used to negotiate symmetric keys with vehicles (both ri,ei∈Zq∗ are picked by RSU Ui and kept secret), and σUi←Sign(skUi,MR2V) is the signature of MR2V=(IDUi,Ei,ti)∈0,1∗. After receiving the broadcast message, vehicle Vj first checks whether identity IDUi has been preloaded into TPD at setup stage or not. If not, vehicle Vj aborts this authentication; otherwise, it verifies signature σUi by running Verify(PPs,IDUi,MR2V,σUi). If algorithm Verify outputs “reject”, vehicle Vj aborts; otherwise, this authentication succeeds.V2R authentication: to authenticate itself to RSUUi, vehicle Vj has to recover its dynamic password Pj in list L and answer the challenge Ri of RSU Ui with authenticate key aj.(1)
VehicleVj computes Pj=Rjaj and Pi=Riaj. Then, it picks fj∈Zq∗ and computes Fj=g2fj and K=H2(Eifj). Key K is used to encrypt MVR=(Pj,H3(IDUi,Pj,Pi,Fj,tj)) with algorithm Enc, where tj is the timestamp. Let Cj=Enc(K,MVR) be the ciphertext of MVR, vehicle Vj replies to RSU Ui with message (IDUi,Fj,tj,Cj).(2)
RSUUi first computes symmetric key K=H2(Fjei) and decrypts Cj with K. Supposing that MVR′=(Pj′,Pi′,HVR′) is the output of Dec(K,Cj), if HVR′≠H3(IDUi,Pj′,Pi′,Fj,tj), RSU Ui aborts; otherwise, RSU Ui searches list Lpub for tuple A′,P′,T′, where P′=Pj′. If such tuple does not exists or has expired, or more than one tuple is found in list Lpub, RSU Ui aborts; otherwise, it computes Pi′′=A′ri. If Pi′′=Pi′, then vehicle Vj manages to authenticate itself to RSU Ui without revealing its real identity.(3)
RSUUi sends its master key mskUi to vehicle Vj in ciphertext format (IDUi,T~i,t~i,C~i), where T~i is the expiry time of mskUi, t~i is a timestamp, and C~i=Enc(K,MRV), MRV=(mskUi,H3(IDUi,mskUi,T~i,t~i)).(4)
VehicleVj decrypts Ci and gets MRV′=(mskUi′,HRV′). If HRV′≠H3(IDUi,mskUi′,T~i,t~i), vehicle Vj aborts; otherwise, it stores master key mskUi′ into TPD. Note that this master key will be erased automatically at time T~i′.


### 5.4. Pseudo-Identity Generation

In terms of privacy preservation, instead of real identities of vehicles, pseudo-identities are generated by TPD to hide the real-world identities of vehicles. Considering a vehicleVj with real identity IDVj in the transmission range of RSU Ui, we define its pseudo-identity as PIDVj=(S,Π0,Π1)=(g1s,H1(IDVj,aj)Xs,YsZθs), where s∈Zq∗ is randomly picked by TPD and θ=H4(g1s,H1(IDVj,aj)Xs).We remark that the computation of pseudo-identity of vehicleVj can be viewed as encrypting H1(IDVj,aj) using Cramer-Shoup encryption scheme (CS scheme) [26] which is secure against adaptive chosen-ciphertext attack (CCA2 secure). The main advantage of such pseudo-identity is that TA could trace the real identity of vehicle by decrypting pseudo-identity. Besides, the nonmalleability of CS scheme does not allow anyone to derive a new and valid pseudo-identity from given one. Using CS scheme might be time-consuming for devices on vehicle, while this problem can be overcame by preparing sufficient pseudo-identities offline in storage device as the on-board storage capacity of vehicle could be extensive.


### 5.5. Message Signing and Verification

When vehicleVj locates in the region of RSU Ui, before signing message, it first generates the private key pskVj of its pseudo-identity PIDVj with master key mskUi and then signs message m with pskVj and broadcasts (PIDVj,IDUi,m,tj,σVj) to RSUs or vehicles around, where tj is a timestamp and σVj←Sign(pskVj,M), M=(PIDVj,m,tj).Messagem can be verified by running Verify(PPUi,PIDVj,M,σVj). However, for verifier that is not in the region of RSU Ui, it has to request the public parameters PPUi of Ui from nearby RSU. Since IBS scheme IBS supports the batch verification of multiple signatures, the verifier is able to take advantage of this property to improve the performance of message verification.


### 5.6. Vehicle Tracing

Pseudo-identity protects the privacy of vehicles on the one hand and facilitates some malicious vehicles to disseminate bogus information on the other. Thus, it is of importance to track down the real identities of misbehaving vehicles which can only be done by TA. Particularly, letPIDVj be one pseudo-identity of malicious vehicle Vj, TA parses PIDVj into (S,Π0,Π1) and computes θ=H4S,Π0, Π1′=Sy+θz. If Π1′≠Π1, then this pseudo-identity is invalid; otherwise TA computes H=Π0/Sx. If there exists one valid tuple {IDVj,Hj,Aj,rj,Pj,Tj} in list L with Hj=H, then TA succeeds to find out the real identity IDVj of vehicle Vj.


### 5.7. Secret Parameters Update

There are two secret parameters in TPD that need to be updated regularly: authentication key and RSU’s master key. Note that RSU’s master key is updated along with V2R authentication. Here, we focus on authentication key update.(1)
Assuming that tuple{IDVj,Hj,Aj,rj,Pj,Tj} reaches the expiration date Tj, TA generates a pseudo-identity PIDA=(Aj,HjAjx,Ajy+θz) for vehicle Vj, where θ=H4(Aj,HjAjx). Then, TA picks r^,r∗,e∈Zq∗ and computes R^=g1r^,R∗=g1r∗,E=g2e where challenge R^ is a test for target vehicle Vj, R∗ is a new challenge for Vj and E is used to negotiate key. TA then computes signature σA←SignpskA,MTA, where pskA=Extractmsks,PIDA and MTA=(PIDA,R^,R∗,t^) and broadcasts MTA,σA, where t^ is a timestamp.(2)
VehicleV with real identity IDV and authentication key a that receives this message of TA would check whether PIDA=(g1a,H1IDV,aXa,YaZθa), where θ=H4(g1a,H1IDV,aXa). Only Vj that possesses aj can recognize this pseudo-identity. Then, Vj prepares to update authentication key. It runs VerifyPPs,PIDA,MTA,σA. If signature σA is valid and timestamp t^ is fresh, vehicle Vj picks a′,f∈Zq∗ and computes a∗=H4(a′,tj), A∗=g1a∗, H∗=H1(IDVj,a∗), F=g2f, K′=H2Ef, and P^=R^aj. Then, vehicle Vj sends message IDTA,F,tj,Cj to TA, where tj is the timestamp, Cj=EncK′,MU, and MU=(A∗,P^,H3(IDTA,A∗,P^,tj)).(3)
TA recoversK′=H2Fe to decrypt Cj and obtains MU′=(A′,H′,P^′,HU′). If HU′≠H3IDTA,A′,P^′,tj, TA aborts; otherwise, it computes P′=Ajr^. If P^′≠P′, TA aborts; otherwise, vehicle Vj passes the test of TA; then TA computes P∗=(A′)r∗ and updates {IDVj,Aj,Hj,rj,Pj,Tj} with {IDVj,A′,H′,r∗,P∗,T∗} in list L, where T∗ is the expiration time. Also, in list Lpub, tuple {Aj,Pj,Tj} is updated with {A′,P∗,T∗}. TA picks r-∈Zq∗, computes R-=g1r-, P-=(A′)r-, and broadcasts PIDA,R-,P-,t-,σA′, where t- is a timestamp, σA′←SignpskA,M-TA is the signature of M-TA=(PIDA,P-,t-).(4)
VehicleVj checks the integrity and validity of message. If signature σA′ is valid and timestamp t- is fresh, vehicle Vj computes P-′=R-a∗. If P-≠P-′, vehicle Vj aborts; otherwise, current authentication key aj and challenge Rj in TPD are replaced with a∗ and R∗.We remark that the centralized update of authentication key might incur DoS attack against TA. Fortunately, there are several effective ways to cope with such attack. First, TA in reality can provide the update service in parallel mode. That is, multiple servers are deployed to interact with vehicles simultaneously which can alleviate the burden on each server and accelerate the overall efficiency. Besides, since TA is the initiator of update procedure, it is able to adaptively adjust the interval of update according to practical situation without compromising the security of whole system. Also, if TA does not receive the reply of one vehicle within a period of time, it would abort the update process with this vehicle and refuse to interact with it temporarily.


## 5.1. Overview

In initialization phase of our framework, TA generates parameters for the whole system. RSUs and vehicles are allowed to join VANET after registration. For vehicle that drives into a new RSU region, it also needs to conduct mutual authentication with RSU. To conceal the real identity of vehicle from RSU, V2R authentication needs the assistance of a list maintained by TA that consists of authentication-related information of vehicles. If this authentication succeeds, vehicle would receive the master key of RSU and be able to sign messages in pseudo-identities. Only TA can recover the real identity of vehicle from its pseudo-identities. There also is an efficient and secure mechanism of updating secrets (i.e., authentication key of vehicle and master key of RSU) in TPD before adversary has collected sufficient information via side-channel attacks. Notations used in our framework are defined as follows.(i)
IBS=(Setup, Extract, Sign, Verify): an IBS scheme that supports batch verification of multiple signatures.(ii)
SE=(KeyGen, Enc, Dec): a symmetric encryption scheme with message space 0,1∗ and key space K.(iii)
G1,G2: two cyclic groups with prime order q.(iv)
g1,g2: two generators of G1,G2.(v)
H1,H2,H3,H4: four hash functions H1:0,1∗→G1, H2:G2→K, H3:0,1∗→0,1l, and H4:0,1∗→Zq∗.(vi)
IDUi/IDVj: real identity of RSU Ui or vehicle Vj.(vii)
PIDVj: pseudo-identity of vehicle Vj.


## 5.2. System Initialization

In initialization phase, TA generates parameters for the whole system and all the RSUs and vehicles have to register themselves to TA before joining the VANET. Precisely, the system is initialized as follows.TA Setup: TA runs algorithmSetup to generate public parameters PPs and system master key msks. TA also generates two cyclic groups G1,G2with prime order q and picks generators g1∈G1,g2∈G2. Then it picks x,y,z∈Zq∗ and computes X=g1x,Y=g1y,Z=g1z which are used to generate pseudo-identities for vehicle. Hash functions H1:0,1∗→G1, H2:G2→K, H3:0,1∗→0,1l, and H4:0,1∗→Zq∗ are chosen by TA. The system public parameters are PP=(PPs,q,G1,G2,g1,g2,X,Y,Z,H1,H2,H3,H4). TA also maintains a private list L to record authentication information of registered vehicles as well as list Lpub that is only accessible to registered RSUs. The details of these lists are described later.RSU Setup: since TA is the only party that ownsmsks in current system, RSU Ui with identity IDUi obtains its private key skUi←Extract(msks,IDUi) from TA. Besides, each RSU Ui has to generate their own public parameters PPUi and master key mskUi by running algorithm Setup. For the sake of system security, we require RSU to update its public parameters and master key regularly and share its latest public parameters among all the registered RSUs.Vehicle Setup: vehicle should register itself to local TA via secure network infrastructure as soon as it enters a new TA region. TPD on vehicle is initialized to preload system public parametersPP and all the identities of registered RSUs. Let Vj be a vehicle with identity IDVj. Supposing that Vj randomly picks aj′∈Zq∗ at time tj, then its authentication key is aj=H4(aj′,tj)∈Zq∗. Vehicle Vj computes Hj=H1(IDVj,aj),Aj=g1aj and submits (IDVj,Hj,Aj) to TA. Then, TA picks rj∈Zq∗ and generates challenge Rj←g1rj and dynamic password Pj=Ajrj for Vj. Authentication key aj and challenge Rj are saved in TPD on vehicle Vj. Meanwhile, TA inserts tuple {IDVj,Hj,Aj,rj,Pj,Tj} into list L and tuple {Aj,Pj,Tj} into list Lpub, where Tj is the expiration date of these two tuples. When tuples in both lists have expired, TA forces corresponding vehicles to update their authentication keys.


## 5.3. Mutual Authentication

Mutual authentication between vehicleVj and RSU Ui happens when vehicle Vj is in the transmission range of RSU Ui but does not possess its latest master key. The whole process consists of two stages.R2V authentication: RSUUi broadcasts message (IDUi,PPUi,Ri,Ei,ti,σUi) periodically to authenticate itself to newly entered vehicles, where timestamp ti provides freshness, challenge Ri=g1ri that changes along with ti is used to authenticate vehicle in next stage, element Ei=g2ei is used to negotiate symmetric keys with vehicles (both ri,ei∈Zq∗ are picked by RSU Ui and kept secret), and σUi←Sign(skUi,MR2V) is the signature of MR2V=(IDUi,Ei,ti)∈0,1∗. After receiving the broadcast message, vehicle Vj first checks whether identity IDUi has been preloaded into TPD at setup stage or not. If not, vehicle Vj aborts this authentication; otherwise, it verifies signature σUi by running Verify(PPs,IDUi,MR2V,σUi). If algorithm Verify outputs “reject”, vehicle Vj aborts; otherwise, this authentication succeeds.V2R authentication: to authenticate itself to RSUUi, vehicle Vj has to recover its dynamic password Pj in list L and answer the challenge Ri of RSU Ui with authenticate key aj.(1)
VehicleVj computes Pj=Rjaj and Pi=Riaj. Then, it picks fj∈Zq∗ and computes Fj=g2fj and K=H2(Eifj). Key K is used to encrypt MVR=(Pj,H3(IDUi,Pj,Pi,Fj,tj)) with algorithm Enc, where tj is the timestamp. Let Cj=Enc(K,MVR) be the ciphertext of MVR, vehicle Vj replies to RSU Ui with message (IDUi,Fj,tj,Cj).(2)
RSUUi first computes symmetric key K=H2(Fjei) and decrypts Cj with K. Supposing that MVR′=(Pj′,Pi′,HVR′) is the output of Dec(K,Cj), if HVR′≠H3(IDUi,Pj′,Pi′,Fj,tj), RSU Ui aborts; otherwise, RSU Ui searches list Lpub for tuple A′,P′,T′, where P′=Pj′. If such tuple does not exists or has expired, or more than one tuple is found in list Lpub, RSU Ui aborts; otherwise, it computes Pi′′=A′ri. If Pi′′=Pi′, then vehicle Vj manages to authenticate itself to RSU Ui without revealing its real identity.(3)
RSUUi sends its master key mskUi to vehicle Vj in ciphertext format (IDUi,T~i,t~i,C~i), where T~i is the expiry time of mskUi, t~i is a timestamp, and C~i=Enc(K,MRV), MRV=(mskUi,H3(IDUi,mskUi,T~i,t~i)).(4)
VehicleVj decrypts Ci and gets MRV′=(mskUi′,HRV′). If HRV′≠H3(IDUi,mskUi′,T~i,t~i), vehicle Vj aborts; otherwise, it stores master key mskUi′ into TPD. Note that this master key will be erased automatically at time T~i′.


## 5.4. Pseudo-Identity Generation

In terms of privacy preservation, instead of real identities of vehicles, pseudo-identities are generated by TPD to hide the real-world identities of vehicles. Considering a vehicleVj with real identity IDVj in the transmission range of RSU Ui, we define its pseudo-identity as PIDVj=(S,Π0,Π1)=(g1s,H1(IDVj,aj)Xs,YsZθs), where s∈Zq∗ is randomly picked by TPD and θ=H4(g1s,H1(IDVj,aj)Xs).We remark that the computation of pseudo-identity of vehicleVj can be viewed as encrypting H1(IDVj,aj) using Cramer-Shoup encryption scheme (CS scheme) [26] which is secure against adaptive chosen-ciphertext attack (CCA2 secure). The main advantage of such pseudo-identity is that TA could trace the real identity of vehicle by decrypting pseudo-identity. Besides, the nonmalleability of CS scheme does not allow anyone to derive a new and valid pseudo-identity from given one. Using CS scheme might be time-consuming for devices on vehicle, while this problem can be overcame by preparing sufficient pseudo-identities offline in storage device as the on-board storage capacity of vehicle could be extensive.


## 5.5. Message Signing and Verification

When vehicleVj locates in the region of RSU Ui, before signing message, it first generates the private key pskVj of its pseudo-identity PIDVj with master key mskUi and then signs message m with pskVj and broadcasts (PIDVj,IDUi,m,tj,σVj) to RSUs or vehicles around, where tj is a timestamp and σVj←Sign(pskVj,M), M=(PIDVj,m,tj).Messagem can be verified by running Verify(PPUi,PIDVj,M,σVj). However, for verifier that is not in the region of RSU Ui, it has to request the public parameters PPUi of Ui from nearby RSU. Since IBS scheme IBS supports the batch verification of multiple signatures, the verifier is able to take advantage of this property to improve the performance of message verification.


## 5.6. Vehicle Tracing

Pseudo-identity protects the privacy of vehicles on the one hand and facilitates some malicious vehicles to disseminate bogus information on the other. Thus, it is of importance to track down the real identities of misbehaving vehicles which can only be done by TA. Particularly, letPIDVj be one pseudo-identity of malicious vehicle Vj, TA parses PIDVj into (S,Π0,Π1) and computes θ=H4S,Π0, Π1′=Sy+θz. If Π1′≠Π1, then this pseudo-identity is invalid; otherwise TA computes H=Π0/Sx. If there exists one valid tuple {IDVj,Hj,Aj,rj,Pj,Tj} in list L with Hj=H, then TA succeeds to find out the real identity IDVj of vehicle Vj.


## 5.7. Secret Parameters Update

There are two secret parameters in TPD that need to be updated regularly: authentication key and RSU’s master key. Note that RSU’s master key is updated along with V2R authentication. Here, we focus on authentication key update.(1)
Assuming that tuple{IDVj,Hj,Aj,rj,Pj,Tj} reaches the expiration date Tj, TA generates a pseudo-identity PIDA=(Aj,HjAjx,Ajy+θz) for vehicle Vj, where θ=H4(Aj,HjAjx). Then, TA picks r^,r∗,e∈Zq∗ and computes R^=g1r^,R∗=g1r∗,E=g2e where challenge R^ is a test for target vehicle Vj, R∗ is a new challenge for Vj and E is used to negotiate key. TA then computes signature σA←SignpskA,MTA, where pskA=Extractmsks,PIDA and MTA=(PIDA,R^,R∗,t^) and broadcasts MTA,σA, where t^ is a timestamp.(2)
VehicleV with real identity IDV and authentication key a that receives this message of TA would check whether PIDA=(g1a,H1IDV,aXa,YaZθa), where θ=H4(g1a,H1IDV,aXa). Only Vj that possesses aj can recognize this pseudo-identity. Then, Vj prepares to update authentication key. It runs VerifyPPs,PIDA,MTA,σA. If signature σA is valid and timestamp t^ is fresh, vehicle Vj picks a′,f∈Zq∗ and computes a∗=H4(a′,tj), A∗=g1a∗, H∗=H1(IDVj,a∗), F=g2f, K′=H2Ef, and P^=R^aj. Then, vehicle Vj sends message IDTA,F,tj,Cj to TA, where tj is the timestamp, Cj=EncK′,MU, and MU=(A∗,P^,H3(IDTA,A∗,P^,tj)).(3)
TA recoversK′=H2Fe to decrypt Cj and obtains MU′=(A′,H′,P^′,HU′). If HU′≠H3IDTA,A′,P^′,tj, TA aborts; otherwise, it computes P′=Ajr^. If P^′≠P′, TA aborts; otherwise, vehicle Vj passes the test of TA; then TA computes P∗=(A′)r∗ and updates {IDVj,Aj,Hj,rj,Pj,Tj} with {IDVj,A′,H′,r∗,P∗,T∗} in list L, where T∗ is the expiration time. Also, in list Lpub, tuple {Aj,Pj,Tj} is updated with {A′,P∗,T∗}. TA picks r-∈Zq∗, computes R-=g1r-, P-=(A′)r-, and broadcasts PIDA,R-,P-,t-,σA′, where t- is a timestamp, σA′←SignpskA,M-TA is the signature of M-TA=(PIDA,P-,t-).(4)
VehicleVj checks the integrity and validity of message. If signature σA′ is valid and timestamp t- is fresh, vehicle Vj computes P-′=R-a∗. If P-≠P-′, vehicle Vj aborts; otherwise, current authentication key aj and challenge Rj in TPD are replaced with a∗ and R∗.We remark that the centralized update of authentication key might incur DoS attack against TA. Fortunately, there are several effective ways to cope with such attack. First, TA in reality can provide the update service in parallel mode. That is, multiple servers are deployed to interact with vehicles simultaneously which can alleviate the burden on each server and accelerate the overall efficiency. Besides, since TA is the initiator of update procedure, it is able to adaptively adjust the interval of update according to practical situation without compromising the security of whole system. Also, if TA does not receive the reply of one vehicle within a period of time, it would abort the update process with this vehicle and refuse to interact with it temporarily.


## 6. Security Analysis

This section gives a comprehensive security analysis of our framework. We show that our framework has achieved all the security objectives mentioned in Section3.Authentication: one can notice that message authentication is guaranteed by IBS scheme immediately, so we mainly analyze the mutual authentication between vehicle and RSU. In R2V authentication, the generation of signature of broadcasted message needs RSU’s private key which is provided by TA. If received signature can be successfully verified with the identity of RSU, vehicle is convinced that current RSU is the sender of messages from the unforgeability of IBS scheme. In V2R authentication, for vehicle Vj, it proves to RSU that it can recover the dynamic password Pj=Ajrj of tuple {Aj,Pj,Tj} in list Lpub and answer the dynamic password Pi=Ajri which is corresponding to new challenge Ri=g1ri generated by RSU. We claim that given Aj and Ri, other entities that do not possess the authentication key aj or ri picked by RSU cannot compute the correct Pi if CDH problem is hard. Therefore, vehicles that send correct dynamic password pair (Pj,Pi) can authenticate themselves to RSU. Since tuple {Aj,Pj,Tj} and Pi are independent of the real identity of Vj, the whole process of authentication does not leak any information about vehicle’s identity.Nonrepudiation: the pseudo-identity of vehicle, corresponding to private key and signature of message broadcasted by vehicle are all generated in TPD. Since pseudo-identity, signature, and timestamp are key components of message, a vehicle cannot deny its behavior of generating message via TPD at certain time. Moreover, the generation of pseudo-identity requires authentication key aj which is only accessible to vehicle itself. Due to the nonmalleability of CS scheme, we note that one cannot derive a new valid pseudo-identity from given one.Identity privacy preserving: the pseudo-identity of vehicle Vj is a ciphertext of H1(IDVj,aj) in CS scheme. From the security of this encryption scheme, pseudo-identity does not leak any information about vehicle’s real identity. Moreover, the mutual authentication between vehicle and RSU does not leak real identity as well.Conditional Traceability: the process of tracing vehicle has been described in Section 5 already. Only TA that possesses the private key x,y,z is able to verify the validity of pseudo-identity, recover Hj=H1(IDVj,aj), and find the real identity IDVj in private list L.Nonframeability: since vehicle’s authentication key is only accessible to itself, TA cannot authenticate itself to RSU as a valid vehicle and obtain the RSU’s master key, let alone generating the private keys of pseudo-identities and forging the signatures of vehicles. On the other hand, although RSU owns master key, it cannot generate vehicle’s new pseudo-identities and valid signatures as the authentication key is required and collected pseudo-identities do not provide any useful information for pseudo-identity generation. Moreover, although RSU could collect a set of pseudo-identities of vehicles, due to unlinkability, it is impossible for RSU to distinguish certain vehicle’s pseudo-identities and to forge serial signatures of this vehicle. TA is also able to detect the reuse of pseudo-identities by decrypting them and querying recovered hash values in maintained list. If TA does not find them in list, then there exists the abuse of pseudo-identities.Ideal TPD freshness: one can note that secrets in TPD are vehicle’s authentication key and RSU’s master key. TA is responsible for the update of vehicle’s authentication key and RSU would regularly update its master key. Thus, realistic TPD is secure enough to store these secrets and ideal TPD is not needed.Unlinkability: in our framework, all messages of vehicle are signed with different pseudo-identities which are independent from each other. It is impossible to distinguish whether two random messages are sent by one vehicle or not. Thus, our framework satisfies unlinkability.Message confidentiality: in V2R authentication, RSU sends its master key in ciphertext form to vehicles that complete current authentication. The master key of RSU is encrypted using symmetric encryption scheme and the negotiation of symmetric key follows the method of Diffie-Hellman key exchange. Thus, transmission of RSU’s master key is confidential and secure. Similarly, the same symmetric encryption scheme and key exchange method are applied in transmitting new authentication information of vehicle during updating secret parameters.Attacks resistance: In proposed framework, we assume that the whole system is initialized in a secure environment, but mutual authentication, message signing and verification, and secret parameter update might suffer various attacks from adversary. We now demonstrate that our framework is resistant to following attacks.(i)
Replay attack: every transmitted message is marked with timestamp. The receiver of message would check the freshness of message via timestamp and discard replayed messages.(ii)
Impersonation attack: in mutual authentication, adversary might try to imitate a valid RSUUi and gain the trust of vehicles. However, the private key of RSU Ui is generated in initialization phase and securely kept by RSU Ui. Adversary cannot access to this private key. Thus, the signature of its message cannot be verified with the identity of Ui. In secret parameters update, if adversary (e.g., registered vehicles or RSUs) wants to impersonate the TA and send update instruction to vehicle Vj, it has to compute the special pseudo-identity PIDA of Vj with public parameters X,Y,Z. The hardness of computing PIDA=(Aj,HjAjx,Ajy+θz) with Aj and X,Y,Z can be reduced to CDH assumption. One update instruction is targeted at only one vehicle, but other irrelevant vehicles might also receive this instruction. If a malicious vehicle intends to imitate the target one Vj, it has to answer the challenge R^ of TA with dynamic password P^. Given R^ and Aj, it is still hard to compute P^=R^aj=Ajr^ according to CDH assumption. Thus, our framework could withstand impersonation attack.(iii)
Modification attack: for signed message, making any modifications could result in the failure of verification from the correctness of IBS scheme. For encrypted message, the plaintext and its hash value are concatenated and encrypted together. If ciphertext is modified arbitrarily, the underlying plaintext cannot be verified with its hash value.(iv)
Side-channel attack: this attack is mainly for vehicle’s TPD which stores sensitive data including authentication key and master key of RSU. It is worth mentioning that the real identity of vehicle is not stored in TPD. In our protocol, these secret parameters are updated frequently such that adversary cannot obtain sufficient data through side-channel analysis. Moreover, new secret parameters are independent of the old ones, so the leakage of old parameters does not benefit the guessing of new ones.Remarks: it is worth mentioning that Sybil attack is inevitable and ubiquitous in most of cryptographic schemes and thus the detection of such attack has been extensively studied [27]. Our framework is vulnerable to Sybil attack as any authenticated vehicle is accessible to the master key of RSU and can imitate other vehicles at the same time by forging their messages. However, we claim that it is possible to detect such attack by authorities in proposed framework. Precisely, misbehaving vehicle cannot imitate other vehicles as it does not know their authentication keys and cannot generate correct pseudo-identities. Collected pseudo-identities also do not help in computing new ones from the nonmalleability of CS scheme. Besides, the reuse of collected pseudo-identities can be detected by TA. Consequently, only pseudo-identities of misbehaving vehicle itself can be generated to conduct Sybil attack. The TA is able to detect such attack easily by revealing its real identity from pseudo-identities.


## 7. Performance Analysis

In this section, we evaluate both the computation and communication costs of authentication in our framework and make a comparison with existing works. To achieve 80-bit security, elliptic curve groupsG1,G2 with 160-bit prime order q, IBS scheme IBS, and symmetric encryption scheme AES with 80-bit security are used in our protocol. In pairing-based IBS scheme IBS, we use bilinear pairing e:G×G→GT to realize 80-bit security level, where G is an additive group with 160-bit prime order p on supersingular elliptic curve with embedding degree 2. The sizes of elements in G1 and G are 320 bits and 1024 bits. For the convenience of discussion, notations of execution time are defined in Table 1.Table 1
Notations of different execution time.
Notation Description T m Average execution time of multiplication operation on groupG1 or G2. T a Execution time of addition operation on groupG1 or G2. T p Execution time of bilinear pairing operatione(⋅,⋅). T p m Average execution time of multiplication operation on groupG. T p a Execution time of addition operation on groupG. T h Average execution time of general hash operation. T s i g n I B S Execution time of signing message usingIBS scheme. T v r f y I B S Execution time of verifying signature usingIBS scheme. T a e s Execution time of AES encryption / decryption. T q u e r y Execution time of searching list.According to [6], bilinear pairing operation that takes Tp≈4ms is the most time-consuming operation. Other bilinear pairing-related operations cost more time than corresponding operations in ECC. That is, Tpm≈3.9Tm=1.7ms and Tpa≈3.9Ta. The execution time of multiplication operation Tm/Tpm is approximately 240 times greater than Ta/Tpa. In comparison to above execution time, Th, Taes, and Tquery could be negligible.


### 7.1. Comparison of Different IBS Schemes

IBOOS and OT-IBS schemes usually might be more efficient than traditional IBS schemes. In IBOOS scheme, time-consuming operations can be completed in offline stage, and the actual signing time is determined by online stage. The structure of OT-IBS scheme is commonly much simpler than that of traditional IBS scheme because of the one-time usage of private key. Moreover, IBS schemes that support batch verification could amortize time-consuming operation over a bundle of signatures. Therefore, for better performance, we only investigate existing IBOOS and OT-IBS schemes that support batch verification.Table2 shows the comparison of signing time Tsign, verification time Tvrfy, and signature size. One can note that bilinear pairing-based IBS schemes XMS and ZWD are less efficient than ECC-based IBS schemes in both verification time and signature size. Schemes LBZ and HZS have same verification time. However, the signing time of LBZ is correlated with the bit length n of message, so it might be greater than that of HZS for long messages. Moreover, scheme HZS enjoys the shortest signature among these schemes. Thus, in following discussion, we adopt scheme HZS as the IBS scheme in our framework.Table 2
Efficiency of different IBS schemes.
Signature Type Scheme Signing TimeTsign Verification TimeTvrfy Signature Size (bits) IBOOS XMS [28] negligible 2 T p + 2 T p m + T p a 2 G + p ≈ 2208 LBZ [29] n T a 3 T m + 2 T a 2 G 1 + q ≈ 800 OT-IBS HZS [6] T m 3 T m + 2 T a G 1 + q ≈ 480 ZWD [13] T p m + T p a 2 T p + T p m + T p a G + p ≈ 1184


### 7.2. Authentication Efficiency

When evaluating an authentication protocol, we are most concerned about the time and communication costs of authentication. In our framework, vehicle that just enters a new RSU region has to complete the mutual authentication with RSU in time; otherwise it cannot communicate with other entities. Thus, we consider the overhead of mutual authentication from the perspective of vehicle. Since RSU broadcasts messages periodically, it is reasonable to assume that vehicle receives these messages as soon as it drives into the region of RSU. The computational overhead of R2V authentication is mainly determined byTvrfyHZS=3Tm+2Ta. Before replying to RSU, vehicle has to spend time Tgenv=3Tm+2Th+Taes to generate message (IDUi,Fj,tj,Cj). In AES, the size of ciphertext is the same as plaintext, so ciphertext Cj is 320∗2+160=800-bit long. Suppose that the size of identity of RSU IDUi is 160 bits, timestamps are 20 bits, and the length of message (IDUi,Fj,tj,Cj) is 160+320+20+800=1300 bits. Then, RSU spends time Tprocr=2Tm+3Th+2Taes+Tquery to process the message from vehicle and prepare master key for it if authentication succeeds, where Tquery is the execution time of searching list Lpub. The length of message (IDUi,T~i,t~i,C~i) sent by RSU is 160+20+20+(160+160)=520 bits. Vehicle needs time Tdecv=Taes+Th to decrypt it and check the master key of RSU. Therefore, the overall computation overhead of mutual authentication is Tv↔r=TvrfyHZS+Tgenv+Tprocr+Tdecv=8Tm+2Ta+6Th+4Taes+Tquery≈8Tm+2Ta, and the communication overhead is 1300+520=1820 bits.Similarly, we also analyze the efficiency of mutual authentication in existing works. In [7], LBZ scheme is used to sign messages during mutual authentication. Suppose that the sizes of code HR of vehicle’s home region, nonce nc, and join request join are 20 bits and ciphertext Epk of vehicle’s real identity is 320 bits; then the length of vehicle’s pseudo-identity TEpkHR‖IDU is 20+320+20+160=520 bits. Then message (ID,PS,t,join,Sign(PS,t)) sent by vehicle is 160+520+20+20+800=1520 bits. The offline signature of LBZ scheme actually could be preloaded by vehicle, so the message (ID,t,PS,IDr,nc,Sign(IDr,t)) returned from RSU is 160+20+520+160+20+800=1680 bits. The total communication overhead is 3200 bits. The computation overhead is 3TvrfyLBZ+TsignLBZ+T′signLBZ=3∗3Tm+2Ta+540Ta+180Ta, where TsignLBZ is correlated to the length of input.In [13], the computational overhead of protocol is TvrfyZWD+Tgenv+Tprocr+Tdecv=2Tp+6Tpm+Tpa+6Th+4Taes+Tquery≈2Tp+6Tpm+Tpa. Suppose that the length of authentication key λ is 160 bits, element F∈G is 1024 bits, then message (F,ID,C,t) sent by vehicle is 1024+160+(160+20)+20=1384 bits, where C=Enc(λ,t). RSU returns message (H,C′) which is 160+(20+160+160)=500 bits long to vehicle. Since RSU has to forward message sent by vehicle to TA, then the communication overhead is 1384∗2+500=3268 bits.Table3 shows the comparison of computation and communication overhead of mutual authentication between vehicle and RSU, where computation overhead is represented as the multiples of Ta. The improvement on computation is (2886Ta-1920Ta)/2886Ta≈33.5% over [7] and (10300Ta-1920Ta)/10300Ta≈81.4% over [13]. In communication overhead, there are (3200-1820)/3200≈43.1% and (3268-1820)/3268≈44.3% improvements over [7] and [13], respectively.Table 3
Comparison of mutual authentication efficiency.
Mutual Authentication Computation Overhead Communication Overhead (bits) Li et al.[7] 9 T m + 726 T a ≈ 2886 T a 3200 Zhang et al.[13] 2 T p + 6 T p m + T p a ≈ 10300 T a 3268 Our framework 8 T m + 2 T a ≈ 1920 T a 1820


### 7.3. Secret Parameters Update Efficiency

At the beginning of update secret parameters, TA has to compute 3∗320=960-bit long pseudo-identity PIDA first, which costs time 2Tm+Ta and then challenges R^,R∗, element E, and signature SignA. The overall broadcast message is 960+320+320+320+20+480=2420 bits long and TA spends time 2Tm+Ta+3Tm+Tm=6Tm+Ta to generate it.We assume that vehicleVj has computed its PIDA in advance and could recognize the update instruction from TA immediately after receiving the broadcast message. Vehicle Vj first verifies the signature, picks new authentication key, and then responds TA with new authentication information (ID,F,t,C) which is 160+320+20+(320+160+320+160)=1460-bit long. This process would take TvrfyHZS+4Tm+3Th+Taes≈7Tm+2Ta.After receiving the authentication information from vehicleVj, TA needs to spend time Taes+Tm to check its integrity. If received information is complete and valid, TA has to prove to Vj that it possesses the latest information of Vj by broadcasting message PIDA,R-,P-,t,Signwhose length is 960+320+320+20+480=2100 bits. The time of generating message is 2Tm+TsignHZS=3Tm.Finally, vehicleVj takes TvrfyHZS+Tm=4Tm+2Ta to verify the message sent by TA, and the procedure of secret parameters update is finished. Overall, the time cost on the vehicle side is 7Tm+2Ta+4Tm+2Ta=11Tm+4Ta, and 6Tm+Ta+3Tm=9Tm+Ta on the TA side. The communication costs are 1460 bits and 2420+2100=4520 bits for vehicle and TA, respectively.


## 7.1. Comparison of Different IBS Schemes

IBOOS and OT-IBS schemes usually might be more efficient than traditional IBS schemes. In IBOOS scheme, time-consuming operations can be completed in offline stage, and the actual signing time is determined by online stage. The structure of OT-IBS scheme is commonly much simpler than that of traditional IBS scheme because of the one-time usage of private key. Moreover, IBS schemes that support batch verification could amortize time-consuming operation over a bundle of signatures. Therefore, for better performance, we only investigate existing IBOOS and OT-IBS schemes that support batch verification.Table2 shows the comparison of signing time Tsign, verification time Tvrfy, and signature size. One can note that bilinear pairing-based IBS schemes XMS and ZWD are less efficient than ECC-based IBS schemes in both verification time and signature size. Schemes LBZ and HZS have same verification time. However, the signing time of LBZ is correlated with the bit length n of message, so it might be greater than that of HZS for long messages. Moreover, scheme HZS enjoys the shortest signature among these schemes. Thus, in following discussion, we adopt scheme HZS as the IBS scheme in our framework.Table 2
Efficiency of different IBS schemes.
Signature Type Scheme Signing TimeTsign Verification TimeTvrfy Signature Size (bits) IBOOS XMS [28] negligible 2 T p + 2 T p m + T p a 2 G + p ≈ 2208 LBZ [29] n T a 3 T m + 2 T a 2 G 1 + q ≈ 800 OT-IBS HZS [6] T m 3 T m + 2 T a G 1 + q ≈ 480 ZWD [13] T p m + T p a 2 T p + T p m + T p a G + p ≈ 1184


## 7.2. Authentication Efficiency

When evaluating an authentication protocol, we are most concerned about the time and communication costs of authentication. In our framework, vehicle that just enters a new RSU region has to complete the mutual authentication with RSU in time; otherwise it cannot communicate with other entities. Thus, we consider the overhead of mutual authentication from the perspective of vehicle. Since RSU broadcasts messages periodically, it is reasonable to assume that vehicle receives these messages as soon as it drives into the region of RSU. The computational overhead of R2V authentication is mainly determined byTvrfyHZS=3Tm+2Ta. Before replying to RSU, vehicle has to spend time Tgenv=3Tm+2Th+Taes to generate message (IDUi,Fj,tj,Cj). In AES, the size of ciphertext is the same as plaintext, so ciphertext Cj is 320∗2+160=800-bit long. Suppose that the size of identity of RSU IDUi is 160 bits, timestamps are 20 bits, and the length of message (IDUi,Fj,tj,Cj) is 160+320+20+800=1300 bits. Then, RSU spends time Tprocr=2Tm+3Th+2Taes+Tquery to process the message from vehicle and prepare master key for it if authentication succeeds, where Tquery is the execution time of searching list Lpub. The length of message (IDUi,T~i,t~i,C~i) sent by RSU is 160+20+20+(160+160)=520 bits. Vehicle needs time Tdecv=Taes+Th to decrypt it and check the master key of RSU. Therefore, the overall computation overhead of mutual authentication is Tv↔r=TvrfyHZS+Tgenv+Tprocr+Tdecv=8Tm+2Ta+6Th+4Taes+Tquery≈8Tm+2Ta, and the communication overhead is 1300+520=1820 bits.Similarly, we also analyze the efficiency of mutual authentication in existing works. In [7], LBZ scheme is used to sign messages during mutual authentication. Suppose that the sizes of code HR of vehicle’s home region, nonce nc, and join request join are 20 bits and ciphertext Epk of vehicle’s real identity is 320 bits; then the length of vehicle’s pseudo-identity TEpkHR‖IDU is 20+320+20+160=520 bits. Then message (ID,PS,t,join,Sign(PS,t)) sent by vehicle is 160+520+20+20+800=1520 bits. The offline signature of LBZ scheme actually could be preloaded by vehicle, so the message (ID,t,PS,IDr,nc,Sign(IDr,t)) returned from RSU is 160+20+520+160+20+800=1680 bits. The total communication overhead is 3200 bits. The computation overhead is 3TvrfyLBZ+TsignLBZ+T′signLBZ=3∗3Tm+2Ta+540Ta+180Ta, where TsignLBZ is correlated to the length of input.In [13], the computational overhead of protocol is TvrfyZWD+Tgenv+Tprocr+Tdecv=2Tp+6Tpm+Tpa+6Th+4Taes+Tquery≈2Tp+6Tpm+Tpa. Suppose that the length of authentication key λ is 160 bits, element F∈G is 1024 bits, then message (F,ID,C,t) sent by vehicle is 1024+160+(160+20)+20=1384 bits, where C=Enc(λ,t). RSU returns message (H,C′) which is 160+(20+160+160)=500 bits long to vehicle. Since RSU has to forward message sent by vehicle to TA, then the communication overhead is 1384∗2+500=3268 bits.Table3 shows the comparison of computation and communication overhead of mutual authentication between vehicle and RSU, where computation overhead is represented as the multiples of Ta. The improvement on computation is (2886Ta-1920Ta)/2886Ta≈33.5% over [7] and (10300Ta-1920Ta)/10300Ta≈81.4% over [13]. In communication overhead, there are (3200-1820)/3200≈43.1% and (3268-1820)/3268≈44.3% improvements over [7] and [13], respectively.Table 3
Comparison of mutual authentication efficiency.
Mutual Authentication Computation Overhead Communication Overhead (bits) Li et al.[7] 9 T m + 726 T a ≈ 2886 T a 3200 Zhang et al.[13] 2 T p + 6 T p m + T p a ≈ 10300 T a 3268 Our framework 8 T m + 2 T a ≈ 1920 T a 1820


## 7.3. Secret Parameters Update Efficiency

At the beginning of update secret parameters, TA has to compute 3∗320=960-bit long pseudo-identity PIDA first, which costs time 2Tm+Ta and then challenges R^,R∗, element E, and signature SignA. The overall broadcast message is 960+320+320+320+20+480=2420 bits long and TA spends time 2Tm+Ta+3Tm+Tm=6Tm+Ta to generate it.We assume that vehicleVj has computed its PIDA in advance and could recognize the update instruction from TA immediately after receiving the broadcast message. Vehicle Vj first verifies the signature, picks new authentication key, and then responds TA with new authentication information (ID,F,t,C) which is 160+320+20+(320+160+320+160)=1460-bit long. This process would take TvrfyHZS+4Tm+3Th+Taes≈7Tm+2Ta.After receiving the authentication information from vehicleVj, TA needs to spend time Taes+Tm to check its integrity. If received information is complete and valid, TA has to prove to Vj that it possesses the latest information of Vj by broadcasting message PIDA,R-,P-,t,Signwhose length is 960+320+320+20+480=2100 bits. The time of generating message is 2Tm+TsignHZS=3Tm.Finally, vehicleVj takes TvrfyHZS+Tm=4Tm+2Ta to verify the message sent by TA, and the procedure of secret parameters update is finished. Overall, the time cost on the vehicle side is 7Tm+2Ta+4Tm+2Ta=11Tm+4Ta, and 6Tm+Ta+3Tm=9Tm+Ta on the TA side. The communication costs are 1460 bits and 2420+2100=4520 bits for vehicle and TA, respectively.


## 8. Conclusions

In this paper, we propose a practical framework of CPPA scheme that does not rely on ideal TPD and supports realistic TPD. This feature makes our framework more suitable for practical use. In addition to traditional security requirements, such as nonrepudiation and conditional privacy preservation, our framework also achieves nonframeability that prevents TA and RSUs from framing innocent vehicles. Performance analysis shows that our framework outperforms existing schemes in terms of mutual authentication.



---

*Source: 4752612-2019-05-23.xml*