# Mix-Context-Based Pseudonym Changing Privacy Preserving Authentication in VANETs

Authors: Mengjia Zeng; Huibin Xu
Journal: Mobile Information Systems
 (2019)

---

## Abstract

Vehicular ad hoc networks (VANETs) have attracted significant attention in academia insofar as they can provide reliable and secure communication between vehicles. It is thus essential to ensure security and preserve privacy. In this paper, we propose mix-context-based pseudonym changing privacy-preserving authentication (MPCPA). MPCPA introduces privacy protection through a mutual authentication mechanism to prevent attack-vehicles from sneaking into a VANET system. Moreover, it preserves the integrity of transmitted messages with an anonymous authentication mechanism. In addition, MPCPA adopts a mix-context-based pseudonym changing strategy to prevent vehicle tracking. A performance analysis demonstrates that MPCPA incurs low computational costs and offers a privacy-preserving scheme that is more secure than existing authentication schemes.


---

## Body

## 1. Introduction

Vehicular ad hoc networks (VANETs) have gained momentum recently due to the emergence of intelligent transportation systems (ITSs). 5G is the next-generation mobile communication system, which is being developed for the expected demand of VANETs [1]. Most ITS research is dedicated to VANETs, offering extensive improvements to the safety and efficiency of transportation networks [2]. Wireless communication permits vehicle-to-infrastructure (V2I) and vehicle-to-vehicle (V2V) communication, as shown in Figure 1. As such, VANETs can improve road safety and offer value-added services to drivers on the road. Here, the infrastructure mainly refers to roadside units (RSUs). Furthermore, through V2V and V2I communication, VANETs can deliver safety-related messages (e.g., emergency reporting, collision warnings, and lane-change assistance) as well as traffic management and infotainment messages [3].Figure 1
Schematic diagram of vehicle communication.Although the feasible benefits for building up traffic safety and efficiency are conceptually attractive, there are some security and privacy challenges that need to be addressed in order to deploy VANETs [4, 5]. For instance, to prove that the sender is a genuine vehicle, messages broadcasted by the sender need to be signed. Neighboring vehicles are then able to verify the integrity of the message and the authenticity of the sender.However, unlike mobile ad hoc networks, VANETs have distinct characteristics that require specific technology to authenticate messages, identify attackers, and protect the privacy and security of the driver’s information.Several privacy requirements for VANETs are identified in the literature. Anonymity is essential among these [6]. Messages must be authenticated without revealing the senders’ identifiers. In order to meet this requirement, many pseudonymous authentication schemes have been proposed.A pseudonym is an anonymous certificate that does not reveal any information about the real identifier of the vehicle. Pseudonyms can be generated or pregenerated on demand [7, 8]. If they are pregenerated, the pseudonyms are stored in the vehicle’s on-board unit [9]. However, research has revealed that the position of a vehicle can be tracked even when pseudonyms are used, as a result of a pseudonym linking attack [10]. An attacker can excavate the relationship between pseudonyms and the real identification of the vehicle. Then, the attacker can steal the vehicles’ real identification.In order to address the above issues, we propose an efficient privacy preserving authentication scheme that we call mix-context-based pseudonym changing privacy-preserving authentication (MPCPA). Our main contributions are as follows:(1)
MPCPA is a privacy protecting mutual authentication mechanism that prevents attack-vehicles from sneaking into the VANET system(2)
MPCPA preserves the integrity of transmitted messages with an anonymous authentication mechanism(3)
MPCPA offers a mix-context-based pseudonym changing strategy with the capability of preventing vehicles from being tracked(4)
Experimental results show that the proposed authentication mechanism is efficient and that the pseudonym changing strategy protects against pseudonym linking attacks.The remainder of this research is organized as follows. A brief review of related works is presented in Section2. Our system model and the necessary preliminaries are described in Section 3. In Section 4, the efficient privacy preserving anonymous authentication scheme is discussed, and in Section 5, the pseudonym changing strategy is described in detail. Finally, we conclude the paper with a summary in Section 6.


## 2. Related Work

There is ample research that undertakes privacy and pseudonymity. For instance, Zhang et al. [11] proposed a novel identity-based batch verification (IBBV) algorithm, although the algorithm is vulnerable to nonrepudiation attacks. Shim [12] introduced an efficient identity- (ID-) based signature (IBS) algorithm that is able to protect against impersonation attacks. However, it is vulnerable to modification attacks. Thenmozhi et al. [13] proposed blind signature-based security and privacy. It implements a security mechanism using blind signature, where the roadside units in collaboration with the trusted authority generate the keys to be transmitted to the vehicles.When providing safety-related messages to vehicles, only authenticated vehicles are allowed to communicate in the network and only authenticated messages can be exchanged among vehicles. Considering the privacy of vehicles, the authentication operation is done anonymously. However, existing algorithms suffer from high computational costs incurred by anonymous authentication. Thus, Vijayakumar et al. [14] proposed an efficient privacy preserving anonymous batch authentication scheme. Their scheme verifies the authenticity of a batch of vehicles when a batch of messages is received.Islam et al. [15] designed a password-based conditional privacy preserving authentication protocol without bilinear pairing or an elliptic curve. The protocol avoids heavy computational costs and introduces a group-key generation mechanism, where vehicles can only communicate with vehicles that have the same group-key. Azees et al. [16] proposed efficient anonymous authentication in order to avoid malicious vehicles from entering into the VANET. However, their scheme still suffers from high computational costs.In addition, a pseudonym changing approach is a common anonymous privacy protection mechanism. Freudiger et al. [17] proposed a game-theoretic solution to change pseudonyms (GSCP). Moreover, Ying et al. [18] introduced dynamic mix-zones for location privacy. However, their scheme is susceptible to semantic linking attacks. In order to avoid adversaries from making predictions, Pan et al. [19] proposed a random pseudonym changing algorithm. Moreover, Eckhoff et al. [20] proposed a mix-zone-based pseudonym changing strategy. According to the strategy, most vehicles change their pseudonym at the same time.


