Sage Journals: Discover world-class research

Abstract

In Internet of Vehicles, establishing swap zones in which vehicles can exchange pseudonyms is an effective method to enhance vehicles’ location privacy. In this article, we propose a new scheme based on dynamic pseudonym swap zone, to protect location privacy of vehicles. For each vehicle, dynamic pseudonym swap zone allows it dynamically to establish a temporary pseudonym swap zone on demand to exchange the pseudonym with another random vehicle in the just formed zone. This randomness of choosing the pseudonym exchanging vehicles prevents dynamic pseudonym swap zone from the secure risk that the information of exchanging participants exposes to their group manager in some existing works in which each pair of pseudonym exchanging participants is assigned by the manager. To avoid the high communication and computation overhead of frequently swapping pseudonyms, dynamic pseudonym swap zone adopts a combination of swap and update to achieve the unlinkability between new and previous pseudonyms. Moreover, dynamic pseudonym swap zone can self-adapt to the varying surroundings to reduce the communication cost of forming pseudonym swap zones in high vehicle density areas. The analysis and simulation results show that our proposed dynamic pseudonym swap zone is a high location privacy preserving, secure, auditable scheme.

Keywords

Internet of Vehicles location privacy protection pseudonym swap dynamic swap zone

Introduction

As a typical application of Internet of Things technology in intelligent transportation system, Internet of Vehicle (IoV)^1–3 can support intelligent traffic management, intelligent dynamic information service, and vehicle intelligent control. To achieve these services, it is essential for vehicles to periodically broadcast safety beacon that contains information such as vehicle identity, location, and driving status transmitted by the Dedicated Short-Range Communication (DSRC). However, such information is vulnerable to exploitation and brings with location privacy and security risks. For example, eavesdroppers can utilize the information to track specific vehicles through reconstructing these vehicles’ trajectory to a certain extent with multi-target tracking technology.⁴

Wireless communications between vehicles are provided by the DSRC, referred to as IEEE Standard 802.11.⁵ DSRC is an efficient wireless communication technology that enables the identification and two-way communication of mobile targets in specific small areas. Two types of DSRC are used in this paper, including vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I). The safety of passengers is increased by exchanging safety relevant information via inter-vehicle communication (IVC). The safety messages could be categorized in two types: periodic beacon safety messages and event announcing safety messages.⁶ The former is some warning messages and has some sort of preventive role against possible incident. The latter is some of the messages which the vehicles issue when it detects an unsafe condition, for example, a car crash, icy surface. In summary, event announcing messages are sent in an unsafe situation, but the preventive messages are issued periodically by all the vehicles. In this article, the location information of neighboring vehicles is obtained through periodic beacon safety messages.

In order to enhance the location privacy of vehicles, many fruitful approaches have been proposed in recent years. Among them, it is a feasible and effective strategy to use pseudonyms to conceal vehicles’ real identities and provide unlinkability of new and previous pseudonyms. In some schemes,^7–9 each vehicle needs to store a large number of anonymous certificates in advance and changes its pseudonym in fixed mix-zones which are carefully selected and are generally road intersections. These methods have to deal with storing and managing too many anonymous certificates, and the limitation that vehicles are allowed only to change pseudonyms in fixed zones make these schemes lack of necessary flexibility. To increase the flexibility of changing pseudonyms, several schemes such as dynamic mix-zone for location privacy (DMLP),¹⁰ pseudonym changes based on candidate-location-list (PCC),¹¹ and cooperative pseudonym change based on neighbors (CPN)¹² have been proposed to form dynamic mix-zones to enhance the location privacy of vehicles. The schemes, however, are still based on pseudonym change approach that cannot provide high location privacy protection, especially where the vehicle density is low.

To further improve the location privacy of vehicles, the SlotSwap scheme proposes the idea of pseudonym exchange that allows a vehicle to select one of its appropriate one-hop neighbor vehicles to exchange pseudonyms in hot spots with high vehicle density.¹³ SlotSwap only supports one-to-one pseudonym exchange rather than exchanging in groups formed by vehicles, which limits its privacy preserving performance to certain extent. In pseudonym swapping scheme based on neighboring vehicles (PSNV),¹⁴ vehicles are allowed to dynamically form groups in which group members can exchange pseudonyms. However, since every pair of vehicles that exchange their pseudonyms with each other is assigned by the group manager, PSNV may expose a vulnerability to the location privacy of group members when a malicious vehicle becomes group manager. Memon¹⁵ proposed that distance and cluster-based energy pseudonyms would change method for road network. It proposed scheme would reduce consumption, but the existence of cluster heads remains a security risk for cluster group members.

To avoid the mentioned weaknesses in the existing pseudonym exchange schemes, we propose the location privacy-preserving scheme based on dynamic pseudonym swap zone (DPSZ), in this article. DPSZ allows each vehicle dynamically to establish a temporary pseudonym swap zone on demand to swap pseudonyms with another random vehicle in the zone. When a vehicle has pseudonym update demand, it will check whether the number of such vehicles, which are among its neighbors and can guarantee the continuous communication with it until to complete the whole procedure of pseudonym swap, is more than the preset threshold. If so, the vehicle will establish a pseudonym swap zone, and respectively perform a pseudonym swap procedure with every other vehicle in the zone. Among all the above pseudonym swaps, there is one and only one that is real swap, and the other swaps are all fictitious. That ensures that the attacker cannot conclude whether the current vehicle swapped its pseudonym and which vehicle in the zone swapped the pseudonym with the current vehicle no matter using the time sequence or the number of the pseudonym swap messages. Moreover, DPSZ can self-adapt to the varying surrounding vehicle density to reduce the communication overhead of establishing pseudonym swap zone.

The main contributions of this article are summarized as follows:

We have proposed a new scheme DPSZ that can achieve high location privacy protection performance through exchanging pseudonyms in swap zones formed dynamically.

Our proposed DPSZ can avoid the secure risk that is brought about by the group manager in the existing works when assigning the exchanging participants. Moreover, DPSZ can also achieve the auditability.

We have introduced the combination of pseudonym swap and update, as well as the method of self-adaptive surroundings to reduce the communication and computation overheads.

In order to ensure the security of data transmission, we have adopted a scheme for generating dynamic encryption keys. The secret key is dynamically formed using the Diffie–Hellman key exchange protocol and used for encryption of private data.

We have evaluated the performance of DPSZ scheme through simulation experiments and compared it with some existing methods. Our analysis also shows that the proposed method is superior to the existing methods in different experimental environments.

The remainder of this article is organized as follows. Section “Related work” reviews the important and typical location privacy preserving works. Section “System model” introduces the system architecture, giving the details of the security model. In section “Pseudonym swapping scheme based on dynamic swap zone,” we present our proposed DPSZ scheme along with detailed dynamic swap zone forming, and pseudonym exchanging algorithms. The evaluation of our proposed system using simulation is presented in section Performance evaluation. Section “Conclusion” concludes the article.

Related work

In recent years, many meaningful research works have already been reported to enhance location privacy of IoV. We survey the existing schemes of location privacy protection for IoV in this section. These existing schemes are reviewed in six parts: mix-zones schemes, silent period approaches, group signature approaches, third-party agent, obfuscation-based schemes, and pseudonym swapping schemes:

Mix-zones schemes: The location privacy of vehicles is protected by anonymous communication zones, that is, mix-zones.¹⁰ The mix-zones are mainly traffic intersections where vehicles’ speed and directions are highly possible to change. During vehicles drive in mix-zones, they update their pseudonyms and are not allowed to send messages. Therefore, it is difficult for attackers to track the target vehicles from the vehicles that are in the same mix-zone, especially when the zone has high vehicle density.

