# Trajectory as an Identity: Privacy-Preserving and Sybil-Resistant Authentication for Internet of Vehicles

Authors: Jiangtao Li; Zhaoheng Song; Yufeng Li; Chenhong Cao; Yuanhang He
Journal: Security and Communication Networks
 (2021)

---

## Abstract

With the advancement of the 5G network, the Internet of Vehicles (IoV) is becoming more and more attractive for academic researchers and industrial. A main challenge of IoV is to guarantee the authenticity of messages and protect drivers’ privacy simultaneously. The majority of privacy-preserving authentication schemes for IoV adopt pseudonyms or group signatures to achieve a balance between security and privacy. However, defending the Sybil attacks in these schemes is challenging. In this work, we propose a novel privacy-preserving authentication scheme for announcement messages, which utilizes the trajectories of vehicles as their identities. When an authenticated message is verified, the verifier is convinced that the message is generated by a vehicle that has a unique masked trajectory. Meanwhile, the real trajectories of vehicles are kept private. In particular, our scheme achieves Sybil attack resistance without the limitation of trajectory length even when the attacker is allowed to use cloud services.


---

## Body

## 1. Introduction

Internet of Vehicles (IoV) is made possible with the advancement of 5G network, which achieves lower latency and supports higher mobility [1, 2]. As a special type of Internet of Things (IoT) [3], IoV allows vehicles to communicate with surrounding vehicles, Road Side Units (RSUs), and infrastructures. By providing road condition warnings, cooperative perception, and driving assistant services, IoV can improve traffic efficiency and road safety [4]. However, vehicle-to-vehicle communications in IoV do not adopt any security mechanism in the network layer [5, 6]. For privacy concerns, the IP address of each vehicle is also dynamically changed. Without a security mechanism, a malicious vehicle in IoV may send false data or misleading messages to other vehicles and infrastructures. For instance, a vehicle may claim a fake traffic jam by broadcasting an announcement message to achieve a better driving condition for himself. Hence, it is necessary to authenticate the messages broadcast in IoV.Adopting signature schemes is a commonly used way to guarantee the authenticity of messages in IoV [7]. If a signature is verified, a vehicle is convinced that the message is sent by the claimed sender and not tempered in transmission. However, due to the openness of wireless communication, an attacker can violate vehicle privacy by simply collecting messages broadcast in IoV [8]. Pseudonym mechanism is a classical way to achieve a trade-off between security and privacy in IoV. Under the pseudonym mechanism, each vehicle will generate multiple certified identities (i.e., public/private key pairs). A vehicle needs to use a fresh identity for each message to keep its identity private. This will bring the vehicle extra storage cost. Besides, the pseudonym mechanism is vulnerable to Sybil attacks. A vehicle can use multiple identities simultaneously to pretend to be multiple vehicles.One approach to overcome the drawback of the pseudonym mechanism is employing the group signature instead of traditional signatures. In group signatures, any group member is allowed to generate signatures on behalf of the group. This way, vehicles’ identities will not be leaked during message authentication. To defend Sybil attacks, the researchers also propose a new primitive named message linkable group signature [9]. If an attacker broadcasts the same message twice, this behavior can be efficiently detected. It is obvious that the message linking technique is useful only when the attacker simply sends the same message repeatedly in launching a Sybil attack. If an attacker tries to send different messages with the same semantic, this Sybil attack defense technique will fail.Several works have been proposed to deal with the Sybil attacks, launched with different messages. One solution is to use the cryptographic puzzle to prevent a vehicle from impersonating multiple vehicles since the computational resource of each vehicle is limited [10]. However, if a vehicle is allowed to outsource the puzzle to the cloud, this solution will not work. Later, Baza et al. [11] proposed to consider both the locations (trajectories) [12] and cryptographic puzzles in detecting Sybil attacks. In [11], only vehicles proved to have traversed some RSUs are regarded as valid vehicles. In contrast, their work does not consider the situation where vehicles may collude with each other. Furthermore, when the vehicle is allowed to use cloud service, the Sybil attack can only be efficiently detected if the trajectory length is long enough.


### 1.1. Contribution

To cope with the above-mentioned problems. We propose to use trajectory as an identity of a vehicle to achieve privacy-preserving and Sybil-resistant authentication for IoV.In the proposed scheme, when a vehicle needs to broadcast an announcement message, it will sign the message with a freshly generated identity. Then, the signed message is broadcast together with the vehicle’s trajectory. The trajectory can be viewed as a certificate of the freshly generated identity. When an announcement message is verified, it is established that the message is signed by the vehicle, confirmed to have a valid trajectory in IoV. Besides, as the identities of RSUs are masked, the real trajectory of vehicles will not be revealed, and hence, the privacy of vehicles is preserved.In particular, when the vehicle is allowed to use cloud services, our proposal is also secure against Sybil attacks without the trajectory length limitation. A vehicle in IoV needs to solve a series of computational puzzles before it can send a valid trajectory request to the RSU. Since the computational puzzles are bound with the secret keys of vehicles, rational vehicles will not choose to outsource the secret key and hence the computational puzzles. Besides benefits from the sequential aggregate signatures used in the scheme, the scheme also achieves efficient RSU verification.


### 1.2. Related Work