## 3. System Model and Preliminaries

### 3.1. System Model

VANETs consist of three types of network entities, as shown in Figure2, viz., trusted authorities (TAs), RSUs, and vehicles.Figure 2
System model.TAs are in charge of registering vehicles and RSUs. In other words, the TA is responsible for issuing public/private key pairs and certificates [21]. It is worth mentioning that a TA is considered to be fully trusted.An RSU is infrastructure deployed at the road side, subordinated by the TA. RSUs can connect to the Internet and communicate with vehicles within range. Furthermore, a vehicle communicates with the TA through the adjacent RSU.Vehicles are motorized vehicles operating on the road. These vehicles mainly communicate with one another to share local traffic information. In addition, each vehicle is equipped with a tamper-proof device. This device stores the private and public keys for the vehicle. It is assumed that TAs, RSUs, and vehicles all have certain computing power. Moreover, all three communication entities adopt a consistent time mechanism.


### 3.2. Mathematical Model

Bilinear pairing technology was proposed by Boneh et al. in 2004 and forms the basis of our proposed authentication mechanism [22]. The mechanism is based on two additive cyclic groups and a multiplicative group. We denote the additive groups by G1 and G2 and the multiplicative group by GT. The three groups have the same prime order, q. It is worth mentioning that q is a large prime. The bilinear map is e:G1×G2⟶GT. The bilinear map satisfies the following properties:(1)
Bilinear: ∀a,b∈Zq∗, the mapping e:G1×G2⟶GT is considered to be bilinear when it satisfies the following equation:(1)eg1a,g2b=eg1,g2ab,whereg1 and g2 are generators of G1 and G2, respectively, and a,b∈Zq∗. Among them, Zq∗=1,2,…,q−1.(2)
Nondegeneracy: eg1,g2≠1GT.(3)
Computable: there is an efficient algorithm that easily computes the bilinear map e:G1×G2⟶GT.


## 3.1. System Model

VANETs consist of three types of network entities, as shown in Figure2, viz., trusted authorities (TAs), RSUs, and vehicles.Figure 2
System model.TAs are in charge of registering vehicles and RSUs. In other words, the TA is responsible for issuing public/private key pairs and certificates [21]. It is worth mentioning that a TA is considered to be fully trusted.An RSU is infrastructure deployed at the road side, subordinated by the TA. RSUs can connect to the Internet and communicate with vehicles within range. Furthermore, a vehicle communicates with the TA through the adjacent RSU.Vehicles are motorized vehicles operating on the road. These vehicles mainly communicate with one another to share local traffic information. In addition, each vehicle is equipped with a tamper-proof device. This device stores the private and public keys for the vehicle. It is assumed that TAs, RSUs, and vehicles all have certain computing power. Moreover, all three communication entities adopt a consistent time mechanism.


## 3.2. Mathematical Model

Bilinear pairing technology was proposed by Boneh et al. in 2004 and forms the basis of our proposed authentication mechanism [22]. The mechanism is based on two additive cyclic groups and a multiplicative group. We denote the additive groups by G1 and G2 and the multiplicative group by GT. The three groups have the same prime order, q. It is worth mentioning that q is a large prime. The bilinear map is e:G1×G2⟶GT. The bilinear map satisfies the following properties:(1)
Bilinear: ∀a,b∈Zq∗, the mapping e:G1×G2⟶GT is considered to be bilinear when it satisfies the following equation:(1)eg1a,g2b=eg1,g2ab,whereg1 and g2 are generators of G1 and G2, respectively, and a,b∈Zq∗. Among them, Zq∗=1,2,…,q−1.(2)
Nondegeneracy: eg1,g2≠1GT.(3)
Computable: there is an efficient algorithm that easily computes the bilinear map e:G1×G2⟶GT.


## 4. Privacy Preserving Anonymous Authentication Scheme

This section describes the proposed pseudonym authentication framework. The framework consists of three parts: system initialization, registration, and mutual authentication of pseudonyms. The authentication framework is shown in Figure3.Figure 3
Block of authentication framework.Pandi et al. [21] proposed an efficient anonymous identity authentication scheme to protect privacy. However, the random numbers in the parameters must be completely random, and it is unclear how collisions are prevented. On the basis of this, temporal parameters are added to avoid collisions when generating random numbers.


### 4.1. System Initialization

During system initialization, the TA is responsible for generating basic common parameters. First, the TA generates two random numbers,m,k∈Zq∗, as private keys, where m is the primary key. That is, MkeyTA=m. Because the values of g1m and g1k are repeatedly used in the following steps, the results are calculated in advance and saved in the form of parameters for subsequent use. Let P=g1m and Q=g1k. The hash function H:0,1∗⟶Zq∗ is then introduced. The common parameters of the system are expressed as pu_sy=q,e,g1,g2,G1,G2,GT,P,Q,H.


### 4.2. Registration Process

