An Enhanced Privacy Preserving，Secure and Efficient Authentication Protocol for VANET

Safiullah Khan，Ali Raza and Seong Oun Hwang

1Department of IT Convergence Engineering，Gachon University，Seongnam，13320，Korea

2ENSAIT，GEMTEX-Laboratoire de Genie et Materiaux Textiles，University of Lille，Lille，F(xiàn)59000，F(xiàn)rance

3School of Computing&Institute of Cyber Security(ICSS)，University of Kent，United Kingdom

4Department of Computer Engineering，Gachon University，Seongnam，13320，Korea

Abstract:Vehicular ad hoc networks(VANETs)have attracted growing interest in both academia and industry because they can provide a viable solution that improves road safety and comfort for travelers on roads.However，wireless communications over open-access environments face many security and privacy issues that may affect deployment of large-scale VANETs.Researchers have proposed different protocols to address security and privacy issues in a VANET， and in this study we cryptanalyze some of the privacy preserving protocols to show that all existing protocols are vulnerable to the Sybil attack.The Sybil attack can be used by malicious actors to create fake identities that impair existing protocols，which allows them to imitate traffic congestion or at worse cause an accident that may result in the loss of human life.This vulnerability exists because those protocols store vehicle identities in an encrypted form， and it is not possible to search over the encrypted identities to find fake vehicles.This attack is serious in nature and very prevalent for privacy-preserving protocols.To cope with this kind of attack，we propose a novel and practical protocol that uses Public key encryption with an equality test(PKEET)to search over the encrypted identities without leaking any information， and eventually eliminate the Sybil attack.The proposed approach improves security and at the same time maintains privacy in VANET.Our performance analysis indicates that the proposed protocol outperforms state-of-the-art protocols:The proposed beacon generation time is constant compared to a linear increase in existing protocols， with beacon verification shown to be faster by 7.908%.Our communicational analysis shows that the proposed protocol with a beacon size of 322 bytes has the least communicational overhead compared to other state-of-the-art protocols.

Keywords: VANET; authentication protocol; cryptanalysis; privacy preserving;intelligent systems

1 Introduction

Vehicular ad hoc networks(VANETs)are a subset of Mobile ad hoc networks(MANETs)in which smart vehicles act as mobile nodes with their movement governed by road topologies.The vehicles communicate with each other using Vehicle-to-vehicle(V2V)communication and with Road-side unit(RSU)， known as Vehicle-to-infrastructure (V2I) communication.Each vehicle is equipped with an On board unit (OBU) that can perform computations and establish communication.A vehicle in a VANET periodically broadcasts messages containing information related to its speed，location，traffic and accidents，known as beacons[1].

Despite these advantages，authentication，security and privacy are critical challenges for VANETs[2].VANETs have an additional number of challenges，particularly in the domain of authentication，privacy and security[3].Unauthenticated information in the network may lead to malicious attacks and service abuses that pose a threat to users [4].In contrast to classical wired networks that have protections in terms of firewalls and gateways，security attacks on such wireless networks could come from various sources to target all nodes [5，6].Additionally， VANETs are an instance of mobile ad hoc networks.Consequently，they inherit all known and unknown security flaws，such as Sybil attacks that are associated with MANETs [7].VANETs are more challenging to secure due to their distinct characteristics and features，such as the high mobility of the end users and wide area of the network[8].Therefore， a new mechanism to provide the desired security， including authentication， integrity，and nonrepudiation，needs to be proposed prior to the practical deployment of VANETs[9].

With regards to issues such as authentication privacy and security， researchers have proposed a number of protocols [10，11].In [10]， the authors proposed a hierarchical privacy preserving pseudonymous authentication protocol for the VANET.Their protocol makes use of two different types of pseudonyms， one is referred to as the primary pseudonym and the second is the secondary pseudonym.A primary pseudonym is provided to a vehicle upon successful verification by the Certification authority(CA).Using this primary pseudonym，the vehicle can request the RSU for a secondary pseudonym that is then broadcast along with the beacons in the VANET.Each pseudonym is associated with an expiration time after which the vehicle has to request new primary and secondary pseudonyms.Primary pseudonyms are associated with a relatively longer expiration time than the secondary pseudonyms.

