Expedite Privacy-Preserving Emergency Communication Scheme for VANETs

Abstract

The existing communication schemes are often unusable in natural disasters and public emergencies. But requirements of information collection and data transmission in emergency scenario are very imperative. Thus, sensor networks ad hoc networks are required in the emergency communication systems. For example, rescue vehicles equipped with wireless communication devices, sensors, and cameras are regularly used to collect and transmit the real-time information for the rescue action. The paper focuses on security solutions for the vehicular ad hoc networks (VANETs) in the emergency communication cases, in which the communication infrastructures are not always available. An expedite privacy-preserving emergency communication (EPEC) scheme is presented for the vehicles to securely connect with the others in the neighbor area even when the trusted infrastructures are destroyed by the disaster. EPEC satisfies conditional privacy preservation requirements, in which both lightweight signature and batch verification are employed to provide efficiency. We also show the proof of the security, feasibility, and efficiency of our EPEC by the theoretical and experimental analyses.

1. Introduction

Information perception, transmission, and processing are big problems in emergency rescues. The wireless sensor networks and ad hoc networks are expected to be used in these scenarios, but the network deployment and resource sharing face new problems of node connection, network security, and human privacy. As we know, vehicles are often used in disaster rescues, such as in Sichuan Earthquake [1] and Tōhoku Earthquake [2]. Then, we can equip rescue vehicles with sensors, cameras, and wireless communication devices, which combine wireless sensor networks with mobile ad hoc networks and will be more applicable in real-time data collection, transmission, and processing. Vehicle communication in rescue action should maintain the primary requirements of security, privacy, and efficiency, which contain mutual authentication, conditional privacy preservation, internal attacks prevention, and expedite authentication in emergency communication. The communication units of these rescue vehicles based networks are similar to typical vehicular ad hoc networks (VANETs), but the network structures are different because there are no road-side units (RSUs). Thus, the new networks are the same as traditional VANETs without the supports of RSUs, and we study the communication scheme for the emergency scenario where the vehicles cannot connect with an RSU.

VANETs mainly consist of mobile vehicles equipped with wireless communication devices and the road-side units. As shown in Figure 1, vehicles can communicate with one another (V2V) and with the RSUs (V2R) by means of the Dedicated Short-Range Communication protocol [3]. Figure 1 also shows that VANET is a subnet under the architecture of the Internet of Things, for VANET is connected with a trust authority (TA) and many Application Servers through the Internet. VANETs can provide drivers with traffic information to defend against dangers and traffic congestions [4], as well as entertainment information to improve the driving experience [5]. Privacy preservation [6] and expedite authentication [7] are two critical issues in VANETs communication, where privacy is conditional as TA is allowed to reveal any entity's real identity and revoke it from the network. It is because on one hand, drivers would not be willing to join VANETs if their private information could not be well preserved. And on the other hand, malicious vehicles should be removed from the network timely. In addition, expedite authentication can reduce packet loss and ensure smooth operations of VANETs. Many communication schemes have been proposed for conditional privacy preservation and expedite authentication in VANETs. But these reported schemes are not suitable for emergency communication in the rescue scenario we described earlier, because they take RSU as an important part of VANETs.

Figure 1

VANETs model.

We will present an expedite privacy-preserving emergency communication (EPEC) scheme for disaster rescues, where RSUs are unavailable. The remainder of this paper is organized as follows. Section 2 overviews the related works in VANETs. In Section 3, we describe the system model and give basic presuppositions used in the proposed scheme. The proposed EPEC is thoroughly described in Section 4. The security analysis of the proposed scheme is presented in Section 5. Performance evaluation is given in Section 6, followed by the conclusion in Section 7.

2. Related Works

Many related studies have been reported in VANETs based on different cryptographic systems, such as public key infrastructure (PKI) based signature, group signature, and identity-based signature. In terms of disaster rescue, the primary functional requirements of communication do not change, but these requirements should be realized without fixed infrastructures. Next, we analyze the related works in the aspects of EPEC's requirements aforementioned.

Mutual authentication is the primitive property required in VANETs communication, which can be achieved through digital signature. Raya and Hubaux proposed PKI-based schemes [16, 17] in 2005 and 2007, respectively to realize authenticity in VANETs. But PKI-based scheme is not suitable for VANETs because of the management overhead of certificates.

The commonly used techniques for conditional privacy preservation are group signature and Mix-zone pseudonym—changing pseudonym within specified region, that is, Mix-zone. Lin et al. [8] adopted short group signature [18], and TACK [9] and TARI [19] adopted group signature with verifier-local revocation [20], to realize conditional privacy preservation. For the shortcoming of the demand for group manager, ring signature [21] met conditional privacy preservation without group managers. However, what makes these schemes inapplicable to VANETs is that the verification cost for group/ring signature is very high. For authentication efficiency, Lu et al. [10] achieved conditional privacy preservation by pseudonym signature. Reference [22] aimed to establish Mix-zones at social points, allowing all vehicles in the Mix-zone to change pseudonyms at the same time. However, only when given a reasonable large number of vehicles in the Mix-zone, the privacy requirements can be well protected due to pseudonyms updating.

In aspect of internal attacks prevention, some existing schemes perform well while some fail to realize internal attacks prevention requirement. IBV [11] devised identity-based signature to realize unidirectional V2R authentication, which could not achieve internal attacks prevention or conditional privacy preservation requirements. Subsequently, TSVC [23] based on the TESLA [24] achieved fast authentication with internal attacks prevention using message authentication code (MAC). However, its drawback is that packet loss ratio increases with the speed of vehicles. ABAKA [12] was dedicated to entertainment services in VANETs, but internal attacks prevention requirement was not realized as users shared the same secret.

