A Distributed Anonymous Reputation System for V2X Communication

1  Introduction

The privacy of one’s location is a major concern, especially for drivers. However, real-time local information, such as traffic and road conditions, is essential for efficient urban management. Therefore, it is critical to collect and share such local information while respecting privacy. Consider a scenario in which vehicles collect local information and exchange it via V2X communication, such as V2V and V2I. To deter message tampering and impersonation, messages from each vehicle should be authenticated. Nevertheless, since location can often be inferred from both the reported content and authentication metadata, linking authenticated messages to persistent vehicle identities can violate privacy.

V2X communication faces significant challenges due to its open and decentralized nature. When malicious vehicles disseminate falsified data, they undermine both the reliability of information exchange and the safety of ordinary drivers. Consequently, trust evaluation and management in V2X communication has attracted significant attention in recent years.

1.1 Previous Works

Vehicle ad-hoc network (VANET) reputation systems have been studied in the literature, but most approaches do not consider the privacy aspect of vehicles (e.g., [1–3]). These studies mainly focus on frameworks for evaluating vehicle behavior and message forwarding to detect misbehavior. In contrast, in the context of crowdsensing, a privacy-aware reputation system called ARTSense was proposed in [4]. In crowdsensing, numerous mobile users voluntarily collect sensing data, such as location and environmental information, which are submitted to and analyzed by a centralized server. Therefore, user privacy must be taken into account. To achieve the anonymity of users, ARTSense separates the data reporting process from the reputation updating process. No user identity information is revealed in individual sensing reports. Furthermore, the server cannot link multiple reports to the same participant due to the use of blind IDs. However, this work is not designed for V2X communication, which is characterized by high mobility and a dynamic network topology.

In 2016, Jaimes et al. [5] proposed a centralized anonymous reputation system (ARS) for V2X communication, including VANETs, in which vehicles interact with roadside units (RSUs) to submit feedback to a centralized reputation server (RepS) and to retrieve their current reputation levels under pseudonyms. The server updates the reputation level of each vehicle by associating anonymous identities with real identities. ARS introduced the notion of security states, which can help identify region-specific risks and support the evaluation of neighboring vehicles’ reputation scores. The reputation level of a vehicle is the result of the aggregation of the reputation levels by the characteristics of generation and forwarding of messages. However, the centralized server causes the bottleneck in scalability, single point of failure, and privacy risk that the server can reveal the location history of vehicle.

In 2018, Lu et al. [6] proposed a blockchain-based anonymous reputation system (BARS) to establish a privacy-preserving trust model for V2X communication. In this system, a certificate authority (CA) issues certificates to vehicles and manages revocation. All activities of CA are recorded on the blockchain for transparency. The certificate includes no vehicle ID and is thus anonymous. On the other hand, a law enforcement authority (LEA) is responsible for managing the correspondence between public keys and real identities. In case of disputes, the LEA can trace a vehicle from a public key used for authentication. Furthermore, BARS incorporates a reputation system in which the LEA monitors and evaluates each vehicle’s behavior, and updates its reputation score. The reputation is certified by the certificate, and updated by the CA with the assistance of the LEA. The reputation system is anonymous due to the hidden vehicle’s ID. However, the two authorities CA and LEA cooperatively update the certificate of each vehicle. Thus, when lots of vehicles communicate messages, the centralized update process can become a bottleneck, i.e., BARS also have a scalability disadvantage. In addition, if the two authorities collude, they may reveal the location history of a vehicle.

1.2 Our Contributions

In this paper, toward a distributed privacy-preserving trust management in V2X communication, we propose an anonymous reputation system for V2X communication, which is derived from an anonymous reputation system for crowdsensing [7]. In the system for crowdsensing, the server updates the reputation certificate of each user s.t. the user’s ID and even the reputation value are hidden. Using a zero-knowledge proof (ZKP), the user can prove the reputation level (an integer range that contains the reputation value). In our proposed system for V2X communication, the server is distributed across CA and RSUs (roadside units). Each vehicle shows the reputation level to the nearest RSU at the beginning of each time interval, similarly to the underlying system [7], and registers a short-time public key. In the interval, the messages from the vehicle are authenticated under the public key and are scored. At the end of the interval, the nearest RSU updates the certificate anonymously.

To situate our contributions within existing approaches, Table 1 summarizes the difference in the architecture, anonymity, and costs across ARS, BARS, and our proposed system. This distributed update in our system avoids the centralized certificate-update process in BARS [6], where two central authorities must update the certificates of many vehicles, potentially causing communication and processing delays. In our system, each update is performed locally at the nearest RSU once per interval, requiring only a few kilobytes of communication and a zero-knowledge proof that is almost fully precomputed on the vehicle side, with the RSU-side processing estimated to take about 40 ms based on timing measurements of the underlying cryptographic operations. This distributed mechanism removes the centralized bottleneck of BARS and mitigates the privacy risk arising from possible authority collusion. Per-message authentication during the interval uses the same pseudonym-certificate mechanism as in existing RSU-assisted V2X systems, and ZKPs are required only once per interval; detailed efficiency considerations are discussed in Section 6. From these efficiency considerations, we consider that the practicality of the proposed system is demonstrated without requiring mobility-level simulations. Network-level performance evaluations under specific traffic and mobility models (e.g., NS-3 or SUMO) are important as complementary research directions that depend on application scenarios. We therefore leave such system-level evaluations as future work.

