A Distributed Pseudonym Management Scheme in VANETs

Abstract

Security and privacy have been important issues in VANETs. Anonymity is an effective way to achieve privacy protection, and it sometimes requires to be disclosed for determining traffic liability. In most pseudonym schemes, an authority is aware of a vehicle's secret, and its compromise will result in the leakage of a large amount of privacy information. So, we propose a distributed traceable pseudonym management scheme in VANETs. In the scheme, a blind signature method is adopted to achieve strict separation of issuance and tracking. The distributed tracking protocol is proposed to enhance the robustness for tracking, which is based on the improved scheme for shared generation of RSA keys. An efficient pseudonymous authentication mechanism is proposed to reduce the communication overhead. Compared with other related proposals, our scheme is unforgeability, especially against authority forge attacks, and has better robustness. Moreover, the performance analysis shows that it is efficient in VANETs.

1. Introduction

Vehicle-to-vehicle and vehicle-to-infrastructure communications improve vehicle's perception from the surrounding environment. Vehicular ad hoc networks (VANETs) will be used widely in collision avoidance, road-hazard notification, and coordinated driving systems [1]. Nonetheless, there are many security threats in VANETs [2–4]. For example, an attacker might tamper with messages to evade accident liability or forge information to meet specific needs. The attacker also might eavesdrop on broadcast messages, analyze data, and track a vehicle. So, security and privacy have been important issues in VANETs.

A number of studies have been made on the issues of security and privacy preservation. Raya and Hubaux [5, 6] pointed out that anonymity is conditional for liability purposes and that authority can disclose the pseudonym. In [5, 6], a security protocol was introduced. Although this protocol can effectively meet the conditional privacy requirement, it is far from efficient and can hardly become a scalable and reliable approach, because the authority has to keep all the anonymous certificates for each vehicle. Lin et al. [7] proposed a security and privacy preserving protocol. With group signature, security, privacy, and traceability can be achieved without inducing the overhead of managing a huge number of stored certificates at the authorities' sides. Calandriello et al. [8, 9] proposed on-the-fly pseudonym generation and self-certification, which alleviates the overhead of managing certificates. Group signature method is adopted to ensure that legitimate nodes can generate their pseudonyms anonymously. Lu et al. [10] presented a conditional privacy preservation protocol, which improves efficiency in terms of the minimized anonymous keys storage at each vehicle. Performance evaluation shows that the protocol can achieve much better efficiency than Raya and Hubaux's [5, 6] and Lin et al.'s [7] when vehicles are revoked. Zhang et al. [11] proposed a scalable robust authentication protocol. In [11], some roadside units (RSUs) serve as the issuer of vehicles' private key, and a signcryption method is employed to distribute the keys securely. Hao et al. [12] proposed a distributed key management framework, which has advantages in the revocation of malicious vehicles and system maintenance. An efficient cooperative message authentication protocol is developed to reduce the computation and communication overhead in the group signature.

The above reported schemes [7–12] are based on group signature. In Boneh et al.'s group signature scheme [13], each user's private key is generated by the private-key issuer, which is a hidden security threat. In [7–9], each vehicle's group private key is computed by a member manager. In [10], a trusted authority is required; the authority generates valid private keys for on-board unit and RSU. In [11], RSU generates and sends the group private key to the vehicle. In [12], some measures are adopted to prevent RSU from misbehaving, but authorities cannot decide which is the malicious, RSU or the vehicle or both, when they find a mismatch. Therefore, these schemes [7–12] suffered from private key revealing attacks, in which the private-key issuer knows each user's private key.

Schaub et al. [14] adopted blind signature technology to achieve the separation of issuing and tracking. But the disadvantages of the scheme are that V-token ( $V_i=E_{{\text{PK}}_{\text{RA}}}(id\parallel r_i)$ ) is produced by a vehicle alone; thus, the vehicle might forge other vehicle's V-token. Moreover, if CA is not credible, it can generate V-token by itself and sign it. CA can obtain the pseudonym certificate from a pseudonym provider and impersonate any vehicle.

To solve the above problems, this paper presents a distributed pseudonym management scheme in secure VANETs. The main contributions of the scheme are as follows. (1) Pseudonym is coproduced by the issuer and the vehicle. Either party attempting to deceive can be detected. It can resist authority forge attacks. (2) An efficient pseudonym authentication mechanism is proposed by finding the optimal number of messages with the pseudonym certificate, which not only reduces the communication overhead but also ensures the message authentication probability $P_{\text{auth}}>95\%$ . (3) Distributed pseudonym tracking based on secret sharing method is presented. The initialization of the tracking protocol does not require a trusted center, thus avoiding any single point of failure. It offers better robustness.

The remainder of this paper is organized as follows. The pseudonym management model is given in Section 2. The pseudonym issuance protocol, the pseudonymous authentication protocol, and the distributed tracking protocol are presented in Sections 3, 4, and 5, respectively. Section 6 analyzes and compares the security and the performance of our scheme with other related schemes. Finally, the conclusion of this paper is given in Section 7.

2. Pseudonym Management Model