Ying et al.¹¹ proposed PCC scheme that allows vehicles to form mix-zones dynamically and change their pseudonyms through candidate location list. Memon et al.¹⁶ and Arain et al.¹⁷ introduced strategies for multi-mixing regions based on dynamic pseudonyms. One scheme is to encourage each vehicle to change pseudonym dynamically inside as well as outside a mix-zone over the road network.¹⁶ Another scheme requires mobile vehicles to communicate with reported server for registration and dynamically pseudonym change.¹⁷ Arain et al.¹⁸ presented a protocol named as clustering-based energy-efficient and communication protocol (CEECP) for multiple mix-zones over road networks, which is proposed to reduce the loop holes of prevailing clustering protocols. Lu et al.^19,20 proposed a pseudonym change method based on social point to enhance location privacy of vehicles. Here, a social point refers to an area where vehicles gather temporarily, for example, a traffic intersection or a parking. If each vehicle changed its pseudonym before it drives out of a social point, then the social point can be regarded as a mix-zone. When the density of vehicles is high at a social point, it is difficult for attackers to track specific vehicles if all vehicles in the social point change their pseudonyms simultaneously. When the vehicle density of a social point is low, however, the two schemes cannot achieve satisfied location privacy protection performance. Due to that the performance of location privacy protection in mix-zones schemes depends on the number of vehicles in a same zone, it is a main challenge to form secure mix zones in environment of low vehicle density.

Silent period approaches: In view of the limitations of mix-zone scheme, some researchers used silent period approach in which vehicles choose a certain silent period and change their pseudonyms without the help of specialized traffic infrastructures. Sampigethaya et al.²¹ proposed AMOEBA scheme to achieve unlinkability between the new and old pseudonyms of vehicles by keeping the vehicles to remain a random silent period. In SLOW,²² vehicles are not allowed to broadcast messages once their speeds are less than a threshold (e.g. 30 km/h), and the vehicles can change their pseudonyms in the situation of low driving speeds. Generally, the random silent period scheme is efficient in protecting location privacy. However, the maximum silent period is limited by the safety beacon broadcast period and it is possible to track vehicles by inferring the temporal and spatial relationship of vehicles.¹⁴

Group signature approaches: In group signature scheme,^23–25 some vehicles form a group in which the members of the group are able to anonymously sign messages on behalf of the entire group. The group signatures can be verified conveniently by the group public key, and nobody except the group manager can track the signer through the corresponding group signatures. For example, the authors proposed a MixGroup approach to enhance vehicles’ location privacy.²³ Through utilizing group signature mechanism, MixGroup approach allows vehicles to establish extended pseudonym-changing regions to exchange the pseudonyms. The continuous exchange of pseudonyms can increase the uncertainty of pseudonym mixing. However, for the group manager knows all the memberships and the identity of every group member, it will lead to huge security risk once the group manager is compromised or held by a malicious node. Moreover, it is a challenging task to manage all the group members efficiently when the size of a group is too large. Perera et al., proposed a new group signature scheme,²⁴ which combines the member revocation mechanism with member registration and construct a fully dynamic group signature that supports manipulation of member revocation through verifier-local revocation (VLR). Group signatures require controllable linkability, so a new group signature scheme that supports controllable linkability is proposed.²⁵ The scheme generates a short signature by constructing a dynamic privacy-protecting signature scheme with both opening and linking capabilities. The short signature generated by the construct is even shorter than this in the best-known group signature scheme.

Third-party agent approaches: In order to reduce the high computation cost brought by too encryption operations in many location privacy protection schemes, some researchers proposed third-party agent approaches.^26,27 These approaches allow vehicles to send messages through a trusted third-party proxy. The approaches achieved the goal of location privacy protection by hiding the identities of individuals within the groups established by the trusted proxies. Although the type of agent pattern ensures sending messages disguisedly, the trusted proxies are prone to become the performance bottleneck of the whole location privacy preserving system when taking their heavy work burden into consideration.

Static and dynamic pseudonyms: The static and dynamic pseudonyms here refer to the way how to obtain pseudonyms. The static pseudonyms are created by a pseudonym issuing authority and stored inside the vehicles. Dynamic pseudonyms refer to that the pseudonyms are dynamically generated by the vehicles themselves. Eckhoff et al.¹³ and Petit et al.²⁸ used static pseudonyms. When all the pseudonyms stored in the vehicles expired, the vehicles need to obtain the new pseudonyms from the pseudonym issuing authority.²⁸ Another strategy is to set up a pseudonym pool and update it by pseudonym exchange.¹³ The pseudonyms in the pseudonym pool can be reused. Vehicles obtain the self-issuance’s authority from the trusted authority, so that the pseudonym can be dynamically generated.^29,30 They generate dynamic pseudonyms using the dynamic pseudonym trust management method and the method of sending authorized anonymous keys to the vehicles. In contrast to static pseudonyms, dynamic pseudonyms have the advantage that once the vehicles complete the corresponding initialization operation, the vehicles can autonomously perform the generation of the pseudonyms. However, in the methods of dynamic pseudonyms, many pseudonyms are generated by the same key obtained from CA. Once the key is compromised, all its derived pseudonyms are likely to be revealed. Moreover, it will bring additional computational overhead for the vehicles to generate pseudonyms.

Pseudonym swapping schemes: To enhance the location privacy of vehicles, the authors proposed the idea of pseudonym exchange that allows a vehicle to select one of its appropriate one-hop neighbor vehicles to exchange pseudonyms in hot spots with high vehicle density.¹³ However, SlotSwap scheme only supports one-to-one pseudonym exchange rather than exchanging in groups formed by vehicles, which limits its privacy preserving performance to certain extent. Li et al.³¹ proposed swing and swap schemes to enhance location privacy of vehicles. The main idea of the scheme is that vehicles exchange their identifiers with each other and then keep a silent time with random length. Memon et al.³² presented an efficient pseudonym change strategy with multiple mix-zones scheme. This strategy builds extended pseudonym-changing regions, namely mixed zones, in which vehicles are allowed to use their identities instead of pseudonyms, and to accumulatively swap their pseudonyms with each other. However, the use of identity communication directly in the mix-zones poses a risk of disclosure of the identity information of the vehicles. Zhang et al.¹⁴ proposed PSNV scheme in which vehicles are allowed to dynamically form groups in which group members can exchange pseudonyms. The conditions for vehicles to construct a pseudonym swap group are that their driving directions are the same, and their speeds and positions are close. Since every pair of vehicles that exchange their pseudonyms with each other is assigned by the group manager, PSNV may pose threat to the location privacy of group members when a malicious vehicle becomes group manager.

System model

System architecture

The system consists of two parts: vehicle subnet and service infrastructure. The vehicle subnet is an ad hoc network that is connected by on-board units (OBUs) installed in vehicles. The service infrastructure consists of a certificate authority (CA) and many road-side units (RSUs). For vehicles, the heterogeneous network architecture includes two types of communication: V2V, V2I, as shown in Figure 1. For simplicity, we regard the wireless channel in this study as the ideal one without packet loss.

Figure 1.

System architecture.

CA is responsible for managing the identities and credentials of RSUs and OBUs in the region. It also manages the generation and cancelation of vehicles’ pseudonyms and certificates. RSUs are responsible for receiving requests from OBUs, relaying the requests to CA, and transmitting the replies of CA to OBUs. The symbols used in this article are listed in Table 1.

Table 1.

Notations.

