# Using BDH for the Message Authentication in VANET

Authors: Mei-Wen Huang; Hsin-Te Wu; Gwo-Jiun Horng; Wen-Shyong Hsieh
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

The transport message security provided by vehicles in VANETs is quite important; vehicle message should be real-time and it will be not complicated to validate message calculation. The method proposed in the essay is mainly to validate the identity by means of Bilinear Diffie-Hellman method, and make vehicles validate the authenticity of RSU and TA’s identity and the effectiveness of key. RSU and TA only need to validate vehicle identity, without helping vehicles produce any key. When vehicle identity validation is completed, vehicles will produce public value and transmit it to other RSU and vehicles, while other vehicles could validate the identity through the message from the sender and public value from RSU.
The advantages of the method proposed in this essay are listed as follows. (1) Vehicles, RSU, and TA can validate mutual identities and the effectiveness of keys. (2) Vehicles can produce public value functions automatically, thus reducing key control risks. (3) Vehicles do not need to show certificates to validate their identities, preventing the certificates from attacking because of long-term exposure. (4) Vehicles adopt a pseudonym ID challenge to validate their own identities during the process of handoff. (5) Vehicle messages can be validated using the Bilinear Diffie-Hellman (BDH) method without waiting for the RSU to validate messages, thus improving the instantaneity of messaging. The method proposed in the essay can satisfy source authentication, message integrity, nonrepudiation, privacy, and conditional untraceability requirements.


---

## Body

## 1. Introduction

Especially VANET receives special attention in terms of traffic security and traffic management [1, 2]. In order to reach the demand of vehicle security, vehicles often broadcast traffic related message among themselves (vehicle position, speed, traffic accidents, and so on) and other services [3], which could reduce traffic jams and dangerous road sections and improve the driving security. VANET usually has two message transmission modes: (
1
) message broadcast mode, through which vehicles could make other vehicles nearby know the traffic condition in the neighborhood; (
2
) one hop message transmission, through which vehicles could transmit message to the designated vehicle and which is mainly used for private communication among vehicles.The essay mainly investigates message security and integral security system layout in VANET, which aims at vehicles’ safety on road. Each vehicle could use broadcast mode and inform other vehicles of the traffic condition nearby, so as to avoid traffic jam and improve driving efficiency. They could also use private communication and RSU or TA (trusted authority) for updating. Assume this message was maliciously attacked or forged, it would cause vehicle collision or traffic jam; so message integrity and source authentication is the important key.The method proposed in the essay is based on RSU. Suppose that each main road was provided with RSU and secondary roads were not. In the whole system framework, TA utilizes Bilinear Diffie-Hellman to generate public/private key and other parameters of its own and RSU, where the effective time of key is added, so TA and RSU is forced to change key regularly and improve system security and all vehicles could validate the legality of RSU through public key and other parameters of RSU and by means of Bilinear Diffie-Hellman.We adopt two-level pseudonym method; that is to say, vehicles have the first-level pseudonym ID in TA and the second-level pseudonym ID in RSU. There is no relationship between the two levels of pseudonym ID in terms of original generation modes, which avoids RSU maliciously conspiring and tracing vehicles. TA and RSU are only responsible for validating vehicle identity, not for the vehicle broadcast message. After the identity authentication of vehicles and RSU, vehicles would transmit public value to RSU, which will then send the public value to each RSU and vehicle, so when a vehicle is broadcasting message, all vehicles could validate the message integrity through the method of Bilinear Diffie-Hellman, without using RSU. Meanwhile, the calculation of Bilinear Diffie-Hellman signatures is not very complicated and the key of Bilinear Diffie-Hellman signatures for vehicles is different each time, so it is unable to get forged and attacked.During the process of handoff, vehicles adopt pseudonym ID challenge method to validate their own identities, which only need communicate pseudonym generation mode with the next RSU. As only vehicles and RSU know the pseudonym generation mode, if the challenge is successful, the identities could be validated mutually, so as to reduce the identity validation time when vehicles are handoff. Meanwhile, vehicles have different public values and pseudonym ID in each RSU.


## 2. Related Works

Public key infrastructure (PKI) method is used in [9]. Suppose that TA issues certificates; each vehicle has private key and certificates have public key relative to private key; when vehicle a is about to communicate with another vehicle b, a will use the public key in b’s certificates to encrypt the message, then a transmits the encrypted message to b, and b decrypts the message through private key. As the certificates are issued by TA, so they are reliable. Provided that b could decrypt the message, the message integrity could be confirmed. Vehicles utilizing PKI for message encrypting and decrypting would improve the calculation complexity and bring great calculation burden during the communication process. In order to protect privacy and not to be traced, certificates must be changed frequently, which will cause burden on TA.A dynamic privacy-preserving key management scheme for location-based services in VANETs was proposed in [4]. This scheme ensures the anonymous authentication of a vehicle and enables double-registration detection. In addition, each vehicle can use a one-way hash function to update the vehicles new session key. However, the computations for message signature and verification presented in [4] are complicated, and the author did not investigate a private communication scheme.In [5], when vehicles are able to get some network access services from RSU, they must broadcast a message and establish common key with vehicles receiving the message, and then this common key could be utilized to guarantee the security while communicating the message. However, the establishment of common key is got through pairing computation of identity-based cryptography (IBC) [10], whose calculation is much more complicated than normal computation, and the calculation burden is quite great. The essay does not discuss the problems when vehicles rekey or change pseudonym ID, which is quite important to VANETs, so it is necessary to propose the solutions.In [6], an elliptic curve digital signature algorithm (ECDSA) was used for message authentication. The current position information is used together with the ECDSA for signing messages from anonymous IDs. Other vehicles do not require a third-party public key certificate for message authentication. However, the authors did not discuss the problems of rekeying and private communication.The literature [7] proposed that a driver can check the status of a road through VANET, the transmission process that utilizes bilinear technology to ensure information security and vehicle privacy. Either a vehicle or an RSU must have identity verification with TA and related key generation. Identity verification utilizes bilinear technology to ensure information security and nonrepudiation. Traditional asymmetric encryption, symmetric encryption, and signature are used for messaging of any unit (vehicle, RSU, or TA). In the literature [7] TA must constantly change the master secret key of a vehicle or RSU, which results in a heavy computational load of TA, and the messaging using asymmetric encryption will cause the same problem during decryption.The literature [8] proposed message batch verification and group message signing and verification for vehicle privacy and information security. Vehicles form a group and each group has a related key for message encryption and decryption. Because the message is sent by a group, it cannot be traced back to a specific vehicle. If a vehicle in the group sends a malicious message, however, it may also be difficult to track down and batch verification will delay real-time messaging.The literature [11] primarily involves group message signing improvement. This paper has improved the group message signing performance, but has not discussed private communications between vehicles or the replacement of relevant vehicle parameters. A vehicle is vulnerable to tracking if the relevant parameters are not replaced regularly.


## 3. Background

### 3.1. Bilinear Pairings and Hard Problems

LetG
1 and G
2 denote an additive and a multiplicative group, and both of them are with prime order q. Let P be generator of G
1, and let e
:
G
1
×
G
1
→
G
2 be a bilinear mapping with the following properties.(1)
Bilinear:(1)
e
=
(
a
P
,
b
P
)
=
e
(
P
,
P
)
a
b
,
e
(
a
·
P
+
b
·
P
,
P
)
=
e
(
a
·
P
,
P
)
e
(
b
·
P
,
P
)
,
∀
P
∈
G
1
,
a
,
b
∈
Z
q
*
.
(2)
Nondegeneracy:∃
P
∈
G
1 such that e
^
(
P
,
P
)
≠
1. That is, the mapping does not send all pairs in G
1
×
G
1 to the identity in G
2.
(3)
Computable: there exists an efficient algorithm to computee
(
P
,
P
) for all P
∈
G
1.The bilinear mape can be implemented using the Weil [12] and Tate [13] pairings on elliptic curves. We consider the implementation of a Tate pairing on a Miyaji-Nakabayashi-Takano (MNT) curve [14] with embedding degree 6, where G
1 is represented by 161 bits and the order q is represented by 160 bits.The following part will define and specify various relevant mathematical problems [15] which will be applied in the essay subsequently.Bilinear Diffie-Hellman (BDH) Problem. Given (
P
,
a
P
,
b
P
,
c
P
)
∈
G
1, where a
,
b
,
c
∈
Z
q
*, compute e
=
(
P
,
P
)
a
b
c.Elliptic Curve Discrete Logarithm Problem (ECDLP). Given two elements P
,
Q
∈
G
1, find an integer a
∈
Z
q
*, such that Q
=
a
P.


### 3.2. Boneh and Franklin’s ID-Based Encryption

We use Boneh and Franklin’s ID-Based Encryption [13] to encrypt and decrypt message. Let k be the system security parameter. Then PKG selects two groups G
1 and G
2 of prime orderq, a bilinear mapping e
=
G
1
×
G
1
→
G
2, and a generator P of group G
1. PKG also picks a random number s
∈
Z
q
* as its master key and then selects two distinct hash functions: H
1
:
{
0,1
}
*
→
G
1
*, H
2
:
G
2
→
{
0,1
}
*. At last, PKG publishes the system parameters (
q
,
G
1
,
G
2
,
e
,
P
,
H
1
,
H
2
) and keeps g secretly.Assume there are two usersa and b. User a utilizes the public key of User b to encrypt message M; the identity of User b is ID
b
∈
{
0,1
}
*, with the public key, private key, and data key being P
U
b
=
H
1
(
I
D
b
), P
R
b
=
s
·
H
1
(
I
D
b
), and P
D
b
=
s
·
P, respectively, and User a selects random number r
∈
Z
q
* randomly. The message encryption process is as follows:
(2)
C
=
{
r
·
P
,
M
⊕
H
2
(
e
(
P
U
b
,
P
D
b
)
r
)
}
,
where C
=
{
U
,
V
} is the encrypted message, User a sends the encrypted message to User b, and then User b utilizes private key for decryption and works out message M after receiving the message, with the calculation as follows:
(3)
e
(
P
R
b
,
U
)
=
e
(
s
·
P
U
b
,
r
·
P
)
=
e
(
P
U
b
,
P
D
b
)
r
,
V
⊕
H
2
(
e
(
P
R
b
,
U
)
)
=
V
⊕
H
2
(
e
(
P
U
b
,
P
D
b
)
r
)
=
M
.


### 3.3. J. H. Cheon, Y. Kim, and H. J. Yoon’s ID-Based Signature

We use J. H. Cheon, Y. Kim, and H. J. Yoon’s ID-Based Signature [14] to attain message signatures and the section uses the system parameters (
q
,
G
1
,
G
2
,
e
^
,
P
,
H
1
,
H
2
) PKG publishes in Section 3.2 and keeps g secretly. Assume User b signatures message M and broadcasts it to other users, who then use the public key and data key of User b to validate the source and message integrity of signature after receiving signatures. User b selects random number r
∈
Z
q
* at random, with the calculation as follows:
(4)
U
=
r
·
P
,
h
=
(
M
,
U
)
,
V
=
r
·
P
U
b
+
h
·
P
R
b
.When other users receiveM, U, and V, they can utilize the public key and public parameter of User b to validate signatures, and the signature validation calculation is as follows:
(5)
e
(
P
U
b
,
U
+
h
·
P
D
b
)
=
e
(
V
,
P
)
.


### 3.4. Bilinear Diffie-Hellman (BDH) Messages Authentication

The essay applies the features of bilinear pairings hard problems [15]. Though the calculation time increases, it is acceptable if the calculation is reasonable. The method we propose assumes that users select two random numbers γ
i and α
i at random, where m
i
=
1
/
H
4
(
M
∥
T
stamp
); then we calculate public value as follows:
(6)
d
=
α
i
*
γ
i
*
m
i
.
Next, we apply them to bilinear pairings, with the calculation as follows:
(7)
D
=
e
(
d
·
P
,
P
)
=
e
(
P
,
P
)
d
,
(8)
D
=
e
(
α
i
·
P
,
m
i
·
γ
i
·
P
)
=
e
(
P
,
P
)
α
i
m
i
γ
i
.If users release messageM, they will first work out α
i, γ
i, and m
i through formula (6) and then issue (
D
,
α
i
·
P
,
γ
i
·
P
,
m
i
) to other users. Other users could validate source and message integrity through formula (8). We utilize hard problems to validate the method’s security. (
1
) According to ECDLP, we publish (
D
,
α
i
·
P
,
γ
i
·
P
,
m
i
) and other users cannot get d from D
=
e
(
P
,
P
)
d and know α
i and γ
i from α
i
·
P and γ
i
·
P, so users cannot forge message maliciously; (
2
) according to BDH and e
(
α
i
·
P
,
m
i
*
γ
i
·
P
)
=
e
(
P
,
P
)
d, DBDHP feature is utilized to validate message integrity, as shown in formula (8).


## 3.1. Bilinear Pairings and Hard Problems

LetG
1 and G
2 denote an additive and a multiplicative group, and both of them are with prime order q. Let P be generator of G
1, and let e
:
G
1
×
G
1
→
G
2 be a bilinear mapping with the following properties.(1)
Bilinear:(1)
e
=
(
a
P
,
b
P
)
=
e
(
P
,
P
)
a
b
,
e
(
a
·
P
+
b
·
P
,
P
)
=
e
(
a
·
P
,
P
)
e
(
b
·
P
,
P
)
,
∀
P
∈
G
1
,
a
,
b
∈
Z
q
*
.
(2)
Nondegeneracy:∃
P
∈
G
1 such that e
^
(
P
,
P
)
≠
1. That is, the mapping does not send all pairs in G
1
×
G
1 to the identity in G
2.
(3)
Computable: there exists an efficient algorithm to computee
(
P
,
P
) for all P
∈
G
1.The bilinear mape can be implemented using the Weil [12] and Tate [13] pairings on elliptic curves. We consider the implementation of a Tate pairing on a Miyaji-Nakabayashi-Takano (MNT) curve [14] with embedding degree 6, where G
1 is represented by 161 bits and the order q is represented by 160 bits.The following part will define and specify various relevant mathematical problems [15] which will be applied in the essay subsequently.Bilinear Diffie-Hellman (BDH) Problem. Given (
P
,
a
P
,
b
P
,
c
P
)
∈
G
1, where a
,
b
,
c
∈
Z
q
*, compute e
=
(
P
,
P
)
a
b
c.Elliptic Curve Discrete Logarithm Problem (ECDLP). Given two elements P
,
Q
∈
G
1, find an integer a
∈
Z
q
*, such that Q
=
a
P.


## 3.2. Boneh and Franklin’s ID-Based Encryption

We use Boneh and Franklin’s ID-Based Encryption [13] to encrypt and decrypt message. Let k be the system security parameter. Then PKG selects two groups G
1 and G
2 of prime orderq, a bilinear mapping e
=
G
1
×
G
1
→
G
2, and a generator P of group G
1. PKG also picks a random number s
∈
Z
q
* as its master key and then selects two distinct hash functions: H
1
:
{
0,1
}
*
→
G
1
*, H
2
:
G
2
→
{
0,1
}
*. At last, PKG publishes the system parameters (
q
,
G
1
,
G
2
,
e
,
P
,
H
1
,
H
2
) and keeps g secretly.Assume there are two usersa and b. User a utilizes the public key of User b to encrypt message M; the identity of User b is ID
b
∈
{
0,1
}
*, with the public key, private key, and data key being P
U
b
=
H
1
(
I
D
b
), P
R
b
=
s
·
H
1
(
I
D
b
), and P
D
b
=
s
·
P, respectively, and User a selects random number r
∈
Z
q
* randomly. The message encryption process is as follows:
(2)
C
=
{
r
·
P
,
M
⊕
H
2
(
e
(
P
U
b
,
P
D
b
)
r
)
}
,
where C
=
{
U
,
V
} is the encrypted message, User a sends the encrypted message to User b, and then User b utilizes private key for decryption and works out message M after receiving the message, with the calculation as follows:
(3)
e
(
P
R
b
,
U
)
=
e
(
s
·
P
U
b
,
r
·
P
)
=
e
(
P
U
b
,
P
D
b
)
r
,
V
⊕
H
2
(
e
(
P
R
b
,
U
)
)
=
V
⊕
H
2
(
e
(
P
U
b
,
P
D
b
)
r
)
=
M
.


## 3.3. J. H. Cheon, Y. Kim, and H. J. Yoon’s ID-Based Signature