In addition to aforementioned requirements, verification efficiency, that is, expedite authentication, is another requisite in VANETs. One-by-one message verification is characterized by being simple to use. In RAISE [13], RSU verified messages one by one and broadcasted 128 bytes for each valid message, which caused severe inefficiency. Cooperative authentication is a method of raising verification efficiency. In COMET [13], verifiers verified message with probability of p, and if it was invalid, they notified the neighbors of the result. CMAP [14] chose verifiers based on location, and nonverifiers waited for the verifiers' results. Cooperative verification can raise verification efficiency, as vehicles do not need to verify every message received. However, due to the uncertainty of the vehicle speed and road conditions, the scalability and practicality of these schemes face questioning. Batch verification is another effective method to improve efficiency as it allows verifiers to authenticate a group of signatures at the same time. CPAS [15] and MLAS [25] verified messages in batch based on bilinear pairing operations. But bilinear pairing operation is of large computational overhead. In addition, for CPAS, there exists the problem of key escrow as private key generator (PKG) is essential to generate user private key. Malina et al. [26] adopted group signature supporting batch verification, and messages were classified in different priority level in order to improve verification efficiency. However, the group signature also suffers from high computational overhead. Even more important, all the previous schemes are not applicable to emergency communication.

Virtually, VANETs-based emergency communication system is a special kind of VANETs model without RSUs. But currently there is no related research. Overall, current works in VANETs cannot satisfy all the functional requirements in this scenario. And it is shown in Table 1, where “✓” indicates “realized” and “×” indicates “unrealized”, respectively. It is obvious that no scheme is applicable to our scenario. To solve this problem, we present an expedite privacy-preserving emergency communication scheme. In terms of conditional privacy preservation, an exclusive secret key is established through secure protocol between the vehicle and TA in the reregistration phase, only allowing TA to track malicious vehicles. As for expedite authentication, lightweight signature and batch verification are combined to reduce computation and communication overhead, providing fast and efficient communication.

Table 1

Comparison of related works.

Schemes				Authentication efficiency			Emergency communication
	Mutual authentication	Conditional privacy preservation	Internal attacks prevention	Primitive overhead	Batch verification	No RSU	Dynamicre-registration	Vehicle group communication
GSIS [8]	✓	✓	✓	High	×	×	×	×
TACK [9]	✓	✓	✓	High	×	×	✓	×
ECPP [10]	✓	✓	✓	High	×	×	✓	×
IBV [11]	×	×	×	High	✓	×	×	×
ABAKA [12]	✓	×	×	Low	✓	×	×	×
RAISE [13]	✓	✓	✓	Low	×	×	×	×
COMET [13]	✓	×	✓	Low	×	✓	×	×
CMAP [14]	✓	✓	✓	High	×	×	×	✓
CPAS [15]	✓	✓	✓	High	✓	×	×	×

The proposed EPEC achieves the following five aspects of requirements. (1) No Fixed RSU. Vehicles can reregister with TA dynamically, and then proceed with mutual authentication in broadcast communication without fixed RSU. (2) Conditional Privacy Preservation. EPEC allows only trusted TA to trace vehicles' real identities. (3) Internal Attacks Prevention. The malicious vehicles can only cause limited damage to the whole networks. (4) High Efficiency. Lightweight signature and batch verification are combined to reduce computation overhead. And identity-based signature is adopted to save communication overhead. (5) Vehicle Group Communication. Vehicles can form a group to communicate timely with each other.

3. System Model and Preliminaries

In this section, we formalize the specific system model for VANETs-based emergency communication and the basic presuppositions used in the proposed scheme EPEC and identify the design objectives.

3.1. System Model

VANETs for disaster rescue are different from the regular vehicular network model in Figure 1. According to the accurate circumstance of disaster rescue, a two-layer network model is proposed, as shown in Figure 2. The upper layer comprises the trust authority TA and the Application Server, while the lower layer is composed of rescue vehicles including emergency communication cars and regular vehicles. TA is responsible for issuing real identification RID and public/private key pairs to all entities. Most importantly, TA is always trusted and can never be compromised. The Application Server is responsible for information analyses and feedbacks. The emergency communication cars contain ambulances, fire trucks, and so on, AMBs for short in EPEC. AMBs are allocated with powerful hardware facilities with longer communication range and stronger computation capability than regular vehicles. They are authorized by TA and can arrive at the target zone after the disaster, responsible for networking the regular vehicles.

Figure 2

System model.

In the framework we proposed, there are two different kinds of communication: the reregistration communication and the broadcast communication, where the broadcast communication can also be divided into vehicle to AMB communication and vehicle group communication. The leftmost group 1 in Figure 2 indicates vehicles reregistration with TA via AMB. Vehicles reregister themselves with the TA via AMB and get the exclusive secret key used to generate pseudonyms. Groups 2 and 3 show the communication with and without AMB available, respectively. EPEC does not require AMBs to cover the entire network. They may move to another place after networking the vehicles in some place. The dashed line indicates the group communication range, within which the vehicles communicate with each other by the wireless communication standard IEEE 802.11p. AMBs communicate securely with TA and the Application Server by satellite communications.

3.2. Basic Presuppositions

An elliptic curve is a cubic equation of the form $y^2+axy+by=x^3+c{x}^2+dx+e$ , where a, b, c, d, and e are all real numbers. In an elliptic curve cryptography (ECC) system, the elliptic curve equation is defined as the form of $E_q(a,b):y^2=x^3+ax+b(\mathrm{mod}q)$ , over a prime finite field ${𝔽}_q$ , where a, $b\in {𝔽}_q$ , $q>3$ , and $4a^3+27b^2\ne 0(\mathrm{mod}q)$ . In general, the security of ECC depends on the difficulties of the following problems [27, 28]. So far, no polynomial algorithm is capable to solve these problems.

Definition 1 (Elliptic Curve Discrete Logarithm Problem (ECDLP)).

Given two points P and Q over $E_q(a,b)$ , the elliptic curve discrete logarithm problem (ECDLP) finds an integer $x\in {𝔽}_q$ such that $x·P=Q$ .

Definition 2 (Computational Diffie-Hellman Problem (CDHP)).

Given three points P, $sP$ , and $tP$ over $E_q(a,b)$ for s, $t\in {𝔽}_q$ , the computational Diffie-Hellman problem (CDHP) finds the point $(st)P$ over $E_q(a,b)$ .

3.3. Design Objectives

In terms of emergency communication, the VANETs system needs to satisfy all requirements in the condition of no fixed infrastructures. The precise functional requirements are presented as following.