In our system, a malicious vehicle cannot be traced by authorities such as the LEA. However, the vehicle can be scored low in the anonymous reputation system, and the messages can be flagged as untrustworthy. The secret key of each RSU is unique, and thus a compromised RSU must also be revoked. The revocation is done using a complete subtree (CS) method [8] to compute revocation information for RSUs. In this paper, we do not address blockchain-based transparency, and the detailed reputation evaluation algorithm for scoring is also beyond the scope of our study. While both components are essential for constructing a complete and practical V2X trust management system, they are conceptually separable from the fundamental challenge we focus on in this research line. Since our main contribution is the distributed certificate-update mechanism with zero-knowledge-proof-based privacy protection, the practical evaluation presented in Section 6 concentrates on this fully specified component. The integration of more sophisticated reputation evaluation algorithms and scalable blockchain-based transparency mechanisms, which may require additional cryptographic and system-level design considerations, is left as future work.

1.3 Difference from the Conference Version [9]

A preliminary version of this paper was presented in ICCE 2024 [9], where security requirements are informally defined, and only the proof sketches for the security requirements are shown. In this paper, we formally show game-based security definitions, and prove the security based on the definitions. Furthermore, we extend the original system [9] by adding a revocation function for malicious RSUs, and we newly provide a detailed efficiency evaluation of the system.

1.4 Related Works

The recent works related to BARS and our proposed system are as follows.

In [10], Ahmed et al. propose a privacy-enhancing V2X trust management system that combines pseudo-identity–based anonymous authentication with blockchain-based revocation, similar to BARS. Compared with BARS, it integrates a more sophisticated context-aware trust (reputation) computation and improves verification efficiency through signature aggregation. However, the scheme relies on a fully trusted TA (Trusted Authority) that centrally generates and manages each vehicle’s pseudo-identities and secret keys, and thus TA can compromise user’s privacy by de-anonymization, as in BARS.

In [11], Feng et al. propose a blockchain-based privacy-preserving authentication system for V2X environments. The system adopts a structure similar to BARS by introducing two ID management entities and realizing vehicle anonymity through pseudonym-based public-key certificates. In addition, the system employs an asynchronous accumulator that is a hash-tree-based mechanism, to accelerate revocation verification. However, this approach focuses solely on authentication and revocation, and thus does not incorporate a reputation-based trust management mechanism. Moreover, if the two management entities collude, the linkage of pseudonyms becomes possible, which results in the leakage of vehicle behavioral information.

In [12], Feng et al. proposed a privacy-preserving authentication scheme for V2X communication. In the system, a certification authority issues certificates for pseudonymous identities and enables anonymous authentication, while leveraging polynomial commitments to achieve constant-cost revocation checking. However, the system also focuses solely on authentication and revocation, and does not provide a reputation-based trust management. Moreover, the certificate update process is centrally managed, allowing the authority to link successive certificates, and thus the privacy of vehicles is compromised.

In [13], Hou et al. introduce a double-layer blockchain architecture, consisting of an event chain and a reputation chain, and propose a sophisticated reputation-based trust management system for V2X communication, which resists against on–off attacks and collusive attacks. However, the system does not address privacy protection. It assumes a fully trusted TA that issues public-key certificates, and thus the TA can easily deanonymize any vehicle even when pseudonyms are used. Moreover, since both reputation information and event reports are persistently stored on the blockchain, linkability among observations and historical behavior may still weaken privacy, even under pseudonym-based identifiers.

In [14], Fernandes et al. propose a V2X trust management system based on a consortium blockchain that employs a PoA (Proof of Authority) consensus mechanism, where RSUs collaboratively update reputation scores to improve efficiency. However, the system relies entirely on a centralized CA for certificate issuance and management, and it does not support certificate updates. As a result, it cannot also prevent deanonymization by the CA, and the reputation values tied to static IDs allow vehicle behavior to be tracked through linkable evaluation records.

2  Preliminaries

2.1 Bilinear Groups

We adopt the following bilinear groups:

1.    G1, G2 and GT are multiplicative groups with same prime order p, where g∈G1 and h∈G2 are generators.

2.    e:G1×G2→GT is a bilinear map s.t.

•   for all u∈G1 and v∈G2, and a,b∈Z,e(ua,vb)=e(u,v)ab holds.

•   e(g,h) is a generator of GT.

2.2 Assumptions

For the security of the proposed system, we use the q-SDH assumption [15].

Definition 1 (q-SDH assumption): For all PPT algorithm 𝒜, the probability

Pr[𝒜(u,v,va,…,v(aq))=(b,v1/(a+b))∧b∈Zp]

is negligible, where u←RG1, v←RG2 and a←RZp.

2.3 BB Signatures

We employ the scheme in [15] where a message and the signature can be proven by the zero-knowledge proofs.

Here are the descriptions of the algorithm.

•   BB-Setup: Select bilinear group parameters (p,G1,G2, GT, e,g,h).

•   BB-KeyGen: Compute w=hγ for γ←RZp∗, where the public key is pk=w and the secret key is sk=γ.

•   BB-Sign: On input of a message m∈Zp, compute A=g1/(m+γ).

•   BB-Verify: On inputs of a message m and a signature A, check if e(A,whm)=e(g,h).

In [15], the security is proved under the q-SDH assumption.

2.4 BBS+ Signatures

We also use an extension of BB signature, BBS+ signature, which is informally introduced in [16], to sign a vector of numerous messages. The concrete structure is displayed in [17,18].

•   BBS+-Setup: Select bilinear group parameters (p,G1,G2,GT,e,g,h). Then, select g1,…,gL+1←RG1.

•   BBS+-KeyGen: Compute w=hγ for γ←RZp∗, where the public key is pk=w and the secret key is sk=γ.

