# Efficient Anonymous Data Authentication for Vehicular Ad Hoc Networks

Authors: Ping Yu; Wei Ni; Guangsheng Yu; Hua Zhang; Ren Ping Liu; Qiaoyan Wen
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Vehicular ad hoc network (VANET) encounters a critical challenge of efficiently and securely authenticating massive on-road data while preserving the anonymity and traceability of vehicles. This paper designs a new anonymous authentication approach by using an attribute-based signature. Each vehicle is defined by using a set of attributes, and each message is signed with multiple attributes, enabling the anonymity of vehicles. First, a batch verification algorithm is developed to accelerate the verification processes of a massive volume of messages in large-scale VANETs. Second, replicate messages captured by different vehicles and signed under different sets of attributes can be dereplicated with the traceability of all the signers preserved. Third, the malicious vehicles forging data can be traced from their signatures and revoked from attribute groups. The security aspects of the proposed approach are also analyzed by proving the anonymity of vehicles and the unforgeability of signatures. The efficiency of the proposed approach is numerically verified, as compared to the state of the art.


---

## Body

## 1. Introduction

Vehicular ad hoc network (VANET), also known as the Internet of Vehicles (IoV), enables vehicles to broadcast road incidents and supports critical road safety and traffic management applications, such as emergency warning, collision avoidance, road condition broadcast, and lane-changing assistance [1]. Each vehicle is expected to be equipped with an on-board unit (OBU) to collect traffic information and transmit captured data to the network to support various applications [2]. Road side units (RSUs) are infrastructures that connect vehicles to the internet and collect data captured by vehicles [3]. They can communicate with vehicles by using communication protocols, such as IEEE 802.11p protocol [4]. Based on the aggregated data, some timely actions can be taken, and hence, traffic safety and efficiency can be improved.As a large-scale open network, VANET faces a critical issue in message authentication [5]. One of the key challenges is how to protect the anonymity of vehicles that capture, authenticate, and upload data against potential adversaries, while preserving the traceability of any malicious vehicles which forge data and infrastructure which conclude with those vehicles. Another challenge is efficiency in terms of computation and storage [6]. There can be large amounts of data captured and certified by different vehicles at every moment in a large-scale VANET. Computational efficiency is critical to the authentication process. There can also be many replicas of the same data in the network. Multiple vehicles can make the same observation, separately authenticate, and upload replicas [7]. The replicas would incur substantial storage overhead, e.g., at cloud service provider (CSP).


### 1.1. Aim, Background, and Motivation

Typical solutions for anonymous message authentication are pseudonym-based techniques, group signature, ring signature, and attribute-based signature (ABS). In pseudonym-based schemes [8–10], each vehicle is equipped with multiple credentials or public keys to break the linkage between its messages. Such schemes define a time period τ and require each vehicle to change its pseudonym every τ time. Besides the anonymity of vehicles, the signature techniques, such as group signature [11–13], ring signature [14, 15], and ABS [16, 17], can be applied to achieve data integrity. Specifically, a message can be embedded into its signature by using a public hash function and then attached to the signature [17]. If the attached message is incomplete or tampered with, the hash value would be different from the embedded, and then the verification fails. In group signature schemes [11–13], a group manager integrates the identities of individuals in a group as the public information of the group, and each vehicle signs its messages on the behalf of the group [18]. In these schemes [11–13], each vehicle maintains a list of revoked vehicles. This method makes the verification time (or delay) of the signatures to grow linearly with the number of revoked vehicles. Ring signature [14, 15, 19] is considered to be a simplified group signature that only consists of vehicles, not managers. Each signer collects the public keys of vehicles in the ring and signs its messages on the behalf of the ring for anonymity. However, the revocation of compromised signers is challenging in many practical scenarios [20].Attribute-based cryptography defines each vehicle by referring to a set of attributes, all of which are owned by multiple vehicles [21]. It protects the identities of the signers from being obtained by the public network and thus provides the anonymity of the signers. A trusted authority (TA) validates the attributes of each vehicle and generates the corresponding secret keys to ensure that data is only uploaded by vehicles with legitimate attributes. Most of the ABS techniques, such as [16, 17], only allow the signatures to be verified one by one, resulting in linear growth of the delay required to verify signatures with an increasing number of messages. The attribute-based techniques are generally unsuitable to large-scale systems where the volume of data is large, such as VANETs [22].


### 1.2. Contribution

This paper presents a new and effective ABS approach for data authentication in VANETs, which protects the anonymity of vehicles against adversaries and the integrity and unforgeability of data, preserves the traceability of malicious vehicles, and facilitates revocations of malicious vehicles. The approach is also efficient in the sense that multiple signatures by different vehicles for different data can be computationally and efficiently verified together. Moreover, replicas signed by different vehicles can be aggregated and dereplicated with improved storage efficiency. The key contributions of the paper are summarized as follows:(1)
We propose a new ABS scheme enabling the identification of malicious vehicles and infrastructures and the revocation of the attribute memberships of the vehicles. The malicious vehicles forging data can be revoked from their attribute groups.(2)
Multiple messages generated and authenticated by different vehicles can be verified together via batch operations. New algorithms are developed to verify the signatures, based on the attributes involved, and are independent of the number of messages, hence substantially cutting off the authentication delay.(3)
The same data signed by different vehicles can be dereplicated while the traceability of each of the vehicles remains, hence significantly saving the storage overhead of the data.The proposed anonymous authentication approach is numerically verified by comparing it with the state of the art. As shown by the simulations, the batch verification algorithm and the data dereplication approaches can significantly reduce the computational cost in verifying multiple signatures and the storage overhead of replicas at the CSP, respectively.


### 1.3. Organization and Notation

The rest of this paper is organized as follows. In Section2, related studies are reviewed, followed by the system architecture in Section 3. In Sections 4 and 5, we propose the new authentication approach and two new efficient algorithms to accelerate signature verification. We define the security model and prove the security of the proposed approach in Section 6. In Section 7, the efficiency of the proposed approach is validated numerically in comparison with existing techniques, followed by concluding remarks in Section 8. Table 1 lists the notations used in the paper.Table 1
Notation and definition.
NotationDefinitionNThe number of attributes in the systemSNThe set of attributes in the systemλSecurity parameter of the systemVi, Aki-th vehicle and the k-th RSUKPSystem-wide public keyKMSystem master secret keyKjSystem attribute public keyKS,ViVehicle secret key of thei-th vehicle ViKS,Vi,jVehicle attribute secret key ofViuiIdentity of thei-th vehicleSiAttribute set of vehicleViℳ,ΔA message and its signatureSAjThe set of vehicles equipped with attributejvjThe membership version of attributejVLjThe list of public keys of vehicles with attributej


## 1.1. Aim, Background, and Motivation

Typical solutions for anonymous message authentication are pseudonym-based techniques, group signature, ring signature, and attribute-based signature (ABS). In pseudonym-based schemes [8–10], each vehicle is equipped with multiple credentials or public keys to break the linkage between its messages. Such schemes define a time period τ and require each vehicle to change its pseudonym every τ time. Besides the anonymity of vehicles, the signature techniques, such as group signature [11–13], ring signature [14, 15], and ABS [16, 17], can be applied to achieve data integrity. Specifically, a message can be embedded into its signature by using a public hash function and then attached to the signature [17]. If the attached message is incomplete or tampered with, the hash value would be different from the embedded, and then the verification fails. In group signature schemes [11–13], a group manager integrates the identities of individuals in a group as the public information of the group, and each vehicle signs its messages on the behalf of the group [18]. In these schemes [11–13], each vehicle maintains a list of revoked vehicles. This method makes the verification time (or delay) of the signatures to grow linearly with the number of revoked vehicles. Ring signature [14, 15, 19] is considered to be a simplified group signature that only consists of vehicles, not managers. Each signer collects the public keys of vehicles in the ring and signs its messages on the behalf of the ring for anonymity. However, the revocation of compromised signers is challenging in many practical scenarios [20].Attribute-based cryptography defines each vehicle by referring to a set of attributes, all of which are owned by multiple vehicles [21]. It protects the identities of the signers from being obtained by the public network and thus provides the anonymity of the signers. A trusted authority (TA) validates the attributes of each vehicle and generates the corresponding secret keys to ensure that data is only uploaded by vehicles with legitimate attributes. Most of the ABS techniques, such as [16, 17], only allow the signatures to be verified one by one, resulting in linear growth of the delay required to verify signatures with an increasing number of messages. The attribute-based techniques are generally unsuitable to large-scale systems where the volume of data is large, such as VANETs [22].


## 1.2. Contribution

This paper presents a new and effective ABS approach for data authentication in VANETs, which protects the anonymity of vehicles against adversaries and the integrity and unforgeability of data, preserves the traceability of malicious vehicles, and facilitates revocations of malicious vehicles. The approach is also efficient in the sense that multiple signatures by different vehicles for different data can be computationally and efficiently verified together. Moreover, replicas signed by different vehicles can be aggregated and dereplicated with improved storage efficiency. The key contributions of the paper are summarized as follows:(1)
We propose a new ABS scheme enabling the identification of malicious vehicles and infrastructures and the revocation of the attribute memberships of the vehicles. The malicious vehicles forging data can be revoked from their attribute groups.(2)
Multiple messages generated and authenticated by different vehicles can be verified together via batch operations. New algorithms are developed to verify the signatures, based on the attributes involved, and are independent of the number of messages, hence substantially cutting off the authentication delay.(3)
The same data signed by different vehicles can be dereplicated while the traceability of each of the vehicles remains, hence significantly saving the storage overhead of the data.The proposed anonymous authentication approach is numerically verified by comparing it with the state of the art. As shown by the simulations, the batch verification algorithm and the data dereplication approaches can significantly reduce the computational cost in verifying multiple signatures and the storage overhead of replicas at the CSP, respectively.


## 1.3. Organization and Notation

The rest of this paper is organized as follows. In Section2, related studies are reviewed, followed by the system architecture in Section 3. In Sections 4 and 5, we propose the new authentication approach and two new efficient algorithms to accelerate signature verification. We define the security model and prove the security of the proposed approach in Section 6. In Section 7, the efficiency of the proposed approach is validated numerically in comparison with existing techniques, followed by concluding remarks in Section 8. Table 1 lists the notations used in the paper.Table 1
Notation and definition.
NotationDefinitionNThe number of attributes in the systemSNThe set of attributes in the systemλSecurity parameter of the systemVi, Aki-th vehicle and the k-th RSUKPSystem-wide public keyKMSystem master secret keyKjSystem attribute public keyKS,ViVehicle secret key of thei-th vehicle ViKS,Vi,jVehicle attribute secret key ofViuiIdentity of thei-th vehicleSiAttribute set of vehicleViℳ,ΔA message and its signatureSAjThe set of vehicles equipped with attributejvjThe membership version of attributejVLjThe list of public keys of vehicles with attributej


## 2. Related Work

