Review on ldentity-Based Batch Verification Schemes for Security and Privacy in VANETs

Eko Fajar Cahyadi | Cahya Damarjati | Min-Shiang Hwang

Abstract—The study of vehicular ad-hoc networks (VANETs) has received significant attention among academia;even so,its security and privacy still become a central issue that is wide-open to discuss.The authentication schemes deployed in VANETs have a substantial impact on its security and privacy.Many researchers have proposed a variety of schemes related to the information verification and efficiency improvement in VANETs.In recent years,many papers have proposed identity-based batch verification (IBV) schemes in regard to diminishing overhead in the message verification process in VANETs.This survey begins with providing background information about VANETs and clarifying its security and privacy,as well as performance requirements that must be satisfied.After presenting an outlook of some relevant surveys of VANETs,a brief review of some IBV schemes published in recent years is conferred.The detailed approach of each scheme,with a comprehensive comparison between them,has been provided afterward.Finally,we summarize those recent studies and possible future improvements.

Index Terms—Efficiency,identity-based batch verification (IBV),security and privacy,survey,vehicular ad-hoc networks (VANETs).

1.lntroduction

Vehicular ad-hoc networks (VANETs) have been attracting many researchers’ attention due to the capability to provide beneficial information among the vehicles and the road environments.This approach aims to improve driving safety.VANETs are loaded with the properties of the intelligent transportation system(ITS),so all of these smart vehicles could communicate with each other via vehicle-to-vehicle (V2V)communications,as well as with the road-side unit (RSU),e.g.,traffic lights or traffic signs,via vehicle-toinfrastructure (V2I) communications[1]-[3].

As shown inFig.1,VANETs are composed by three major components:Trusted authority (TA),RSU,and the on-board unit (OBU).The two-layer VANETs topology concepts have been introduced in [4],and then used by several publications[5]-[9].The top layer consists of TA,while in the lower layer,it comprises RSU and OBU.TA acts as the trust and security management center of the entire VANETs,including registration and certification (public and private key certificates) for RSUs and OBUs when they join the network,and revoking nodes in the case of vehicles broadcasting fraud messages or performing malicious behavior[10]-[13].RSUs are fixed infrastructures located on the roadside at dedicated locations,such as intersections or parking lots,which are fully controlled by TA[14],[15].They act as a bridge between TA and vehicles (OBUs),which are connected to TA by the wire and OBUs by a wireless channel[12].OBU is equipped in every vehicle as a transceiver to communicate with another vehicle’s OBUs (V2V) and RSUs (V2I).It will broadcast information,like the position,speed,and direction to improve the road environment and traffic safety,and create mutual awareness of the vehicles around the local traffic condition[12],[16].In the context of this paper,a tamper-proof device (TPD) is installed in every vehicle’s OBU and it is assumed to be credible and invulnerable against any compromised attempt from the outside.

A series of studies have been done to improve the reliability of VANETs before the public real implementation.To avoid a destructive action of the adversaries,several fundamental issues related to security and privacy in VANETs must be properly addressed.

Fig.1.VANETs topology.

1.1.Security and Privacy

In general,some of the security requirements that should be satisfied in identity-based batch verification(IBV) schemes of VANETs are message authentication,non-repudiation,conditional anonymity,traceability,unlinkability,replaying resistance,and forward and backward security revocation[3],[5],[13],[17].On the other hand,because sensitive personal information of vehicles in the networks is also important to be protected from the adversaries,privacy preservation in VANETs has become the next essential factor to discuss.In VANETs,privacy shares several common requirement cases with security[18],e.g.,anonymity and unlinkability.First,anonymity is needed to protect sensitive information of vehicles,such as the current vehicle location and driver’s licenses.The leak of personal details can cause a dangerous situation for the victims[19].However,the anonymity of the vehicles should be conditional,in a way that the legal authority,that is TA,is able to trace once a dispute occurs[13],[20]-[24].Second,unlinkability is the next privacy-related requirement that is supposed to be satisfied.Unlinkability means that two or more pseudonym messages related to the same vehicle cannot be linked to each other[25].

The following shows the detailed description of security and privacy requirements that must be satisfied in VANETs[5].

1) Message authentication:The implementation of the message authentication method is intended to allow the vehicle or RSU to differentiate the original message from the bogus message.Furthermore,message authentication is also applied to resist the modification and impersonation attacks.

2) Identity privacy-preserving:A sender of a message should be anonymous within a set of potential senders.In IBV,the real identity of the user will be converted to an anonymous identity by the assistance of TPD.Therefore,without knowing the private master key of TPD,an adversary cannot reveal the real identity of the legitimate user.However,to reach accountability,only conditional anonymity is possible in VANETs.Conditional anonymity is also related to traceability due to only TA can trace the user’s real identity.

3) Unlinkability:The adversary vehicles (or RSUs) should not be able to link two or more subsequent pseudonym messages of the same vehicle.