We use J. H. Cheon, Y. Kim, and H. J. Yoon’s ID-Based Signature [14] to attain message signatures and the section uses the system parameters (
q
,
G
1
,
G
2
,
e
^
,
P
,
H
1
,
H
2
) PKG publishes in Section 3.2 and keeps g secretly. Assume User b signatures message M and broadcasts it to other users, who then use the public key and data key of User b to validate the source and message integrity of signature after receiving signatures. User b selects random number r
∈
Z
q
* at random, with the calculation as follows:
(4)
U
=
r
·
P
,
h
=
(
M
,
U
)
,
V
=
r
·
P
U
b
+
h
·
P
R
b
.When other users receiveM, U, and V, they can utilize the public key and public parameter of User b to validate signatures, and the signature validation calculation is as follows:
(5)
e
(
P
U
b
,
U
+
h
·
P
D
b
)
=
e
(
V
,
P
)
.


## 3.4. Bilinear Diffie-Hellman (BDH) Messages Authentication

The essay applies the features of bilinear pairings hard problems [15]. Though the calculation time increases, it is acceptable if the calculation is reasonable. The method we propose assumes that users select two random numbers γ
i and α
i at random, where m
i
=
1
/
H
4
(
M
∥
T
stamp
); then we calculate public value as follows:
(6)
d
=
α
i
*
γ
i
*
m
i
.
Next, we apply them to bilinear pairings, with the calculation as follows:
(7)
D
=
e
(
d
·
P
,
P
)
=
e
(
P
,
P
)
d
,
(8)
D
=
e
(
α
i
·
P
,
m
i
·
γ
i
·
P
)
=
e
(
P
,
P
)
α
i
m
i
γ
i
.If users release messageM, they will first work out α
i, γ
i, and m
i through formula (6) and then issue (
D
,
α
i
·
P
,
γ
i
·
P
,
m
i
) to other users. Other users could validate source and message integrity through formula (8). We utilize hard problems to validate the method’s security. (
1
) According to ECDLP, we publish (
D
,
α
i
·
P
,
γ
i
·
P
,
m
i
) and other users cannot get d from D
=
e
(
P
,
P
)
d and know α
i and γ
i from α
i
·
P and γ
i
·
P, so users cannot forge message maliciously; (
2
) according to BDH and e
(
α
i
·
P
,
m
i
*
γ
i
·
P
)
=
e
(
P
,
P
)
d, DBDHP feature is utilized to validate message integrity, as shown in formula (8).


## 4. Proposed Scheme

This chapter would introduce the methods proposed in the essay. Section4.2 introduces the system installation for the methods in Section 4.2. Section 4.3 introduces registration of vehicles and RSU, creation of vehicles and RSU related tables, and how vehicles carry out handoff at different RSU regions. Section 4.4 describes the message transmission between vehicles and message validation, vehicle message communication between different RSU, and private communication among TA, RSU, and vehicle. Section 4.5 introduces key updating and cancellation of identity between TA and RSU.


### 4.1. System Model

In system environment, as shown in Figure1, we assume that the overall environment only has one TA and TA is the legally binding unit mechanism and in charge of controlling the whole network’s security, which will provide the real identities of malicious nodes for legal prosecution when malicious nodes attack. On the one hand, the role of TA takes charge of validating vehicles or RSU’s identities and on the other hand RSU and relevant coefficients are set by TA and RSU is set up on some common traffic facilities, such as traffic lights. TA and RSU are provided with wire/wireless communication. The communication between TA and RSU adopts wire communication, such as backbone. TA, RSU, and vehicles use short distance wireless communication equipment and the communication between RSU and vehicles adopts wireless communication. The parameters used in the method are described in the Notation section.Figure 1
System environment diagram.


### 4.2. System Initialization

The section introduces the system installation of TA, RSU, and vehicles, which need not any certificates and could validate their own identities only by BDH messages authentication. Meanwhile, key sets the effective time, whose effectiveness could be validated any time.


#### 4.2.1. TA System Setup

Suppose the chapter would select five distinct hash functions:H
:
{
0,1
}
*
→
Z
q
*, H
1
:
{
0,1
}
*
→
G
1
*, H
2
:
G
2
→
{
0,1
}
*, H
3
:
G
1
→
{
0,1
}
*, and H
4
:
Wordseries
→
{
0,1
}
*.From the beginning, TA would calculate public value to solve public key, private key, and public parameter of TA as follows.(1)
Supposeα
I
D
TA
,
t
,
γ
I
D
TA
,
t
∈
Z
q
* and m
I
D
TA
,
t
=
H
4
(
I
D
TA
,
t
∥
T
l
I
D
TA
,
t
), where T
l
I
D
TA
,
t is the valid period of key and I
D
TA
,
t is the real ID of TA.
(2)
The calculation public value (D
I
D
TA
,
t) is as follows:
(9)
d
I
D
TA
,
t
=
α
I
D
TA
,
t
*
(
m
I
D
TA
,
t
*
γ
I
D
TA
,
t
)
,
(10)
D
I
D
TA
,
t
=
e
(
d
I
D
TA
,
t
P
,
P
)
=
e
(
P
,
P
)
d
I
D
TA
,
t
,
(11)
D
I
D
TA
,
t
=
e
(
α
I
D
TA
,
t
P
,
m
I
D
TA
,
t
*
γ
I
D
TA
,
t
P
)
.
(3)
Set public keyP
U
I
D
TA
,
t
=
H
1
(
I
D
TA
,
t
)
∈
G
1
*.
(4)
Set private keyP
R
I
D
TA
,
t
=
α
I
D
TA
,
t
P
U
I
D
TA
,
t.
(5)
Set data keyP
D
I
D
TA
,
t
=
α
I
D
TA
,
t
·
P.TA would stored
I
D
TA
,
t and provide it for TA or RSU changing public key and other parameters in the future, which would also make the following parameters (
q, G
1, G
2, e, P, H, H
1, H
2, H
3, H
4, D
I
D
TA
,
t, I
D
TA
,
t, P
D
I
D
TA
,
t, γ
I
D
TA
,
t
P, and T
l
I
D
TA
,
t
) public. When vehicles or RSU want to communicate with TA, it will be first to validate TA’s identity and key’s validness. α
I
D
TA
,
t, γ
I
D
TA
,
t, and d
I
D
TA
,
t cannot be known from the above public parameters. Therefore, malicious attackers couldn’t forge TA and TA does not need any certificates to validate its own identity.


#### 4.2.2. RSU System Setup

TA utilizesα
I
D
TA
,
t to set public key, private key, and other parameters of each RSU and selects y
∈
Z
q
* as the master key of private communication. Suppose the number of RSU is m and j
=
1 to m; then the calculation of TA is as follows.(1)
TA selectsx
I
D
R
j
,
t
∈
Z
q
* as the master key of private communication.
(2)
Calculate private communication key ofR
j to be e
(
y
·
P
+
x
R
j
,
t
·
P
,
P
) and e
(
P
U
I
D
R
j
,
t
·
P
+
x
I
D
R
j
,
t
·
P
,
P
).
(3)
Calculate public key, private key, and other parameters ofR
j as follows:
(12)
d
I
D
TA
,
t
=
α
I
D
TA
,
t
*
(
m
I
D
TA
,
t
*
γ
I
D
TA
,
t
)
,
where m
I
D
TA
,
t
=
1
/
H
4
(
I
D
R
j
,
t
∥
T
lifetime
I
D
R
j
,
t
) and I
D
R
j
,
t is the real ID of RSU.
(4)
Set public keyP
U
R
j
,
t
=
H
1
(
I
D
R
j
,
t
).
(5)
Set private keyP
R
R
j
=
α
I
D
TA
,
t
·
P
U
R
j
,
t.
(6)
Set data keyP
D
R
j
,
t
=
α
I
D
TA
,
t
P.TA would create a table to record RSU’s ID, key’s valid time, being legal or not, and RSU’s common key, with the calculation method for common key proposed in Section4.4.3.TA will not giveR
j any certificates and it can validate the identity only by BDH messages authentication. Meanwhile, each RSU’s key has valid time and it could be known whether key is within the valid time only from the identity validation. Any unit could validate RSU or TA’s legitimacy through the following formula, with the calculation as follows:
(13)
D
TA
=
e
(
P
D
u
,
m
u
*
γ
u
P
)
,
where u represents TA or any one RSU.


#### 4.2.3. Vehicle System Setup

TA is only in charge of validating vehicles’ identities and public value and it does not produce vehicles’ key, so as to avoid the risk of controlling key. Suppose the number of vehicles ism and i
=
1 to m; then the calculation is as follows.(1)
VehicleV
i would calculate the first-level pseudonym of it and TA’s ID (I
D
V
i
,
i), where I
D
V
i
,
i
=
H
(
I
D
V
i
,
t
∥
I
D
TA
,
t
) and I
D
V
i
,
t is the real ID of the vehicle.
(2)
VehicleV
i would calculate public value of it and TA’s identity validation, with the calculation as follows:
(14)
d
I
D
V
i
,
i
=
α
I
D
V
i
,
i
*
m
I
D
V
i
,
i
*
γ
I
D
V
i
,
i
.
(3)
VehicleV
i utilizes TA’s public key to encrypt message M and transmit it to TA, with the calculation as follows:
(15)
C
=
{
r
·
P
,
M
⊕
H
2
(
e
(
PU
I
D
TA
,
t
,
P
D
I
D
TA
,
t
)
r
)
}
,where r
∈
Z
q
*, M
=
(
D
I
D
V
i
,
i
∥
α
I
D
V
i
,
i
·
P
∥
γ
I
D
V
i
,
i
P
∥
I
D
V
i
,
t
∥
I
D
V
i
,
t
), and V
i transmits the encrypted message C to TA, with the calculation as follows:
(16)
e
(
P
R
I
D
TA
,
t
,
U
)
=
e
(
P
U
I
D
TA
,
t
,
P
D
I
D
TA
,
t
)
r
V
⊕
H
2
(
e
(
P
R
I
D
TA
,
t
,
U
)
)
=
V
⊕
H
2
(
e
(
P
U
I
D
TA
,
t
,
P
D
I
D
TA
,
t
)
r
)
=
M
.TA would validateV
i’s first-level pseudonym ID (I
D
V
i
,
i) and then public value, as shown in the following formula:
(17)
D
I
D
V
i
,
i
=
e
(
α
I
D
V
i
,
i
P
,
m
I
D
V
i
,
i
*
γ
I
D
V
i
,
i
P
)
.


### 4.3. Message Broadcast and Message Authentication in RSU

When a vehicle enters RSU region, the vehicle would first check if RID table has already had the message validated mutually with RSU. If there is none, what will be done is to start from Section4.3.1 to carry out identity validation with RSU, create SPID table and RID table with RSU in Section 4.3.2, and then discuss the method of vehicles being handoff at different RSU in Section 4.3.3.


#### 4.3.1. Registration

Suppose that when the vehicleV
i enters region R
j and V
i has not created public value related functions and identity validation with R
j, then V
i would utilize TA to validate its own identity, so RSU could believe in the second-level pseudonym ID and public value of V
i. Two ways could be adopted for TA to validate vehicle’s identities: (
1
) challenge of vehicles’ pseudonym ID; (
2
) validation of public value. The challenge of vehicles’ pseudonym ID could be adopted for RSU validating vehicles’ identities, with the calculation as follows.(1)
The calculation of vehicles validating TA identity:
(
1.1
)
the vehicleV
i selects k
∈
Z
q
*;
(
1.2
)
the vehicleV
i recalculates the first-level pseudonym ID as follows:
(18)
reg
=
H
k
(
I
D
V
i
,
i
)
,
ID
V
i
,
i
′
=
H
(
reg
∥
I
D
TA
,
t
)
.
V
i combines the arithmetic result after experiencing k times of hash with I
D
TA
,
t and then goes through one hash arithmetic to produce the first-level pseudonym ID (I
D
V
i
,
i).
(
1.3
)
The vehicleV
i calculates α
I
D
V
i
,
i
,
γ
I
D
V
i
,
i, and m
I
D
V
i
,
i
=
1
/
H
4
(
ID
V
i
,
i
′
) by formula (14).
(
1.4
)
V
i would utilize TA’s public key to encrypt message M asC, where M
=
k
∥
I
D
V
i
,
i
∥
I
D
V
i
,
p
ID
V
i
,
i
′
∥
α
I
D
V
i
,
i
∥
γ
I
D
V
i
,
i
∥
T
stamp.
(2)
The calculation of RSU validating vehicles’ identities:
(
2.1
)
the vehicleV
i selects r
∈
Z
q
*;
(
2.2
)
the vehicleV
i calculates initializing pseudonym ID to be I
D
V
i
,
p
=
H
(
I
D
V
i
,
i
∥
r
),
whereI
D
V
i
,
p is the pseudonym ID of V
j within R
j range;
(
2.3
)
the vehicleV
i calculates public value (D
I
D
V
i
,
p) used within R
j range;
(
2.4
)
V
i would utilize R
j’s public key to encrypt message M as C
1, where M
=
k
∥
I
D
V
i
,
p
∥
D
I
D
V
i
,
p
∥
T
stamp.V
i would transmit C and C1 to R
j, which would use the common key (S
K
R
j
,
TA) with TA to reencrypt message C by symmetric key encryption and transmit it to TA, and then TA and R
j will validate if the identities are correct, with the calculation as follows.(1)
TA validatesV
i’s identity as follows:
(
1.1
)
TA utilizes private key to decrypt the encrypted messageC;
(
1.2
)
TA utilizesI
D
V
i
,
i to search public value (
D
I
D
V
i
,
i
);
(
1.3
)
TA utilizesk to calculate V
i’s new pseudonym ID, as shown in formula (18);
(
1.4
)
TA calculates the public value of the validated vehicles, as shown in formula (17);
(
1.5
)
if the above is validated correctly, it shows that the identity of the vehicleV
i is correct and TA utilizes the common key (S
K
TA
,
R
j) with R
j to tell R
j that the vehicle V
i is legal;
(
1.6
)
TA restoresV
i’s I
D
V
i
,
i
=
ID
V
i
,
i
′ and I
D
V
i
,
p in table.
(2)
RSU validatesV
i’s identity as follows:
(
2.1
)
R
j receives the message from TA that V
i is legal and R
j utilizes private key to decrypt the encrypted message C
1;
(
2.2
)
R
j calculates V
i’s private communication key as follows:
(19)
e
(
P
U
I
D
R
j
,
t
+
x
I
D
R
j
,
t
·
P
)
·
e
(
P
U
I
D
V
i
,
t
+
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
,
P
)
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
,
where Z
I
D
V
i
,
p is the random number selected by V
i;
(
2.3
)
R
j provides signatures to V
i, with the calculation as follows: r
∈
Z
q
*, U
=
r
·
P, h
=
(
M
,
U
), V
=
r
·
P
U
I
D
R
j
,
t
+
h
·
P
R
I
D
R
j
,
t, message M
=
(
D
I
D
V
i
,
p
∥
T
l
I
D
V
i
,
p
∥
I
D
V
i
,
p
∥
P
D
I
D
R
j
,
t ∥
P
U
I
D
R
j
,
t
∥
I
D
R
j
,
t
∥
T
l
I
D
R
j
,
t
∥
γ
I
D
R
j
,
t
), and the message after signing is Sig
n
R
j
,
V
i
=
(
U
∥
V
∥
M
);
(
2.4
)
R
j utilizes k as the key of symmetric encryption and transmits V
i’s private communication key and R
j’s signature Sig
n
R
j
,
V
i to V
i.R
j would sign public value, pseudonym ID, and key’s validness of the vehicles within the range at the fixed time and transmit the signature to each vehicle within the range. The signature is Sig
n
R
j
,
V
=
(
I
D
V
i
,
p
∥
D
I
D
V
i
,
p
∥
T
l
I
D
V
i
,
p
∥
⋯
∥
I
D
V
m
,
p
∥
D
I
D
V
m
,
p  ∥
T
stamp
), so each vehicle only needs to validate the signature after receiving the signature message and then the public value of each vehicle could be known, with the calculation of signature validation as follows:
(20)
e
(
P
U
I
D
R
j
,
t
,
U
+
h
·
P
D
I
D
R
j
,
t
)
=
e
(
V
,
P
)
.Each vehicle would store the message in the vehicle message table (see Table1).Table 1
Vehicle message table.
Vehicle’s ID
Public value
Valid time
Being legal or not
I
D
V
1
,
p
D
I
D
V
1
,
p
T
l
I
D
V
1
,
p
True
⋯
⋯
⋯
⋯
I
D
V
m
-
1
,
p
D
I
D
V
m
-
1
,
p
T
l
I
D
V
m
-
1
,
p
True
I
D
V
m
,
p
D
I
D
V
m
,
p
T
l
I
D
V
m
,
p
TrueDuring the process, onlyV
i and TA know I
D
V
i
,
i and RSU cannot know I
D
V
i
,
i, so pseudonym and privacy could be attained. After knowing I
D
V
i
,
i, TA could validate V
i’s identity. If V
i is a legal vehicle, RSU would also accept V
i’s second-level initializing pseudonym ID and public value and assist V
i to create RID-key table.