There are three types of entities: (1) a vehicle (V). Its identity is ${\text{ID}}_V$ , corresponding to a long-term public key $(N_V,e_V)$ and a long-term private key $d_V$ . Its pseudonym is ID_PV, corresponding to a short-term public key $(N_{\text{PV}},e_{\text{PV}})$ and a short-term private key $d_{\text{PV}}$ . The vehicle contains a sensing input module, a wireless communication module, a central processing module, and a hardware security module (HSM) [15]. The HSM generates public and private keys, stores private keys, and provides digital signature service. (2) An authority: it is divided into certificate authority (CA), pseudonym certificate authority (PCA), and tracking authority (TA). PCA issues pseudonym certificates, but it does not know the pseudonym. Only TA knows the relation between the pseudonym and the identity. CA issues ${\text{Cert}}_V$ , and ${\text{Cert}}_V$ contains ${\text{ID}}_V$ and $(N_V,e_V)$ . PCA issues Cert_PV, and Cert_PV contains ID_PV and $(N_{\text{PV}},e_{\text{PV}})$ . PCA's public and private keys are denoted as $(N_{\text{PCA}},e_{\text{PCA}})$ and $d_{\text{PCA}}$ , respectively. TA's public and private keys are denoted as $(N,e)$ and d, respectively. There are some PCAs in the model, and V may apply for a pseudonym to the neighboring PCA. Only a few suspicious vehicles need to be disclosed, so TAs are rare. But if only one authority acts as TA, abuse can occur. Based on the secret sharing method, we extend one authority to k authorities forming $\text{TAs}=\{{\text{TA}}_1,{\text{TA}}_2,\dots ,{\text{TA}}_k\}$ . ${\text{TA}}_i$ ( $1⩽i⩽k$ ) may be a law enforcement agency, a judge, or a privacy protection agency. ${\text{TA}}_i$ 's identity is ${\text{ID}}_i$ . Assume that the vehicle is preloaded with the public keys of CA, PCA, and TAs during the vehicle's initialization. (3) Roadside unit (RSU): it communicates with vehicles and other devices on the internet.

The security and privacy requirements in the model are as follows.

Anonymity. For other entities (such as PCA, attackers) except TAs, it is computationally infeasible to disclose the identity from a pseudonym.

Traceability. If the members in TAs implement the protocol honestly, at least m members can disclose collaboratively the identity from a pseudonym.

Unforgeability. For any entity, it is computationally infeasible to forge a false signature or impersonate another entity.

Robustness. If any authority compromises, the implementation of pseudonym issuance, pseudonymous authentication, and tracking are not affected.

The process of pseudonym management is shown in Figure 1. (1)  The vehicle V gets an identity certification from CA. (2)  V applies for pseudonym certificates. (3)  PCA issues some pseudonym certificates to V. (4)  V communicates with other vehicles and RSU with the pseudonym certificates. (5)  Once other vehicles find suspicious vehicles, they submit a tracking request to TAs. (6)  TAs disclose the identity from the pseudonym.

Figure 1

Pseudonym management framework.

The model consists of three protocols: a pseudonym issuance protocol, a pseudonymous authentication protocol, and a distributed tracking protocol. TAs' public key $(N,e)$ is generated during the initialization stage and used in the pseudonym issuance protocol. Pseudonym certificates are generated in the issuance protocol and used in the pseudonymous authentication protocol. Once suspicious messages appear in pseudonymous authentication, the distributed tracking protocol is activated.

3. Pseudonym Issuance Protocol

Chaum [16] first proposed the concept of a blind signature, which allows users to get a message signature without leaking any contents. The pseudonym certificate issuance protocol adopts the blind signature method.

• (1)

V sends ${\text{ID}}_V\parallel n\parallel {({\text{ID}}_V\parallel n)}^{d_v}\mathrm{mod}{N}_V\parallel {\text{Cert}}_V$ to PCA, where n is the number of pseudonyms.

(2)

PCA verifies ${({\text{ID}}_V\parallel n)}^{d_v}\mathrm{mod}{N}_V$ , if passed, and sends ${\text{ID}}_{\text{PCA}}\parallel {\text{ID}}_V\parallel \text{exp}\parallel (({\text{ID}}_{\text{PCA}}\parallel {\text{ID}}_V\parallel \text{exp}{)}^{d_{\text{PCA}}}\mathrm{mod}{N}_{\text{PCA}}{)}^{e_V}\mathrm{mod}{N}_V$ to V, where $\text{exp}$ is the expiration date.

(3)

V extracts $(({\text{ID}}_{\text{PCA}}\parallel {\text{ID}}_V\parallel \text{exp}{)}^{d_{\text{PCA}}}\mathrm{mod}{N}_{\text{PCA}}{)}^{e_V}\mathrm{mod}{N}_V$ , decrypts it, and gets ${({\text{ID}}_{\text{PCA}}\parallel {\text{ID}}_V\parallel \text{exp})}^{d_{\text{PCA}}}\mathrm{mod}{N}_{\text{PCA}}$ . Then V verifies PCA's signature, if passed, picks two random integers $r_i$ and $x_i$ ( $1⩽i⩽2n$ ), and generates the pseudonyms as follows:

$$\begin{array}{l}{\text{ID}}_{\text{P}{\text{V}}_i}\\ ={\left(r_i\parallel {r_i}^{d_v}\mathrm{mod}{N}_V\parallel {\left({\text{ID}}_{\text{PCA}}\parallel {\text{ID}}_V\parallel \text{exp}\right)}^{d_{\text{PCA}}}\mathrm{mod}{N}_{\text{PCA}}\right)}^e\mathrm{mod}N,\end{array}$$

(1)

 

V extends them to

$$\begin{array}{cc}& b_i={\text{ID}}_{\text{PCA}}\parallel {\text{ID}}_{\text{P}{\text{V}}_i}\parallel \text{exp}\parallel e_{{\text{PV}}_i}\parallel N_{{\text{PV}}_i}.\end{array}$$

(2)

 

V sends PCA the blind alternative commitments $c_i=({x_i}^{e_{\text{PCA}}})·\text{SHA}(b_i)\mathrm{mod}{N}_{\text{PCA}}$ ( $1⩽i⩽2n$ ), where SHA is a message digest function.

(4)

PCA randomly generates verification set I, $I=\{i\mid i\in [\mathrm{1,2}n]\}$ , and $|I|=n$ , and sends I to V.

(5)

V shows $\{(r_i,{r_i}^{d_v},x_i,e_{{\text{PV}}_i},N_{{\text{PV}}_i})\mid i\in I\}$ to PCA.

(6)

PCA computes ${\text{ID}}_{{\text{PV}}_i}^{\prime }$ , $b_i^{\prime }$ and $c_i^{\prime }=({x_i}^{e_{\text{PCA}}})·\text{SHA}(b_i^{\prime })\mathrm{mod}{N}_{\text{PCA}}$ and checks $c_i^{\prime }=c_i$ . If passed, PCA sends the blind signatures $\{{c_j}^{d_{\text{PCA}}}\mathrm{mod}{N}_{\text{PCA}}\mid j\notin I\}$ of the remaining commitments to V.

(7)

V removes the blind factors ${c_j}^{d_{\text{PCA}}}/x_j=\text{SHA}(b_j{)}^{d_{\text{PCA}}}\mathrm{mod}{N}_{\text{PCA}}(j\notin I)$ and gets the pseudonym certificates as follows:

$$\begin{array}{cc}& {\text{Cert}}_{{\text{PV}}_j}=b_j\parallel \text{SHA}{\left(b_j\right)}^{d_{\text{PCA}}}.\end{array}$$

(3)

The prerequisite of implementing the protocol is that during the initialization stage, V has got TAs' public key $(N,e)$ and PCA's public key $(N_{\text{PCA}},e_{\text{PCA}})$ . Before applying for a pseudonym, the short-time public and private keys of the vehicle have been already generated. (1) V sends a request signed with $d_V$ to PCA to prove its identity ${\text{ID}}_V$ . (2) PCA sends the signature secretly, not only to prove PCA's identity but also to coproduce V's pseudonym. Sending the signature secretly can prevent the signature from leaking. (3) V produces pseudonyms and blinds them. In (4), (5), and (6) PCA opens n commitments among $2n$ commitments to verify. If passed, PCA signs blindly the remaining n commitments. (7) V removes the blind factors and gets the pseudonym certificates.

In Schaub et al.'s issuance protocol [14], CA signs V-tokens for a vehicle. Pseudonym provider (PP) checks the validity of V-tokens; if valid, PP issues a pseudonym certificate. Four rounds of interaction are required. If CA wants to cheat, it will not interact with a vehicle. And it will obtain a fake pseudonym certificate and impersonate a vehicle, so will PP.

In our issuance protocol, PCA issues directly a pseudonym certificate to a vehicle, and three rounds of interaction are required. A pseudonym is coproduced by V and PCA. PCA cannot provide $r_i\parallel {r_i}^{d_v}$ to forge a pseudonym of V. V cannot provide $({\text{ID}}_{\text{PCA}}\parallel {\text{ID}}_{V^{*}}\parallel \text{exp}{)}^{d_{\text{PCA}}}$ to forge the pseudonym of another vehicle $V^{*}$ . Even if V eavesdrops on the communication between $V^{*}$ and PCA, V cannot decrypt $(({\text{ID}}_{\text{PCA}}\parallel {\text{ID}}_{V^{*}}\parallel \text{exp}{)}^{d_{\text{PCA}}}\mathrm{mod}{N}_{\text{PCA}}{)}^{e_{V^{*}}}$ . So, it fails to forge the pseudonym. Furthermore, the cut-choose method is also adopted in our protocol, like in Schaub et al.'s protocol, and prevents content spoofing to a certain extent.

As a result, our issuance protocol maintains good property of vehicular privacy in the presence of an authority and provides security against authority forge attack. Moreover, the communication overhead is reduced from four rounds to three rounds.

4. Pseudonymous Authentication Protocol