Dynamic Reregistration without Fixed RSUs. As fixed RSUs may have been destroyed during the disaster, vehicles reregister themselves with TA via AMBs to get the system public parameters. However, AMBs do not cover the entire network and vehicle may need to update the secret key. So vehicles should be able to dynamically reregister with TA when AMB is available.

Mutual Authentication. AMB needs to authenticate itself to regular vehicles on arriving at the disaster area. And vehicles should also be authenticated when they reregister with TA through AMB. In addition, during broadcast phase vehicles need to authenticate each other to ensure that the messages are indeed sent by legitimate entities to guard against the impersonation attack. The mutual authentication is achieved by signature, which also enforces message integrity checking.

Conditional Privacy Preservation. The real identity of a vehicle should be hidden from any entity during the communication process in order to protect the sender's private information. But on the other hand, when vehicles are found to abuse the network or are in dispute for an accident, it is necessary to allow TA to trace back to the obligated vehicles' real identities and revoke them.

Internal Attacks Prevention. Different from reference [11, 12], legitimate vehicles holding their own secret key materials can get neither the private key nor the real identity of another licit vehicle. Even if some vehicles are captured by the attacker, the attacker cannot obtain other legitimate vehicles' secret key materials with the captured materials.

Efficiency. Because of the strict time restriction of message authentication in VANETs, communication schemes should be efficient in terms of small computational overhead and acceptable verification delay. In addition, the communication overhead of the security programs should be as small as possible considering the confined bandwidth.

4. EPEC: Expedite Privacy-Preserving Emergency Communication

In this section, we detail the expedite privacy-preserving emergency communication EPEC scheme for VANETs-based disaster rescue. EPEC presents expedite authentication for two communication patterns: EPEC1 for vehicle networking with AMB and EPEC2 for vehicle group communication without AMB. When AMB enters the disaster area, it regularly broadcasts beacon of its own identification. Vehicles receiving the beacon verify its authenticity and, if valid, reregister with TA via AMB. Specific to the requirement of conditional privacy preservation, a secure key agreement protocol is proposed to establish an exclusive secret key between the vehicle and TA during the reregistration phase. Then, vehicles self-generate pseudonyms for subsequent broadcast communication. In both vehicle to AMB communication and vehicle group communication, point multiplications instead of bilinear pairings are conducted for authentication, thus saving computational overhead. Besides, signatures can be verified in batch. The prime notations in EPEC are defined in Table 2.

Table 2

Notations.

Notations	Descriptions
AMB	Emergency communication car
$V_i$	Regular vehicle
${\text{PK}}_i$ / ${\text{SK}}_i$	Public/private key of $V_i$
$h_1$ , $h_2$	One-way hash function $h_1$ , $h_2$ : {0, 1}*→ ${\mathbb{Z}}_q^{\mathrm{*}}$
H	MapToPoint hash function H: {0, 1}*→ $G_1$
$k_i$	Secret key of $V_i$
${\text{ID}}_i$	Pseudonym of $V_i$
${\text{CSK}}_i$	Private key of $V_i$ corresponding to ${\text{ID}}_i$
GSK	Group secret key

4.1. System Initialization

Before AMBs enter the disaster area, TA initializes the system to establish the public parameters. It is reasonable to assume that TA bootstraps the whole system, as a single authority VANETs model is under consideration in Figure 2. Specifically, in this phase, TA generates a cyclic additive group $G_1$ and a multiplicative group $G_2$ of the same prime order q, chooses two generators P, $Q\in G_1$ , and then gets $g=e(P,Q)$ . In addition, TA picks three secure cryptographic hash functions $h_1$ , $h_2$ , and H, where $h_1,h_2\hspace{0.17em}:\hspace{0.17em}{\{\mathrm{0,1}\}}^{*}\to {\mathbb{Z}}_q^{*}$ and $H\hspace{0.17em}:\hspace{0.17em}{\{\mathrm{0,1}\}}^{*}\to G_1$ . Then, TA randomly chooses $s\in {\mathbb{Z}}_q^{*}$ as its master key and sets $P_{\text{pub}}=sQ$ . Finally, TA gets the system public parameters $\{G_1,G_2,g,P,Q,P_{\text{pub}},h_1,h_2,H\}$ . Vehicles and AMBs can download the system public parameters from TA.

4.2. EPEC1: Networking with AMB

AMBs enter the disaster area after the system initialization for dynamic vehicle reregistration, after which vehicles generate pseudonyms by themselves and conduct communication with AMB according to EPEC1.

4.2.1. Dynamic Reregistration

In the reregistration procedure, a secure protocol with secret key agreement is presented to establish a shared secret key between vehicle and TA via AMB. The protocol is secured with signature and encryption to prevent the intermediate intrusion attacks. The precise process is shown in Figure 3.

Figure 3

EPEC1: Vehicle reregistration protocol.

AMB periodically broadcasts its own identity information when entering some area with the following beacon message:

$$\begin{array}{l}\text{Bea}=〈M,T_i,\text{IDSig}\left(M\mid \mid T_i\right)〉,\\ M={\text{ID}}_{\text{AMB}}\mid \mid \text{P}{\text{K}}_{\text{AMB}}\mid \mid \text{Cer}{\text{t}}_{\text{TA}}\left(\text{P}{\text{K}}_{\text{AMB}}\mid \mid \text{I}{\text{D}}_{\text{AMB}}\right)\mid \mid \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\text{other}\hspace{0.17em}\hspace{0.17em}\text{information},\end{array}$$

(1) where $\text{I}{\text{D}}_{\text{AMB}}$ is the identity of AMB, $\text{Cer}{\text{t}}_{\text{TA}}(\text{P}{\text{K}}_{\text{AMB}}\mid \mid \text{I}{\text{D}}_{\text{AMB}})$ is the certificate of public key $\text{P}{\text{K}}_{\text{AMB}}$ signed by TA, $T_i$ is the current timestamp, and $\text{IDSig}(M\mid \mid T_i)$ is the secure identity-based signature [29] with the private key $\text{CS}{\text{K}}_{\text{AMB}}=(h_1(\text{I}{\text{D}}_{\text{AMB}})+s{)}^{-1}P$ to provide the origin authentication on the beacon. Concretely, $\text{IDSig}(M\mid \mid T_i)$ has the following form of $\text{IDSig}(M\mid \mid T_i)=(\alpha ,\beta )$ as