During the registration phase, the TA is responsible for generating public keys, private keys, and pseudonyms for the RSUs and vehicles. For a vehicle, for example, the public key, private key, and pseudonym are generated as follows:Step 1.
When a vehiclevi moves into the TA’s communication range, it transmits its name, address, license plate number, and other basic information to the TA—together with the sending time ti of this message. Due to the TA’s limited communication range and the high-speed movement of vehicles, few vehicles will be near the TA concurrently. Indeed, because the transmission time timei of a vehicle is recorded in seconds, timei is almost certainly unique. Therefore, this data can be used to identify the vehicle.Step 2.
The TA generates a random numbert∈Zq∗ by using timei as the seed for the random number after receiving the basic information sent by vehicle vi. The random number t is used as the system private key for vehicle vi. That is, Sskvi=t. Then, the TA calculates Spukvi=g1t as the system public key for vehicle vi.Step 3.
In order to avoid transmitting real information about the vehicle during the authentication process, a forged vehicle identification code, i.e., the pseudonym, is used as the identification during vehicle authentication. The pseudonym is used to protect the privacy of vehiclevi from other vehicles. The initial pseudonym PSvi=Spukvi×P=g1m+t is calculated by the TA.Step 4.
The TA calculatesIDvi=Spukvi×P×Q=g1m+k+t and considers it a fake ID for vehicle vi.Step 5.
The TA stores the informationPSυi,IDvi of vehicle vi. At the same time, the TA sends the initial pseudonym, public key, and private key PSυi,Spukvi,Sskvi to the vehicle.
The TA’s registration process for the RSU also goes through the five steps described above. That is, the TA generates a random numberr∈Zq∗ as the system private key SskRi for the i−th RSU. It then calculates its system public key SpukRi=g1r, initial pseudonym PSRi=SpukRi×P=g1r+m, and fake ID IDRi=SpukRi×P×Q=g1m+k+r. Finally, the TA stores PSRi,IDRi and sends PSRi,SpukRi,SskRi to RSUi.


### 4.3. Anonymous Authentication Based on Privacy Preserving

The authentication process takes place in the intercommunicating vehicle network entities. Its purpose is to prove the legitimacy of the communication entities and the integrity of the data in the transmission process. If the information is sent directly, there will be a risk of privacy disclosure. Therefore, anonymity is used to verify the legitimacy of the communication entity. Because the link time of each entity in the communication process is very short, if we can ensure the dynamic changes of various data, we can enhance the privacy. Therefore, the execution process of the algorithm coupled with a timeliness judgment validates the data in the timeliness range. Otherwise, the invalid data need to be recalculated and verified.


#### 4.3.1. Generating Anonymous Certificates and Anonymous Signatures

In this algorithm, the legitimacy and data integrity of communication entities are realized by verifying certificates and signatures. In order to prove the legitimacy of the communication entity, the certificate verifies whether the sending entity has the legal identity. If it does not, it will proceed by verifying the signature and disconnecting from the communication entity. Signature verification confirms that the data are complete and untampered during the transmission. Therefore, before verifying the validity and data integrity, it is necessary to generate vehicle certificates and signatures. The anonymous vehicle certificates are generated through the steps in Algorithm1.Algorithm 1:Generating anonymous certificate.
Step 1. Vehicle vi uses the current time timei as the seed of random number to generate random number ti∈Zq∗ and calculates its authentication public key Apukvi=g1ti.
Step 2. Vehicle vi generates 3 random numbers a,b,c∈Zq∗ and computes authentication parameters L1=g1ti+a+b, L2=g1a+b, L3=g1b+c−t, L4=g1−t, L1′=g1a+b+c, L2′=g1b+c, and L3′=g1−c.
Step 3. Use authentication public key and authentication parameters L1∼L4 and system parameter P from function H to generate vehicle vi′s authentication verification code Ac=HApuKiL1L2L3L4P.
Step 4. Use Ac,L1′∼L3′,L4, authentication public key, and pseudonym of vehicle vi to combine an anonymous certification Cervi=AcL1′L2′L3′L4ApukviPSvi.Assuming that the data to be transmitted for vehiclevi is data and expressed as D, its anonymous signature Sigυi is generated as follows:(2)Sigυi=g2HD+ti+t−1.Finally, vehiclevi proves its legitimacy by broadcasting messages msg, consisting of vehicle vi′s anonymous certificate, the anonymous signature, and the system public key:(3)msg=CerviSigυiSpukvi.


#### 4.3.2. Identity Verification

Other vehicles or RSUs that receivemsg will verify the identity of the sender. The verification process is as follows:Step 1.
Separately calculate the following:(4)X=PSvi×L4,La=Apukvi×L1′×L3′,Lb=L1′×L3′,Lc=L2′×L4.Step 2.
Use parametersX,La,Lb,Lc to generate a new verification code Ac′, as follows:(5)Ac′=HApuKiLaLbLcL4X.Step 3.
Verify the validity of the identity of the vehicle sending the message by verifying whetherAc=Ac′ is valid. The composition of Ac and Ac′ is compared, and it suffices to validate L1=La,L2=Lb,L3=Lc,P=X. The verification process is as follows:(6)Ac=Ac′,(7)La=Apukvi×L1′×L3′=g1ti×g1a+b+c×g1−c=g1ti+a+b+c−c=g1ti+a+b=L1,(8)Lb=L1′×L3′=g1a+b+c×g1−c=g1a+b+c−c=g1a+b=L2,(9)Lc=L2′×L4=g1b+c×g1−t=g1b+c−t=L3,(10)Lc=L2′×L4=g1b+c×g1−t=g1b+c−t=L3,(11)X=PSvi×L4=g1m+t×g1−t=g1m+t−t=g1m=P.
Therefore,Ac=Ac′ is established and the legal identity of the vehicle vi is verified.


#### 4.3.3. Verifying Data Integrity

