# An efficient revocable group signature scheme in vehicular ad hoc networks.

1. IntroductionDue 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.

* GTA is a general trusted agency of VANETs. It provides management and generates public/private key pairs for LTAs. As usual, GTA is assumed as powerful enough in terms of communication, computation, and storage capability, and it is unworkable to compromise to any adversary.

* LTAs are local trusted agencies. Suppose that there are I LTAs in the jurisdictional limits of GTA. LTAs generate public/private key pairs for RSUs. In addition, BVs register at the LTA which they belong to before joining VANETs. LTAs issue blind certificates to legal BVs. Then, LTAs are also assumed as powerful enough for communication, computation, and storage capability, and they are infeasible to compromise to any adversary.

* RSUs work as the group manager in groups consisting of BVs. Assume that there are J RSUs in the jurisdictional limits of a LTA. RSUs generate the group public key and update it if there is a join or quit of BVs. They are also responsible for distributing public key materials to BVs in the groups. In this paper, RSUs are assumed to be semi-trust, which means honest but curious, honest for performing operation but curious about real identities of BVs.

* BVs represent vehicle users. They register at the LTA which they attribute to before joining VANETs. They are able to broadcast and receive signed messages in groups. Each vehicle is assumed to have a tamper-proof device (TPD) to store security-related materials. In this paper, it is supposed that each vehicle is uniquely identified by its battery.

2.2 Chinese Remainder Theorem

If [p.sub.1], [p.sub.2], ..., [p.sub.k] are pairwise coprime, where k [greater than or equal to] 2, set P = [p.sub.1][p.sub.2] ... [p.sub.k] = [p.sub.1][P.sub.1] = [p.sub.2][P.sub.2] = = [p.sub.k][P.sub.k], where [P.sub.i] = P/[p.sub.i], i = 1,2, ..., k. Then the positive integer value of the congruence equations (1) is c [equivalent to] [k.summation over (i=1)][y.sub.i] [P.sub.i][P.sub.i] [equivalent to] [y.sub.1][P'.sub.1][P.sub.1] + [y.sub.2][P'.sub.2][P.sub.2] + ... + [y.sub.k][P'.sub.k][P.sub.k] (mod P), where [P'.sub.i] is positive integer and meets the congruence equation [P'.sub.i][P.sub.i] [equivalent to] 1(mod [p.sub.i]), i = 1,2, ..., k.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

2.3 Hash Function

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

(1) Given X, it is easy to calculate h(x) = y. While conversely, given y = h(x), it is hard to compute x.

(2) Given x, it is computationally unworkable to find x [not equal to] x' such that h(x') = h(x).

2.4 Bilinear Parings

In this paper, the properties of the bilinear operation are defined as follows: [G.sub.1] represents an additive cyclic group with order q, [G.sub.2] represents a multiplicative cyclic group with the same order, e: [G.sub.1] x [G.sub.1] [right arrow] [G.sub.2] is a bilinear map, which meets the following requirements:

(1) Bilinearity: [for all]R, S, T [member of] [G.sub.1], there are e(R, S + T) = e(R, S) e(R, T), e(R + S, T) = e(R, T )e(S, T);

(2) Nondegenerative: [there exists]R, S [member of] [G.sub.1], satisfies e(R, S) [not equal to] 1;

(3) Computability: [for all]R, S [member of] [G.sub.1], e(R, S) is computable in polynomial time.

2.5 Notations

There are some symbols mentioned below as Table 1.

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

* random primes b, c such that b [greater than or equal to] [2.sup.512], c [greater than or equal to] [2.sup.512], let n = b x c;

* a random number e < [phi](n) as its own public key, where [phi](n) = (b -1) x (c - 1), and gcd(e, [phi](n)) = 1;