$$\begin{array}{cc}& \alpha =h_2\left(M\mid \mid T_i\mid \mid r\right),\\ \beta =\left(x+\alpha \right)\text{CS}{\text{K}}_{\text{AMB}},\end{array}$$

(2) with a random number $x\in {\mathbb{Z}}_q^{*}$ , and $r=g^x$ .

As AMB's communication range is much larger than regular vehicles, $V_i$ can receive the beacon Bea before AMB enters its communication range. It allows $V_i$ to verify the beacon first and if valid, prepare reregistration message. The actual verification procedure is as follows.

• (i)

In regard to replay attack, $V_i$ first checks the freshness of the beacon. Assuming that $V_i$ receives the message Bea at $T_i^{\prime }$ , $V_i$ checks whether $\mathrm{\Delta }T\ge T_i^{\prime }-T_i$ is valid, where $\mathrm{\Delta }T$ is the preset maximum transmission delay of the system. If the inequality does not hold, $V_i$ discards the outdated message; otherwise, $V_i$ continues the verification.

(ii)

$V_i$ verifies the validity of AMB's certificate Cert using TA's public key. If the following equation

$$\begin{array}{cc}& \text{Verify}(\text{P}{\text{K}}_{\text{TA}},\text{Cer}{\text{t}}_{\text{TA}}\left(\text{P}{\text{K}}_{\text{AMB}}\right))=1\end{array}$$

(3) holds, $V_i$ continues to verify AMB's signature on the message.

(iii)

$V_i$ checks the signature $\text{Sig}(M\mid \mid T_i)$ with

$$\begin{array}{cc}& \alpha =h_2\left(M\mid \mid T_i\mid \mid e(\beta ,h_1\left(\text{I}{\text{D}}_{\text{AMB}}\right)Q+P_{\text{pub}})g^{-\alpha }\right).\end{array}$$

(4)

If (4) holds, the beacon is accepted and $V_i$ continues its reregistration process. Otherwise, $V_i$ waits for new AMB beacons. As aforementioned, all vehicles already have public/private key pairs, public key certificates, and real identities issued by TA. They reregister with TA using the key pairs and real identities. The process of reregistration and key agreement is secured with elliptic curve digital signature algorithm (ECDSA) and elliptic curve integrated encryption scheme (ECIES).

First, vehicle $V_i$ randomly selects $a\in {\mathbb{Z}}_q^{*}$ and concatenates the random element $aP$ and its real identity. Then, $V_i$ encrypts the concatenation with the TA's public key. Finally, $V_i$ encrypts the concatenation of the encryption and the time stamp with AMB's public key PK_AMB and sends it to the AMB in the following form:

$$\begin{array}{cc}& \text{RM}1={\text{ENC}}_{{\text{PK}}_{\text{AMB}}}\left(T_i\mid \mid \mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{ENC}}_{{\text{PK}}_{\text{TA}}}\left(aP\mid \mid {\text{RID}}_i\right)\right),\end{array}$$

(5) where ENC indicates the elliptic curve integrated encryption scheme ECIES, and the same as follows.

Receiving the first message RM1 from vehicle $V_i$ at $T_i^{\prime }$ , AMB decrypts the message and verifies its freshness. If the inequality $\mathrm{\Delta }T\ge T_i^{\prime }-T_i$ holds, it delivers the remaining part of the message, that is, RM2, to TA securely. Otherwise, it discards the message. Consider

$$\begin{array}{cc}& \text{RM}2={\text{ENC}}_{{\text{PK}}_{\text{TA}}}\left(aP\mid \mid {\text{RID}}_i\right).\end{array}$$

(6)

TA decrypts the message and verifies the real identity ${\text{RID}}_i$ . If ${\text{RID}}_i$ is in the revocation list (RL), the message will be abandoned. Otherwise, TA randomly chooses $b\in {\mathbb{Z}}_q^{*}$ , gets $k_i=abP$ and computes $V{K}_i={\text{RID}}_i\oplus h_1(k_i)$ . Next, TA signs the concatenation of $aP$ and $bP$ and then encrypts the signature and $bP$ by $V_i$ 's public key. Then, the $V{K}_i$ and the encryption are sent to AMB securely. Consider

$$\begin{array}{cc}& \text{RM}3=V{K}_i\mid \mid {\text{ENC}}_{{\text{PK}}_i}\left(bP\mid \mid {\text{Sig}}_{{\text{SK}}_{\text{TA}}}\left(aP\mid \mid bP\right)\right).\end{array}$$

(7) In (7), Sig represents the ECDSA signature.

AMB stores the $V{K}_i$ for vehicle authentication subsequently. Then, it passes the message RM4 to vehicle $V_i$ . Consider

$$\begin{array}{cc}& \text{RM}4={\text{ENC}}_{{\text{PK}}_i}\left(bP\mid \mid {\text{Sig}}_{{\text{SK}}_{\text{TA}}}\left(aP\mid \mid bP\right)\right).\end{array}$$

(8)

The vehicle verifies the TA's signature and, if valid, sends its own signature on $aP$ and $bP$ to the TA via AMB. Consider

$$\begin{array}{cc}& \text{RM}5=\text{RM}6={\text{Sig}}_{{\text{SK}}_i}\left(aP\mid \mid bP\right).\end{array}$$

(9)

TA authenticates the vehicle $V_i$ 's signature. If it is valid, a shared secret key $k_i=abP$ between $V_i$ and TA has been established, which is essential for real identity tracing of a malicious vehicle.

The secret key agreement protocol adopts ECDSA signature and ECIES encryption to prevent the intermediate intrusion attacks. Under the assumption of computational Diffie-Hellman problem, the adversary cannot calculate any information about the secret key $k_i$ , ensuring that the real identity of the vehicle can only be tracked by TA.

4.2.2. Pseudonym Self-Generation

In the identity-based cryptography, the entity's public key can be generated based on the real identity. Different pseudonyms are used to sign messages to protect the vehicles from being tracked or associated.