#### 4.3.2. Table Establishment

Each vehicle would have RID-key table (see Table2) and vehicle message table (see Table 1); RID-key table is for storing public value and relevant parameters which vehicles establish for RSU and vehicle message table is for storing public value and relevant parameters of other vehicles. Each RSU has SPID-key for storing vehicles’ public value and relevant parameters and RSU message table (see Table 3) is used for storing the key of private communication between RSU and relevant parameters.Table 2
RID-key table.
ID of RSU
Public value
Pseudonym ID
Random number
Valid time
Being legal or not
R
1
D
I
D
V
i
,
p
′
I
D
V
i
,
p
′
k
′
T
l
I
D
V
i
,
p
′
True
⋯
⋯
⋯
R
j
+
2
D
I
D
V
i
,
p
′
′
I
D
V
i
,
p
′
′
k
′
′
T
l
I
D
V
i
,
p
′
′
True
⋯
⋯
⋯
R
m
D
I
D
V
i
,
p
′
′
′
I
D
V
i
,
p
′
′
′
k
′
′
′
T
l
I
D
V
i
,
p
′
′
′
TrueTable 3
RSU message.
ID of RSU
Public key
Public parameter
Valid time
Legal or illegal
Private communication key
R
1
P
U
I
D
R
1
,
t
PD
I
D
R
1
,
t
′
γ
I
D
R
1
,
t
T
l
I
D
R
1
,
t
True
S
K
R
1
,
R
j
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
R
1
,
t
,
P
)
e
(
P
,
P
)
y
⋯
⋯
⋯
⋯
⋯
⋯
R
m
P
U
I
D
R
m
,
t
PD
I
D
R
m
,
t
′
γ
I
D
R
m
,
t
T
l
I
D
R
m
,
t
True
S
K
R
m
,
R
j
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
R
m
,
t
,
P
)
e
(
P
,
P
)
y
⋯
⋯
⋯
⋯
⋯
⋯After the vehicleV
i and R
j create public value and relevant parameters, V
i begins to produce public value and pseudonym ID close to RSU, with the calculation as follows.(1)
V
i selects k
∈
Z
q
* at random.
(2)
Calculate each RSU’s pseudonym ID as follows:(21)
reg
=
H
k
(
I
D
V
i
,
p
)
,
(22)
ID
V
i
,
p
′
=
H
(
reg
∥
I
D
R
R
)
.
(3)
Calculate each RSU’s public value (D
I
D
V
i
,
p).
(4)
V
i would calculate the common key with R
j as the key of symmetrical encryption, encrypt message M, and transmit it to R
j. The message content comprises each RSU’s public value, random numbers k
∈
Z
q
* and I
D
V
i
,
p, M
=
D
I
D
V
i
,
p
′
∥
k
∥
I
D
V
i
,
p
∥
⋯
∥
D
I
D
V
i
,
p
′′′
∥
k
′′′
∥
I
D
V
i
,
p
∥
T
stamp, and common key, with the calculation as formula (31).
(5)
Then, the vehicle stores relevant parameters in RID table.After receiving the encrypted message ofV
i, R
j would calculate the common key with V
i and only R
j and V
i know the common key, so the message source and integrity could be confirmed. Then, after decrypting message C, R
j would encrypt individual public value, pseudonym ID and random numbers of V
i, and each RSU and transmit them to each RSU. Each RSU receives the message and stores V
i’s public value, pseudonym ID, and random numbers in SPID table, as shown in Table 4. Meanwhile, each RSU would calculate V
i’s pseudonym ID, as shown in formula (18) and R
j would also report illegal RSU and valid time close to RSU to the vehicle V
i, so as to avoid malicious attack.Table 4
SPID-key table.
Pseudonym ID
Public value
Initializing ID
Valid time
Legal or illegal
Random number
I
D
V
1
,
p
′
D
I
D
V
1
,
p
′
I
D
V
1
,
p
T
l
I
D
V
1
,
p
True
k
⋯
⋯
⋯
⋯
⋯
I
D
V
m
,
p
′
′
D
I
D
V
m
,
p
′
′
I
D
V
m
,
p
T
l
I
D
V
m
,
p
True
k
′
′
⋯
⋯
⋯
⋯
⋯
⋯


#### 4.3.3. Handoff Problem

VANET Standard 802.11P [16] is focused on the dedicated short-range communication (DSRC) protocol, which applies to short-range communications. As a result, vehicles use different RSUs to perform handoff when moving at high speed. A problem would be caused; that is, vehicles must revalidate identities mutually with TA and RSU and reestablish a new key. Suppose vehicles establish trusting relationship with each RSU from the beginning; they could know if other RSUs are legal or not and the validity of RSU related key through the trusted RSU and transmit vehicles’ public value and other parameters to other RSUs via the trusted RSU.Suppose the vehicleV
i has already created RID-key table; when V
i is about to enter R
b, it would first check if Table R
b is legal and valid. If it is confirmed legal and valid, V
i would transmit pseudonym ID (I
D
V
i
,
p) and public value (D
I
D
V
i
,
p) to R
b, which would utilize I
D
V
i
,
p to check if V
i is within the valid time and if it is the legal user in SPID table after receiving the message. If it is legal, R
b would calculate V
i’s private communication key and sign to V
i and V
i’s private communication key is calculated as follows: (23)
e
(
P
U
I
D
V
i
,
p
+
x
I
D
R
b
,
p
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
b
,
p
·
P
,
P
)
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
.UseZ
I
D
V
i
,
p
=
k as the symmetrical encryption and transmit private communication key and signature to V
i.OnlyV
i and R
b know k. If the message could be unlocked and represent V
i itself, the identities of both sides could be validated by means of pseudonym ID challenge. If it is validated correctly, R
b would periodically broadcast V
i’s pseudonym ID, public value, and validity by means of signature.


### 4.4. Message Transmission and Validation

This section mainly discusses vehicles’ message broadcasting and validation within RSU range in Section4.4.1, that is, between different RSUs in Section 4.4.2 and the private communication from TA to RSU, from RSU to vehicles, and from vehicle to vehicle in Section 4.4.3.


#### 4.4.1. Message Transmission and Validation within RSU Range

WhenV
i is about to broadcast one message M within R
j communication range, V
i would perform the calculation as follows:
(24)
e
(
P
,
P
)
d
I
D
V
i
,
p
=
e
(
α
I
D
V
i
,
p
·
P
,
1
H
4
(
I
D
V
i
,
p
∥
M
∥
T
stamp
)
·
γ
I
D
V
i
,
p
·
P
)
.V
i would broadcast α
I
D
V
i
,
p
·
P, I
D
V
i
,
p, γ
I
D
V
i
,
p
·
P, T
stamp, and M to the vehicles within the communication range. After receiving the message, other vehicles would check if there is I
D
V
i
,
p’s public value in their own vehicle message table and if they know V
i’s public value, they could validate the message source and integrity through formula (24).Assuming that after vehicleV
j receives a message from V
i, V
j can judge whether message V
i is correct. As the public value of V
i
(
e
(
P
,
P
)
d
I
D
V
i
,
p
) is public, then V
j can determine whether α
I
D
V
i
,
p
·
P, I
D
V
i
,
p, γ
I
D
V
i
,
p
·
P, T
stamp, and M are the message sent by V
i. First calculate 1
/
H
4
(
I
D
V
i
,
p
∥
M
∥
T
stamp
) and then calculate whether e
(
α
I
D
V
i
,
p
·
P
,
(
1
/
H
4
(
I
D
V
i
,
p
∥
M
∥
T
stamp
)
)
·
γ
I
D
V
i
,
p
·
P
)
=
e
(
P
,
P
)
d
I
D
V
i
,
p is correct. If it is correct, it indicates that the message is issued by V
i; otherwise it will be discarded. Since only V
i knows d
I
D
V
i
,
p and e
(
P
,
P
)
d
I
D
V
i
,
p is a problem, it cannot be forged by other vehicles.


#### 4.4.2. Communication between Different RSUs

Two vehicles cannot communicate with each other between different RSUs; the reason lies in that the vehicle’s public value and pseudonym ID are different in different RSUs and vehicles’ public value in each RSU cannot be known between RSUs. Therefore, it is unable to assist vehicles to validate the correctness of the message transmitted from other RSUs. As shown in Figure2,  V
i and V
j are R
a and R
b, respectively, in two different RSUs. When V
i broadcasts a message to V
j, though V
j receives the message, it does not know if public value is owned by itself and it cannot confirm if it is the legal user. In order to resolve the above problem, as shown in Figure 3, (
1
)  V
j first transmits the message to V
i, the message content is request message: R
b
∥
I
D
V
j
,
p
∥
T
stamp, and V
j informs us within different RSUs; (
2
) after the successful entry of R
a identity validation, V
i transmits one signature to V
i and the signature is Sig
n
R
a
→
V
i
=
(
U
∥
V
∥
M
), where M
=
(
D
I
D
V
i
,
p
∥
T
l
I
D
V
i
,
p
∥
I
D
V
i
,
p
∥
P
D
I
D
R
a
,
t
∥
P
U
I
D
R
a
,
t
∥
I
D
R
a
,
t
∥  T
l
I
D
R
a
,
t
∥
γ
I
D
R
a
,
t
). V
i would broadcast signatures to V
j, then V
j could know R
a’s public key and public parameters and validate signatures and R
a’s validity. After the success of validation, V
j could know V
i’s public value and validate the message source and integrity.Figure 2
The communication problem between two vehicles in the different RSU.Figure 3
The solution of the communication problem.


#### 4.4.3. Private Communication

In the following part we will discuss five cases of private communication: Case 1: private communication between TA and RSU, Case 2: private communication between RSU and RSU, Case 3: private communication between vehicle and vehicle, Case 4: private communication between vehicle and RSU, and Case 5: private communication between TA and vehicle.Case  1. Suppose R
j wants to perform private communication with TA; TA has already transmitted private communication key to R
j in Section 4.2.2. First, R
j and TA will validate each other’s identities and key’s validity and R
j would calculate the private communication with TA as follows: (25)
SK
R
j
,
TA
=
e
(
P
U
I
D
R
j
,
t
+
x
I
D
R
j
,
t
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
,
P
)
·
e
(
P
U
I
D
TA
,
t
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
.
Next, TA calculates the private communication with R
j as follows:
(26)
S
K
TA
,
R
j
=
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
·
e
(
P
U
I
D
R
j
,
t
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
,
where P
U
I
D
TA
,
t
=
H
1
(
I
D
TA
), P
U
I
D
R
j
,
t
=
H
1
(
I
D
R
j
); as ID is public, it could be calculated by itself. Therefore, the common key in formulae (25) and (26) is the same and TA and R
j could perform private communication.Case  2. Suppose R
j wants to perform private communication with R
k. First, R
j and R
k will validate each other’s identities and key’s validity and R
j would calculate the private communication with R
k as follows:(27)
S
K
R
j
,
R
k
=
e
(
P
U
I
D
R
j
,
t
+
x
I
D
R
j
,
t
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
,
P
)
·
e
(
P
U
I
D
R
k
,
t
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
P
U
I
D
R
k
,
t
,
P
)
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
R
k
,
t
,
P
)
e
(
y
·
P
,
P
)
.
Next, R
k calculates the private communication with R
j as follows:
(28)
S
K
R
j
,
R
k
=
e
(
P
U
I
D
R
k
,
t
+
x
I
D
R
k
,
t
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
k
,
t
·
P
,
P
)
·
e
(
P
U
I
D
R
j
,
t
,
P
)
=
e
(
P
U
I
D
R
k
,
t
,
P
)
e
(
x
I
D
R
k
,
t
·
P
,
P
)
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
y
·
P
,
P
)
e
(
x
I
D
R
k
,
t
·
P
,
P
)
=
e
(
P
U
I
D
R
k
,
t
,
P
)
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
y
·
P
,
P
)
,
where P
U
I
D
R
k
,
t
=
H
1
(
I
D
R
k
,
t
), P
U
I
D
R
j
,
t
=
H
1
(
I
D
R
j
,
t
); it could be known that the private communication key is the same from the final results.Case  3. Suppose V
i wants to perform private communication with V
j. First, V
i and V
j will validate each other’s identities and key’s validity and V
j would calculate the private communication with V
j as follows:
(29)
S
K
V
i
,
V
j
=
e
(
P
U
I
D
V
i
,
p
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
·
e
(
P
U
I
D
V
j
,
p
,
P
)
=
(
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
×
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
P
U
I
D
V
j
,
p
,
P
)
)
×
(
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
)
-
1
=
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
P
U
I
D
V
j
,
p
,
P
)
e
(
y
·
P
,
P
)
.
Next, V
j calculates the private communication with V
j as follows:
(30)
S
K
V
i
,
V
j
=
e
(
P
U
I
D
V
j
,
p
+
x
I
D
R
k
,
t
·
P
+
Z
I
D
V
j
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
k
,
t
·
P
+
Z
I
D
V
j
,
p
·
P
,
P
)
·
e
(
P
U
I
D
V
i
,
p
,
P
)
=
(
e
(
P
U
I
D
V
j
,
p
,
P
)
e
(
x
I
D
R
k
,
t
·
P
,
P
)
×
e
(
Z
I
D
V
j
,
p
·
P
,
P
)
e
(
P
U
I
D
V
i
,
p
,
P
)
)
×
(
e
(
y
·
P
,
P
)
e
(
x
I
D
R
k
,
t
·
P
,
P
)
e
(
Z
I
D
V
j
,
p
·
P
,
P
)
)
-
1
=
e
(
P
U
I
D
V
j
,
p
,
P
)
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
y
·
P
,
P
)
,
where P
U
I
D
V
j
,
p
=
H
1
(
I
D
V
j
,
p
) and P
U
I
D
V
i
,
p
=
H
1
(
I
D
V
i
,
p
) and it could be known that the private communication key is the same from the final results.Case  4. Suppose V
i wants to perform private communication with R
j. First, V
i and R
j will validate each other’s identities and key’s validity and V
j would calculate the private communication with R
j as follows:
(31)
S
K
V
i
,
R
j
=
e
(
P
U
I
D
V
i
,
p
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
·
e
(
P
U
I
D
R
j
,
t
,
P
)
=
(
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
×
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
P
U
I
D
R
j
,
t
,
P
)
)
×
(
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
)
-
1
=
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
y
·
P
,
P
)
.
Next, R
j calculates the private communication with V
j as follows:
(32)
S
K
R
j
,
V
i
=
e
(
P
U
I
D
R
j
,
t
+
x
I
D
R
j
,
t
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
,
P
)
·
e
(
P
U
I
D
V
i
,
p
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
y
·
P
,
P
)
,
where P
U
I
D
V
i
,
p
=
H
1
(
I
D
V
i
,
p
) and P
U
I
D
R
j
,
t
=
H
1
(
I
D
R
j
,
t
); it could be known from the final results that the private communication key is the same.Case  5. Suppose V
i wants to perform private communication with TA. First, V
i and TA will validate each other’s identities and key’s validity and V
j would calculate the private communication with TA as follows:
(33)
S
K
V
i
,
TA
=
e
(
P
U
I
D
V
i
,
p
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
·
e
(
P
U
I
D
TA
,
t
,
P
)
=
(
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
×
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
P
U
I
D
TA
,
t
,
P
)
)
×
(
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
)
-
1
=
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
.
Next, TA calculates the private communication with V
j as follows:
(34)
S
K
TA
,
V
i
=
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
·
e
(
P
U
I
D
V
i
,
p
,
P
)
=
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
y
·
P
,
P
)
,
where P
U
I
D
V
i
,
p
=
H
1
(
I
D
V
i
,
p
) and P
U
I
D
TA
,
t
=
H
1
(
I
D
TA
,
t
) and it could be known from the final results that the private communication key is the same.From Case 1 to Case 5, it could be known that private communication could be performed among vehicles, RSU or TA, and the private communication key of any vehicle and RSU has the top secrets and their own secrets, so it is impossible to forge any vehicle or RSU, as you must know the top secrets.Though the private communication method costs much more calculation time for the first time, which is spent in validating the other’s identity and calculating the private communication key between them, the calculation time during the communication within the other’s valid time is much less, as the common secret key has already been established, which will not be recalculated until the other’s valid time expires. For the symmetrical encryption, the calculation time is less. For the equipment which often uses private communication, such as RSU to RSU or RSU to TA, the time which private communication spends could be reduced.