A complete authentication message consists of six fields: messageID $\parallel$ payload $\parallel$ timestamp $\parallel$ signature $\parallel$ certificate $\parallel$ TTL. “MessageID” is the message number during the same pseudonym period. “Payload” contains collision data, location, direction, speed, and so on. “Timestamp” is to prevent from replaying attacks. “Signature” is the signature of the first three fields. The next field is $\text{Cer}{\text{t}}_{\text{P}{\text{V}}_i}=b_i\parallel \text{SHA}(b_i{)}^{d_{\text{PCA}}}$ , where $b_i={\text{ID}}_{\text{PCA}}\parallel \text{I}{\text{D}}_{{\text{PV}}_i}\parallel \text{exp}\parallel e_{{\text{PV}}_i}\parallel N_{{\text{PV}}_i}$ . “TTL” means how long the message is allowed to remain to prevent message flooding. If the key has 1024 bits, the signature has 1024 bits. As $\text{exp}$ has 26 bytes [17], the pseudonym certificate length is $L_{{\text{Cert}}_{\text{PV}}}=2+384+26+128+128+128=796$  B. Finally, the total message length is $L_{\text{Message}}=2+100+4+128+796+1=1031$  B, and the pseudonym certificate accounts for 77% of the total message length.

If each message carries a certificate of 796 bytes during the same pseudonym period, the communication overhead is high. If only the first message carries the certificate, the message length is reduced from 1031 bytes to 235 bytes. However, if the first message with the certificate does not arrive at the receiver, other received messages which do not contain the certificate cannot be verified.

Some researchers proposed a mechanism to reduce the communication overhead of secure messages by omitting the inclusion of certificates in messages. Concrete methods such as the periodic omission of certificates, neighbor-based certificate omission, and congestion-based certificate omission were proposed in [9], [18], and [19], respectively. In these schemes, the optimal parameter was obtained by means of simulation. In contrast to the earlier proposals, we found the optimal parameter by means of probability analysis.

Define that α is the number of messages and λ is the number of messages with pseudonym certificate during one pseudonym period. If at least one message with certificate is accepted by the receiver, other arrived messages with the same pseudonym can be authenticated. Define the message authentication probability $P_{\text{auth}}$ as $P_{\text{auth}}=1-{(1-P_{\text{accept}})}^{\lambda }$ , where $P_{\text{accept}}$ is the packet reception rate. We used a packet reception rate model of broadcast channel in a good channel condition $P(d)=-0.004d+1/7\sin (\pi /125d)+1$ [9], where d is the distance between the sender and the receiver.

Figure 2 shows the relationship among the message authentication probability $P_{\text{auth}}$ , the intervehicle distance d, and the number of messages with certificate λ. Assuming that λ is a constant, $P_{\text{auth}}$ decreases with the increase of d; assuming that d is a constant, $P_{\text{auth}}$ increases with the increase of λ. From the figure, it can be further observed that if $\lambda \ge 5$ and $d\le 130$ , then $P_{\text{auth}}>95\%$ . That means we take $\lambda =5$ , which can meet the need of most vehicles for broadcast message authentication. Thus, $\lambda =5$ is the optimal number of messages with the pseudonym certificate.

Figure 2

Impact of different d and λ on pseudonymous authentication.

We define $len$ as the average message length, and Figure 3 shows the relationship between $len$ and α under the condition of $\lambda =5$ . The parameter $len$ decreases with the increase of α. It means that during a pseudonym period the more the messages are, the less communication overhead is.

Figure 3

Relationship between average message length and the number of messages during a pseudonym period.

5. Distributed Tracking Protocol

Based on the secret sharing scheme [20], TAs' private key d is assigned to the k authorities, and any one subset of at least m of them can disclose the secret. Generally, there is a trusted center during the initialization stage of the secret sharing scheme. Once the center compromises, the privacy will be leaked. Boneh and Franklin [21] discussed the generation of RSA keys without a dealer, but the protocol required the help of a third party. Cocks [22] presented another protocol to generate shared RSA keys without the help of a third party. There exists a large number of modular exponentiation operations to generate the modulus, and thus the efficiency of the protocol is poor. Malkin et al. [23] extended two parties [21] to k parties.

Instead of time-consuming modular exponentiation, we use modular multiplication to generate N, where N is the modulus of RSA. And furthermore, we extend the $(k,k)$ threshold schemeto a more general form $(m,k)$ , where m is the number of members and k is the threshold value. Based on the above ideas, the distributed tracking protocol is developed. It consists of distributed generation of modulus N, distributed generation of private key and secret share, and collaborative tracking. The first two parts are completed collaboratively by all members during initialization, and the third part is implemented collaboratively by at least m members during the tracking stage.

5.1. Distributed Generation of Modulus N

Each member ${\text{TA}}_i$ ( $1\le i\le k$ ) picks random primes $p_i$ , $q_i$ and computes modulus $N=({\sum }_{i=1}^k{p}_i)({\sum }_{i=1}^k{q}_i)$ without revealing $p_i$ , $q_i$ . Assuming that k is an odd, the steps are as follows:

• (1)

${\text{TA}}_i$ picks two random primes $p_i$ , $q_i$ and a random $r_{i,j}\in Z_P$   (prime $P>N$ ). ${\text{TA}}_i$ computes and sends $r_{i,j}{p}_i$ and $r_{i,j}{q}_i$ to ${\text{TA}}_j$ ( $1\le j\le k$ , $j\ne i$ ).

(2)

${\text{TA}}_j$ computes $r_{i,j}{p}_i{q}_j$ and $r_{i,j}{q}_i{p}_j$ and sends $r_{i,j}{p}_i{q}_j+r_{i,j}{q}_i{p}_j$ to ${\text{TA}}_i$ .