In pseudonym-based schemes, each vehicle is issued a short-term pseudonym and corresponding private key. With the pseudonym and private key, a vehicle can anonymously generate identity-based aggregate signatures by choosing a one-time string. In [9], the authors adopted a hash message authentication code to achieve efficient authentication. However, frequent changes of pseudonyms could not be avoided. In [22], a pseudonym-based anonymous authentication in VANET was proposed. Multiple vehicles shared the same secret value to support batch verification. This would be inconvenient for highly dynamic networks, such as VANET, where vehicles move all the time and the messages to be batch-verified may be from the vehicles not sharing the same secret value.In group signature schemes [11–13], a group manager integrates the identities of individuals in a group as the public information of the group, and each vehicle signs its messages on the behalf of the group [18]. In these schemes [11–13], each vehicle maintains a list of revoked vehicles. This method makes the verification time (or delay) of the signatures to grow linearly with the number of revoked vehicles. The authors of [23] proposed an anonymous authentication system by using a time-dependent group signature technique supportive of signer revocation. The authors assumed the existence of a time-dependent token. Each signer with a unique identity can generate a signature on a message by using its secret keys and the time token. Multiple messages of the same signer are linkable if they are signed within a given period. The authors of [12] proposed a threshold group signature scheme, where receivers only accept messages confirmed by more than a prespecified number of vehicles.Ring signature [14, 15, 19] is considered to be a simplified group signature that only consists of vehicles, not managers. Each signer collects the public keys of vehicles in the ring and signs its messages on the behalf of the ring for anonymity. Au [14] proposed a scheme with constant signature size and proved its security under the Diffie–Hellman inversion assumption. In [19], a secure and unrestricted identity-based ring signature scheme was developed. The authors proved that their scheme can achieve signer anonymity in the standard model. However, the revocation of compromised signers is challenging in many practical scenarios [20].ABS was first proposed in [21] as a primitive to protect the privacy of message signers. Each message is signed by a predicate of attributes. In [16], the ABS technique was employed to achieve outsourced cloud data integrity auditing. A data owner could specify designated auditors with particular attributes to confirm the integrity of the data. In [17], the anonymity of vehicles was ensured by a t,n threshold predicate. In addition, the authors designed that the identity of a malicious vehicle could be traced from its signature and revoked from the attribute groups. In [20], all data were signed under a threshold predicate. Specifically, a signature was generated under a threshold gate predicate. The verification of the signature could only confirm that the signatures were generated by t attributes out of n.Batch verification has been widely employed in anonymous vehicular scenarios to accelerate signature verification [9, 22, 24–30]. Multiple signatures can be verified together, thus shortening latency. An identity-based aggregate signature was proposed in [26]. The individual identity-based signatures generated by different vehicles can be aggregated and verified together. The messages signed under the same one-time string can be aggregated and verified by the nearby RSUs. Zhang et al. [30] proposed a one-time identity-based aggregate signature. The system proposed in [30] includes a trusted authority (TA) and multiple lower-level TAs. The signature is only valid under the user’s identity and public information of the lower-level TAs. Multiple signatures can be verified together, and the signatures can be compressed into one to reduce storage requirement.


## 3. System Architecture

Figure1 shows the proposed system which consists of a TA, a large number of vehicles, multiple RSUs, and a CSP.Figure 1
Architecture of the proposed system.The TA is the only fully trusted entity in the system. It produces public parameters of the system, initializes RSUs by publishing public keys, and registers vehicles by issuing secret keys for their legitimate attributes. The TA is also responsible for identifying malicious vehicles that forge messages and revoking the vehicles and/or their attributes. Each vehicle registers at the TA and requests the secret keys corresponding to its attributes. The TA issues a dedicated random value (as the identity of the vehicle) and embeds the value into all of the attribute-related secret keys of the vehicle. This ensures the traceability of the signatures of the vehicle by the TA.Each vehicle can sign messages by using a subset of its attribute secret keys and send the signed messages to its nearest RSU. The use of attributes ensures the anonymity of vehicles. Any adversaries can only infer that the message is generated by a qualified vehicle with legitimate attributes and cannot identify the vehicle.The RSUs are fixed infrastructures at the roadside and act as a bridge between vehicles and CSP. They are responsible for collecting messages sent by vehicles, transferring the messages to the CSP, and providing services to nearby vehicles.In our scheme, the CSP is connected to all the RSUs. It has the ability to verify all the signatures from the network and make decisions based on these data. The CSP can verify multiple signatures at once by using the proposed batch verification algorithm and suppress replicas signed by different vehicles to improve its storage efficiency.The proposed efficient attribute-based anonymous authentication system constitutes the following suite of new algorithms:(i)
Initialization:λ⟶KP,KP′,KM,Kj∀j∈SN. The TA takes a security parameter λ as the input and outputs the system public keys (PKs) KP and KP′, the system master secret key (MSK) KM, and system attribute public keys Kj for each legitimate attribute j∈SN of the system.(ii)
Vehicle registration:Vi,Si,KM,Kj∀j∈Si⟶KS,Vi,KS,Vi,j∀j∈Si. By taking KM and Kj∀j∈Si as the input, the TA generates the vehicle secret key KS,Vi for the vehicle and vehicle attribute secret keys KS,Vi,j for each attribute j∈Si of the vehicle Vi.(iii)
Signature generation:KP,KP′,Kj∀j∈Si′,KS,Vi, KS,Vi,j∀j∈Si, ℳ⟶Δ. With the input of the public parameters, i.e., KP, KP′, and Kj∀j∈Si, the vehicle Vi signs the data ℳ by using a subset of its attribute set, denoted by Si′⊂Si. The vehicle Vi outputs the signature Δ with the data ℳ.(iv)
Signature verification:KP,KP′,Kj∀j∈Si,Δ⟶“0”or“1”. The CSP takes the system public parameters and the signature Δ as the input, verifies the signature, and outputs “0” or “1” to indicate that the signature is verified unsuccessfully or successfully, respectively.(v)
Trace:KM,Δ⟶Vi. Given the MSK and Δ, the TA retrieves the identity of the vehicle by running this algorithm.(vi)
Attribute revocation:KM,Kj,Vi⟶Kj′,KS,Vi,j′. The TA can revoke any attribute j of any vehicle i by taking the system attribute public key of attribute j as the input and then generates a new system attribute public key and vehicle attribute secret keys.As part of the suite of algorithms, two new algorithms are explicitly designed to accelerate the verification process of the proposed attribute-based anonymous authentication system in VANETs.(i)
Batch verification:KP,KP′,Kj∀j∈SN,Δk∀k∈1,L⟶“0”or“1”. The CSP is designed to verify multiple messages signed by different vehicles together using batch operations. Given the signatures Δ1,…,ΔL, the CSP outputs “1” to indicate that all the L signatures are legitimate. Otherwise, the CSP outputs “0.”(ii)
Dereplication:KP,KP′,Kj∀j∈SN,Δk∀k∈1,K⟶Δ. Given K signatures of the same message, the CSP generates a new signature Δ, which records that the message has been signed by K vehicles and preserves the traceability of the vehicles.


## 4. Anonymous Authentication Algorithm

### 4.1. System Parameter Initialization

The TA initializes the system by generating the system public key, MSK, and the system attribute public keys. Suppose that there areN attributes in the system. The set SN collects all the N attributes. The TA first generates two groups G and GT. Let g and eg,g be the generators of groups G and GT, respectively. e is a bilinear mapping (given two multiplicative groups G and GT with prime order p, the bilinear mapping e maps two elements in G to another element in GT, i.e., e:G×G⟶GT. This mapping has two properties: (1) bilinearity: ega,gb = eg,gab = egb,ga, a,b∈ℤP, where ℤP is an additive cyclic group [31]. (2) Nondegeneracy: eg,g≠1. Here, the number of bits in an element of the multiplicative group depends on a security parameter λ) which maps any two elements in G to an element in GT. H· is a hash function which maps a binary sequence to an element in G, i.e., 0,1∗⟶G. By using H·, any message can be mapped to a group element in G and embedded into a signature.The TA selects two random valuesα,β∈ℤp as the system master secret key (MSK), KM=α,β, and publishes the system public keys KP=gαβ and KP′=gβ. The MSK is only known to the TA to trace misbehaved or malicious vehicles. For each attribute j, the TA selects random values vj and sj∈ℤp, sets hj=gsj, and generates the system attribute public keys for attribute j, denoted by Kj, as given by(1)Kj=hjβvj,where vj indicates the current version of the membership of attribute group j. vj is important to revoke the attributes of vehicles (as will be described in Section 4.5). The system public key and system attribute public keys are given by(2)PP=KP,KP′,∀j∈SN:Kj.For each attributej, the TA maintains the vehicle public keys of all the vehicles equipped with the attribute, denoted by VLj:(3)VLj=∀i∈SAj:eg,gui,where SAj is the current set of vehicles with attribute j. The TA publishes VLj. If the membership of attribute j changes, the TA updates the value vj and the system attribute public key Kj and cancels eg,gui of any revoked vehicle Vi from VLj, i.e., VLj′=VLj,eg,gui.


### 4.2. Registration of the Vehicle

For each vehicle, the TA assigns a unique random valueui and generates eg,gui as the vehicle public key of the vehicle. The TA also computes the vehicle secret key KS,Vi for the vehicle. KS,Vi=gui. Suppose that each vehicle Vi has the set of attributes Si. The vehicle can sign messages by using a subset of its attributes. For each attribute of the vehicle j∈Si, the TA generates the vehicle attribute secret key as follows:(4)KS,Vi,j=hjuivj·gαa.The secret key of vehicleVi is given by(5)SK=KS,Vi,KS,Vi,j,∀j∈Si.Note that the random valueui which is specific to the i-th vehicle is embedded into the vehicle attribute secret key KS,Vi,j to retain the traceability of the vehicle. The vehicle may broadcast faked messages. The unique value of the vehicle, ui, can be recovered by the TA from any signature of the vehicle, as will be described in Section 4.5, and thus ensures the traceability of the vehicle. Moreover, no attacker can forge the signatures of the vehicle without the secret value ui.


### 4.3. Signature Generation

Any vehicleVi can sign a message ℳ by using a subset of its attributes Si′⊂Si. The vehicle selects a random value x∈ℤp and maps ℳ to an element in G by using a hash function H·. The resultant signature of the vehicle Vi consists of the following:(6)σ1=∏j∈Si′KS,Vi,jx·Hℳx=∏j∈Si′hjuivjx·∏j∈Si′gαx·Hℳx=∏j∈Si′hjuivjx·gαx|Si′|·Hℳx,(7)σ2=KS,Vix=guix,(8)σ3=KP′x=gβx,(9)σ4=gx.The messageℳ is sent to the CSP, together with the attribute set Si′ and the signature, as given by(10)Δ=ℳ,Si′,σ1,σ2,σ3,σ4.


### 4.4. Signature Verification

Given the system public parameters in (2) and the signature Δ in (10), any data users can verify the signature with no need for the identity of the vehicle producing the signature. The data users can confirm that the data is signed by a legitimate vehicle with the up-to-date secret keys of all the attributes in Si′ if and only if(11)eσ1,KP′=eσ2,∏j∈Si′Kj⋅eσ3,Hℳ⋅eσ4,KPSi′.Proof.
Suppose that the version of the attributes embedded in the signature isvj,∀j∈Si′, and the latest membership version of the j-th attribute is vj′,j∈Si′. The left-hand side (LHS) of (11) can be written as(12)e∏j∈Si′hjuivjx⋅gαx|Si′|⋅Hℳx,gβ=∏j∈Si′ehjuivjx,gβ⋅egαx|Si′|,gβ⋅eHℳx,gβ=∏j∈Si′ehj,gβuivjx⋅eg,gβαx|Si′|⋅eHℳ,gβx,where the equalities are taken based on the bilinearity of the bilinear mapping e. Similarly, we can rewrite the right-hand side (RHS) of (11), as given by(13)eguix,∏j∈Si′hjβvj′⋅egβx,Hℳ⋅egx,gαβ|Si′|=∏j∈Si′eguix,hjβvj′⋅eg,Hℳβx⋅eg,gxαβ|Si′|=∏j∈Si′ehj,gβuivj′x⋅eg,gxαβ|Si′|⋅eHℳ,gβx.
By comparing (12) and (13), we can see that the LHS and RHS of (11) are equal if and only if vj=vj′. In other words, it is confirmed that the signature is signed by a legitimate vehicle with the up-to-date vehicle secret keys for the attributes if and only if (11) holds.