4) Traceability:TA should be able to reveal the real identity from the anonymous identities of the user in the case of a dispute.Traceability is also called conditional anonymity.

5) Non-repudiation:This requirement will give the message receiver a guarantee about integrity and authenticity of information it receives since the sender of the message cannot deny the information it has sent.

6) Replaying attack resistance:The networks could endure passive data capture and its subsequent retransmission of an unauthorized message produced by the adversaries.

7) Impersonation attack resistance:The networks could resist the attacker which tries to assume or impersonate the identities of the legitimate vehicles in VANETs to generate the signature for any messages.

1.2.Relevant Surveys

Several distinctive surveys related to VANETs have been published in the recent years[10],[11],[15],[16],[22],[25]-[35].In general,all of those publications cover the background of VANETs,security and privacy,and the challenges that came after them.Gillaniet al.summarized major security issues,threats,core requirements,and challenges to design a fail-safe security framework in VANETs[28].In 2015,Quet al.provided a review of schemes related to security and privacy in VANETs,which published between 2004 and 2014 extensively,by introducing the basic ideas of most of the security models and classifying them based on their cryptography algorithms[30].In 2015,Petitet al.specifically focused on privacy challenges of V2X communications and reviewed the proposed pseudonym authentication schemes in vehicular networks[16].The most recent survey about VANETs was published in 2019 by Luet al.[10].They offered an excellent overview of security,various authentication schemes for privacy-preserving,and trust management of VANETs.

1.3.lBV

Batch verification is a method for verifying large amounts of digital signatures at once.This verification method can reduce the computational cost compared with one-by-one schemes[36].In the context of VANETs,RSU could communicate with hundreds of OBUs,where each of them sends a safety-related message to RSU every 100 ms to 300 ms[37].Without a batch verification process,a sequentially large number of signatures could take a long period to process,undeniably causing a bottleneck at RSUs.According to [4],if roughly 180 vehicles are kept within the communications range of RSU,and each vehicle is sending a message every 300 ms;this means a verifier (such as RSU) has to verify 600 messages per second.In terms of performance,we compared the computation delay,communications delay,and storage overhead of the schemes under reviewed.

In 2008,Zhanget al.proposed an IBV scheme for vehicular sensor networks[4].This method intends to verify multiple signatures at the same time instead of processing them sequentially.To satisfy the user identity privacy,this scheme generates distinct pseudo identities and the corresponding private keys for signing each message with TPD installed in OBU of each vehicle.Since the IBV scheme adopts identitybased cryptography (IBC)[38],it does not need any signature certificate,such as the public key infrastructure(PKI) and elliptic curve digital signature algorithm (ECDSA) for message authentication;hence,the computation and communications overhead can be low.

In 2011,Zhanget al.published their subsequent work on the basis of their previous IBV scheme[6].As the main reform,they adopted a group testing approach to find a better solution to improve the efficiency of invalid signature identification in a batch verification scheme.When a forged signature is found in the batch,even with a substantial probability,this scheme is expected to take a lower computation cost compared with its counterpart scheme.In the meanwhile,the computation and communications costs of their scheme in the normal condition remain the same as their previous work.

In [7],Lee and Lai tried to point out the vulnerability of Zhanget al.’s[6]scheme.Lee and Lai revealed that Zhanget al.’s scheme suffered from a replaying attack and did not achieve the non-repudiation requirements.Succeeding in addressing the security issue,Lee and Lai also improved the message verification process of Zhanget al.’s scheme.Their approach resulted in a more efficient computation cost of the system.

Several improvement studies towards Lee and Lai’s scheme have been published in the following years[5],[39].In 2015,Bayatet al.revealed that Lee and Lai’s scheme could not hold the impersonation attack[39].The adversaries would generate a valid signature on behalf of the legitimate user.Therefore,they proposed a scheme that tried to improve the security of Lee and Lai’s scheme,despite relatively equal performance was achieved.In 2017,Tzenget al.employed a bilinear pairing IBV scheme[5],trying to improve Lee and Lai’s scheme by revealing its vulnerability towards the identity privacy-preserving attack,the forgery attack,and the anti-traceability attack.It has proven that their scheme is survived against some security and privacy requirements,such as message authentication,identity privacy-preserving,traceability,non-repudiation,unlinkability,and replaying attacks.They also gave a more effective computation and communications delay value compared with any equivalent bilinear IBV schemes.Huet al.made a slight modification of Tzenget al.’s scheme by using a pairing-free IBV scheme to obtain better efficiency in the computational cost[40].However,we will not give further discussion in this paper,since only bilinear pairing-related papers will be considered in the next section.

1.4.Our Contributions