### 4.5. Key Updating and Identity Cancellation

When TA’s key validity expires, TA would utilize formula (9) to replace α
I
D
TA
,
t
·
P, γ
I
D
TA
,
t
P, m
I
D
TA
,
t, and T
l
I
D
TA
,
t, which will not influence the communication of RSU and vehicles during the process. TA would use α
I
D
TA
,
t
·
P as the data key (P
D
I
D
TA
,
t), H
1
(
I
D
TA
,
t
)
∈
G
1 is public key (P
U
I
D
TA
,
t), α
I
D
TA
,
t
P
U
I
D
TA
,
t is private key (P
R
I
D
TA
,
t), γ
I
D
TA
,
t
P is another public parameter, T
l
I
D
TA
,
t is TA’s public key, private key, and valid time, and TA makes new parameters public.At RSU’s key updating part, as TA and RSU mainly perform identity validation instead of the message validation among vehicles. IfR
j finds key will expire soon, R
j would calculate the common key (S
K
R
j
,
TA) with TA, as shown in formula (26), and then encrypt message M and transmit to TA, M
=
(
P
D
I
D
R
j
,
t
∥
P
U
I
D
R
j
,
t
∥
γ
I
D
R
j
,
t
∥
T
l
I
D
R
j
,
t
∥
T
stamp
). After receiving the encrypted message, TA would calculate the common key (S
K
R
j
,
TA) with R
j, decrypt the message, and validate R
j’s identity, as shown in formula (13). Next, TA would search table to check if R
j is legal. If it is legal, TA would recalculate R
j’s public key, private key, private communication key, and other parameters and then utilize S
K
TA
,
R
j to encrypt the parameters and transmit them back to R
j. After receiving the message, R
j would reutilize S
K
R
j
,
TA for decryption and revalidating if the parameters are public value (D
I
D
TA
,
t), as shown in formula (13). Thus RSU key updating is completed. During the process, only the vehicle communication within the range would be influenced, and RSU requires retransmitting a new signature to each vehicle.Suppose vehicleV
i is a malicious node; R
m would first utilize Table 5 to search V
i’s initializing pseudonym ID (I
D
V
i
,
p) and then use the common key with each RSU to encrypt I
D
V
i
,
p and transmit to each RSU. Before the receiving, each RSU would first check SPID table and see if there is initializing pseudonym ID. If there is, V
i registration would be forbidden during handoff. After receiving R
m message, TA would first validate if V
i is a malicious node. If it is, TA would search table according to I
D
V
i
,
p and first set V
i’s legality false. When TA revalidates V
i’s identity via RSU (as shown in Section 4.3.1), TA would forbid V
i registration.SupposeR
j is a malicious node; adjacent R
m would directly utilize the common key with TA to encrypt the message and inform TA that R
j is a malicious node. TA would first validate if R
j is a malicious node. If it is, TA would set R
j’s legality in table false and use the common key with RSU to inform all RSUs that R
j is a malicious node, so that malicious RSU or vehicles updating KEY or communication subsequently would be stopped.


## 4.1. System Model

In system environment, as shown in Figure1, we assume that the overall environment only has one TA and TA is the legally binding unit mechanism and in charge of controlling the whole network’s security, which will provide the real identities of malicious nodes for legal prosecution when malicious nodes attack. On the one hand, the role of TA takes charge of validating vehicles or RSU’s identities and on the other hand RSU and relevant coefficients are set by TA and RSU is set up on some common traffic facilities, such as traffic lights. TA and RSU are provided with wire/wireless communication. The communication between TA and RSU adopts wire communication, such as backbone. TA, RSU, and vehicles use short distance wireless communication equipment and the communication between RSU and vehicles adopts wireless communication. The parameters used in the method are described in the Notation section.Figure 1
System environment diagram.


## 4.2. System Initialization

The section introduces the system installation of TA, RSU, and vehicles, which need not any certificates and could validate their own identities only by BDH messages authentication. Meanwhile, key sets the effective time, whose effectiveness could be validated any time.


### 4.2.1. TA System Setup

Suppose the chapter would select five distinct hash functions:H
:
{
0,1
}
*
→
Z
q
*, H
1
:
{
0,1
}
*
→
G
1
*, H
2
:
G
2
→
{
0,1
}
*, H
3
:
G
1
→
{
0,1
}
*, and H
4
:
Wordseries
→
{
0,1
}
*.From the beginning, TA would calculate public value to solve public key, private key, and public parameter of TA as follows.(1)
Supposeα
I
D
TA
,
t
,
γ
I
D
TA
,
t
∈
Z
q
* and m
I
D
TA
,
t
=
H
4
(
I
D
TA
,
t
∥
T
l
I
D
TA
,
t
), where T
l
I
D
TA
,
t is the valid period of key and I
D
TA
,
t is the real ID of TA.
(2)
The calculation public value (D
I
D
TA
,
t) is as follows:
(9)
d
I
D
TA
,
t
=
α
I
D
TA
,
t
*
(
m
I
D
TA
,
t
*
γ
I
D
TA
,
t
)
,
(10)
D
I
D
TA
,
t
=
e
(
d
I
D
TA
,
t
P
,
P
)
=
e
(
P
,
P
)
d
I
D
TA
,
t
,
(11)
D
I
D
TA
,
t
=
e
(
α
I
D
TA
,
t
P
,
m
I
D
TA
,
t
*
γ
I
D
TA
,
t
P
)
.
(3)
Set public keyP
U
I
D
TA
,
t
=
H
1
(
I
D
TA
,
t
)
∈
G
1
*.
(4)
Set private keyP
R
I
D
TA
,
t
=
α
I
D
TA
,
t
P
U
I
D
TA
,
t.
(5)
Set data keyP
D
I
D
TA
,
t
=
α
I
D
TA
,
t
·
P.TA would stored
I
D
TA
,
t and provide it for TA or RSU changing public key and other parameters in the future, which would also make the following parameters (
q, G
1, G
2, e, P, H, H
1, H
2, H
3, H
4, D
I
D
TA
,
t, I
D
TA
,
t, P
D
I
D
TA
,
t, γ
I
D
TA
,
t
P, and T
l
I
D
TA
,
t
) public. When vehicles or RSU want to communicate with TA, it will be first to validate TA’s identity and key’s validness. α
I
D
TA
,
t, γ
I
D
TA
,
t, and d
I
D
TA
,
t cannot be known from the above public parameters. Therefore, malicious attackers couldn’t forge TA and TA does not need any certificates to validate its own identity.


### 4.2.2. RSU System Setup

TA utilizesα
I
D
TA
,
t to set public key, private key, and other parameters of each RSU and selects y
∈
Z
q
* as the master key of private communication. Suppose the number of RSU is m and j
=
1 to m; then the calculation of TA is as follows.(1)
TA selectsx
I
D
R
j
,
t
∈
Z
q
* as the master key of private communication.
(2)
Calculate private communication key ofR
j to be e
(
y
·
P
+
x
R
j
,
t
·
P
,
P
) and e
(
P
U
I
D
R
j
,
t
·
P
+
x
I
D
R
j
,
t
·
P
,
P
).
(3)
Calculate public key, private key, and other parameters ofR
j as follows:
(12)
d
I
D
TA
,
t
=
α
I
D
TA
,
t
*
(
m
I
D
TA
,
t
*
γ
I
D
TA
,
t
)
,
where m
I
D
TA
,
t
=
1
/
H
4
(
I
D
R
j
,
t
∥
T
lifetime
I
D
R
j
,
t
) and I
D
R
j
,
t is the real ID of RSU.
(4)
Set public keyP
U
R
j
,
t
=
H
1
(
I
D
R
j
,
t
).
(5)
Set private keyP
R
R
j
=
α
I
D
TA
,
t
·
P
U
R
j
,
t.
(6)
Set data keyP
D
R
j
,
t
=
α
I
D
TA
,
t
P.TA would create a table to record RSU’s ID, key’s valid time, being legal or not, and RSU’s common key, with the calculation method for common key proposed in Section4.4.3.TA will not giveR
j any certificates and it can validate the identity only by BDH messages authentication. Meanwhile, each RSU’s key has valid time and it could be known whether key is within the valid time only from the identity validation. Any unit could validate RSU or TA’s legitimacy through the following formula, with the calculation as follows:
(13)
D
TA
=
e
(
P
D
u
,
m
u
*
γ
u
P
)
,
where u represents TA or any one RSU.


### 4.2.3. Vehicle System Setup

TA is only in charge of validating vehicles’ identities and public value and it does not produce vehicles’ key, so as to avoid the risk of controlling key. Suppose the number of vehicles ism and i
=
1 to m; then the calculation is as follows.(1)
VehicleV
i would calculate the first-level pseudonym of it and TA’s ID (I
D
V
i
,
i), where I
D
V
i
,
i
=
H
(
I
D
V
i
,
t
∥
I
D
TA
,
t
) and I
D
V
i
,
t is the real ID of the vehicle.
(2)
VehicleV
i would calculate public value of it and TA’s identity validation, with the calculation as follows:
(14)
d
I
D
V
i
,
i
=
α
I
D
V
i
,
i
*
m
I
D
V
i
,
i
*
γ
I
D
V
i
,
i
.
(3)
VehicleV
i utilizes TA’s public key to encrypt message M and transmit it to TA, with the calculation as follows:
(15)
C
=
{
r
·
P
,
M
⊕
H
2
(
e
(
PU
I
D
TA
,
t
,
P
D
I
D
TA
,
t
)
r
)
}
,where r
∈
Z
q
*, M
=
(
D
I
D
V
i
,
i
∥
α
I
D
V
i
,
i
·
P
∥
γ
I
D
V
i
,
i
P
∥
I
D
V
i
,
t
∥
I
D
V
i
,
t
), and V
i transmits the encrypted message C to TA, with the calculation as follows:
(16)
e
(
P
R
I
D
TA
,
t
,
U
)
=
e
(
P
U
I
D
TA
,
t
,
P
D
I
D
TA
,
t
)
r
V
⊕
H
2
(
e
(
P
R
I
D
TA
,
t
,
U
)
)
=
V
⊕
H
2
(
e
(
P
U
I
D
TA
,
t
,
P
D
I
D
TA
,
t
)
r
)
=
M
.TA would validateV
i’s first-level pseudonym ID (I
D
V
i
,
i) and then public value, as shown in the following formula:
(17)
D
I
D
V
i
,
i
=
e
(
α
I
D
V
i
,
i
P
,
m
I
D
V
i
,
i
*
γ
I
D
V
i
,
i
P
)
.


## 4.2.1. TA System Setup

Suppose the chapter would select five distinct hash functions:H
:
{
0,1
}
*
→
Z
q
*, H
1
:
{
0,1
}
*
→
G
1
*, H
2
:
G
2
→
{
0,1
}
*, H
3
:
G
1
→
{
0,1
}
*, and H
4
:
Wordseries
→
{
0,1
}
*.From the beginning, TA would calculate public value to solve public key, private key, and public parameter of TA as follows.(1)
Supposeα
I
D
TA
,
t
,
γ
I
D
TA
,
t
∈
Z
q
* and m
I
D
TA
,
t
=
H
4
(
I
D
TA
,
t
∥
T
l
I
D
TA
,
t
), where T
l
I
D
TA
,
t is the valid period of key and I
D
TA
,
t is the real ID of TA.
(2)
The calculation public value (D
I
D
TA
,
t) is as follows:
(9)
d
I
D
TA
,
t
=
α
I
D
TA
,
t
*
(
m
I
D
TA
,
t
*
γ
I
D
TA
,
t
)
,
(10)
D
I
D
TA
,
t
=
e
(
d
I
D
TA
,
t
P
,
P
)
=
e
(
P
,
P
)
d
I
D
TA
,
t
,
(11)
D
I
D
TA
,
t
=
e
(
α
I
D
TA
,
t
P
,
m
I
D
TA
,
t
*
γ
I
D
TA
,
t
P
)
.
(3)
Set public keyP
U
I
D
TA
,
t
=
H
1
(
I
D
TA
,
t
)
∈
G
1
*.
(4)
Set private keyP
R
I
D
TA
,
t
=
α
I
D
TA
,
t
P
U
I
D
TA
,
t.
(5)
Set data keyP
D
I
D
TA
,
t
=
α
I
D
TA
,
t
·
P.TA would stored
I
D
TA
,
t and provide it for TA or RSU changing public key and other parameters in the future, which would also make the following parameters (
q, G
1, G
2, e, P, H, H
1, H
2, H
3, H
4, D
I
D
TA
,
t, I
D
TA
,
t, P
D
I
D
TA
,
t, γ
I
D
TA
,
t
P, and T
l
I
D
TA
,
t
) public. When vehicles or RSU want to communicate with TA, it will be first to validate TA’s identity and key’s validness. α
I
D
TA
,
t, γ
I
D
TA
,
t, and d
I
D
TA
,
t cannot be known from the above public parameters. Therefore, malicious attackers couldn’t forge TA and TA does not need any certificates to validate its own identity.


## 4.2.2. RSU System Setup

TA utilizesα
I
D
TA
,
t to set public key, private key, and other parameters of each RSU and selects y
∈
Z
q
* as the master key of private communication. Suppose the number of RSU is m and j
=
1 to m; then the calculation of TA is as follows.(1)
TA selectsx
I
D
R
j
,
t
∈
Z
q
* as the master key of private communication.
(2)
Calculate private communication key ofR
j to be e
(
y
·
P
+
x
R
j
,
t
·
P
,
P
) and e
(
P
U
I
D
R
j
,
t
·
P
+
x
I
D
R
j
,
t
·
P
,
P
).
(3)
Calculate public key, private key, and other parameters ofR
j as follows:
(12)
d
I
D
TA
,
t
=
α
I
D
TA
,
t
*
(
m
I
D
TA
,
t
*
γ
I
D
TA
,
t
)
,
where m
I
D
TA
,
t
=
1
/
H
4
(
I
D
R
j
,
t
∥
T
lifetime
I
D
R
j
,
t
) and I
D
R
j
,
t is the real ID of RSU.
(4)
Set public keyP
U
R
j
,
t
=
H
1
(
I
D
R
j
,
t
).
(5)
Set private keyP
R
R
j
=
α
I
D
TA
,
t
·
P
U
R
j
,
t.
(6)
Set data keyP
D
R
j
,
t
=
α
I
D
TA
,
t
P.TA would create a table to record RSU’s ID, key’s valid time, being legal or not, and RSU’s common key, with the calculation method for common key proposed in Section4.4.3.TA will not giveR
j any certificates and it can validate the identity only by BDH messages authentication. Meanwhile, each RSU’s key has valid time and it could be known whether key is within the valid time only from the identity validation. Any unit could validate RSU or TA’s legitimacy through the following formula, with the calculation as follows:
(13)
D
TA
=
e
(
P
D
u
,
m
u
*
γ
u
P
)
,
where u represents TA or any one RSU.


## 4.2.3. Vehicle System Setup

TA is only in charge of validating vehicles’ identities and public value and it does not produce vehicles’ key, so as to avoid the risk of controlling key. Suppose the number of vehicles ism and i
=
1 to m; then the calculation is as follows.(1)
VehicleV
i would calculate the first-level pseudonym of it and TA’s ID (I
D
V
i
,
i), where I
D
V
i
,
i
=
H
(
I
D
V
i
,
t
∥
I
D
TA
,
t
) and I
D
V
i
,
t is the real ID of the vehicle.
(2)
VehicleV
i would calculate public value of it and TA’s identity validation, with the calculation as follows:
(14)
d
I
D
V
i
,
i
=
α
I
D
V
i
,
i
*
m
I
D
V
i
,
i
*
γ
I
D
V
i
,
i
.
(3)
VehicleV
i utilizes TA’s public key to encrypt message M and transmit it to TA, with the calculation as follows:
(15)
C
=
{
r
·
P
,
M
⊕
H
2
(
e
(
PU
I
D
TA
,
t
,
P
D
I
D
TA
,
t
)
r
)
}
,where r
∈
Z
q
*, M
=
(
D
I
D
V
i
,
i
∥
α
I
D
V
i
,
i
·
P
∥
γ
I
D
V
i
,
i
P
∥
I
D
V
i
,
t
∥
I
D
V
i
,
t
), and V
i transmits the encrypted message C to TA, with the calculation as follows:
(16)
e
(
P
R
I
D
TA
,
t
,
U
)
=
e
(
P
U
I
D
TA
,
t
,
P
D
I
D
TA
,
t
)
r
V
⊕
H
2
(
e
(
P
R
I
D
TA
,
t
,
U
)
)
=
V
⊕
H
2
(
e
(
P
U
I
D
TA
,
t
,
P
D
I
D
TA
,
t
)
r
)
=
M
.TA would validateV
i’s first-level pseudonym ID (I
D
V
i
,
i) and then public value, as shown in the following formula:
(17)
D
I
D
V
i
,
i
=
e
(
α
I
D
V
i
,
i
P
,
m
I
D
V
i
,
i
*
γ
I
D
V
i
,
i
P
)
.