### 4.5. Traceability of Vehicles and Attribute Revocation

#### 4.5.1. Traceability of Malicious Vehicles

An important aspect of the proposed approach is its traceability of malicious vehicles through anonymous signatures. As described in Section4.1, ui is a unique random value for vehicle i, and the TA can use it to identify the vehicle at the TA. The TA stores all the values ui,∀i. Then, the TA can take each ui as the input and test whether the following equation holds:(14)σ2=σ4ui.If (14) holds, the TA identifies ui as the identity of the malicious vehicle. Otherwise, the TA iterates other values until (14) holds.


#### 4.5.2. Attribute Revocation

When a malicious vehicle is found, as described in Section4.5.1, the TA first detects the attributes of the vehicle and generates new public keys for the attributes. After that, the TA updates the attribute-related secret keys of the other legitimate vehicles equipped with the attributes. In this case, the attribute-related secret keys of the malicious vehicle are no longer up to date and cannot be used to generate legitimate signatures. In other words, the malicious vehicle is revoked from the system.The TA is able to revoke any attribute, e.g., attributej, of any vehicle in two steps. The TA chooses a new membership version of the attribute, denoted by vj′, and updates the system public key of this attribute, as given by(15)Kj′=hjβvj′.The TA also generates an update key for each vehicleVi equipped with attribute j since the membership of attribute j has changed. The update key can be given by(16)UKui=hjuivj′−vj.After receivingUKui, Vi updates its secret key of attribute j as follows:(17)KS,Vi,j′=KS,Vi,j⋅UKui=hjuivj⋅gα⋅hjuivj′−vj=hjuivj′⋅gα.


## 4.1. System Parameter Initialization

The TA initializes the system by generating the system public key, MSK, and the system attribute public keys. Suppose that there areN attributes in the system. The set SN collects all the N attributes. The TA first generates two groups G and GT. Let g and eg,g be the generators of groups G and GT, respectively. e is a bilinear mapping (given two multiplicative groups G and GT with prime order p, the bilinear mapping e maps two elements in G to another element in GT, i.e., e:G×G⟶GT. This mapping has two properties: (1) bilinearity: ega,gb = eg,gab = egb,ga, a,b∈ℤP, where ℤP is an additive cyclic group [31]. (2) Nondegeneracy: eg,g≠1. Here, the number of bits in an element of the multiplicative group depends on a security parameter λ) which maps any two elements in G to an element in GT. H· is a hash function which maps a binary sequence to an element in G, i.e., 0,1∗⟶G. By using H·, any message can be mapped to a group element in G and embedded into a signature.The TA selects two random valuesα,β∈ℤp as the system master secret key (MSK), KM=α,β, and publishes the system public keys KP=gαβ and KP′=gβ. The MSK is only known to the TA to trace misbehaved or malicious vehicles. For each attribute j, the TA selects random values vj and sj∈ℤp, sets hj=gsj, and generates the system attribute public keys for attribute j, denoted by Kj, as given by(1)Kj=hjβvj,where vj indicates the current version of the membership of attribute group j. vj is important to revoke the attributes of vehicles (as will be described in Section 4.5). The system public key and system attribute public keys are given by(2)PP=KP,KP′,∀j∈SN:Kj.For each attributej, the TA maintains the vehicle public keys of all the vehicles equipped with the attribute, denoted by VLj:(3)VLj=∀i∈SAj:eg,gui,where SAj is the current set of vehicles with attribute j. The TA publishes VLj. If the membership of attribute j changes, the TA updates the value vj and the system attribute public key Kj and cancels eg,gui of any revoked vehicle Vi from VLj, i.e., VLj′=VLj,eg,gui.


## 4.2. Registration of the Vehicle

For each vehicle, the TA assigns a unique random valueui and generates eg,gui as the vehicle public key of the vehicle. The TA also computes the vehicle secret key KS,Vi for the vehicle. KS,Vi=gui. Suppose that each vehicle Vi has the set of attributes Si. The vehicle can sign messages by using a subset of its attributes. For each attribute of the vehicle j∈Si, the TA generates the vehicle attribute secret key as follows:(4)KS,Vi,j=hjuivj·gαa.The secret key of vehicleVi is given by(5)SK=KS,Vi,KS,Vi,j,∀j∈Si.Note that the random valueui which is specific to the i-th vehicle is embedded into the vehicle attribute secret key KS,Vi,j to retain the traceability of the vehicle. The vehicle may broadcast faked messages. The unique value of the vehicle, ui, can be recovered by the TA from any signature of the vehicle, as will be described in Section 4.5, and thus ensures the traceability of the vehicle. Moreover, no attacker can forge the signatures of the vehicle without the secret value ui.


## 4.3. Signature Generation

Any vehicleVi can sign a message ℳ by using a subset of its attributes Si′⊂Si. The vehicle selects a random value x∈ℤp and maps ℳ to an element in G by using a hash function H·. The resultant signature of the vehicle Vi consists of the following:(6)σ1=∏j∈Si′KS,Vi,jx·Hℳx=∏j∈Si′hjuivjx·∏j∈Si′gαx·Hℳx=∏j∈Si′hjuivjx·gαx|Si′|·Hℳx,(7)σ2=KS,Vix=guix,(8)σ3=KP′x=gβx,(9)σ4=gx.The messageℳ is sent to the CSP, together with the attribute set Si′ and the signature, as given by(10)Δ=ℳ,Si′,σ1,σ2,σ3,σ4.


## 4.4. Signature Verification

Given the system public parameters in (2) and the signature Δ in (10), any data users can verify the signature with no need for the identity of the vehicle producing the signature. The data users can confirm that the data is signed by a legitimate vehicle with the up-to-date secret keys of all the attributes in Si′ if and only if(11)eσ1,KP′=eσ2,∏j∈Si′Kj⋅eσ3,Hℳ⋅eσ4,KPSi′.Proof.
Suppose that the version of the attributes embedded in the signature isvj,∀j∈Si′, and the latest membership version of the j-th attribute is vj′,j∈Si′. The left-hand side (LHS) of (11) can be written as(12)e∏j∈Si′hjuivjx⋅gαx|Si′|⋅Hℳx,gβ=∏j∈Si′ehjuivjx,gβ⋅egαx|Si′|,gβ⋅eHℳx,gβ=∏j∈Si′ehj,gβuivjx⋅eg,gβαx|Si′|⋅eHℳ,gβx,where the equalities are taken based on the bilinearity of the bilinear mapping e. Similarly, we can rewrite the right-hand side (RHS) of (11), as given by(13)eguix,∏j∈Si′hjβvj′⋅egβx,Hℳ⋅egx,gαβ|Si′|=∏j∈Si′eguix,hjβvj′⋅eg,Hℳβx⋅eg,gxαβ|Si′|=∏j∈Si′ehj,gβuivj′x⋅eg,gxαβ|Si′|⋅eHℳ,gβx.
By comparing (12) and (13), we can see that the LHS and RHS of (11) are equal if and only if vj=vj′. In other words, it is confirmed that the signature is signed by a legitimate vehicle with the up-to-date vehicle secret keys for the attributes if and only if (11) holds.


## 4.5. Traceability of Vehicles and Attribute Revocation

### 4.5.1. Traceability of Malicious Vehicles

An important aspect of the proposed approach is its traceability of malicious vehicles through anonymous signatures. As described in Section4.1, ui is a unique random value for vehicle i, and the TA can use it to identify the vehicle at the TA. The TA stores all the values ui,∀i. Then, the TA can take each ui as the input and test whether the following equation holds:(14)σ2=σ4ui.If (14) holds, the TA identifies ui as the identity of the malicious vehicle. Otherwise, the TA iterates other values until (14) holds.


### 4.5.2. Attribute Revocation

When a malicious vehicle is found, as described in Section4.5.1, the TA first detects the attributes of the vehicle and generates new public keys for the attributes. After that, the TA updates the attribute-related secret keys of the other legitimate vehicles equipped with the attributes. In this case, the attribute-related secret keys of the malicious vehicle are no longer up to date and cannot be used to generate legitimate signatures. In other words, the malicious vehicle is revoked from the system.The TA is able to revoke any attribute, e.g., attributej, of any vehicle in two steps. The TA chooses a new membership version of the attribute, denoted by vj′, and updates the system public key of this attribute, as given by(15)Kj′=hjβvj′.The TA also generates an update key for each vehicleVi equipped with attribute j since the membership of attribute j has changed. The update key can be given by(16)UKui=hjuivj′−vj.After receivingUKui, Vi updates its secret key of attribute j as follows:(17)KS,Vi,j′=KS,Vi,j⋅UKui=hjuivj⋅gα⋅hjuivj′−vj=hjuivj′⋅gα.


## 4.5.1. Traceability of Malicious Vehicles

An important aspect of the proposed approach is its traceability of malicious vehicles through anonymous signatures. As described in Section4.1, ui is a unique random value for vehicle i, and the TA can use it to identify the vehicle at the TA. The TA stores all the values ui,∀i. Then, the TA can take each ui as the input and test whether the following equation holds:(14)σ2=σ4ui.If (14) holds, the TA identifies ui as the identity of the malicious vehicle. Otherwise, the TA iterates other values until (14) holds.


## 4.5.2. Attribute Revocation

When a malicious vehicle is found, as described in Section4.5.1, the TA first detects the attributes of the vehicle and generates new public keys for the attributes. After that, the TA updates the attribute-related secret keys of the other legitimate vehicles equipped with the attributes. In this case, the attribute-related secret keys of the malicious vehicle are no longer up to date and cannot be used to generate legitimate signatures. In other words, the malicious vehicle is revoked from the system.The TA is able to revoke any attribute, e.g., attributej, of any vehicle in two steps. The TA chooses a new membership version of the attribute, denoted by vj′, and updates the system public key of this attribute, as given by(15)Kj′=hjβvj′.The TA also generates an update key for each vehicleVi equipped with attribute j since the membership of attribute j has changed. The update key can be given by(16)UKui=hjuivj′−vj.After receivingUKui, Vi updates its secret key of attribute j as follows:(17)KS,Vi,j′=KS,Vi,j⋅UKui=hjuivj⋅gα⋅hjuivj′−vj=hjuivj′⋅gα.


## 5. Batch Verification and Dereplication

### 5.1. Batch Verification