Despite a large number of surveys have been published in recent years,discussing security,privacy preservation,routing protocols,authentication schemes of VANETs,etc.,as the best of our knowledge,there is no comprehensive survey that specifically provides a detail representative approach of bilinear pairing IBV schemes in VANETs.In this paper,we summarize four related articles on the IBV schemes,and provide an outlook in terms of security and privacy,and their performance.Each article published in the subsequent year presents an improvement of the previous related method,and we will give the detail explanation gradually in Sections 2 and 3.Indubitably,each survey has its emphasis and deficiency.Therefore,this work is complementary to the previous surveys mentioned earlier.

For better understanding,the rest of this paper is organized as follows.In Section 2,we cover a detailed review of each representative method in the bilinear pairing IBV scheme.It is followed by a comparison of all surveyed publications in Section 3.Finally,the future outlook is presented in Section 4,while the conclusion is presented in Section 5.

2.Related Work

In this section,we provide a relational approach of several representative publications that have common interest in bilinear pairing IBV schemes for message authentication and verification of VANETs.Four different schemes are explained in detail and described in several phases:The system initialization phase,anonymous identity and signature generation phase,and message verification phase.Notations throughout this paper are represented inTable 1.

Table 1:Notations of this paper

2.1.Bilinear Mapping

DenoteGas a cyclic additive group generated byPandGTas a cyclic multiplicative group with the same prime orderq.Let∶G×G→GTbe a bilinear map if it satisfies the following properties.

AsGis a cyclic additive group generated byP,givenP,aP,bP,cP∈Gwitha,b,c∈Z?qbeing unknown values,CDHP is difficult to solve,because no polynomial time algorithm can discoverabP∈G.

2.2.Zhang et al.’s Scheme

As mentioned in subsection 1.3,in 2008,Zhanget al.proposed another approach based on the bilinear pairing batch verification method to deal with a bottleneck verification issue,known as the IBV scheme[4].Later,their work became a reference to several studies related to the IBV scheme in VANETs.The main feature of IBV schemes is the utilization of anonymous identities and corresponding private keys of the user for signing each traffic-related message.These pseudo identities and user’s private keys are generated by TPD installed in each OBU of the vehicles.TPD is composed of three modules:The authentication module,anonymous identity generation module,and private key generation module,as depicted inFig.2.In 2011,Zhanget al.proposed an improved scheme by adopting a group testing technique to find the invalid signature in the signature batch efficiently,while the rest of the IBV method process remained the same[6].

Fig.2.TPD of Zhang et al.’s scheme.

The concept of the VANETs topology proposed by Zhanget al.is called the two-layer network model.It is comprised of the top layer,where TA is located,and the lower layer that consists of RSU and OBU.All the functions of TA,RSU,and OBU have been discussed in Section 1 and depicted inFig.1.The proposed scheme of Zhanget al.includes system initialization,anonymous identity and signature generation,and message verification phases,which are described as follows.

1) System initialization:In this phase,TA generates the system parameters for each RSU and vehicle.

Step 1:AsPis a generator in the cyclic additive groupGandGTis a cyclic multiplicative group,bothGandGThave the same prime orderq.Afterwards,let∶G×G→GTbe a bilinear map as defined above.

Step 2:TA picks two Hash functions,H∶{0,1}?→Gandh∶{0,1}?→.

Step 3:TA chooses two random numbers {s1,s2}∈as its two private master keys,and calculatesPpub1=s1PandPpub2=s2Pas its two public keys.

Step 4:To activate TPD,TA assigns a unique real identity RID ∈Gand a password PWD for each vehicle.Then each vehicle preloads { RID,PWD,s1,s2} into their TPDs.

Step 5:TA announces the public parameters {G,GT,q,P,Ppub1,Ppub2} to all RSUs and vehicles.

2) Anonymous identity and signature generation:To satisfy the user privacy,TPD of each vehicle will generate the anonymous identity and private key of the vehicle.Then the private key will be used for signing the message.

Step 1:As mentioned before,TPD is comprised of three modules,and the first one is the authentication module.In this module,the vehicleViinputs its real identity R ID and password PWD to TPD.If both R ID and PWD are correct,the authentication module will proceed the request,otherwise refuse.

Step 2:After verifying RID and PWD,the request would follow up to the anonymous identity generation module.TPD will pick a random numberri,and generate an anonymous identity AIDi,where AIDi={AIDi,1,AIDi,2}.Therichanges each time and guarantees the distinction of AIDi,1and AIDi,2.For each AIDi,we have

After the encryption,A IDi,1and A IDi,2are delivered to the private key generation module.

Step 3:Next,in the private key generation module,since an anonymous identity has two parts (A IDi,1and AIDi,2) ,this module is responsible for computing a private key based on AIDi,1and AIDi,2.Thus,the resultant private key S Kialso contains two parts,S Ki={SKi,1,SKi,2},where

Note the anonymous identity A IDiand the private key S Kican be generated offline,so there is no delay for the signing message process.