(3)

${\text{TA}}_i$ computes $s_{i,j}=(1/r_{i,j})(r_{i,j}{p}_i{q}_j+r_{i,j}{q}_i{p}_j)=p_i{q}_j+p_j{q}_i$ ( $j\ne i$ ),

$$\begin{array}{l}{N}_i={\sum }_{j=\mathrm{1},j\ne i}^k{s}_{i,j}+\mathrm{2}{p}_i{q}_i\\ \phantom{N_i}=p_i{\sum }_{j=\mathrm{1},j\ne i}^k{q}_j+q_i{\sum }_{j=\mathrm{1},j\ne i}^k{p}_j+\mathrm{2}{p}_i{q}_i\end{array}$$

(4)

 

and broadcasts $N_i$ in TAs.

(4)

All members compute ${\sum }_{i=1}^k{N}_i$ and get $N={\sum }_{i=1}^k{N}_i/2$ .

(5)

Any member in TAs picks an integer $g\in Z_N^{*}$ randomly and broadcasts g in TAs.

(6)

TA₁ computes and broadcasts $V_1=g^{N-p_1-q_1+1}\mathrm{mod}N$ ; all other members ${\text{TA}}_i$ ( $2\le i\le k$ ) compute and broadcast $V_i=g^{p_i+q_i}\mathrm{mod}N$ ; all members verify $V_1={\prod }_{i=2}^k{V}_i\mathrm{mod}N$ .

(7)

If the verification fails, all members execute steps (1)–(6) again. Otherwise, success is returned.

5.2. Distributed Generation of Private Key and Secret Share

$\varphi (N)$ is Euler function of N, denoted as ϕ. If N is the product of two primes,

$$\begin{array}{cc}& \varphi =N-{\sum }_{i=\mathrm{1}}^k{p}_i-{\sum }_{i=\mathrm{1}}^k{q}_i+\mathrm{1}.\end{array}$$

(5)

• (1)

  TA₁ computes ${\varphi }_1=N-p_1-q_1+1$ , and another member ${\text{TA}}_i$ ( $2\le i\le k$ ) computes ${\varphi }_i=-p_i-q_i$ . Then, each member ${\text{TA}}_i$ ( $1\le i\le k$ ) broadcasts ${\varphi }_i\mathrm{mod}e$ in TAs.

• (2)

  ${\text{TA}}_i$ collects ${\varphi }_j\mathrm{mod}e$ , and computes $\psi ={\sum }_{j=1}^k{\varphi }_j\mathrm{mod}e=\varphi \mathrm{mod}e$ and $\zeta =-{\psi }^{-1}\mathrm{mod}e$ .

•  

    ${\text{TA}}_i$ obtains its own private key

  $$\begin{array}{cc}& d_i=\lfloor \frac{\zeta {\varphi }_i}{e}\rfloor .\end{array}$$

  (6)

• (3)

  ${\text{TA}}_i$ picks a random degree $m-1$ polynomial $c_i(x)\in Z_P[x]$ , satisfying $c_i(0)=d_i$ . It computes $s_{i,j}=c_i({\text{ID}}_j)$ and sends $s_{i,j}$ to ${\text{TA}}_j$ ( $j\ne i$ ) secretly.

• (4)

  ${\text{TA}}_i$ collects $s_{j,i}$ , then computes the secret share

  $$\begin{array}{cc}& s_i={\sum }_{j=\mathrm{1}}^k{s}_{j,i}\mathrm{mod}P.\end{array}$$

  (7)

After implementing the protocol, each member obtains the private key $d_i$ and secret share $s_i$ . The operation of computing $\varphi \mathrm{mod}e$ reveals ${\log }_{\mathrm{2}}e$ low bits of ϕ. In order to protect ϕ from revealing more bits, we take a small e.

5.3. Collaborative Tracking

• (1)

The vehicle $V^{*}$ reports the signed message with a certificate to a tracking authority such as TA₁. TA₁ checks whether the signed message and the certificate are valid.

(2)

If passed, TA₁ extracts ID_PV from Cert_PV and sends ID_PV to other members. If $m-1$ members accept a tracking request, they constitute a tracking group. Assume that their identities are ${\text{ID}}_1,{\text{ID}}_2,\dots ,{\text{ID}}_m$ .

(3)

Participants ${\text{TA}}_i$ ( $2\le i\le m$ ) send ${{\text{ID}}_{\text{PV}}}^{{\alpha }_i}\mathrm{mod}N$ to TA₁, where ${\alpha }_i=s_i{l}_i(0)\mathrm{mod}P$ .

(4)

TA₁ tries all possible u and x ( $0⩽u⩽k-1$ , $-m<x⩽0$ ) and computes

$$\begin{array}{l}{{\text{ID}}_{\text{PV}}}^{xP+u}·\prod _{i=1}^m{{\text{ID}}_{\text{PV}}}^{{\alpha }_i}\mathrm{mod}N\\ =r\parallel r^{d_v}\mathrm{mod}{N}_V\parallel {\left({\text{ID}}_{\text{PCA}}\parallel {\text{ID}}_{\text{V}}\parallel \text{exp}\right)}^{d_{\text{PCA}}}\mathrm{mod}{N}_{\text{PCA}}.\end{array}$$