Then GTA computes d as its private key, which satisfies e x d [equivalent to] 1(mod ([phi](n)).

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

(2) GTA generates parameters for LTAs using RSA algorithm. For [LTA.sub.i], where 1 [less than or equal to] i [less than or equal to] I, GTA chooses

* random primes [b.sub.i], [c.sub.i] such that [b.sub.i] [greater than or equal to] [2.sup.512], [c.sub.i] [greater than or equal to] [2.sup.512], let [n.sub.i] = [b.sub.i] x [c.sub.i];

* a random number [e.sub.i] < [phi]([n.sub.i]) as the public key of [LTA.sub.i], where [phi]([n.sub.i]) = ([b.sub.i] - 1) x ([c.sub.i] - 1), and gcd([e.sub.i], [phi]([n.sub.i])) = 1;

* a random number [g.sub.i] as the identity code of [LTA.sub.i];

GTA computes [d.sub.i] as the private key of [LTA.sub.i], which satisfies [e.sub.i] x [d.sub.i] [equivalent to] 1(mod [phi]([n.sub.i])).

Then GTA safely sends the parameters to [LTA.sub.i]. [LTA.sub.i] publishes ([e.sub.i], [n.sub.i], [g.sub.i]) as its public parameters, and secretly save the tuple ([b.sub.i], [c.sub.i], [d.sub.i]).

(3) LTA generates key pairs for RSUs using RSA algorithm. For [RSU.sub.i], where 1 [less than or equal to] i [less than or equal to] J, LTA chooses

* random primes [s.sub.i], [t.sub.i] such that [s.sub.i] [greater than or equal to] [2.sup.512], [t.sub.i] [greater than or equal to] [2.sup.512], let [m.sub.i] = [s.sub.i] x [t.sub.i];

* a random number [u.sub.i] < [phi]([m.sub.i]) as the public key of [RSU.sub.i], where [phi]([m.sub.i]) = ([s.sub.i] - 1) x ([t.sub.i] - 1), and gcd([u.sub.i], [phi]([m.sub.i])) = 1;

Then LTA computes [v.sub.i] as the private key of [RSU.sub.i], which satisfies [u.sub.i] x [v.sub.i] [equivalent to] 1 (mod [phi]([m.sub.i])). After receiving of these parameters, [RSU.sub.i] publishes its public parameters ([u.sub.i], [m.sub.i]), and keeps ([s.sub.i], [t.sub.i], [v.sub.i]) 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 [LTA.sub.1]. [LTA.sub.1] chooses 3 random generators R, [R.sub.1], [R.sub.2] [member of] [G.sub.1].

(1) BV randomly generates a number [[xi].sub.BV] and computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then BV sends [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to [LTA.sub.1].

(2) [LTA.sub.1] randomly chooses Q [member of] [G.sub.1] and r [member of] [Z.sup.*.sub.q], and computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then LTA, sends z, a, [delta], U, Y, [T.sub.2]. [HMAC.sub.k1](z[parallel]a[parallel][delta][parallel]U[parallel]Y[parallel][T.sub.2]) to BV.

(3) BV randomly chooses [alpha], [beta], [gamma], [lambda], [mu], [sigma], u, v [member of] [Z.sup.*.sub.q], and computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then BV sends l, [T.sub.3], [HMAC.sub.k1](l [parallel][T.sub.3]) to [LTA.sub.1].

(4) LTA computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sends [S.sub.1], [S.sub.2], [T.sub.4], [HMAC.sub.k1]([S.sub.1][parallel][S.sub.2][parallel][T.sub.4]) to BV.

(5) If the equations hold with e(R, [S.sub.1]) = a[y.sup.1], e(M, [S.sub.1]) = [delta][z.sup.1], BV computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The restrictive partially blind signature on (M', j) is (Y', U', z', j', [S'.sub.1], [S'.sub.2]) and the requested blind certificate is {(M', j), (Y', U', z', j', [S'.sub.1], [S'.sub.2]), B}, 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, [T.sub.i] 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 [RSU.sub.i] and there are s vehicle users in the original time.

(1) [RSU.sub.1]: User [V.sub.i] submits its request and blind certificate to [RSU.sub.1], where 1 [less than or equal to] i [less than or equal to] s. That is, there are s vehicles and [V.sub.i] represents the ith member. [RSU.sub.1] verifies the validity of the blind certificate above all. The verification process is as Fig. 3.

(1.1) BV sends certificate, [T.sub.6], [HMAC.sub.k2](certificate[parallel][T.sub.6]) to [RSU.sub.1].

(1.2) [RSU.sub.1] computes A = e{M', [Q.sub.LTA1]). If A [not equal to] O, computes i = [H.sub.4](A, B, [Q.sub.RSU1], time), where time is the binary representation of the current time. [RSU.sub.1] sends the challenge i to BV.

(1.3) BV computes [r.sub.1] = i([[xi].sub.x][alpha]) + [beta] and [r.sub.2] = i[alpha] + [sigma]. Then BV sends [r.sub.1], [r.sub.2] to [RSU.sub.i].

(1.4) [RSU.sub.1] computes a' = e(P, [S'.sub.1])[y.sup.-j'] and [delta]' = e(M', [S'.sub.1])[z'.sup.-j']. The signature is valid if e([S.sub.2], R) = e(Y' + [H.sub.3](M', Y', U', A, z', a', [delta]')[Q.sub.LTA1], [P.sub.pub]) x e([H.sub.1](j), U') holds. [RSU.sub.i] accepts this certificate if and only if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If the certificate is valid and not expired, the verification is successful. Therefore, [RSU.sub.1] allows [V.sub.i] joining to the group and stores its blind certificate into database, 1 [less than or equal to] i [less than or equal to] s.