The integrity of the transmitted data is ensured by verifying the signature. As such, the data are untampered. The receiver uses equation (11) to verify the integrity of the data. If equation (11) holds, the data are untampered, and the receiver receives the message. Otherwise, the message is rejected:(12)eg1HD⋅Apukvi⋅Spukvi,Sigi=eg1,g2.The process of checking this is as follows:(13)eg1HD⋅Apukvi⋅Spukvi,Sigi=eg1HD⋅g1ti⋅g1t,g2HD+ti+t−1=eg1HD+ti+t,g2HD+ti+t−1=eg1,g2HD+ti+t×HD+ti+t−1=eg1,g2.Therefore, the integrity of the data is verified, indicating that it has not been tampered with during the transmission process.


## 4.1. System Initialization

During system initialization, the TA is responsible for generating basic common parameters. First, the TA generates two random numbers,m,k∈Zq∗, as private keys, where m is the primary key. That is, MkeyTA=m. Because the values of g1m and g1k are repeatedly used in the following steps, the results are calculated in advance and saved in the form of parameters for subsequent use. Let P=g1m and Q=g1k. The hash function H:0,1∗⟶Zq∗ is then introduced. The common parameters of the system are expressed as pu_sy=q,e,g1,g2,G1,G2,GT,P,Q,H.


## 4.2. Registration Process

During the registration phase, the TA is responsible for generating public keys, private keys, and pseudonyms for the RSUs and vehicles. For a vehicle, for example, the public key, private key, and pseudonym are generated as follows:Step 1.
When a vehiclevi moves into the TA’s communication range, it transmits its name, address, license plate number, and other basic information to the TA—together with the sending time ti of this message. Due to the TA’s limited communication range and the high-speed movement of vehicles, few vehicles will be near the TA concurrently. Indeed, because the transmission time timei of a vehicle is recorded in seconds, timei is almost certainly unique. Therefore, this data can be used to identify the vehicle.Step 2.
The TA generates a random numbert∈Zq∗ by using timei as the seed for the random number after receiving the basic information sent by vehicle vi. The random number t is used as the system private key for vehicle vi. That is, Sskvi=t. Then, the TA calculates Spukvi=g1t as the system public key for vehicle vi.Step 3.
In order to avoid transmitting real information about the vehicle during the authentication process, a forged vehicle identification code, i.e., the pseudonym, is used as the identification during vehicle authentication. The pseudonym is used to protect the privacy of vehiclevi from other vehicles. The initial pseudonym PSvi=Spukvi×P=g1m+t is calculated by the TA.Step 4.
The TA calculatesIDvi=Spukvi×P×Q=g1m+k+t and considers it a fake ID for vehicle vi.Step 5.
The TA stores the informationPSυi,IDvi of vehicle vi. At the same time, the TA sends the initial pseudonym, public key, and private key PSυi,Spukvi,Sskvi to the vehicle.
The TA’s registration process for the RSU also goes through the five steps described above. That is, the TA generates a random numberr∈Zq∗ as the system private key SskRi for the i−th RSU. It then calculates its system public key SpukRi=g1r, initial pseudonym PSRi=SpukRi×P=g1r+m, and fake ID IDRi=SpukRi×P×Q=g1m+k+r. Finally, the TA stores PSRi,IDRi and sends PSRi,SpukRi,SskRi to RSUi.


## 4.3. Anonymous Authentication Based on Privacy Preserving

The authentication process takes place in the intercommunicating vehicle network entities. Its purpose is to prove the legitimacy of the communication entities and the integrity of the data in the transmission process. If the information is sent directly, there will be a risk of privacy disclosure. Therefore, anonymity is used to verify the legitimacy of the communication entity. Because the link time of each entity in the communication process is very short, if we can ensure the dynamic changes of various data, we can enhance the privacy. Therefore, the execution process of the algorithm coupled with a timeliness judgment validates the data in the timeliness range. Otherwise, the invalid data need to be recalculated and verified.


### 4.3.1. Generating Anonymous Certificates and Anonymous Signatures

In this algorithm, the legitimacy and data integrity of communication entities are realized by verifying certificates and signatures. In order to prove the legitimacy of the communication entity, the certificate verifies whether the sending entity has the legal identity. If it does not, it will proceed by verifying the signature and disconnecting from the communication entity. Signature verification confirms that the data are complete and untampered during the transmission. Therefore, before verifying the validity and data integrity, it is necessary to generate vehicle certificates and signatures. The anonymous vehicle certificates are generated through the steps in Algorithm1.Algorithm 1:Generating anonymous certificate.
Step 1. Vehicle vi uses the current time timei as the seed of random number to generate random number ti∈Zq∗ and calculates its authentication public key Apukvi=g1ti.
Step 2. Vehicle vi generates 3 random numbers a,b,c∈Zq∗ and computes authentication parameters L1=g1ti+a+b, L2=g1a+b, L3=g1b+c−t, L4=g1−t, L1′=g1a+b+c, L2′=g1b+c, and L3′=g1−c.
Step 3. Use authentication public key and authentication parameters L1∼L4 and system parameter P from function H to generate vehicle vi′s authentication verification code Ac=HApuKiL1L2L3L4P.
Step 4. Use Ac,L1′∼L3′,L4, authentication public key, and pseudonym of vehicle vi to combine an anonymous certification Cervi=AcL1′L2′L3′L4ApukviPSvi.Assuming that the data to be transmitted for vehiclevi is data and expressed as D, its anonymous signature Sigυi is generated as follows:(2)Sigυi=g2HD+ti+t−1.Finally, vehiclevi proves its legitimacy by broadcasting messages msg, consisting of vehicle vi′s anonymous certificate, the anonymous signature, and the system public key:(3)msg=CerviSigυiSpukvi.


### 4.3.2. Identity Verification