The proposed approach allows multiple signatures to be verified at one go, referred to as “batch verification.” This is important to reduce the computational complexity and delay of signature verification, especially in the presence of a large number of devices and a high volume of data. Without loss of generality, we consider thatL messages, ℳ1, ⋯, ℳL, are signed by L different vehicles, V1,…,VL, by using the attribute sets S1′,…,SL′, respectively. From (10), for each of the vehicles, i.e., vehicle i, the signatures are given by(18)Δi=ℳi,Si′,σi,1,σi,2,σi,3,σi,4,i=1,…,L,where, based on (6)–(9), we have(19)σi,1=∏j∈Si′hjuivjxi⋅gαxiSi′⋅Hℳixi,σi,2=guixi,σi,3=gβxi,σi,4=gxi.LetS=S1′∪⋯∪SL′. The set SAj collects vehicles that have signed one of the L messages by using attribute j. AS is the set of RSUs included in the L signatures. It is confirmed that the signatures Δ1,…,ΔL are signed by the legitimate vehicles with the update-to-date secret keys if and only if(20)e∏i∈1,Lσi,1,KP′=∏j∈Se∏i∈SAjσi,2,Kj⋅∏i∈1,LeHℳi,σi,3⋅e∏i∈1,Lσi,4,KPSi′.Proof.
The correctness of (20) is proved as follows. Referring to the proof of (11), we assume that the membership version embedded into the signatures is vj, and the current membership version of attribute j is vj′. We rewrite the LHS of (20) as(21)∏i∈1,Le∏j∈Si′hjuivjxi⋅gαxiSi′⋅Hℳixi,gβ,(22)=∏j∈Sehjvj∑i∈SAjuixi,gβ⋅∏i∈1,LegαxiSi′,gβ⋅∏i∈1,LeHℳixi,gβ,(23)=∏j∈Sehj,gβvj∑i∈SAjuixi⋅∏i∈1,Leg,gαxiβSi′⋅∏i∈1,LeHℳi,gβxi,where the two equalities are due to the bilinearity of bilinear mapping. In specific, (21) can be written as the product of three bilinear mappings: (a) ∏i∈1,Le∏j∈Si′hjuivjxi,gβ, (b) ∏i∈1,Le∏j∈Si′gαxiSi′,gβ, and (c) ∏i∈1,LeHℳixi,gβ. Both (a) and (b) can be rearranged according to the attribute set S which is the union of Si′, ∀i∈1,L. The collection of vehicles signing messages by using attribute j is SAj. (22) is rewritten as (23) based on the bilinearity of e. Specifically, the exponents of hj and g inside the bilinear mappings (a), (b), and (c) are moved out of the mappings.
We also rewrite the RHS of (20), as given by(24)∏j∈Se∏i∈SAjguixi,hjβvj′⋅∏i∈1,LeHℳi,gβxi⋅e∏i∈1,Lgxi,gαβSi′,(25)=∏j∈Seg∑i∈SAjuixi,hjβvj′⋅∏i∈1,LeHℳi,gβxi⋅∏i∈1,Legxi,gαβ|Si′|,(26)=∏j∈Sehj,gβvj′∑i∈SAjuixi⋅∏i∈1,LeHℳi,gβxi⋅∏i∈1,Leg,gαβxiSi′,where the bilinearity of the mapping e ensures the correctness of the equalities.
By comparing (23) and (26), we conclude that the LHS and RHS of (20) are equal if and only if vj=vj′. In other words, if (20) holds, all the L signatures are generated with up-to-date vehicle attribute secret keys. The L signatures are all legitimate.


### 5.2. Data Dereplication

The second feature of the proposed approach is its dereplication of signatures describing the same message while preserving the traceability of the vehicles certifying the message. Suppose that messageℳ is signed by K vehicles, denoted by V1,…,VK, by using the K attribute sets S1′,…,SK′, respectively. Let S′=S1′∪⋯∪SK′. The set SAj collects the vehicles equipped with attribute j. With reference to (10), the signatures are given by(27)Δi=ℳ,Si,σi,1,σi,2,σi,3,σi,4,i=1,…,K,where, based on (6)–(9), we have(28)σi,1=∏j∈Si′hjuivjxi⋅gαxiSi′⋅Hℳixi,σi,2=guixi,σi,3=gβxi,σi,4=gxi.Here,x1,…,xK stand for the random values selected by the vehicles V1,…,VK, respectively.Let a matrixΓK,S′ specify the attributes used to sign the message ℳ:(29)ΓK,S′=b1,1b1,2⋯b1,|S′|b2,1b2,2⋯b2,|S′|⋮⋮⋮bK,1bK,2⋯bK,|S′|,where S′ is the size of S′ and bi,j∈0,1. bi,j=1 indicates that vehicle Vi signs ℳ by using attribute j. bi,j=0 indicates otherwise.The CSP defines the aggregated signature, as given by(30)Δ=ℳ,Γ,A1,A2,j∀j∈S′,A3,A4,σi,2,σi,4i∈1,K,where(31)A1=∏i∈1,Kσi,1=∏j∈S′hjvj∑i∈SAjuixi⋅∏i∈1,KgαxiSi′⋅Hℳ∑i∈1,Kxi,A2,j=∏i∈SAjσi,2=∏i∈SAjguixi=g∑i∈SAjuixi,A3=∏i∈1,Kσi,3=∏i∈1,Kgβxi=gβ∑i∈1,Kxi,A4=∏i∈1,Kσi,4=g∑i∈1,Kxi.Any data user has the ability to verify the aggregated signature, i.e.,Δ, if and only if(32)eA1,KP′=∏j∈S′eA2,j,Kj⋅eA3,Hℳ⋅eA4Si′,KP.Proof.
As defined in the proof of (11), the membership version of attribute j embedded into the signatures is vj, and the membership version in the system attribute public key, i.e., Kj, is vj′. We rewrite the LHS of (32) as(33)e∏j∈S′hjvj∑i∈SAjuixi⋅∏j∈1,KgαxiSi′⋅Hℳ∑i∈1,Kxi,gβ,(34)=e∏j∈S′hjvj∑i∈SAjuixi,gβ·∏j∈1,KegαxiSi′,gβ⋅eHℳ∑i∈1,Kxi,gβ,(35)=∏j∈S′ehj,gβvj∑i∈SAjuixi⋅∏j∈1,Keg,gαβxiSi′⋅eHℳ,gβ∑i∈1,Kxi,where the two equalities are due to the bilinearity of bilinear mapping. (33) can be rewritten as the product of three mappings in (34). The exponents of the group elements of G are moved outside the mapping e in (35).
We also rewrite the RHS of (32) as(36)∏j∈S′eg∑i∈SAjuixi,hjβvj′⋅egβ∑i∈1,Kxi,Hℳ⋅∏j∈1,KegxiSi′,gαβ,(37)=∏j∈S′ehj,gβvj′∑i∈SAjuixi⋅eHℳ,gβ∑i∈1,Kxi⋅∏j∈1,Keg,gαβxiSi′.
By comparing (35) and (37), we show that the LHS and RHS of (32) are equal if and only if vj=vj′. Then, we conclude that message ℳ is signed by K vehicles with legitimate secret keys.


## 5.1. Batch Verification

The proposed approach allows multiple signatures to be verified at one go, referred to as “batch verification.” This is important to reduce the computational complexity and delay of signature verification, especially in the presence of a large number of devices and a high volume of data. Without loss of generality, we consider thatL messages, ℳ1, ⋯, ℳL, are signed by L different vehicles, V1,…,VL, by using the attribute sets S1′,…,SL′, respectively. From (10), for each of the vehicles, i.e., vehicle i, the signatures are given by(18)Δi=ℳi,Si′,σi,1,σi,2,σi,3,σi,4,i=1,…,L,where, based on (6)–(9), we have(19)σi,1=∏j∈Si′hjuivjxi⋅gαxiSi′⋅Hℳixi,σi,2=guixi,σi,3=gβxi,σi,4=gxi.LetS=S1′∪⋯∪SL′. The set SAj collects vehicles that have signed one of the L messages by using attribute j. AS is the set of RSUs included in the L signatures. It is confirmed that the signatures Δ1,…,ΔL are signed by the legitimate vehicles with the update-to-date secret keys if and only if(20)e∏i∈1,Lσi,1,KP′=∏j∈Se∏i∈SAjσi,2,Kj⋅∏i∈1,LeHℳi,σi,3⋅e∏i∈1,Lσi,4,KPSi′.Proof.
The correctness of (20) is proved as follows. Referring to the proof of (11), we assume that the membership version embedded into the signatures is vj, and the current membership version of attribute j is vj′. We rewrite the LHS of (20) as(21)∏i∈1,Le∏j∈Si′hjuivjxi⋅gαxiSi′⋅Hℳixi,gβ,(22)=∏j∈Sehjvj∑i∈SAjuixi,gβ⋅∏i∈1,LegαxiSi′,gβ⋅∏i∈1,LeHℳixi,gβ,(23)=∏j∈Sehj,gβvj∑i∈SAjuixi⋅∏i∈1,Leg,gαxiβSi′⋅∏i∈1,LeHℳi,gβxi,where the two equalities are due to the bilinearity of bilinear mapping. In specific, (21) can be written as the product of three bilinear mappings: (a) ∏i∈1,Le∏j∈Si′hjuivjxi,gβ, (b) ∏i∈1,Le∏j∈Si′gαxiSi′,gβ, and (c) ∏i∈1,LeHℳixi,gβ. Both (a) and (b) can be rearranged according to the attribute set S which is the union of Si′, ∀i∈1,L. The collection of vehicles signing messages by using attribute j is SAj. (22) is rewritten as (23) based on the bilinearity of e. Specifically, the exponents of hj and g inside the bilinear mappings (a), (b), and (c) are moved out of the mappings.
We also rewrite the RHS of (20), as given by(24)∏j∈Se∏i∈SAjguixi,hjβvj′⋅∏i∈1,LeHℳi,gβxi⋅e∏i∈1,Lgxi,gαβSi′,(25)=∏j∈Seg∑i∈SAjuixi,hjβvj′⋅∏i∈1,LeHℳi,gβxi⋅∏i∈1,Legxi,gαβ|Si′|,(26)=∏j∈Sehj,gβvj′∑i∈SAjuixi⋅∏i∈1,LeHℳi,gβxi⋅∏i∈1,Leg,gαβxiSi′,where the bilinearity of the mapping e ensures the correctness of the equalities.
By comparing (23) and (26), we conclude that the LHS and RHS of (20) are equal if and only if vj=vj′. In other words, if (20) holds, all the L signatures are generated with up-to-date vehicle attribute secret keys. The L signatures are all legitimate.


## 5.2. Data Dereplication

The second feature of the proposed approach is its dereplication of signatures describing the same message while preserving the traceability of the vehicles certifying the message. Suppose that messageℳ is signed by K vehicles, denoted by V1,…,VK, by using the K attribute sets S1′,…,SK′, respectively. Let S′=S1′∪⋯∪SK′. The set SAj collects the vehicles equipped with attribute j. With reference to (10), the signatures are given by(27)Δi=ℳ,Si,σi,1,σi,2,σi,3,σi,4,i=1,…,K,where, based on (6)–(9), we have(28)σi,1=∏j∈Si′hjuivjxi⋅gαxiSi′⋅Hℳixi,σi,2=guixi,σi,3=gβxi,σi,4=gxi.Here,x1,…,xK stand for the random values selected by the vehicles V1,…,VK, respectively.Let a matrixΓK,S′ specify the attributes used to sign the message ℳ:(29)ΓK,S′=b1,1b1,2⋯b1,|S′|b2,1b2,2⋯b2,|S′|⋮⋮⋮bK,1bK,2⋯bK,|S′|,where S′ is the size of S′ and bi,j∈0,1. bi,j=1 indicates that vehicle Vi signs ℳ by using attribute j. bi,j=0 indicates otherwise.The CSP defines the aggregated signature, as given by(30)Δ=ℳ,Γ,A1,A2,j∀j∈S′,A3,A4,σi,2,σi,4i∈1,K,where(31)A1=∏i∈1,Kσi,1=∏j∈S′hjvj∑i∈SAjuixi⋅∏i∈1,KgαxiSi′⋅Hℳ∑i∈1,Kxi,A2,j=∏i∈SAjσi,2=∏i∈SAjguixi=g∑i∈SAjuixi,A3=∏i∈1,Kσi,3=∏i∈1,Kgβxi=gβ∑i∈1,Kxi,A4=∏i∈1,Kσi,4=g∑i∈1,Kxi.Any data user has the ability to verify the aggregated signature, i.e.,Δ, if and only if(32)eA1,KP′=∏j∈S′eA2,j,Kj⋅eA3,Hℳ⋅eA4Si′,KP.Proof.
As defined in the proof of (11), the membership version of attribute j embedded into the signatures is vj, and the membership version in the system attribute public key, i.e., Kj, is vj′. We rewrite the LHS of (32) as(33)e∏j∈S′hjvj∑i∈SAjuixi⋅∏j∈1,KgαxiSi′⋅Hℳ∑i∈1,Kxi,gβ,(34)=e∏j∈S′hjvj∑i∈SAjuixi,gβ·∏j∈1,KegαxiSi′,gβ⋅eHℳ∑i∈1,Kxi,gβ,(35)=∏j∈S′ehj,gβvj∑i∈SAjuixi⋅∏j∈1,Keg,gαβxiSi′⋅eHℳ,gβ∑i∈1,Kxi,where the two equalities are due to the bilinearity of bilinear mapping. (33) can be rewritten as the product of three mappings in (34). The exponents of the group elements of G are moved outside the mapping e in (35).
We also rewrite the RHS of (32) as(36)∏j∈S′eg∑i∈SAjuixi,hjβvj′⋅egβ∑i∈1,Kxi,Hℳ⋅∏j∈1,KegxiSi′,gαβ,(37)=∏j∈S′ehj,gβvj′∑i∈SAjuixi⋅eHℳ,gβ∑i∈1,Kxi⋅∏j∈1,Keg,gαβxiSi′.
By comparing (35) and (37), we show that the LHS and RHS of (32) are equal if and only if vj=vj′. Then, we conclude that message ℳ is signed by K vehicles with legitimate secret keys.