Symbol	Description
$I D_{i}$	Real identity of vehicle $v_{i}$
$K_{i}$	Secret key shared by $v_{i}$ and CA
$PI D_{i}, P K_{i}$ , $S K_{i}$ , $Cer t_{i}$	Pseudonym, public, private key and certificate that $v_{i}$ obtains form CA
Hash()	Hash functions of generating pseudonyms
$PI D_{i, k}$	Kth pseudonym that $v_{i}$ generates by Hash(), $PI D_{i},$ and $K_{i}$
$ξ$	Attack strength of the attacker
$p$	Probability that a vehicle being tracked by the attacker
$Γ_{s}$	Threshold of vehicle number to establish a pseudonym swap zone
$t_{i, j}$	Link expiration time between the two vehicles
$Γ_{t}$	Threshold of time to complete a pseudonym swap
$x_{i}, x_{j}, g, P$	Used to generate a secret key common parameters between $v_{i}$ and $v_{j}$
$K_{i, j}$	Session key shared by v_i and v_j to encrypt pseudonym swap data
$p_{t}$	Probability that the eligible vehicles respond a request to establish pseudonym swap zone
$ψ_{i}$	The neighbor vehicle set of the vehicle $v_{i}$
REQ	Pseudonym swap request
REP	Pseudonym swap request reply
$t s_{i}$	Timestamp of step i

CA: certificate authority.

Threat and trust models

The assessment criterion for location privacy is always related to the ability of attackers to track a target vehicle in the network. We assume that there is a global passive attacker who can eavesdrop on every message sent across the network. Nevertheless, the attacker does not know the details of the message if the message is encrypted. We also assume that the attacker knows all the maps between each vehicle and its true identification completely.

We use the probabilistic attacker model:¹³ Assume that the probability of an attacker to track a pseudonym exchange between two nodes is $ξ \in [0.5, 1)$ . During driving, a target vehicle can randomly establish a swap zone which is indicated as $U = {v_{1}, v_{2}, v_{3}, \dots, v_{n}}$ . When a pseudonym exchange occurs in the swap zone, the probability for the attacker to successfully track the exchange can be calculated as follows

p = \frac{ξ}{ξ + (| U | - 1) \times (1 - ξ)}

(1)

According to equation (1), when the swap zone of the target vehicle is composed of six vehicles and the attacker’s ability is weak, for example, $ξ = 0.5$ , the probability that the target vehicle is tracked is about $p = 0.17$ .

In this article, we assume that CA is honest, and the RSUs are semi-honest, and the OBUs are dishonest. Moreover, we assumed that CA and every RSU has strong physical security and cannot be breached easily. Honest members are protected by abundant security mechanism and not controlled by attackers. Moreover, honest members do not attack other members and not collect or disseminate the privacy of other members. Semi-honest members are roughly the same as honest members. However, unlike honest members, semi-honest members may collect user privacy.³³ The RSUs are the communication medium between OBUs and CA, so we believe that RSUs are semi-honest. The CA has the registration information of all members. If the CA becomes an attacker, the threat it poses will be much greater than other roles, so the CA must be handled by the official trusted authority, and we believe that it is honest.

Pseudonym swapping scheme based on dynamic swap zone

In this section, we will detail the proposed DPSZ scheme that includes four phases: registration, pseudonym update, pseudonym swapping, and pseudonym swap log uploading.

Registration

When joining the network for the first time, each vehicle, for example, $v_{i}$ must register with CA. After registered, a vehicle must login to CA each time when the vehicle starts up to run on the road, and request a different pseudonym $PI D_{i}$ , a pair of public and private keys $P K_{i}, S K_{i}$ and the corresponding certificate $Cer t_{i}$ . Moreover, $v_{i}$ needs to request a secret key $K_{i}$ to generate derived pseudonyms. With the key $K_{i}$ , $v_{i}$ can use Hash function to generate a set of derived pseudonyms by iteration. Let $PI D_{i}$ be the pseudonym of vehicle $v_{i}$ , its first derived pseudonym $PI D_{i, 1}$ is generated by a one-way Hash function based on the pseudonym and the key $K_{i}$ , and the subsequent pseudonym is generated by the Hash function based on the previous derived pseudonym and secret key. The generation process of derived pseudonyms is as follows:

\begin{matrix} PI D_{i, 1} = Hash (PI D_{i}, K_{i}) \\ PI D_{i, 2} = Hash (PI D_{i, 1}, K_{i}) \\ ⋮ \\ PI D_{i, k} = Hash, (PI D_{i, k - 1}, K_{i}) \end{matrix}

Without the secret key $K_{i}$ , it is computationally infeasible for the attacker to establish a linkage between the derived pseudonyms and the pseudonym $PI D_{i}$ .

Pseudonym update

In IoV, vehicles need to broadcast safety beacons periodically, which is the base of many applications. To protect the location privacy, vehicles can use pseudonyms in their safety beacons and even in communication with other vehicles and RSUs. In the proposed DPSZ, each vehicle, for example, $v_{i}$ , just uses its pseudonym hash chain to achieve privacy protection. At first,v_i uses the last one of its hash chain, i.e. PID_i,k, as its pseudonym. Then, v_i periodically updates its pseudonym by using the pseudonym’s previous one in the hash chain to replace itself, i.e., replacing PIDi,k with its previous one PID_i,k-1, and so on. If a vehicle remains its current pseudonym unchanged for a long time, the risk that its location privacy is exposed to attackers will remarkably increase. On the other hand, to save storage space, the size of its hash chain is limited and the derived pseudonyms will be used up after a certain period. Therefore, the pseudonyms of vehicles will be swapped to further improve location privacy protection and solve the problem that the number of the derived pseudonyms is limited. When over a half of derived pseudonyms in the hash chain have been used, the windows of pseudonym swapping will be opened. Opening a pseudonym swap window is a signal that the current vehicle is allowed to launch a new pseudonym swap. This signal is unknown to other vehicles, for they cannot know how many derived pseudonyms the current vehicle have used so far.

Pseudonym swapping

To complete pseudonym swap, there are four steps need to be done as shown in Figure 2. Among them, Steps 1 and 2 are utilized to establish a swap zone, and meanwhile to generate a session key by the embedded improved Diffie-Hellman key exchange protocol.³⁴ The session key is used to protect the following procedure of pseudonym swapping. Steps 3 and 4 are the procedure of pseudonym swapping. Algorithm 1 describes the overall process of the pseudonym swap algorithm and marks the parts of each step.

Figure 2.

Pseudonym swapping based on dynamic swap zone.

Algorithm 1. Pseudonym swap.
Input: $v_{i}, Φ_{i}$ , $Γ_{t}$ , $Γ_{s}$ , $ψ_{i}$ Output: pseudonyms swapped 1 Initialization: $k \leftarrow 1$ , $ψ_{i} \leftarrow NULL$ 2 while $v_{k} \in Φ_{i}$ do 3 $t_{i, k} \leftarrow$ calculated by formula (2) 4 if $t_{i, k} \geq Γ_{t}$ do 5 $v_{k}$ is added to the collection $ψ_{i}$ Step 1 6 end if 7 $k \leftarrow k + 1$ 8 end while 9 if $\| ψ_{i} \| \geq Γ_{s}$ do 10 $v_{i}$ broadcast establishing pseudonym swap zone message which includes swap request, $y_{i}$ , $P$ , and g. 11 for all $v_{k} \in ψ_{i}$ do 12 $k_{i, k} \leftarrow$ calculated by formula (6) Step 2 13 reply to $v_{i}$ , the message includes the value of swap, $y_{k}$ and $t s_{1}$ . swap and $t s_{1}$ encrypted by $k_{i, k}$ . 14 end for 15 $v_{r} \leftarrow v_{r} \in ψ_{i}$ and the value of swap is true Step 3 16 $k_{i, r} \leftarrow$ calculated by formula (6) 17 $v_{i}$ broadcast the pseudonyms swap data which encrypted by $k_{i, r}$ , including $PI D_{i}$ , $S K_{i}$ , $P K_{i}$ , and $Cer t_{i}$ . 18 for all $v_{k} \in ψ_{i}$ do 19 $m \leftarrow$ calculated by formula (7) 20 if $m$ is available data do 21 $v_{k}$ reply $PI D_{k}$ , $S K_{k}$ , $P K_{k}$ and $Cer t_{k}$ to $v_{i}$ . The pseudonyms swap data which encrypted by $k_{i, k}$ . Step 4 22 else reply the invalid data of the same size as the swap data to $v_{i}$ . The invalid data which encrypted by $k_{i, k}$ . 23 end if 24 end for 25 end if