Step 4:Finally,a vehicle can obtain a list of anonymous identities,AIDi={AIDi,1,AIDi,2},and private keys,SKi={SKi,1,SKi,2}.The output of TPD is { AIDi,SKi}.

Step 5:Each messageMihas to be signed before sent.From the output of TPD,each vehicleViwill calculate the signatureSito signMi.

Step 6:ThenViwill broadcast the final message { AIDi,Mi,Si} to the nearest RSUs.

3) Message verification:The message verification process consists of two versions:Single message verification and batch message verification.

Step 1:When RSU receives a final message {AIDi,Mi,Si} from a vehicle,it will check the message’s signatureSi.

Step 2:In the single message verification,RSU will check { AIDi,Mi,Si} by verifying whether

If (6) is held,then the message is legal and unaltered.

Step 3:In the batch message verification,if RSU receives a number of messages,denoted as{AID1,M1,S1},{AID2,M2,S2},…,{AIDn,Mn,Sn},it can verify the message’s validity simultaneously by the batch message verification.

Step 4:Then RSU starts the batch message verification shown in (17).If (17) is held,then the message is legal and unaltered.

2.3.Lee and Lai’s Scheme

In 2013,Lee and Lai proposed an improved scheme of Zhanget al.’s IBV scheme[7].Lee and Lai described that Zhanget al.’s IBV scheme was vulnerable to the replaying attack and the repudiation attack.First,to overcome the replaying attack,Lee and Lai added a timestampTiin the anonymous identity and signature generation phase.The currentTiis set in the private key generation module in TPD for generating the private key SKi,2,as depicted inFig.3.Subsequently,to achieve non-repudiation,Lee and Lai’s scheme used the random numbervito avoid a malicious user denying the signature by swappingMiandSi.Furthermore,they claimed that their scheme not only could tackle those two flaws,but also achieve traceability and conditional anonymity.In the performance evaluation,Lee and Lai’s scheme also outperformed Zhanget al.’s scheme.And further discussion related to the security and performance of this scheme will be described in Section 3.

Fig.3.TPD of Lee and Lai’s scheme.

The proposed scheme of Lee and Lai includes system initialization,anonymous identity and signature generation,and message verification phases described as follows.

1) System initialization:In this phase,TA generates the system parameters for each RSU and vehicle.Generally,the process in this phase is relatively similar to Zhanget al.’s IBV scheme,except,in Lee and Lai’s scheme,TA picks one more one-way Hash functionh2(?) for private key generation in the next phase.

Step 1:AsPis a generator in the cyclic additive groupGandGTis a cyclic multiplicative group,bothGandGThave the same prime orderq.Afterwards,let∶G×G→GTbe a bilinear map as defined before.

Step 2:TA picks three Hash functions,H∶{0,1}?→G,h∶{0,1}?→,andh2∶{0,1}?→.

Step 3:TA chooses two random numbers {s1,s2}∈as its two private master keys,and calculatesPpub1=s1PandPpub2=s2Pas its two public keys.

Step 4:TA assigns a real identity RID ∈Gand the password PWD for each vehicle.Then each vehicle preloads { RID,PWD,s1,s2} into their TPD.

Step 5:TA announces the public parameters {G,GT,,q,P,Ppub1,Ppub2,H(?),h(?),h2(?)} to all RSUs and vehicles.

2) Anonymous identity and signature generation:As mentioned in the system initialization phase,TA adds one more one-way Hash function,h2(?),andTito be used in the private key S Ki,2generation,instead ofH(?).

Step 1:The process in the authentication module of this phase is the same as Zhanget al.’s TPD.The vehicleViinputs its real identity RID and password PWD to TPD.If both RID and PWD are correct,the authentication module will proceed the request,otherwise refuse.

Step 2:After verifying RID and PWD,the request would be followed up to an anonymous identity generation module.TPD will pick a random numberriand generate the anonymous identity AIDi,where AIDi={AIDi,1,AIDi,2}.Therichanges each time and guarantees the distinction of AIDi,1and AIDi,2for each AIDi.We have

After the encryption,A IDi,1and A IDi,2are delivered to the private key generation module.

Step 3:Next,in the private key generation module,since an anonymous identity has two parts (A IDi,1and AIDi,2) ,this module is responsible for computing a private key based on AIDi,1and AIDi,2.Thus,the resultant private key S Kialso contains two parts,S Ki={SKi,1,SKi,2},where

whereTiis the current timestamp picked by TPD to overcome the replaying attack.

Step 4:Finally,a vehicle can obtain a list of anonymous identities,A IDi={AIDi,1,AIDi,2},and private keys,SKi={SKi,1,SKi,2}.The output of TPD is { AIDi,SKi,Ti}.

Step 5:Each messageMihas to be signed before sent.From the output of TPD,each vehicleViwill calculate the signatureSito signMi:

Step 6:ThenViwill broadcast the final message { AIDi,Mi,Si,Ti} to the nearest RSUs.

3) Message verification:The message verification process consists of two versions:Single message verification and batch message verification.

Step 1:When RSU receives a final message {AIDi,Mi,Si,Ti} from a vehicle,it will check the message’s timestampTi.IfTRSU-Ti≤ΔT,RSU continues the verification process,otherwise rejects the message.TRSUdenotes the received time of the message at RSU,while ΔTdenotes the predefined endurable transmission delay.

Step 2:In the single message verification,RSU checks { AIDi,Mi,Si,Ti} by verifying whether

If (13) is held,then the message is legal and unaltered.

Step 3: In the batch verification,if RSU receives a number of messages denoted as{AID1,M1,S1,T1},{AID2,M2,S2,T2},…,{AIDn,Mn,Sn,Tn},it can verify the message’s validity simultaneously by the batch message verification.Before the process begins,RSU generates a random numbervito ensure the non-repudiation of signatures.The value ofviranges between 1 andx,wherexis a small value and does not make the overhead of computation.

Step 4:Then RSU starts the batch message verification as shown in (14).If (14) is held,then the message is legal and unaltered.

2.4.Bayat et al.’ Scheme

In 2014,Bayatet al.tried to propose an improved scheme of Lee and Lai’s IBV scheme[39].Bayatet al.described Lee and Lai’s scheme suffered from an impersonation attack,where the adversaries could generate a valid signature on behalf of the legitimate user.They claimed that these flaws were coming from the weakness of the private key S Ki,2,so they made some improvements on it.

The proposed scheme by Bayatet al.includes system initialization,anonymous identity and signature generation,and message verification phases,which are described as follows.

1) System initialization:In this phase,TA generates the system parameters for each RSU and vehicle.Bayatet al.implemented a relatively same process in this phase compared with Zhanget al.’s scheme.TA only uses one map-to-point Hash functionH(?) and a one-way Hash functionh(?).

Step 1:AsPis a generator in the cyclic additive groupGandGTis a cyclic multiplicative group,bothGandGThave the same prime orderq.Afterwards,let∶G×G→GTbe a bilinear map as defined before.

Step 2:TA picks two Hash functions,H∶{0,1}?→Gandh∶{0,1}?→.

Step 3:TA chooses two random numbers {s1,s2}∈as its two private master keys,and calculatesPpub1=s1PandPpub2=s2Pas its two public keys.

Step 4:TA assigns a real identity RID ∈Gand a password PWD for each vehicle.Then each vehicle preloads { RID,PWD,s1,s2}.

Step 5:TA announces the public parameters {G,GT,,q,P,Ppub1,Ppub2,H(?),h(?)} to all RSUs and vehicles.

2) Anonymous identity and signature generation:To satisfy the user privacy,TPD of each vehicle will perform the anonymous identity generation and private key generation,as depicted inFig.4.

Fig.4.TPD of Bayat et al.’s scheme.

Step 1:The process in the authentication module of this phase is the same as Zhanget al.’s TPD.The vehicleViinputs its real identity RID and password PWD to TPD.If both RID and PWD are correct,the authentication module will proceed the request,otherwise refuse.

Step 2:After verifying RID and PWD,the request would follow up an anonymous identity generation module.TPD will pick a random numberri,and generate the anonymous identity AIDi,where AIDi={AIDi,1,AIDi,2}.Therichanges each time and guarantees the distinction of AIDi,1and AIDi,2.For each AIDi,we have

After the encryption,A IDi,1and A IDi,2are delivered to the private key generation module.

Step 3:Next,in the private key generation module,since an anonymous identity has two parts (A IDi,1and AIDi,2) ,this module is responsible for computing a private key based on AIDi,1and AIDi,2.Thus,the resultant private key S Kialso contains two parts,S Ki={SKi,1,SKi,2},where

where {A}xis thex-coordinate of the elliptic curve pointA.

Step 4:Finally,a vehicle can obtain a list of anonymous identities,A IDi={AIDi,1,AIDi,2},and private keys,SKi={SKi,1,SKi,2}.The output of TPD is { AIDi,SKi,Ti}.

Step 5:Each messageMihas to be signed before sent.From the output of TPD,each vehicleViwill calculate the signatureSito signMi.

Step 6:ThenViwill broadcast the final message { AIDi,Mi,Si,Ti} to the nearest RSUs.

3) Message verification:The message verification process consists of two versions:Single message verification and batch message verification.

Step 1:When RSU receives a final message {AIDi,Mi,Si,Ti} from a vehicle,it will check the message’s timestampTi.IfTRSU-Ti≤ΔT,RSU continues the verification process,otherwise rejects the message.HereTRSUdenotes the received time of the message at RSU and ΔTdenotes the predefined endurable transmission delay.