•   BBS+-Sign: On input of a vector ℳ of L messages (m1,…,mL)∈ZpL, choose η,ζ←RZp, and compute A=(gg1ζg2m1…gL+1mL)1/(η+γ). The signature is σ=(A,η,ζ).

•   BBS+-Verify: For the signature σ=(A,η,ζ)and(m1,…,mL),checkife(A,whη)=e(gg1ζg2m1⋯ gL+1mL,h).

The security is proved in [18] under the q-SDH assumption.

2.5 Signature-Based Proofs of Knowledges (SPKs)

For Non-Interactive Zero-Knowledge Protocol (NIZK) proofs on representations, we adopt signature-based proofs of knowledge (SPKs), which are converted from zero-knowledge proofs of knowledge (PoKs) or Sigma protocols [19]. Concretely, we utilize the SPK to prove a representation of C∈G1 to g1,g2,…∈G1 (or G2, or GT) which is denoted as SPK{(x1,x2,…):C=g1x1g2x2⋯}(M) where x1,x2,…∈Zp. This SPK means a signature on message M by a signer with the secrets x1,x2,… s.t. the relation holds.

2.6 Complete Subtree (CS) Method

We adopt Complete Subtree (CS) method [8] to achieve efficient user revocation in group signatures [20–22]. First, a group manager (GM) generates a binary tree with the number of leaves equal to the total number of users, N. Each node is assigned a node ID, and each user is assigned to a leaf node. An example is shown in Fig. 1, where each user is assigned to nodes u7 to u14. The GM issues and publishes a membership certificate A for each node on the path from the root node to the leaf nodes u0,u1,…,ul. Additionally, whenever a user is revoked, the GM issues and publishes a revocation certificate R for each cover node that is a root of a subtree whose subtrees consist only of leaf nodes of non-revoked users. A non-revoked user can prove that she has not been revoked by demonstrating the existence of both A and R generated from the same node. In the case shown in Fig. 1, if the user of node 10 is revoked, the GM selects cover nodes (u2, u3, u9) using the CS method and generates corresponding certificates (R2,R3,R9). The revocation list thus becomes (R2,R3,R9). For N total users and r revoked users, the size of the revocation list is O(r⋅log⁡(N/r)), enabling efficient revocation with O(1) time complexity for signature generation and verification in group signatures.

Figure 1: Example of CS method

3  Model of Proposed System

3.1 Syntax

The proposed anonymous reputation system consists of the following algorithm and protocols. The participants of this system are the certificate authority (CA), the roadside units (RSUs), and vehicles. In this system, messages sent from each anonymous vehicle are linkable via a pseudonym (i.e., short-time public key) during each time interval, and messages across intervals are unlinkable. At the first message in the interval, the vehicle shows the vehicle’s reputation level to the nearest RSU, and the pseudonym at the interval is registered. The vehicle must ensure that the nearest RSU is not being revoked during this authentication. Each message is rated by the nearest RSU, and the scores at each interval are accumulated by RSUs. At the final message in the interval, the reputation of the vehicle is updated by the nearest RSU.

The anonymity of this system ensures that an adversary cannot obtain information about each vehicle other than the evaluation level and linkability (determining whether any two authenticated vehicles are the same) at each interval. This requirement means that the adversary cannot know the ID of the RSU with which each vehicle last communicated in the previous interval. Therefore, while hiding the public key of the last RSU that it communicated with, the vehicle performs a zero-knowledge proof of the certificate of the evaluation value by the RSU.

•   Setup: CA takes a security parameter λ as input. This algorithm generates a key pair of public key spk and secret key ssk of the CA and initializes set SSet that keeps tags of used reputation certificates. This algorithm also prepares RSUs in a CS tree structure, generates a secret key rski of each RSU i in the tree structure, and distributes the secret key to RSU i. SSet is shared with all RSUs.

•   Register: This is an interactive protocol between a vehicle and the CA. The common input is spk, and the input of the CA is ssk. The vehicle is issued a reputation certificate cert0 for initial reputation rep0=0.

•   RevokeRSU: This algorithm allows the CA to revoke an RSU. Given the ID of a revoked RSU, it outputs a revocation list RLT at the current revocation interval T.

•   Show: This protocol is called in the first communication at each time interval. This is an interactive protocol between a vehicle and the nearest RSU, where the vehicle shows that its reputation value is included in an integer range that is called reputation level. The vehicle also checks that the RSU is not being revoked. The common input are spk and reputation level ℓ. The vehicle’s input is certt−1 for its current reputation value rept−1. The RSU’s input is SSet. The common outputs are a pseudonym pseuτ of the vehicle at the current interval τ and the certificate pcertτ, the output of the vehicle is the secret key pskτ of pseuτ, and the outputs of the RSU are a commitment Cm,t′ to messages to be certified for next Update, and the updated SSet to which the tag St−1 of certt−1 is added. The pseudonym pseuτ, the reputation level ℓ, and Cm,t′ are shared with all RSUs.

•   Authentication: This is an interactive protocol between a vehicle and the nearest RSU. The common input is spk, and the inputs of the vehicle are message M, reputation level ℓ, pseuτ, pcertτ, and pskτ. The outputs of the RSU is the validity bit 1 (accepted) or 0 (rejected), and (M,pseuτ).

Each message M is rated by the nearest RSU based on some evaluation method (e.g., ARTSense [4]) that uses the reputation level together with other information. A negative rating is possible by using a negative integer. For the rated score s, (M,pseuτ,s) is shared with all RSUs.