## 4.3. Message Broadcast and Message Authentication in RSU

When a vehicle enters RSU region, the vehicle would first check if RID table has already had the message validated mutually with RSU. If there is none, what will be done is to start from Section4.3.1 to carry out identity validation with RSU, create SPID table and RID table with RSU in Section 4.3.2, and then discuss the method of vehicles being handoff at different RSU in Section 4.3.3.


### 4.3.1. Registration

Suppose that when the vehicleV
i enters region R
j and V
i has not created public value related functions and identity validation with R
j, then V
i would utilize TA to validate its own identity, so RSU could believe in the second-level pseudonym ID and public value of V
i. Two ways could be adopted for TA to validate vehicle’s identities: (
1
) challenge of vehicles’ pseudonym ID; (
2
) validation of public value. The challenge of vehicles’ pseudonym ID could be adopted for RSU validating vehicles’ identities, with the calculation as follows.(1)
The calculation of vehicles validating TA identity:
(
1.1
)
the vehicleV
i selects k
∈
Z
q
*;
(
1.2
)
the vehicleV
i recalculates the first-level pseudonym ID as follows:
(18)
reg
=
H
k
(
I
D
V
i
,
i
)
,
ID
V
i
,
i
′
=
H
(
reg
∥
I
D
TA
,
t
)
.
V
i combines the arithmetic result after experiencing k times of hash with I
D
TA
,
t and then goes through one hash arithmetic to produce the first-level pseudonym ID (I
D
V
i
,
i).
(
1.3
)
The vehicleV
i calculates α
I
D
V
i
,
i
,
γ
I
D
V
i
,
i, and m
I
D
V
i
,
i
=
1
/
H
4
(
ID
V
i
,
i
′
) by formula (14).
(
1.4
)
V
i would utilize TA’s public key to encrypt message M asC, where M
=
k
∥
I
D
V
i
,
i
∥
I
D
V
i
,
p
ID
V
i
,
i
′
∥
α
I
D
V
i
,
i
∥
γ
I
D
V
i
,
i
∥
T
stamp.
(2)
The calculation of RSU validating vehicles’ identities:
(
2.1
)
the vehicleV
i selects r
∈
Z
q
*;
(
2.2
)
the vehicleV
i calculates initializing pseudonym ID to be I
D
V
i
,
p
=
H
(
I
D
V
i
,
i
∥
r
),
whereI
D
V
i
,
p is the pseudonym ID of V
j within R
j range;
(
2.3
)
the vehicleV
i calculates public value (D
I
D
V
i
,
p) used within R
j range;
(
2.4
)
V
i would utilize R
j’s public key to encrypt message M as C
1, where M
=
k
∥
I
D
V
i
,
p
∥
D
I
D
V
i
,
p
∥
T
stamp.V
i would transmit C and C1 to R
j, which would use the common key (S
K
R
j
,
TA) with TA to reencrypt message C by symmetric key encryption and transmit it to TA, and then TA and R
j will validate if the identities are correct, with the calculation as follows.(1)
TA validatesV
i’s identity as follows:
(
1.1
)
TA utilizes private key to decrypt the encrypted messageC;
(
1.2
)
TA utilizesI
D
V
i
,
i to search public value (
D
I
D
V
i
,
i
);
(
1.3
)
TA utilizesk to calculate V
i’s new pseudonym ID, as shown in formula (18);
(
1.4
)
TA calculates the public value of the validated vehicles, as shown in formula (17);
(
1.5
)
if the above is validated correctly, it shows that the identity of the vehicleV
i is correct and TA utilizes the common key (S
K
TA
,
R
j) with R
j to tell R
j that the vehicle V
i is legal;
(
1.6
)
TA restoresV
i’s I
D
V
i
,
i
=
ID
V
i
,
i
′ and I
D
V
i
,
p in table.
(2)
RSU validatesV
i’s identity as follows:
(
2.1
)
R
j receives the message from TA that V
i is legal and R
j utilizes private key to decrypt the encrypted message C
1;
(
2.2
)
R
j calculates V
i’s private communication key as follows:
(19)
e
(
P
U
I
D
R
j
,
t
+
x
I
D
R
j
,
t
·
P
)
·
e
(
P
U
I
D
V
i
,
t
+
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
,
P
)
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
,
where Z
I
D
V
i
,
p is the random number selected by V
i;
(
2.3
)
R
j provides signatures to V
i, with the calculation as follows: r
∈
Z
q
*, U
=
r
·
P, h
=
(
M
,
U
), V
=
r
·
P
U
I
D
R
j
,
t
+
h
·
P
R
I
D
R
j
,
t, message M
=
(
D
I
D
V
i
,
p
∥
T
l
I
D
V
i
,
p
∥
I
D
V
i
,
p
∥
P
D
I
D
R
j
,
t ∥
P
U
I
D
R
j
,
t
∥
I
D
R
j
,
t
∥
T
l
I
D
R
j
,
t
∥
γ
I
D
R
j
,
t
), and the message after signing is Sig
n
R
j
,
V
i
=
(
U
∥
V
∥
M
);
(
2.4
)
R
j utilizes k as the key of symmetric encryption and transmits V
i’s private communication key and R
j’s signature Sig
n
R
j
,
V
i to V
i.R
j would sign public value, pseudonym ID, and key’s validness of the vehicles within the range at the fixed time and transmit the signature to each vehicle within the range. The signature is Sig
n
R
j
,
V
=
(
I
D
V
i
,
p
∥
D
I
D
V
i
,
p
∥
T
l
I
D
V
i
,
p
∥
⋯
∥
I
D
V
m
,
p
∥
D
I
D
V
m
,
p  ∥
T
stamp
), so each vehicle only needs to validate the signature after receiving the signature message and then the public value of each vehicle could be known, with the calculation of signature validation as follows:
(20)
e
(
P
U
I
D
R
j
,
t
,
U
+
h
·
P
D
I
D
R
j
,
t
)
=
e
(
V
,
P
)
.Each vehicle would store the message in the vehicle message table (see Table1).Table 1
Vehicle message table.
Vehicle’s ID
Public value
Valid time
Being legal or not
I
D
V
1
,
p
D
I
D
V
1
,
p
T
l
I
D
V
1
,
p
True
⋯
⋯
⋯
⋯
I
D
V
m
-
1
,
p
D
I
D
V
m
-
1
,
p
T
l
I
D
V
m
-
1
,
p
True
I
D
V
m
,
p
D
I
D
V
m
,
p
T
l
I
D
V
m
,
p
TrueDuring the process, onlyV
i and TA know I
D
V
i
,
i and RSU cannot know I
D
V
i
,
i, so pseudonym and privacy could be attained. After knowing I
D
V
i
,
i, TA could validate V
i’s identity. If V
i is a legal vehicle, RSU would also accept V
i’s second-level initializing pseudonym ID and public value and assist V
i to create RID-key table.


### 4.3.2. Table Establishment

Each vehicle would have RID-key table (see Table2) and vehicle message table (see Table 1); RID-key table is for storing public value and relevant parameters which vehicles establish for RSU and vehicle message table is for storing public value and relevant parameters of other vehicles. Each RSU has SPID-key for storing vehicles’ public value and relevant parameters and RSU message table (see Table 3) is used for storing the key of private communication between RSU and relevant parameters.Table 2
RID-key table.
ID of RSU
Public value
Pseudonym ID
Random number
Valid time
Being legal or not
R
1
D
I
D
V
i
,
p
′
I
D
V
i
,
p
′
k
′
T
l
I
D
V
i
,
p
′
True
⋯
⋯
⋯
R
j
+
2
D
I
D
V
i
,
p
′
′
I
D
V
i
,
p
′
′
k
′
′
T
l
I
D
V
i
,
p
′
′
True
⋯
⋯
⋯
R
m
D
I
D
V
i
,
p
′
′
′
I
D
V
i
,
p
′
′
′
k
′
′
′
T
l
I
D
V
i
,
p
′
′
′
TrueTable 3
RSU message.
ID of RSU
Public key
Public parameter
Valid time
Legal or illegal
Private communication key
R
1
P
U
I
D
R
1
,
t
PD
I
D
R
1
,
t
′
γ
I
D
R
1
,
t
T
l
I
D
R
1
,
t
True
S
K
R
1
,
R
j
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
R
1
,
t
,
P
)
e
(
P
,
P
)
y
⋯
⋯
⋯
⋯
⋯
⋯
R
m
P
U
I
D
R
m
,
t
PD
I
D
R
m
,
t
′
γ
I
D
R
m
,
t
T
l
I
D
R
m
,
t
True
S
K
R
m
,
R
j
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
R
m
,
t
,
P
)
e
(
P
,
P
)
y
⋯
⋯
⋯
⋯
⋯
⋯After the vehicleV
i and R
j create public value and relevant parameters, V
i begins to produce public value and pseudonym ID close to RSU, with the calculation as follows.(1)
V
i selects k
∈
Z
q
* at random.
(2)
Calculate each RSU’s pseudonym ID as follows:(21)
reg
=
H
k
(
I
D
V
i
,
p
)
,
(22)
ID
V
i
,
p
′
=
H
(
reg
∥
I
D
R
R
)
.
(3)
Calculate each RSU’s public value (D
I
D
V
i
,
p).
(4)
V
i would calculate the common key with R
j as the key of symmetrical encryption, encrypt message M, and transmit it to R
j. The message content comprises each RSU’s public value, random numbers k
∈
Z
q
* and I
D
V
i
,
p, M
=
D
I
D
V
i
,
p
′
∥
k
∥
I
D
V
i
,
p
∥
⋯
∥
D
I
D
V
i
,
p
′′′
∥
k
′′′
∥
I
D
V
i
,
p
∥
T
stamp, and common key, with the calculation as formula (31).
(5)
Then, the vehicle stores relevant parameters in RID table.After receiving the encrypted message ofV
i, R
j would calculate the common key with V
i and only R
j and V
i know the common key, so the message source and integrity could be confirmed. Then, after decrypting message C, R
j would encrypt individual public value, pseudonym ID and random numbers of V
i, and each RSU and transmit them to each RSU. Each RSU receives the message and stores V
i’s public value, pseudonym ID, and random numbers in SPID table, as shown in Table 4. Meanwhile, each RSU would calculate V
i’s pseudonym ID, as shown in formula (18) and R
j would also report illegal RSU and valid time close to RSU to the vehicle V
i, so as to avoid malicious attack.Table 4
SPID-key table.
Pseudonym ID
Public value
Initializing ID
Valid time
Legal or illegal
Random number
I
D
V
1
,
p
′
D
I
D
V
1
,
p
′
I
D
V
1
,
p
T
l
I
D
V
1
,
p
True
k
⋯
⋯
⋯
⋯
⋯
I
D
V
m
,
p
′
′
D
I
D
V
m
,
p
′
′
I
D
V
m
,
p
T
l
I
D
V
m
,
p
True
k
′
′
⋯
⋯
⋯
⋯
⋯
⋯


### 4.3.3. Handoff Problem

VANET Standard 802.11P [16] is focused on the dedicated short-range communication (DSRC) protocol, which applies to short-range communications. As a result, vehicles use different RSUs to perform handoff when moving at high speed. A problem would be caused; that is, vehicles must revalidate identities mutually with TA and RSU and reestablish a new key. Suppose vehicles establish trusting relationship with each RSU from the beginning; they could know if other RSUs are legal or not and the validity of RSU related key through the trusted RSU and transmit vehicles’ public value and other parameters to other RSUs via the trusted RSU.Suppose the vehicleV
i has already created RID-key table; when V
i is about to enter R
b, it would first check if Table R
b is legal and valid. If it is confirmed legal and valid, V
i would transmit pseudonym ID (I
D
V
i
,
p) and public value (D
I
D
V
i
,
p) to R
b, which would utilize I
D
V
i
,
p to check if V
i is within the valid time and if it is the legal user in SPID table after receiving the message. If it is legal, R
b would calculate V
i’s private communication key and sign to V
i and V
i’s private communication key is calculated as follows: (23)
e
(
P
U
I
D
V
i
,
p
+
x
I
D
R
b
,
p
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
b
,
p
·
P
,
P
)
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
.UseZ
I
D
V
i
,
p
=
k as the symmetrical encryption and transmit private communication key and signature to V
i.OnlyV
i and R
b know k. If the message could be unlocked and represent V
i itself, the identities of both sides could be validated by means of pseudonym ID challenge. If it is validated correctly, R
b would periodically broadcast V
i’s pseudonym ID, public value, and validity by means of signature.


## 4.3.1. Registration

Suppose that when the vehicleV
i enters region R
j and V
i has not created public value related functions and identity validation with R
j, then V
i would utilize TA to validate its own identity, so RSU could believe in the second-level pseudonym ID and public value of V
i. Two ways could be adopted for TA to validate vehicle’s identities: (
1
) challenge of vehicles’ pseudonym ID; (
2
) validation of public value. The challenge of vehicles’ pseudonym ID could be adopted for RSU validating vehicles’ identities, with the calculation as follows.(1)
The calculation of vehicles validating TA identity:
(
1.1
)
the vehicleV
i selects k
∈
Z
q
*;
(
1.2
)
the vehicleV
i recalculates the first-level pseudonym ID as follows:
(18)
reg
=
H
k
(
I
D
V
i
,
i
)
,
ID
V
i
,
i
′
=
H
(
reg
∥
I
D
TA
,
t
)
.
V
i combines the arithmetic result after experiencing k times of hash with I
D
TA
,
t and then goes through one hash arithmetic to produce the first-level pseudonym ID (I
D
V
i
,
i).
(
1.3
)
The vehicleV
i calculates α
I
D
V
i
,
i
,
γ
I
D
V
i
,
i, and m
I
D
V
i
,
i
=
1
/
H
4
(
ID
V
i
,
i
′
) by formula (14).
(
1.4
)
V
i would utilize TA’s public key to encrypt message M asC, where M
=
k
∥
I
D
V
i
,
i
∥
I
D
V
i
,
p
ID
V
i
,
i
′
∥
α
I
D
V
i
,
i
∥
γ
I
D
V
i
,
i
∥
T
stamp.
(2)
The calculation of RSU validating vehicles’ identities:
(
2.1
)
the vehicleV
i selects r
∈
Z
q
*;
(
2.2
)
the vehicleV
i calculates initializing pseudonym ID to be I
D
V
i
,
p
=
H
(
I
D
V
i
,
i
∥
r
),
whereI
D
V
i
,
p is the pseudonym ID of V
j within R
j range;
(
2.3
)
the vehicleV
i calculates public value (D
I
D
V
i
,
p) used within R
j range;
(
2.4
)
V
i would utilize R
j’s public key to encrypt message M as C
1, where M
=
k
∥
I
D
V
i
,
p
∥
D
I
D
V
i
,
p
∥
T
stamp.V
i would transmit C and C1 to R
j, which would use the common key (S
K
R
j
,
TA) with TA to reencrypt message C by symmetric key encryption and transmit it to TA, and then TA and R
j will validate if the identities are correct, with the calculation as follows.(1)
TA validatesV
i’s identity as follows:
(
1.1
)
TA utilizes private key to decrypt the encrypted messageC;
(
1.2
)
TA utilizesI
D
V
i
,
i to search public value (
D
I
D
V
i
,
i
);
(
1.3
)
TA utilizesk to calculate V
i’s new pseudonym ID, as shown in formula (18);
(
1.4
)
TA calculates the public value of the validated vehicles, as shown in formula (17);
(
1.5
)
if the above is validated correctly, it shows that the identity of the vehicleV
i is correct and TA utilizes the common key (S
K
TA
,
R
j) with R
j to tell R
j that the vehicle V
i is legal;
(
1.6
)
TA restoresV
i’s I
D
V
i
,
i
=
ID
V
i
,
i
′ and I
D
V
i
,
p in table.
(2)
RSU validatesV
i’s identity as follows:
(
2.1
)
R
j receives the message from TA that V
i is legal and R
j utilizes private key to decrypt the encrypted message C
1;
(
2.2
)
R
j calculates V
i’s private communication key as follows:
(19)
e
(
P
U
I
D
R
j
,
t
+
x
I
D
R
j
,
t
·
P
)
·
e
(
P
U
I
D
V
i
,
t
+
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
,
P
)
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
,
where Z
I
D
V
i
,
p is the random number selected by V
i;
(
2.3
)
R
j provides signatures to V
i, with the calculation as follows: r
∈
Z
q
*, U
=
r
·
P, h
=
(
M
,
U
), V
=
r
·
P
U
I
D
R
j
,
t
+
h
·
P
R
I
D
R
j
,
t, message M
=
(
D
I
D
V
i
,
p
∥
T
l
I
D
V
i
,
p
∥
I
D
V
i
,
p
∥
P
D
I
D
R
j
,
t ∥
P
U
I
D
R
j
,
t
∥
I
D
R
j
,
t
∥
T
l
I
D
R
j
,
t
∥
γ
I
D
R
j
,
t
), and the message after signing is Sig
n
R
j
,
V
i
=
(
U
∥
V
∥
M
);
(
2.4
)
R
j utilizes k as the key of symmetric encryption and transmits V
i’s private communication key and R
j’s signature Sig
n
R
j
,
V
i to V
i.R
j would sign public value, pseudonym ID, and key’s validness of the vehicles within the range at the fixed time and transmit the signature to each vehicle within the range. The signature is Sig
n
R
j
,
V
=
(
I
D
V
i
,
p
∥
D
I
D
V
i
,
p
∥
T
l
I
D
V
i
,
p
∥
⋯
∥
I
D
V
m
,
p
∥
D
I
D
V
m
,
p  ∥
T
stamp
), so each vehicle only needs to validate the signature after receiving the signature message and then the public value of each vehicle could be known, with the calculation of signature validation as follows:
(20)
e
(
P
U
I
D
R
j
,
t
,
U
+
h
·
P
D
I
D
R
j
,
t
)
=
e
(
V
,
P
)
.Each vehicle would store the message in the vehicle message table (see Table1).Table 1
Vehicle message table.
Vehicle’s ID
Public value
Valid time
Being legal or not
I
D
V
1
,
p
D
I
D
V
1
,
p
T
l
I
D
V
1
,
p
True
⋯
⋯
⋯
⋯
I
D
V
m
-
1
,
p
D
I
D
V
m
-
1
,
p
T
l
I
D
V
m
-
1
,
p
True
I
D
V
m
,
p
D
I
D
V
m
,
p
T
l
I
D
V
m
,
p
TrueDuring the process, onlyV
i and TA know I
D
V
i
,
i and RSU cannot know I
D
V
i
,
i, so pseudonym and privacy could be attained. After knowing I
D
V
i
,
i, TA could validate V
i’s identity. If V
i is a legal vehicle, RSU would also accept V
i’s second-level initializing pseudonym ID and public value and assist V
i to create RID-key table.