Furthermore， in [10]， the authors provided a brief security analysis to claim the security of the proposed protocol.Usually， in VANETs (e.g.， in [10，11])， authorities (such as a CA and Social network(SN)，respectively)store the real identities of the vehicles in an encrypted form.Consequently，searching on encrypted data becomes complicated because these authorities are required to first decrypt the encrypted identity prior to searching [12–15] work based on a fully trusted authority.If the trusted authority is compromised， these protocols do not provide security and privacy.We need protocols which can provide privacy even if partially/fully trusted authorities are compromised.Sometimes in an Internet of things(IoT)era(e.g.，Internet of vehicles(IoV)，smart grids，healthcare，etc.)we need a balance between user privacy and access to information by authorities(CA and SN).Searchable encryption is a cryptographic scheme that provides this kind of balance[16–22].Public key encryption with equality test(PKEET)is a special type of searchable encryption scheme[23]，with a kind of Public key encryption(PKE)that allows to check whether two ciphertexts are encrypted under(possibly)different public keys contain the same message.In other words，searchable encryption is a positive way to protect users’sensitive data，while preserving search ability on the server side.It allows the server to search encrypted data without leaking any information in plaintext data.For more indepth information about searchable encryption，readers are encouraged to read[24].

We have surveyed many VANET related protocols and classify them into two categories.The protocols in the first category do not encrypt the real identities of vehicles，including[25，26]，which can reveal information about the vehicle’s daily route.Therefore，they do not provide privacy preservation.The protocols in the second category encrypt the real identities in order to preserve the privacy of the vehicles，which is more desirable for state-of-the-art methods.However，we found that a number of existing protocols including [10，11] in the second category are vulnerable to the Sybil attack since the identities are encrypted and cannot be verified.Thus， a malicious vehicle can create many fake identities， exploiting this vulnerability which may result in fake congestion in the network and subsequently cause serious accidents.To address this problem，we present a novel privacy-preserving protocol secure against the Sybil attack with practical performance.Therefore， this paper not only shows that the protocols are vulnerable against the Sybil attack， but also provides a novel protocol with stronger security along with efficient authentication，beacon generation and beacon verification.In addition，other parameters for the proposed algorithm like the transmit power and scheduling are based on adaptive-transmit power control algorithm[27]，while radio resource allocation is performed using a supervised deep learning technique[28].

The contributions of this paper can be summarized as follows:

1.In this paper， we cryptanalyze existing protocols that protect privacy by encrypting vehicles’real identities and are claimed to be secure and efficient protocols for VANETs.We show for the first time that they are vulnerable to the Sybil attack because they cannot verify the vehicle identity during primary pseudonym generation， which is encrypted.This attack may result in fake congestion in the network and subsequently cause catastrophic consequences， which should be resolved.However， protecting such protocols from the Sybil attack is complicated in nature because the vehicle identities in the existing protocols such as[10，11]are encrypted to protect user privacy.It is difficult to protect both user privacy and security against the Sybil attack at the same time.Hence，we present a new research direction when designing a secure and privacy-preserving protocol for VANET.

2.We propose a novel privacy-preserving protocol secure against the Sybil attack by introducing searchable encryption that allows for verification of encrypted vehicle identities.This proposed method is generic in the sense that it can be applied to all protocols vulnerable to the Sybil attack due to encrypted vehicle identities.We examine various attack scenarios and prove that the proposed protocol is secure against the Sybil attack along with satisfying the general security requirements for VANET protocols.

3.We also perform an in-depth analysis of the proposed protocol in terms of the performance over time.The proposed beacon generation has constant time with an increasing number of beacons， in contrast to the linearly increasing time for existing protocols.Regarding beacon verification time，it outperforms existing protocols by 7.908%.We also show that the proposed protocol with a beacon size of 322 bytes has the least communicational over-head compared to other state-of-the-art protocols.The proposed protocol shows its practical applicability in VANET as the beacons are generated and verified on a massive scale.