Step 2:In the single message verification,RSU checks { AIDi,Mi,Si,Ti} by verifying whether

If (20) is held,then the message is legal and unaltered.

Step 3:In the batch message verification,if RSU receives a number of messages,denoted as{AID1,M1,S1,T1},{AID2,M2,S2,T2},…,{AIDn,Mn,Sn,Tn},it can verify the message’s validity simultaneously by the batch message verification as shown in (21).If (21) is held,then the message is legal and unaltered.

2.5.Tzeng et al.’s Scheme

Recently,Tzenget al.proposed another improved scheme of Lee and Lai’s IBV scheme[5].They described that at least there were three security issues in Lee and Lai’s scheme,e.g.,identity privacy violation,the forgery attack,and the anti-traceability attack.Therefore,their contribution addressed those three flaws by proposing a better scheme that held towards the security requirements,such as message authentication,conditional anonymity,unlinkability,traceability,non-repudiation,and replaying resistance.In addition,the improvement in the computation and communications overhead area was also taken into account.

Similar to [4],[6],[7],and [39],Tzenget al.also employed TPD to satisfy the user privacy,as depicted inFig.5.However,there stand out some differences between Tzenget al.’s and the previous schemes,particularly in the signature generation process.TA in Tzenget al.’s scheme employs one private master keys1,as described in the system initialization phase.Therefore,Tzenget al.’s scheme only has one public keyPpub1=s1P.After the real identity RID of the user and its password PWD are verified in the authentication module,an anonymous identity generation module will calculate AIDi,1and AIDi,2for the user subsequently.Different from Lee and Lai’s scheme,in Tzenget al.’s scheme,AIDican be generated offline to diminish delay in TPD.In the message signing module,Viinputs the messageMito TPD.There is no private key(signing key) SKigeneration process in Tzenget al.’s TPD.The signatureSiofMiis generated right in the message signing module,together with the timestampTi.Therefore,the output of TPD is {AIDi,Mi,Si,Ti}.In the performance evaluation,Tzenget al.’s scheme also can outperform Lee and Lai’s scheme.And further discussion related to security and the performance improvement of this scheme will be detailed in Section 3.

Fig.5.TPD of Tzeng et al.’s scheme.

The proposed scheme of Tzenget al.includes system initialization,anonymous identity and signature generation,and message verification phases,which are described as follows.

1) System initialization:In this phase,TA generates the system parameters for each RSU and vehicle.As an improved scheme of Lee and Lai’s,in this phase Tzenget al.used one map-to-point Hash functionH(?)and a one-way Hash functionh(?),just like Bayatet al.’s scheme.Tzenget al.also added one more generator,so they havePandQas the generators inG.

Step 1:AsPandQare two generators in the cyclic additive groupGandGTis a cyclic multiplicative group,bothGandGThave the same prime orderq.Afterwards,let∶G×G→GTbe a bilinear map as defined before.

Step 2:TA picks two Hash functions:H∶{0,1}?→Gandh∶{0,1}?→

Step 3:TA chooses a random numbers1∈as its private master key and calculatesPpub1=s1Pas its public key.

Step 4:TA assigns a real identity RID ∈Gand a password PWD for each vehicle.Then each vehicle preloads { RID,PWD,s1} into their TPDs.

Step 5:TA announces the public parameters {G,GT,q,,P,Q,Ppub1,H(?),h(?)} to all RSUs and vehicles.

2) Anonymous identity and signature generation:To satisfy the user privacy,TPD of each vehicle performs the anonymous identity generation and signature generation as depicted inFig.5.

Step 1:The process in the authentication module of this phase is the same as Zhanget al.’s TPD.The vehicleViinputs its real identity RID and password PWD to TPD.If both RID and PWD are correct,the authentication module will proceed the request,otherwise refuse.

Step 2:After verifying RID and PWD,the request would follow up the anonymous identity generation module.TPD will pick a random numberri∈,and generate the anonymous identity AIDi,where AIDi={AIDi,1,AIDi,2}.Therichanges each time and guarantees the distinction of AIDi,1and AIDi,2.For each AIDi,we have

After the encryption,A IDi,1and A IDi,2are delivered to the message signing module.

Step 3:Next,Vigenerates and inputs the messageMito the message signing module in TPD.The message signing module generates a current timestampTi,and then computes the signatureSito signMi.

Step 4:Then,Viwill broadcast the final message { AIDi,Mi,Si,Ti} to the nearest RSUs and vehicles.

3) Message verification:The message verification process consists of two versions:Single message verification and batch message verification.

Step 1:When RSU or the vehicle receives a final message {AIDi,Mi,Si,Ti} from a nearby vehicle,it will check the message’s timestampTi.IfTRSU-Ti≤ΔT,RSU continues the verification process,otherwise rejects the message.TRSUdenotes the received time of the message at RSU,while ΔTdenotes the predefined endurable transmission delay.