Existing privacy protection authentication schemes for IoV can generally be categorized into two types: pseudonym-based ones and group signature-based ones. In the pseudonym-based authentication scheme, each vehicle can hold multiple pseudonymous identities [13]. The vehicle can use a new pseudonymous identity to send messages at regular intervals or after sending several messages according to its own privacy needs. No entity except for a trusted authority can distinguish whether any two pseudonymous identities belong to the same vehicle. However, the anonymity of these schemes is achieved at the cost of frequently changing pseudonymous identities [14]. Under the traditional Public Key Infrastructure (PKI) architecture [15], the trusted authority needs to issue a certificate for each pseudonymous public key, so the vehicle needs to store a large number of pseudonymous certificates and their corresponding keys in advance. This brings extra storage costs to vehicles.In order to reduce the cost of storage and communication of vehicles caused by pseudonym management, privacy-preserving authentication schemes based on group signature are proposed [16, 17]. In these schemes, when the vehicle needs to change its pseudonym, the vehicle can use its group private key to issue a certificate to the new pseudonym, so there is no need to store a large number of pseudonyms. Later, Hao et al. [18] also proposed a distributed group model [19] for group signature-based authentication schemes in IoV. Under this model, an RSU acts as a group administrator to manage the group and distribute certificates and keys to vehicles entering its area. When the vehicle leaves the communication range of the current RSU and enters the next RSU, the vehicle will be automatically revoked. Recently, Lin et al. [20] and Mollah et al. [21] also proposed to use blockchain and smart contracts in realizing identity management and improve existing privacy protection authentication schemes. However, traditional group signature-based solutions are not secure against Sybil attacks.In order to defend Sybil attacks, Wu et al. [9] proposed the concept of message linkable group signature. In the message linkable group signature-based schemes, if a vehicle generates more than two signatures for the same message, it can be efficiently detected. Chen et al. [22] also proposed to use direct anonymous authentication schemes and one-time anonymous signatures to realize message linkability, which is similar to the effect of [9]. However, the message linking techniques are only useful for event-driven announcement messages in IoV. For the announcement messages that allow the vehicle to send different messages with the same semantics, message linking techniques will not play the role of defending Sybil attacks.Another method to realize Sybil detection is anonymous trajectory-based authentication. In [12], each vehicle needs to request a trajectory from the RSU when it passes through. Compared with the message linkable solutions, this method may prevent an attacker from sending Sybil messages with the same semantics. At the same time, in order to achieve anonymity, RSU needs to use a zero-knowledge signature that can be linked in a short time to protect the privacy of the vehicle’s location. However, the vehicle may generate multiple false trajectories and send them to the RSU to achieve a denial-of-service (DOS) attack. Hence, Liu et al. [10] proposed to use cryptographic puzzles to resist DOS and Sybil attacks in the IoV. Recently, Baza et al. [11] combined the idea of the cryptographic puzzle with the trajectory proof method in [12] and proposed a solution to detect Sybil attacks. However, this work does not consider the situation where vehicles may collude with each other. When the vehicle is allowed to use cloud service, the Sybil attack can only be efficiently detected if the trajectory length is long enough.


### 1.3. Organization

The rest of the paper is organized as follows: we describe the system architecture and design goals in Section2. Section 3 gives some of the cryptographic primitives used in our scheme. We present our scheme in Section 4 and analyze its security and efficiency in Section 5. Finally, we conclude the paper in Section 6.


## 1.1. Contribution

To cope with the above-mentioned problems. We propose to use trajectory as an identity of a vehicle to achieve privacy-preserving and Sybil-resistant authentication for IoV.In the proposed scheme, when a vehicle needs to broadcast an announcement message, it will sign the message with a freshly generated identity. Then, the signed message is broadcast together with the vehicle’s trajectory. The trajectory can be viewed as a certificate of the freshly generated identity. When an announcement message is verified, it is established that the message is signed by the vehicle, confirmed to have a valid trajectory in IoV. Besides, as the identities of RSUs are masked, the real trajectory of vehicles will not be revealed, and hence, the privacy of vehicles is preserved.In particular, when the vehicle is allowed to use cloud services, our proposal is also secure against Sybil attacks without the trajectory length limitation. A vehicle in IoV needs to solve a series of computational puzzles before it can send a valid trajectory request to the RSU. Since the computational puzzles are bound with the secret keys of vehicles, rational vehicles will not choose to outsource the secret key and hence the computational puzzles. Besides benefits from the sequential aggregate signatures used in the scheme, the scheme also achieves efficient RSU verification.


## 1.2. Related Work

Existing privacy protection authentication schemes for IoV can generally be categorized into two types: pseudonym-based ones and group signature-based ones. In the pseudonym-based authentication scheme, each vehicle can hold multiple pseudonymous identities [13]. The vehicle can use a new pseudonymous identity to send messages at regular intervals or after sending several messages according to its own privacy needs. No entity except for a trusted authority can distinguish whether any two pseudonymous identities belong to the same vehicle. However, the anonymity of these schemes is achieved at the cost of frequently changing pseudonymous identities [14]. Under the traditional Public Key Infrastructure (PKI) architecture [15], the trusted authority needs to issue a certificate for each pseudonymous public key, so the vehicle needs to store a large number of pseudonymous certificates and their corresponding keys in advance. This brings extra storage costs to vehicles.In order to reduce the cost of storage and communication of vehicles caused by pseudonym management, privacy-preserving authentication schemes based on group signature are proposed [16, 17]. In these schemes, when the vehicle needs to change its pseudonym, the vehicle can use its group private key to issue a certificate to the new pseudonym, so there is no need to store a large number of pseudonyms. Later, Hao et al. [18] also proposed a distributed group model [19] for group signature-based authentication schemes in IoV. Under this model, an RSU acts as a group administrator to manage the group and distribute certificates and keys to vehicles entering its area. When the vehicle leaves the communication range of the current RSU and enters the next RSU, the vehicle will be automatically revoked. Recently, Lin et al. [20] and Mollah et al. [21] also proposed to use blockchain and smart contracts in realizing identity management and improve existing privacy protection authentication schemes. However, traditional group signature-based solutions are not secure against Sybil attacks.In order to defend Sybil attacks, Wu et al. [9] proposed the concept of message linkable group signature. In the message linkable group signature-based schemes, if a vehicle generates more than two signatures for the same message, it can be efficiently detected. Chen et al. [22] also proposed to use direct anonymous authentication schemes and one-time anonymous signatures to realize message linkability, which is similar to the effect of [9]. However, the message linking techniques are only useful for event-driven announcement messages in IoV. For the announcement messages that allow the vehicle to send different messages with the same semantics, message linking techniques will not play the role of defending Sybil attacks.Another method to realize Sybil detection is anonymous trajectory-based authentication. In [12], each vehicle needs to request a trajectory from the RSU when it passes through. Compared with the message linkable solutions, this method may prevent an attacker from sending Sybil messages with the same semantics. At the same time, in order to achieve anonymity, RSU needs to use a zero-knowledge signature that can be linked in a short time to protect the privacy of the vehicle’s location. However, the vehicle may generate multiple false trajectories and send them to the RSU to achieve a denial-of-service (DOS) attack. Hence, Liu et al. [10] proposed to use cryptographic puzzles to resist DOS and Sybil attacks in the IoV. Recently, Baza et al. [11] combined the idea of the cryptographic puzzle with the trajectory proof method in [12] and proposed a solution to detect Sybil attacks. However, this work does not consider the situation where vehicles may collude with each other. When the vehicle is allowed to use cloud service, the Sybil attack can only be efficiently detected if the trajectory length is long enough.


## 1.3. Organization

The rest of the paper is organized as follows: we describe the system architecture and design goals in Section2. Section 3 gives some of the cryptographic primitives used in our scheme. We present our scheme in Section 4 and analyze its security and efficiency in Section 5. Finally, we conclude the paper in Section 6.


## 2. System Architecture and Design Goals

In this section, we describe the system models and design goals of this work.


### 2.1. System Architecture