The pseudonym ${\text{ID}}_i$ comprises three parts: ${\text{ID}}_{i,1}$ , $\text{I}{\text{D}}_{i,2}$ , and $\text{E}{\text{T}}_i$ , where ${\text{ID}}_{i,1}$ and ${\text{ID}}_{i,2}$ are the pseudonym material and $\text{E}{\text{T}}_i$ is the life period of this pseudonym. Note that the pseudonym life period $\text{E}{\text{T}}_i$ is predelimited in the system. To generate a pseudonym, the vehicle first selects a random number $r_i\in {\mathbb{Z}}_q^{*}$ to establish point $R_i\in G$ , so that $R_i=(x_i,y_i)=r_{i}P$ . The vertical and horizontal coordinates of each point $R_i$ are integers within ${𝔽}_q$ . Then, the vehicle generates its pseudonym as

$$\begin{array}{cc}& {\text{ID}}_{i,1}=R_i,\\ {\text{ID}}_{i,2}={\text{RID}}_i\oplus h_1\left(k_i\right)\oplus \text{H}\left({\text{ID}}_{i,1}\mid \mid \text{E}{\text{T}}_i\right),\\ \text{I}{\text{D}}_i=\left({\text{ID}}_{i,1},{\text{ID}}_{i,2},\text{E}{\text{T}}_i\right).\end{array}$$

(10) And the corresponding private key ${\text{CSK}}_i$ is

$$\begin{array}{cc}& {\text{CSK}}_i=h_1\left({\text{ID}}_i\mid \mid V{K}_i\right),\\ V{K}_i={\text{RID}}_i\oplus h_1\left(k_i\right).\end{array}$$

(11)

In the end, the vehicle $V_i$ stores a list of the pseudonym ${\text{ID}}_i$ with its corresponding private key ${\text{CSK}}_i$ and the random point $R_i$ . Notice that (1) it is essential to insert life period $\text{E}{\text{T}}_i$ into every pseudonym to prevent attackers from abusing obsolete pseudonyms; (2) the pseudonym and the corresponding private key generation can be completed prior to the broadcast communication. Thus, the delay of signing a message does not include the time of generating the pseudonym and its private key.

4.2.3. Vehicle to AMB Communication

Signing. After the reregistration and the pseudonym generation, vehicles can send perceived information to AMB. And AMB verifies vehicles' messages in batch and delivers the results to the Application Server. Then, the feedbacks from the Application Server are forwarded to vehicles via AMB. Vehicle $V_i$ 's signature ${\sigma }_i$ on message $M_i$ has the following form

$$\begin{array}{cc}& {\sigma }_i=r_i+h_2\left(M_i\mid \mid \text{I}{\text{D}}_i\right){\text{CSK}}_i,\end{array}$$

(12) where $r_i$ is the random integer meeting $R_i=r_{i}P$ . It is obvious that a vehicle needs to compute one hash function and one multiplication to sign a message. Compared to group signature and other identity-based signature, it can significantly save computational cost in the signature generation phase. Finally, $V_i$ broadcasts the message in form of $〈\text{I}{\text{D}}_i,M_i,{\sigma }_i,T_i〉$ as shown in Figure 4.

Figure 4

EPEC1: Vehicle to AMB communication.

Verification. It is computational costly to verify messages one by one. Batch verification allows verifiers to authenticate a number of messages at once, to save computational overhead and reduce verification delay. In EPEC1, vehicles' messages can be verified in batch. Given n distinct signatures ${\sigma }_1,{\sigma }_2,{\sigma }_3,\dots ,{\sigma }_n$ received from $V_1,V_2,V_3,\dots ,V_n$ , respectively, AMB first checks the pseudonym life period $\text{E}{\text{T}}_i$ to prevent attackers from abusing the obsolete pseudonyms. Then, AMB checks the timestamps in the messages, verifies the freshness of every message, and deletes outdated ones. Next, AMB calculates the vehicles' private key ${\text{CSK}}_i$ with the $V{K}_i$ , which satisfies (10); $\text{I}{\text{D}}_{i,2}=V{K}_i\oplus H(\text{I}{\text{D}}_{i,1}\mid \mid \text{E}{\text{T}}_i)$ . Finally, AMB verifies all the signatures in batch. The specific batch verification process is introduced in detail as follows.

• (i)

AMB first checks the pseudonym life period $\text{E}{\text{T}}_i$ to delete obsolete pseudonym signature.

(ii)

For freshness, AMB checks the transmission delay. Assuming that AMB receives the message at $T_i^{\prime }$ , AMB checks whether $\mathrm{\Delta }T\ge T_i^{\prime }-T_i$ is valid. If the inequality holds, AMB continues the verification; otherwise, it discards the outdated message. This step is done for every message.

(iii)

AMB calculates the vehicle's corresponding private key according to (11), $\text{CS}{\text{K}}_i=h_1(I{D}_i\mid \mid V{K}_i)$ .

(iv)

Verify all the signatures by

$$\begin{array}{cc}& \left(\sum {\sigma }_i\right)P=\sum I{D}_{i,1}+\left(\sum h_2\left(M_i\mid \mid I{D}_i\right){\text{CSK}}_i\right)P.\end{array}$$

(13)

If (13) holds, all the signatures are valid in the batch; otherwise, there is at least one invalid signature, which calls for invalid signature detection algorithm to find the invalid ones.

Note that AMB needs to find out the verification key of $V_1,V_2,V_3,\dots ,V_n$ , by checking which of the stored $V{K}_i$ satisfies (10); $\text{I}{\text{D}}_{i,2}=V{K}_i\oplus H(\text{I}{\text{D}}_{i,1}\mid \mid \text{E}{\text{T}}_i)$ . And the private key ${\text{CSK}}_i$ needs to be calculated to achieve authentication during the verifying process. However, the security of our scheme is not destroyed. As even AMB knows $V_i$ 's private key, it is difficult for AMB to forge $V_i$ 's signature. This is because $r_i$ is safe based on the ECDLP problem (in Definition 1), even $\text{I}{\text{D}}_{i,1}$ is publicly known. In addition, vehicles change pseudonyms regularly and different pseudonyms are based on different random number $r_i$ . Thus, AMB cannot get legitimate vehicle's secret key or forge its signature with the obsolete pseudonym and corresponding private key.

4.3. EPEC2: Vehicle Group Communication without AMB