Step 2:In the single message verification,RSU checks { AIDi,Mi,Si,Ti} by verifying whether

If (25) is held,then the message is legal and unaltered.

Step 3:In the batch message verification,if RSU receives a number of messages,denoted as{AID1,M1,S1,T1},{AID2,M2,S2,T2},…,{AIDn,Mn,Sn,Tn},it can verify the message’s validity simultaneously by the batch message verification.Similar to Lee and Lai’s scheme,before the process begins,RSU generates a random numbervito ensure the non-repudiation of signatures.The value ofviranges between 1 andx,wherexis a small value and does not make the overhead of computation.

Step 4:Then RSU and the vehicle start the batch message verification as shown in (26).

3.Comparison

In this section,we give a detailed evaluation related to the previous four compared schemes.The main attention is focused on the security and performance evaluations of the articles in review.The security requirements have been given in Section 1.Meanwhile,the performance evaluation demonstrates the efficiency of the four proposed schemes based on the simulation results.

3.1.Security Evaluation

We have analyzed all four schemes towards seven security requirements they must hold,including message authentication,identity privacy-preserving,traceability,non-repudiation,unlinkability,replaying attack resistance,and impersonation attack resistance.The results shown inTable 2indicate certain attacks can occur in the particular scheme revealed by the other authors.

Table 2:Security comparison

1) Message authentication: Message authentication is an essential security requirement in VANETs that must be satisfied by all discussed schemes.The message must be authenticated and sent by legitimate entities.In addition,the integrity of the message itself must be granted.All the schemes satisfy this requirement.

2) Identity privacy-preserving:All the schemes claimed that they could hold this requirement.However,Tzenget al.found that Lee and Lai’s scheme suffered from identity privacy violation.The adversaries can reveal the real identities of the vehicles in the target without knowing TA’s private master keys {s1,s2}.Just take it into consideration when there is one malicious vehicle trying to reveal the real identity of another vehicle in the same network.First,the malicious vehicle could fetch the published message{AIDi,Mi,Si,Ti}and public parameters of TA {G,GT,,q,P,Ppub1,Ppub2,H(?),h(?),h2(?)} to calculate the private key S Ki,2of the vehicle in target.By using {AIDi,Ti} from the message and {Ppub2,h2(?)} from public parameters,a malicious vehicle can calculate the private key of the vehicle SKi,2=h2(AIDi,1∣∣AIDi,2∣∣Ti)Ppub2.After confirming SKi,2,another private key SKi,1=Si-h(Mi)SKi,2can be calculated;finally,the real identity RIDi=AIDi,2⊕H(SKi,1) is revealed.Therefore,it is only TA as the only entity that is able to reveal the real identities of any vehicles in the case of a dispute.

4) Non-repudiation:In the non-repudiation requirement,the legitimate vehicle should not be able to deny the message to be sent after TA has revealed it[43].All the schemes claimed that their work can achieve the non-repudiation requirement.However,Lee and Lai proved that Zhanget al.’s cannot hold the task.For instance,one malicious vehicle generates several messages {AID1,M1,S1},{AID2,M2,S2},and{AID3,M3,S3},and swaps the content to {AID1,M1,S3},{AID2,M2,S1},and {AID3,M3,S2}.Despite the fact that the order of the signature is swapped between the messages,their sum through the batch verification process would remain the same as shown in (27).

For this reason,the attackers can deny their signatures.

5) Unlinkability:In this requirement,the attacker should not link any two or more messages to the same sender.All the schemes satisfy this requirement.

6) Replaying attack:Lee and Lai exposed that Zhanget al.’s scheme is vulnerable to the replaying attack,since the message broadcasted by the vehicle only contains {AIDi,Mi,Si} while no timestamp which is commonly used to resist such an attack.By this condition,an adversary can intercept {AIDi,Mi,Si} and resend the message at a future time point to challenge RSU or other vehicles.Therefore,Lee and Lai added a timestampTiin the final message { AIDi,Mi,Si,Ti} to overcome the replaying attack.

For example,the message causes an accident,and then TA will trace and try to reveal the real identity of the sender by calculatingUnfortunately,after RID is found,both TA and RSU assume that the malicious messages are sent by a legitimate vehicleVi,and the actual malicious party who sents those messages can escape.

3.2.Performance Evaluation

In this subsection,we evaluate the computation overhead of one and multiplenmessages from all discussed schemes[5]-[7],[39].The computation cost for signing and verifying one message and multiplenmessages is presented inTable 3.LetTmtpdenote the time of one map-to-point Hash operation,Tmulbe the time of one-point multiplication over an elliptic curve,andTparbe the time to perform one pairing operation,all of the computational costs presented here are directly derived from all of the original publications that are mainly simulated through the 3.0 GHz,Intel Pentium IV engine.

Table 3:Computation overhead comparison