As shown in Figure1, the IoV scenario considered in this work consists of the following entities:(i)
Road side units (RSUs): RSUs in the system are equipped with computation and communication modules. They are responsible for issuing partial authenticated trajectories for vehicles.(ii)
Vehicles: vehicles in the system can communicate with surrounding vehicles and RSUs. When they encounter an event (e.g., traffic accident), they can send an announcement message to the announcement manager. We note that the vehicles might be malicious. They may send fake messages or launch Sybil attacks.(iii)
Trusted authority (TA): the trusted authority can be the Department of Motor Vehicles (DMV). It is responsible for issuing certificates for vehicles and initializing the system.(iv)
Announcement manager: the announcement manager is an authority that collects and verifies the announcement messages sent by the vehicles. It is supposed to be a semihonest authority; that is, it will perform all steps of the scheme honestly. However, it is curious about the privacy of vehicles.Figure 1
System architecture.


### 2.2. Design Goals

A privacy-preserving Sybil-resistant announcement scheme for IoV should achieve the following security and efficiency requirements.(i)
Privacy-preserving authentication: it is required that all announcement messages should be authenticated. Besides, the real trajectories of vehicles should be kept private.(ii)
Sybil attack resistance: if a vehicle tries to launch a Sybil attack, that is, pretending to be multiple vehicles, it can be efficiently detected. In particular, the scheme should be secure, even if the vehicle is allowed to use cloud service to launch such an attack.(iii)
Resisting RSU compromise: in the system, the authenticity of messages should be kept even if some RSUs are compromised by the attacker.(iv)
Efficient RSU verification: the RSU is responsible for verifying the trajectory requests. The request verification should be efficiently processed. Besides, the RSU should also be able to handle the trajectory requests efficiently even under Denial-of-Service (DoS) attacks.


## 2.1. System Architecture

As shown in Figure1, the IoV scenario considered in this work consists of the following entities:(i)
Road side units (RSUs): RSUs in the system are equipped with computation and communication modules. They are responsible for issuing partial authenticated trajectories for vehicles.(ii)
Vehicles: vehicles in the system can communicate with surrounding vehicles and RSUs. When they encounter an event (e.g., traffic accident), they can send an announcement message to the announcement manager. We note that the vehicles might be malicious. They may send fake messages or launch Sybil attacks.(iii)
Trusted authority (TA): the trusted authority can be the Department of Motor Vehicles (DMV). It is responsible for issuing certificates for vehicles and initializing the system.(iv)
Announcement manager: the announcement manager is an authority that collects and verifies the announcement messages sent by the vehicles. It is supposed to be a semihonest authority; that is, it will perform all steps of the scheme honestly. However, it is curious about the privacy of vehicles.Figure 1
System architecture.


## 2.2. Design Goals

A privacy-preserving Sybil-resistant announcement scheme for IoV should achieve the following security and efficiency requirements.(i)
Privacy-preserving authentication: it is required that all announcement messages should be authenticated. Besides, the real trajectories of vehicles should be kept private.(ii)
Sybil attack resistance: if a vehicle tries to launch a Sybil attack, that is, pretending to be multiple vehicles, it can be efficiently detected. In particular, the scheme should be secure, even if the vehicle is allowed to use cloud service to launch such an attack.(iii)
Resisting RSU compromise: in the system, the authenticity of messages should be kept even if some RSUs are compromised by the attacker.(iv)
Efficient RSU verification: the RSU is responsible for verifying the trajectory requests. The request verification should be efficiently processed. Besides, the RSU should also be able to handle the trajectory requests efficiently even under Denial-of-Service (DoS) attacks.


## 3. Preliminary

This section describes several cryptographic primitives used in our proposed scheme.


### 3.1. Sequential Aggregate Signature

Sequential aggregate signature (SeqAS) allows a signer to add his signature on a different message to the current signature sequentially. The aggregated signature has the same size as the previous signature. A signature will be able to pass the verification if and only if all the aggregated signatures are generated correctly.Definition 1.
(sequential aggregate signature). A sequential aggregate signature (SeqAS) scheme consists of four algorithms,AggSetup,AggKeyGen,AggSign, and AggVerify, defined as follows:(i)
AggSetup: the setup algorithm takes as input a security parameter and outputs public parameters(ii)
AggKeyGen: the key generation algorithm takes as input a security parameter and outputs a public key PK and a private key SK(iii)
AggSignSKα′,M;M: the aggregate signing algorithm takes as input an aggregate-so-far α′ on messages M = (tr1,…Mk), a message M, and a private key SK; it outputs a new aggregated signature α(iv)
AggVerifyα,M;PK: the aggregate verification algorithm takes as input an aggregate signature α on messages M = (tr1,…,Ml); it outputs ⊤ or ⊥ which indicates the signature is valid or not
In this paper, we adopt the SeqAS signature scheme proposed by Lee et al. [23].


### 3.2. Threshold Signatures without a Trusted Dealer

A threshold signature is a distributed multiparty signature protocol. In aθ,n-threshold signature, a valid signature will be reconstructed only when no less than θ signers sign on the same message.Definition 2.
(threshold signature without a trusted dealer). Aθ,n-threshold signature scheme without trusted dealer consists of the following algorithms:(i)
TSetup: this can be an interactive algorithm run by the players P1,P2,…,Pn. The algorithm outputs a public key PK. The private output of each player Pi is xi such that x1,…,xn⟶SK, where SK is the secret key corresponding to PK.(ii)
TSign: this algorithm generates the signature share. A player Pi takes a message m and its private key xi as input and outputs a signature share σi.(iii)
Reconstruct: this algorithm takes as a collection of θ signature shares. If all signature shares are valid, it outputs a message signature pair m,σ; else, it outputs ⊥.(iv)
TVerify: this algorithm takes a message signature pair as input and outputs ⊤/⊥, which indicates the signature is valid or not.
It is easy to construct a secure threshold signature algorithm using BLS short signature [24] and the distributed key generation algorithm for discrete-log-based cryptosystems [25].


### 3.3. Message Authentication Code

A message authentication code (MAC) is a cryptographic primitive that can prevent an adversary from modifying the messages sent from one entity to another.Definition 3.
(message authentication code). A message authentication code consists of the following three algorithms:(i)
Gen: it outputs a uniformly distributed key k(ii)
MAC: it takes a message m and the secret key k as input and outputs a tag t(iii)
Vrfy: it takes a message m and the secret key k and a tag t as input and outputs ⊤/⊥, which indicates the MAC is valid or not
For every secret keyk, it holds that Vrfykm,MACkm=⊤.


### 3.4. Computational Puzzle