As we do not assume that AMBs cover the whole network, they may forward to another place after networking the vehicles. So, vehicle group communication scheme is requisite for vehicle communication without AMBs.

4.3.1. Vehicle Group Formation

In this subsection, we present how to form a vehicle group with the help of AMB. The establishment of a group is divided into four stages as shown in Figure 5. Concretely, the specific procedure of group formation is detailed as the following.

• (i)

First of all, AMB generates the group request message $M=\{\text{GR},\text{I}{\text{D}}_1,\text{I}{\text{D}}_2,\text{I}{\text{D}}_3,\dots ,\text{I}{\text{D}}_n\}$ to start the group establishment, where $\text{GR}$ indicates the group request and the group identity. AMB broadcasts the message in the form of

$$\begin{array}{cc}& \text{GR}=〈\text{I}{\text{D}}_{\text{AMB}},M,T_i,\text{IDSig}\left(M\mid \mid T_i\right)〉,\end{array}$$

(14) where IDSig is the same identity-based signature as (2).

(ii)

Vehicles receiving the message verify AMB's signature first and, if valid, check for their own pseudonym $\text{I}{\text{D}}_j$ . If found, they generate agreed message $M_j=\{\text{GA},\text{I}{\text{D}}_j\}$ and send it to AMB as follows:

$$\begin{array}{cc}& \text{GA}=〈\text{I}{\text{D}}_i,M_i,{\sigma }_i,T_i〉.\end{array}$$

(15)

(iii)

Receiving all the agreed messages, AMB verifies all the signatures in batch. If the batch verification fails, AMB suspends the protocol and broadcasts new group formation request. Otherwise, AMB sends group key request message GKR to TA applying for the group key. Consider

$$\begin{array}{l}\text{GKR}\\ \hspace{0.5em}=〈\text{I}{\text{D}}_{\text{AMB}},M\left(\text{GR},\text{I}{\text{D}}_1,\text{I}{\text{D}}_2,\dots ,\text{I}{\text{D}}_n\right),T_i,\text{IDSig}\left(M,T_i\right)〉.\end{array}$$

(16)

(iv)

Upon receiving the group key request message GKR, TA verifies AMB's signature. If valid, they choose random number $\text{rand}$ and get the group private key $\text{GSK}=s·\text{rand}$ . TA encrypts the shared group private key with each vehicle's secret key $k_i$ , respectively, and sends the group key establishment message GKE to AMB. Consider

$$\begin{array}{l}\text{GKE}=〈M(\text{I}{\text{D}}_1,\text{I}{\text{D}}_2,\dots ,\text{I}{\text{D}}_n,E_{k_1}\left(\text{GSK}\right),\\ \hspace{1em}\hspace{1em}{E}_{k_2}\left(\text{GSK}\right),\dots ,E_{k_n}\left(\text{GSK}\right)),\\ \hspace{1em}{T}_i,{\text{Sig}}_{{\text{SK}}_{\text{TA}}}\left(M,T_i\right)〉.\end{array}$$

(17) In the GKE message, E is a symmetric encryption algorithm. The message is delivered to the group member via AMB. The group member $V_i$ first verifies TA's signature and then conducts decryption with its own $k_i$ to get the group private key GSK. Finally, $V_i$ calculates the group public key as $\text{GPK}=\text{GSK}·P$ .

Figure 5

EPEC2: Group formation protocol.

4.3.2. Vehicle Group Communication without AMB

After group formation, vehicles can conduct mutual authentication within the group for real-time communication without AMB. With the pregenerated pseudonym $\text{I}{\text{D}}_i$ and the newly generated group private key GSK, $V_i$ generates the signature ${\sigma }_i$ as

$$\begin{array}{cc}& {\sigma }_i=r_i+h_2\left(M_i\mid \mid I{D}_i\right)\text{GSK}.\end{array}$$

(18) The GSK is employed to generate group message signature for more efficient authentication. The group message is broadcasted in the format of $〈\text{GR},\text{I}{\text{D}}_i,M_i,{\sigma }_i,T_i〉$ as shown in Figure 6.

Figure 6

EPEC2: Vehicle group communication.

Receiving the message, the verifier $V_j$ first checks the time validity as aforementioned. If the message is fresh, it comes to the signature verification phase as

$$\begin{array}{cc}& {\sigma }_{i}P=\text{I}{\text{D}}_{i,1}+h_2\left(M_i\mid \mid \text{I}{\text{D}}_i\right)\text{GPK}.\end{array}$$

(19)

Note that the batch verification is also applicable to group communication, providing a much smaller computational overhead of two point multiplication operations. Thus EPEC2 provides much smaller authentication delay than other schemes, which will be detailed in Section 6.

4.4. Invalid Signature Detection

Invalid signature detection algorithm is essential for batch verification scheme. This is because invalid signatures could come from a variety of reasons, such as malicious vehicles, legitimate vehicle failure, or wireless channel interference. The batch verification will fail when there is one invalid signature in the batch. IBV [11] may suffer from severe inefficiency as it does not pay attention to invalid signatures. Once an invalid signature frustrates the batch verification, all the valid ones in the batch will be discarded. Therefore, invalid signature detection mechanism is necessary. ABAKA [12] adopted the binary search method for invalid signature detection. When the batch verification fails, messages in the batch are bisected, and verified, respectively until only one message left or valid. But it is inefficient to retest the messages for $d\lceil \text{lo}{\text{g}}_2(n)\rceil$ times, where n and d are the total message number and the invalid signature number in the batch, respectively. In order to reduce rebatch verification overhead, we adopt the Generalized Binary Splitting algorithm [30], which is the most efficient testing algorithm when d is not very great. In the worst case that all the d invalid signatures are divided into different subbatches during each section, the number of tests required is as follows:

$$\begin{array}{cc}& \text{N}{\text{T}}_{\text{GBS}}=d-1+\lceil \text{lo}{\text{g}}_2\left(n*d\right)\rceil .\end{array}$$

(20) And the precise re-batch verification cost caused by invalid signature detection will be discussed in Section 6.

5. Security Analysis

We analyze the security performance of the proposed scheme EPEC in this section. According to the security objectives aforementioned, EPEC is evaluated in the following four aspects: dynamic reregistration without fixed RSUs, mutual authentication, conditional privacy preservation, and internal attacks prevention. And the efficiency of EPEC is analyzed in Section 6 in three different aspects. The security of EPEC is analyzed as follows.