In Zhanget al.’s scheme[6],Tmtp=0.6 ms,Tmul=0.6 ms,andTpar=4.5 ms.The time delay resulted from signing one message andnmessages isTmul=0.6 ms andnTmul=0.6nms,respectively.In the meanwhile,the computation delay for verifying one message andnmessages is 3Tpar+Tmtp+Tmul=14.7 ms and 3Tpar+nTmtp+nTmul=13.5+1.2nms,respectively.

In Lee and Lai’s scheme[7],Tmtp=0.6 ms,Tmul=0.6 ms,andTpar=4.5 ms.The time delay resulted from signing one message andnmessages is 2Tmul=1.2 ms and 2nTmul=1.2nms,respectively.In the meanwhile,the computation delay for verifying one message andnmessages is similar,3Tpar+Tmul=14.1 ms.

In Bayatet al.’s scheme[40],Tmtp=0.11025 ms,Tmul=0.441 ms,andTpar=8.82 ms.The time delay resulted from signing one message andnmessages is not described.In the meanwhile,the computation delay for verifying one message andnmessages is similar,3Tpar+Tmul+Tmtp=27.01125 ms.

Finally,in Tzenget al.’s scheme[5],Tmtp=3.9 ms,Tmul=0.6 ms,andTpar=4.5 ms.The time delay resulted from signing one message andnmessages isTmul=0.6 ms andnTmul=0.6nms,respectively.In the meanwhile,the computation delay for verifying one message andnmessages is similar,2Tpar+Tmul=9.6 ms.

4.Outlook

Even though the IBV schemes can provide an excellent security guarantee,coupled with efficient computation and communications overhead,the future challenge related to more sophisticated attacks could jam the network and slow down the verification time.Future development could be summarized as follows.

4.1.lllegal Signature ldentification

It has been mentioned in subsection 1.3,Zhanget al.[6]employed group testing to improve the ability to find the invalid signature efficiently.In the following years,several other publications[14],[44],[45]also proposed distinctive ideas on this issue.Liet al.[44]proposed a matrix-based mechanism to quickly locate the signatureverification fault without re-verifying each of those signatures.In 2015,Renet al.[45]proposed a cube-based mechanism to locate an illegal signature in the batch messages by employing a 3-dimensional (x-axis,y-axis,andz-axis) plane.The verifier will generate a cube with a facet lengthm,when it receives several pairs of messages (M0,S0),(M1,S1),…,(Mt-1,St-1) from the signer whilem3≥t.In the next step,the verifier will identifytrandom numbersri,whereri∈{i=0,1,…,m3-1},and fill thosetsignatures in them×m×mcube with a coordinate (x,y,z) plane,withri=xm2+ym+zandx,y,z∈{0,1,…,m-1}.Finally,the verifier can batch the three coordinate axes.More detailed explanation refers to [45].

Recently,Luet al.[14]proposed a blockchain anonymous public key infrastructure (PKI)-based reputation system for a hybrid trust model in VANETs.They employed an enhancement of the Merkle tree (the chronological Merkle tree (CMT) and the lexicographical Merkle tree (LMT)) for illegal message identification.CMT was used to validate every transaction and the certificate,while LMT was used for identifying the revoked public key.

From above brief description,we would take a consideration to explore the last two schemes proposed in[14] and [45] in our next project.

4.2.Pairing-Free Operation

As briefly discussed in subsection 1.3,Huet al.[40]proposed an IBV scheme with pairing-free for VANETs by improving Tzenget al.’s scheme[5].Since it did not use the bilinear pairing operation,the computation cost would be much lower.From subsection 3.2,we can see that the pairing operationTparperforms as the most time-consuming cryptographic operation among the others.Gayathriet al.[46]described the elliptic curve cryptography (ECC) with 224-bits key has an equal level of security as 2048-bits key of the RSA cryptosystem.The much smaller size of the key improves the efficiency of computational and communicational overhead,storage capacity,and bandwidth efficiency.As proven in [46],the pairing-free operation also held several security requirements,such as authentication,integrity,privacy,non-repudiation,traceability,anonymity,and revocation.By such promising features,we also would take consideration of this operation in the subsequent development.

5.Conclusion

Security and privacy hold an important role in VANETs infrastructure development.The messages exchange over V2I and V2V communications should be fully granted,otherwise,the users’ information would be in danger.In this paper,we have summarized four IBV scheme-related publications,which are interrelated to each other,and provide an outlook in terms of security and privacy,and performance.Each IBV scheme that has been reviewed in subsections 2.3 to 2.5 has a concern in relation to bilinear pairing utilization.We have shown and compared all the phases including system initialization,anonymous identity and signature generation,and message verification phases,in the same manner.The security and performance evaluation also has been discussed in Section 3.A comprehensive improvement of every article that rectified the previously referenced papers has been provided.

Disclosures

The authors declare no conflicts of interest.