•   Update: This protocol is called in the final communication at each time interval, where the total score s~τ for each pseuτ at the current interval τ, i.e., s~τ=∑isi for all (Mi,pseuτ,si), is prepared. This is an interactive protocol between a vehicle and the nearest RSU. The common input is spk, and the input of the vehicle is certt−1 for the previous reputation rept−1, and the inputs of the RSU i are pseuτ,Cm,t′,s~τ,rski. The output of the vehicle is a new reputation certificate certt for the updated reputation rept=rept−1+s~τ.

3.2 Security Requirements

As in [7], we consider the following requirements:

•   Reputation Unforgeability: Any vehicle cannot prove inappropriate reputation level, i.e., for the correct reputation rep~t−1 which added from s~τ1,…,s~τk, where s~τi is the total score for each pseuτi assigned to the vehicle at the interval τi, the vehicle cannot prove any inappropriate level ℓ s.t. rep~t−1 is not included in the integer range of the level ℓ.

•   Anonymity: Any adversary cannot obtain any information on each vehicle except the reputation level and the linkability (i.e., whether the vehicles of any two authentications are the same or not ) in each interval from the protocols. This means that the adversary cannot determine whether the vehicles of any two authentications are the same or not across intervals. Furthermore, this requirement means that the adversary cannot know the ID of the nearest RSU that executes the Update protocol.

We adjust the security requirements in the underlying system [7] to our above-mentioned model in the V2X communication, as follows. In the underlying system, each authentication is rated, and the score is added to the reputation of the user, but in the proposed system, scores in each interval are summed and added to the the reputation of the vehicle. Thus, in the underlying system, all authentications are unlinkable w.r.t. the sameness of the user, but in the proposed system, the authentications during each interval are linkable (the authentications across intervals are unlinkable).

Furthermore, we require the following security properties in authentications and RSU revocation.

•   Misauthentication resistance: In each Authentication protocol, any vehicle which does not succeed Show protocol in the current interval cannot be accepted.

•   RSU revocablity: An RSU can be revoked, and then any vehicle with a reputation certificate issued from a revoked RSU does not succeed Show protocol.

We formally define the security requirements, as follows.

3.2.1 Reputation Unforgeability

In the definition of reputation unforgeability, we utilize the following oracles.

•   OCV−Reg: It takes as input vehicle ID k. A Register protocol is executed between the honest CA and a corrupted vehicle k controlled by the adversary 𝒜. k is added to the set of corrupted vehicles CV.

•   OCV−Show: It takes as inputs vehicle ID k∈CV, RSU ID i, and reputation level ℓ. A Show protocol is executed between an honest RSU i and a corrupted vehicle k controlled by the adversary 𝒜, where the reputation level ℓ is proved, the pseudonym pseuτ and the certificate pcertτ for the current interval τ are outputted, SSet is updated, and an entry (k,pseuτ,ℓ,Cm,t′,s~=0) is kept.

•   OCV−Auth: It takes as inputs vehicle ID k∈CV, RSU ID i, the pseudonym pseuτ at the current interval τ, message M, and the rated score s. An Authentication protocol is executed between an honest RSU i and a corrupted vehicle k controlled by the adversary 𝒜 with the current revocation list RLT, where s~ in the entry (k,pseuτ,ℓ,Cm,t′,s~) is updated as s~′=s~+s.

•   OCV−Update: It takes as inputs vehicle ID k∈CV, RSU ID i, and total score s~ at the current interval. An Update protocol is executed between an honest RSU i and a corrupted vehicle k controlled by the adversary 𝒜, where the total score s~ is added to the reputation rept−1 of the vehicle k, and repk of the entry (k,repk) is updated as repk′=repk+s~ (if no entry for k, new entry of (k,repk=s~) is generated).

•   ORevokeRSU: It takes as an input RSU ID i. Using RevokeRSU, the new RLT at the current interval T is outputted.

Then, consider the following reputation unforgeability game, where O=(OCV−Reg,OCV−Show,OCV−Auth,OCV−Update,ORevokeRSU).

Game𝒜RU(λ):

   (spk,ssk,SSet,{rski})←Setup(λ);

   Run 𝒜O(spk);

   Return 1 if

      the final OCV−Show oracle is accepted,

      but repk is not in the integer range of level ℓ.

   Return 0;

Definition 2(Reputation Unforgeability): An anonymous reputation system is reputation unforgeable, if for any PPT adversary 𝒜,Pr[Game𝒜RU(λ)=1] is negligible in λ.

3.2.2 Misauthentication Resistance

In the definition of misauthentication resistance, we utilize the oracles in the reputation unforgeability.

Then, consider the following misauthentication resistance game, where O=(OCV−Reg,OCV−Show,OCV−Auth,OCV−Update,ORevokeRSU).

Game𝒜MR(λ):

   (spk,ssk,SSet,{rski})←Setup(λ);

   Run 𝒜O(spk);

   Return 1 if

      the final OCV−Auth oracle is accepted,

      but the vehicle k is not accepted in OCV−Show oracle previously executed during the same

      interval.

   Return 0;

Definition 3(Misauthentication Resistance): An anonymous reputation system is misauthentication resistant, if for any PPT adversary 𝒜, Pr[Game𝒜MR(λ)=1] is negligible in λ.

3.2.3 RSU Revocability

In the definition of RSU revocability, we utilize the oracles in the reputation unforgeability.

Then, consider the following revocability game, where O=(OCV−Reg,OCV−Show,OCV−Auth,OCV−Update, ORevokeRSU).

