Although many revocable group signature schemes has been proposed in vehicular ad hoc networks (VANETs), the existing schemes suffer from long computation delay on revocation that they cannot adapt to the dynamic VANETs. Based on Chinese remainder theorem and Schnorr signature algorithm, this paper proposes an efficient revocable group signature scheme in VANETs. In the proposed scheme, it only need to update the corresponding group public key when a member quits the group, and in the meanwhile the key pairs of unchanged group members are not influenced. Furthermore, this scheme can achieve privacy protection by making use of blind certificates. Before joining to the VANETs, users register at local trusted agencies (LTAs) with their ID cards to obtain blind certificates. The blind certificate will be submitted to roadside units (RSUs) to verify the legality of users. Thus, the real identities of users can be protected. In addition, if there is a dispute, users can combine to submit open applications to RSUs against a disputed member. And LTAs can determine the real identity of the disputed member. Moreover, since the key pairs employed by a user are different in different groups, attackers are not able to track the movement of users with the obtained public keys in a group. Furthermore, performance analysis shows that proposed scheme has less computation cost than existing schemes.
1. Introduction
D
ue to the extraordinary commercial and social potential, VANETs have been paid more and more attention. VANETs were first proposed at ITUT standardization in 2003
[1]
.VANETs are a type of Mobile Adhoc Network (MANET) which is the nextgeneration 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, rearend 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 privacypreserving authentication in VANETs
[2]

[4]
. Anonymous authentication is one of promising solutions for privacypreserving 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 privacypreserving 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 privacypreserving 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 anticollusion.
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 areILTAs 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 areJRSUs 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 semitrust, 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 tamperproof device (TPD) to store securityrelated materials. In this paper, it is supposed that each vehicle is uniquely identified by its battery.
System Model of VANETs
 2.2 Chinese Remainder Theorem
If
p
_{1}
,
p
_{2}
,⋯,
p_{k}
are pairwise coprime, where
k
≥ 2, set
P
=
p
_{1}
p
_{2}
⋯
p_{k}
=
p
_{1}
P
_{1}
=
p
_{2}
P
_{2}
= ⋯ =
p_{k}P_{k}
, 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 oneway hash function is considered to be secure if it satisfies the following properties.

(1) Givenx, it is easy to calculateh(x) =y. While conversely, giveny=h(x) , it is hard to computex.

(2) Givenx, it is computationally unworkable to findx≠x' such thath(x') =h(x).
 2.4 Bilinear Parings
In this paper, the properties of the bilinear operation are defined as follows:
G
_{1}
represents an additive cyclic group with order
q
,
G
_{2}
represents a multiplicative cyclic group with the same order,
e
:
G
_{1}
×
G
_{1}
→
G
_{2}
is a bilinear map, which meets the following requirements:

(1) Bilinearity: ∀R,S,T∈G1, there aree(R,S+T) =e(R,S)e(R,T) ,e(R+S,T) =e(R,T)e(S,T) ;

(2) Nondegenerative: ∃R,S∈G1, satisfiese(R,S) ≠ 1;

(3) Computability: ∀R,S∈G1,e(R,S) is computable in polynomial time.
 2.5 Notations
There are some symbols mentioned below as
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

• random primesb,csuch thatb≥ 2512,c≥ 2512, letn=b×c;

• a random numbere<ϕ(n) as its own public key, whereϕ(n) = (b−1)⋅(c−1) , and gcd(e,ϕ(n)) = 1;
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 LTA
_{i}
, where 1 ≤
i
≤
I
, GTA chooses

• random primesbi,cisuch thatbi≥ 2512,ci≥ 2512, letni=bi×ci;

• a random numberei<ϕ(ni) as the public key of LTAi, whereϕ(ni) = (bi−1)⋅(ci−1), and gcd(ei,ϕ(ni)) = 1;