Algorithm 1. Pseudonym swap.

Input:

v_{i}, Φ_{i}

, $Γ_{t}$ , $Γ_{s}$ , $ψ_{i}$
Output: pseudonyms swapped
1 Initialization: $k \leftarrow 1$ , $ψ_{i} \leftarrow NULL$
2 while

v_{k} \in Φ_{i}

do
3

t_{i, k} \leftarrow

calculated by formula (2)
4 if

t_{i, k} \geq Γ_{t}

do
5

v_{k}

is added to the collection

ψ_{i}

Step 1 6 end if
7

k \leftarrow k + 1

8 end while
9 if

| ψ_{i} | \geq Γ_{s}

do
10

v_{i}

broadcast establishing pseudonym swap zone message which includes swap request,

y_{i}

P

, and g.
11 for all

v_{k} \in ψ_{i}

do
12

k_{i, k} \leftarrow

calculated by formula (6)
Step 2 13 reply to

v_{i}

, the message includes the value of swap,

y_{k}

and

t s_{1}

. swap and

t s_{1}

encrypted by

k_{i, k}

.
14 end for
15

v_{r} \leftarrow v_{r} \in ψ_{i}

and the value of swap is true
Step 3 16

k_{i, r} \leftarrow

calculated by formula (6)
17

v_{i}

broadcast the pseudonyms swap data which encrypted by

k_{i, r}

, including

PI D_{i}

S K_{i}

P K_{i}

, and

Cer t_{i}

.
18 for all

v_{k} \in ψ_{i}

do
19

m \leftarrow

calculated by formula (7)
20 if

m

is available data do
21

v_{k}

PI D_{k}

S K_{k}

P K_{k}

and

Cer t_{k}

v_{i}

. The pseudonyms swap data which encrypted by

k_{i, k}

.
Step 4 22 else reply the invalid data of the same size as the swap data to

v_{i}

. The invalid data which encrypted by

k_{i, k}

.
23 end if
24 end for
25 end if

To ensure the security of swapping pseudonym, before initializing a request to establish a swap zone, vehicles first judge whether their surroundings satisfies the two conditions as follows:

Condition 1: link continuous connected time

In IoV, vehicles have high mobility, and thus, the links between vehicles are dynamic, volatile, and intermittent. It is necessary to compute the continuous connected time of every pair of vehicles that prepare to swap their pseudonyms. For a vehicle $v_{i}$ , it can know the coordinate, speed, and direction information of any one of its neighbor vehicles, for example, $v_{j}$ , from the beacon message broadcasted by $v_{j}$ . According to the method,³⁵ $v_{i}$ can compute the length of the continuous connected time between it and $v_{j}$ as follows

t_{i, j} = \frac{- (ab + cd) + \sqrt{(a^{2} + c^{2}) r^{2} - {(ad - bc)}^{2}}}{a^{2} + b^{2}}

(2)

where the meanings of a, b, c, and d are respectively showed as below: $a = s_{i} \cos θ_{i} - s_{j} \cos θ_{j}$ , $b = x_{i} - x_{j}$ , $c = s_{i} \sin θ_{i} - s_{j} \sin θ_{j}$ , and $d = y_{i} - y_{j}$ . Here, ( $x_{i}, y_{i}$ ) and ( $x_{j}, y_{j}$ ), $s_{i}$ and $s_{j}$ , $θ_{i}$ and $θ_{j}$ are the coordinates, speeds and directions of $v_{i}$ and $v_{j}$ , respectively. The distance of the two vehicles is r.

To complete the procedure of forming a swapping zone and exchanging pseudonyms, we need a threshold to judge whether there is enough continuous connected time between the vehicles that will take part in the swapping zone. For the whole procedure of forming swapping zone and exchange pseudonyms consists of four steps: establishing request broadcast, join reply, pseudonym swapping broadcast, and pseudonym swapping reply. Therefore, the threshold time, indicated as $Γ_{t}$ , can be expressed as

Γ_{t} = 2 t_{b} + 2 Γ_{s} t_{r}

(3)

where $t_{b}$ is the time period from broadcasting a message until being received by one-hop neighbor vehicles, and $t_{r}$ is the time period from sending a message to being received one of neighbor vehicles. The two values, that is, $t_{b}$ and $t_{r}$ , can be obtained by the methods.³⁶ Since a swap zone consists of $Γ_{s}$ vehicles at least, $v_{i}$ has to take $Γ_{s} t_{r}$ at least to receive the replay messages from its neighbors in each of the two replay phases.

In order to judge whether there will be a link between the vehicles $v_{x}$ and $v_{y}$ which can support them to complete a procedure of pseudonym swap, we need to calculate the link continuous connected time $t_{x, y}$ according to the beacon messages, and then check that whether $t_{x, y}$ is not less than $Γ_{t}$ . If so, the link between $v_{x}$ and $v_{y}$ will satisfy the condition of link continuous connected time.

Condition 2: size of pseudonym swap zone

The size of DPSZ, that is, the number of vehicles that participate and form the swap zone, has an important influence on the strength of unlinkibility of the exchanged pseudonyms. It is obvious that the larger the size of the pseudonym swap zone is, the lower the probability for vehicles to be tracked is. However, due to the dynamic distribution of vehicles in IoV, when a vehicle has the requirement of swapping pseudonym, there are not always enough neighbor vehicles for it to form a swap zone. Therefore, we need to determine the threshold of swap zone size, indicated as $Γ_{s}$ , in order to ensure the security of pseudonym swap when the size of a swap zone is not less than $Γ_{s}$ . According to equation (1), the threshold value $Γ_{s}$ can be determined through the probability of being tracked $p$ by the attacker with different attack strengths $ξ$ . Figure 3 shows the relationship between the probability of being tracked $p$ , the threshold $Γ_{s}$ , and the attack ability $ξ$ . As can be seen from this figure, the larger $Γ_{s}$ needs to be, when the higher the probability of being tracked is, and the stronger the attacker’s ability is. When the values of $p$ and $ξ$ are known, for example, $p = 0.2$ and $ξ = 0.5$ , the size of $Γ_{s}$ can be determined, that is, $Γ_{s} = 5$ .

Figure 3.

Threshold $Γ_{s}$ under different possibility of being tracked $p$ and different attack strengths.

When a vehicle $v_{i}$ has pseudonym swap need, it first checks whether its surrounding satisfies the two conditions above. Let $Φ_{i}$ be the neighbor vehicle set of $v_{i}$ , then the set consisted of the vehicles which have adequate link continuous connected time with $v_{i}$ can be indicated as

ψ_{i} = {v_{j} | \forall v_{j} \in Φ_{i}, t_{i, j} \geq Γ_{t}}

(4)

If $| ψ_{i} | \geq Γ_{s}$ , which shows $v_{i}$ can establish a swap zone with secure size, then $v_{i}$ begins to initialize a request of establishing pseudonym swap zone as follows:

Step 1: request of forming pseudonym swap zone

The initiating vehicle $v_{i}$ randomly selects a large prime number $P$ , a primitive element g and a random number $x_{i}$ , and calculates $y_{i}$ according to formula (5)

y_{i} = g^{x_{i}} \mod P

(5)

Use the current pseudonym $PI D_{i, k}$ to broadcast the pseudonym swap request, $y_{i}$ , $P$ , g and timestamp $t s_{1}$ . Before broadcasting the message, the vehicle node must first encrypt the message with the private key $S K_{i}$ and then digitally sign $Sig n_{m}$ the encrypted message, and attach the public key $P K_{i}$ in message. Vehicles which receive this message can validate its origin.