Game𝒜Rev(λ):

   (spk,ssk,SSet,{rski})←Setup(λ);

   Run 𝒜O(spk);

   Return 1 if

      the final OCV−Show oracle is accepted,

      but for the vehicle k, the RSU i in the previously executed OCV−Update oracle is revoked.

   Return 0;

Definition 4(RSU Revocability): An anonymous reputation system is RSU revocable, if for any PPT adversary 𝒜, Pr[Game𝒜Rev(λ)=1] is negligible in λ.

3.2.4 Anonymity

In the definition of anonymity, we utilize the following oracles.

•   OHV−Reg: It takes as input vehicle ID k. A Register protocol is executed between the corrupted CA controlled by the adversary 𝒜 and an honest vehicle k. k is added to the set of honest vehicles HV.

•   OHV−Show: It takes as inputs vehicle ID k∈HV, RSU ID i, and reputation level ℓ. A Show protocol is executed between an honest vehicle k and a corrupted RSU i controlled by the adversary 𝒜, where the reputation level ℓ is proved, the pseudonym pseuτ and the certificate pcertτ for the current interval τ are outputted, SSet is updated, and an entry (k,pseuτ,ℓ,Cm,t′,s~=0) is kept.

•   OHV−Auth: It takes as inputs vehicle ID k∈HV, RSU ID i, the pseudonym pseuτ at the current interval τ, message M, and the rated score s. An Authentication protocol is executed between an honest vehicle k and a corrupted RSU i controlled by the adversary 𝒜 with the current revocation list RLT, where s~ in the entry (k,pseuτ,ℓ,Cm,t′,s~) is updated as s~′=s~+s.

•   OHV−Update: It takes as inputs vehicle ID k∈HV, RSU ID i, and total score s~ at the current interval. An Update protocol is executed between an honest vehicle k and a corrupted RSU i controlled by the adversary 𝒜, where the total score s~ is added to the reputation rept−1 of the vehicle k, and repk of the entry (k,repk) is updated as repk′=repk+s~ (if no entry for k, new entry of (k,repk=s~) is generated).

•   ORevokeRSU: It takes as an input RSU ID i. Using RevokeRSU, the new RLT at the current interval T is outputted.

•   OLoR: It takes as inputs vehicle IDs k0∗,k1∗∈HV, RSU ID i, and reputation level ℓ. Return 0 if repk0∗≠repk1∗ for entries (k0∗,repk0∗),(k1∗,repk1∗). Otherwise, select random bit b, and a Show protocol is executed between an honest vehicle kb∗ and a corrupted RSU i controlled by the adversary 𝒜, where the reputation level ℓ is proved, the pseudonym pseuτ and the certificate pcertτ for the current interval τ are outputted, SSet is updated, and an entry (kb∗,pseuτ,ℓ,Cm,t′,s~=0) is kept. After that, a Show protocol is executed between an honest vehicle k¬b∗ and a corrupted RSU i similarly. Then, Authentication protocols for kb∗ and for k¬b∗ with corrupted RSUs are executed, and Update protocols for kb∗ and for k¬b∗ with corrupted RSUs are executed, where the added score s~ is the same.

Then, consider the following anonymity game, where O=(OHV−Reg,OHV−Show,OHV−Auth,OHV−Update, ORevokeRSU,OLoR).

Game𝒜Ano(λ):

  (spk,ssk,SSet,{rski})←Setup(λ);

  b′←𝒜O(spk,ssk,{rski});

  Return 1 if b=b′;

  Return 0;

Definition 5(Anonymity): An anonymous reputation system is anonymous, if for any PPT adversary 𝒜, |Pr[Game𝒜Ano(λ)=1]−1/2| is negligible in λ.

4  Proposed Scheme

4.1 Construction Idea

In BARS [6], two central authorities update a certificate for a short-time public key and the reputation to issue the vehicle, where the authorities have to evaluate each vehicle and update the reputation and the certificate. As a result, the update process is centralized and not scalable.

In our system, distributed RSUs in the V2X system manage the scores of each vehicle in each interval, and the nearest RSU updates a certificate for the new reputation using the RSU’s secret key.

As the base system, we adopt the anonymous reputation system [7] for crowdsensing. In the system, a server and users participate. The server issues a certificate for the reputation to each user, where the certificate is a BBS+ signature on the user’s secret, a certificate tag for checking one-time use of the certificate, and the reputation. Since the concrete value of the reputation can reveal the relevance to other authentications, the reputation level (an integer range where the reputation value is included) is shown in the Show protocol for authentication. In addition, while the reputation value is hidden using commitments, the certificate is updated by the server s.t. the certified reputation is reflected by the score for the authentication using the evaluation method of ARTSense [4].

We extend the system of [7] to construct the anonymous reputation system for V2X communication, as follows. In our system, a CA, RSUs, and vehicles participate. The central CA generates the CA’s key pair, and each RSU’s individual key pairs, and also generates the certificate of the RSU’s public key as a BBS+ signature which can be proved by an SPKs. The BBS+ signature is also used for RSU revocation, as mentioned later. At first, a vehicle is issued as an initial certificate which is similar to the original certificate in [7], i.e., a BBS+ signature on the user’s secret, a certificate tag, and the (initial) reputation. The original Show protocol is separated to Show protocol and Update protocol in our system. In Show called in the first time of each time interval, a vehicle proves the knowledge of the reputation certificate similarly to [7] to show the reputation level. In Update called in the final time of each time interval, instead of the central CA, the nearest RSU updates the reputation certificate reflected by the total score of the vehicle in the interval, where the BBS+ signature of the certificate is generated using the RSU’s secret key.

