1. Introduction

Due to the extraordinary commercial and social potential, VANETs have been paid more and more attention. VANETs were first proposed at ITU-T standardization in 2003[1].VANETs are a type of Mobile Ad-hoc Network (MANET) which is the next-generation networking technology to provide communication between vehicles (V2V) or between a vehicle and infrastructure (V2I) using wireless communication. VANETs are aimed to solve problems that traffic congestion and safety etc. In VANETs, moving vehicles send and receive all sorts of messages, such as front brakes, rear-end collision warnings, detailed information of the weather, traffic congestion, and accident rescue information and so on, so that the vehicles on the road can choose a more efficient route and avoid many accidents. However, it would also lead to a threat for the moving vehicle’s privacy when it transmits or receives different types of messages on the road in VANETs, as its communication can be used to link its identity to its physical entity. There are many researches on security and privacy-preserving authentication in VANETs [2]-[4]. Anonymous authentication is one of promising solutions for privacy-preserving scheme, which usually can be achieved by applying pseudonym and group signature [5].

In pseudonym scheme, the real identity of a user can be hidden with the pseudonymous communication. And a Trusted Authority (TA) is required to issue the pseudonym to each member and record the corresponding real identity. In VANETs, many existing authentication schemes apply the pseudonym for anonymity [6]-[10]. However, if a member employs only one pseudonym in VANETs, attackers can obtain the complete route of the member and its ordered services in driving then attackers can deduce the real identity of the member. In [11], Beresford has experimental proved that a single pseudonym cannot meet privacy-preserving because attackers are able to trace the public information of users. Therefore, pseudonym should be updated at regular intervals [12]-[14]. However, with the increase of vehicles, the management and maintenance of pseudonym would be a bottleneck of anonymous authentication in VANETs, and regular replacement of pseudonym would effect on routing efficiency and increase packet loss.

Group signature means that each group member is capable of signing messages representing the group, and anyone can authenticate the signed messages with the group public key while the verifier cannot determine which group member is the signer. Moreover, if there is a dispute, group manager can identify the signer. Group signatures are widely used in VANETs to realize anonymous authentication with privacy-preserving authentication [15]-[19]. In order to improve the efficiency of schemes based on group signatures in VANETs, a great quantity of researches have been proposed[20]-[28]. In VANETs, Road Side Units (RSUs) generate groups within their ambit. Owing to the frequent and high speed joining and leaving of vehicles in VANETs, the schemes based on group signatures in VANETs should be able to achieve efficient joining and revocation of group members. In addition, efficient joining has been achieved in most existing schemes [15]-[28], in which RSUs generate key pairs for the new group member and broadcast a new group public key. However, efficient revocation is still a difficult problem for the existing schemes [15],[16],[24]-[27]. In existing schemes based on group signatures in VANETs[16],[24],[26],[27], the key pairs of other group members will be influenced when a member quits the group, which makes excessive traffic load and does not meet the requirements of dynamic VANETs. In this paper, an efficient revocable group signature scheme in VANETs is proposed. If there is a revocation in the group, the key pairs of unrevoked group members are not influenced, and the key pair and certificate of the revoked member are no longer valid. Furthermore, the proposed scheme keeps the forward and backward security, and it is anti-collusion.

The remainder of paper is organized as follows: Section 2 gives system model and preliminaries of this paper. Section 3 describes the proposed scheme in detail. Section 4 presents security analysis of the scheme and the comparison with the other two revocable schemes. Section 5 makes a conclusion.

 

2. SYSTEM MODEL AND PRELIMINARIES

2.1 System Model

In this paper, the system model of VANETs consists of a GTA, LTAs, fixed RSUs at the road side, and mobile BVs equipped in vehicles, as shown in Fig. 1.

Fig. 1.System Model of VANETs

2.2 Chinese Remainder Theorem

If p1,p2,⋯,pk are pairwise coprime, where k ≥ 2, set P = p1p2⋯pk = p1P1 = p2P2 = ⋯ = pkPk, where . Then the positive integer value of the congruence equations (1) is , where is positive integer and meets the congruence equation , i = 1,2,⋯,k .

2.3 Hash Function

Hash function is defined as h : {0,1}* → {0,1}n , where {0,1}* denotes a bit string of arbitrary length, {0,1}n indicates a string of length with n. A one-way hash function is considered to be secure if it satisfies the following properties.

2.4 Bilinear Parings

In this paper, the properties of the bilinear operation are defined as follows: G1 represents an additive cyclic group with order q, G2 represents a multiplicative cyclic group with the same order, e:G1×G1→G2 is a bilinear map, which meets the following requirements:

2.5 Notations

There are some symbols mentioned below as Table 1.

Table 1.Symbols and Meaning

 

3. PROPOSED SCHEME

3.1. Initialization

(1) Above all, GTA generates its own public/private key pair making use of RSA algorithm. According to RSA algorithm, GTA chooses

Then GTA computes d as its private key, which satisfies e ⋅ d ≡ 1(modϕ(n)) .

GTA publishes the public parameters (e, n) , and keeps (b, c, d) secret.

(2) GTA generates parameters for LTAs using RSA algorithm. For LTAi , where 1 ≤ i ≤ I , GTA chooses

GTA computes di as the private key of LTAi, which satisfies ei ⋅ di ≡ 1(modϕ(ni)) .

Then GTA safely sends the parameters to LTAi. LTAi publishes (ei,ni,gi) as its public parameters, and secretly save the tuple (bi,ci,di) .

(3) LTA generates key pairs for RSUs using RSA algorithm. For RSUi, where 1 ≤ i ≤ J , LTA chooses

Then LTA computes vi as the private key of RSUi, which satisfies ui⋅vi ≡ 1(modϕ(mi)) .

After receiving of these parameters, RSUi publishes its public parameters (ui,mi), and keeps (si,ti,vi) secret.

3.2. Registration

Before accessing to VANETs, a user should register at the LTA which it belongs to for getting a blind certificate, which will be submitted to RSUs to prove its legitimacy without disclosing its real identity. In reality, ID cards are used to complete registration. ID-based restrictive partially blind signature technique [29] had been combined to generate permit in [30]. In this paper, we also adopt the permit to generate blind certificates as Fig. 2. Suppose the BV registers at LTA1. LTA1 chooses 3 random generators R, R1, R2 ∈ G1 .

Fig. 2.Certificate Generation

(1) BV randomly generates a number ξBV and computes M = ABV = ξBVR1 + R2 , ρ = e(R, QLTA1) , ρ1 = e(R1, QLTA1) , ρ2 = e(R2, QLTA1) and y = e(Ppub, QLTA1) . Then BV sends IDBV,M,T1,SIGΓBV(H1(IDBV∥M∥T1)) to LTA1.

(2) LTA1 randomly chooses Q ∈ G1 and r ∈ , and computes z = e(M,ΓLTA1) , a = e(R,Q), δ = e(M,Q) , U=rR and Y = rQLTA1 . Then LTA1 sends z, a, δ, U, Y, T2, HMACk1(z∥a∥δ∥U∥Y∥T2) to BV.

(3) BV randomly chooses α,β,γ,λ,μ,σ,u,v ∈ , and computes M' = αM , A = e(M',QLTA1) , , δ' = δuαAν , z'=zα , a'=auρν , Y' = λY + λμQLTA1 - γH1(j) , U' = λU + γPpub , l = λ-1H2(M',Y',U',A,B,z',a',δ')+ μ, j' = lu and k1 = e(ΓBV,QLTA1) . Then BV sends l,T3,HMACk1(l∥T3) to LTA1.

(4) LTA computes S1 = Q+lΓLTA1 , S2 = (r+l)ΓLTA1 + rH1(j) and sends S1,S2,T4,HMACk1(S1∥S2∥T4) to BV.