Dynamic Reregistration without Fixed RSUs. AMBs authorized by TA enter the disaster area for networking the regular vehicles. In EPEC, AMBs don't cover the entire network. Vehicles dynamically reregister with TA when AMB is available. In addition, vehicles are able to update their secret keys via other AMBs.

Mutual Authentication. The proposed scheme EPEC securely achieves mutual authentication during the process of vehicles reregistration and broadcast communication. On arriving, AMB authenticates itself securely to vehicles by identity-based signature [29]. Next, vehicles authenticate themselves with ECDSA signature. The secure signatures guarantee mutual authentication among vehicle, AMB, and TA. In addition, the proposed lightweight pseudonym based signature enforces mutual authentication in broadcast communication. Pseudonym $\text{I}{\text{D}}_i$ used during broadcast communication is self-generated with $V_i$ 's unique secret key $k_i$ and real identity ${\text{RID}}_i$ , which guarantees that no one else can forge $V_i$ 's pseudonym and signature. The signature also ensures that only the unmodified messages from legitimate senders are accepted. Because once the message content is distorted during the transportation, the signature verification will fail.

Conditional Privacy Preservation. The actual identity of a vehicle is concealed by the pseudonym in EPEC. As vehicle's secret key used to generate pseudonym is exclusive and can't be compromised because of the computational Diffie-Hellman problem. In addition, regular pseudonym changing prevents attackers from tracing a specific vehicle in the long term. But on the other hand, malicious vehicles should be revealed and revoked from the network in time. TA, and only TA is allowed to trace the real identity of a vicious vehicle. For example, once $V_i$ is found misbehaving, the $\text{I}{\text{D}}_i$ is reported to TA. Then, TA reveals the real identity ${\text{RID}}_i$ through the following process:

$$\begin{array}{l}\text{I}{\text{D}}_{i,2}\oplus h_1\left(k_i\right)\oplus H\left(\text{I}{\text{D}}_{i,1}\mid \mid \text{E}{\text{T}}_i\right)\\ \hspace{1em}=\text{RI}{\text{D}}_i\oplus h_1\left(k_i\right)\oplus H\left(\text{I}{\text{D}}_{i,1}\mid \mid \text{E}{\text{T}}_i\right)\oplus h_1\left(k_i\right)\\ \hspace{1em}\hspace{1em}\oplus H\left(\text{I}{\text{D}}_{i,1}\mid \mid \text{E}{\text{T}}_i\right)\\ \hspace{1em}=\text{RI}{\text{D}}_i.\end{array}$$

(21) And it is TA that determines whether to revoke $V_i$ from the system or not. The specific revocation mechanism is out of the scope of our paper.

Internal Attacks Prevention. Another important security property of EPEC is the ability to prevent internal attacks. Even if an attacker has captured some vehicles and got their private keys, the attacker still can't forge a valid signature of other legitimate vehicle, because it knows neither the private key nor the private secret used to reveal the real identity of the legitimate vehicle. In addition, the damage caused by the captured vehicles is also limited, because the tracking mechanism can quickly retrieve the real identities of these vehicles. TA can revoke the malicious vehicles from the network promptly.

6. Performance Evaluation

In this section, the effectiveness of EPEC is evaluated in terms of message verification delay, transmission overhead, and verification delay with invalid signatures. In the evaluation, EPEC is compared with four related typical schemes: IBV [11], ABAKA [12], ECDSA [13], and CPAS [15]. IBV is a typical batch verification scheme for unidirectional authentication based on bilinear pairing operations. ABAKA is a point multiplication based signature scheme with batch verification. Reference [13] presents a key establishment and authentication protocol RAISE based on ECDSA signature in the IEEE standard 1609.2. It is referred to as ECDSA in the evaluation. CPAS is a typical mutual authentication scheme with batch verification based on bilinear pairing operations.

6.1. Message Verification Delay

To evaluate and compare the schemes' verification delay, we first define the time complexity of the main cryptographic operations required in our EPEC and other schemes. Let $T_{\text{mtp}}$ , $T_{\text{mul}}$ , and $T_{\text{par}}$ denote the time to perform a MapToPoint hash operation, a point multiplication over an elliptic curve, and a bilinear pairing operation, respectively. According to [31], $T_{\text{mul}}$ is 0.6 ms, $T_{\text{mtp}}$ is 0.6 ms, and $T_{\text{par}}$ is 4.5 ms. It is apparent that the computational time of MapToPoint hash operation and point multiplication is much smaller than bilinear pairing operation. We don't consider the cost of one way hash function, which is only 2 microseconds. Table 3 shows the computational overhead of all the schemes in terms of authenticating a single message and n messages.

Table 3

Computational overhead.

Schemes	Authenticate a single message	Authenticate n messages
ECDSA	${4T}_{\text{mul}}$	${4nT}_{\text{mul}}$
IBV	${3T}_{\text{par}}+T_{\text{mtp}}+T_{\text{mul}}$	${3T}_{\text{par}}+{nT}_{\text{mtp}}+{nT}_{\text{mul}}$
ABAKA	${3T}_{\text{mul}}$	$(2n+1)T_{\text{mul}}$
CPAS	${3T}_{\text{par}}+{2T}_{\text{mul}}$	${3T}_{\text{par}}+(n+1)T_{\text{mul}}$
EPEC1	$T_{\text{mtp}}+{2T}_{\text{mul}}$	${nT}_{\text{mtp}}+{2T}_{\text{mul}}$
EPEC2	${2T}_{\text{mul}}$	${2T}_{\text{mul}}$

Notice that IBV is an authentication scheme without mutual authentication and key agreement. So, for fairness, the schemes are compared in unidirectional authentication case without key agreement. The mutual authentication function of EPEC is analyzed in Section 5. And for EPEC, the broadcast authentication cost equals on the two sides. From the comparison in Table 3, we can see that the proposed scheme EPEC achieves the least computational overhead. ECDSA verifies n distinct signatures one by one; so, the n messages verification is the most inefficient. Although IBV adopts batch verification, the basic pairing operation is computational costly. ABAKA also verifies signatures with point multiplications, but the verification cost is much higher than our EPEC.