The rest of the paper is organized as follows:The background and relevant studies are introduced in Section 2.A cryptanalysis of the existing protocols is provided in Section 3.Section 4 defines the proposed protocol.Section 5 presents the analysis of the proposed protocol.Section 6 concludes the paper.

2 Background

In this section，we present background knowledge on a conventional VANET architecture as well as the assumptions and cryptographic tools used in this work.

2.1 Conventional VANET Architecture

Fig.1 depicts a conventional VANET architecture，where a vehicle first needs to be registered with the Registration authority(RA)in order to receive and send the beacons in the VANET.According to [29]， each vehicle has a unique identifier associated with it.In this paper， we refer to it asVIDi.VIDi，is an electronic license plate，and can be issued and installed in the vehicle’s OBU by the vehicle registration authorities.VIDiserves as a real identity of a vehicle and uniquely identifies it.A vehicle in our model is required to provideVIDito RA for registration.Our system model consists of the following participants.

1.Registration authority(RA):During the registration，RA generates a public/private key pair using PKEET[30]and encrypts theVIDiwith a public key and sends the encryptedVIDito the initial vehicle(Vi)and a trapdoor T to CA through a secure channel.Upon the request of legal authorities，RA provides the decryption key to reveal theVIDi.

2.Certification authority (CA):CA issues the primary pseudonyms and keeps associations between the encryptedVIDiand the primary pseudonym.Each primary pseudonym has an expiration time(TCA)， after which a vehicle needs to get a new primary pseudonym.This can be done by two means:first by requesting through the RSU located in the area where the vehicle is currently traveling and the other by directly requesting it to CA through 3G/4G communication.

3.Roadside units (RSUs):Secondary pseudonyms are issued by RSU upon request from a vehicle.RSU maintains the association between the primary pseudonyms and secondary pseudonyms.Upon the request of secondary pseudonyms， RSU checks the validation of primary pseudonyms and issues the secondary pseudonyms if they are valid.Each secondary pseudonym has an expiration time(TRSU)relatively smaller thanTCA.OnceTRSUexpires，the vehicle needs to acquire a new secondary pseudonym from RSU.

4.Sender/Initial vehicle:The sender vehicle，denoted byViin the rest of the paper，generates the beacons and broadcasts them.

5.Receiver vehicle:The receiver vehicle，denoted byVrin the rest of the paper，verifies the received beacon.In case the message is forged，it reports this message to RSU.IfTRSUexpires，the beacon is discarded.

2.2 Assumptions

We have made a number of assumptions that underpin the cryptanalysis and the proposed protocol，and these are outlined next.

1.An honest but curious behavior is expected from CA，RA，and RSU.

2.We assume that CA，RA，and RSU do not collude.

3.Cryptographic credentials are kept safe by all parties.

4.All parties have synchronized clocks.

5.CA，RA，and RSU use a secure channel to communicate.

Figure 1:Conventional VANET architecture

2.3 Cryptographic Tools

Elliptic curve cryptography (ECC) is one of the most used cryptographic schemes in security because it provides a high level of security and efficiency.However， it doesn’t provide search over encrypted data，which is sometimes required.To provide search over encrypted data，researchers have proposed schemes like PKEET.Therefore，we use two different cryptographic schemes.We use PKEET if there is need to search over encrypted data， and we use ECC if there is no need to search over encrypted data，because it is computationally efficient compared to PKEET.Each of the cryptographic schemes is given as follows:

1.Elliptic curve cryptography (ECC):ECC [31，32] is widely used to implement encryption algorithms and digital signatures.Assume thatFpis a finite field wherepis a large prime number.Edenotes an elliptic curve overFpand it is defined by the following equation.