## 6. Security Analysis

We consider two security properties of the system, namely, the unforgeability of signatures and the anonymity of vehicles. The unforgeability of signatures ensures that the attackers, such as malicious vehicles or RSUs, cannot forge a signature of other vehicles. The anonymity of vehicles indicates that signatures can only certify that a message is signed by a qualified vehicle with up-to-date related attributes and cannot reveal the identity of the vehicle. This ensures that any adversary cannot retrieve the identity of the signer from a signature. We first define the decisional Diffie–Hellman (DDH) assumption [32] as follows.Definition 1 (decisional Diffie–Hellman (DDH) assumption).
Given two elements in groupG, denoted by X=ga and Y=gb. It is hard to decide Z=gab or Z is a random element in G, denoted by Z=gz. Here, z is a random value in ℤp.


### 6.1. Security Model

#### 6.1.1. Unforgeability of the Signature

With reference to [21, 33, 34], we prove the unforgeability of the proposed system by constructing a game between a challenger and a forger. In this section, we define the game between a challenger and a forger as follows:(i)
Init: the forger first chooses a vehicleV∗ with attribute set S∗ as the target vehicle and attempts to forge a signature of this vehicle.(ii)
Setup: the challenger initializes the system, generates the public parameters, and sends them to the forger.(iii)
Phase 1: the forger can request the secret keys of any vehicleVi other than V∗. The forger can revoke any attribute of a vehicle Vi whose secret keys have been queried and obtain the updated attribute-related public keys.(iv)
Forgery: with the results of the queries in phase 1, the forger generates a forged signatureσ∗ of a message ℳ∗ under the targeted attribute set S∗.(v)
Guess: the challenger checks whetherσ∗ is a valid signature. If yes, the challenger outputs ‘1’ to indicate that Z=gab.We say that the proposed approach ensures the unforgeability of the signature if the forger cannot generate a valid signatureσ∗ with the unique value of V∗ embedded.


#### 6.1.2. Anonymity of the Signer

We adopt the selective indistinguishability of signatures to prove the anonymity of the vehicles with reference to [35]. We define the interaction between a challenger and an adversary as follows:(i)
Init: the adversary chooses a vehicleV∗ as its target.(ii)
Setup: the challenger sets up the system and sends the public parameters with the parameters of DDH assumption embedded into the adversary.(iii)
Phase 1: the adversary can query for the secret keys of any vehicleVi with the restriction that Vi≠V∗.(iv)
Challenge: the adversary submits a messageℳ and an attribute set S∗ to the challenger. The challenger signs ℳ under the attribute set S∗ by using the secret keys of V∗.(v)
Phase 2: the adversary continues to query for the secret keys of other vehicles different fromV∗.(vi)
Guess: the adversary outputs a guessδ∈0,1 and sends it to the challenger. Here, “1” and “0” represent Δ∗ is a valid and invalid signature of V∗.We say that the proposed approach achieves the anonymity of the signer if the adversary cannot output a guessr′=r with a nonnegligible probability.


### 6.2. Security Proof

#### 6.2.1. Unforgeability of the Signature

With reference to [34], we verify the unforgeability of the proposed authentication technique by constructing a game between a challenger and a forger, where the forger can be an adversarial vehicle or RSU which attempts to forge the signature of a predefined attribute set S∗. The challenger interacts with the forger by initializing the system and responding to queries. The details are given as follows:(i)
Setup: the challenger selects two random valuesα^,β^∈ℤp and sets α=a+α^ and β=b+β^, respectively. This is achieved by generating the system public keys KP∗ and KP′∗ as follows:(38)KP∗=gαβ=ga+α^b+β^=Z⋅Yα^⋅Xβ^⋅gα^β^,(39)KP′∗=gβ=gb+β^=Y⋅gβ^.For each attributej, the challenger initializes an empty vehicle list VLj, chooses random values sj∈ℤp, and sets hj∗=gsj. The challenger also selects a random value vj and generates the attribute-related public key Kj as follows:(40)Kj∗=hj∗βvj=gsjb+β^vj=Ysjvj⋅gsjβj^vj.(ii)
Phase 1: the forger can process three types of queries, namely, “H⋅ query,” “secret key query,” and “attribute revocation query,” as follows:H⋅ query: the challenger models H⋅ as a random oracle and maintains a list of history recordings, denoted by HL. When the forger requests the hash value of a message ℳ, the challenger first checks if ℳ has been recorded in the list HL. If ℳ has been recorded, the challenger returns the corresponding value Hℳ to the forger. Otherwise, the challenger selects a random value m∈ℤp, generates Hℳ=gm, and sets HL=HL∪ℳ,m,Hℳ.Secret key query: the forger is able to request the secret keys of a vehicle whose attribute setSi satisfies the requirement that Si≠S∗. Specifically, the forger submits a query, denoted by QV=Vi,Si, to the challenger. QV represents that vehicle Vi is equipped with an attribute set Si. The challenger selects a random value ui∈ℤp and computes KS,Vi∗=gui. For each attribute j, the challenger maintains a vehicle list by setting VLj=VLj∪eg,gui. Then, the challenger generates KS,Vi,j∗ as given by(41)KS,Vi,j∗=hjuivj⋅ga+α^=gsjuivj⋅X⋅gα^.Then, the challenger sendsKS,Vi∗,KS,Vi,j∗∀j∈Si to the forger.Attribute revocation query: the forger is able to revoke any vehicle in the vehicle listVLj. It first transmits eg,gui to the challenger. The challenger checks whether eg,gui∈VLj. If ui∉VLj, the challenger rejects this query. Otherwise, it chooses a new value vj′∈ℤp and updates the attribute-related public key Kj as follows:(42)Kj∗′=hjβvj′=gsjb+β^vj′=Ysjvj′⋅gsjβ^vj′.(iii)
Forgery: the forger first queries theH⋅ oracle and obtains Hℳ∗=gm∗. Then, the forger selects a random value x∈ℤp and outputs a forged signature Δ∗=ℳ∗,S∗,σ1∗,σ2∗,σ3∗,σ4∗ on message ℳ∗ by using the queried public keys and secret keys under the predefined attribute set S∗.(43)σ1∗=∏j∈S∗KS,Vi,jx⋅Hℳ∗x=∏j∈S∗gsjuivj⋅X⋅gα^x⋅gm∗x=guix∑j∈S∗sjvj⋅XxS∗⋅gxα^S∗⋅gm∗x,σ2∗=guix,σ3∗=gβx=gb+β^x=Yx⋅gβ^x,σ4∗=gx.(iv)
Guess: the challenger checks whetherΔ∗ is a valid signature and outputs a guess of Z in the DDH assumption. If Δ∗ is a valid signature, the challenger outputs “1” to indicate that Z=gab.We say that the forger can violate the unforgeability of the proposed algorithm if and only ifΔ∗ is a valid signature. According to (11), Δ∗ can be successfully verified if and only if the parameter Z in (38) is gab, instead of gz. This contradicts the DDH assumption, where the uncertainty of gab is proved to be hard against any polynomial adversaries [32]. Therefore, the unforgeability of the proposed approach is ensured.


#### 6.2.2. Anonymity of the Signer

We proceed to prove the anonymity of the vehicles based on the signature indistinguishability. Given a vehicleV∗ with a set of attributes S∗ and a signature Δ generated by using a subset of S∗, we prove in the following that it is hard to distinguish whether V∗ has signed the data or not. We define interactions between a challenger and an adversary as follows:(i)
Init: the adversary chooses a vehicleV∗ whose attribute set is S∗ as its target vehicle.(ii)
Setup: the challenger selects a random valueu¯∈ℤp and sets u∗=b+u¯ as the secret value for V∗. The challenger publishes the public key of V∗ as follows:(44)KS,V∗=gu∗=gb+u¯=Y⋅gu¯.As described in Section6.2.1, the challenger chooses random values α′,β′,sj′,v¯j∀j∈ℤp and generates KP∗=gα′β′, KP′∗=gβ′, and hj∗=gsj′∀j. The challenger also sets vj∗=a+v¯j for each attribute j∈S∗ by generating(45)Kj∗=hj∗β′vj∗=gsj′β′a+v¯j=Xβ′sj′⋅gβ′sjv¯j.It is noteworthy that the attribute-related public keyKj∗ still preserves the randomness and uniqueness of Kj because of the random values sj and v^j. Then, the challenger sends the public parameters, i.e., KP∗, KP′∗, and Kj∗, to the adversary.(iii)
Secret key query: the adversary can query the secret keys of vehicleVi whose attribute set is Si, and Vi≠V∗. The challenger chooses a random value ui′∈ℤp and generates KS,Vi∗=gui′. Let QV=Vi,Si represent the secret key query of Vi. For each attribute j∈Si, the challenger computes the attribute-related secret keys, as given by(46)KS,Vi,j∗=hj∗ui′vj∗⋅gα′=gui′sj′a+v¯j⋅gα′=Xui′sj′⋅gui′sj′v¯j⋅gα′.Then, the challenger transmits the secret key of the vehicleVi, i.e., KS,Vi∗,KS,Vi,j∗∀j∈Si, to the adversary.(iv)
Challenge: in this phase, the adversary chooses a messageℳ∗ and sends it to the challenger. As done in Section 6.2.1, we model H⋅ as Hℳ∗=gm∗. The challenger signs ℳ∗ by using the secret keys of vehicle V∗. It also selects a random value x′∈ℤp. The details are given as follows:(47)σ1∗=∏j∈S∗hju∗vj∗x′⋅gα′x′S∗⋅Hℳ∗x′=∏j∈S∗gsj′x′b+u¯a+v¯j⋅gα′x′S∗⋅gm∗x′=∏j∈S∗Zsj′x′⋅∏j∈S∗Xsj′x′u¯⋅∏j∈S∗Ysj′x′vj¯⋅∏j∈S∗gsj′x′u¯v¯j⋅gα′x′S∗⋅gm∗x′,σ2∗=gu∗x′=gb+u¯x=Yx′⋅gu¯x′,σ3∗=gβ′x′,σ4∗=gx′.Then, the challenger transmitsΔ∗=ℳ∗,S∗,σ1∗,σ2∗,σ3∗,σ4∗ to the adversary.(v)
Phase 2:A can repeatedly query for the secret keys of vehicles Vi≠V∗.(vi)
Guess: the adversary can output a guessδ∈0,1 and send δ to the challenger. Here, “1” and “0” indicate that Δ∗ is a legitimate signature of V∗ or not, respectively.Ifδ=1, the adversary can break the anonymity of the proposed signature algorithm, but in this case, the challenger can confirm that Z=gab, which indicates that the challenger could breach the DDH assumption. Since the security of DDH has been proved in [32], we can assert that the anonymity of the proposed system is ensured.