(8)

It extracts $(\text{I}{\text{D}}_{\text{PCA}}\parallel {\text{ID}}_V\parallel \text{exp}{)}^{d_{\text{PCA}}}\mathrm{mod}{N}_{\text{PCA}}$ and further gets ${\text{ID}}_{\text{PCA}}\parallel {\text{ID}}_V\parallel \text{exp}$ with $e_{\text{PCA}}$ . TA₁ gets ${\text{ID}}_V$ according to the actual meaning of the strings.

Then TA₁ submits ${\text{ID}}_V$ to PCA, and PCA puts it into the blacklist. PCA will reject the request of the vehicle in the blacklist for pseudonym certificates. So, the pseudonym tracking protocol combined with the pseudonym issuance protocol can realize the revocation of malicious vehicles.

In Lin et al.'s protocol [7], a centralized method for tracking is adopted. A trace manager (TM) computes a vehicle's private key from a signed message in order to disclose the vehicle's identity. Once TM is compromised, a large amount of privacy information is leaked.

In Schaub et al.'s protocol [14], the secret sharing method for tracking is adopted to prevent misuse and abuse of a system. The method is distributed, but it generally requires a trusted center to distribute secret share in the initialization phase. Therefore, the trusted center will be a secure bottleneck.

In our tracking protocol, all the processes in the secret sharing method adopt a fully distributed structure, such as generation of private key and secret share, generation of modulus N and collaborative tracking. As a result, our tracking protocol avoids a single point of failure.

6. Analysis

6.1. Security Analysis

Proposition 1.

Neither issuing authorities nor other vehicles can determine the relationship between a pseudonym and an identity in the protocol family, so the scheme achieves anonymity.

Proof.

(1) During the issuance stage, PCA gets $c_i=({x_i}^{e_{\text{PCA}}})·\text{SHA}(b_i)\mathrm{mod}{N}_{\text{PCA}}$ . V picks $x_i$ randomly, so PCA cannot get $b_i$ and ${\text{ID}}_{{\text{PV}}_i}$ . Though PCA knows ${\text{ID}}_V$ , it cannot establish the relationship between ${\text{ID}}_V$ and ${\text{ID}}_{{\text{PV}}_i}$ .

(2) Other vehicles get the signed messages and extract ${\text{ID}}_{\text{P}{\text{V}}_i}=(r_i\parallel {r_i}^{d_v}\mathrm{mod}{N}_V\parallel (\text{I}{\text{D}}_{\text{PCA}}\parallel \text{I}{\text{D}}_V\parallel \text{exp}{)}^{d_{\text{PCA}}}\mathrm{mod}{N}_{\text{PCA}}{)}^e\mathrm{mod}N$ . They do not know TAs' private key d and thus cannot obtain V's identity ${\text{ID}}_V$ .

Proposition 2.

The m authorities in TAs can disclose the identity ${ID}_V$ from a pseudonym ${ID}_{PV}$ , so the scheme achieves traceability.

Proof.

Let $\psi =\varphi \mathrm{mod}e={\sum }_{i=1}^k{\varphi }_i\mathrm{mod}e$ , $\zeta =-{\psi }^{-1}\mathrm{mod}e$ , and then $\zeta \varphi +1=-{\varphi }^{-1}\varphi +1=0\mathrm{mod}e$ , indicating $e\mid \zeta \varphi +1$ .

Since $de=\mathrm{1}\mathrm{mod}\varphi$ , this gives $d=(\zeta \varphi +1)/e=({\sum }_{i=1}^k\zeta {\varphi }_i+1)/e$ . Let $d_i=\lfloor \zeta {\varphi }_i/e\rfloor$ ; then

$$\begin{array}{cc}& d={\sum }_{i=\mathrm{1}}^k{d}_i+u\hspace{1em}\left(\mathrm{0}\le u\le k-\mathrm{1}\right).\end{array}$$

(9)

Construct a degree $m-1$ polynomial $c(x)={\sum }_{j=1}^k{c}_j(x)\mathrm{mod}P$ , obviously satisfying $c(0)={\sum }_{j=1}^k{c}_j(0)={\sum }_{j=1}^k{d}_j$ and $c({\text{ID}}_i)={\sum }_{j=1}^k{c}_j({\text{ID}}_i)={\sum }_{j=1}^k{s}_{j,i}=s_i$ . According to the Lagrange interpolation formula ${\sum }_{j=1}^k{d}_j={\sum }_{i=1}^m{s}_i{l}_i(\mathrm{0})\mathrm{mod}P$ , let ${\alpha }_i=s_i{l}_i(0)\mathrm{mod}P$ , so

$$\begin{array}{cc}& {\sum }_{j=\mathrm{1}}^k{d}_j={\sum }_{i=\mathrm{1}}^m{\alpha }_i+xP.\end{array}$$

(10)

Since $0\le {\sum }_{j=1}^k{d}_j<\varphi$ , $0\le {\alpha }_i<P$ , $0\le {\sum }_{i=1}^m{\alpha }_i<mP$ , therefore $-m<x\le 0$ .

Taking the formula (10) into the formula (9), we can obtain the following formula:

$$\begin{array}{cc}& d={\sum }_{i=1}^m{\alpha }_i+xP+u\hspace{1em}\left(0\le u\le k-1,\hspace{0.17em}\hspace{0.17em}-m<x\le 0\right).\end{array}$$

(11)

Consider the issuance protocol and obtain

$$\begin{array}{l}r\parallel r^{d_v}\mathrm{mod}{N}_V\parallel {\left({\text{ID}}_{\text{PCA}}\parallel \text{I}{\text{D}}_V\parallel \text{exp}\right)}^{d_{\text{PCA}}}\mathrm{mod}{N}_{\text{PCA}}\\ \hspace{1em}\hspace{1em}={{\text{ID}}_{\text{PV}}}^d={{\text{ID}}_{\text{PV}}}^{{\sum }_{i=1}^m{\alpha }_i+xP+u}\\ \hspace{1em}\hspace{1em}={{\text{ID}}_{\text{PV}}}^{xP+u}·\prod _{i=1}^m{{\text{ID}}_{\text{PV}}}^{{\alpha }_i}\mathrm{mod}N.\end{array}$$

(12)

Compute $((\text{I}{\text{D}}_{\text{PCA}}\parallel \text{I}{\text{D}}_V\parallel \text{exp}{)}^{d_{\text{PCA}}}{)}^{e_{\text{PCA}}}\mathrm{mod}{N}_{\text{PCA}}$ with $e_{\text{PCA}}$ and obtain V's identity ${\text{ID}}_V$ .

Proposition 3.

Regardless of the PCA, the vehicles and the outside attacker, forging the pseudonym certificate is as difficult as solving a large integer factorization problem.

Proof.

A pseudonym ${\text{ID}}_{\text{P}{\text{V}}_i}$ is coproduced by V and PCA, because $r_i\parallel {r_i}^{d_v}\mathrm{mod}{N}_V$ is provided by V and $(\text{I}{\text{D}}_{\text{PCA}}\parallel \text{I}{\text{D}}_V\parallel \text{exp}{)}^{d_{\text{PCA}}}\mathrm{mod}{N}_{\text{PCA}}$ is provided by PCA.

• (1)

PCA cannot provide $r_i\parallel {r_i}^{d_v}\mathrm{mod}{N}_V$ to forge a pseudonym.

(2)

V cannot provide $(\text{I}{\text{D}}_{\text{PCA}}\parallel \text{I}{\text{D}}_{V^{*}}\parallel \text{exp}{)}^{d_{\text{PCA}}}\mathrm{mod}{N}_{\text{PCA}}$ to forge the pseudonym of $V^{*}$ .

(3)

An external attacker without V's and PCA's private keys cannot pass the authentication, because the issuance protocol is with two-way authentication. Therefore, the attacker neither obtains the blind signature nor personates PCA to sign the pseudonym certificate.

In short, forging an RSA signature or cracking an RSA cipher is as difficult as factorizing a large integer, so the scheme achieves unforgeability.

Proposition 4.

The scheme is robust.

Proof.

(1) The separation of pseudonym issuance authorities and tracking authorities, to some extent, reduces the risk.

(2) Some PCAs are deployed in the model. Once a PCA fails, other PCAs can still provide pseudonym issuance service.

(3) In the pseudonymous authentication protocol, the optimal number of messages with the pseudonym certificates is suggested. It ensures the message authentication probability $P_{\text{auth}}>95\%$ . That means when a message arrives, a vehicle can verify the signature with high probability. Therefore, the protocol not only reduces the communication overhead but also ensures robustness.

(4) During the TAs initialization stage, the generation of modulus N and the generation of the private key and the secret share are distributed fully. So, the scheme does not require a trusted center, and it avoids any single point of failure.

(5) During the TAs operation stage, as long as the number of compromised members is not more than $m-1$ , privacy cannot be leaked.

We further compared our scheme with similar works that are intended to ensure conditional privacy preserving communication [7, 14]. The results of comparisons of security features among our scheme, Lin et al.'s scheme [7], and Schaub et al.'s scheme[14] are shown in Table 1. All the three schemes provide anonymity, traceability, and authentication.

Table 1

Security features comparisons.

	Anonymity	Traceability	Authentication	Unforgeability (especially against authority attacks)	Robustness (especially for tracking)
Lin et al.'s scheme [7]	Yes	Yes	Yes	No	Centralized
Schaub et al.'s scheme [14]	Yes	Yes	Yes	No	Distributed
Our scheme	Yes	Yes	Yes	Yes	Fully distributed

Lin et al.'s scheme is based on a group signature method, in which a member manager (MM) generates member private keys and sends them privately; MM knows all private keys, and it can forge a valid group signature on an arbitrary message. Schaub et al.'s scheme adopts a blind signature method to issue certificates, and thus CA or PP does not know the relationship of an identity and a pseudonym; unfortunately, CA or PP can forge a pseudonym certificate for itself. Therefore, Lin et al. and Schaub et al.'s schemes are not secure against authority forge attacks. In our scheme, a pseudonym is coproduced by a manager and a vehicle; neither PCA nor V is capable of providing complete data to forge a pseudonym; our scheme is unforgeability, especially against authority forge attacks.

As mentioned in Section 5, the tracking methods for Lin et al., Schaub et al. and ours are centralized, distributed, and fully distributed, respectively. Our scheme has better robustness.