A computational puzzle is a computational problem, which is used to verify if an entity has an estimated computational power. The hardness of a computational puzzle can be adjusted by a hardness parameter. A specific computational puzzle is usually represented by a random seed. To solve a computational puzzle, an entity needs to consume some computational resources. However, given a solution, it should be easy to verify the correctness of the solution. The hash-based puzzle is one of the famous computational puzzles used in the proof of work mechanism.


## 3.1. Sequential Aggregate Signature

Sequential aggregate signature (SeqAS) allows a signer to add his signature on a different message to the current signature sequentially. The aggregated signature has the same size as the previous signature. A signature will be able to pass the verification if and only if all the aggregated signatures are generated correctly.Definition 1.
(sequential aggregate signature). A sequential aggregate signature (SeqAS) scheme consists of four algorithms,AggSetup,AggKeyGen,AggSign, and AggVerify, defined as follows:(i)
AggSetup: the setup algorithm takes as input a security parameter and outputs public parameters(ii)
AggKeyGen: the key generation algorithm takes as input a security parameter and outputs a public key PK and a private key SK(iii)
AggSignSKα′,M;M: the aggregate signing algorithm takes as input an aggregate-so-far α′ on messages M = (tr1,…Mk), a message M, and a private key SK; it outputs a new aggregated signature α(iv)
AggVerifyα,M;PK: the aggregate verification algorithm takes as input an aggregate signature α on messages M = (tr1,…,Ml); it outputs ⊤ or ⊥ which indicates the signature is valid or not
In this paper, we adopt the SeqAS signature scheme proposed by Lee et al. [23].


## 3.2. Threshold Signatures without a Trusted Dealer

A threshold signature is a distributed multiparty signature protocol. In aθ,n-threshold signature, a valid signature will be reconstructed only when no less than θ signers sign on the same message.Definition 2.
(threshold signature without a trusted dealer). Aθ,n-threshold signature scheme without trusted dealer consists of the following algorithms:(i)
TSetup: this can be an interactive algorithm run by the players P1,P2,…,Pn. The algorithm outputs a public key PK. The private output of each player Pi is xi such that x1,…,xn⟶SK, where SK is the secret key corresponding to PK.(ii)
TSign: this algorithm generates the signature share. A player Pi takes a message m and its private key xi as input and outputs a signature share σi.(iii)
Reconstruct: this algorithm takes as a collection of θ signature shares. If all signature shares are valid, it outputs a message signature pair m,σ; else, it outputs ⊥.(iv)
TVerify: this algorithm takes a message signature pair as input and outputs ⊤/⊥, which indicates the signature is valid or not.
It is easy to construct a secure threshold signature algorithm using BLS short signature [24] and the distributed key generation algorithm for discrete-log-based cryptosystems [25].


## 3.3. Message Authentication Code

A message authentication code (MAC) is a cryptographic primitive that can prevent an adversary from modifying the messages sent from one entity to another.Definition 3.
(message authentication code). A message authentication code consists of the following three algorithms:(i)
Gen: it outputs a uniformly distributed key k(ii)
MAC: it takes a message m and the secret key k as input and outputs a tag t(iii)
Vrfy: it takes a message m and the secret key k and a tag t as input and outputs ⊤/⊥, which indicates the MAC is valid or not
For every secret keyk, it holds that Vrfykm,MACkm=⊤.


## 3.4. Computational Puzzle

A computational puzzle is a computational problem, which is used to verify if an entity has an estimated computational power. The hardness of a computational puzzle can be adjusted by a hardness parameter. A specific computational puzzle is usually represented by a random seed. To solve a computational puzzle, an entity needs to consume some computational resources. However, given a solution, it should be easy to verify the correctness of the solution. The hash-based puzzle is one of the famous computational puzzles used in the proof of work mechanism.


## 4. Privacy-Preserving and Sybil Attack Resistant Announcement

In this section, we describe the proposed privacy-preserving and Sybil attack resistant announcement scheme. We first give a high-level description of our scheme. Then, we explain the scheme in detail.


### 4.1. High-Level Description

In the scheme, we use the trajectory as the vehicle’s identity to achieve privacy-preserving authentication of announcement messages. The trajectory of a vehicle contains a number of RSUs and timestamps pairs, which indicate that the vehicle encounters an RSU at a specific time. For privacy concerns, the identity of each RSU is masked as a time-varying tag. To get the trajectory authenticated by an RSU, a vehicle needs to solve a series of computational puzzles generated by one of its neighboring RSUs. This is the first line of defending a vehicle from generating multiple trajectories. Besides, considering that a vehicle may use cloud service to bypass this computational puzzle defense line, a vehicle is required to sign on the intermediate computational puzzle results. When a vehicle obtains a verified trajectory, it is able to send an authenticated announcement message. Finally, before accepting an announcement message, we also adopt a Sybil detection method to prevent vehicles from colluding with each other to launch a Sybil attack. The details of our scheme are described in the following subsections.


### 4.2. System Initialization

In this stage, RSUs run theTSetup algorithm of the θ,n-threshold signature scheme without a trusted dealer. At the end of this algorithm, it generates a public key PK. Each RSU Rk holds a secret key xk. Besides, each vehicle holds the public keys corresponding to the secret key shares of the neighboring RSUs.Besides, TA runs theGen algorithm of message authentication code to generate the secret key MK and the AggSetup algorithm of the sequential aggregate signature (SeqAS) to generate the public parameters. MK is distributed to all the RSUs in the system. Each vehicle vi generates an initial public/private key pairs PK1vi,SK1vi using the AggKeyGen algorithm of SeqAS and obtains certificates for the public key from the TA so that vehicles can anonymously authenticate to the RSUs. Getting these certificates from the TA can be done during the annual vehicle registration at the DMV.


### 4.3. Trajectory Requests