Step 2: reply to form pseudonym swap zone

After receiving the broadcast message of the initiating vehicle, the neighboring vehicle $v_{j}$ determines whether the initiating vehicle is a malicious node by the digital signature. After determining the security of the initiating vehicle, it is checked whether the link continuous connected time with the requester satisfies the condition. If the link continuous connected time is satisfied, a number is randomly selected as $x_{j}$ , a common secret key $K_{i, j}$ with the originating vehicle is calculated according to formula (6)

K_{i, j} = {y_{i}}^{x_{j}} \mod P = g^{x_{i} x_{j}} \mod P

(6)

The neighbor vehicle $v_{j}$ replies to the initiating vehicle with the current value of swap, the value of $y_{j}$ , and timestamp $t s_{2}$ . If the swap condition is not met, no reply will be made. $v_{j}$ replies that the value of swap is true, which means that $v_{j}$ can perform pseudonym swap. Conversely, a reply with the value of swap is false means that $v_{j}$ cannot perform pseudonym swap or other reasons at the current time. For the security of the data, the reply message is encrypted using the common secret key $K_{i, j}$ of $v_{j}$ .

Step 3: broadcast of pseudonym swap data

After the initiating vehicle receives the reply messages, the initiating vehicle needs to count the return information of the vehicles in the pseudonym swap zone and establish a separate secret key $K_{i, j}$ with each vehicle in the zone by the return value $y_{j}$ . The initiating vehicle $v_{i}$ randomly selects a vehicle $v_{r}$ from the vehicles whose return information is true for pseudonym swap. The initiating vehicle $v_{i}$ transmits pseudonym swap data to the vehicle $v_{r}$ by means of broadcasting, and the swap data include the pseudonym $PI D_{i}$ , key pair $S K_{i}$ and $P K_{i}$ , timestamp $t s_{3}$ . Please note that the secret key $K_{i}$ is not allowed as a swapped data. We encrypt the broadcast content with the secret key $K_{i, r}$ formed by the initiating vehicle $v_{i}$ and the vehicle $v_{r}$ . Only the vehicle $v_{r}$ can decrypt the broadcast content, and the other members in the zone cannot get valid data by decrypting the broadcast content. The initiating vehicle needs to digitally sign the encrypted message before broadcasting, so the vehicles which receive the message can validate its origin.

Step 4: reply of pseudonym swap data

After receiving the encrypted swap data message broadcasted by $v_{i}$ , the vehicles in the zone first verify the digital signature of the message. After the verification is passed, the decryption operation is performed according to formula (7)

m = c \times {({y_{i}}^{x_{r}})}^{- 1} \mod P

(7)

Obviously, only vehicle $v_{r}$ can decrypt the encrypted data. Then $v_{r}$ encrypts its own swap data $PI D_{r}$ , $S K_{r}$ , $P K_{r}$ , $Cer t_{r}$ and timestamp $t s_{4}$ by secret key $K_{i, r}$ and sends the data to the originating vehicle $v_{i}$ . Even though other members in the pseudonym swap zone cannot decrypt the encrypted data from $v_{i}$ , each of them needs to encrypt an invalid data with the same size as the one sent by $v_{r}$ through its own session key, and to transmit to $v_{i}$ . For all vehicles in the pseudonym swap zone respectively return a same size message to $v_{i}$ , it is difficult for the attacker to judge which vehicle has swapped the actual pseudonym with $v_{i}$ from the number and sequence of communication between the vehicles.

Pseudonym swap log uploading

After the vehicles swap their pseudonyms successfully, CA can no longer associate the pseudonyms with the real identity of the vehicles, which conflicts with the secure demand of detecting and handling vehicles with misbehaviors. Therefore, it is obligatory for the initiating vehicle to upload the pseudonym swap log to CA each time after exchanging the pseudonyms. Utilizing the logs, CA can rebuild the map between the real identities and the swapped pseudonyms of the vehicles. In DPSZ, once the procedure of swapping pseudonym is completed, the pseudonym swap log of the initiating vehicle will be transmitted to the CA. The log includes that the pseudonym identities of both parties involved, that is, $PI D_{i}$ and $PI D_{r}$ , and timestamp $t s_{5}$ , which is encrypted through the session key $K_{i, r}$ shared by $v_{i}$ and $v_{r}$ . Moreover, $v_{i}$ encrypts the above information by the shared key $K_{i}$ , and adds it into the log. The detailed content of the log message and the procedure of updating is shown in Figure 4.

Figure 4.

Pseudonym swap log uploading.

For the openness of wireless channel, $v_{r}$ can receive the log message sent by $v_{i}$ , and check whether $v_{i}$ uploads the correct information about the completed swap. If $v_{r}$ did not receive the log message until it drives out of the communication range of $v_{i}$ , then it would think that something went wrong. Thus, $v_{r}$ sends an accusing message about the pseudonym procedure to CA after waiting a random period of time. After receiving the log sent by $v_{i}$ , CA first verifies whether ${PI D_{i}, PI D_{r}, t s_{1}}_{K_{i, r}}$ is identical to the one that includes in the part information encrypted by $K_{i}$ and checks the novelty of the timestamp $t s_{5}$ . Then CA waits a preset period of time and checks whether receives an accusing message from $v_{r}$ . If all goes well, then the CA would update the mapping between the real identifiers and the pseudonyms for $v_{i}$ and $v_{r}$ . Otherwise, CA would check whether one or both of the two vehicles $v_{i}$ and $v_{r}$ misbehaved. If CA affirms that there is a misbehavior by one of the two vehicles, for example, $v_{i}$ , then CA will take steps as follows: (1) expel $v_{i}$ from the system; (2) put it in the blacklist; (3) revoke the public certificate of $v_{i}$ ; (4) cancel the pseudonym swap, and inform the victim to login again to obtain a new pseudonym, certificate, and shared key (for example, $v_{r}$ is the victim, then $v_{r}$ will log in to the CA and re-acquire the $PI D_{r}$ , ${Cert}_{r}$ and $K_{r}$ . After that, it will update and swap of the pseudonym according to the new data).

Self-adaptive communication surroundings

In DPSZ, all neighbor vehicles, which have eligible link continuous connected time with the initiating vehicle, are required to reply to the requirement message and to participate in the swap zone. When the initiating vehicle is in some areas, for example, intersections, where the density of vehicles is high, the vehicle number of participating the swap zone could be large, which will result in too high communication and computation costs. To solve the problem, we improve Steps 1 and 2 of pseudonym swapping protocol of DPSZ and make DPSZ implement self-adaptive communication surroundings.

In Step 1, the initiating vehicle adds the number of its eligible neighbor vehicles, that is, $| ψ_{i} |$ , into the broadcast message of establishing swap zone. In Step 2, based on the important information $| ψ_{i} |$ , each neighbor vehicle that has eligible link continuous time can calculate the reply probability $p_{r}$ by equation (8)