6.2. Performance Analysis

6.2.1. Computation Overhead

For convenience to evaluate the computation cost of the protocol, we ignored the computation cost of some operations such as a hash function and a multiplication operation, since they are quite light in terms of load. We focused on some time-consuming operations defined in the following notations.

•  

  $T_P$ : The time of executing a bilinear map operation.

 

  $T_{\text{exp}}$ : The time of executing a modular exponentiation operation in the cyclic group.

 

  $T_e$ : The time of executing RSA encryption or RSA verification.

 

  $T_d$ : The time of executing RSA decryption or RSA signature.

In order to provide the precise comparisons of computation cost, we use the experiment data in [24–26] to evaluate them. The experiment environment is operated on a standard PC, whose processor is Pentium IV with the maximum clock speed of 3 GHz. The pairing system is considered the Tate pairing system. The order of a nonsupersingular curve over a finite field $E(F_p)$ is 160 bits, which is as difficult to break as 1024-bit RSA. In this experiment environment, it requires 4.5 ms to perform a bilinear map operation and 0.6 ms to perform a modular exponentiation operation [25, 26]. It requires 0.2 ms to perform RSA encryption/verification and 4 ms to perform RSA decryption/signature [24].

The results of comparisons of computation cost are shown in Table 2, where n is the number of pseudonym certificates obtained at one time and k is the number of tracking authorities. Some common parameters and secret keys are generated in the system initialization, and for convenience we did not evaluate the computation cost of the initialization in all the three schemes. In Schaub et al.'s scheme and ours, the average computation costs for issuance and tracking are considered.

Table 2

Computation cost comparisons.

	Issuance	Signature and verification	Tracking
Lin et al.'s scheme [7]	$T_{\text{exp}}$	$\mathrm{12}{T}_{\text{exp}}+T_P+\mathrm{12}{T}_{\text{exp}}+2T_P$	$2T_{\text{exp}}$
Schaub et al.'s scheme [14]	$7T_e+4T_d+(T_e+T_d)/n$	$T_e+T_d$	$T_d$
Our scheme	$6T_e+3T_d+3(T_e+T_d)/n$	$T_e+T_d$	$\left(k+1\right)T_d$
Computation time (ms)
Lin et al.'s [7]	0.6	$\mathit{27.9}$	1.2
Schaub et al.'s [14]	$\mathit{17.4}+\mathit{4.2}/n$	$\mathit{4.2}$	4
Ours	$\mathit{13.2}+\mathit{12.6}/n$	$\mathit{4.2}$	$4(k+1)$

Compared with Lin et al.'s scheme, ours and Schaub et al.'s scheme require less computation for signature and verification and more computation for issuance and track. Compared with Schaub et al.'s, our scheme requires less computation for issuance if $n>2$ and more computation for tracking.

6.2.2. Communication Overhead

In Table 3, α is the number of signed messages and λ is the number of signed messages with pseudonym certificate during one pseudonym period in the authentication protocol; m is the threshold value in the distributed tracking protocol. The communication cost of Lin et al.'s scheme is the lowest, but their scheme suffered from the private key revealing attacks, in which MM knows the private key of each member. Schaub et al.'s scheme and ours rely on the blind signature method and achieve vehicular privacy protection in the presence of the authority. Compared with Schaub et al.'s scheme, our scheme is efficient in terms of the communication overhead.

Table 3

Communication cost comparisons.

	Issuance (rounds)	Signed messages (B)	Tracking (B)
Lin et al.'s scheme [7]	1	289	309
Schaub et al.'s scheme [14]	4	1031	$\mathrm{512}+\mathrm{519}/m$
Our scheme	3	235 + 796 $\lambda /\alpha$	$\mathrm{512}+\mathrm{519}/m$

6.2.3. Storage Overhead

In Schaub et al.'s scheme and ours, the storage cost of the vehicle is high because some pseudonym certificates need to be stored; the storage cost of the manager for tracking is very little because an identity can be obtained directly from the pseudonym certificate. On the contrary, the storage cost of the manager in Lin et al.'s scheme is high because the record set $(A_i,{\text{ID}}_i)$ needs to be stored.

7. Conclusions

In this paper, a secure and efficient pseudonym management scheme for vehicular ad hoc networks is proposed. The scheme not only maintains the property of conditional privacy preservation but also provides the advantages in security against authority forge attacks and better robustness. In the scheme, a pseudonym is coproduced by V and PCA to avoid the deception of either party. A blind signature method is used to achieve the separation of issuance and tracking. Based on the improved share generation scheme of the RSA keys, the distributed tracking protocol is proposed to avoid a single point of failure. By searching for the optimal number of messages with a pseudonym certificate, the efficient pseudonym authentication mechanism is given to reduce communication overhead. By uniting the pseudonym issuance protocol and the tracking protocol, malicious vehicles are revoked easily. Moreover, compared with Schaub et al.'s scheme, the communication cost and computation cost in our scheme are lower. As a result, our proposed scheme is suitable for anonymous communication with tracking requirements in VANETs, since it provides security, robustness, and efficiency.

For future research, we will discuss interdependencies of various factors, establish systematic evaluation mechanism of the overall performance, and further enhance the performance.