Other vehicles or RSUs that receivemsg will verify the identity of the sender. The verification process is as follows:Step 1.
Separately calculate the following:(4)X=PSvi×L4,La=Apukvi×L1′×L3′,Lb=L1′×L3′,Lc=L2′×L4.Step 2.
Use parametersX,La,Lb,Lc to generate a new verification code Ac′, as follows:(5)Ac′=HApuKiLaLbLcL4X.Step 3.
Verify the validity of the identity of the vehicle sending the message by verifying whetherAc=Ac′ is valid. The composition of Ac and Ac′ is compared, and it suffices to validate L1=La,L2=Lb,L3=Lc,P=X. The verification process is as follows:(6)Ac=Ac′,(7)La=Apukvi×L1′×L3′=g1ti×g1a+b+c×g1−c=g1ti+a+b+c−c=g1ti+a+b=L1,(8)Lb=L1′×L3′=g1a+b+c×g1−c=g1a+b+c−c=g1a+b=L2,(9)Lc=L2′×L4=g1b+c×g1−t=g1b+c−t=L3,(10)Lc=L2′×L4=g1b+c×g1−t=g1b+c−t=L3,(11)X=PSvi×L4=g1m+t×g1−t=g1m+t−t=g1m=P.
Therefore,Ac=Ac′ is established and the legal identity of the vehicle vi is verified.


### 4.3.3. Verifying Data Integrity

The integrity of the transmitted data is ensured by verifying the signature. As such, the data are untampered. The receiver uses equation (11) to verify the integrity of the data. If equation (11) holds, the data are untampered, and the receiver receives the message. Otherwise, the message is rejected:(12)eg1HD⋅Apukvi⋅Spukvi,Sigi=eg1,g2.The process of checking this is as follows:(13)eg1HD⋅Apukvi⋅Spukvi,Sigi=eg1HD⋅g1ti⋅g1t,g2HD+ti+t−1=eg1HD+ti+t,g2HD+ti+t−1=eg1,g2HD+ti+t×HD+ti+t−1=eg1,g2.Therefore, the integrity of the data is verified, indicating that it has not been tampered with during the transmission process.


## 4.3.1. Generating Anonymous Certificates and Anonymous Signatures

In this algorithm, the legitimacy and data integrity of communication entities are realized by verifying certificates and signatures. In order to prove the legitimacy of the communication entity, the certificate verifies whether the sending entity has the legal identity. If it does not, it will proceed by verifying the signature and disconnecting from the communication entity. Signature verification confirms that the data are complete and untampered during the transmission. Therefore, before verifying the validity and data integrity, it is necessary to generate vehicle certificates and signatures. The anonymous vehicle certificates are generated through the steps in Algorithm1.Algorithm 1:Generating anonymous certificate.
Step 1. Vehicle vi uses the current time timei as the seed of random number to generate random number ti∈Zq∗ and calculates its authentication public key Apukvi=g1ti.
Step 2. Vehicle vi generates 3 random numbers a,b,c∈Zq∗ and computes authentication parameters L1=g1ti+a+b, L2=g1a+b, L3=g1b+c−t, L4=g1−t, L1′=g1a+b+c, L2′=g1b+c, and L3′=g1−c.
Step 3. Use authentication public key and authentication parameters L1∼L4 and system parameter P from function H to generate vehicle vi′s authentication verification code Ac=HApuKiL1L2L3L4P.
Step 4. Use Ac,L1′∼L3′,L4, authentication public key, and pseudonym of vehicle vi to combine an anonymous certification Cervi=AcL1′L2′L3′L4ApukviPSvi.Assuming that the data to be transmitted for vehiclevi is data and expressed as D, its anonymous signature Sigυi is generated as follows:(2)Sigυi=g2HD+ti+t−1.Finally, vehiclevi proves its legitimacy by broadcasting messages msg, consisting of vehicle vi′s anonymous certificate, the anonymous signature, and the system public key:(3)msg=CerviSigυiSpukvi.


## 4.3.2. Identity Verification

Other vehicles or RSUs that receivemsg will verify the identity of the sender. The verification process is as follows:Step 1.
Separately calculate the following:(4)X=PSvi×L4,La=Apukvi×L1′×L3′,Lb=L1′×L3′,Lc=L2′×L4.Step 2.
Use parametersX,La,Lb,Lc to generate a new verification code Ac′, as follows:(5)Ac′=HApuKiLaLbLcL4X.Step 3.
Verify the validity of the identity of the vehicle sending the message by verifying whetherAc=Ac′ is valid. The composition of Ac and Ac′ is compared, and it suffices to validate L1=La,L2=Lb,L3=Lc,P=X. The verification process is as follows:(6)Ac=Ac′,(7)La=Apukvi×L1′×L3′=g1ti×g1a+b+c×g1−c=g1ti+a+b+c−c=g1ti+a+b=L1,(8)Lb=L1′×L3′=g1a+b+c×g1−c=g1a+b+c−c=g1a+b=L2,(9)Lc=L2′×L4=g1b+c×g1−t=g1b+c−t=L3,(10)Lc=L2′×L4=g1b+c×g1−t=g1b+c−t=L3,(11)X=PSvi×L4=g1m+t×g1−t=g1m+t−t=g1m=P.
Therefore,Ac=Ac′ is established and the legal identity of the vehicle vi is verified.


## 4.3.3. Verifying Data Integrity

The integrity of the transmitted data is ensured by verifying the signature. As such, the data are untampered. The receiver uses equation (11) to verify the integrity of the data. If equation (11) holds, the data are untampered, and the receiver receives the message. Otherwise, the message is rejected:(12)eg1HD⋅Apukvi⋅Spukvi,Sigi=eg1,g2.The process of checking this is as follows:(13)eg1HD⋅Apukvi⋅Spukvi,Sigi=eg1HD⋅g1ti⋅g1t,g2HD+ti+t−1=eg1HD+ti+t,g2HD+ti+t−1=eg1,g2HD+ti+t×HD+ti+t−1=eg1,g2.Therefore, the integrity of the data is verified, indicating that it has not been tampered with during the transmission process.