## 4.3.2. Table Establishment

Each vehicle would have RID-key table (see Table2) and vehicle message table (see Table 1); RID-key table is for storing public value and relevant parameters which vehicles establish for RSU and vehicle message table is for storing public value and relevant parameters of other vehicles. Each RSU has SPID-key for storing vehicles’ public value and relevant parameters and RSU message table (see Table 3) is used for storing the key of private communication between RSU and relevant parameters.Table 2
RID-key table.
ID of RSU
Public value
Pseudonym ID
Random number
Valid time
Being legal or not
R
1
D
I
D
V
i
,
p
′
I
D
V
i
,
p
′
k
′
T
l
I
D
V
i
,
p
′
True
⋯
⋯
⋯
R
j
+
2
D
I
D
V
i
,
p
′
′
I
D
V
i
,
p
′
′
k
′
′
T
l
I
D
V
i
,
p
′
′
True
⋯
⋯
⋯
R
m
D
I
D
V
i
,
p
′
′
′
I
D
V
i
,
p
′
′
′
k
′
′
′
T
l
I
D
V
i
,
p
′
′
′
TrueTable 3
RSU message.
ID of RSU
Public key
Public parameter
Valid time
Legal or illegal
Private communication key
R
1
P
U
I
D
R
1
,
t
PD
I
D
R
1
,
t
′
γ
I
D
R
1
,
t
T
l
I
D
R
1
,
t
True
S
K
R
1
,
R
j
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
R
1
,
t
,
P
)
e
(
P
,
P
)
y
⋯
⋯
⋯
⋯
⋯
⋯
R
m
P
U
I
D
R
m
,
t
PD
I
D
R
m
,
t
′
γ
I
D
R
m
,
t
T
l
I
D
R
m
,
t
True
S
K
R
m
,
R
j
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
R
m
,
t
,
P
)
e
(
P
,
P
)
y
⋯
⋯
⋯
⋯
⋯
⋯After the vehicleV
i and R
j create public value and relevant parameters, V
i begins to produce public value and pseudonym ID close to RSU, with the calculation as follows.(1)
V
i selects k
∈
Z
q
* at random.
(2)
Calculate each RSU’s pseudonym ID as follows:(21)
reg
=
H
k
(
I
D
V
i
,
p
)
,
(22)
ID
V
i
,
p
′
=
H
(
reg
∥
I
D
R
R
)
.
(3)
Calculate each RSU’s public value (D
I
D
V
i
,
p).
(4)
V
i would calculate the common key with R
j as the key of symmetrical encryption, encrypt message M, and transmit it to R
j. The message content comprises each RSU’s public value, random numbers k
∈
Z
q
* and I
D
V
i
,
p, M
=
D
I
D
V
i
,
p
′
∥
k
∥
I
D
V
i
,
p
∥
⋯
∥
D
I
D
V
i
,
p
′′′
∥
k
′′′
∥
I
D
V
i
,
p
∥
T
stamp, and common key, with the calculation as formula (31).
(5)
Then, the vehicle stores relevant parameters in RID table.After receiving the encrypted message ofV
i, R
j would calculate the common key with V
i and only R
j and V
i know the common key, so the message source and integrity could be confirmed. Then, after decrypting message C, R
j would encrypt individual public value, pseudonym ID and random numbers of V
i, and each RSU and transmit them to each RSU. Each RSU receives the message and stores V
i’s public value, pseudonym ID, and random numbers in SPID table, as shown in Table 4. Meanwhile, each RSU would calculate V
i’s pseudonym ID, as shown in formula (18) and R
j would also report illegal RSU and valid time close to RSU to the vehicle V
i, so as to avoid malicious attack.Table 4
SPID-key table.
Pseudonym ID
Public value
Initializing ID
Valid time
Legal or illegal
Random number
I
D
V
1
,
p
′
D
I
D
V
1
,
p
′
I
D
V
1
,
p
T
l
I
D
V
1
,
p
True
k
⋯
⋯
⋯
⋯
⋯
I
D
V
m
,
p
′
′
D
I
D
V
m
,
p
′
′
I
D
V
m
,
p
T
l
I
D
V
m
,
p
True
k
′
′
⋯
⋯
⋯
⋯
⋯
⋯


## 4.3.3. Handoff Problem

VANET Standard 802.11P [16] is focused on the dedicated short-range communication (DSRC) protocol, which applies to short-range communications. As a result, vehicles use different RSUs to perform handoff when moving at high speed. A problem would be caused; that is, vehicles must revalidate identities mutually with TA and RSU and reestablish a new key. Suppose vehicles establish trusting relationship with each RSU from the beginning; they could know if other RSUs are legal or not and the validity of RSU related key through the trusted RSU and transmit vehicles’ public value and other parameters to other RSUs via the trusted RSU.Suppose the vehicleV
i has already created RID-key table; when V
i is about to enter R
b, it would first check if Table R
b is legal and valid. If it is confirmed legal and valid, V
i would transmit pseudonym ID (I
D
V
i
,
p) and public value (D
I
D
V
i
,
p) to R
b, which would utilize I
D
V
i
,
p to check if V
i is within the valid time and if it is the legal user in SPID table after receiving the message. If it is legal, R
b would calculate V
i’s private communication key and sign to V
i and V
i’s private communication key is calculated as follows: (23)
e
(
P
U
I
D
V
i
,
p
+
x
I
D
R
b
,
p
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
b
,
p
·
P
,
P
)
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
.UseZ
I
D
V
i
,
p
=
k as the symmetrical encryption and transmit private communication key and signature to V
i.OnlyV
i and R
b know k. If the message could be unlocked and represent V
i itself, the identities of both sides could be validated by means of pseudonym ID challenge. If it is validated correctly, R
b would periodically broadcast V
i’s pseudonym ID, public value, and validity by means of signature.


## 4.4. Message Transmission and Validation

This section mainly discusses vehicles’ message broadcasting and validation within RSU range in Section4.4.1, that is, between different RSUs in Section 4.4.2 and the private communication from TA to RSU, from RSU to vehicles, and from vehicle to vehicle in Section 4.4.3.


### 4.4.1. Message Transmission and Validation within RSU Range

WhenV
i is about to broadcast one message M within R
j communication range, V
i would perform the calculation as follows:
(24)
e
(
P
,
P
)
d
I
D
V
i
,
p
=
e
(
α
I
D
V
i
,
p
·
P
,
1
H
4
(
I
D
V
i
,
p
∥
M
∥
T
stamp
)
·
γ
I
D
V
i
,
p
·
P
)
.V
i would broadcast α
I
D
V
i
,
p
·
P, I
D
V
i
,
p, γ
I
D
V
i
,
p
·
P, T
stamp, and M to the vehicles within the communication range. After receiving the message, other vehicles would check if there is I
D
V
i
,
p’s public value in their own vehicle message table and if they know V
i’s public value, they could validate the message source and integrity through formula (24).Assuming that after vehicleV
j receives a message from V
i, V
j can judge whether message V
i is correct. As the public value of V
i
(
e
(
P
,
P
)
d
I
D
V
i
,
p
) is public, then V
j can determine whether α
I
D
V
i
,
p
·
P, I
D
V
i
,
p, γ
I
D
V
i
,
p
·
P, T
stamp, and M are the message sent by V
i. First calculate 1
/
H
4
(
I
D
V
i
,
p
∥
M
∥
T
stamp
) and then calculate whether e
(
α
I
D
V
i
,
p
·
P
,
(
1
/
H
4
(
I
D
V
i
,
p
∥
M
∥
T
stamp
)
)
·
γ
I
D
V
i
,
p
·
P
)
=
e
(
P
,
P
)
d
I
D
V
i
,
p is correct. If it is correct, it indicates that the message is issued by V
i; otherwise it will be discarded. Since only V
i knows d
I
D
V
i
,
p and e
(
P
,
P
)
d
I
D
V
i
,
p is a problem, it cannot be forged by other vehicles.


### 4.4.2. Communication between Different RSUs

Two vehicles cannot communicate with each other between different RSUs; the reason lies in that the vehicle’s public value and pseudonym ID are different in different RSUs and vehicles’ public value in each RSU cannot be known between RSUs. Therefore, it is unable to assist vehicles to validate the correctness of the message transmitted from other RSUs. As shown in Figure2,  V
i and V
j are R
a and R
b, respectively, in two different RSUs. When V
i broadcasts a message to V
j, though V
j receives the message, it does not know if public value is owned by itself and it cannot confirm if it is the legal user. In order to resolve the above problem, as shown in Figure 3, (
1
)  V
j first transmits the message to V
i, the message content is request message: R
b
∥
I
D
V
j
,
p
∥
T
stamp, and V
j informs us within different RSUs; (
2
) after the successful entry of R
a identity validation, V
i transmits one signature to V
i and the signature is Sig
n
R
a
→
V
i
=
(
U
∥
V
∥
M
), where M
=
(
D
I
D
V
i
,
p
∥
T
l
I
D
V
i
,
p
∥
I
D
V
i
,
p
∥
P
D
I
D
R
a
,
t
∥
P
U
I
D
R
a
,
t
∥
I
D
R
a
,
t
∥  T
l
I
D
R
a
,
t
∥
γ
I
D
R
a
,
t
). V
i would broadcast signatures to V
j, then V
j could know R
a’s public key and public parameters and validate signatures and R
a’s validity. After the success of validation, V
j could know V
i’s public value and validate the message source and integrity.Figure 2
The communication problem between two vehicles in the different RSU.Figure 3
The solution of the communication problem.


### 4.4.3. Private Communication

In the following part we will discuss five cases of private communication: Case 1: private communication between TA and RSU, Case 2: private communication between RSU and RSU, Case 3: private communication between vehicle and vehicle, Case 4: private communication between vehicle and RSU, and Case 5: private communication between TA and vehicle.Case  1. Suppose R
j wants to perform private communication with TA; TA has already transmitted private communication key to R
j in Section 4.2.2. First, R
j and TA will validate each other’s identities and key’s validity and R
j would calculate the private communication with TA as follows: (25)
SK
R
j
,
TA
=
e
(
P
U
I
D
R
j
,
t
+
x
I
D
R
j
,
t
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
,
P
)
·
e
(
P
U
I
D
TA
,
t
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
.
Next, TA calculates the private communication with R
j as follows:
(26)
S
K
TA
,
R
j
=
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
·
e
(
P
U
I
D
R
j
,
t
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
,
where P
U
I
D
TA
,
t
=
H
1
(
I
D
TA
), P
U
I
D
R
j
,
t
=
H
1
(
I
D
R
j
); as ID is public, it could be calculated by itself. Therefore, the common key in formulae (25) and (26) is the same and TA and R
j could perform private communication.Case  2. Suppose R
j wants to perform private communication with R
k. First, R
j and R
k will validate each other’s identities and key’s validity and R
j would calculate the private communication with R
k as follows:(27)
S
K
R
j
,
R
k
=
e
(
P
U
I
D
R
j
,
t
+
x
I
D
R
j
,
t
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
,
P
)
·
e
(
P
U
I
D
R
k
,
t
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
P
U
I
D
R
k
,
t
,
P
)
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
R
k
,
t
,
P
)
e
(
y
·
P
,
P
)
.
Next, R
k calculates the private communication with R
j as follows:
(28)
S
K
R
j
,
R
k
=
e
(
P
U
I
D
R
k
,
t
+
x
I
D
R
k
,
t
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
k
,
t
·
P
,
P
)
·
e
(
P
U
I
D
R
j
,
t
,
P
)
=
e
(
P
U
I
D
R
k
,
t
,
P
)
e
(
x
I
D
R
k
,
t
·
P
,
P
)
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
y
·
P
,
P
)
e
(
x
I
D
R
k
,
t
·
P
,
P
)
=
e
(
P
U
I
D
R
k
,
t
,
P
)
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
y
·
P
,
P
)
,
where P
U
I
D
R
k
,
t
=
H
1
(
I
D
R
k
,
t
), P
U
I
D
R
j
,
t
=
H
1
(
I
D
R
j
,
t
); it could be known that the private communication key is the same from the final results.Case  3. Suppose V
i wants to perform private communication with V
j. First, V
i and V
j will validate each other’s identities and key’s validity and V
j would calculate the private communication with V
j as follows:
(29)
S
K
V
i
,
V
j
=
e
(
P
U
I
D
V
i
,
p
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
·
e
(
P
U
I
D
V
j
,
p
,
P
)
=
(
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
×
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
P
U
I
D
V
j
,
p
,
P
)
)
×
(
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
)
-
1
=
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
P
U
I
D
V
j
,
p
,
P
)
e
(
y
·
P
,
P
)
.
Next, V
j calculates the private communication with V
j as follows:
(30)
S
K
V
i
,
V
j
=
e
(
P
U
I
D
V
j
,
p
+
x
I
D
R
k
,
t
·
P
+
Z
I
D
V
j
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
k
,
t
·
P
+
Z
I
D
V
j
,
p
·
P
,
P
)
·
e
(
P
U
I
D
V
i
,
p
,
P
)
=
(
e
(
P
U
I
D
V
j
,
p
,
P
)
e
(
x
I
D
R
k
,
t
·
P
,
P
)
×
e
(
Z
I
D
V
j
,
p
·
P
,
P
)
e
(
P
U
I
D
V
i
,
p
,
P
)
)
×
(
e
(
y
·
P
,
P
)
e
(
x
I
D
R
k
,
t
·
P
,
P
)
e
(
Z
I
D
V
j
,
p
·
P
,
P
)
)
-
1
=
e
(
P
U
I
D
V
j
,
p
,
P
)
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
y
·
P
,
P
)
,
where P
U
I
D
V
j
,
p
=
H
1
(
I
D
V
j
,
p
) and P
U
I
D
V
i
,
p
=
H
1
(
I
D
V
i
,
p
) and it could be known that the private communication key is the same from the final results.Case  4. Suppose V
i wants to perform private communication with R
j. First, V
i and R
j will validate each other’s identities and key’s validity and V
j would calculate the private communication with R
j as follows:
(31)
S
K
V
i
,
R
j
=
e
(
P
U
I
D
V
i
,
p
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
·
e
(
P
U
I
D
R
j
,
t
,
P
)
=
(
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
×
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
P
U
I
D
R
j
,
t
,
P
)
)
×
(
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
)
-
1
=
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
y
·
P
,
P
)
.
Next, R
j calculates the private communication with V
j as follows:
(32)
S
K
R
j
,
V
i
=
e
(
P
U
I
D
R
j
,
t
+
x
I
D
R
j
,
t
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
,
P
)
·
e
(
P
U
I
D
V
i
,
p
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
y
·
P
,
P
)
,
where P
U
I
D
V
i
,
p
=
H
1
(
I
D
V
i
,
p
) and P
U
I
D
R
j
,
t
=
H
1
(
I
D
R
j
,
t
); it could be known from the final results that the private communication key is the same.Case  5. Suppose V
i wants to perform private communication with TA. First, V
i and TA will validate each other’s identities and key’s validity and V
j would calculate the private communication with TA as follows:
(33)
S
K
V
i
,
TA
=
e
(
P
U
I
D
V
i
,
p
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
·
e
(
P
U
I
D
TA
,
t
,
P
)
=
(
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
×
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
P
U
I
D
TA
,
t
,
P
)
)
×
(
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
)
-
1
=
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
.
Next, TA calculates the private communication with V
j as follows:
(34)
S
K
TA
,
V
i
=
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
·
e
(
P
U
I
D
V
i
,
p
,
P
)
=
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
y
·
P
,
P
)
,
where P
U
I
D
V
i
,
p
=
H
1
(
I
D
V
i
,
p
) and P
U
I
D
TA
,
t
=
H
1
(
I
D
TA
,
t
) and it could be known from the final results that the private communication key is the same.From Case 1 to Case 5, it could be known that private communication could be performed among vehicles, RSU or TA, and the private communication key of any vehicle and RSU has the top secrets and their own secrets, so it is impossible to forge any vehicle or RSU, as you must know the top secrets.Though the private communication method costs much more calculation time for the first time, which is spent in validating the other’s identity and calculating the private communication key between them, the calculation time during the communication within the other’s valid time is much less, as the common secret key has already been established, which will not be recalculated until the other’s valid time expires. For the symmetrical encryption, the calculation time is less. For the equipment which often uses private communication, such as RSU to RSU or RSU to TA, the time which private communication spends could be reduced.