The point in this construction is that, in Show, the vehicle needs to hide the ID of the RSU updating the certificate, since the RSU’s ID allows one to link Show and Update by the same RSU. This is why we use an SPK where the RSU’s public key of BBS+ signatures is hidden but the correctness is ensured by proving the knowledge of the certificate of the public key.

In addition, we introduce the authentication protocol for each vehicle accepted by Show protocol to send a message to the nearest RSU. In Show protocol, for a short time public key in an ordinary digital signature scheme, the public key certificate is issued from the RSU. In each message authentication, the sent message is signed w.r.t. the public key. Thus, authentications during one interval can be linked. However, authentications across the interval are unlinkable.

Furthermore, we adopt a CS-based revocation method for RSUs. A CS tree is constructed, where each leaf corresponds to an RSU. The certificate of an RSU’s key consists of BBS+ signatures on the RSU’s secret key and on each node ID uj along the path from the root to the RSU’s leaf. To revoke an RSU, the CA selects cover nodes representing the revocation and publishes BBS+ signatures on these cover nodes together with the revocation interval, forming the revocation certificate. In the Show protocol, the vehicle additionally proves that for some node ID uj—which is signed by a BBS+ signature for the public key of the RSU that issued the current reputation certificate—the uj is a cover node, i.e., it is signed as part of the revocation certificate. This implies that the RSU has not been revoked.

4.2 Proposed Algorithm and Protocols

Fig. 2 illustrates the overall protocol flow among the vehicle, the nearest RSU, and the CA. The system public parameters are published to all participants. In Setup, the CA distributes secret keys to RSUs. In Register, the CA provides each vehicle with a vehicle secret key and an initial reputation certificate. The latest RSU revocation list is distributed in RevokeRSU. At the beginning of each interval, the vehicle executes the Show protocol with the nearest RSU to prove its reputation level and register a fresh short-term public key as its pseudonym key. During the interval, messages are authenticated using pseudonym-based signatures, and the RSU locally updates the scores. At the end of the interval, the vehicle anonymously obtains an updated reputation certificate from the nearest RSU through the Update protocol.

Figure 2: Protocol flow: Setup, Register, RevokeRSU, Show, per-message Authentication in an interval, and Update

The proposed algorithm and protocols are as follows.

Setup: In this algorithm, the CA generates key pairs of BB signatures and BBS+ signatures. Then, the CA computes the BB signature on every value in the integer range of reputation level 1≤ℓ≤L as the reputation level certificate. The CA also computes the secret key rski of each RSU i and their BBS+ signatures. The RSU is authenticated using CS-method-based revocable scheme. In the previous work [7], a BB signature certificate for the public key w2,i=h0γ2,i of RSU i was issued as A~i=f01/(γ1+γ2,i). However, in the proposed system, the certificate is changed to a BBS+ signature certificate A~i,j. This allows it to serve not only as the certificate of RSU public key but also as the certificate A of node uj in the CS method.

1.    Select bilinear groups G1,G2,GT, and a bilinear map e with a prime order p>2λ, where λ is the given security parameter. Then, select g0,g1,g2,g3,g4,f0,f1←RG1, h0,h1←RG2. For all 1≤ℓ≤L, choose γ0,ℓ←RZp∗, and computes w0,ℓ=h0γ0,ℓ, where γ0,ℓ is the secret key for the BB signature proving the reputation level ℓ. Choose γ1←RZp∗, and compute w1=h0γ1, where γ1 is the secret key for the following certificate (BBS+ signature) for w2,i. For all RSU i∈[1,numRSU], where numRSU is the number of RSUs, choose γ2,i←RZp∗, and compute w2,i=h0γ2,i and w~2,i=g3γ2,i where γ2,i is the secret key of every RSU i in the BBS+ signatures. As the special secret key of the CA, choose γ2,0←RZp∗, and compute w2,0=h0γ2,0 and w~2,0=g3γ2,0.

2.    For all 1≤ℓ≤L, generate the reputation level certificate Aℓ,Rℓ,k=f01/(γ0,ℓ+Rℓ,k) (BB signature) for every value Rℓ,k in the ℓ-th integer range indicating reputation level ℓ, where Kℓ is the number of the values in the ℓ-th integer range.

3.    The CA assigns RSU i to a leaf ul of a binary tree in CS method, and u0,ul,⋯,uℓ are the nodes on the path from the root node to the leaf node uℓ. For j=0,⋯,ℓ, randomly choose ηi,j′,ζi,j′←RZp∗ and issue a BBS+ signature (A~i,j,ηi,j′,ζi,j′) on (uj,γ2,i) s.t.

A~i,j=(g0g1ζi,j′g2ujg3γ2,i)1γ1+ηi,j′.

Then, send ⟨vi⟩:=(u0,u1,⋯,uℓ) to RSU i. The public key of RSU i is w~2,i=g3γ2,i.

4.    For pseudonym certificates of each RSU i∈[0,numRSU], generate a secret key pcski and the corresponding public key pcpki in the ordinary digital signature scheme. For the public key certificates, generate a secret key pcskCA of CA and the corresponding public key pcpkCA in the ordinary digital signature scheme. For every i∈[1,numRSU], generate the public key certificate pcpkcerti as the digital signature on message (pcpki,i) using the secret key pcskCA.

5.    Initialize set SSet as empty, and output CA’s public key