## 5. Pseudonym Changing Mechanism

In this section, we describe the proposed pseudonym changing mechanism in detail. We assume that each vehicle has a set of pseudonyms pregenerated by the TA. In addition, each pseudonym has a short duration, called the stable time. In other words, each vehicle has to change its pseudonym frequently. The model for the pseudonym changing mechanism is shown in Figure4.Figure 4
Model for the pseudonym changing mechanism.


### 5.1. Resolved Problem

Even when vehicles change their pseudonyms, attackers can discover the relationship between the pseudonyms by various means. Consequently, the position of vehicles can be tracked. This attack is called a pseudonym linking attack, as shown Figure5. To illustrate this, we consider a case with three vehicles (A, B, and C). If only vehicle B changes its pseudonym from B1 to B2 during Δt, an attacker can discover that B1 and B2 are associated with B.Figure 5
Pseudonym linking attack.The proposed pseudonym changing mechanism prevents this type of attack by making it more difficult for the attacker to link pseudonyms. The main purpose of the proposed pseudonym changing mechanism is to determine where and when a vehicle should change its pseudonym [10].


### 5.2. Mix-Context-Based Cooperative Pseudonym Mechanism

In the proposed MPCPA, each vehicle decides independently where and when to change its pseudonym; in this way, each pseudonym has a stable time. Once this stable time expires, the vehicle is ready to change its pseudonym and is able to check whether the mix-context condition is satisfied. If this is the case, the vehicle changes its pseudonym immediately. Otherwise, the vehicle waits until the maximum wait time expires, at which time it must change its pseudonym. The mechanism is shown in Figure6.Figure 6
Diagram of the proposed pseudonym mechanism.As shown in Figure6, the mix-context condition is a substantial element in the proposed mechanism. Thus, we analyzed this condition in detail.In VANETs, vehicles need to broadcast their beacons at the same time, and synchrony is achieved with GPS clocks. Therefore, we make use of these beacons by inserting two flags into each beacon, as shown in Figure7.Figure 7
Beacon format.Here, the wait-flag indicates whether a vehicle is waiting to change its pseudonym. If the wait-flag is 1, the vehicle is waiting to change its pseudonym. Otherwise, it is not. The ready-flag indicates whether the vehicle is ready to change its pseudonym during the next time slot. If the ready-flag is 1, the vehicle is ready to change its pseudonym. Both the wait-flag and ready-flag are initially set to 0.In addition, the proposed MPCPA is a cooperative model. Each vehicle needs to construct a list of neighbors. LetLυ denote the set of vehicles neighboring vehicle υ. The list of neighbors is generated by data received by the beacons.When the stable time expires, the wait-flag is set to 1. The ready-flag is then set to 1 when the vehicle finds at leastk neighboring vehicles with a wait-flag equal to 1 and k≤L, where L denotes the number of neighboring vehicles.The conditions for changing a pseudonym are shown in Algorithm2. The vehicle will change its pseudonym when at least k neighboring vehicles are ready to change their pseudonyms, or when one of neighboring vehicles has k or more neighbors ready to change their pseudonyms.Algorithm 2:Mix-context cooperative pseudonym changing mechanism.
Input: Lυ=0,…,N,k
Output: pseudonym changing
If num_nbυ≥k then
Vehicle υ changes the pseudonym
Else
for i=1 to N
If num_nbi≥k then
Vehicle υ changes the pseudonym
End if
End for
End ifSpecifically,num_nb is used to count the number of neighboring vehicles with a ready-flag equal to 1. When num_nbυ = 3, for instance, there are three neighboring vehicles with a ready-flag equal to 1.


## 5.1. Resolved Problem

Even when vehicles change their pseudonyms, attackers can discover the relationship between the pseudonyms by various means. Consequently, the position of vehicles can be tracked. This attack is called a pseudonym linking attack, as shown Figure5. To illustrate this, we consider a case with three vehicles (A, B, and C). If only vehicle B changes its pseudonym from B1 to B2 during Δt, an attacker can discover that B1 and B2 are associated with B.Figure 5
Pseudonym linking attack.The proposed pseudonym changing mechanism prevents this type of attack by making it more difficult for the attacker to link pseudonyms. The main purpose of the proposed pseudonym changing mechanism is to determine where and when a vehicle should change its pseudonym [10].


## 5.2. Mix-Context-Based Cooperative Pseudonym Mechanism