## 4.4.1. Message Transmission and Validation within RSU Range

WhenV
i is about to broadcast one message M within R
j communication range, V
i would perform the calculation as follows:
(24)
e
(
P
,
P
)
d
I
D
V
i
,
p
=
e
(
α
I
D
V
i
,
p
·
P
,
1
H
4
(
I
D
V
i
,
p
∥
M
∥
T
stamp
)
·
γ
I
D
V
i
,
p
·
P
)
.V
i would broadcast α
I
D
V
i
,
p
·
P, I
D
V
i
,
p, γ
I
D
V
i
,
p
·
P, T
stamp, and M to the vehicles within the communication range. After receiving the message, other vehicles would check if there is I
D
V
i
,
p’s public value in their own vehicle message table and if they know V
i’s public value, they could validate the message source and integrity through formula (24).Assuming that after vehicleV
j receives a message from V
i, V
j can judge whether message V
i is correct. As the public value of V
i
(
e
(
P
,
P
)
d
I
D
V
i
,
p
) is public, then V
j can determine whether α
I
D
V
i
,
p
·
P, I
D
V
i
,
p, γ
I
D
V
i
,
p
·
P, T
stamp, and M are the message sent by V
i. First calculate 1
/
H
4
(
I
D
V
i
,
p
∥
M
∥
T
stamp
) and then calculate whether e
(
α
I
D
V
i
,
p
·
P
,
(
1
/
H
4
(
I
D
V
i
,
p
∥
M
∥
T
stamp
)
)
·
γ
I
D
V
i
,
p
·
P
)
=
e
(
P
,
P
)
d
I
D
V
i
,
p is correct. If it is correct, it indicates that the message is issued by V
i; otherwise it will be discarded. Since only V
i knows d
I
D
V
i
,
p and e
(
P
,
P
)
d
I
D
V
i
,
p is a problem, it cannot be forged by other vehicles.


## 4.4.2. Communication between Different RSUs

Two vehicles cannot communicate with each other between different RSUs; the reason lies in that the vehicle’s public value and pseudonym ID are different in different RSUs and vehicles’ public value in each RSU cannot be known between RSUs. Therefore, it is unable to assist vehicles to validate the correctness of the message transmitted from other RSUs. As shown in Figure2,  V
i and V
j are R
a and R
b, respectively, in two different RSUs. When V
i broadcasts a message to V
j, though V
j receives the message, it does not know if public value is owned by itself and it cannot confirm if it is the legal user. In order to resolve the above problem, as shown in Figure 3, (
1
)  V
j first transmits the message to V
i, the message content is request message: R
b
∥
I
D
V
j
,
p
∥
T
stamp, and V
j informs us within different RSUs; (
2
) after the successful entry of R
a identity validation, V
i transmits one signature to V
i and the signature is Sig
n
R
a
→
V
i
=
(
U
∥
V
∥
M
), where M
=
(
D
I
D
V
i
,
p
∥
T
l
I
D
V
i
,
p
∥
I
D
V
i
,
p
∥
P
D
I
D
R
a
,
t
∥
P
U
I
D
R
a
,
t
∥
I
D
R
a
,
t
∥  T
l
I
D
R
a
,
t
∥
γ
I
D
R
a
,
t
). V
i would broadcast signatures to V
j, then V
j could know R
a’s public key and public parameters and validate signatures and R
a’s validity. After the success of validation, V
j could know V
i’s public value and validate the message source and integrity.Figure 2
The communication problem between two vehicles in the different RSU.Figure 3
The solution of the communication problem.


## 4.4.3. Private Communication

In the following part we will discuss five cases of private communication: Case 1: private communication between TA and RSU, Case 2: private communication between RSU and RSU, Case 3: private communication between vehicle and vehicle, Case 4: private communication between vehicle and RSU, and Case 5: private communication between TA and vehicle.Case  1. Suppose R
j wants to perform private communication with TA; TA has already transmitted private communication key to R
j in Section 4.2.2. First, R
j and TA will validate each other’s identities and key’s validity and R
j would calculate the private communication with TA as follows: (25)
SK
R
j
,
TA
=
e
(
P
U
I
D
R
j
,
t
+
x
I
D
R
j
,
t
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
,
P
)
·
e
(
P
U
I
D
TA
,
t
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
.
Next, TA calculates the private communication with R
j as follows:
(26)
S
K
TA
,
R
j
=
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
·
e
(
P
U
I
D
R
j
,
t
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
,
where P
U
I
D
TA
,
t
=
H
1
(
I
D
TA
), P
U
I
D
R
j
,
t
=
H
1
(
I
D
R
j
); as ID is public, it could be calculated by itself. Therefore, the common key in formulae (25) and (26) is the same and TA and R
j could perform private communication.Case  2. Suppose R
j wants to perform private communication with R
k. First, R
j and R
k will validate each other’s identities and key’s validity and R
j would calculate the private communication with R
k as follows:(27)
S
K
R
j
,
R
k
=
e
(
P
U
I
D
R
j
,
t
+
x
I
D
R
j
,
t
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
,
P
)
·
e
(
P
U
I
D
R
k
,
t
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
P
U
I
D
R
k
,
t
,
P
)
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
R
k
,
t
,
P
)
e
(
y
·
P
,
P
)
.
Next, R
k calculates the private communication with R
j as follows:
(28)
S
K
R
j
,
R
k
=
e
(
P
U
I
D
R
k
,
t
+
x
I
D
R
k
,
t
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
k
,
t
·
P
,
P
)
·
e
(
P
U
I
D
R
j
,
t
,
P
)
=
e
(
P
U
I
D
R
k
,
t
,
P
)
e
(
x
I
D
R
k
,
t
·
P
,
P
)
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
y
·
P
,
P
)
e
(
x
I
D
R
k
,
t
·
P
,
P
)
=
e
(
P
U
I
D
R
k
,
t
,
P
)
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
y
·
P
,
P
)
,
where P
U
I
D
R
k
,
t
=
H
1
(
I
D
R
k
,
t
), P
U
I
D
R
j
,
t
=
H
1
(
I
D
R
j
,
t
); it could be known that the private communication key is the same from the final results.Case  3. Suppose V
i wants to perform private communication with V
j. First, V
i and V
j will validate each other’s identities and key’s validity and V
j would calculate the private communication with V
j as follows:
(29)
S
K
V
i
,
V
j
=
e
(
P
U
I
D
V
i
,
p
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
·
e
(
P
U
I
D
V
j
,
p
,
P
)
=
(
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
×
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
P
U
I
D
V
j
,
p
,
P
)
)
×
(
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
)
-
1
=
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
P
U
I
D
V
j
,
p
,
P
)
e
(
y
·
P
,
P
)
.
Next, V
j calculates the private communication with V
j as follows:
(30)
S
K
V
i
,
V
j
=
e
(
P
U
I
D
V
j
,
p
+
x
I
D
R
k
,
t
·
P
+
Z
I
D
V
j
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
k
,
t
·
P
+
Z
I
D
V
j
,
p
·
P
,
P
)
·
e
(
P
U
I
D
V
i
,
p
,
P
)
=
(
e
(
P
U
I
D
V
j
,
p
,
P
)
e
(
x
I
D
R
k
,
t
·
P
,
P
)
×
e
(
Z
I
D
V
j
,
p
·
P
,
P
)
e
(
P
U
I
D
V
i
,
p
,
P
)
)
×
(
e
(
y
·
P
,
P
)
e
(
x
I
D
R
k
,
t
·
P
,
P
)
e
(
Z
I
D
V
j
,
p
·
P
,
P
)
)
-
1
=
e
(
P
U
I
D
V
j
,
p
,
P
)
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
y
·
P
,
P
)
,
where P
U
I
D
V
j
,
p
=
H
1
(
I
D
V
j
,
p
) and P
U
I
D
V
i
,
p
=
H
1
(
I
D
V
i
,
p
) and it could be known that the private communication key is the same from the final results.Case  4. Suppose V
i wants to perform private communication with R
j. First, V
i and R
j will validate each other’s identities and key’s validity and V
j would calculate the private communication with R
j as follows:
(31)
S
K
V
i
,
R
j
=
e
(
P
U
I
D
V
i
,
p
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
·
e
(
P
U
I
D
R
j
,
t
,
P
)
=
(
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
×
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
P
U
I
D
R
j
,
t
,
P
)
)
×
(
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
)
-
1
=
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
y
·
P
,
P
)
.
Next, R
j calculates the private communication with V
j as follows:
(32)
S
K
R
j
,
V
i
=
e
(
P
U
I
D
R
j
,
t
+
x
I
D
R
j
,
t
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
,
P
)
·
e
(
P
U
I
D
V
i
,
p
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
=
e
(
P
U
I
D
R
j
,
t
,
P
)
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
y
·
P
,
P
)
,
where P
U
I
D
V
i
,
p
=
H
1
(
I
D
V
i
,
p
) and P
U
I
D
R
j
,
t
=
H
1
(
I
D
R
j
,
t
); it could be known from the final results that the private communication key is the same.Case  5. Suppose V
i wants to perform private communication with TA. First, V
i and TA will validate each other’s identities and key’s validity and V
j would calculate the private communication with TA as follows:
(33)
S
K
V
i
,
TA
=
e
(
P
U
I
D
V
i
,
p
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
y
·
P
+
x
I
D
R
j
,
t
·
P
+
Z
I
D
V
i
,
p
·
P
,
P
)
·
e
(
P
U
I
D
TA
,
t
,
P
)
=
(
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
×
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
e
(
P
U
I
D
TA
,
t
,
P
)
)
×
(
e
(
y
·
P
,
P
)
e
(
x
I
D
R
j
,
t
·
P
,
P
)
e
(
Z
I
D
V
i
,
p
·
P
,
P
)
)
-
1
=
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
.
Next, TA calculates the private communication with V
j as follows:
(34)
S
K
TA
,
V
i
=
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
y
·
P
,
P
)
·
e
(
P
U
I
D
V
i
,
p
,
P
)
=
e
(
P
U
I
D
TA
,
t
,
P
)
e
(
P
U
I
D
V
i
,
p
,
P
)
e
(
y
·
P
,
P
)
,
where P
U
I
D
V
i
,
p
=
H
1
(
I
D
V
i
,
p
) and P
U
I
D
TA
,
t
=
H
1
(
I
D
TA
,
t
) and it could be known from the final results that the private communication key is the same.From Case 1 to Case 5, it could be known that private communication could be performed among vehicles, RSU or TA, and the private communication key of any vehicle and RSU has the top secrets and their own secrets, so it is impossible to forge any vehicle or RSU, as you must know the top secrets.Though the private communication method costs much more calculation time for the first time, which is spent in validating the other’s identity and calculating the private communication key between them, the calculation time during the communication within the other’s valid time is much less, as the common secret key has already been established, which will not be recalculated until the other’s valid time expires. For the symmetrical encryption, the calculation time is less. For the equipment which often uses private communication, such as RSU to RSU or RSU to TA, the time which private communication spends could be reduced.


## 4.5. Key Updating and Identity Cancellation

When TA’s key validity expires, TA would utilize formula (9) to replace α
I
D
TA
,
t
·
P, γ
I
D
TA
,
t
P, m
I
D
TA
,
t, and T
l
I
D
TA
,
t, which will not influence the communication of RSU and vehicles during the process. TA would use α
I
D
TA
,
t
·
P as the data key (P
D
I
D
TA
,
t), H
1
(
I
D
TA
,
t
)
∈
G
1 is public key (P
U
I
D
TA
,
t), α
I
D
TA
,
t
P
U
I
D
TA
,
t is private key (P
R
I
D
TA
,
t), γ
I
D
TA
,
t
P is another public parameter, T
l
I
D
TA
,
t is TA’s public key, private key, and valid time, and TA makes new parameters public.At RSU’s key updating part, as TA and RSU mainly perform identity validation instead of the message validation among vehicles. IfR
j finds key will expire soon, R
j would calculate the common key (S
K
R
j
,
TA) with TA, as shown in formula (26), and then encrypt message M and transmit to TA, M
=
(
P
D
I
D
R
j
,
t
∥
P
U
I
D
R
j
,
t
∥
γ
I
D
R
j
,
t
∥
T
l
I
D
R
j
,
t
∥
T
stamp
). After receiving the encrypted message, TA would calculate the common key (S
K
R
j
,
TA) with R
j, decrypt the message, and validate R
j’s identity, as shown in formula (13). Next, TA would search table to check if R
j is legal. If it is legal, TA would recalculate R
j’s public key, private key, private communication key, and other parameters and then utilize S
K
TA
,
R
j to encrypt the parameters and transmit them back to R
j. After receiving the message, R
j would reutilize S
K
R
j
,
TA for decryption and revalidating if the parameters are public value (D
I
D
TA
,
t), as shown in formula (13). Thus RSU key updating is completed. During the process, only the vehicle communication within the range would be influenced, and RSU requires retransmitting a new signature to each vehicle.Suppose vehicleV
i is a malicious node; R
m would first utilize Table 5 to search V
i’s initializing pseudonym ID (I
D
V
i
,
p) and then use the common key with each RSU to encrypt I
D
V
i
,
p and transmit to each RSU. Before the receiving, each RSU would first check SPID table and see if there is initializing pseudonym ID. If there is, V
i registration would be forbidden during handoff. After receiving R
m message, TA would first validate if V
i is a malicious node. If it is, TA would search table according to I
D
V
i
,
p and first set V
i’s legality false. When TA revalidates V
i’s identity via RSU (as shown in Section 4.3.1), TA would forbid V
i registration.SupposeR
j is a malicious node; adjacent R
m would directly utilize the common key with TA to encrypt the message and inform TA that R
j is a malicious node. TA would first validate if R
j is a malicious node. If it is, TA would set R
j’s legality in table false and use the common key with RSU to inform all RSUs that R
j is a malicious node, so that malicious RSU or vehicles updating KEY or communication subsequently would be stopped.


## 5. Security and Performance Analysis