In this section, we explain the trajectory requests stage by an example illustrated in Figure2 where a vehicle travels along 4 RSUs. It is assumed that the threshold θ of the signature scheme is set to be 3. The vehicle vi requests a trajectory proof as follows:Figure 2
Example of trajectory requests with 4 RSUs.Whenvi encounters the first RSU R1, vi interacts with R1 as follows:(1)
It computes a signatureα1vi=AggsignSK1vit0, where t0 is the timestamp, then sends the request:(1)Ticket0≔t0α1viCTAPK1vi,toRk, where CTAPK1vi is a certificate of vehicle vi which was generated by the TA.On receiving the request fromvi, R1 verifies the signature α1vi. If α1vi is valid, it computes Tag1=MACMKIDR1t1, where MK is the shared secret key among all RSUs, IDR1 is the identity of RSU R1,t1 is the current timestamp. Let tr1=PK1v1t1Tag1; it then computes σR1tr1=TSignskR1tr1 and sends back(2)TR1≔tr1σR1tr1.(2)
Whenvi receives TR1 and travels from R1 to R2, it generates a new public/private key pairs PK2vi,SK2vi as its fresh pseudonym. It needs to solve a series of the computational puzzle before submitting a trajectory request. In detail, let N0=TR1,α0vi≔TR1, and j=1. It performs the following operations repeatedly until it arrives at the communication radius of R2:(a)
Find a nonceNjsuch thatHNjPK2viNj−1<β(b)
Compute a signature using theAggSignalgorithm:αjvi=AggSignSK2viαj−1vi,Nj(c)
j=j+1Supposej=j∗; when vi arrives at the range of R1, it sends the ticket to R2:(3)Ticket1≔TR1,N1R1,…,Nj∗R1,α1vi,R1,…,αj∗vi,R1.WhenR2 receives the ticket, R2 verifies the ticket as follows:(a)
Computej^=t∗−t1/Δ, where t∗ is the current timestamp and Δ is the estimated time for a vehicle to solve one computational puzzle. If j∗≥j^, go to the next step; otherwise, return ⊥. The estimated number of puzzles vi can solve when traveling from R1 to R2,(b)
IfHNjPK2viαj−1vi<T holds for all j∈1,…,j∗, go to the next step; otherwise, return ⊥.(c)
IfAggVerifyαj∗vi,N0,…,Nj∗;PK2vi = 1, go to the next step; otherwise, return ⊥.(d)
IfTVerifytr1,σR1tr1=⊤, and Tag1=MACMKIDR1t1; otherwise, return ⊥.If the ticket is valid, it sends back the partial trajectory:(4)TR2≔tr2σR2tr2σR2tr1,where(5)tr2=PK2vit2Tag2t1Tag1,andTag2=MACMKIDR2‖t2.(3)
When the vehiclevi moves on and reaches the communication radius of R3, it computes the new ticket:(6)Ticket2≔TR2,N1R2,…,Nj∗R2,α1vi,R2,…,αj∗vi,R2,similar to the procedure when traveling fromR1 to R2. When R3 receives the ticket, it verifies the ticket. If the ticket is valid, it sends back the partial trajectory:(7)TR3≔tr3σR3tr3σR3tr2σtr1,where(8)tr3=PK3vit3Tag3t2Tag2t1Tag1,andTag3=MACMKIDR3‖t3.We note that, to computeσtr1, R3 needs to compute σR3tr1 and then perform the Reconstruct algorithm of the threshold signature scheme described in Section 3.2.


### 4.4. Message Announcement and Trajectory Update

When a vehicle encounters at leastθ RSUs, a vehicle can generate/update a trajectory and send an announcement message with its secret key.When considering the example thatθ=3, after vi receives TR3, it is able to retrieve the signature σtr1 on message tr1=PK1vit1Tag1. This message signature pair indicates that the vehicle with public key PK1vi reaches a RSU (masked as Tag1) at time t1. Hence, tr1,σtr1 is an authenticated trajectory, vi can compute the signature αviM=AggSignM and broadcast the announcement message:(9)Annou≔M,αviM;tr1,σtr1;t^,where t^ is the timestamp.Whenvi reaches R4, it can obtain(10)TR4≔tr4σR4tr4σR4tr3σtr2and hence retrieve tr2,σtr2 as its new authenticated trajectory, which indicates that the vehicle with public key PK2vi reaches a RSU (masked as Tag1) at time t1 and another RSU (masked as Tag2 at time t2).We note that if a vehicle keeps extending one trajectory, it is possible for the announcement manager to distinguish whether two announcement messages are generated by the same vehicle or not. If a vehicle does not wish to link two messages, it just needs to drop the old trajectory and start the trajectory request from scratch.


### 4.5. Announcement Verification and Sybil Attacks Detection

On receiving an announcement messageAnnou≔M,αviM;trk,σtrk;t^, the announcement manager verifies the message as follows:(a)
IfTVerifytrk,σtrk=1, go to the next step; otherwise, return ⊥(b)
IfAggVerifyM,αviM, return ⊤; otherwise, return ⊥If an announcement message passes the above verification, the announcement manager will search all existing trajectories to finish the Sybil attack detection. Similar to the method in [12], the following two types of trajectories will be regarded as Sybil trajectories:(a)
Small windows size trajectories: since it is impossible for a vehicle to travel from one RSU to another in a time much shorter than an estimated time, any trajectory containing a window size shorter than a certain time will be regarded as a Sybil trajectory(b)
Long trajectories within a time period: since a vehicle cannot encounter a large number of RSUs within a fixed time, any trajectory that is longer than an estimated length will be regarded as a Sybil trajectoryIf a trajectory survives the Sybil attack detection and the signature verification, this announcement message will be accepted by the announcement manager.


## 4.1. High-Level Description

In the scheme, we use the trajectory as the vehicle’s identity to achieve privacy-preserving authentication of announcement messages. The trajectory of a vehicle contains a number of RSUs and timestamps pairs, which indicate that the vehicle encounters an RSU at a specific time. For privacy concerns, the identity of each RSU is masked as a time-varying tag. To get the trajectory authenticated by an RSU, a vehicle needs to solve a series of computational puzzles generated by one of its neighboring RSUs. This is the first line of defending a vehicle from generating multiple trajectories. Besides, considering that a vehicle may use cloud service to bypass this computational puzzle defense line, a vehicle is required to sign on the intermediate computational puzzle results. When a vehicle obtains a verified trajectory, it is able to send an authenticated announcement message. Finally, before accepting an announcement message, we also adopt a Sybil detection method to prevent vehicles from colluding with each other to launch a Sybil attack. The details of our scheme are described in the following subsections.


## 4.2. System Initialization

In this stage, RSUs run theTSetup algorithm of the θ,n-threshold signature scheme without a trusted dealer. At the end of this algorithm, it generates a public key PK. Each RSU Rk holds a secret key xk. Besides, each vehicle holds the public keys corresponding to the secret key shares of the neighboring RSUs.Besides, TA runs theGen algorithm of message authentication code to generate the secret key MK and the AggSetup algorithm of the sequential aggregate signature (SeqAS) to generate the public parameters. MK is distributed to all the RSUs in the system. Each vehicle vi generates an initial public/private key pairs PK1vi,SK1vi using the AggKeyGen algorithm of SeqAS and obtains certificates for the public key from the TA so that vehicles can anonymously authenticate to the RSUs. Getting these certificates from the TA can be done during the annual vehicle registration at the DMV.


## 4.3. Trajectory Requests