Here，(4a3+27b2)mod p≠ 0 andx，y，a，b ε Fp.Let us suppose thatObe an infinite point，Gbe an additive group with orderqand generatorp.LetPandQbe two points onE;then point addition operation inGis defined asP+Q=R.The Elliptic curve discrete logarithmic problem(ECDLP)[33]is computationally infeasible.Scalar multiplication inGis given by the following equation.

Given the pointsPandQfromG，ECDLP is to finds ε Fpsuch thats.P=Q.ECC consists of the following algorithms:

a)Setup(π):It takes security parameterπas input and outputs the public parameter

b)KeyGen(pp):It takes the public parameterppas input，and outputs a public/secret key pair(Pk，Sk).

c)Encrypt(m，Pk):It takes a messagemand the receiver’s public keyPkas input and outputs a ciphertextC.

d)Decrypt(C，Sk):It takes a ciphertextCand the receiver’s secret keySkas input and outputs a plaintextm.

e)Signature Generation(C，Sk):It takes a ciphertextCand the sender’s secret keySkas input and outputs a signatures.

f)Signature Verification(s，Sk):It takes a signaturesand the sender’s public keyPkas input and outputs 1 if the signaturesis true otherwise 0.

Although the complete description of these modules is out of the scope of this paper，interested readers are encouraged to read[34]for more information about these modules.

2.Public key encryption with equality test (PKEET):This is a special type of searchable encryption scheme that allows checking whether two ciphertexts encrypted under (possibly)different public keys contain the same message or not.The scheme in[23]does not provide a trapdoor for authorization to perform an equality test.Later，Ma et al.[30]proposed a variant of PKEET with different authorization methods that provide more control to the user over authorization.It consists of the following algorithms:

a)Setup(λ):It takes security parameterλas input and outputs the public parameterpp.

b)KeyGen(pp):It takes the public parameterppas input and outputs a public/secret key pair(Pk，Sk).

c)Encrypt (M， Pk):It takes a messageMand the receiver’s public keyPkas input and outputs a ciphertextC.

d)Decrypt (C， Sk):It takes a ciphertextCand the receiver’s secret keySkas input and outputs a plaintextM.

e)Aut1(SKi):It takes the secret keySKias input and outputs a trapdoorT1，ifor userUi.

f)Test1(Ci，T1，i，Cj，T1，j):It takesUi’s ciphertextCi，the trapdoorT1，i，Uj’s ciphertextCjand the trapdoorT1，jas inputs， and outputs 1 ifCiandCjcontain the same message and 0 otherwise.

Note that[30]is only used by RA and CA in our scheme.

2.4 Security and Privacy Requirements

Both security and privacy are important for secure communications in VANETs.According to the latest research efforts[35–38]，a scheme for VANET should meet the following requirements:

1.Message authentication:RSUs are able to check the validity of the messages sent by vehicles.In addition，RSUs are able to detect any modification of the received message.

2.Privacy preservation:RSUs and other vehicles are not able to extract the vehicle’s real identity.Any third party is not able to get the vehicle’s real identity by analyzing intercepted messages.

3.Traceability/Vehicle revocation:The protocol is able to extract the vehicle’s real identity by analyzing its messages when it is necessary.e.g.，when a malicious vehicle sends a false or forged message to mislead others.

4.Un-linkability:RSUs and malicious vehicles are not able to link two messages sent by the same vehicle，i.e.，they cannot trace the vehicle’s action through its messages.

5.Resistance to attacks:The scheme is able to withstand various common attacks such as the Sybil attack that exist in VANETs.

3 Cryptanalysis

In this section，we cryptanalyze and demonstrate with an example how to mount the Sybil attack in one of the state-of-the-art protocols [10]， because in a VANET， Sybil attacks are very important to address.In the Sybil attack，the attacker subverts the reputation of a network service by creating a large number of pseudonymous identities and uses them to gain a disproportionately large influence.For an easy explanation，we assume the following scenario from[10](The complete description of[10]is out of the scope of this research article.However，we encourage interested readers to read[10，11]to completely understand the attack).Let us suppose that in the step of primary pseudonym generation in[10]，a malicious(internal)initial vehicleViwants to authenticate a fake vehicleVf.Vigenerates two random numbersn， n’， public/private ECC key pairsPKi/SKiandPKi’/SKi’.Visends the information along withVIDitoCAin the following two steps.