This section mainly illustrates that the method proposed in the essay could reach(
1
) message source, (
2
) message integrity, (
3
) nonrepudiation, (
4
) pseudonym, and (
5
) untraceability, in terms of security analysis. As far as the performance analysis is concerned, we carry out performance analysis in [4–6] (Table 7).


### 5.1. Security Analysis

We discuss the security analysis from 5 aspects as follows.(1) Confidentiality. No matter what unit (TA, RSU, and vehicles) performs private communication, the private communication with the other side could be guaranteed, as the vehicle’s private communication key contains the vehicle, RSU, and TA’s secrets. During the communication, though the vehicle and RSU’s secrets could be eliminated, malicious nodes could not get TA’s secret y from the private communication key or the results after elimination, so malicious nodes cannot forge other’s private key or listen in.(2) Source Authentication and Nonrepudiation. Before the communication, RSU must validate vehicles’ identities. After the success of validation, RSU would utilize signature method to broadcast vehicles’ pseudonym ID and public value to each vehicle, which could then know each legal vehicle’s public value from the signature, so the message broadcasted by vehicles could be validated via BHD function. As the public value cannot be forged, it could represent the vehicle itself and the vehicle sending messages could reach nonrepudiation and know the source of the message.(3) Message Integrity. As the public value (e
(
P
,
P
)
d) is public and the BHD function is e
(
P
,
P
)
d
=
e
(
α
P
,
(
1
/
m
)
γ
P
), though m and P are public, α, γ, or d could not be got from P or m. Suppose the malicious node forges m and the validation result is e
(
P
,
P
)
d
≠
e
(
α
P
,
(
1
/
m
′
)
γ
P
), so malicious nodes cannot forge messages and change messages and other vehicles could validate message integrity.(4) Pseudonym. The vehicle uses different pseudonym IDs at different RSU. Suppose RSU cannot know vehicle’s real ID by collusion attack and malicious nodes cannot collect vehicle messages to calculate vehicles’ read ID, as vehicle’s pseudonym ID produces irregularity.(5) Privacy. The essay adopts two-level pseudonym ID. The first level is the pseudonym ID between vehicle and TA, which is known to only TA and vehicle and not broadcasted to RSU or vehicles. The second-level pseudonym ID is produced by RSU and vehicle. Suppose RSU traces vehicles’ travel path by means of collusion attack and the trace time and range are limited, as after the time slice, vehicles will be revalidated by TA and replace the first-level and second-level pseudonym ID, then the pseudonym ID produces irregularity, so the vehicles’ privacy could be improved.


### 5.2. Performance Analysis

In this section, we compare our method with [4–8]. Table 5 shows the differences and we could know that our method has a lot of advantages from the table.Table 5
The comparison of property.
Property
Method
[4]
[5]
[6]
[7]
[8]
Proposed  method
Security and privacy preservation
Yes
Yes
Yes
Yes
Yes
Yes
Do need the certificate
No
No
No
No
No
No
Do need the help of RSU for authentication
No
No
No
No
No
No
PKI-based system
No
No
No
Yes
No
No
Communication within different RSU
Yes
No
Yes
Yes
Yes
Yes
Privacy communicate
Yes
Yes
Yes
Yes
No
YesIn Table6, we propose encryption/decryption calculation time. According to [17, 18], the implementation of the bilinear mapping is provided based on the Tate pairing over a Miyaji-Nakabayashi-Takano (MNT) curve [19] with embedding degree 6 and 160-bit q.Table 6
Execution time in milliseconds.
Notations
Descriptions
Execution time (ms)
T
p
Pairing operation
≈4.5
T
m
Point multiplication
≈0.6
T
e
Field exponentiation
≈0.54
ASE
RSA encryption
0.19
ASD
RSA decryption
4.65
HMAC
HMAC
0.002
SE
AES encryption
<0.19
SD
AES decryption
<4.65Table 7
Performance analysis.
Property
Method
[4]
[5]
[6]
[7]
[8]
Proposed  method
The broadcast message
Signing:
5
*
T
m
+
3
*
T
p Verification: 4
*
T
m
+
4
*
T
p
Signing
n
*
T
p
+
n
*
HMAC Verification
n
*
T
p
+
n
*
HMAC
Signing:
1
*
T
p Verification: 3
*
T
p
Signing
T
p
+
T
m  Verification
T
p
+
T
m
Signing
2
*
T
p
+
0.19 Verification
T
p
+
T
m
+
0.19
Signing
2
*
T
m Verification
T
p
+
T
m
Spending time
36.4 ms
n
*
9 ms + n
*
0.004 ms
18 ms
10.2 ms
9.98 ms
6.3 ms
Handoff
3
*
T
p
4
*
T
m
+
T
e
+
2
*
T
p
N/A
N/A
N/A
1
*
SE + 1
*
SD
+
3
*
T
m
Spending time
13.5 ms
11.94 ms
N/A
N/A
N/A
<5.44 ms
Communication between different RSUs
Signing:
5
*
T
m
+
3
*
T
p Verification:
4
*
T
m
+
4
*
T
p
N/A
Signing:
1
*
T
p Verification: 3
*
T
p
Signing
T
p
+
T
m Verification
T
p
+
T
m
Signing
2
*
T
p
+
0.19 Verification
T
p
+
T
m
+
0.19
Signing
2
*
T
m Verification
2
*
T
p
+
2
*
T
m
Spending time
36.4 ms
N/A
18 ms
10.2 ms
9.98 ms
11.4 ms
Privacy communicate
N/A
Signing
T
P + SE Verification
T
p + SD
N/A
SigningASE  Verification ASD
N/A
Signing
T
m
+
T
P
+
SE Verification
T
m
+
T
P
+
SD
Spending time
N/A
<13.84 ms
N/A
4.84 ms
N/A
<15.04 msWe utilize Table6, to calculate the time for broadcasting messages and validating messages in [4–8]. The method proposed in the essay supposes that if a vehicle is about to broadcast messages to other vehicles within the range, the vehicle would calculate d
I
D
V
i
,
p
=
α
I
D
V
i
,
p
*
(
1
/
H
4
(
I
D
V
i
,
p
*
M
*
T
stamp
)
)
*
γ
I
D
V
i
,
p. As these calculations belong to the general integer calculation, whose calculation complexity is quite low, and the vehicle will change α
I
D
V
i
,
p and γ
I
D
V
i
,
p into points, 2
*
T
m calculation time will be spent. The vehicle will broadcast the following messages to other vehicles (
M
∥
α
I
D
V
i
,
p
∥
γ
I
D
V
i
,
p
∥
I
D
V
i
,
p
∥
T
stamp
) and then calculate the message validation time. After receiving messages, other vehicles could first inquire about the vehicle’s public value and the validation is e
(
P
,
P
)
d
I
D
V
i
,
p
=
e
(
α
I
D
V
i
,
p
·
P
,
(
1
/
H
4
(
I
D
V
i
,
p
*
M
*
T
stamp
)
)
*
γ
I
D
V
i
,
p
·
P
), so the time for broadcasting and validating messages in the essay is T
m +T
p.During the handoff process of vehicles in the essay, when RSU’s pseudonym ID challenge is successful, RSU would assist vehicles to produce signature time, as shown in formula (4), which needs 3
*
T
m in all. RSU produces vehicles’ private communication key, as shown in formula (21), which needs 4
*
T
m
+
3
*
T
p, so the total time is 7
*
T
m
+
3
*
T
p. When messages are broadcast to other vehicles within different RSUs, vehicles producing message signatures need 2
*
T
m, other vehicles validating signatures, as shown in formula (22), and need T
m
+
T
p, and validating vehicles’ message needs T
m
+
T
p, so the total time required is 4
*
T
m
+
2
*
T
p.References [4, 6] both use certificates to validate their own identities, so the broadcasting messages could validate their own identities within RSU range or outside RSU range. In [5], the concept of identity-based is utilized and vehicles establish common key with each vehicle, so when vehicles broadcast messages, they would utilize the common key with each vehicle as HMAC’s key and encrypt messages and then transmit the encrypted message to the other side, as broadcasting messages requires establishing n common keys to encrypt messages and other vehicles also need establish common keys for decryption, so there is 2
n
*
T
p altogether. As [5] does not discuss the communication between vehicles at different RSUs, it is unable to calculate the encryption and decryption time.


## 5.1. Security Analysis

We discuss the security analysis from 5 aspects as follows.(1) Confidentiality. No matter what unit (TA, RSU, and vehicles) performs private communication, the private communication with the other side could be guaranteed, as the vehicle’s private communication key contains the vehicle, RSU, and TA’s secrets. During the communication, though the vehicle and RSU’s secrets could be eliminated, malicious nodes could not get TA’s secret y from the private communication key or the results after elimination, so malicious nodes cannot forge other’s private key or listen in.(2) Source Authentication and Nonrepudiation. Before the communication, RSU must validate vehicles’ identities. After the success of validation, RSU would utilize signature method to broadcast vehicles’ pseudonym ID and public value to each vehicle, which could then know each legal vehicle’s public value from the signature, so the message broadcasted by vehicles could be validated via BHD function. As the public value cannot be forged, it could represent the vehicle itself and the vehicle sending messages could reach nonrepudiation and know the source of the message.(3) Message Integrity. As the public value (e
(
P
,
P
)
d) is public and the BHD function is e
(
P
,
P
)
d
=
e
(
α
P
,
(
1
/
m
)
γ
P
), though m and P are public, α, γ, or d could not be got from P or m. Suppose the malicious node forges m and the validation result is e
(
P
,
P
)
d
≠
e
(
α
P
,
(
1
/
m
′
)
γ
P
), so malicious nodes cannot forge messages and change messages and other vehicles could validate message integrity.(4) Pseudonym. The vehicle uses different pseudonym IDs at different RSU. Suppose RSU cannot know vehicle’s real ID by collusion attack and malicious nodes cannot collect vehicle messages to calculate vehicles’ read ID, as vehicle’s pseudonym ID produces irregularity.(5) Privacy. The essay adopts two-level pseudonym ID. The first level is the pseudonym ID between vehicle and TA, which is known to only TA and vehicle and not broadcasted to RSU or vehicles. The second-level pseudonym ID is produced by RSU and vehicle. Suppose RSU traces vehicles’ travel path by means of collusion attack and the trace time and range are limited, as after the time slice, vehicles will be revalidated by TA and replace the first-level and second-level pseudonym ID, then the pseudonym ID produces irregularity, so the vehicles’ privacy could be improved.


## 5.2. Performance Analysis

In this section, we compare our method with [4–8]. Table 5 shows the differences and we could know that our method has a lot of advantages from the table.Table 5
The comparison of property.
Property
Method
[4]
[5]
[6]
[7]
[8]
Proposed  method
Security and privacy preservation
Yes
Yes
Yes
Yes
Yes
Yes
Do need the certificate
No
No
No
No
No
No
Do need the help of RSU for authentication
No
No
No
No
No
No
PKI-based system
No
No
No
Yes
No
No
Communication within different RSU
Yes
No
Yes
Yes
Yes
Yes
Privacy communicate
Yes
Yes
Yes
Yes
No
YesIn Table6, we propose encryption/decryption calculation time. According to [17, 18], the implementation of the bilinear mapping is provided based on the Tate pairing over a Miyaji-Nakabayashi-Takano (MNT) curve [19] with embedding degree 6 and 160-bit q.Table 6
Execution time in milliseconds.
Notations
Descriptions
Execution time (ms)
T
p
Pairing operation
≈4.5
T
m
Point multiplication
≈0.6
T
e
Field exponentiation
≈0.54
ASE
RSA encryption
0.19
ASD
RSA decryption
4.65
HMAC
HMAC
0.002
SE
AES encryption
<0.19
SD
AES decryption
<4.65Table 7
Performance analysis.
Property
Method
[4]
[5]
[6]
[7]
[8]
Proposed  method
The broadcast message
Signing:
5
*
T
m
+
3
*
T
p Verification: 4
*
T
m
+
4
*
T
p
Signing
n
*
T
p
+
n
*
HMAC Verification
n
*
T
p
+
n
*
HMAC
Signing:
1
*
T
p Verification: 3
*
T
p
Signing
T
p
+
T
m  Verification
T
p
+
T
m
Signing
2
*
T
p
+
0.19 Verification
T
p
+
T
m
+
0.19
Signing
2
*
T
m Verification
T
p
+
T
m
Spending time
36.4 ms
n
*
9 ms + n
*
0.004 ms
18 ms
10.2 ms
9.98 ms
6.3 ms
Handoff
3
*
T
p
4
*
T
m
+
T
e
+
2
*
T
p
N/A
N/A
N/A
1
*
SE + 1
*
SD
+
3
*
T
m
Spending time
13.5 ms
11.94 ms
N/A
N/A
N/A
<5.44 ms
Communication between different RSUs
Signing:
5
*
T
m
+
3
*
T
p Verification:
4
*
T
m
+
4
*
T
p
N/A
Signing:
1
*
T
p Verification: 3
*
T
p
Signing
T
p
+
T
m Verification
T
p
+
T
m
Signing
2
*
T
p
+
0.19 Verification
T
p
+
T
m
+
0.19
Signing
2
*
T
m Verification
2
*
T
p
+
2
*
T
m
Spending time
36.4 ms
N/A
18 ms
10.2 ms
9.98 ms
11.4 ms
Privacy communicate
N/A
Signing
T
P + SE Verification
T
p + SD
N/A
SigningASE  Verification ASD
N/A
Signing
T
m
+
T
P
+
SE Verification
T
m
+
T
P
+
SD
Spending time
N/A
<13.84 ms
N/A
4.84 ms
N/A
<15.04 msWe utilize Table6, to calculate the time for broadcasting messages and validating messages in [4–8]. The method proposed in the essay supposes that if a vehicle is about to broadcast messages to other vehicles within the range, the vehicle would calculate d
I
D
V
i
,
p
=
α
I
D
V
i
,
p
*
(
1
/
H
4
(
I
D
V
i
,
p
*
M
*
T
stamp
)
)
*
γ
I
D
V
i
,
p. As these calculations belong to the general integer calculation, whose calculation complexity is quite low, and the vehicle will change α
I
D
V
i
,
p and γ
I
D
V
i
,
p into points, 2
*
T
m calculation time will be spent. The vehicle will broadcast the following messages to other vehicles (
M
∥
α
I
D
V
i
,
p
∥
γ
I
D
V
i
,
p
∥
I
D
V
i
,
p
∥
T
stamp
) and then calculate the message validation time. After receiving messages, other vehicles could first inquire about the vehicle’s public value and the validation is e
(
P
,
P
)
d
I
D
V
i
,
p
=
e
(
α
I
D
V
i
,
p
·
P
,
(
1
/
H
4
(
I
D
V
i
,
p
*
M
*
T
stamp
)
)
*
γ
I
D
V
i
,
p
·
P
), so the time for broadcasting and validating messages in the essay is T
m +T
p.During the handoff process of vehicles in the essay, when RSU’s pseudonym ID challenge is successful, RSU would assist vehicles to produce signature time, as shown in formula (4), which needs 3
*
T
m in all. RSU produces vehicles’ private communication key, as shown in formula (21), which needs 4
*
T
m
+
3
*
T
p, so the total time is 7
*
T
m
+
3
*
T
p. When messages are broadcast to other vehicles within different RSUs, vehicles producing message signatures need 2
*
T
m, other vehicles validating signatures, as shown in formula (22), and need T
m
+
T
p, and validating vehicles’ message needs T
m
+
T
p, so the total time required is 4
*
T
m
+
2
*
T
p.References [4, 6] both use certificates to validate their own identities, so the broadcasting messages could validate their own identities within RSU range or outside RSU range. In [5], the concept of identity-based is utilized and vehicles establish common key with each vehicle, so when vehicles broadcast messages, they would utilize the common key with each vehicle as HMAC’s key and encrypt messages and then transmit the encrypted message to the other side, as broadcasting messages requires establishing n common keys to encrypt messages and other vehicles also need establish common keys for decryption, so there is 2
n
*
T
p altogether. As [5] does not discuss the communication between vehicles at different RSUs, it is unable to calculate the encryption and decryption time.


## 6. Conclusion

The method in the essay adopts BDH messages authentication to produce TA and RSU’s public key and other parameters. Any vehicles could validate if RSU is legal through BDH messages authentication method and utilize pseudonym ID challenge method to validate RSU and vehicles’ identities, which quickens handoff processing time.It is hoped that message batch validation and how to judge vehicles are malicious nodes will be added. Though the essay proposes cancellation of users’ function, it does not mention how to judge users to be malicious nodes, which will be put into the study and make the study more complete.



---

*Source: 231976-2014-09-25.xml*