(2) [RSU.sub.1] [right arrow] [V.sub.i]: After confirming the validity of the presented certificate, [RSU.sub.1] generates key materials for vehicle user [V.sub.i] based on Schonorr signature algorithm. [RSU.sub.1] randomly selects primes [p.sub.i], [q.sub.i], where [q.sub.i]|[p.sub.i] - 1, [p.sub.i] [greater than or equal to] [2.sup.512], [q.sub.i] [greater than or equal to] [2.sup.160], and [p.sub.i] [greater than or equal to] [g.sub.1], [g.sub.1] is the identity code of [LTA.sub.1]. After which, RSU1 sends the tuple [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to [V.sub.i] in a secure environment, where [v.sub.1] is the private key of RSU1.

(3) [V.sub.i]: After receiving the parameters from [RSU.sub.1], [V.sub.i] primarily verifies its legality. If the equations [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are satisfied, [V.sub.i] believes the parameters are valid and produced by [RSU.sub.1], where [u.sub.1] is the public key of [RSU.sub.1], [m.sub.1] is the public parameter of [RSU.sub.1]. [V.sub.i] will product its own public/private key pair employing the key materials as step (4).

(4) [V.sub.i] [right arrow] [RSU.sub.1]: [V.sub.i] randomly selects [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as its private key, and computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as its public key. Then, [V.sub.i] sends [y.sub.i] to [RSU.sub.1] via a secure channel, such as a Secure Socket Layer.

(5) [RSU.sub.1]: [RSU.sub.1] reserves the public key of all group members with their corresponding blind certificate in database and public Table 2.

For member [V.sub.i], [RSU.sub.1] transmits ([y.sub.i], certification) to [LTA.sub.1] via a secure channel. [LTA.sub.1] stores ([y.sub.i], certification) in its reserve.

(6) [RSU.sub.1] generates the group public key. Taking advantage of the obtained public keys of s members, [RSU.sub.1] computes the group key according to the congruence equations (2).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

The value to the equations (2) is c [equivalent to] [s.summation over (i=1)] [y.sub.i][P.sub.i][P'.sub.i] (mod P), where P = [p.sub.1][p.sub.2] ... [p.sub.s = [p.sub.1][P.sub.1] = [p.sub.2][P.sub.2] = ... = [p.sub.s][P.sub.s], [P.sub.i] = P/[p.sub.i], i = 1, 2, ..., s and [P'.sub.i] is positive integer and satisfies the congruence equation [P'.sub.i][P.sub.i] [equivalent to] 1(mod [p.sub.i]), i = 1, 2, ..., s. Here c is the group public key. Then [RSU.sub.1] chooses a secure hash function h, and publishes ([g.sub.1], [m.sub.1], [u.sub.1], c, h).

When member [V.sub.i] is willing to broadcast a message, [V.sub.i] 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. [V.sub.k] randomly chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and computes f = [g.sup.[omega].sub.1] (mod [p.sub.k]), [pi] = h(f[parallel]M), [zeta] = [omega] - [x.sub.k][pi] (mod [q.sub.k]), where [g.sub.1] is the identity code of [LTA.sub.1], [x.sub.k] is the private key of [V.sub.k], [p.sub.k], [q.sub.k] are the primes chosen by [RSU.sub.1] for [V.sub.k]. Then, ([pi], [zeta], [p.sub.k]) is the signature of [V.sub.k] on M.

3.5. Verification

Anyone else can verify the signed message with the signature ([pi], [zeta], [p.sub.k]) and the group public key ([g.sub.1], [m.sub.1], [u.sub.1], c, h) as Algorithm 1.

Algorithm 1: Message authentication algorithm for any verifier Require: ([pi], [zeta], [p.sub.k]), ([g.sub.1], [m.sub.1], [u.sub.1], c, h) 1: Computes c [equivalent to] [y.sub.k] (mod [p.sub.k]) and obtains the public key [y.sub.k] of [V.sub.k]. 2: Check whether the obtained public key [y.sub.k] is in Table 2, if [y.sub.k] is in the Table 2, go to step 3. 3: Computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. 4: if the equation [pi] = h(f'[parallel]M) holds, then accept the message is signed by [V.sub.k] and opens the message. 5: end if

3.6. Joining

It is supposed that vehicle user [V.sub.s+1] wants to join to the group of [RSU.sub.1]. [V.sub.s+1] performs the following steps to join the group.

(1) [V.sub.s+1] submits its accession request and blind certificate to [RSU.sub.1]. [RSU.sub.1] verifies the validity of [V.sub.s+1] using Fig. 3. For eligible [V.sub.s+1], [RSU.sub.1] generates key parameters for [V.sub.s+1]. Based on Schnorr signature algorithm, [RSU.sub.1] randomly selects primes [p.sub.s+1], [q.sub.s+1], where [q.sub.s+1]|[p.sub.s+1] -1, [p.sub.s+1] [greater than or equal to] [2.sup.512], [q.sub.s+1] [greater than or equal to] [2.sup.160], and [p.sub.s+1] [greater than or equal to] [g.sub.1]. Then, [RSU.sub.1] sends [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to [V.sub.s+1] via a secure channel.

(2) [V.sub.s+1] verifies the legality of the received parameters. If the equations (3) hold, [V.sub.k] believes the parameters are valid and produced by [RSU.sub.1].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

Then [V.sub.s+1] randomly chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as its private key, and computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as its public key. And [V.sub.s+1] sends [y.sub.s+1] to [RSU.sub.1] via a secure channel.

(3) [RSU.sub.1] reserves [y.sub.s+1] with its corresponding certificate in database and updates Table 2 to Table 3.

Then [RSU.sub.1] securely transmits ([y.sub.s+1], certification) to [LTA.sub.1]. [LTA.sub.1] stores ([y.sub.s+1], certification) in its reserve.

(4) [RSU.sub.1] computes the new group key according to the congruence equations (4).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

the value to the equations (4) is [c.sub.new] [equivalent to] [s+1.summation over (i=1)] [y.sub.i][P.sub.i new][P'.sub.i new](mod [P.sub.new]), where [P.sub.new] = [p.sub.1][p.sub.2] ... [p.sub.s][p.sub.s+1] = P[p.sub.s+1]. The value of [P.sub.inew] and [P'.sub.i new] can be calculated by using Algorithm 2, where 1 [less than or equal to] i [less than or equal to] s + 1.

Algorithm 2: The process of calculating [P.sub.inew] and [P'.sub.inew]. Require: [P.sub.i], [P'.sub.i], [p.sub.i] (1 [less than or equal to] i [less than or equal to] s + 1) 1: if 1 [less than or equal to] i [less than or equal to] s then compute [P.sub.i new] = [P.sub.i][p.sub.s+1], [P'.sub.inew] = [P'.sub.i][p.sup.-1.sub.s+1], where [p.sub.s+1][p.sup.-1.sub.s+1] [equivalent to] 1(mod [p.sub.i]), since [P'.sub.inew][P.sub.inew] [equivalent to] 1(mod [p.sub.i]) and [P.sub.i][P'.sub.i] [equivalent to] l(mod [p.sub.i]). 2: if i = s + R then impute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [P'.sub.(s+1)new] [equivalent to] [P.sup.-1.sub.(s+1)new] (mod [p.sub.s+1]). 3 : Output: [P.sub.inew] and [P'.sub.inew] (1 [less than or equal to] i [less than or equal to] s + 1)

Thereby, [c.sub.new] is the new group public key. But if c [equivalent to] [c.sub.new] (mod [P.sub.new]), [RSU.sub.1] returns to step (1) to generate key parameters again for user. Finally [RSU.sub.1] publishes ([g.sub.1], [m.sub.1], [u.sub.1], [c.sub.new], h).

3.7 Revocation

Assume that [V.sub.k] represents an arbitrary group member and there are s members in the group. If the vehicle user [V.sub.k] (1 [less than or equal to] k [less than or equal to] s) wants to quit the group, [V.sub.k] only needs to transmit the quit request to [RSU.sub.1]. And [RSU.sub.1] changes the public key of [V.sub.k] in the database to compute a new group public key c'. Substituting [y'.sub.k] for [y.sub.k], [RSU.sub.1] computes the new group public key according to the congruence equations (5).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

For equations (5), the value is c' [equivalent to] [s.summation over (i=1,i[not equal to]k)][y.sub.i][P.sub.i][P'.sub.i] + [y'.sub.k][P.sub.k][P'.sub.k] (mod P) [equivalent to] c - [y.sub.k][P.sub.k][P'.sub.k] + [y'.sub.k][P.sub.k][P'.sub.k](mod P), where [y'.sub.k] [equivalent to] [y.sub.k](mod [P.sub.k]) should not hold. Then [RSU.sub.1] updates Table 3 to Table 4.

By the above steps, there is only one change for computing the new group public key that [y'.sub.k] is altered to [y.sub.k] in calculation formula, where c' is the new group public key after the revocation of [V.sub.k].

After the revocation, both c' [equivalent to] [y.sub.k] (mod [p.sub.k]) and [pi] = h(f[parallel]M) will not hold, then the messages signed by [V.sub.k] 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 [V.sub.k], they can combine to submit an open application with the message ([pi], [zeta], [p.sub.k], M) to [RSU.sub.1]. There should be a specific number of users in reality, which is a measure of whether [RSU.sub.1] will accept the application.

With enough users, [RSU.sub.1] accept the application and compute the public key [y.sub.k] of [V.sub.k] by c [equivalent to] [y.sub.k] (mod [p.sub.k]). Then, [RSU.sub.1] searches its database to find the corresponding blind certificate of [V.sub.k] and submits (application, certificate) to [LTA.sub.1].

[LTA.sub.1] firstly checks the open application. Then [LTA.sub.1] retrieves its database to find the real identity of [V.sub.k] 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 [BV.sub.i]. RSU transmits the public key and the blind certificate of [BV.sub.i] to the corresponding LTA. Then LTA retrieves its database and find out the real identity of [BV.sub.i].

Unforgeability. By unforgeability meant that a signed message proved to be generated by [V.sub.k] can only be generated by [V.sub.k]. In our scheme, if a vehicle user [V.sub.j] receives a signed message ([pi], [zeta], [p.sub.k], M), with the group public parameters ([g.sub.1], [m.sub.1], [u.sub.1], c, h), [V.sub.j] will firstly compute the public key [y.sub.k] of [V.sub.k] by using equation c [equivalent to] [y.sub.k] (mod [p.sub.k]). Then [V.sub.j] computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and checks whether the equation [pi] = h(f[parallel]M) holds or not, if holds, [V.sub.j] believes the message is signed by [V.sub.k], otherwise abandons the message.

Since [p.sub.k] is a public parameter of [V.sub.k] and c is also pubic, the public key [y.sub.k] of [V.sub.k] obtained by equation c [equivalent to] [y.sub.k] (mod [p.sub.k]) is unique.

If an attacker Eve attends to forge a signature ([pi], [zeta]', [p.sub.k], M') of [V.sub.k], Eve randomly chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and computes f = [g.sup.[omega]'.sub.1] (mod [p.sub.k]), [pi]' = h(f', M'), [zeta]' = [omega]' - [x.sub.k]'[pi] (mod [q'.sub.k]), where [q'.sub.k]| [p.sub.k] - 1. However, [x.sub.k]' is necessary to compute [zeta]', and [x.sub.k]' should meet [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since the discrete logarithm problem, Eve cannot forge a signature of [V.sub.k].

Nonrepudiation. By nonrepudiation meant that [V.sub.k] cannot deny its own signed messages. Since the signed messages are unforgeable, and the public key [y.sub.k] of [V.sub.k] can be computed by c [equivalent to] [y.sub.k] (mod [p.sub.k]) for all the valid messages signed by [V.sub.k], [V.sub.k] cannot deny its own signed messages.

Forward security. If a user [V.sub.s+1] joins to the group, its public/private key pair [y.sub.s+1]/[x.sub.s+1] are generated by the public parameters, where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Moreover, the group public key is changed from c to [c.sub.new] by equations (6).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (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 [equivalent to] [y.sub.s+1](mod [p.sub.s+1]) also holds, so that the congruence equation c [equivalent to] [c.sub.new] (mod [P.sub.new]) should hold. In section 3.6, there is the restriction on the new group public key that the equation c [equivalent to] [c.sub.new] (mod [P.sub.new]) should not hold. Therefore, in proposed scheme, the forward security is guaranteed.

Backward Security. After the revocation of vehicle [V.sub.k], the group public key is refreshed from c to c by using equations (7).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (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' [equivalent to] [y.sub.k] (mod [p.sub.k]) holds that the revoked member is still able to sign messages with its old private key [x.sub.k]. Or the revoked member can obtain [x'.sub.k] which meets the equation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] that the revoked member can sign messages with the private key [x'.sub.k]. If the congruence equation c [equivalent to] [y.sub.k] (mod [p.sub.k]) holds, then the congruence equation [y'.sub.k] [equivalent to] [y.sub.k] (mod [p.sub.k]) holds, while a significant restriction on [y'.sub.k] is that the equation [y'.sub.k] [equivalent to] [y.sub.k] (mod [p.sub.k]) should not holds. The revoked member still can obtain the new group public key c' and compute c' [equivalent to] [y'.sub.k] (mod [p.sub.k]) to get [y'.sub.k]. If the revoked member can obtain [x'.sub.k] which meets the equation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 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 ([pi]', [zeta]', [p.sub.k], M') by an existing group member or generate a valid signed message ([pi]", [zeta]", 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 [V.sub.1], [V.sub.2], ..., [V.sub.s] and the group public key is c. For [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where 1 [less than or equal to] i [less than or equal to] s. If [V.sub.1], [V.sub.2], ..., [V.sub.m] wants to generate a new valid signed message ([pi]", [zeta]", p', M"), it is necessary to get parameters y' and x', where y' [equivalent to] [g.sub.1.sup.x'] (mod p'). Each verifier needs to compute y' by using c [equivalent to] 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 [y.sub.i], where 1 [less than or equal to] i [less than or equal to] s. Then, if [V.sub.1], [V.sub.2], ..., [V.sub.m] 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.

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.

In the proposed scheme, if a member [V.sub.k] quits the group, RSU only needs to substitute [y'.sub.k] for [y.sub.k] as the equations (5), and calculate the new group public key c' [equivalent to] c - ([y.sub.k] - [y'.sub.k])[P.sub.k][P'.sub.k] (mod P) 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 [T.sub.Mu] as multiplication. Hence the computational load is 2[T.sub.Ad]+4[T.sub.Mu].

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 [n.sub.gr] members in the group.

In [26], RSU can revoke a member [x.sub.j] 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 (4[T.sub.Ad] + [T.sub.In] + 6[T.sub.mu] + 5[T.sub.Ex])([n.sub.gr]-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 ([T.sub.Ad] + 3[T.sub.Mu] + 4[T.sub.Ex] + [T.sub.p])([n.sub.gr]-1).

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

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.

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.

This work was supported by the Natural Science Foundation of China (61102056, 61201132, 61402351), Fundamental Research Funds for the Central Universities of China (K5051301013) and the 111 Project of China (B08038).

http://dx.doi.org/10.3837/tiis.2015.10.027

References

[1] FIEBIG B., "European traffic accidents and purposed solutions," in Proc. of the ITU-T Workshop on Standardization in Telecommunication for Motor Vehicles. Geneva: ITU-T, pp. 24-25, 2003.

[2] V. Daza and J. Domingo-Ferrer, "Trustworthy privacy preserving car-generated announcements in vehicular ad hoc networks," IEEE Trans. Veh. Technol., vol. 58, no. 4, pp. 1876-1886, May 2009. Article (CrossRefLink)

[3] M. Raya and A. Aziz, "Efficient secure aggregation in VANETs," in Proc. of 3rd Int.Workshop VANETs, pp. 67-75, 2006. Article (CrossRefLink)

[4] M. Raya and J. Hubaux, "The security of vehicular ad hoc networks," in Proc. of 3rd ACM Workshop SASN, pp. 11-21, 2005. Article (CrossRefLink)

[5] J. Ren and J. Wu., "Survey on Anonymous communications in computer networks," Computer Communications, Elsevier, vol. 33, issue 4, pp. 420-431, May 2010. Article (CrossRefLink)

[6] Chaum, "Untraceable electronic mail, return addresses, and digital pseudonyms," Communications of the ACM, 24(2): pp. 84-90, 1981. Article (CrossRefLink)

[7] Sun and Jinyuan Zhang, "An Identity-Based Security System for User Privacy in Vehicular Ad Hoc Networks," IEEE Trans on Parallel and Distributed Systems, vol. 21, pp. 1227-1239, Sept. 2010. Article (CrossRefLink)

[8] Dijing Huang and Misra, S, "PACP: An Efficient Pseudonymous Authentication-Based Conditional Privacy Protocol for VANETs," IEEE Trans on Intelligent Transportation Systems, vol. 12, pp. 736-746, 2011. Article (CrossRefLink)

[9] Jonathan Petit and Florian Schaub, "Pseudonym Schemes in Vehicular Networks: A Survey," IEEE Communication Surveys & Tutorials, vol. 17, pp. 228-255, 2015. Article (CrossRefLink)

[10] Jie Li and Huang Lu, "ACPN: A Novel Authentication Framework with Conditional Privacy-Preservation and Non-Repudiation for VANETs," IEEE Trans on Parallel and Distributed Systems, vol. 26, pp. 938-948, 2015. Article (CrossRefLink)

[11] Beresford A R and Stajano F., "Location privacy in pervasive computing," Pervasive Computing, 2(1): pp. 46-55, 2003. Article (CrossRefLink)

[12] Elmer Schoch and Frank Kargl, "Impact of Pseudonym Changes on Geographic Routing in VANETs," Springer, LNCS. 4357, pp. 43-57, 2006. Article (CrossRefLink)

[13] Rongxing Lu and Xiaodong Li, "Pseudonym Changing at Social Spots: An Effective Strategy for Location Privacy in VANETs," IEEE Trans on Vehicular Technology, vol. 61, pp. 86-96, 2012. Article (CrossRefLink)

[14] Sam, M.M. and Vijayashanthi, N.,"An effective strategy for pseudonym generation & changing scheme with privacy preservation for vanet," International Conference on ICICA, pp. 109-117, May. 2014. Article(CrossRefLink)

[15] Hui Liu and Hui Li, "Efficient and Secure Authentication Protocol for VANET," IEEE 2010 International Conference on CIS, pp. 523-527, 2010. Article (CrossRefLink)

[16] Mamun, M.S.I. and Miyaji, A., "A Multi-purpose Group Signature for Vehicular Network Security," in Proc. of IEEE 2014 17th International Conference on NBiS, pp. 511-516, Sept. 2014. Article (CrossRefLink)

[17] Jun Shao and Xiaodong Lin, "A Threshold Anonymous Authentication Protocol for VANETs," IEEE Trans on Vehicular Technology, 2015. Article (CrossRefLink)

[18] Jung, Chae Duk and Sur, Chul, "A robust and efficient anonymous authentication protocol in VANETs," IEEE Journal of Communication and Networks, vol. 11, pp. 607-614, Dec. 2009. Article (CrossRefLink)

[19] Yong Hao and Yu Cheng, "Distributed Key Management with Protection Against RSU Compromise in Group Signature Based VANETs," IEEE GLOBECOM 2008, pp. 1-5, 2008. Article (CrossRefLink)

[20] Yong Hao and Yu Cheng, "A Distributed Key Management Framework with Cooperative Message Authentication in VANETs," IEEE Journal on Selected Areas in Communications, vol. 29, pp. 616-629, May, 2011. Article(CrossRefLink)

[21] Xiaoyan Zhu and Shunrong Jiang, "Privacy-preserving authentication based on group signature for VANETs," IEEE GLOBECOM, pp. 4609-4614, Dec. 2013. Article (CrossRefLink)

[22] Chaurasia, B.K. and Verma, S., "Message broadcast in VANETs using group signature," IEEE WCSN, pp. 131-136, Dec. 2008. Article (CrossRefLink)

[23] Xiaoyan Zhu and Shunrong Jiang, "Efficient Privacy-Preserving Authentication for Vehicular Ad Hoc Networks," IEEE Trans. Veh. Technol. vol. 63, no. 2, Feb. 2014. Article (CrossRefLink)

[24] Li He and Wen Tao Zhu, "Mitigating DoS attacks against signature-based authentication in VANETs," IEEE International Conference on CASE, vol. 3, pp. 261-265, May 2012. Article (CrossRefLink)

[25] Chun-I Fan and Wei-Zhe Sun, "Strongly Privacy-preserving Communication Protocol for VANETs," IEEE 2014 Ninth ASIA JCIS, pp. 119-126, Sept. 2014. Article (CrossRefLink)

[26] Lingbo Wei and Jianwei Liu, "On a Group Signature Scheme Supporting Batch Verification for Vehicular Networks," in Proc. of IEEE 2011 Third International Conference on MINES, pp. 436-440, 2011. Article (CrossRefLink)

[27] Toru Nakanishi and Hiroki Fujii, "Revocable Group Signature Schemes with Constant Costs for Signing and Verifying," International Association for Cryptologic Research, pp. 463-480, 2009. Article (CrossRefLink)

[28] Mamun, M.S.I. and Miyaji, A., "Secure VANET applications with a refined group signature," in Proc. of IEEE 2014 Twelfth ANNUAL International Conference on PST, pp. 199-206, 2014. Article (CrossRefLink)

[29] X.Chen, F.Zhang, and S.Liu, "ID-based restrictive partially blind signatures and applications," J. Syst. Softw, vol. 80, no. 2, pp. 164-171, 2007. Article (CrossRefLink)

[30] Zhenyu Yang and Shucheng Yu, "[P.sup.2]: Privacy-Preserving Communication and Precise Reward Architecture For V2G Networks in Smart Grid," IEEE Trans. Smart Grid, Vol. 2, pp. 697-706, Dec. 2011. Article (CrossRefLink)

[31] Pointcheval, D. and Stern, J., "Security Proofs for Signature Schemes," EUROCRYPT, LNCS, vol. 1070, pp. 387-398. Springer, Heidelberg, 1996. Article (CrossRefLink)

[32] Yannick Seurin, "On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model", EUROCRYPT, LNCS, Springer, Heidelberg, vol. 7237, pp. 554-571. 2012. Article (CrossRefLink)

[33] http://crypto.stanford.edu/pbc/.

Zhen Zhao was born in Shanxi, Changzhi, P.R. China in 1993. At present, she is pursuing her master degree in Xidian University, Xi'an, China. Her main research interests include key management, group signature, smart grid and wireless network security.

Jie Chen is an associate professor of Xidian University. She received her MS and PhD degree from Xidian University in 2005 and 2007. Her research interests include cryptographic protocols, design and analysis of cipher algorithm, security in Smart Grid. Email: jchen@mail.xidian.edu.cn.

Yueyu Zhang received his MS and PhD degree from Xidian University in 2005 and 2008. He is currently a visiting scholar at Michigan State University. Now he is an associate professor of Xidian University. His research interests include cryptographic protocols, security in Internet of Things and wireless network. Email: yyzhang@xidian.edu.cn.

Lanjun Dang received her M.E. degree and PH.D. degree in Communication and Information Systems from Xidian University, Xi'an, China, in 2005 and 2008, respectively. Now she is an associate professor of Xidian University. Her research interests included the security of mobile IP networks, authentication in wireless sensor networks, and information security.

Zhen Zhao (1), Jie Chen (1), Yueyu Zhang (1,2), and Lanjun Dang (1)

(1) State Key Laboratory of Integrated Service Networks, Xidian University Xi'an, Shaanxi, 710071, China [e-mail: zhaozhenbeyond@163.com; jchen@mail.xidian.edu.cn; yyzhang@xidian.edu.cn; ljdang@mail.xidian.edu.cn]

(2) Department of ECE, Michigan State University East Lansing, MI 48824, USA [e-mail: yueyu@msu.edu]

* Corresponding author: Jie Chen

Received May 12, 2015; revised July 26, 2015; accepted August 23, 2015; published October 31, 2015

Table 1. Symbols and Meaning Symbols Meaning [V.sub.k] the kth vehicle user [ID.sub.x] the real identity of an entity x in VANETs [Q.sub.x]/[[GAMMA].sub.x] the ID-based public/private key pair of BV x corresponding to its real identity [ID.sub.x] [MATHEMATICAL EXPRESSION the ID-based signature on a message M NOT REPRODUCIBLE using the ID-based private key IN ASCII] (M) [[GAMMA].sub.x] of signer x [MATHEMATICAL EXPRESSION the symmetric key encryption on message NOT REPRODUCIBLE M using the shared secret key k IN ASCII] (M) [HMAC.sub.k] (M) a hash-based message authentication code on message M using the shared secret key k Table 2. The Public Keys of the Existing Group Members The public key [y.sub.1] [y.sub.2] ... The public key [y.sub.i] ... [y.sub.s] Table 3. The Public Keys of the Existing Group Members The public key [y.sub.1] [y.sub.2] ... [y.sub.k] ... The public key [y.sub.s] [y.sub.s+1] Table 4. The Public Keys of the Existing Group Members The public key [y.sub.1] [y.sub.2] ... [y.sub.k-1] The public key [y.sub.k+1] ... [y.sub.s] Table 5. Comparison of Function Shao Chae Duk Yong Zhu Jun Jung Hao Xiaoyan Function Ours [17] [18] [20] [23] Member joining [check] [check] [check] [check] [check] Member revocation [check] [check] [check] Anonymity [check] [check] [check] [check] [check] Traceability [check] [check] [check] [check] [check] Unforgeability [check] [check] Forward security [check] Backward security [check] Anti-collusion [check] [check] [check] Wei Mamun, Lingbo M.S.I. Function [26] [28] Member joining [check] [check] Member revocation [check] [check] Anonymity [check] [check] Traceability [check] [check] Unforgeability Forward security Backward security Anti-collusion Table 6. Execution Time for Operations Denotation Time(ms) [T.sub.Ex] An exponentiation in [Z.sub.p.sup.*] 0.067 [T.sub.Ad] An addition in [Z.sub.p] 0.001 [T.sub.Mu] A multiplication in [Z.sub.p.sup.*] 0.001 [T.sub.In] An inverse operation in [Z.sub.p.sup.*] 0.004 [T.sub.p] A pairing operation 16.064 Table 7. Comparison on Revocation Computational Load of a Group Member Ours Wei Lingbo [26] Total 2[T.sub.Ad] + (4 [T.sub.Ad] + [T.sub.In] + computational 4[T.sub.Mu] 6[T.sub.Mu] + 5[T.sub.Ex]) load ([n.sub.gr]-1) Computational 0 3 [T.sub.Ad] + [T.sub.In] + load for each 5 [T.sub.Mu] + 4[T.sub.Ex] unrevoked member Computational 2[T.sub.Ad] + ([T.sub.Ad] + [T.sub.Mu] + load for RSU 4[T.sub.Mu] [T.sub.Ex])([n.sub.gr]-1) Mamun, M.S.I. [28] Total ([T.sub.Ad] + 3[T.sub.Mu] + computational 4[T.sub.Ex] + Tp) load ([n.sub.gr]-l) Computational [T.sub.Mu]+2[T.sub.Ex] + load for each [T.sub.p] unrevoked member Computational ([T.sub.Ad] + load for RSU 2[T.sub.Mu] + 2[T.sub.Ex]) ([n.sub.gr]-l)

Printer friendly Cite/link Email Feedback | |

Author: | Zhao, Zhen; Chen, Jie; Zhang, Yueyu; Dang, Lanjun |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Report |

Date: | Oct 1, 2015 |

Words: | 8075 |

Previous Article: | A receiver-aided seamless and smooth inter-RAT handover at layer-2. |

Next Article: | Background subtraction for moving cameras based on trajectory-controlled segmentation and label inference. |

Topics: |