p_{r} = {\begin{matrix} 1, | ψ_{i} | = Γ_{s} \\ e^{1 - \frac{| ψ_{i} |}{Γ_{s}}}, | ψ_{i} | > Γ_{s} \end{matrix}

(8)

Equation (8) can ensure the eligible neighbor vehicles reply with high probability when $| ψ_{i} |$ is equal to or slightly more than $Γ_{s}$ . When $| ψ_{i} |$ is greater than $Γ_{s}$ , the probability $p_{r}$ is controlled to reduce. And the larger the $| ψ_{i} |$ is, the smaller the $p_{r}$ is.

Security analysis

In this section, we analyze the main secure goals that our proposed DPSZ can satisfy as follows:

Conditional anonymity. In all communication processes except loginning to CA each time when a vehicle, for example, $v_{i}$ , starts up, it uses pseudonyms instead of its real identity to communicate with other vehicles. The pseudonyms of vehicles include two types: the one obtained from CA, and these generated by one-way hash function. For example, as to $v_{i}$ , its pseudonyms include $PI D_{i}$ and $PI D_{i, 1}, PI D_{i, 2}, \dots, PI D_{i, k}$ . Therefore, for any one vehicle, no other vehicles, RSU, or attackers can obtain its real identify except CA.

Unlinkability. In order to maintain the location privacy of vehicles, it is necessary for each vehicle, for example, $v_{i}$ , to ensure the unlinkability between its current pseudonym and the previous pseudonyms. As the pseudonyms are generated by a one-way hash function, the attacker without the secret key $K_{i}$ that is only shared by and CA cannot infer the relationship between the current pseudonym and the previous pseudonyms. Even when $v_{i}$ swapping with the pseudonyms with another vehicle, for example, $v_{r}$ , the secret key of each of them, that is, $K_{i}$ and $K_{r}$ , will not be allowed to be exchanged. Thus, $v_{r}$ cannot obtain $K_{i}$ and cannot link the new pseudonyms of $v_{i}$ , which are generated by the hash function, $PI D_{r}$ , and $K_{i}$ , with the previous ones generated by the hash function, $PI D_{i}$ , and $K_{i}$ .

Auditability. In DPSZ, the initializing vehicle in pseudonym swapping zone is obliged to upload the swap log by which CA can always the map between the real identities and the pseudonyms of vehicles. Meanwhile, the other participant of the just completed swap can judge the correctness and timeliness of the log message uploaded by the initializing vehicle and has the right to send accusing message to CA when meeting with misbehaviors. By utilizing accusing messages and log messages, CA can exactly find out those vehicles with malicious behaviors and exclude them from the system.

Performance evaluation

This section evaluates the performance of DPSZ scheme through simulation experiments. We compare the performance of DPSZ and the existing schemes PSNV, SlotSwap, and DMLP. Among them, PSNV is a location privacy protection scheme based on dynamically generated groups. SlotSwap refers to the scheme that vehicles select the appropriate one-hop neighbor nodes in the social spots with high vehicle density environment to exchange pseudonyms. DMLP is a location privacy protection scheme based on dynamic mixed areas. We compare the four schemes by analyzing their average anonymous entropy and probability of being tracked.

Performance metrics

We use entropy to measure the strength of location privacy protection for vehicles. Consider a pseudonym swap zone where a collection of vehicles, denoted by $ψ_{i} = {v_{1}, v_{2}, v_{3}, \dots, v_{n}}$ , will perform the pseudonym swaps. Let $p_{i}$ represent the successful tracking probability of vehicle $v_{i}$ after pseudonyms swaps. Then the entropy of the anonymous set $ψ_{i}$ is

E (ψ_{i}) = - \sum_{i = 1}^{ψ_{i}} p_{i} \times lo g_{2} p_{i}

(9)

Assuming that there are four vehicles in the pseudonym exchange area, the set of probability that four vehicles are tracked is P_i = {0.25, 0.25, 0.25, 0.25}, then the entropy of the anonymous set is $E (ψ_{i}) = 2$ . The greater the entropy is, the higher the location privacy of the vehicle is.

Let N represent the number of vehicles in the entire network. After there have been n zones swapped pseudonyms, the entropy of the average anonymous set of the entire network is

E_{ave} = \frac{\sum_{j = 1}^{n} \sum_{k = 1}^{| ψ_{i} |} E (ψ_{j})}{N}

(10)

Simulation setting

We selected a 3500 m×3000 m city area, including 37 intersections and 62 two-way road sections. We use C++ to develop a simulation platform to simulate an IoV running in urban area. The speeds of vehicles are randomly selected from 10 to 90km/h which are related to the speed limit of the road segments. The movement of vehicles uses the Manhattan mobile model.³⁷ Detailed simulation parameters are shown in Table 2.

Table 2.

Simulation parameters.

Parameter	Value
Simulation time	1800 s
Simulation area	3500 m × 3000 m
Number of intersections	37
Number of roads	62
Number of vehicles	[100, 900]
Number of RSU	124
Attacking ability	[0.5, 0.95]
Communication range	300 m
Vehicle velocity	[10, 90]km/h
Beacon message interval	1 s
Beacon packet	100 bytes
Data packet	350 bytes
Ack packet	50 bytes

RSU: road-side units.

Impact of self-adaptive communication surroundings

The self-adaptive communication surroundings are designed to reduce the communication cost of the areas where the density of vehicles is high. We use the size of the packets generated by the initiating vehicles communication as the communication cost. Figure 5 compares the communication cost of the vehicles in the two cases of with and without the self-adaptive communication surroundings strategy. It can be seen from the figure that the communication cost of the two cases is not much different in the environments with low vehicle density. With the increasing number of vehicles, we can see a significant difference between them. As the number reaches 500, the communication cost of vehicles in the self-adaptive scheme begins to stabilize, and the communication cost of vehicles in the non-self-adaptive scheme still shows a trend of continuous growth. It can be seen from the experimental results in the figure that the self-adaptive scheme can effectively control the communication cost of the vehicles in the environments with high vehicle density. As it requires lots of computing to generate, transmit, receive, and process a large amount of communication data, this means that our scheme can effectively reduce communication burden, and meanwhile can also lower computation overhead in high vehicle density case.

Figure 5.

The effect of the self-adaptive communication surroundings.

Impact of swap zone size threshold

The effect of different $Γ_{s}$ values on the average anonymous entropy of the vehicles is evaluated in the experiment. Figure 6 shows the average anonymous entropy of the vehicles under the different values of $Γ_{s}$ . It can be seen from the figure that as the value of $Γ_{s}$ increases, the average anonymous entropy of the vehicles gradually decreases. If the value of $Γ_{s}$ increases, the number of times the vehicle performs pseudonym swap on the same running distance will decrease. Therefore, the average anonymous entropy of the vehicles shows a downward trend. It can be seen from this figure that the average anonymous entropy of the vehicles decreases significantly when the value of $Γ_{s}$ is greater than 8. It is indicated that when the value of $Γ_{s}$ is set to be greater than 8, the number of times the vehicles can perform pseudonym swap is reduced. It can be seen from Figures 3 and 6 that the determination of $Γ_{s}$ cannot be too large or too small. The threshold $Γ_{s}$ which is the number of vehicles in zone needs to be determined jointly based on the average anonymous entropy and the probability $p$ being tracked.

Figure 6.

The effect of the threshold of participant vehicles on the average anonymous entropy.

Impact of vehicle density

Figure 7 shows comparisons of average anonymous entropy and the probability of the vehicles being tracked under different vehicle densities by the number of different vehicles in the simulation area. Figure 7(a) shows the average anonymous density conditions. In this simulation, we represent different entropy at different vehicle densities. From this graph, we can observe that as the number of vehicles increases, the average anonymity of the four schemes shows an upward trend. The average anonymous entropy indicates the degree of privacy of the vehicles, so the probability of the vehicles being tracked decreases as the vehicle density increases (as shown in Figure 7(b)). It can be seen from Figure 7(a) that when the number of vehicles is less than 600, the average anonymous entropy of the vehicles increases as the number of vehicles increases, and the probability of being tracked decreases as the number of vehicles increases. As the density of vehicles increases, the number of vehicles that meet the exchange conditions will also increase, so the anonymity of the vehicles increases and the probability of being tracked decreases. When the number of vehicles is greater than 600, the average anonymous entropy of the vehicles shows a stable trend. Our algorithm introduces the self-adaptive communication surrounding for controlling the number of vehicles in the zone when the vehicle density is too high. Therefore, after the vehicle density exceeds a certain value, the average anonymous entropy of the vehicles will no longer change with the vehicle density changes. Therefore, in Figure 7(b), when the number of vehicles is greater than 600, the probability being tracked no longer fluctuates with the density of the vehicles. It can be seen from the experimental results that when the number of vehicles is greater than 600, the privacy of the vehicles is optimal, which is based on the initial parameters defined in Table 2.

Figure 7.

Different vehicle density: (a) average anonymous entropy and (b) being tracked probability.

The pseudonym swap of the SlotSwap scheme is only for two vehicles. Therefore, the SlotSwap scheme has a low swap efficiency, in turn, the average anonymity entropy of the scheme is low. The experimental results show that the PSNV scheme is closer to the experimental results of this paper’s scheme. Since DPSZ scheme rationally divides the swap zone to make full use of the swap opportunity, the effect of this scheme is still slightly better than the scheme PSNV. However, the difference in entropy in CAse where the vehicle-intensive scene is sparse relative to the vehicle density is still relatively large. The number of vehicles satisfying the swap condition is increased in CAse of a dense vehicle, and thus, the average anonymous entropy of the vehicles also increased. Experiments show that our algorithm performs better than the other three schemes at any vehicle density. This is because our solution is able to use the pseudonym swap opportunity as much as possible to achieve location privacy protection, even in the scenario where the vehicles are sparse.

Impact of vehicle speeds

Figure 8(a) shows comparisons of the average anonymous entropy of the four schemes at different running speeds. It can be seen from Figure 8(a) that the average anonymous entropy of the four schemes is in the form of rising first and then decreasing. As the speed of the vehicles accelerate during the running, the changes of the surrounding vehicles are accelerated; the number of neighboring vehicles that can participate in the pseudonym swap will also increase. When the speed is too fast, the effective communication time between vehicles will also be reduced; what’s more, the vehicles selection for pseudonym swap will also be reduced. The probability of the vehicles being tracked is inversely proportional to the average anonymous entropy, so the probability of the vehicles being tracked first drops and then rises (as shown in Figure 8(b)). From the simulation results in Figure 8(a), the speed for the four schemes to achieve optimal anonymity is 50 km/h for DPSZ, 60 km/h for PSNV, 30 km/h for DMLP, and 40 km/h for SlotSwap.

Figure 8.

Different running speeds: (a) average anonymous entropy and (b) being tracked probability.

At different operating speeds, DPSZ’s average anonymous entropy and probability of being tracked are less volatile than the other three schemes. Therefore, it can be concluded that the running speed has less influence on the vehicle anonymity of the other three schemes. The conditional restrictions on the swap members in the scheme PSNV are relatively simple and neglect the condition that the vehicles are running at high speed. Both the DMLP scheme and the SlotSwap scheme are aimed at the pseudonym swap between two vehicles, so the speed of the vehicles has little effect on the two schemes. In our scheme, we reasonably increased the number and range of candidate vehicles to minimize the impact of running speed on the pseudonym swap. From the simulation results in Figure 8(a), we can see that the average anonymous entropy of our proposed DPSZ increases at first and reaches the highest value at 50 km/h, then decreases with the speed varying from 10 to 90 km/h. The reason is that if a vehicle needs to establish a DPSZ, it has to satisfy the two conditions: (1) there are some neighbor vehicles, and the link continuous connected time between each of them and the vehicle is not less than the threshold $Γ_{t}$ ; (2) the number of such neighbor vehicles fitting Condition 1 is less than the threshold $Γ_{s}$ . Too slow or too fast vehicle speeds are not conducive to the forming of DPSZs.

According to Wikipedia contributors,³⁸ the speed limit of urban roads is basically between 20 and 60 km/h in many countries, and our DPSZ scheme shows better anonymous performance in the speed range compared with the other three schemes. This means that DPSZ is suitable for urban area.

Impact of simulation time

Under the different running time, Figure 9 compares the average anonymous entropy of the vehicles and the probability of being tracked. We assume that the probability of the vehicles being tracked at startup is 100%. As shown in Figure 9(a), the average anonymous entropy of the vehicles increases with increasing runtime. The higher the degree of anonymity of the vehicles, the lower the probability of being tracked. It can be seen from Figure 9(b) that as the running time increases, the probability of the vehicles being tracked is gradually reduced, and the probability of our scheme being tracked is significantly lower than that of the other three schemes. At the beginning of the simulation run, there are more vehicles that need to perform pseudonym swap, so the average anonymous entropy growth rate is larger. The growth rate of the average anonymous entropy of the vehicles after the simulation run for 400 s tends to be stable. Correspondingly, the probability of the vehicles being tracked drops steadily after the simulation runs for 400 s. When the running time is different, we can see from the experimental results that our scheme is superior to the other three schemes in terms of the average anonymous entropy and the probability of the vehicles being tracked. Therefore, our scheme has better anonymity than the other three schemes.

Figure 9.

Different simulation time: (a) average anonymous entropy and (b) being tracked probability.

Impact of attack capability

Depending on the ability of attackers, the effect of different schemes will differ. Figure 10(a) shows the average anonymous entropy of the four schemes under different attack capabilities. It can be seen from the figure that within the range of effective anonymous value fluctuate, the average anonymous entropy decreases as the attack ability increases. The stronger the attack ability, the higher $p$ which is the probability that the vehicles will being tracked, so the average anonymous entropy is correspondingly reduced. The probability of the vehicles being tracked is related to $p$ , so the probability of the vehicles being tracked increases as the attackers’ attack ability increases (Figure 10(b)). It can be seen from Figure 10(a) that when the attackers’ attack ability is 0.7–0.75, the average anonymous entropy of the vehicles decreases significantly. It shows that the vehicles have better anonymity when the attackers’ attack ability is less than 0.7.

Figure 10.

Different attack capabilities: (a) average anonymous entropy and (b) being tracked probability.

Regardless of the attack capability, both the DMLP scheme and the SlotSwap scheme are directed to the pseudonym swap between two vehicles, so the average anonymous entropy values of the two schemes are close. When the scheme DPSZ performs a pseudonym swap, all participating vehicles respond with messages of the same type and length. The attackers cannot determine the vehicle which performed the pseudonym swap with the initiating vehicle by the number and type of communication between the vehicles, thereby achieving good privacy. Under different attack capabilities, the experimental results also show that the scheme DPSZ is superior to the other three schemes in terms of the average anonymous entropy and the probability of the vehicles being tracked, thus reflecting good privacy protection performance.

Conclusion

We have presented a new location privacy protection scheme DPSZ. We first defined the two conditions for vehicles to establish a pseudonym swap zone: link continuous connected time and available vehicle number. When a vehicle has pseudonym swap need and its surrounding satisfies the above two conditions, it is allowed to form a dynamic zone to swap the pseudonym with another vehicle randomly selected in the zone. That makes DPSZ eliminate the secure risk of assigning the exchanging participants which is brought about by the group manager in the existing works. To avoid the high communication and computation costs of frequent pseudonym swap, we introduced the combination of pseudonym update and pseudonym swap. We also used a self-adaptive surrounding method to reduce the communication cost in areas with dense vehicles. We analyzed the security of the proposed DPSZ scheme in terms of conditional anonymity, unlinkability, and auditability. Moreover, we executed simulation to evaluate the location privacy protection performance of DPSZ and several existing typical schemes. The simulation results show that DPSZ achieve higher performance compared with the other schemes.

Footnotes

Handling Editor: Weizhi Meng

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported by the National Natural Science Foundation of China under grants nos 61662042, 61262081, and 61462056; the Yunnan Provincial Key Project of Applied Basic Research Plan under grants no. 2014FA028.

ORCID iD

Yong Feng

References

Butt

Iqbal

Shah

et al . Social Internet of Vehicles: architecture and enabling technologies. Comput Electr Eng 2018; 69: 68–84.

Akhtar

Ergen

Ozkasap

. Vehicle mobility and communication channel models for realistic and efficient highway VANET simulation. IEEE T Veh Commun 2015; 65(1): 248–262.

Memon

Arain

. Dynamic path privacy protection framework for continuous query service over road networks. World Wide Web 2017; 20(4): 639–672.

Amini

Lindqvist

Hong

et al . Caché: caching location-enhanced content to improve user privacy. In: Proceedings of the 9th international conference on mobile systems, applications, and services (Mobisys’11), Bethesda, MD, 28 June–1 July 2011, pp.197–210. New York: ACM.

IEEE Standard 802.11:2012. Part 11: wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications.

Saleh

Saeed

Mahmood

et al . On the performance of safety message dissemination in vehicular Ad Hoc networks. In: 4th European conference on universal multiservice networks (ECUMN’07), Toulouse, 14–16 February 2007. New York: IEEE.

Freudiger

Jadliwala

Hubaux

et al . Privacy of community pseudonyms in wireless peer-to-peer networks. Mobile Netw Appl 2013; 18(3): 413–428.

Chim

Hui

CKL

Yiu

et al . MLAS: multiple level authentication scheme for VANETs. Ad Hoc Netw 2012; 10(7): 1445–1456.

Shim

. An ID-based aggregate signature scheme with constant pairing computations. J Syst Software 2010; 83(10): 1873–1880.

10.

Ying

Makrakis

Mouftah

. Dynamic mix-zone for location privacy in vehicular networks. IEEE Commun Lett 2013; 17(8): 1524–1527.

11.

Ying

Makrakis

. Pseudonym changes scheme based on candidate-location-list in vehicular networks. In: IEEE international conference on communications (ICC), London, 8–12 June 2015, pp.7292–7297. New York: IEEE.

12.

Pan

. Cooperative pseudonym change scheme based on the number of neighbors in VANETs. J Netw Comput Appl 2013; 36(6): 1599–1609.

13.

Eckhoff

Sommer

Gansen

et al . Strong and affordable location privacy in VANETs: identity diffusion using time-slots and swapping. In: Vehicular networking conference (VNC), Jersey City, NJ, 13–15 December 2010, pp.174–181. New York: IEEE.

14.

Zhang

Feng

Liu

. A location privacy enhancement scheme based on intra-group pseudonym swapping for vehicular Ad Hoc networks. Appl Res Comput 2017; 34(10): 3098–3103.

15.

Memon

. Distance and clustering-based energy-efficient pseudonyms changing strategy over road network. Int J Commun Syst 201831: e3704.

16.

Memon

Ali

Zubedi

et al . DPMM: dynamic pseudonym-based multiple mix-zones generation for mobile traveler. Multimed Tools Appl 2016; 76(22): 24359–24388.

17.

Arain

Zhongliang

Memon

et al . Privacy preserving dynamic pseudonym-based multiple mix-zones authentication protocol over road networks. Wireless Pers Commun 2017; 95(2): 1–17.

18.

Arain

Uqaili

Deng

et al . Clustering based energy efficient and communication protocol for multiple mix-zones over road networks. Wireless Pers Commun 2016; 95(2): 411–428.

19.

Lin

Luan

et al . Anonymity analysis on social spot based pseudonym changing for location privacy in VANETs. In: IEEE international conference on communications (ICC), Kyoto, Japan, 5–9 June 2011, pp.1–5. New York: IEEE.

20.

Lin

Luan

et al . Pseudonym changing at social spots: an effective strategy for location privacy in VANETs. IEEE T Veh Technol 2012; 61: 86–96.

21.

Sampigethaya

Huang

et al . AMOEBA: robust location privacy scheme for VANET. IEEE J Sel Area Comm 2007; 25(8): 1569–1589.

22.

Buttyán

Holczer

Weimerskirch

et al . SLOW: a practical pseudonym changing scheme for location privacy in VANETs. In: Vehicular networking conference (VNC), Tokyo, Japan, 28–30 October 2009, pp.1–8. New York: IEEE.

23.

Kang

Huang

et al . Mixgroup: accumulative pseudonym exchanging for location privacy enhancement in vehicular social networks. IEEE T Depend Secure 2016; 13: 93–105.

24.

Perera

MNS

Koshiba

. Fully dynamic group signature scheme with member registration and verifier-local revocation. In: International conference on mathematics and computing, Varanasi, India, 9–11 January 2018, pp.399–415. Springer: New York.

25.

Hwang

Chen

Cho

et al . Short dynamic group signature scheme supporting controllable linkability. IEEE T Inf Foren Sec 2015; 10(6): 1109–1124.

26.

Sampigethaya

Huang

et al . Caravan: providing location privacy for VANET. In: Embedded security in cars (ESCAR), Seattle, WA, 2005, https://pdfs.semanticscholar.org/fb10/495488bfc72edaf63bd17bc7963b34b6cefe.pdf

27.

Scheuer

Fuchs

Federrath

. A safety-preserving mix zone for VANETs. In: Proceedings of the 8th international conference on trust, privacy and security in digital business (TrustBus’11), Toulouse, 29 August–2 September 2011, pp.37–48. Berlin: Springer.

28.

Petit

Schaub

Feiri

et al . Pseudonym schemes in vehicular networks: a survey. IEEE Commun Surv Tut 2015; 17(1): 228–255.

29.

Memon

Mirza

. MADPTM: mix zones and dynamic pseudonym trust management system for location privacy. Int J Commun Syst 2018; 31(17): e3795.

30.

Mathews

. An effective strategy for pseudonym generation & changing scheme with privacy preservation for VANET. In: International conference on electronics and communication systems (ICECS), Coimbatore, India, 13–14 February 2014, pp.1–6. New York: IEEE.

31.

Sampigethaya

Huang

et al . Swing & swap: user-centric approaches towards maximizing location privacy. In: Proceedings of the 2006 ACM workshop on privacy in the electronic society (WPES), Alexandria, VA, 30 October 2006, pp.19–28. New York: ACM.

32.

Memon

Chen

Arain

et al . Pseudonym changing strategy with multiple mix zones for trajectory privacy protection in road networks. Int J Commun Syst 2017; 31: e3437.

33.

Araki

Furukawa

Lindell

et al . High-throughput semi-honest secure three-party computation with an honest majority. In: ACM SIGSAC conference on computer & communications security, Vienna, 24–28 October 2016. New York: ACM.

34.

Buchmann

. Introduction to cryptography. 2nd ed. New York: Springer Science and Business Media, 2013, pp.190–191.

35.

Lee

Gerla

. Mobility prediction and routing in Ad Hoc wireless networks. Int J Netw Manag 2010; 11(1): 3–30.

36.

Qiu

Wang

Chen

. TMED: a spider-web-like transmission mechanism for emergency data in vehicular Ad Hoc networks. IEEE T Veh Technol 2018; 67(9): 8682–8694.

37.

Ramakrishnan

Selvi

Nishanth

. Efficiency measure of routing protocols in vehicular Ad Hoc network using freeway mobility model. Wirel Netw 2017; 23: 1–11.

38.

Wikipedia contributors. Spee-d limits by country, https://en.wikipedia.org/wiki/Speed_limits_by_country (accessed 9 April 2019).

Location privacy preserving scheme based on dynamic pseudonym swap zone for Internet of Vehicles

Abstract

Keywords

Introduction

Related work

System model

System architecture

Threat and trust models

Pseudonym swapping scheme based on dynamic swap zone

Registration

Pseudonym update

Pseudonym swapping

Pseudonym swap log uploading

Self-adaptive communication surroundings

Security analysis

Performance evaluation

Performance metrics

Simulation setting

Impact of self-adaptive communication surroundings

Impact of swap zone size threshold

Impact of vehicle density

Impact of vehicle speeds

Impact of simulation time

Impact of attack capability

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References