## 6.1. Security Model

### 6.1.1. Unforgeability of the Signature

With reference to [21, 33, 34], we prove the unforgeability of the proposed system by constructing a game between a challenger and a forger. In this section, we define the game between a challenger and a forger as follows:(i)
Init: the forger first chooses a vehicleV∗ with attribute set S∗ as the target vehicle and attempts to forge a signature of this vehicle.(ii)
Setup: the challenger initializes the system, generates the public parameters, and sends them to the forger.(iii)
Phase 1: the forger can request the secret keys of any vehicleVi other than V∗. The forger can revoke any attribute of a vehicle Vi whose secret keys have been queried and obtain the updated attribute-related public keys.(iv)
Forgery: with the results of the queries in phase 1, the forger generates a forged signatureσ∗ of a message ℳ∗ under the targeted attribute set S∗.(v)
Guess: the challenger checks whetherσ∗ is a valid signature. If yes, the challenger outputs ‘1’ to indicate that Z=gab.We say that the proposed approach ensures the unforgeability of the signature if the forger cannot generate a valid signatureσ∗ with the unique value of V∗ embedded.


### 6.1.2. Anonymity of the Signer

We adopt the selective indistinguishability of signatures to prove the anonymity of the vehicles with reference to [35]. We define the interaction between a challenger and an adversary as follows:(i)
Init: the adversary chooses a vehicleV∗ as its target.(ii)
Setup: the challenger sets up the system and sends the public parameters with the parameters of DDH assumption embedded into the adversary.(iii)
Phase 1: the adversary can query for the secret keys of any vehicleVi with the restriction that Vi≠V∗.(iv)
Challenge: the adversary submits a messageℳ and an attribute set S∗ to the challenger. The challenger signs ℳ under the attribute set S∗ by using the secret keys of V∗.(v)
Phase 2: the adversary continues to query for the secret keys of other vehicles different fromV∗.(vi)
Guess: the adversary outputs a guessδ∈0,1 and sends it to the challenger. Here, “1” and “0” represent Δ∗ is a valid and invalid signature of V∗.We say that the proposed approach achieves the anonymity of the signer if the adversary cannot output a guessr′=r with a nonnegligible probability.


## 6.1.1. Unforgeability of the Signature

With reference to [21, 33, 34], we prove the unforgeability of the proposed system by constructing a game between a challenger and a forger. In this section, we define the game between a challenger and a forger as follows:(i)
Init: the forger first chooses a vehicleV∗ with attribute set S∗ as the target vehicle and attempts to forge a signature of this vehicle.(ii)
Setup: the challenger initializes the system, generates the public parameters, and sends them to the forger.(iii)
Phase 1: the forger can request the secret keys of any vehicleVi other than V∗. The forger can revoke any attribute of a vehicle Vi whose secret keys have been queried and obtain the updated attribute-related public keys.(iv)
Forgery: with the results of the queries in phase 1, the forger generates a forged signatureσ∗ of a message ℳ∗ under the targeted attribute set S∗.(v)
Guess: the challenger checks whetherσ∗ is a valid signature. If yes, the challenger outputs ‘1’ to indicate that Z=gab.We say that the proposed approach ensures the unforgeability of the signature if the forger cannot generate a valid signatureσ∗ with the unique value of V∗ embedded.


## 6.1.2. Anonymity of the Signer

We adopt the selective indistinguishability of signatures to prove the anonymity of the vehicles with reference to [35]. We define the interaction between a challenger and an adversary as follows:(i)
Init: the adversary chooses a vehicleV∗ as its target.(ii)
Setup: the challenger sets up the system and sends the public parameters with the parameters of DDH assumption embedded into the adversary.(iii)
Phase 1: the adversary can query for the secret keys of any vehicleVi with the restriction that Vi≠V∗.(iv)
Challenge: the adversary submits a messageℳ and an attribute set S∗ to the challenger. The challenger signs ℳ under the attribute set S∗ by using the secret keys of V∗.(v)
Phase 2: the adversary continues to query for the secret keys of other vehicles different fromV∗.(vi)
Guess: the adversary outputs a guessδ∈0,1 and sends it to the challenger. Here, “1” and “0” represent Δ∗ is a valid and invalid signature of V∗.We say that the proposed approach achieves the anonymity of the signer if the adversary cannot output a guessr′=r with a nonnegligible probability.


## 6.2. Security Proof

### 6.2.1. Unforgeability of the Signature

With reference to [34], we verify the unforgeability of the proposed authentication technique by constructing a game between a challenger and a forger, where the forger can be an adversarial vehicle or RSU which attempts to forge the signature of a predefined attribute set S∗. The challenger interacts with the forger by initializing the system and responding to queries. The details are given as follows:(i)
Setup: the challenger selects two random valuesα^,β^∈ℤp and sets α=a+α^ and β=b+β^, respectively. This is achieved by generating the system public keys KP∗ and KP′∗ as follows:(38)KP∗=gαβ=ga+α^b+β^=Z⋅Yα^⋅Xβ^⋅gα^β^,(39)KP′∗=gβ=gb+β^=Y⋅gβ^.For each attributej, the challenger initializes an empty vehicle list VLj, chooses random values sj∈ℤp, and sets hj∗=gsj. The challenger also selects a random value vj and generates the attribute-related public key Kj as follows:(40)Kj∗=hj∗βvj=gsjb+β^vj=Ysjvj⋅gsjβj^vj.(ii)
Phase 1: the forger can process three types of queries, namely, “H⋅ query,” “secret key query,” and “attribute revocation query,” as follows:H⋅ query: the challenger models H⋅ as a random oracle and maintains a list of history recordings, denoted by HL. When the forger requests the hash value of a message ℳ, the challenger first checks if ℳ has been recorded in the list HL. If ℳ has been recorded, the challenger returns the corresponding value Hℳ to the forger. Otherwise, the challenger selects a random value m∈ℤp, generates Hℳ=gm, and sets HL=HL∪ℳ,m,Hℳ.Secret key query: the forger is able to request the secret keys of a vehicle whose attribute setSi satisfies the requirement that Si≠S∗. Specifically, the forger submits a query, denoted by QV=Vi,Si, to the challenger. QV represents that vehicle Vi is equipped with an attribute set Si. The challenger selects a random value ui∈ℤp and computes KS,Vi∗=gui. For each attribute j, the challenger maintains a vehicle list by setting VLj=VLj∪eg,gui. Then, the challenger generates KS,Vi,j∗ as given by(41)KS,Vi,j∗=hjuivj⋅ga+α^=gsjuivj⋅X⋅gα^.Then, the challenger sendsKS,Vi∗,KS,Vi,j∗∀j∈Si to the forger.Attribute revocation query: the forger is able to revoke any vehicle in the vehicle listVLj. It first transmits eg,gui to the challenger. The challenger checks whether eg,gui∈VLj. If ui∉VLj, the challenger rejects this query. Otherwise, it chooses a new value vj′∈ℤp and updates the attribute-related public key Kj as follows:(42)Kj∗′=hjβvj′=gsjb+β^vj′=Ysjvj′⋅gsjβ^vj′.(iii)
Forgery: the forger first queries theH⋅ oracle and obtains Hℳ∗=gm∗. Then, the forger selects a random value x∈ℤp and outputs a forged signature Δ∗=ℳ∗,S∗,σ1∗,σ2∗,σ3∗,σ4∗ on message ℳ∗ by using the queried public keys and secret keys under the predefined attribute set S∗.(43)σ1∗=∏j∈S∗KS,Vi,jx⋅Hℳ∗x=∏j∈S∗gsjuivj⋅X⋅gα^x⋅gm∗x=guix∑j∈S∗sjvj⋅XxS∗⋅gxα^S∗⋅gm∗x,σ2∗=guix,σ3∗=gβx=gb+β^x=Yx⋅gβ^x,σ4∗=gx.(iv)
Guess: the challenger checks whetherΔ∗ is a valid signature and outputs a guess of Z in the DDH assumption. If Δ∗ is a valid signature, the challenger outputs “1” to indicate that Z=gab.We say that the forger can violate the unforgeability of the proposed algorithm if and only ifΔ∗ is a valid signature. According to (11), Δ∗ can be successfully verified if and only if the parameter Z in (38) is gab, instead of gz. This contradicts the DDH assumption, where the uncertainty of gab is proved to be hard against any polynomial adversaries [32]. Therefore, the unforgeability of the proposed approach is ensured.


### 6.2.2. Anonymity of the Signer

We proceed to prove the anonymity of the vehicles based on the signature indistinguishability. Given a vehicleV∗ with a set of attributes S∗ and a signature Δ generated by using a subset of S∗, we prove in the following that it is hard to distinguish whether V∗ has signed the data or not. We define interactions between a challenger and an adversary as follows:(i)
Init: the adversary chooses a vehicleV∗ whose attribute set is S∗ as its target vehicle.(ii)
Setup: the challenger selects a random valueu¯∈ℤp and sets u∗=b+u¯ as the secret value for V∗. The challenger publishes the public key of V∗ as follows:(44)KS,V∗=gu∗=gb+u¯=Y⋅gu¯.As described in Section6.2.1, the challenger chooses random values α′,β′,sj′,v¯j∀j∈ℤp and generates KP∗=gα′β′, KP′∗=gβ′, and hj∗=gsj′∀j. The challenger also sets vj∗=a+v¯j for each attribute j∈S∗ by generating(45)Kj∗=hj∗β′vj∗=gsj′β′a+v¯j=Xβ′sj′⋅gβ′sjv¯j.It is noteworthy that the attribute-related public keyKj∗ still preserves the randomness and uniqueness of Kj because of the random values sj and v^j. Then, the challenger sends the public parameters, i.e., KP∗, KP′∗, and Kj∗, to the adversary.(iii)
Secret key query: the adversary can query the secret keys of vehicleVi whose attribute set is Si, and Vi≠V∗. The challenger chooses a random value ui′∈ℤp and generates KS,Vi∗=gui′. Let QV=Vi,Si represent the secret key query of Vi. For each attribute j∈Si, the challenger computes the attribute-related secret keys, as given by(46)KS,Vi,j∗=hj∗ui′vj∗⋅gα′=gui′sj′a+v¯j⋅gα′=Xui′sj′⋅gui′sj′v¯j⋅gα′.Then, the challenger transmits the secret key of the vehicleVi, i.e., KS,Vi∗,KS,Vi,j∗∀j∈Si, to the adversary.(iv)
Challenge: in this phase, the adversary chooses a messageℳ∗ and sends it to the challenger. As done in Section 6.2.1, we model H⋅ as Hℳ∗=gm∗. The challenger signs ℳ∗ by using the secret keys of vehicle V∗. It also selects a random value x′∈ℤp. The details are given as follows:(47)σ1∗=∏j∈S∗hju∗vj∗x′⋅gα′x′S∗⋅Hℳ∗x′=∏j∈S∗gsj′x′b+u¯a+v¯j⋅gα′x′S∗⋅gm∗x′=∏j∈S∗Zsj′x′⋅∏j∈S∗Xsj′x′u¯⋅∏j∈S∗Ysj′x′vj¯⋅∏j∈S∗gsj′x′u¯v¯j⋅gα′x′S∗⋅gm∗x′,σ2∗=gu∗x′=gb+u¯x=Yx′⋅gu¯x′,σ3∗=gβ′x′,σ4∗=gx′.Then, the challenger transmitsΔ∗=ℳ∗,S∗,σ1∗,σ2∗,σ3∗,σ4∗ to the adversary.(v)
Phase 2:A can repeatedly query for the secret keys of vehicles Vi≠V∗.(vi)
Guess: the adversary can output a guessδ∈0,1 and send δ to the challenger. Here, “1” and “0” indicate that Δ∗ is a legitimate signature of V∗ or not, respectively.Ifδ=1, the adversary can break the anonymity of the proposed signature algorithm, but in this case, the challenger can confirm that Z=gab, which indicates that the challenger could breach the DDH assumption. Since the security of DDH has been proved in [32], we can assert that the anonymity of the proposed system is ensured.