The computational overhead increases with the number of messages for all these schemes. The message verification delay ratio of these schemes is shown in Figure 7. It is apparent that EPEC is superior to all the other typical schemes, because EPEC adopts lightweight point multiplication to verify messages. Figure 7(a) indicates the relationship between EPEC1 and other schemes. It is obvious that the delay ratio between EPEC1 and ABAKA is always less than 0.50 regardless of the number of messages; the delay ratio between EPEC1 and ECDSA is approximately 0.25 when the number of messages is larger than 60. From Figure 7(b), we can see that the delay ratio between EPEC2 and other schemes approaches zero with the traffic density increasing, which is because the batch verification overhead has nothing to do with the number of messages for EPEC2.

Figure 7

Verification delay ratio with different traffic density.

6.2. Transmission Overhead

We consider the transmission overhead in terms of the signature and the certificate appended to the original message, while the message itself is not counted. The comparison of all the schemes is shown in Table 4. ECDSA signature is 42 bytes in length, but a certificate of 125 bytes must be transmitted along with each message, resulting in the total transmission overhead of 167 bytes. For IBV, the length of signature is 21 bytes, while pseudonym is 42 bytes. In ABAKA, the 20 bytes verification message and the 20 bytes material message all are authentication materials, resulting in a signature of 40 bytes. CPAS has 60 bytes signature, 41 bytes pseudonym, and 4 bytes message type information.

Table 4

Transmission overhead.

Schemes	One message	n messages
ECDSA	181 B	181n B
IBV	63 B	63n B
ABAKA	80 B	80n B
CPAS	105 B	105n B
EPEC1	82 B	82n B
EPEC2	84 B	84n B

The transmission overhead of ECDSA is the largest among the five schemes, while IBV has the smallest. Since IBV adopts bilinear pairing cryptographic operations for signature, which is short in length but costly in verification. The overhead of ABAKA is a bit less than EPEC, which is because 2 bytes life period $\text{E}{\text{T}}_i$ is added to the pseudonym in our scheme to prevent expired pseudonyms abuse. For group communication EPEC2, there is additional 2 bytes group ID information. Obviously, the transmission overhead increases linearly for all the schemes with the number of messages.

6.3. Verification Delay with Invalid Signatures

Batch verification can save computational overhead and provide low verification delay. However, the expense of the batch verification is that invalid signature may cause verification failure and re-batch verification is needed. As aforementioned, GBS is the most efficient invalid signature detection scheme when the number of invalid signatures is not very great. We adopt GBS, while the IBV and ABAKA use binary search algorithm to check the invalid signatures. Table 5 shows the computational overhead for first batch verification and one time re-batch verification. ABAKA and EPEC only need point multiplications for re-batch verification, while IBV and CPAS need three bilinear pairing operations.

Table 5

Computational overhead with invalid signatures.

Schemes	First batch verification	Rebatch verification
IBV	${3T}_{\text{par}}+{nT}_{\text{mtp}}+{nT}_{\text{mul}}$	${3T}_{\text{par}}$
ABAKA	$(2n+1)T_{\text{mul}}$	${1T}_{\text{mul}}$
CPAS	${3T}_{\text{par}}+(n+1)T_{\text{mul}}$	${3T}_{\text{par}}$
EPEC1	${nT}_{\text{mtp}}+{2T}_{\text{mul}}$	${2T}_{\text{mul}}$
EPEC2	${2T}_{\text{mul}}$	${2T}_{\text{mul}}$

The verification delay $\text{VD}$ with invalid signatures in the worst case is computed with

$$\begin{array}{cc}& \text{VD}=1*\text{V}{\text{T}}_{\text{first}}+\text{NT}*\text{V}{\text{T}}_{\text{re-batch}},\end{array}$$

(22) where $\text{V}{\text{T}}_{\text{first}}$ is the verification time needed for the first batch verification, $\text{NT}$ is the number of tests needed to find all $d(d\ge 1)$ invalid signatures, and $\text{V}{\text{T}}_{\text{re-batch}}$ is the verification time for one time re-batch verification. The verification delay for EPEC1 is

$$\begin{array}{l}\text{V}{\text{D}}_{\text{EPEC}1}=\left(n*T_{\text{mtp}}+2*T_{\text{mul}}\right)\\ +\left(d-1+\lceil \text{lo}{\text{g}}_2\left(n*d\right)\rceil \right)*\left(2*T_{\text{mul}}\right),\end{array}$$

(23) with $\text{N}{\text{T}}_{\text{GBS}}$ in (20). And for other schemes, binary search is adopted for invalid signature detection with the tests number of $\text{N}{\text{T}}_{\text{BS}}=d*\lceil \text{lo}{\text{g}}_2(n)\rceil$ .

Figure 8 gives the verification delay ratio with the number of invalid signatures. In the experiment, the messages number n is set 300. It is apparently shown that our EPEC achieves the smallest verification delay with invalid signature detection compared to other three typical schemes. The efficiency of IBV and CPAS decreases markedly with the number of invalid signature increasing, because their re-batch verification requires three time-consuming bilinear pairing operations. EPEC2 achieves high efficiency even when the number of invalid signatures is large.

Figure 8

Verification delay ratio with invalid signatures.

7. Conclusion

In this paper, we propose an expedite privacy-preserving emergency communication (EPEC) scheme for VANETs-based disaster rescue. EPEC fulfils two communication patterns: EPEC1 for vehicle networking with AMB and EPEC2 for vehicle group communication without AMB, respectively. By the theoretical and experimental analyses, we show that the proposed scheme has the following advantages. (1) No Fixed RSU. Vehicles are able to reregister themselves with TA dynamically. (2) Conditional Privacy Preservation. EPEC allows only TA to trace malicious vehicle's real identity. (3) Internal Attacks Prevention. The captured vehicles can only cause limited damage to the whole networks. (4) High Efficiency. Lightweight signature and batch verification are combined to reduce authentication delay. And identity-based signature is adopted to save the delivery cost of public key certificates. To sum up, EPEC represents expedite authentication and satisfies the conditional privacy preservation requirement in emergency communication.