Step 1:Vi→CA:n||PKi||VIDi.

RA generates a number of public/private ECC key pairs and provides CA the public keys that are later used by CA forVIDiencryption.CA validates theVIDi.Upon verification，it encryptsVIDiwith one of the public keys of RA.CA encryptsnwith its paillier homomorphic encryption public key PKCAP，generates an expiration time TCA and creates the following database entries as shown in Tab.1.

Table 1:Examples of the CA database with attack scenario in[10]

CA signs(TCA||PKi||(n)PKCAP)and assigns it toVias its primary pseudonym.Note that CA hasVIDiin encrypted form using RA’s public key.Hence，CA cannot seeVIDionce encrypted(until RA provides the corresponding private key).NowViagain sendsn’，PKi’，andVIDitoCAin order to get another valid primary pseudonym.

Step 2:Vi→CA:n`||PKi`||VIDi.

CA validatesVIDi.CA can not check whetherVIDiis already in its database or not becauseVIDiis in encrypted form in its database.Upon verification， it encryptsVIDiwith one of the public keys generated by RA，encryptsn’with its Paillier public keyPKCAP，generates an expiration timeT’CAand creates the following database entries as shown in Tab.2.

Table 2:Examples of the CA database with attack scenario in[10]

CA signs(T’CA||PK’i||(n)’PKCAP) and assigns it toVias its primary pseudonym.Hence，Vihas successfully obtained two valid primary pseudonyms at a time.Vican give one of its primary pseudonyms toVf.Using this primary pseudonym，Vfcan obtain a secondary pseudonym and can communicate in the network.Vican create many numbers of such fake authenticated vehicles in the network and can cause fake congestion.The Sybil attack is shown in Fig.2.

Figure 2:Demonstration of sybil attack in[10]

4 Proposed Protocol

In this section， we propose a new protocol that uses PKEET to eliminate the Sybil attack.The proposed protocol provides improved efficiency，security and maintains privacy in the VANET.The dynamic network architecture of the proposed protocol is shown in Fig.3 and the protocol is given as follows:

4.1 Off-line Registration and Initialization

At the time of offline registration， CA broadcasts security parameters.Each entity creates its public/private key pairs using ECC.In the case of RA， it also creates public/private key pairs using PKEET.Vicontacts RA with itsVIDiand public keyPKithrough a secure channel(e.g.，by physically visiting).RA uses (PKEET) [30] to encrypt and sign theVIDiand gives it toVi.Furthermore， RA gives the trapdoorTof its private keyPKRAto CA through a secure channel(Note that，in[10，11]，RA gives just its public keys to CA and SN，respectively).We use PKEET in[30]，which allows to stop the Sybil attack by using the equality test.

Step 1:Vi→RA:VIDi||PKi.

Step 2:RA→Vi:(PKEET(VIDi)PKRA)SKRA.

Step 3:RA→CA:T.

Figure 3:Working of proposed protocol

4.2 Primary Pseudonym Generation

Visigns(PKEET(VIDi)PKRA)SKRA||PKiusing its private keySKiand encrypts it using CA’s public keyPKCAand sends it to CA to get a primary pseudonym for the first time(i.e.，initially but only once).

Step 4:Vi→(((PKEET(VIDi)PKRA)SKRA||PKi)SKi)PKCK.

CA verifies the signature of RA and checks using the equality test function whetherPKEET(VIDi)PKRAexists in its database or not.If it does not exist，then CA issues the primary pseudonym(TCA||PKi)SKCKand stores it in its database as shown in Tab.3.

CA encrypts(TCA||PKi)SKCKusingPKiand sends it toVi.

Step 5:CA→Vi:((TCA||PKi)SKCK)PKi.

Table 3:Example of the CA database in the proposed protocol