## 6.2.1. Unforgeability of the Signature

With reference to [34], we verify the unforgeability of the proposed authentication technique by constructing a game between a challenger and a forger, where the forger can be an adversarial vehicle or RSU which attempts to forge the signature of a predefined attribute set S∗. The challenger interacts with the forger by initializing the system and responding to queries. The details are given as follows:(i)
Setup: the challenger selects two random valuesα^,β^∈ℤp and sets α=a+α^ and β=b+β^, respectively. This is achieved by generating the system public keys KP∗ and KP′∗ as follows:(38)KP∗=gαβ=ga+α^b+β^=Z⋅Yα^⋅Xβ^⋅gα^β^,(39)KP′∗=gβ=gb+β^=Y⋅gβ^.For each attributej, the challenger initializes an empty vehicle list VLj, chooses random values sj∈ℤp, and sets hj∗=gsj. The challenger also selects a random value vj and generates the attribute-related public key Kj as follows:(40)Kj∗=hj∗βvj=gsjb+β^vj=Ysjvj⋅gsjβj^vj.(ii)
Phase 1: the forger can process three types of queries, namely, “H⋅ query,” “secret key query,” and “attribute revocation query,” as follows:H⋅ query: the challenger models H⋅ as a random oracle and maintains a list of history recordings, denoted by HL. When the forger requests the hash value of a message ℳ, the challenger first checks if ℳ has been recorded in the list HL. If ℳ has been recorded, the challenger returns the corresponding value Hℳ to the forger. Otherwise, the challenger selects a random value m∈ℤp, generates Hℳ=gm, and sets HL=HL∪ℳ,m,Hℳ.Secret key query: the forger is able to request the secret keys of a vehicle whose attribute setSi satisfies the requirement that Si≠S∗. Specifically, the forger submits a query, denoted by QV=Vi,Si, to the challenger. QV represents that vehicle Vi is equipped with an attribute set Si. The challenger selects a random value ui∈ℤp and computes KS,Vi∗=gui. For each attribute j, the challenger maintains a vehicle list by setting VLj=VLj∪eg,gui. Then, the challenger generates KS,Vi,j∗ as given by(41)KS,Vi,j∗=hjuivj⋅ga+α^=gsjuivj⋅X⋅gα^.Then, the challenger sendsKS,Vi∗,KS,Vi,j∗∀j∈Si to the forger.Attribute revocation query: the forger is able to revoke any vehicle in the vehicle listVLj. It first transmits eg,gui to the challenger. The challenger checks whether eg,gui∈VLj. If ui∉VLj, the challenger rejects this query. Otherwise, it chooses a new value vj′∈ℤp and updates the attribute-related public key Kj as follows:(42)Kj∗′=hjβvj′=gsjb+β^vj′=Ysjvj′⋅gsjβ^vj′.(iii)
Forgery: the forger first queries theH⋅ oracle and obtains Hℳ∗=gm∗. Then, the forger selects a random value x∈ℤp and outputs a forged signature Δ∗=ℳ∗,S∗,σ1∗,σ2∗,σ3∗,σ4∗ on message ℳ∗ by using the queried public keys and secret keys under the predefined attribute set S∗.(43)σ1∗=∏j∈S∗KS,Vi,jx⋅Hℳ∗x=∏j∈S∗gsjuivj⋅X⋅gα^x⋅gm∗x=guix∑j∈S∗sjvj⋅XxS∗⋅gxα^S∗⋅gm∗x,σ2∗=guix,σ3∗=gβx=gb+β^x=Yx⋅gβ^x,σ4∗=gx.(iv)
Guess: the challenger checks whetherΔ∗ is a valid signature and outputs a guess of Z in the DDH assumption. If Δ∗ is a valid signature, the challenger outputs “1” to indicate that Z=gab.We say that the forger can violate the unforgeability of the proposed algorithm if and only ifΔ∗ is a valid signature. According to (11), Δ∗ can be successfully verified if and only if the parameter Z in (38) is gab, instead of gz. This contradicts the DDH assumption, where the uncertainty of gab is proved to be hard against any polynomial adversaries [32]. Therefore, the unforgeability of the proposed approach is ensured.


## 6.2.2. Anonymity of the Signer

We proceed to prove the anonymity of the vehicles based on the signature indistinguishability. Given a vehicleV∗ with a set of attributes S∗ and a signature Δ generated by using a subset of S∗, we prove in the following that it is hard to distinguish whether V∗ has signed the data or not. We define interactions between a challenger and an adversary as follows:(i)
Init: the adversary chooses a vehicleV∗ whose attribute set is S∗ as its target vehicle.(ii)
Setup: the challenger selects a random valueu¯∈ℤp and sets u∗=b+u¯ as the secret value for V∗. The challenger publishes the public key of V∗ as follows:(44)KS,V∗=gu∗=gb+u¯=Y⋅gu¯.As described in Section6.2.1, the challenger chooses random values α′,β′,sj′,v¯j∀j∈ℤp and generates KP∗=gα′β′, KP′∗=gβ′, and hj∗=gsj′∀j. The challenger also sets vj∗=a+v¯j for each attribute j∈S∗ by generating(45)Kj∗=hj∗β′vj∗=gsj′β′a+v¯j=Xβ′sj′⋅gβ′sjv¯j.It is noteworthy that the attribute-related public keyKj∗ still preserves the randomness and uniqueness of Kj because of the random values sj and v^j. Then, the challenger sends the public parameters, i.e., KP∗, KP′∗, and Kj∗, to the adversary.(iii)
Secret key query: the adversary can query the secret keys of vehicleVi whose attribute set is Si, and Vi≠V∗. The challenger chooses a random value ui′∈ℤp and generates KS,Vi∗=gui′. Let QV=Vi,Si represent the secret key query of Vi. For each attribute j∈Si, the challenger computes the attribute-related secret keys, as given by(46)KS,Vi,j∗=hj∗ui′vj∗⋅gα′=gui′sj′a+v¯j⋅gα′=Xui′sj′⋅gui′sj′v¯j⋅gα′.Then, the challenger transmits the secret key of the vehicleVi, i.e., KS,Vi∗,KS,Vi,j∗∀j∈Si, to the adversary.(iv)
Challenge: in this phase, the adversary chooses a messageℳ∗ and sends it to the challenger. As done in Section 6.2.1, we model H⋅ as Hℳ∗=gm∗. The challenger signs ℳ∗ by using the secret keys of vehicle V∗. It also selects a random value x′∈ℤp. The details are given as follows:(47)σ1∗=∏j∈S∗hju∗vj∗x′⋅gα′x′S∗⋅Hℳ∗x′=∏j∈S∗gsj′x′b+u¯a+v¯j⋅gα′x′S∗⋅gm∗x′=∏j∈S∗Zsj′x′⋅∏j∈S∗Xsj′x′u¯⋅∏j∈S∗Ysj′x′vj¯⋅∏j∈S∗gsj′x′u¯v¯j⋅gα′x′S∗⋅gm∗x′,σ2∗=gu∗x′=gb+u¯x=Yx′⋅gu¯x′,σ3∗=gβ′x′,σ4∗=gx′.Then, the challenger transmitsΔ∗=ℳ∗,S∗,σ1∗,σ2∗,σ3∗,σ4∗ to the adversary.(v)
Phase 2:A can repeatedly query for the secret keys of vehicles Vi≠V∗.(vi)
Guess: the adversary can output a guessδ∈0,1 and send δ to the challenger. Here, “1” and “0” indicate that Δ∗ is a legitimate signature of V∗ or not, respectively.Ifδ=1, the adversary can break the anonymity of the proposed signature algorithm, but in this case, the challenger can confirm that Z=gab, which indicates that the challenger could breach the DDH assumption. Since the security of DDH has been proved in [32], we can assert that the anonymity of the proposed system is ensured.


## 7. Numerical and Experimental Study

In this section, we implement the proposed attribute-based anonymous authentication approach and conduct a comparison study of efficiency between the proposed scheme and three state-of-the-art ABS techniques, namely, Yu et al.’s algorithm [16], Cui et al.’s algorithm [17], and Xiong et al.’s algorithm [36]. These techniques are based on ABS techniques and can be applied to VANETs to support anonymous authentication. We first compare the schemes from the functionalities and security aspects. The details are provided in Table 2.Table 2
Functional and computational comparisons of the proposed approach with existing ABS techniques, i.e., Yu et al.’s algorithm [16], Cui et al.’s algorithm [17], and Xiong et al.’s algorithm [36].
SchemePolicyTraceabilityRevocabilityComputational costYu et al.’s algorithm [16]t,nNoNoSΛ+2PG+3SΛEG+2SΛEGTKCui et al.’s algorithm [17]t,nYesYes4PG+SΛEG+5MGKXiong et al.’s algorithm [36]LSSSNoYes3PG+SΛEG+EGTKProposed without batchn,nYesYes3PG+2SΛ+2MG+MGTKProposed batch verificationS+K+1PG+SA+2K−3MG+S+K−1MGT1In this example, we use the number of operations to represent the encryption overhead of IoT devices. PG denotes the bilinear mapping operation e. EG and EGT represent the exponential operation in group EG and EGT, respectively, and MG and MGT stand for the multiplicative operation in EG and EGT. 2S denotes the size of the whole set of attributes in the system. SΛ is the number of attributes involved in an access structure Λ (an access tree or matrix), and nu stands for the number of users in the ABE systems. SA denotes the average number of vehicles equipped with an attribute.Our experimental testbed runs Charm-Crypto in a Mac laptop to provide the framework of our cryptosystem. Charm-Crypto supports a range of cryptographic settings, including pairing, exponential, and multiplicative operations in bilinear elliptic curve groups. We choose “SS512” as the target elliptic curve to simulate the state-of-the-art algorithms [16, 17, 36] and the proposed approach. The Mac laptop runs 10.14.5 operating system and has an Intel Core i5 with an operating frequency of 2.3 GHz and a memory of 8G bytes.


### 7.1. Efficiency of Batch Verification