In this section, we explain the trajectory requests stage by an example illustrated in Figure2 where a vehicle travels along 4 RSUs. It is assumed that the threshold θ of the signature scheme is set to be 3. The vehicle vi requests a trajectory proof as follows:Figure 2
Example of trajectory requests with 4 RSUs.Whenvi encounters the first RSU R1, vi interacts with R1 as follows:(1)
It computes a signatureα1vi=AggsignSK1vit0, where t0 is the timestamp, then sends the request:(1)Ticket0≔t0α1viCTAPK1vi,toRk, where CTAPK1vi is a certificate of vehicle vi which was generated by the TA.On receiving the request fromvi, R1 verifies the signature α1vi. If α1vi is valid, it computes Tag1=MACMKIDR1t1, where MK is the shared secret key among all RSUs, IDR1 is the identity of RSU R1,t1 is the current timestamp. Let tr1=PK1v1t1Tag1; it then computes σR1tr1=TSignskR1tr1 and sends back(2)TR1≔tr1σR1tr1.(2)
Whenvi receives TR1 and travels from R1 to R2, it generates a new public/private key pairs PK2vi,SK2vi as its fresh pseudonym. It needs to solve a series of the computational puzzle before submitting a trajectory request. In detail, let N0=TR1,α0vi≔TR1, and j=1. It performs the following operations repeatedly until it arrives at the communication radius of R2:(a)
Find a nonceNjsuch thatHNjPK2viNj−1<β(b)
Compute a signature using theAggSignalgorithm:αjvi=AggSignSK2viαj−1vi,Nj(c)
j=j+1Supposej=j∗; when vi arrives at the range of R1, it sends the ticket to R2:(3)Ticket1≔TR1,N1R1,…,Nj∗R1,α1vi,R1,…,αj∗vi,R1.WhenR2 receives the ticket, R2 verifies the ticket as follows:(a)
Computej^=t∗−t1/Δ, where t∗ is the current timestamp and Δ is the estimated time for a vehicle to solve one computational puzzle. If j∗≥j^, go to the next step; otherwise, return ⊥. The estimated number of puzzles vi can solve when traveling from R1 to R2,(b)
IfHNjPK2viαj−1vi<T holds for all j∈1,…,j∗, go to the next step; otherwise, return ⊥.(c)
IfAggVerifyαj∗vi,N0,…,Nj∗;PK2vi = 1, go to the next step; otherwise, return ⊥.(d)
IfTVerifytr1,σR1tr1=⊤, and Tag1=MACMKIDR1t1; otherwise, return ⊥.If the ticket is valid, it sends back the partial trajectory:(4)TR2≔tr2σR2tr2σR2tr1,where(5)tr2=PK2vit2Tag2t1Tag1,andTag2=MACMKIDR2‖t2.(3)
When the vehiclevi moves on and reaches the communication radius of R3, it computes the new ticket:(6)Ticket2≔TR2,N1R2,…,Nj∗R2,α1vi,R2,…,αj∗vi,R2,similar to the procedure when traveling fromR1 to R2. When R3 receives the ticket, it verifies the ticket. If the ticket is valid, it sends back the partial trajectory:(7)TR3≔tr3σR3tr3σR3tr2σtr1,where(8)tr3=PK3vit3Tag3t2Tag2t1Tag1,andTag3=MACMKIDR3‖t3.We note that, to computeσtr1, R3 needs to compute σR3tr1 and then perform the Reconstruct algorithm of the threshold signature scheme described in Section 3.2.


## 4.4. Message Announcement and Trajectory Update

When a vehicle encounters at leastθ RSUs, a vehicle can generate/update a trajectory and send an announcement message with its secret key.When considering the example thatθ=3, after vi receives TR3, it is able to retrieve the signature σtr1 on message tr1=PK1vit1Tag1. This message signature pair indicates that the vehicle with public key PK1vi reaches a RSU (masked as Tag1) at time t1. Hence, tr1,σtr1 is an authenticated trajectory, vi can compute the signature αviM=AggSignM and broadcast the announcement message:(9)Annou≔M,αviM;tr1,σtr1;t^,where t^ is the timestamp.Whenvi reaches R4, it can obtain(10)TR4≔tr4σR4tr4σR4tr3σtr2and hence retrieve tr2,σtr2 as its new authenticated trajectory, which indicates that the vehicle with public key PK2vi reaches a RSU (masked as Tag1) at time t1 and another RSU (masked as Tag2 at time t2).We note that if a vehicle keeps extending one trajectory, it is possible for the announcement manager to distinguish whether two announcement messages are generated by the same vehicle or not. If a vehicle does not wish to link two messages, it just needs to drop the old trajectory and start the trajectory request from scratch.


## 4.5. Announcement Verification and Sybil Attacks Detection

On receiving an announcement messageAnnou≔M,αviM;trk,σtrk;t^, the announcement manager verifies the message as follows:(a)
IfTVerifytrk,σtrk=1, go to the next step; otherwise, return ⊥(b)
IfAggVerifyM,αviM, return ⊤; otherwise, return ⊥If an announcement message passes the above verification, the announcement manager will search all existing trajectories to finish the Sybil attack detection. Similar to the method in [12], the following two types of trajectories will be regarded as Sybil trajectories:(a)
Small windows size trajectories: since it is impossible for a vehicle to travel from one RSU to another in a time much shorter than an estimated time, any trajectory containing a window size shorter than a certain time will be regarded as a Sybil trajectory(b)
Long trajectories within a time period: since a vehicle cannot encounter a large number of RSUs within a fixed time, any trajectory that is longer than an estimated length will be regarded as a Sybil trajectoryIf a trajectory survives the Sybil attack detection and the signature verification, this announcement message will be accepted by the announcement manager.


## 5. Analysis and Evaluation

### 5.1. Security Analysis