4.3 Secondary Pseudonym Generation

Videcrypts the primary pseudonym，generates a random numberrand a new public/private key pairPk’i，Sk’i，and then concatenatesrandPk’iwith the primary pseudonym.Thereafter，Visigns it usingSKi，encrypts it using the public keyPKRSUof RSU and sends it to RSU.

Step 6:Vi→RSU:(((TCA||PKi)SKCK||r||Pk’i)SKi)PKRSU.

RSU decrypts(((TCA||PKi)SKCK||r||Pk’i)SKi)PKRSUand verifies the signaturesSKCAandSKi.IfTCAis valid，RSU generates a secondary pseudonymSs=(TRSU||PK’i)and signs it using its private keySKRSU.RSU also computesZ=Ss+rand signs it usingSKRSU.RSU sends((Ss)SKRSU)，((Z)SKRSU)by encrypting it usingPK’itoVi.RSU maintains its database as shown in Tab.4.

Step 7:RSU→Vi:((Ss)SKRSU，((Z)SKRSU)PK’i.

Table 4:Example of the RSU database in the proposed protocol

4.4 Beacon Generation

Vicomputesh1=H(Ss+r+m+TRSU)，wheremis a beacon message andHis a hash function.Vithen sends(h1，m，(Z)SKRSU，TRSU)toVr.

Step 8:Vi←Vr:(h1，m，(Z)SKRSU，TRSU).

4.5 Beacon Verification

Vrchecks ifTRSUis valid.If it is valid，Vrverifies the signatureSKRSUand computeshx=H(Z+m+TRSU).Ifh1=hx，Vr accepts the beacon.Otherwise it rejects the beacon.

4.6 Renewal of Primary Pseudonym

Once theTCAexpires，Virequests CA via 3G/4G communication or RSU for a new primary pseudonym.Vigenerates a new public/private key pairPK’’i/SK’’i，concatenatesPK’’iwith its current primary pseudonym， signs it using currentPKi， encrypts it usingPKCAand sends it toCA.CAgenerates a new primary pseudonym usingPK’’iand new expiration timeT’CAand signs it usingSKCA.CAencrypts it usingPK’’iand sends the new primary pseudonym toVi.CAthen updates the corresponding primary pseudonym with a new primary pseudonym in its database.

Vi→CA:(((TCA||PKi)SKCK||PK’’i)SKi)PKCA.

CA→Vi:(((T’CA)||PK’’i)SKCK)PK’’i.

4.7 Renewal of Secondary Pseudonym

To renew a secondary pseudonym，once theTRSUexpires，Vigenerates a new public/private key pairPK’’’i/SK’’’iand a random numberr’.Vithen concatenatesPK’’’iandr’with its current secondary pseudonym and signs it using the currentPK’i.Vithen encrypts them usingPKRSUand sends them to RSU.RSU checks the signaturesSKRSUandSK’i.RSU creates a new secondary pseudonym with new expiration timeTRSU’.RSU generatesZ’=Ss’+r’，whereSs’=(TRSU’||PKi’’’).RSU signsZ’andSs’usingSKRSU.RSU then sends the signedZ’andSs’toViby encrypting them usingPKi’’’.RSU updates the corresponding secondary pseudonym in its database with the new one.The optimal time to refresh the secondary pseudonym is 1.4 s，which means that eachVirequests for secondary pseudonym after approximately 7 beacons.In caseVitries to use expired secondary pseudonym，it will not be accepted by RSU as all the entities are synchronized.Thus，the vehicle using the expired secondary pseudonym will not be able to communicate.

5 Analysis of Proposed Protocol

This section provides an analysis of our protocol with two perspectives.First is the security analysis，where we provide various attack scenarios and explain the resilience of our protocol against those attacks to show the effectiveness of the protocol in accordance with the design goals.Next，we provide the computational and communicational efficiency in form of the computational time and communicational bytes required for beacon generation and verification.

5.1 Security Analysis

1.Message Integrity:The receiving vehicles ensure the integrity of the received message by verifying the signature of the RSU and comparingh1andhx.

2.Vehicle Authentication:VrauthenticatesViby verifying the signature of RSU in secondary pseudonym and validity ofTRSU.

3.Non-repudiation:Vibroadcasts the beacons by computingh1usingr(which is only known toVi)with its secondary pseudonym，mandTRSU.Hence it provides non repudiation.TRSUis valid for very short time.Therefore，each beacon is unique itself and it also prevents the replay attack and keeps the vehicle anonymous.

4.Privacy Preserving:The primary pseudonym and secondary pseudonym are changing very often，which makes it very difficult to track a particular device.Even if RA，CA，or RSU are compromised，the privacy of the vehicles remains secure.

5.Vehicle Revocation:IfViis involved in a malicious activity，Vrreports it to the RSU with its secondary pseudonym.RSU blocks the malicious vehicle and sends it primary pseudonym to CA which also blocks it and reports it to RA.Then RA can reveal its real identity by sharing the respective private key of PKEET with CA.Thus，the offender’s vehicle is revoked.

6.Conditional Anonymity:The real identity of the offender vehicle in our scheme is traced and revoked from the VANET when malicious activities are detected，as described above.

5.2 Attack Scenarios

We show how the proposed protocol defends against the following attack scenarios.

Theorem 1:Sybil attack is not feasible in the proposed protocol.

Proof:IfVitries to get another primary pseudonym by the Sybil attack， CA will check ifPKEET(VIDi)PKRAexists in its database or not by using the equality test.If it exists， CA will not issue the primary pseudonym.Hence，the Sybil attack is not feasible.

Theorem 2:Communication between all the participants is secure.

Proof:All the communication in our protocol is encrypted using ECC cryptography.According to the Diffie-Hellman Problem，given an elementhand the valuehx，it is computationally infeasible for an attacker to compute secret x.Therefore，all the communication is secure.

Theorem 3:Vr cannot correlate the secondary pseudonyms of Vi.

Proof:Vichanges the secondary pseudonyms after a few beacon broadcasts.Thereafter，Vrreceives the beacons containing different secondary pseudonyms.Therefore，it is very hard for aVrto establish any correlation between rapidly changing secondary pseudonyms.

Theorem 4:If an attacker succeeds in compromising RSU，no valuable information is leaked.

Proof:RSU only stores the mapping between the current primary pseudonym and secondary pseudonym.The primary pseudonyms are changed after a short period of time.Therefore，it is very hard for an attacker to get any useful information by compromising any of the RSUs.

Theorem 5:If an attacker succeeds in compromising the CA database， no valuable information is leaked.

Proof:Since the database of CA contains encrypted VIDs of vehicles，no valuable information is leaked even though CA is compromised.

Theorem 6:Even if an RSU tries to correlate the pseudonyms of an initiator.it hardly establishes the linkability between them.

Proof:RSUs only issue secondary pseudonyms on the basis of a primary pseudonym.An initiator only uses a primary pseudonym for a short period of time，after which it securely gets another primary pseudonym from CA without the knowledge of RSU.It is，therefore，very hard for the RSU to establish any link between two primary pseudonyms.

If any vehicle is involved in malicious activity，the malicious participant can be reported to RSU with its secondary pseudonym.RSU can then report it to the CA which will further cooperate with RA to get the associated encryption key for primary pseudonym.Thereafter， they can revoke/track the malicious participant using its ID in primary pseudonym.

Tab.5 shows the comparison of the proposed solution with[10，11].We observed that the protocols in[10，11]are vulnerable to the Sybil attack.However，the proposed solution in this study is resistant to against the possible Sybil attack.If CA and SN are compromised in[10，11]，respectively，they do not provide privacy preservation becauseVisends itsVIDiin plaintext.In the proposed solution，since CA is given an encrypted form ofVIDi， a compromised CA cannot leak any valuable information regardingVIDi.

Table 5:Comparison with[10，11]

5.3 Performance Evaluation

We evaluate the performance of our proposed scheme using our testbed.Our testbed includes an Intel i5 processor with 8 GB of RAM and the computation is carried in a C++，as C++supports a rich set of cryptographic libraries[39].Execution time for the cryptographic operations is given in Tab.6.We compare the computational overhead for generation and verification of broadcasted beacons in[10，11]with our proposed protocol.

Table 6:Execution time and descriptions of cryptographic operations

Beacon generation:In Fig.4a， it is evident that the proposed protocol outperforms others in terms of beacon generation.For beacon generation， [10] computes one signature， so the total time required for beacon generation is 1.88 ms，whereas[11]computes one signature，one AES encryption，and one ECC key generation.Hence，the total time required for beacon generation is 1.88+0.357+2≈4.237 ms.For beacon generation，the proposed protocol only computes one hash(H)，so the total time required is 0.0001 ms.Hence，the proposed protocol is the most efficient in beacon generation，taking almost constant time， which means that， unlike [10，11]， the time for beacon generation does not increase linearly with an increase in the number of beacons generated because the proposed method uses only one hash for beacon generation whereas others use signature verification along with encryption，which are computationally inefficient.

Beacon verification:For beacon verification， as shown in Fig.4b， [10] computes two signature verifications，so the total time required for beacon verification is 2.946+2.946 ≈5.892 ms，whereas[11] computes one signature verification and one AES decryption for beacon verification， hence the time required for beacon verification is 2.946+0.253 ≈3.199 ms.For beacon verification， the proposed protocol computes one hash and one signature verification， so the total time required for message verification is 2.946+0.0001 ≈2.9461 ms.The proposed protocol provides 7.908% faster time for beacon verification compared to [11]， because the proposed protocol uses hash which is computationally efficient compared to AES decryption in[11].

5.4 Communication Overhead

In this section，we evaluate and compare the size of beacons and show that the proposed protocol has the most efficient communicational overhead.Description of size for each element in a beacon is given in Tab.7.The the size of beacon in the proposed protocol is 322 bytes，whereas the size of beacon in [10，11] is 362 and 364 respectively， as shown in Tab.8.Hence the proposed protocoloutperforms others in terms of communicational overhead.

Figure 4:Computational overhead for:(a)beacon generation，(b)beacon verification

Table 7:Size of elements

The corresponding hardware implementations for this protocol consist of hash function for the beacon generation， and hash function and signature verification for beacon verification.The associated hardware requirements can be accomplished using one hash;the light weight hash function as implemented in [40] can serve as the best option for this case in FPGA platform.Similarly for the signature verification case，the ECC can be employed，where the efficient implementations can be found in[32].Later，we intend to design the whole protocol in hardware that can utilize the resource sharing techniques for the efficient implementation of the protocol.

Table 8:Communicational overhead comparison

6 Conclusions and Future Work

In this paper， our cryptanalysis results found that the VANET authentication protocols are vulnerable to Sybil attacks.To remove this flaw， we proposed a novel protocol using searchable encryption by enabling search over encrypted identities.As a result of that，the security is improved while maintaining the privacy.The proposed solution is generic and can be applied to existing protocols that are vulnerable to Sybil attack.Simulation results show that the beacon generation time is constant while the beacon verification time is 7.908% faster compared to the state-of-the-art protocols.In addition，the beacon size is also reduced to 322 bytes，indicating that the protocol is efficient enough to be used for practical applications.In the future，we intend to adopt lightweight authentication[41]to improve the speed of the beacon verification in the proposed protocol.Efficient implementation techniques can also be developed for specialized hardware (GPU and FPGA) to enhance the speed performance and allow for large scale adoption.Furthermore，we will extend our proposed protocol to other applications such as bluetooth low energy[42]to make them secure from such attacks.

Acknowledgement:We thank our families and colleagues who provided us with moral support.

Funding Statement:This work was supported by Institute of Information&Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No.2021-0-00540， Development of Fast Design and Implementation of Cryptographic Algorithms based on GPU/ASIC).

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.