We start by comparing the proposed approach with the state-of-the-art techniques in terms of computational overhead at the signature verification phase. We assume that there areK signatures to be verified and use the verification time (or delay) to represent the computational cost of the schemes. S denotes the number of attributes included in the K signatures. Three variations of the proposed approach, referred to as “proposed algorithm without batch,” “proposed batch verification when S=10,” and “proposed batch verification when S=20,” are plotted in Figure 2. We set SI=5; in other words, each message is signed under five attributes. Every result is the average of 100 independent experimental tests in the figure.Figure 2
Computational overhead comparison.In Figure2, we can see that the verification time of all the schemes increases with the number of messages, and the proposed approaches take shorter verification time than the existing techniques. We also see that “proposed algorithm without batch” intersects “proposed batch verification S=10” and “proposed batch verification S=20” when the number of signatures is 10 and 20, respectively. With the increase of K, the two variations of the proposed batch verification algorithm can outperform the algorithm without batch verification when the number of data is greater than the number of attributes. Moreover, the batch verification algorithms can perform better when the number of attributes is 10, i.e., S=10, than they do when S=20.


### 7.2. Efficiency of Data Dereplication

We compare the communication overhead of the proposed dereplication with that of the existing works in Figure3(a). We use the length of signatures to represent the communication cost. Assume that there are K signature/replicas describing the same message ℳ. We evaluate the communication overhead of the K signatures by using the bit-length of signatures. Table 3 shows the comparison of the proposed approach and the existing algorithms, i.e., Yu et al.’s scheme [16], Cui et al.’s scheme [17], and Xiong et al.’s scheme [36]. LG is the length of an element in the group G. Lℳ denotes the length of a message ℳ. LSΛ is the size of an access structure Λ (an attribute set or matrix). SΛ is the average size of attributes included in an ABS signature scheme. As shown in Figure 3(a), the proposed dereplication algorithms can show their advantage when the number of replicas is larger than the number of attributes included in the K signatures. Specifically, “proposed dereplication S=10” and “proposed dereplication S=20” can outperform the “proposed without dereplication” when the number of signatures is around and above 10 and 20, respectively. The proposed approach requires substantially lower communication cost than Yu et al.’s scheme [16] and Cui et al.’s scheme [17].Figure 3
Performance comparison between the proposed approach and the state-of-the-art Yu et al.’s algorithm [16], Cui et al.’s algorithm [17], and Xiong et al.’s algorithm [36]. (a) Communication overhead comparison. (b) Storage overhead comparison.
(a)(b)Table 3
Communication comparison of the proposed dereplication approach and the state-of-the-art techniques, i.e., Yu et al.’s algorithm [16], Cui et al.’s algorithm [17], and Xiong et al.’s algorithm [36].
SchemesCommunication costYu et al.’s scheme [16]Lℳ+LSΛ+3SILGKCui et al.’s scheme [17]Lℳ+LSΛ+4LG+3LGTKXiong et al.’s scheme [36]Lℳ+LSΛ+3LGKProposed without dereplicationLℳ+LSΛ+4LGKProposed data dereplicationLℳ+LSΛ+S+2K+3LGBesides the communication overhead, we also compare the storage overhead of vehicles in different schemes. We assume that there are up to 50 replicas to be stored. The schemes without dereplication, i.e., Yu et al.’s scheme [16], Cui et al.’s scheme [17], and Xiong et al.’s scheme [36], are expected to store the replicas separately to record the responsible vehicle. The proposed scheme can aggregate the replicas and preserve the traceability of the signers. The aggregated signature is given by Δ=ℳ,Γ,A1,A2,j∀j∈S′,A3,A4,σi,2,σi,4i∈1,K; see (30). In our design, σi,2,σi,4i∈1,K is preserved in Δ to trace the signers of the replicas and can be stored at a central server only. In this case, the vehicles can store Δ′=ℳ,Γ,A1,A2,j∀j∈S′,A3,A4 to reduce storage overhead. We also evaluate the storage overhead of Δ′, called “proposed without traceability,” as shown in Figure 3(b). In the figure, we show that the proposed scheme can compress the storage space of replicas and largely reduce the storage overhead of vehicles.


### 7.3. Experiment Analysis

We evaluate the network performance of the proposed scheme by using SUMO and NS3 [4]. OpenStreetMap can help us get traffic data in a certain area and import the data to SUMO, which is a tool for building network simulators. As a C++ library, SUMO can load the road conditions from OpenStreetMap and simulate traffic flows. NS3 is a network simulator and can be combined with SUMO to simulate various communication protocols in different scenarios. We adopt IEEE 802.11p as the transmission protocol.We generate a realistic map near the University of Technology Sydney (UTS) to simulate the performance of the proposed scheme. Figures4 and 5 show the map of UTS in the real scenario and in SUMO, respectively. We consider average message transmission delay (ATD) to evaluate the performance of our scheme in VANET. The ATD can be defined as the average time cost to transmit messages from a sender to a receiver, denoted by(48)ATD=1N∑i=1N1Ni∑j=1NiTr,j−Ts,j.Figure 4
The map of the University of Technology Sydney.Figure 5
The map of the University of Technology Sydney in SUMO.Here,N is the total number of vehicles in the experiment. Ni denotes the number of messages received by the i-th vehicle Vi. Tr,j and Ts,j represent the receiving time and the sending time of the j-th message of Vi, respectively.Figure6 illustrates the relationship between the average transmission delay and the number of vehicles in the considered area. We can observe that the ATD grows linearly with the number of vehicles in the map. We also analyze how the size of packet influences the transmission delay. We take “packet size = 512 bytes” and “packet size = 1024 bytes” into consideration. From Figure 6, we can conclude that the ATD increases with the size of packet.Figure 6
The relationship between the transmission delay and the number of vehicles.


## 7.1. Efficiency of Batch Verification

We start by comparing the proposed approach with the state-of-the-art techniques in terms of computational overhead at the signature verification phase. We assume that there areK signatures to be verified and use the verification time (or delay) to represent the computational cost of the schemes. S denotes the number of attributes included in the K signatures. Three variations of the proposed approach, referred to as “proposed algorithm without batch,” “proposed batch verification when S=10,” and “proposed batch verification when S=20,” are plotted in Figure 2. We set SI=5; in other words, each message is signed under five attributes. Every result is the average of 100 independent experimental tests in the figure.Figure 2
Computational overhead comparison.In Figure2, we can see that the verification time of all the schemes increases with the number of messages, and the proposed approaches take shorter verification time than the existing techniques. We also see that “proposed algorithm without batch” intersects “proposed batch verification S=10” and “proposed batch verification S=20” when the number of signatures is 10 and 20, respectively. With the increase of K, the two variations of the proposed batch verification algorithm can outperform the algorithm without batch verification when the number of data is greater than the number of attributes. Moreover, the batch verification algorithms can perform better when the number of attributes is 10, i.e., S=10, than they do when S=20.


## 7.2. Efficiency of Data Dereplication

We compare the communication overhead of the proposed dereplication with that of the existing works in Figure3(a). We use the length of signatures to represent the communication cost. Assume that there are K signature/replicas describing the same message ℳ. We evaluate the communication overhead of the K signatures by using the bit-length of signatures. Table 3 shows the comparison of the proposed approach and the existing algorithms, i.e., Yu et al.’s scheme [16], Cui et al.’s scheme [17], and Xiong et al.’s scheme [36]. LG is the length of an element in the group G. Lℳ denotes the length of a message ℳ. LSΛ is the size of an access structure Λ (an attribute set or matrix). SΛ is the average size of attributes included in an ABS signature scheme. As shown in Figure 3(a), the proposed dereplication algorithms can show their advantage when the number of replicas is larger than the number of attributes included in the K signatures. Specifically, “proposed dereplication S=10” and “proposed dereplication S=20” can outperform the “proposed without dereplication” when the number of signatures is around and above 10 and 20, respectively. The proposed approach requires substantially lower communication cost than Yu et al.’s scheme [16] and Cui et al.’s scheme [17].Figure 3
Performance comparison between the proposed approach and the state-of-the-art Yu et al.’s algorithm [16], Cui et al.’s algorithm [17], and Xiong et al.’s algorithm [36]. (a) Communication overhead comparison. (b) Storage overhead comparison.
(a)(b)Table 3
Communication comparison of the proposed dereplication approach and the state-of-the-art techniques, i.e., Yu et al.’s algorithm [16], Cui et al.’s algorithm [17], and Xiong et al.’s algorithm [36].
SchemesCommunication costYu et al.’s scheme [16]Lℳ+LSΛ+3SILGKCui et al.’s scheme [17]Lℳ+LSΛ+4LG+3LGTKXiong et al.’s scheme [36]Lℳ+LSΛ+3LGKProposed without dereplicationLℳ+LSΛ+4LGKProposed data dereplicationLℳ+LSΛ+S+2K+3LGBesides the communication overhead, we also compare the storage overhead of vehicles in different schemes. We assume that there are up to 50 replicas to be stored. The schemes without dereplication, i.e., Yu et al.’s scheme [16], Cui et al.’s scheme [17], and Xiong et al.’s scheme [36], are expected to store the replicas separately to record the responsible vehicle. The proposed scheme can aggregate the replicas and preserve the traceability of the signers. The aggregated signature is given by Δ=ℳ,Γ,A1,A2,j∀j∈S′,A3,A4,σi,2,σi,4i∈1,K; see (30). In our design, σi,2,σi,4i∈1,K is preserved in Δ to trace the signers of the replicas and can be stored at a central server only. In this case, the vehicles can store Δ′=ℳ,Γ,A1,A2,j∀j∈S′,A3,A4 to reduce storage overhead. We also evaluate the storage overhead of Δ′, called “proposed without traceability,” as shown in Figure 3(b). In the figure, we show that the proposed scheme can compress the storage space of replicas and largely reduce the storage overhead of vehicles.


## 7.3. Experiment Analysis

We evaluate the network performance of the proposed scheme by using SUMO and NS3 [4]. OpenStreetMap can help us get traffic data in a certain area and import the data to SUMO, which is a tool for building network simulators. As a C++ library, SUMO can load the road conditions from OpenStreetMap and simulate traffic flows. NS3 is a network simulator and can be combined with SUMO to simulate various communication protocols in different scenarios. We adopt IEEE 802.11p as the transmission protocol.We generate a realistic map near the University of Technology Sydney (UTS) to simulate the performance of the proposed scheme. Figures4 and 5 show the map of UTS in the real scenario and in SUMO, respectively. We consider average message transmission delay (ATD) to evaluate the performance of our scheme in VANET. The ATD can be defined as the average time cost to transmit messages from a sender to a receiver, denoted by(48)ATD=1N∑i=1N1Ni∑j=1NiTr,j−Ts,j.Figure 4
The map of the University of Technology Sydney.Figure 5
The map of the University of Technology Sydney in SUMO.Here,N is the total number of vehicles in the experiment. Ni denotes the number of messages received by the i-th vehicle Vi. Tr,j and Ts,j represent the receiving time and the sending time of the j-th message of Vi, respectively.Figure6 illustrates the relationship between the average transmission delay and the number of vehicles in the considered area. We can observe that the ATD grows linearly with the number of vehicles in the map. We also analyze how the size of packet influences the transmission delay. We take “packet size = 512 bytes” and “packet size = 1024 bytes” into consideration. From Figure 6, we can conclude that the ATD increases with the size of packet.Figure 6
The relationship between the transmission delay and the number of vehicles.


## 8. Conclusion

This paper presents a new approach for secure, efficient, and anonymous data authentication in VANET. The approach defines each vehicle by using a set of attributes and enables the vehicle to sign messages under part of its attributes. The malicious vehicles forging data can be identified and revoked. The verification of multiple messages can be conducted together in a batch, hence reducing the delay of verifying massive data in large-scale VANETs. The replicas of the same data can be dereplicated to reduce the storage requirement for data, e.g., at the CSP. The approach is experimentally verified to outperform existing techniques in terms of verification delay and storage requirement.



---

*Source: 6638453-2021-02-23.xml*