In the proposed MPCPA, each vehicle decides independently where and when to change its pseudonym; in this way, each pseudonym has a stable time. Once this stable time expires, the vehicle is ready to change its pseudonym and is able to check whether the mix-context condition is satisfied. If this is the case, the vehicle changes its pseudonym immediately. Otherwise, the vehicle waits until the maximum wait time expires, at which time it must change its pseudonym. The mechanism is shown in Figure6.Figure 6
Diagram of the proposed pseudonym mechanism.As shown in Figure6, the mix-context condition is a substantial element in the proposed mechanism. Thus, we analyzed this condition in detail.In VANETs, vehicles need to broadcast their beacons at the same time, and synchrony is achieved with GPS clocks. Therefore, we make use of these beacons by inserting two flags into each beacon, as shown in Figure7.Figure 7
Beacon format.Here, the wait-flag indicates whether a vehicle is waiting to change its pseudonym. If the wait-flag is 1, the vehicle is waiting to change its pseudonym. Otherwise, it is not. The ready-flag indicates whether the vehicle is ready to change its pseudonym during the next time slot. If the ready-flag is 1, the vehicle is ready to change its pseudonym. Both the wait-flag and ready-flag are initially set to 0.In addition, the proposed MPCPA is a cooperative model. Each vehicle needs to construct a list of neighbors. LetLυ denote the set of vehicles neighboring vehicle υ. The list of neighbors is generated by data received by the beacons.When the stable time expires, the wait-flag is set to 1. The ready-flag is then set to 1 when the vehicle finds at leastk neighboring vehicles with a wait-flag equal to 1 and k≤L, where L denotes the number of neighboring vehicles.The conditions for changing a pseudonym are shown in Algorithm2. The vehicle will change its pseudonym when at least k neighboring vehicles are ready to change their pseudonyms, or when one of neighboring vehicles has k or more neighbors ready to change their pseudonyms.Algorithm 2:Mix-context cooperative pseudonym changing mechanism.
Input: Lυ=0,…,N,k
Output: pseudonym changing
If num_nbυ≥k then
Vehicle υ changes the pseudonym
Else
for i=1 to N
If num_nbi≥k then
Vehicle υ changes the pseudonym
End if
End for
End ifSpecifically,num_nb is used to count the number of neighboring vehicles with a ready-flag equal to 1. When num_nbυ = 3, for instance, there are three neighboring vehicles with a ready-flag equal to 1.


## 6. Performance Analysis

In this section, we analyze the performance of the proposed MPCPA.


### 6.1. Security Analysis

The proposed scheme satisfies anonymous vehicle authentication and privacy protection.


#### 6.1.1. Anonymous Vehicle Authentication

As explained in Section4.3 and detailed in Algorithm 1, a vehicle v generates an anonymous certificate and an anonymous signature for message M. Message M contains a signature and a certificate. Vehicle v is successfully authenticated only when equation (6) is satisfied.


#### 6.1.2. Privacy Protection

The privacy of the vehicles is protected using a digital signature and the mix-context cooperative pseudonym changing mechanism, as detailed inAlgorithm 2. Each vehicle has a set of pseudonyms, and a vehicle changes its pseudonym only when the mix-context conditions are satisfied. This mechanism protects vehicle privacy and prevents vehicles from being tracked.


### 6.2. Computation Cost and Verification Time of Anonymous Authentication

We selected two main evaluation metrics to evaluate the performance of the proposed authentication mechanism: the computation cost and the verification time. Both metrics reflect the complexity of the algorithm. The computation cost refers to the total amount of time required for the authentication process. In addition, we compared the performance of MPCPA to that of four well-known authentication mechanisms, viz., IBBV [11], GSCP [17], key-insulated pseudonym self-delegation (KPSD) [23], and secure authentication scheme for VANETs with batch verification (SABV) [24].Lettp, th, and tm denote the execution time for the pairing operation, hash operation, and multiplication operation, respectively. Accordingly, te and ts are the execution time required for the exponentiation operations in G1 and G2, respectively.The total amount of consumed time for the various schemes is shown in Table1. We can observe that our MPCPA algorithm outperforms existing schemes in terms of the computational cost. As such, the proposed scheme has a relatively fast execution time. In particular, for one certification and signature, MPCPA required only 2tp, 2te, and 2th for the verification process.Table 1
Total amount of consumed time.
Scheme
Execution time for operation
Pairing
Hash
Multiplication
Exponentiation
MPCPA
(1 +n)tp
nt
h
—
(1 +n)te
GSCP
(2 + 3n)tp
2nt
h
(n + 5)tm
—
KPSD
(3 +n)tp
nt
h
—
(4 +n)te + 5nts
IBBV
3ntp
3nt
h
(2n + 5)tm
—
SABV
(2 + 3n)tp
nt
h
—
nt
eNext, the verification time of MPCPA was compared to that of IBBV, GSCP, KPSD, and SABV. Figure8 shows the results of this experiment. Indeed, with an increase in the number of received messages, the verification time will increase. Compared to IBBV, GSCP, KPSD, and SABV, the proposed MPCPA performed better in terms of the verification time. For example, with 120 received messages, our MPCPA algorithm required merely 600 ms to complete the verification process, whereas the other algorithms needed more than 900 ms.Figure 8
Verification time of various schemes.


### 6.3. Avoiding Pseudonym Linking Attacks

According to the above analysis, the purpose of the proposed pseudonym mechanism is to defend against attackers seeking to track vehicles and stealing private information with a pseudonym linking attack. In order to analyze the effectiveness of the proposed mechanism, the tracking model in [25] was introduced to determine the tracking probability.We denote the number of vehicles ready to change their pseudonyms atΔt by NΔt. According to a Poisson process, NΔt is distributed as follows:(14)PrNΔt=i=λΔtie−λΔti!,where the vehicles are uniformly distributed with rate λ.When the stable time of the pseudonym expires, the vehicle is ready to change its pseudonym. Thus, we assume that at least one vehicle has changed its pseudonym. The probabilityPt that a new pseudonym will be linked to the same vehicle is derived as follows [26]:(15)Pt=PrNΔt=1∣NΔt≥1=PrNΔt=11−PrNΔt=0=λte−λt1−e−λt.Note that in Algorithm2, parameter k plays an important role in defending against a pseudonym linking attack. Therefore, the impact of parameter k on the probability Pt is relevant. Given that λ=k/Lυ, Figure 9 shows tracking probabilities under different λ values. As shown in the figure, the probability drastically decreases as k increases. This is expected. The more vehicles simultaneously changing their pseudonyms, the less likely they are to be tracked.Figure 9
Tracking probability over 80 s.


## 6.1. Security Analysis