• a random numbergias the identity code of LTAi;
GTA computes
d_{i}
as the private key of LTA
_{i}
, which satisfies
e_{i}
⋅
d_{i}
≡ 1(mod
ϕ
(
n_{i}
)) .
Then GTA safely sends the parameters to LTA
_{i}
. LTA
_{i}
publishes (
e_{i}
,
n_{i}
,
g_{i}
) as its public parameters, and secretly save the tuple (
b_{i}
,
c_{i}
,
d_{i}
) .
(3) LTA generates key pairs for RSUs using RSA algorithm. For RSU
_{i}
, where 1 ≤
i
≤
J
, LTA chooses

• random primessi,tisuch thatsi≥ 2512,ti≥ 2512, letmi=si×ti;

• a random numberui<ϕ(mi) as the public key of RSUi, whereϕ(mi) = (si−1)⋅(ti−1), and gcd(ui,ϕ(mi)) = 1 ;
Then LTA computes
v_{i}
as the private key of RSU
_{i}
, which satisfies
u_{i}
⋅
v_{i}
≡ 1(mod
ϕ
(
m_{i}
)) .
After receiving of these parameters, RSU
_{i}
publishes its public parameters (
u_{i}
,
m_{i}
), and keeps (
s_{i}
,
t_{i}
,
v_{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. IDbased 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
_{1}
. LTA
_{1}
chooses 3 random generators
R
,
R
_{1}
,
R
_{2}
∈
G
_{1}
.
Certificate Generation
(1) BV randomly generates a number
ξ_{BV}
and computes
M
=
A_{BV}
=
ξ_{BV}
R
_{1}
+
R
_{2}
,
ρ
=
e
(
R
,
Q
_{LTA1}
) ,
ρ
_{1}
=
e
(
R
_{1}
,
Q
_{LTA1}
) ,
ρ
_{2}
=
e
(
R
_{2}
,
Q
_{LTA1}
) and
y
=
e
(
P_{pub}
,
Q
_{LTA1}
) . Then BV sends
ID_{BV}
,
M
,
T
_{1}
,
SIG
_{ΓBV}
(
H
_{1}
(
ID_{BV}
∥
M
∥
T
_{1}
)) to LTA
_{1}
.
(2) LTA
_{1}
randomly chooses
Q
∈
G
_{1}
and
r
∈
, and computes
z
=
e
(
M
,Γ
_{LTA1}
) ,
a
=
e
(
R
,
Q
),
δ
=
e
(
M
,
Q
) ,
U
=
rR
and
Y
=
r
Q
_{LTA1}
. Then LTA
_{1}
sends
z
,
a
,
δ
,
U
,
Y
,
T
_{2}
,
HMAC
_{k1}
(
z
∥
a
∥
δ
∥
U
∥
Y
∥
T
_{2}
) to BV.
(3) BV randomly chooses
α
,
β
,
γ
,
λ
,
μ
,
σ
,
u
,
v
∈
, and computes
M
' =
αM
,
A
=
e
(
M
',
Q
_{LTA1}
) ,
,
δ
' =
δ^{uα}A^{ν}
,
z
'=
z^{α}
,
a
'=
a^{u}ρ^{ν}
,
Y
' =
λY
+
λμQ
_{LTA1}

γH
_{1}
(
j
) ,
U
' =
λU
+
γP_{pub}
,
l
=
λ
^{1}
H
_{2}
(
M
',
Y
',
U
',
A
,
B
,
z
',
a
',
δ
')+
μ
,
j
' =
lu
and
k
_{1}
=
e
(Γ
_{BV}
,
Q
_{LTA1}
) . Then BV sends
l
,
T
_{3}
,
HMAC
_{k1}
(
l
∥
T
_{3}
) to LTA
_{1}
.
(4) LTA computes
S
_{1}
=
Q
+
l
Γ
_{LTA1}
,
S
_{2}
= (
r
+
l
)Γ
_{LTA1}
+
rH
_{1}
(
j
) and sends
S
_{1}
,
S
_{2}
,
T
_{4}
,
HMAC
_{k1}
(
S
_{1}
∥
S
_{2}
∥
T
_{4}
) to BV.
(5) If the equations hold with
e
(
R
,
S
_{1}
) =
ay^{l}
,
e
(
M
,
S
_{1}
) =
δz^{l}
, 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,
T_{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 highspeed on updating in groups and secure on protecting the privacy of users.
It is assumed that the establishment occurs at RSU
_{1}
and there are
s
vehicle users in the original time.
(1) RSU
_{1}
: User
V_{i}
submits its request and blind certificate to RSU
_{1}
, where 1 ≤
i
≤
s
. That is, there are
s
vehicles and
V_{i}
represents the
i
^{th}
member. RSU
_{1}
verifies the validity of the blind certificate above all. The verification process is as
Fig. 3
.
Certificate Authentication

(1.1) BV sendscertificate,T6,HMACk2(certificate∥T6) to RSU1.

(1.2) RSU1computesA=e(M',QLTA1) . IfA≠ 0, computesi=H4(A,B,QRSU1,time) , wheretimeis the binary representation of the current time. RSU1sends the challengeito BV.

(1.3) BV computesr1=i(ξxα) +βandr2=iα+σ. Then BV sendsr1,r2to RSU1.

(1.4) RSU1computesand. The signature is valid ifholds. RSU1accepts this certificate if and only if.
If the certificate is valid and not expired, the verification is successful. Therefore, RSU
_{1}
allows
V_{i}
joining to the group and stores its blind certificate into database, 1 ≤
i
≤
s
.
(2) RSU
_{1}
→
V_{i}
: After confirming the validity of the presented certificate, RSU
_{1}
generates key materials for vehicle user
V_{i}
based on Schonorr signature algorithm. RSU
_{1}
randomly selects primes
p_{i}
,
q_{i}
, where
q_{i}

p_{i}
−1,
p_{i}
≥ 2
^{512}
,
q_{i}
≥ 2
^{160}
, and
p_{i}
≥
g
_{1}
,
g
_{1}
is the identity code of LTA
_{1}
. After which, RSU
_{1}
sends the tuple
to
V_{i}
in a secure environment, where
v
_{1}
is the private key of RSU
_{1}
.
(3)
V_{i}
: After receiving the parameters from RSU
_{1}
,
V_{i}
primarily verifies its legality. If the equations
,
are satisfied,
V_{i}
believes the parameters are valid and produced by RSU
_{1}
, where
u
_{1}
is the public key of RSU
_{1}
,
m
_{1}
is the public parameter of RSU
_{1}
.
V_{i}
will product its own public/private key pair employing the key materials as step (4).
(4)
V_{i}
→
RSU
_{1}
:
V_{i}
randomly selects
as its private key, and computes
as its public key. Then,
V_{i}
sends
y_{i}
to RSU
_{1}
via a secure channel, such as a Secure Socket Layer.
(5)
RSU
_{1}
: RSU
_{1}
reserves the public key of all group members with their corresponding blind certificate in database and public
Table 2
.
The Public Keys of the Existing Group Members
The Public Keys of the Existing Group Members
For member
V_{i}
, RSU
_{1}
transmits (
y_{i}
,
certification
) to LTA
_{1}
via a secure channel. LTA
_{1}
stores (
y_{i}
,
certification
) in its reserve.
(6) RSU
_{1}
generates the group public key. Taking advantage of the obtained public keys of
s
members, RSU
_{1}
computes the group key according to the congruence equations (2).
The value to the equations (2) is
, where
P
=
p
_{1}
p
_{2}
⋯
p_{s}
=
p
_{1}
P
_{1}
=
p
_{2}
P
_{2}
=⋯=
p_{s}P_{s}
,
,
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 RSU
_{1}
chooses a secure hash function
h
, and publishes (
g
_{1}
,
m
_{1}
,
u
_{1}
,
c
,
h
) .
When member
V_{i}
is willing to broadcast a message,
V_{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
V_{k}
wants to sign a message
M
,
V_{k}
will sign it by using Schnorr signature algorithm.
V_{k}
randomly chooses
and computes
,
π
=
h
(
f
∥
M
) ,
ζ
=
ω
−
x_{k}π
(mod
q_{k}
), where
g
_{1}
is the identity code of LTA
_{1}
,
x_{k}
is the private key of
V_{k}
,
p_{k}
,
q_{k}
are the primes chosen by RSU
_{1}
for
V_{k}
. Then, (
π
,
ζ
,
p_{k}
) is the signature of
V_{k}
on
M
.
 3.5. Verification
Anyone else can verify the signed message with the signature (
π
,
ζ
,
p_{k}
) and the group public key (
g
_{1}
,
m
_{1}
,
u
_{1}
,
c
,
h
) as
Algorithm 1
.
 3.6. Joining
It is supposed that vehicle user
V
_{s+1}
wants to join to the group of RSU
_{1}
.
V
_{s+1}
performs the following steps to join the group.
(1)
V
_{s+1}
submits its accession request and blind certificate to RSU
_{1}
. RSU
_{1}
verifies the validity of
V
_{s+1}
using
Fig. 3
. For eligible
V
_{s+1}
, RSU
_{1}
generates key parameters for
V
_{s+1}
. Based on Schnorr signature algorithm, RSU
_{1}
randomly selects primes
p
_{s+1}
,
q
_{s+1}
, where
q
_{s+1}

p
_{s+1}
−1,
p
_{s+1}
≥ 2
^{512}
,
q
_{s+1}
≥ 2
^{160}
, and
p
_{s+1}
≥
g
_{1}
. Then, RSU
_{1}
sends
to
V
_{s+1}
via a secure channel.
(2)
V
_{s+1}
verifies the legality of the received parameters. If the equations (3) hold,
V_{k}
believes the parameters are valid and produced by RSU
_{1}
.
Then
V
_{s+1}
randomly chooses
as its private key, and computes
as its public key. And
V
_{s+1}
sends
y
_{s+1}
to RSU
_{1}
via a secure channel.
(3) RSU
_{1}
reserves
y
_{s+1}
with its corresponding certificate in database and updates
Table 2
to
Table 3
.
The Public Keys of the Existing Group Members
The Public Keys of the Existing Group Members
Then RSU
_{1}
securely transmits (
y
_{s+1}
,
certification
) to LTA
_{1}
. LTA
_{1}
stores (
y
_{s+1}
,
certification
) in its reserve.
(4) RSU
_{1}
computes the new group key according to the congruence equations (4).
the value to the equations (4) is
, where
P_{new}
=
p
_{1}
p
_{2}
⋯
p_{s}
p
_{s+1}
=
Pp
_{s+1}
. The value of
P_{inew}
and
can be calculated by using
Algorithm 2
, where 1 ≤
i
≤
s
+1.
Thereby,
c_{new}
is the new group public key. But if
c
≡
c_{new}
(mod
P_{new}
) , RSU
_{1}
returns to step (1) to generate key parameters again for user. Finally RSU
_{1}
publishes (
g
_{1}
,
m
_{1}
,
u
_{1}
,
c_{new}
,
h
) .
 3.7 Revocation
Assume that
V_{k}
represents an arbitrary group member and there are
s
members in the group. If the vehicle user
V_{k}
(1 ≤
k
≤
s
) wants to quit the group,
V_{k}
only needs to transmit the quit request to RSU
_{1}
. And RSU
_{1}
changes the public key of
V_{k}
in the database to compute a new group public key
c
' . Substituting
for
y_{k}
, RSU
_{1}
computes the new group public key according to the congruence equations (5).
For equations (5), the value is
, where
≡
y_{k}
(mod
p_{k}
) should not hold. Then RSU
_{1}
updates
Table 3
to
Table 4
.
The Public Keys of the Existing Group Members
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
y_{k}
is altered
in calculation formula, where
c
' is the new group public key after the revocation of
V_{k}
.
After the revocation, both
c
' ≡
y_{k}
(mod
p_{k}
) and
π
=
h
(
f

M
) will not hold, then the messages signed by
V_{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_{k}
, they can combine to submit an open application with the message (π, ζ,
p_{k}
,
M
) to RSU
_{1}
. There should be a specific number of users in reality, which is a measure of whether RSU
_{1}
will accept the application.
With enough users, RSU
_{1}
accept the application and compute the public key
y_{k}
of
V_{k}
by
c
≡
y_{k}
(mod
p_{k}
). Then, RSU
_{1}
searches its database to find the corresponding blind certificate of
V_{k}
and submits (
application
,
certificate
) to LTA
_{1}
.
LTA
_{1}
firstly checks the open application. Then LTA
_{1}
retrieves its database to find the real identity of
V_{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
_{i}
. RSU transmits the public key and the blind certificate of BV
_{i}
to the corresponding LTA. Then LTA retrieves its database and find out the real identity of BV
_{i}
.
Unforgeability.
By unforgeability meant that a signed message proved to be generated by
V_{k}
can only be generated by
V_{k}
. In our scheme, if a vehicle user
V_{j}
receives a signed message (π, ζ,
p_{k}
,
M
) with the group public parameters (
g
_{1}
,
m
_{1}
,
u
_{1}
,
c
,
h
),
V_{j}
will firstly compute the public key
y_{k}
of
V_{k}
by using equation
c
≡
y_{k}
(mod
p_{k}
). Then
V_{j}
computes
and checks whether the equation
π
=
h
(
f

M
) holds or not, if holds,
V_{j}
believes the message is signed by
V_{k}
, otherwise abandons the message.
Since
p_{k}
is a public parameter of
V_{k}
and
c
is also pubic, the public key
y_{k}
of
V_{k}
obtained by equation
c
≡
y_{k}
(mod
p_{k}
) is unique.
If an attacker Eve attends to forge a signature (π', ζ',
p_{k}
,
M
') of
V_{k}
, 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
V_{k}
.
Nonrepudiation.
By nonrepudiation meant that
V_{k}
cannot deny its own signed messages. Since the signed messages are unforgeable, and the public key
y_{k}
of
V_{k}
can be computed by
c
≡
y_{k}
(mod
p_{k}
) for all the valid messages signed by
V_{k}
,
V_{k}
cannot deny its own signed messages.
Forward security.
If a user
V
_{s+1}
joins to the group, its public/private key pair
y
_{s+1}
/
x
_{s+1}
are generated by the public parameters, where
. Moreover, the group public key is changed from
c
to
c_{new}
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 ≡
y
_{s+1}
(mod
p
_{s+1}
) also holds, so that the congruence equation
c
≡
c_{new}
(mod
p_{new}
) should hold. In section 3.6, there is the restriction on the new group public key that the equation
c
≡
c_{new}
(mod
p_{new}
) should not hold. Therefore, in proposed scheme, the forward security is guaranteed.
Backward Security.
After the revocation of vehicle
V_{k}
, 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
' ≡
y_{k}
(mod
p_{k}
) holds that the revoked member is still able to sign messages with its old private key
x_{k}
. 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
' ≡
y_{k}
(mod
p_{k}
) holds, then the congruence equation
≡
y_{k}
(mod
p_{k}
) holds, while a significant restriction on
is that the equation
≡
y_{k}
(mod
p_{k}
) should not holds. The revoked member still can obtain the new group public key
c
' and compute c' ≡
(mod
p_{k}
) 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.
Anticollusion.
By anticollusion meant that several group members can together forge a signed message (
π
',
ζ
',
p_{k}
,
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
V
_{1}
,
V
_{2}
,⋯,
V_{s}
and the group public key is
c
. For
V_{i}
,
, where 1 ≤
i
≤
s
. If
V
_{1}
,
V
_{2}
,⋯,
V_{m}
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
y_{i}
, where 1 ≤
i
≤
s
. Then, if
V
_{1}
,
V
_{2}
,⋯,
V_{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
.
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 i53210 2.5GHz CPU and 4GB RAM.
Execution Time for Operations
Execution Time for Operations
In the proposed scheme, if a member
V_{k}
quits the group, RSU only needs to substitute
for
y_{k}
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
T_{Mu}
as multiplication. Hence the computational load is 2
T_{Ad}
+4
T_{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_{gr}
members in the group.
In
[26]
, RSU can revoke a member
x_{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_{Ad}
+
T_{In}
+6
T_{Mu}
+5
T_{Ex}
)(
n_{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_{Ad}
+3
T_{Mu}
+4
T_{Ex}
+
T_{p}
)(
n_{gr}
1).
We compare the revocation computational load of a group member in this scheme with
[26]
and
[28]
in
Table 7
.
Comparison on Revocation Computational Load of a Group Member
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.
Comparison of Total Computational Load
Comparison of Computational Load for Each Unrevoked Member
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.
BIO
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.
FIEBIG B.
“European traffic accidents and purposed solutions,”
ITUT
in Proc. of the ITUT Workshop on Standardization in Telecommunication for Motor Vehicles.
Geneva
2003
24 
25
Daza V.
,
DomingoFerrer J.
2009
“Trustworthy privacy preserving cargenerated announcements in vehicularad hocnetworks,”
IEEE Trans. Veh. Technol.
58
(4)
1876 
1886
DOI : 10.1109/TVT.2008.2002581
Raya M.
,
Aziz A.
“Efficient secure aggregation in VANETs,”
in Proc. of 3rd Int.Workshop VANETs
2006
67 
75
Raya M.
,
Hubaux J.
“The security of vehicular ad hoc networks,”
in Proc. of 3rd ACM Workshop SASN
2005
11 
21
Chaum
1981
“Untraceable electronic mail, return addresses, and digital pseudonyms,”
Communications of the ACM
24
(2)
84 
90
DOI : 10.1145/358549.358563
Sun
,
Zhang Jinyuan
2010
“An IdentityBased Security System for User Privacy in Vehicular Ad Hoc Networks,”
IEEE Trans on Parallel and Distributed Systems
21
1227 
1239
DOI : 10.1109/TPDS.2010.14
Huang Dijing
,
Misra S
2011
“PACP: An Efficient Pseudonymous AuthenticationBased Conditional Privacy Protocol for VANETs,”
IEEE Trans on Intelligent Transportation Systems
12
736 
746
DOI : 10.1109/TITS.2011.2156790
Petit Jonathan
,
Schaub Florian
2015
“Pseudonym Schemes in Vehicular Networks: A Survey,”
IEEE Communication Surveys & Tutorials
17
228 
255
DOI : 10.1109/COMST.2014.2345420
Li Jie
,
Lu Huang
2015
“ACPN: A Novel Authentication Framework with Conditional PrivacyPreservation and NonRepudiation for VANETs,”
IEEE Trans on Parallel and Distributed Systems
26
938 
948
DOI : 10.1109/TPDS.2014.2308215
Schoch Elmer
,
Kargl Frank
2006
“Impact of Pseudonym Changes on Geographic Routing in VANETs,”
LNCS.
Springer
4357
43 
57
Lu Rongxing
,
Li Xiaodong
2012
“Pseudonym Changing at Social Spots: An Effective Strategy for Location Privacy in VANETs,”
IEEE Trans on Vehicular Technology
61
86 
96
DOI : 10.1109/TVT.2012.2205028
Sam M.M.
,
Vijayashanthi N.
“An effective strategy for pseudonym generation & changing scheme with privacy preservation for vanet,”
International Conference on ICICA
May. 2014
109 
117
Liu Hui
,
Li Hui
“Efficient and Secure Authentication Protocol for VANET,”
IEEE 2010 International Conference on CIS
2010
523 
527
Mamun M.S.I.
,
Miyaji A.
“A Multipurpose Group Signature for Vehicular Network Security,”
in Proc. of IEEE 2014 17th International Conference on NBiS
Sept. 2014
511 
516
Shao Jun
,
Lin Xiaodong
“A Threshold Anonymous Authentication Protocol for VANETs,”
IEEE Trans on Vehicular Technology
2015
Jung Chae Duk
,
Sur Chul
2009
“A robust and efficient anonymous authentication protocol in VANETs,”
IEEE Journal of Communication and Networks
11
607 
614
DOI : 10.1109/JCN.2009.6388414
Hao Yong
,
Cheng Yu
“Distributed Key Management with Protection Against RSU Compromise in Group Signature Based VANETs,”
IEEE GLOBECOM 2008
2008
1 
5
Hao Yong
,
Cheng Yu
2011
“A Distributed Key Management Framework with Cooperative Message Authentication in VANETs,”
IEEE Journal on Selected Areas in Communications
29
616 
629
DOI : 10.1109/JSAC.2011.110311
Zhu Xiaoyan
,
Jiang Shunrong
“Privacypreserving authentication based on group signature for VANETs,”
IEEE GLOBECOM
Dec. 2013
4609 
4614
Chaurasia B.K.
,
Verma S.
“Message broadcast in VANETs using group signature,”
IEEE WCSN
Dec. 2008
131 
136
Zhu Xiaoyan
,
Jiang Shunrong
2014
“Efficient PrivacyPreserving Authentication for Vehicular Ad Hoc Networks,”
IEEE Trans. Veh. Technol.
63
(2)
DOI : 10.1109/TVT.2013.2294032
He Li
,
Zhu Wen Tao
“Mitigating DoS attacks against signaturebased authentication in VANETs,”
IEEE International Conference on CASE
May 2012
vol. 3
261 
265
Fan ChunI
,
Sun WeiZhe
“Strongly Privacypreserving Communication Protocol for VANETs,”
IEEE 2014 Ninth ASIA JCIS
Sept. 2014
119 
126
Wei Lingbo
,
Liu Jianwei
“On a Group Signature Scheme Supporting Batch Verification for Vehicular Networks,”
in Proc. of IEEE 2011 Third International Conference on MINES
2011
436 
440
Nakanishi Toru
,
Fujii Hiroki
“Revocable Group Signature Schemes with Constant Costs for Signing and Verifying,”
International Association for Cryptologic Research
2009
463 
480
Mamun M.S.I.
,
Miyaji A.
“Secure VANET applications with a refined group signature,”
in Proc. of IEEE 2014 Twelfth ANNUAL International Conference on PST
2014
199 
206
Chen X.
,
Zhang F.
,
Liu S.
2007
“IDbased restrictive partially blind signatures and applications,”
J. Syst. Softw
80
(2)
164 
171
DOI : 10.1016/j.jss.2006.02.046
Yang Zhenyu
,
Yu Shucheng
2011
“P2:PrivacyPreserving Communication and Precise Reward Architecture For V2G Networks in Smart Grid,”
IEEE Trans. Smart Grid
2
697 
706
DOI : 10.1109/TSG.2011.2140343
Pointcheval D.
,
Stern J.
“Security Proofs for Signature Schemes,”
Springer
Heidelberg
EUROCRYPT, LNCS, vol. 1070
1996
387 
398
Seurin Yannick
“On the Exact Security of SchnorrType Signatures in the Random Oracle Model”
Springer
Heidelberg
EUROCRYPT, LNCS
2012
vol. 7237
554 
571
http://crypto.stanford.edu/pbc/