We show that our scheme achieves privacy-preserving authentication and Sybil attack resistance via the following two theorems.Theorem 1.
Our scheme achieves privacy-preserving authentication property defined in Section2.2.Proof.
We show our scheme achieves privacy-preserving authentication in the following two aspects.
Firstly, a message will be accepted by the announcement manager if and only if bothmk,σmk and M,αviM are valid message signature pairs. The first signature guarantees that the trajectory mk is signed by at least θ RSUs. The second signature guarantees that the announcement message is signed by the vehicle with public key PKkvi that is the owner of the trajectory mk. Combining the unforgeability of SeqAS signatures and threshold signatures, we have that the announcement messages are authenticated.
Secondly, the real trajectories of vehicles are hidden to both eavesdroppers and curious announcement managers. Since vehicles will generate a fresh pseudonym when they travel from one RSU to another, it is not possible to link different pseudonyms for both eavesdroppers and announcement manager. Since all the identities of RSUs are masked as a time-varying tag, it is not possible to link two vehicles that passed by the same location at different times. Hence, it is not possible for vehicles to reveal the real trajectories of vehicles.
Overall, we have that our scheme achieves privacy-preserving authentication.□Theorem 2.
Our scheme achieves the Sybil attack resistant property defined in Section2.2.Proof.
Firstly, it is difficult for a vehicle to generate two valid trajectory requests to a specific RSU. When a vehicle travels from one RSU to another, it has to solve a series of computational puzzles. Due to the security of the hash functions, the computational hash puzzle cannot be solved with less than an estimated time. Besides, since the initial random seed of the puzzle, that is,N0≔TR1 is generated by the previous RSU, the hash puzzle cannot be precomputed. Furthermore, all the subsequent random seeds depend on solutions to previous hash puzzles. Hence, the hash puzzle should be computed sequentially. This guarantees that it is difficult for a vehicle to generate two valid trajectory requests to a specific RSU.
Secondly, a rational attacker will not choose to outsource the computational puzzle. Every solution to a computational puzzle should be signed before it proceeds to the next computational puzzle. Hence, if a vehicle chooses to outsource the computational puzzle to the cloud service, it has to provide its secret key to the cloud. Otherwise, the vehicle has to communicate frequently with the cloud service, and the communication delay might be even longer than the time to solve one computational puzzle.
Overall, the proposed scheme is secure against Sybil attacks.□
In the following, we briefly argue that our scheme also satisfies the property of resisting RSU compromise and efficient RSU verification.


#### 5.1.1. Resisting RSU Compromise

The security of the threshold signature scheme guarantees that the signature is unforgeable even if the adversary hasθ−1 secret keys. Hence, even if θ−1 RSUs are compromised by an attacker, it is not possible to generate a forged trajectory.


#### 5.1.2. Efficient RSU Verification

When verifying the validity of a trajectory request, the RSU needs to verify the correctness of the solution to the hash puzzle and the intermediate signatures. It is obvious that the puzzle verification is fast since only hash computation is required. Hence, the computational puzzle also guarantees the efficiency of RSU verification even under the DoS attacks. Besides, since the aggregate signature is adopted in our scheme, multiple signatures generated by the same vehicle can be verified efficiently.


### 5.2. Theoretical Comparison

In Table1, we compare the efficiency and security of the proposed scheme with the result of Wu et al. [9] and Baza et al. [11]. For efficiency, we compare the signature size and computational cost of message announcement and verification. TExp and TPairing refer to the running time of exponential computation in G1 and pairing computation. From the benchmark result, the running time of TPairing is around 10 times that of TExp. The signature size and signature generation cost of our scheme are comparable with related works. When verifying multiple signatures, the computational cost of our proposal is lower than that of [9, 11]. Besides, compared with the existing result, our scheme achieves Sybil attack resistance without requiring long enough trajectories.Table 1
Theoretical comparison.
SignatureSignVerifyn signaturesPPA†SybilRSU compromise[9]160 bytes6TExp3nTPairing✔✗✗[11]35 bytesTExpnTPairing✔✔‡✗This work96 bytes4TExp2n−1TExp+5TPairing✔✔✔†PPA: privacy-preserving authentication; Sybil: Sybil attack resistance; RSU Compromise: security against RSU compromise attacks. ‡It achieves Sybil attack resistance with the restriction of long enough trajectories.


### 5.3. Efficiency Evaluation

To evaluate the efficiency of our scheme, we first perform a simulation to evaluate the computational cost of signature generation and verification. Besides, we compare the signature verification cost of our proposal with that of Wu et al. [9] and Baza et al. [11]. The simulations were run on a Linux machine with an Intel Core i7-4790 processor @ 3.6 GHz. The bilinear group is implemented by a BN Curve with a 128-bit security level. We use the MIRACL library to implement the cryptographic algorithms of our scheme. We simulate the stages where a vehicle requests a trajectory, and the RSU verifies the signature of vehicles. In the trajectory request generation phase, we only evaluate the signature generation time since the time for solving a puzzle is almost fixed.Figure3(a) shows the computational cost of generating and verifying signatures of our scheme. When the number of puzzles a vehicle that needs to solve varies from 1 to 31, the signature generation time grows from 0.45 milliseconds to 14 milliseconds. Meanwhile, the cost of signature verification grows much slower than the signature generation time. When the number of puzzles grows from 1 to 31, the signature verification time for RSU grows from 18.6 ms to 26.3 ms. Figure 3(b) compares the computation cost for verifying n signatures of our proposal with that of Wu et al. [9] and Baza et al. [11]. It is shown that when the number of signatures is larger than 10, our proposal has a lower computational cost than the result of [9, 11].Figure 3
The computational costs. (a) The cost of sign and verify. (b) Comparison.
(a)(b)We then use MOSAIC to simulate the communication delay of the proposed scheme and compare our result with that of [9, 11]. The road scenario is shown in Figure 4(a), which is an area of 5×10km2 in Shanghai, China. The average speed of vehicles grows from 10 m/s to 40 m/s. The number of vehicles is set to be 100. The time for each simulation is 400 s. Similar to [9], the communication delay is computed as the average delay of each message for each vehicle. Figure 4(b) shows the simulation result. At the cost of realizing a stronger security guarantee, the communication delay of our proposal is slightly higher than [11]. However, the highest delay of our proposal in the simulation is less than 4 ms.Figure 4
The communication delay. (a) The road scenario. (b) The simulation result.
(a)(b)


## 5.1. Security Analysis