The proposed scheme satisfies anonymous vehicle authentication and privacy protection.


### 6.1.1. Anonymous Vehicle Authentication

As explained in Section4.3 and detailed in Algorithm 1, a vehicle v generates an anonymous certificate and an anonymous signature for message M. Message M contains a signature and a certificate. Vehicle v is successfully authenticated only when equation (6) is satisfied.


### 6.1.2. Privacy Protection

The privacy of the vehicles is protected using a digital signature and the mix-context cooperative pseudonym changing mechanism, as detailed inAlgorithm 2. Each vehicle has a set of pseudonyms, and a vehicle changes its pseudonym only when the mix-context conditions are satisfied. This mechanism protects vehicle privacy and prevents vehicles from being tracked.


## 6.1.1. Anonymous Vehicle Authentication

As explained in Section4.3 and detailed in Algorithm 1, a vehicle v generates an anonymous certificate and an anonymous signature for message M. Message M contains a signature and a certificate. Vehicle v is successfully authenticated only when equation (6) is satisfied.


## 6.1.2. Privacy Protection

The privacy of the vehicles is protected using a digital signature and the mix-context cooperative pseudonym changing mechanism, as detailed inAlgorithm 2. Each vehicle has a set of pseudonyms, and a vehicle changes its pseudonym only when the mix-context conditions are satisfied. This mechanism protects vehicle privacy and prevents vehicles from being tracked.


## 6.2. Computation Cost and Verification Time of Anonymous Authentication

We selected two main evaluation metrics to evaluate the performance of the proposed authentication mechanism: the computation cost and the verification time. Both metrics reflect the complexity of the algorithm. The computation cost refers to the total amount of time required for the authentication process. In addition, we compared the performance of MPCPA to that of four well-known authentication mechanisms, viz., IBBV [11], GSCP [17], key-insulated pseudonym self-delegation (KPSD) [23], and secure authentication scheme for VANETs with batch verification (SABV) [24].Lettp, th, and tm denote the execution time for the pairing operation, hash operation, and multiplication operation, respectively. Accordingly, te and ts are the execution time required for the exponentiation operations in G1 and G2, respectively.The total amount of consumed time for the various schemes is shown in Table1. We can observe that our MPCPA algorithm outperforms existing schemes in terms of the computational cost. As such, the proposed scheme has a relatively fast execution time. In particular, for one certification and signature, MPCPA required only 2tp, 2te, and 2th for the verification process.Table 1
Total amount of consumed time.
Scheme
Execution time for operation
Pairing
Hash
Multiplication
Exponentiation
MPCPA
(1 +n)tp
nt
h
—
(1 +n)te
GSCP
(2 + 3n)tp
2nt
h
(n + 5)tm
—
KPSD
(3 +n)tp
nt
h
—
(4 +n)te + 5nts
IBBV
3ntp
3nt
h
(2n + 5)tm
—
SABV
(2 + 3n)tp
nt
h
—
nt
eNext, the verification time of MPCPA was compared to that of IBBV, GSCP, KPSD, and SABV. Figure8 shows the results of this experiment. Indeed, with an increase in the number of received messages, the verification time will increase. Compared to IBBV, GSCP, KPSD, and SABV, the proposed MPCPA performed better in terms of the verification time. For example, with 120 received messages, our MPCPA algorithm required merely 600 ms to complete the verification process, whereas the other algorithms needed more than 900 ms.Figure 8
Verification time of various schemes.


## 6.3. Avoiding Pseudonym Linking Attacks

According to the above analysis, the purpose of the proposed pseudonym mechanism is to defend against attackers seeking to track vehicles and stealing private information with a pseudonym linking attack. In order to analyze the effectiveness of the proposed mechanism, the tracking model in [25] was introduced to determine the tracking probability.We denote the number of vehicles ready to change their pseudonyms atΔt by NΔt. According to a Poisson process, NΔt is distributed as follows:(14)PrNΔt=i=λΔtie−λΔti!,where the vehicles are uniformly distributed with rate λ.When the stable time of the pseudonym expires, the vehicle is ready to change its pseudonym. Thus, we assume that at least one vehicle has changed its pseudonym. The probabilityPt that a new pseudonym will be linked to the same vehicle is derived as follows [26]:(15)Pt=PrNΔt=1∣NΔt≥1=PrNΔt=11−PrNΔt=0=λte−λt1−e−λt.Note that in Algorithm2, parameter k plays an important role in defending against a pseudonym linking attack. Therefore, the impact of parameter k on the probability Pt is relevant. Given that λ=k/Lυ, Figure 9 shows tracking probabilities under different λ values. As shown in the figure, the probability drastically decreases as k increases. This is expected. The more vehicles simultaneously changing their pseudonyms, the less likely they are to be tracked.Figure 9
Tracking probability over 80 s.


## 7. Conclusion and Future Work

In this paper, we proposed a privacy-preserving authentication scheme for secure communication in VANETs. The proposed MPCPA introduces an anonymous authentication mechanism to preserve the privacy of the vehicles. Furthermore, a mix-context-based cooperative pseudonym changing mechanism protects the location of vehicle users. The proposed authentication scheme is efficient in terms of its computational complexity. Our evaluation demonstrated that MPCPA greatly reduces computational overhead and provides an efficient means for preserving the privacy of vehicles.In future research, we will study cooperative message verification and batch signature verification to reduce computational overhead further, and we will subject our scheme to extensive experimentation to verify its authentication scheme. It is noteworthy that the proposed MPCPA is not independent from the RSU. Consequently, we will consider ways of carrying out privacy preserving authentication without the need for the RSU.



---

*Source: 3109238-2019-06-02.xml*