spk=(p,G1,G2,GT,e,{w0,ℓ}ℓ=1L,w1,{(w2,i,w~2,i}i=0numRSU,g0,g1,g2,g3,g4,f0,f1,h0,h1,{{Aℓ,k}k=1Kℓ}ℓ=1L,{⟨vi⟩,{(A~i,j,ηi,j′,ζi,j′)}j=0ℓ}i=0numRSU,pcpkCA),

the CA’s secret key ssk=γ2,0, and the RSU’s secret key rski=(γ2,i,pcski,pcpki,pcpkcerti) for i∈[1,numRSU].

Register: This is an interactive protocol between a vehicle V and the CA. The CA issues an initial reputation certificate cert0 for the vehicle. The common input is spk, and the CA’s input is ssk.

1.   [V]: Select secret x←RZp∗, a reputation certificate’s tag S0←RZp∗, and a random factor ζ0′←RZp∗. Compute the commitment to the messages (x,S0) to be signed by Cm,0′=g1ζ0′g2xg3S0. Then, prove to the CA that Cm,0′ is correctly formed by the following SPK on a random message M^.

SPK{(ζ0′,x,S0):Cm,0′=g1ζ0′g2xg3S0}(M^)

2.   [CA]: Set the initial reputation as rep0=0, and choose random factors ζ0′′,η0←RZp∗. Then, using the secret key γ2,0 of BBS+ signatures, sign the vector of messages (x,S0,rep0) as B0=(g0g1ζ0′′Cm,0′g4rep0)1/γ2,0+η0, and send back σ~0′=(B0,η0,ζ0′′) to the vehicle.

3.   [V]: Set Cm,0=Cm,0′g4rep0 for rep0=0, compute ζ0=ζ0′+ζ0′′, and set the BBS+ signature on the messages (x,S0,rep0) as σ~0=(B0,η0,ζ0), where B0=(g0g1ζ0g2xg3S0g4rep0)1/γ2,0+η0. Output cert0=(x,rep0,σ~0,S0,Cm,0).

RevokeRSU: This algorithm enables the CA to revoke an RSU. For the current tree, the cover nodes obtained using the CS method are denoted as {u0′,u1′,⋯,unum′}, where num≤r⋅log⁡(N/r). For all i∈[0,num], random values ηT,j′′,ζT,j′′←RZp∗ are chosen, and the revocation certificate is calculated as a BBS+ signature (RT,j,ηT,j′′,ζT,j′′) on (uj′,T) s.t.

RT,j=(g0g1ζT,j′′g2uj′g3T)1γ1+ηT,j′′.

The revocation list is output as RLT={(RT,j,ηT,j′′,ζT,j′′)}j=1num.

Show: This is an interactive protocol between a vehicle V and the nearest RSU, where the vehicle shows RSU its reputation level ℓ, a pseudonym pseuτ is registered for a time interval τ, and the corresponding secret key pskτ is kept in V. At the beginning of the protocol, the vehicle’s reputation value is proved on certt−1, where the vehicle’s inputs are certt−1=(x,rept−1,σ~t−1,St−1,Cm,t−1), where σ~t−1=(Bt−1,ηt−1,ζt−1). Here, t indicates the number of updates in the reputation certificates for the vehicle. Let RSU i be the RSU that issued σ~t−1. The input of RSU is SSet.

1.   [V]: From spk, retrieve a reputation level certificate Aℓ,rept−1 such that its current reputation rept−1 is in the ℓ-th range. Choose rAℓ←RZp and compute the commitment CAℓ=Aℓ,rept−1f1rAℓ and ρ=rAℓ⋅rept−1. Retrieve a certificate (A~i,j,ηi,j′,ζi,j′) for a node uj of the CS-method tree s.t. the certificate was issued to the RSU i and uj is a cover node at the current revocation time T. Choose ζ′^←RZp and compute the commitment CA~i,j=A~i,jg1ζ^′. Choose rw~2,i←RZp and compute the commitment Cw~2,i=w~2,if1rw~2,i. Set θ′=ζi,j′+ζ^⋅ηi,j′. Retrieve the revocation certificate (RT,j,ηT,j′′,ζT,j′′) for the cover node uj at T. Choose ζ′′^←RZp, and compute CRT,j=RT,j⋅g1ζ^′′. Set θ′′=ζT,j′′+ζ^′′⋅ηT,j′′ Then, choose ζ^,rw2,i←RZp, compute the commitments CBt−1=Bt−1g1ζ^ and Cw2,i=w2,i⋅h1rw2,i, and set θ=ζt−1+ζ^ηt−1. Choose ζt′←RZp∗ and St←RZp∗, and compute Cm,t′=g1ζt′g2xg3Stg4rept−1 as the commitment to the vector of (x,St,rept−1). Set ν=ζ^⋅rw2,i and compute the commitments Cζ^=g0ζ^g1rζ^ and Cν=g0νg1rν for a randomly chosen rζ^,rν∈Zp. Set β^=rν−rw2,i⋅rζ^. Send CAℓ,CA~i,j,Cw~2,i,CRT,j,CBt−1,Cw2,i,Cm,t′,Cζ^,Cν, and St−1 to the nearest RSU, and using the following SPK on a random message M^, prove that the reputation rept−1 is in the ℓ-th range, certt−1 is valid, Cm,t′ is correct, and the RSU i is not revoked.

SPK{(rAℓ,rept−1,ρ,θ′,uj,rw~2,i,ηi,j′,ζ^′,θ′′,ηT,j′′,ζ^′′,θ,x,rw2,ηt−1,ζ^,ν,rζ^,rν,β^,ζt′,St):e(CAℓ,w0,ℓ)⋅e(f0,h0)−1=e(f1,w0,ℓ)rAℓ⋅e(CAℓ,h0)−rept−1⋅e(f1,h0)ρ(1)

∧e(CA~i,j,w1)⋅e(Cw~2,i,h0)−1⋅e(g0,h0)−1=e(g1,h0)θ′⋅e(g2,h0)uj⋅e(f1,h0)−rw~2,i⋅e(CA~i,j,h0)−ηi,j′⋅e(g1,w1)ζ^′(2)

∧e(CRT,j,w1)⋅e(g3,h0)−T⋅e(g0,h0)−1=e(g1,h0)θ′′⋅e(g2,h0)uj⋅e(CRT,j,h0)−ηT,j′′⋅e(g1,w1)ζ^′′(3)

∧e(CBt−1,Cw2,i)⋅e(g3,h0)−St−1⋅e(g0,h0)−1=e(g1,h0)θ⋅e(g2,h0)x⋅e(g4,h0)rept−1⋅e(CBt−1,h1)rw2,i    ⋅e(CBt−1,h0)−ηt−1⋅e(g1,Cw2,i)ζ^⋅e(g1,h1)−ν(4)

∧Cζ^=g0ζ^g1rζ^∧Cν=g0νg1rν(5)

∧Cν=Cζ^rw2,i⋅g1β^(6)

∧e(Cw~2,i,h0)⋅e(g3,Cw2,i)−1=e(f1,h0)rw~2,i⋅e(g3,h1)−rw2,i(7)

∧Cm,t′=g1ζt′g2xg3Stg4rept−1}(M^).(8)

The Eq. (1) implies the verification of the (variant of) BB signature A~ℓ on message rept−1 for level ℓ, as in [7]. The Eq. (2) implies the verification of the BBS+ signature (A~i,j,ηi,j′,ζi,j′) on messages uj,γ2,i w.r.t. the CA’s public key w1, which ensures the node uj on the path to RSU and the RSU’s public key w2,i. The Eq. (3) implies the verification of BBS+ signature (RT,j,ηT,j′′,ζT,j′′) on message uj,T w.r.t. public key w1, which ensures that the cover node uj of the tree at time T is the same as the node uj for A~i,j. The Eqs. (5) and (6) show ν=ζ^⋅rw2,i, and thus the Eq. (4) implies the verification of the BBS+ signature (Bt−1,ηt−1,ζt−1) on messages x,St−1,rept−1 w.r.t. the RSU i’s public key w2,i. The Eq. (7) shows the same secret key γ2,i of w2,i and w~2,i. These are proved in Lemma 1 in the next section.

2.   [RSU]: To check the freshness of the proved certificate, check if St−1∈SSet. If it is true, abort. Otherwise, add tag St−1 in set SSet. Verify the SPK. If it is invalid, abort.

3.   [V]: Generate a short-time key pair in the ordinary digital signature scheme, where the public key is opkτ and the secret key is oskτ. Send opkτ as the pseudonym at the current interval τ.

4.   [RSU]: As the certificate on opkτ, generate the ordinary signature sigi,τ on message (opkτ,ℓ,τ,i) using the secret key pcski in rski, for the reputation level ℓ of the vehicle, and send pseuτ=opkτ and pcertτ=(sigi,τ,pcpki,pcpkcerti). Output pseuτ, pcertτ, Cm,t′, and the updated SSet.

5.   [V]: Verify the signature sigi,τ on (opkτ,ℓ,τ,i) using the public key pcpki in the ordinary digital signatures. Verify the signature pcpkcerti on (pcpki,i) using the public key pcpkCA in the ordinary digital signatures. If either is invalid, abort. Otherwise, output pseuτ=opkτ, pcertτ=(sigi,τ,pcpki,pcpkcerti), and pskτ=oskτ.

Authentication: This is an interactive protocol between a vehicle V and the nearest RSU. The common input is spk, and the input of the vehicle is message M, pseuτ, pcertτ, and pskτ. The output of the RSU is the validity bit 1 (accepted) or 0 (rejected), and (M,pseuτ).

1.   [V]: For message M, using the secret key pskτ=oskτ, compute the digital signature authsig on M and send (M,authsig,pseuτ,pcertτ,ℓ).

2.   [RSU]: Using pcpki (resp., pcpkCA), verify the signature sigi,τ (resp., pcpkcerti) on (opkτ,ℓ,τ,i) (resp., (pcpki,i)) where pcertτ=(sigi,τ,pcpki,pcpkcerti) and pseuτ=opkτ. Using opkτ, verify the signature authsig on M. If either one is not valid, abort. Otherwise, this vehicle is accepted. Output (M,pseuτ).

Update: This is an interactive protocol between a vehicle and the nearest RSU i. The common input is spk, and the input of the vehicle is certt−1 for the previous reputation rept−1, and the inputs of the RSU i are pseuτ,Cm,t′,s~τ,rski. The output of the vehicle is a new reputation certificate certt for the updated reputation rept=rept−1+s~τ.

1.   [RSU]: Compute Cm,t=Cm,t′g4s~τ, and using γ2,i in rski=(γ2,i,pcski,pcpki,pcpkcerti), generate Bt=(g0g1ζt′′Cm,t)1/γ2,i+ηt=(g0g1ζt′′g1ζt′g2xg3Stg4rept−1g4s~τ)1/γ2,i+ηt for ζt′′,ηt←RZp∗. Then, send back σ~t′=(Bt,ηt,ζt′′) to the vehicle.

2.   [V]: Compute ζt=ζt′+ζt′′, rept=rept−1+s~τ and set the signature on the vector of messages (x,St,rept) as σ~t=(Bt,ηt,ζt), where Bt=(g0g1ζtg2xg3Stg4rept)1/γ2,i+ηt. Output certt=(x,rept,σ~t,St,Cm,t).