(5) If the equations hold with e(R,S1) = ayl, e(M,S1) = δzl , BV computes , . The restrictive partially blind signature on (M', j) is and the requested blind certificate is , where B will be used in the verification of the certificate.

The blind certificates can protect the privacy of users and prevent the users’ real identity from revealing on the move. Thus a secure drive is successfully established for users in terms of communication.

The scheme defines j to be the expiration time of the certificates, Ti to be a precise timestamp for preventing replay attack.

3.3. Groups Establishment

RSUs establish groups consisting of BVs in their corresponding area. In this paper, Chinese remainder theorem is utilized to generate group public keys. Upon the public keys of group members, a RSU generates a group public key. Any user can authenticate signed messages with the group public key. If there is a join or quit for users, RSU will update the group public key using Chinese remainder theorem. Moreover, RSU need not to change the key pairs of other unchanged efficient group members when RSU adds or deletes a member in the group. That is, whether there is a join or quit, the key pairs of old members in the group are unaffected. For greater security, Schnorr signature algorithm is applied in this paper. As a result, it is high-speed on updating in groups and secure on protecting the privacy of users.

It is assumed that the establishment occurs at RSU1 and there are s vehicle users in the original time.

(1) RSU1: User Vi submits its request and blind certificate to RSU1, where 1 ≤ i ≤ s . That is, there are s vehicles and Vi represents the ith member. RSU1 verifies the validity of the blind certificate above all. The verification process is as Fig. 3.

Fig. 3.Certificate Authentication

If the certificate is valid and not expired, the verification is successful. Therefore, RSU1 allows Vi joining to the group and stores its blind certificate into database, 1 ≤ i ≤ s .

(2) RSU1 → Vi : After confirming the validity of the presented certificate, RSU1 generates key materials for vehicle user Vi based on Schonorr signature algorithm. RSU1 randomly selects primes pi, qi, where qi | pi−1, pi ≥ 2512 , qi ≥ 2160 , and pi ≥ g1, g1 is the identity code of LTA1. After which, RSU1 sends the tuple to Vi in a secure environment, where v1 is the private key of RSU1.

(3) Vi : After receiving the parameters from RSU1, Vi primarily verifies its legality. If the equations , are satisfied, Vi believes the parameters are valid and produced by RSU1, where u1 is the public key of RSU1, m1 is the public parameter of RSU1. Vi will product its own public/private key pair employing the key materials as step (4).

(4) Vi → RSU1 : Vi randomly selects as its private key, and computes as its public key. Then, Vi sends yi to RSU1 via a secure channel, such as a Secure Socket Layer.

(5) RSU1 : RSU1 reserves the public key of all group members with their corresponding blind certificate in database and public Table 2.

Table 2.The Public Keys of the Existing Group Members

For member Vi, RSU1 transmits (yi, certification) to LTA1 via a secure channel. LTA1 stores (yi, certification) in its reserve.

(6) RSU1 generates the group public key. Taking advantage of the obtained public keys of s members, RSU1 computes the group key according to the congruence equations (2).

The value to the equations (2) is , where P = p1p2⋯ps = p1P1 = p2P2 =⋯= psPs, , i = 1,2,⋯,s and is positive integer and satisfies the congruence equation , i = 1,2,⋯,s. Here c is the group public key. Then RSU1 chooses a secure hash function h , and publishes (g1, m1, u1, c, h) .

When member Vi is willing to broadcast a message, Vi will sign the message M as 3.4.

3.4. Signature

For greater security, this paper uses Schnorr signature algorithm [31] to sign messages. If Vk wants to sign a message M, Vk will sign it by using Schnorr signature algorithm. Vk randomly chooses and computes , π = h(f∥M) , ζ = ω − xkπ(mod qk), where g1 is the identity code of LTA1, xk is the private key of Vk , pk , qk are the primes chosen by RSU1 for Vk . Then, (π, ζ, pk) is the signature of Vk on M .

3.5. Verification

Anyone else can verify the signed message with the signature (π, ζ, pk) and the group public key (g1, m1, u1, c, h) as Algorithm 1.

3.6. Joining

It is supposed that vehicle user Vs+1 wants to join to the group of RSU1. Vs+1 performs the following steps to join the group.

(1) Vs+1 submits its accession request and blind certificate to RSU1. RSU1 verifies the validity of Vs+1 using Fig. 3. For eligible Vs+1, RSU1 generates key parameters for Vs+1. Based on Schnorr signature algorithm, RSU1 randomly selects primes ps+1,qs+1, where qs+1|ps+1−1, ps+1 ≥ 2512,qs+1 ≥ 2160 , and ps+1 ≥ g1 . Then, RSU1 sends to Vs+1 via a secure channel.

(2) Vs+1 verifies the legality of the received parameters. If the equations (3) hold, Vk believes the parameters are valid and produced by RSU1.

Then Vs+1 randomly chooses as its private key, and computes as its public key. And Vs+1 sends ys+1 to RSU1 via a secure channel.

(3) RSU1 reserves ys+1 with its corresponding certificate in database and updates Table 2 to Table 3.

Table 3.The Public Keys of the Existing Group Members

Then RSU1 securely transmits (ys+1, certification) to LTA1. LTA1 stores (ys+1, certification) in its reserve.

(4) RSU1 computes the new group key according to the congruence equations (4).

the value to the equations (4) is , where Pnew = p1p2⋯psps+1 = Pps+1. The value of Pinew and can be calculated by using Algorithm 2, where 1 ≤ i ≤ s+1.

Thereby, cnew is the new group public key. But if c ≡ cnew(mod Pnew) , RSU1 returns to step (1) to generate key parameters again for user. Finally RSU1 publishes (g1, m1, u1, cnew, h) .

3.7 Revocation

Assume that Vk represents an arbitrary group member and there are s members in the group. If the vehicle user Vk (1 ≤ k ≤ s) wants to quit the group, Vk only needs to transmit the quit request to RSU1. And RSU1 changes the public key of Vk in the database to compute a new group public key c' . Substituting for yk , RSU1 computes the new group public key according to the congruence equations (5).

For equations (5), the value is , where ≡ yk (mod pk) should not hold. Then RSU1 updates Table 3 to Table 4.

Table 4.The Public Keys of the Existing Group Members

By the above steps, there is only one change for computing the new group public key that yk is altered in calculation formula, where c' is the new group public key after the revocation of Vk.

After the revocation, both c' ≡ yk(mod pk) and π = h(f || M) will not hold, then the messages signed by Vk will no longer be verified to be legal.

In the revocation, the keys of unrevoked group members do not need to update.

3.8 Opening

Assume that users find there are something false or malicious in messages which is signed by Vk, they can combine to submit an open application with the message (π, ζ, pk, M) to RSU1. There should be a specific number of users in reality, which is a measure of whether RSU1 will accept the application.

With enough users, RSU1 accept the application and compute the public key yk of Vk by c ≡ yk(mod pk). Then, RSU1 searches its database to find the corresponding blind certificate of Vk and submits (application, certificate) to LTA1.

LTA1 firstly checks the open application. Then LTA1 retrieves its database to find the real identity of Vk by search its certificate. In reality, there are different punishments for this case according to different policies in each area.

 

4. SECURITY AND PERFORMANCE ANALYSIS

4.1 Security Analysis

Anonymity. Due to the application of restrictive partially blind signature technique in the generation of blind certificates, attackers cannot deduce the real identity of BVs from the blind certificate[30]. Further, blind certificates of BV update regularly, thus attackers are not able to track a specific blind certificate. Moreover, since the key pairs of group members are not related to their real identity, it is also impossible for attackers to obtain the identity information of members.

Integrity. Since the signature is generated by Schnorr signature algorithm, and the Schnorr signature scheme has been known to be provably secure in the Random Oracle Model[31],[32], the integrity of messages is guaranteed.

Traceability. In dispute cases, LTAs are able to trace the real identity of BVi. RSU transmits the public key and the blind certificate of BVi to the corresponding LTA. Then LTA retrieves its database and find out the real identity of BVi.

Unforgeability. By unforgeability meant that a signed message proved to be generated by Vk can only be generated by Vk. In our scheme, if a vehicle user Vj receives a signed message (π, ζ, pk, M) with the group public parameters (g1, m1, u1, c, h), Vj will firstly compute the public key yk of Vk by using equation c ≡ yk(mod pk). Then Vj computes and checks whether the equation π = h(f || M) holds or not, if holds, Vj believes the message is signed by Vk, otherwise abandons the message.

Since pk is a public parameter of Vk and c is also pubic, the public key yk of Vk obtained by equation c ≡ yk(mod pk) is unique.

If an attacker Eve attends to forge a signature (π', ζ', pk, M') of Vk, Eve randomly chooses and computes , π' = h(f',M') , , where . However, is necessary to compute ζ' , and should meet . Since the discrete logarithm problem, Eve cannot forge a signature of Vk.

Nonrepudiation. By nonrepudiation meant that Vk cannot deny its own signed messages. Since the signed messages are unforgeable, and the public key yk of Vk can be computed by c ≡ yk(mod pk) for all the valid messages signed by Vk, Vk cannot deny its own signed messages.

Forward security. If a user Vs+1 joins to the group, its public/private key pair ys+1/xs+1 are generated by the public parameters, where . Moreover, the group public key is changed from c to cnew by equations (6).

It is necessary that the forward security should be protected, that is, messages signed by a new group member should not be verified to be legal with the old group public key. If the messages are verified to be valid, the congruence equation c ≡ ys+1(mod ps+1) also holds, so that the congruence equation c ≡ cnew(mod pnew) should hold. In section 3.6, there is the restriction on the new group public key that the equation c ≡ cnew(mod pnew) should not hold. Therefore, in proposed scheme, the forward security is guaranteed.

Backward Security. After the revocation of vehicle Vk, the group public key is refreshed from c to c' by using equations (7).

In order to satisfy backward security, the messages signed by revoked members should not be legal for the new group public key. If the messages can be verified to be legal, there are two scenarios. The congruence equation c' ≡ yk(mod pk) holds that the revoked member is still able to sign messages with its old private key xk . Or the revoked member can obtain which meets the equation that the revoked member can sign messages with the private key . If the congruence equation c' ≡ yk(mod pk) holds, then the congruence equation ≡ yk (mod pk) holds, while a significant restriction on is that the equation ≡ yk (mod pk) should not holds. The revoked member still can obtain the new group public key c' and compute c' ≡ (mod pk) to get . If the revoked member can obtain which meets the equation , then the member can solve the discrete logarithm problem.

In conclusion, the backward security of the proposed scheme is guaranteed.

Anti-collusion. By anti-collusion meant that several group members can together forge a signed message (π',ζ',pk,M') by an existing group member or generate a valid signed message (π",ζ",p',M").

As mentioned in unforgeability, group members will solve the discrete logarithm problem if they can forge a signed message of an existing group member.

Suppose that there are s group members V1, V2,⋯, Vs and the group public key is c. For Vi, , where 1 ≤ i ≤ s . If V1, V2,⋯, Vm wants to generate a new valid signed message (π",ζ",p',M"), it is necessary to get parameters y' and x' , where . Each verifier needs to compute y' by using c ≡ y'(mod p') and then check whether y' is in the table of the existing group member’s public keys, hence y' should be able to equal to one of yi , where 1 ≤ i ≤ s . Then, if V1, V2,⋯, Vm can forge a signed message successfully, they can forge a signed message of an existing group member, accordingly they can solve the discrete logarithm problem.

4.2 Performance Analysis

Function. In this section, a comparison of function between our scheme and some other group signature schemes in VANETs is made as Table 5.

Table 5.Comparison of Function

Computation. In this section, we analyze the performance of the proposed scheme in terms of computational loads.

Table 6 gives the test time for the involved cryptography operations [33]. The experiments are conducted on a computer with Intel i5-3210 -2.5GHz CPU and 4-GB RAM.

Table 6.Execution Time for Operations

In the proposed scheme, if a member Vk quits the group, RSU only needs to substitute for yk as the equations (5), and calculate the new group public key while key pairs of other group members are not influenced. The revocation costs 2 addition, 2 multiplication, 2 modular arithmetic to calculate the new group public key. Since for CPU modular arithmetic is more efficient than multiplication, we assume that execution time for modular arithmetic is TMu as multiplication. Hence the computational load is 2TAd+4TMu.

A comparison between the proposed scheme and two other revocable schemes [26],[28] is made on the revocation complexity of a group member, respectively. Here we assume that there are ngr members in the group.

In [26], RSU can revoke a member xj by broadcasting a revocation list RL, and upon receiving a RL, each unrevoked member updates its parameters accordingly. There are 1 addition, 1 division and 1 exponentiation on each unrevoked member for RSU, and 3 addition, 1 inverse operation, 2 multiplication, 3 division and 4 exponentiation for each unrevoked member. Since for CPU division is as efficient as multiplication, the total computational load of this scheme is (4TAd+TIn+6TMu+5TEx)(ngr-1).

In [28], if a member leaves the group, RSU needs to update credential element and publish the corresponding public key parameters for each unrevoked member. There are 1 addition, 1 multiplication, 1 division and 2 exponentiation for RSU on each unrevoked member, and 1 multiplication, 2 exponentiation and 1 pairing operation for each unrevoked member. The total computational load of this scheme is (TAd+3TMu+4TEx+Tp)(ngr-1).

We compare the revocation computational load of a group member in this scheme with [26] and [28] in Table 7.

Table 7.Comparison on Revocation Computational Load of a Group Member

As shown in Table 7, regardless of the quantity of group members, the revocation computational load is a constant in the proposed scheme which has lower computational load than the other two schemes. The comparison between our scheme and the two schemes on total computational load, computational load for each unrevoked member and computational load for RSU are shown in Fig. 4, Fig. 5 and Fig. 6, respectively.

Fig. 4.Comparison of Total Computational Load

Fig. 5.Comparison of Computational Load for Each Unrevoked Member

Fig. 6.Comparison of Computational Load for RSU

 

5. CONCLUSION

In this paper, an efficient revocable group signature scheme in VANETs is proposed. When a member quits the group, RSU only needs to compute 1 module arithmetic to compute the new group public key. On the security analysis, our scheme keeps the forward and backward security. Furthermore, our scheme has a lower computation load. Owing to the frequent and high speed joining and leaving of vehicles in VANETs, this scheme with the property of efficient revocation is suitable for the dynamic VANETs. Moreover, the scheme is suitable for most dynamic scenes.