We show that our scheme achieves privacy-preserving authentication and Sybil attack resistance via the following two theorems.Theorem 1.
Our scheme achieves privacy-preserving authentication property defined in Section2.2.Proof.
We show our scheme achieves privacy-preserving authentication in the following two aspects.
Firstly, a message will be accepted by the announcement manager if and only if bothmk,σmk and M,αviM are valid message signature pairs. The first signature guarantees that the trajectory mk is signed by at least θ RSUs. The second signature guarantees that the announcement message is signed by the vehicle with public key PKkvi that is the owner of the trajectory mk. Combining the unforgeability of SeqAS signatures and threshold signatures, we have that the announcement messages are authenticated.
Secondly, the real trajectories of vehicles are hidden to both eavesdroppers and curious announcement managers. Since vehicles will generate a fresh pseudonym when they travel from one RSU to another, it is not possible to link different pseudonyms for both eavesdroppers and announcement manager. Since all the identities of RSUs are masked as a time-varying tag, it is not possible to link two vehicles that passed by the same location at different times. Hence, it is not possible for vehicles to reveal the real trajectories of vehicles.
Overall, we have that our scheme achieves privacy-preserving authentication.□Theorem 2.
Our scheme achieves the Sybil attack resistant property defined in Section2.2.Proof.
Firstly, it is difficult for a vehicle to generate two valid trajectory requests to a specific RSU. When a vehicle travels from one RSU to another, it has to solve a series of computational puzzles. Due to the security of the hash functions, the computational hash puzzle cannot be solved with less than an estimated time. Besides, since the initial random seed of the puzzle, that is,N0≔TR1 is generated by the previous RSU, the hash puzzle cannot be precomputed. Furthermore, all the subsequent random seeds depend on solutions to previous hash puzzles. Hence, the hash puzzle should be computed sequentially. This guarantees that it is difficult for a vehicle to generate two valid trajectory requests to a specific RSU.
Secondly, a rational attacker will not choose to outsource the computational puzzle. Every solution to a computational puzzle should be signed before it proceeds to the next computational puzzle. Hence, if a vehicle chooses to outsource the computational puzzle to the cloud service, it has to provide its secret key to the cloud. Otherwise, the vehicle has to communicate frequently with the cloud service, and the communication delay might be even longer than the time to solve one computational puzzle.
Overall, the proposed scheme is secure against Sybil attacks.□
In the following, we briefly argue that our scheme also satisfies the property of resisting RSU compromise and efficient RSU verification.


### 5.1.1. Resisting RSU Compromise

The security of the threshold signature scheme guarantees that the signature is unforgeable even if the adversary hasθ−1 secret keys. Hence, even if θ−1 RSUs are compromised by an attacker, it is not possible to generate a forged trajectory.


### 5.1.2. Efficient RSU Verification

When verifying the validity of a trajectory request, the RSU needs to verify the correctness of the solution to the hash puzzle and the intermediate signatures. It is obvious that the puzzle verification is fast since only hash computation is required. Hence, the computational puzzle also guarantees the efficiency of RSU verification even under the DoS attacks. Besides, since the aggregate signature is adopted in our scheme, multiple signatures generated by the same vehicle can be verified efficiently.


## 5.1.1. Resisting RSU Compromise

The security of the threshold signature scheme guarantees that the signature is unforgeable even if the adversary hasθ−1 secret keys. Hence, even if θ−1 RSUs are compromised by an attacker, it is not possible to generate a forged trajectory.


## 5.1.2. Efficient RSU Verification

When verifying the validity of a trajectory request, the RSU needs to verify the correctness of the solution to the hash puzzle and the intermediate signatures. It is obvious that the puzzle verification is fast since only hash computation is required. Hence, the computational puzzle also guarantees the efficiency of RSU verification even under the DoS attacks. Besides, since the aggregate signature is adopted in our scheme, multiple signatures generated by the same vehicle can be verified efficiently.


## 5.2. Theoretical Comparison

In Table1, we compare the efficiency and security of the proposed scheme with the result of Wu et al. [9] and Baza et al. [11]. For efficiency, we compare the signature size and computational cost of message announcement and verification. TExp and TPairing refer to the running time of exponential computation in G1 and pairing computation. From the benchmark result, the running time of TPairing is around 10 times that of TExp. The signature size and signature generation cost of our scheme are comparable with related works. When verifying multiple signatures, the computational cost of our proposal is lower than that of [9, 11]. Besides, compared with the existing result, our scheme achieves Sybil attack resistance without requiring long enough trajectories.Table 1
Theoretical comparison.
SignatureSignVerifyn signaturesPPA†SybilRSU compromise[9]160 bytes6TExp3nTPairing✔✗✗[11]35 bytesTExpnTPairing✔✔‡✗This work96 bytes4TExp2n−1TExp+5TPairing✔✔✔†PPA: privacy-preserving authentication; Sybil: Sybil attack resistance; RSU Compromise: security against RSU compromise attacks. ‡It achieves Sybil attack resistance with the restriction of long enough trajectories.


## 5.3. Efficiency Evaluation

To evaluate the efficiency of our scheme, we first perform a simulation to evaluate the computational cost of signature generation and verification. Besides, we compare the signature verification cost of our proposal with that of Wu et al. [9] and Baza et al. [11]. The simulations were run on a Linux machine with an Intel Core i7-4790 processor @ 3.6 GHz. The bilinear group is implemented by a BN Curve with a 128-bit security level. We use the MIRACL library to implement the cryptographic algorithms of our scheme. We simulate the stages where a vehicle requests a trajectory, and the RSU verifies the signature of vehicles. In the trajectory request generation phase, we only evaluate the signature generation time since the time for solving a puzzle is almost fixed.Figure3(a) shows the computational cost of generating and verifying signatures of our scheme. When the number of puzzles a vehicle that needs to solve varies from 1 to 31, the signature generation time grows from 0.45 milliseconds to 14 milliseconds. Meanwhile, the cost of signature verification grows much slower than the signature generation time. When the number of puzzles grows from 1 to 31, the signature verification time for RSU grows from 18.6 ms to 26.3 ms. Figure 3(b) compares the computation cost for verifying n signatures of our proposal with that of Wu et al. [9] and Baza et al. [11]. It is shown that when the number of signatures is larger than 10, our proposal has a lower computational cost than the result of [9, 11].Figure 3
The computational costs. (a) The cost of sign and verify. (b) Comparison.
(a)(b)We then use MOSAIC to simulate the communication delay of the proposed scheme and compare our result with that of [9, 11]. The road scenario is shown in Figure 4(a), which is an area of 5×10km2 in Shanghai, China. The average speed of vehicles grows from 10 m/s to 40 m/s. The number of vehicles is set to be 100. The time for each simulation is 400 s. Similar to [9], the communication delay is computed as the average delay of each message for each vehicle. Figure 4(b) shows the simulation result. At the cost of realizing a stronger security guarantee, the communication delay of our proposal is slightly higher than [11]. However, the highest delay of our proposal in the simulation is less than 4 ms.Figure 4
The communication delay. (a) The road scenario. (b) The simulation result.
(a)(b)


## 6. Conclusion

Privacy-preserving authentication and Sybil attack defense are major challenges in IoV. In this work, we propose to use verified trajectories as the identities of vehicles to achieve privacy-preserving authentication and Sybil attack resistance. Since all the trajectories are masked, the privacy of vehicles is preserved. Furthermore, with the help of trajectories, Sybil attacks can be efficiently detected. Benefitting from our proposed puzzle chains, our scheme is secure against Sybil attacks in the presence of cloud service assistant attackers. Finally, the efficient evaluation shows that the computational overhead of our scheme is acceptable.



---

*Source: 8251697-2021-12-31.xml*