Efficient location-based conditional privacy-preserving authentication scheme for vehicle ad hoc networks

Abstract

Due to the real-time requirement of message in vehicle ad hoc networks, it is a challenge to design an authentication for vehicle ad hoc networks to achieve security, efficiency, and conditional privacy-preserving. To address the challenge, many conditional privacy-preserving authentication schemes using bilinear pairing or ideal tamper-proof device have been proposed for vehicle ad hoc networks in recent years. However, the bilinear pairing operation is one of the most complex cryptographic operations and the assumption of tamper-proof device is very strong. In this article, an efficient location-based conditional privacy-preserving authentication scheme without the bilinear pairing and tamper-proof device is proposed. Compared with the most recently proposed authentication schemes, the proposed scheme markedly decreases the computation costs of message signing and message verification phase, while satisfies all security requirements of vehicle ad hoc networks and provides conditional privacy-preserving.

Keywords

Vehicle ad hoc networks efficiency conditional privacy-preserving elliptic curve cryptosystem

Introduction

With the substantial increase in vehicle ownership, people’s life and occupation have more and more closer relationship with vehicles. As a result, the importance of promoting traffic safety and efficiency is more and more highlighted. Over the past decade, vehicle ad hoc networks (VANETs) have drawn great attention from the government, academia, and industry. The security applications and value-added applications are proposed to improve the traffic safety and driving experience.^1,2 In general, a VANET consists of vehicles equipped with onboard units (OBUs), fixed roadside units (RSUs), and a trusted authority (TA). Vehicle’s OBU communicates with other vehicles and RSUs via a public wireless channel. RSUs also connect TA via wired channel. A general system architecture of VANETs is shown in Figure 1. According to dedicated short-range communication (DSRC) protocol, OBUs broadcast traffic-related messages and vehicles’ condition messages periodically at every 100–300 ms, where traffic-related messages include congestion state, traffic events, and so on, and vehicles’ condition messages include speed, current time, direction, position, and so on. With these messages, the application can obtain better awareness of traffic data and provide the best solution for vehicles.^3,4

Figure 1.

The general system architecture of VANETs.

Traffic-related messages are always transmitted by open channels and are vulnerable to various security attacks, privacy-leaking, and compromise. Therefore, prior to deployment of the promising applications in VANETs, the security and privacy issues of VANETs should be solved. To ensure the reliability and integrity of messages, message authentication scheme is involved in VANETs.⁵ In general, the vehicles (i.e. the vehicle’s owner) do not want their private information to be exposed or be traced from the messages they have broadcasted, so VANETs should protect some sensitive information of the message generator. On the contrary, as a message involves in a controversial matter, there is one and only one, such as the trusted legal authority, that is able to retrieve the real identity of message generator. It is the so-called conditional privacy-preserving, which has been an urgent security requirement for VANETs.^6–8 Traffic-related messages in VANETs are real-time and should be processed promptly, and therefore, another intractable issue is the efficiency of message signing and verification. Fortunately, many message authentication schemes have been proposed to address security, efficiency, and conditional privacy-preserving for VANETs during the recent 10 years.^8
–23

Related work

Roughly speaking, there are two categories of conditional privacy-preserving authentication (CPPA) schemes for VANETs: schemes using group signatures and schemes using varied pseudonyms. In the first category, vehicles sign messages with the group signature.²⁴ To be specific, a vehicle can sign its messages on behalf of the whole group to hide its real identity with a signing key which is allocated by the group manager once it joins the vehicle group legally. Some interesting schemes are presented in previous studies.^9–13 Because no one (except the group manager) can distinguish the signer of any message among the group member but the group manager can retrieve the real identity of message signers, these schemes can achieve conditional privacy-preserving well. However, the computation costs of these schemes are much more than that of the traditional signature. In addition, it may have to construct the whole group when vehicles are revoked. Therefore, group signature schemes are not suitable for the large-scale VANETs. Although some group signatures with verifier-location revocation, such as Boneh and Shacham,²⁵ can alleviate revocation problem, they are still very inefficient in revocation when the number of revoked vehicles is increasing.²⁶

In the second category, a vehicle signs messages with different pseudonyms and corresponding signing keys. In 2005, Raya and Hubaux¹⁴ proposed a concrete anonymous authentication based on traditional signatures and anonymous certificates. In Raya et al.’s scheme, each vehicle should store a number of anonymous certificates and corresponding public/private key pairs, so that the vehicle can use different public/private keys in different authentication processes. Consequently, vehicles have to spend a mass of storage space to store public pairs in Raya et al.’s scheme. Freudiger et al.¹⁵ proposed an anonymous scheme using mix-zones. But it still does not resolve the problem of certificates’ stores. Lu et al.¹⁰ proposed an anonymous authentication using temporary anonymous certificates based on the group signature, in which the certificates are issued by an RSU when vehicles pass the RSU. Nevertheless, Lu et al.’s scheme is inefficient because of frequent and transient bilateral communication in certificates’ issues. To achieve secure communication with low communication overhead, Zhang et al.¹⁶ proposed a message authentication using Hash Message Authentication Code (HMAC). However, their scheme needs to preload a certain amount of certificates to each vehicle. In the aforementioned authentication schemes, a large number of anonymous certificates raise an insurmountable problem to the management and storage of certificates.^17,26

To solve the problem of certificates’ management, identity-based public key cryptosystem (PKC)²⁷ has been adopted to construct message authentication for VANETs, which needs no certificate to be bound to user’s identities and public keys. Zhang et al.¹⁸ proposed an efficient authentication scheme using identity-based PKC. Zhang et al.’s scheme assumes that each vehicle is equipped with a tamper-proof device (TPD), which is supposed to be secure against any security attacks and infeasible to extract the data, including secret keys and codes, for any adversaries. Hence, each vehicle in Zhang et al.’s scheme can generate a pseudonym and corresponding signing key with TPD. To improve efficiency, Zhang et al.’s scheme provides batch verification to achieve the simultaneous verification for a large number of messages. But Zhang et al.’s scheme suffers from the relay attack and impersonation attack and cannot provide the function of non-repudiation.^19,20 In recent years, researchers have proposed some similar authentication schemes for VANETs.^{8,13,21–23,28–30} These schemes can solve the problem of certificates’ management perfectly and achieve conditional privacy-preserving well. But these schemes are predicated on bilinear pairs, which is one of complex cryptographic operations. He et al.⁷ proposed a new similar authentication scheme (called CPPA), which uses elliptic curve cryptosystem (ECC) instead of bilinear pairs. They demonstrated that CPPA achieves a better performance in terms of computation and communication cost than other similar schemes. However, the schemes using TPD are subjected to two key issues. On one hand, the security assumption of TPD is very strong.^31,32 If the master key of the authority is corrupted from any TPD, the whole system will be devastated. On the other hand, TPD is much expensive and normally costs several thousand dollars,³³ which is very hard for all vehicle owners to pay several thousand dollars for TPD.

In view of the potential deficiency of TPD, some researchers proposed identity-based CPPA scheme without TPD.^34–37 Chim et al.³⁴ proposed a software-based solution to construct message authentication scheme, called secure and privacy enhancing communications schemes (SPECS), which does not rely on any special hardware. In SPECS, the vehicle uses a different pseudo identity for each session to achieve conditional privacy-preserving. However, Horng et al.³⁵ demonstrated that SPECS³⁴ is vulnerable to impersonation attack and proposed an improved scheme over SPECS. Xue and Ding³⁶ proposed a top–down security authentication scheme, called location-based privacy-preserving authentication protocol (LPA). In LPA, the top authority authorizes the RSUs to issue group certificates to vehicles. Malhi and Batra³⁷ proposed a secure privacy-preserving authentication framework for VANETs (called privacy-preserving authentication framework using bloom filter (PAFB)). Multiple authorities are involved to retrieve the real identity of a message. The performance analysis showed that PAFB is much more efficient than similar schemes in terms of computation and communication cost.

Motivation and contributions

In most recent years, several authentication schemes based on bilinear pairing without any special security devices (e.g. TPD)^35–37 have been proposed for VANETs. These schemes have overcome some serious weaknesses that exist in the certificate-based authentication scheme and shown better computation and security performance than previously proposed similar schemes. Nevertheless, bilinear pairing operation is involved in these schemes, which is a complex cryptographic operation. To achieve the security level of 80 bits, bilinear pairing should construct the paring operation and scalar multiplication operation using a super singular curve.³⁸ In VANETs, the OBUs and RSUs are limited in computational capability. According to DSRC protocol, vehicles or RSUs often receive a huge number of messages in a short time, and most of these messages in VANETs are time-sensitive and life-critical that should be verified and processed timely. As the bilinear pairing operations are too complex for OBUs and RSUs, these schemes still cannot satisfy the computation requirement of VANETs, especially for vast message verifications. Therefore, it is still a rewarding challenge to design an efficient and secure authentication scheme without using TPD for VANETs.

To address the challenge, we propose a new secure and efficient CPPA scheme using ECC, which could use a non-super singular curve to achieve the security level of 80 bits and decrease computation cost sharply. In brief, there are threefold contributions of this article:

We propose a new location-based CPPA scheme for VANETs without using any special device, such as ideal TPD.

The proposed scheme is constructed based on ECC without any complex bilinear pairing operations. In addition, the batch message verification is provided in the proposed scheme to improve the verification efficiency. The performance analysis and comparison show that the proposed scheme can achieve better performance than other similar schemes.

The security analysis demonstrates that the proposed scheme can meet the security and privacy requirements of VANETs.

The rest of this article is organized into five sections: section “Background” introduces the research background. The proposed authentication scheme for VANETs is proposed in section “The proposed scheme.” The security analysis is demonstrated in section “Security analysis.” Performance analysis is shown in section “Performance analysis and comparison.” Finally, conclusion is given in section “Conclusion.”

Background

System architecture

The three-layer network model³⁷ is adopted in this article. The top layer includes regional trusted authority (RTA) and key generation center (KGC), the middle layer includes RSUs, and the lower layer includes vehicles, as shown in Figure 1:

KGC and RTA: The KGC is viewed as a trusted administrator, and it is responsible for system parameters’ generation and allocates partial registered vehicles. The RTA is in charge of the public key management of registered vehicles and RSU under its jurisdictional area and is responsible for the deployment and monitoring. The KGC and the RTA can retrieve the real identity from wrong messages (i.e. a message with valid signature but untrue content) jointly.

OBUs: Each vehicle is equipped with an OBU and global position system (GPS) module. An OBU regularly broadcasts messages about traffic status, such as position, direction, speed, traffic condition, danger warming, and others. Moreover, it is in charge of communication with other OBUs and RSUs according to DSRC protocol.

RSUs: RSUs are some fixed substance units along roadside. An RSU can communicate with vehicle’s OBU via DSRC and connects RTA via a wired channel. RSUs are monitored by the RTA periodically. We assume that if an RSU is compromised, it will be detected soon and informed to its neighbor RSUs by the RTA.³⁷ Each RSU maintains a list of neighbor RSUs. If a neighbor in its list is compromised, the RSU will broadcast to vehicles within its communication range. When the compromised RSU is recovered, the RTA and RSUs will undo the former operation.

Threat model

The VANET system would suffer from various security attacks when providing secure driving service and some other application service. In our proposed system model of secure message authentication, we assume that the TA is fully trusted by other parties in the system, and it has the highest security level so that it can hardly be attacked by adversaries. And the authentication server (AS) is a credible service center as well. Thus, in this system, there are two major types of attackers who can implement security attacks.^16,20

The external attacker

This kind of attackers can damage the VANET system via launching a series of security attacks, such as impersonation attacks (i.e. legal vehicles, RSUs and application servers), tampering attacks, replay attacks, DoS attacks, and tracking attacks. Usually, an external attacker will resort to unscrupulous means to achieve their attack goals.

The internal attacker

This kind of attackers is usually some malicious registered vehicles. They are likely to maximize their interest by the security vulnerabilities of the system. For example, a malicious vehicle may publish fake message about traffic congestion to tempt other vehicles to change their routes so that the malicious one can get better road resources. And the malicious vehicle can use a fake identity or collude with others to derive its own benefits. What is more, some malicious vehicles can tamper the position information to escape from traffic responsibility. Nevertheless, such attackers will not attack the system on the occasion of having known that it will be held accountable or no benefits.

Security requirements

In this article, similar to Malhi and Batra,³⁷ we assume that the KGC and the RTA are infeasible to compromise by any adversaries and can be completely trusted, which is a common assumption in VANET schemes.^18,21,31 We also assume that once a compromised RSU could be checked out timely, it is under the real-time monitor of the RTA.^36,37 Based on the assumption, authentication schemes for VANETs should satisfy the security and privacy requirements as follows:

Message integrity and authentication: In VANETs, a message should be authenticated. For this, the message’s generator can be ensured as a registered member of the system and the message is the original one without any modification.³⁹

Traceability: When a vehicle is involved in a controversial matter, the TA should be able to retrieve the real identity of the messages related to this matter for justice. Otherwise, inside attackers and malicious users have no qualms to broadcast wrong messages to other vehicles.

Provide conditional privacy-preserving: Like privacy-preserving in other scenarios, the real identity of a vehicle must be anonymous to any others, including vehicles, RSUs, and attackers. However, a maliciously behaved registered vehicle may broadcast wrong messages by abusing the anonymity function. To prevent the registered vehicles from abusing the property of anonymity, the RTA and KGC should be able to retrieve the identity of the message generator. Therefore, the authentication scheme should provide conditional privacy-preserving.

Resistance to modification attack: Because the messages of VANETs are delivered in unsecure wireless communication channels, the adversary can easily obtain and modify messages. The proposed authentication scheme should be able to resist the modification attack.

Resistance to impersonation attack: The adversary can send messages to others to impersonate an illegal vehicle to destroy traffic safety or obtain personal interest. Therefore, the proposed authentication scheme should be able to resist the impersonation attack.⁴⁰

Resistance to replay attack: This attack is a form of security attack in which a valid data transmission is maliciously or fraudulently repeated or delayed. In VANETs, the adversary can get the messages of other vehicles and launch security attack by repeating these messages. Therefore, the proposed authentication scheme should be able to resist the replay attack.

Resistance to man-in-the-middle attack: This attack is an attack where the attacker secretly relays and possibly alters the communication between two parties who believe they are directly communicating with each other. In VANETs, an attacker can launch this attack more easily.³⁷ Therefore, the proposed authentication scheme should be able to resist man-in-the-middle attack.

The proposed scheme

In this section, we propose a new efficient CPPA for vehicular communications. The proposed scheme consists of five phases: system setup, pseudonym allocation, message signing phase, message verification phase, and identity extraction phase. To simplify the presentation, the notations used in this article are listed in Table 1.

Table 1.

Notations used and description.

Symbol	Description
p, q	Two large prime numbers
G	Additive group of prime order q
P	Generator of G
$E_{p} (a, b)$	Elliptic curve: $y^{2} = x^{3} + ax + b mod p$
KGC	Key generation center
s	Secret key of KGC
P_pub	$P_{pub} = sP$ ; it is the public key of KGC
RTA	Regional trusted authority
$P_{RTA} / λ$	Conventional public/private key pairs of RTA
RSU	Road side units
$P_{RS U_{j}} / y_{j}$	Public/private key pairs of $RS U_{j}$ , $P_{RS U_{j}} = y_{j} \cdot P$
$I D_{vi}$	Identity of vehicle $V_{i}$
$P_{vi} / x_{vi}$	Conventional public/private key pairs of vehicle $V_{i}$
$QI D_{vi}$	$QI D_{vi} = H_{3} (I D_{vi})$ ; it is the partial public key of vehicle $V_{i}$
$p p_{vi}$	$p p_{vi} = s \cdot QI D_{vi}$ ; it is the partial secret key of vehicle $V_{i}$
$E_{pk} (.) / D_{sk} (.)$	Encryption function with pk and decryption function with sk
$SI G_{sk} (.)$	Signature function with key sk

Like the analysis in section “Background,” we assume that KGC and RTAs can be trusted completely; they are infeasible to compromise by any adversaries, and the compromised RSUs can be checked out by RTA timely.

System setup

The system setup includes two processes: initialization parameters and management for RSUs’ registration for vehicles.

The initialization parameters are executed by the KGC as the following steps:

S1: The KGC chooses an elliptic curve $E_{p} (a, b)$ defined by equation $y^{2} = x^{3} + ax + b mod p$ , where p is a large prime, $a, b \in F_{p} W$ and then selects a point P on $E_{p} (a, b)$ as a generator of group G with order q, where G is an additive group of prime order q. Next, the TA selects a key $s \in Z_{q}^{*}$ as its eternal private secret key and calculates $P_{pub} = sP$ as its public key.

S2: The KGC chooses four secure hash functions, $H_{1} : {0, 1}^{*} \to G$ , $H_{2} : G \times G \times G \to Z_{q}$ , $H_{3} : {0, 1}^{*} \times G \times {0, 1}^{*} \times {0, 1}^{*} \times {0, 1}^{*} \times G \times G \to Z_{q}$ , and $H_{4} : {0, 1}^{*} \times G \times {0, 1}^{*} \times {0, 1}^{*} \times G \times G \times G \to Z_{q}$ , as cryptographic hash functions used in the scheme. It also defines conventional encryption/decryption functions $E_{pk} (.) / D_{sk} (.)$ and a signature function $SI G_{sk} (.)$ , where pk/sk are the keys for encryption/decryption/signature.

S3: The TA sets $paras = {E_{p} (a, b), p, q, G, P, H_{1}, H_{2}, H_{3}, H_{4}, P_{pub}, E_{pk} (.) / D_{sk} (.), SIG (.)}$ as the system public parameters and publishes paras to all RTAs, RSUs, and vehicles.

Each RTA selects $(λ, P_{RTA})$ as its public/private key pairs and publishes $P_{RTA}$ as its public key and manages RSUs and vehicles in its administrative region.

RSUs with location $lo c_{j}$ (suppose named $RS U_{j}$ ) are deployed by the RTA and are allocated conventional public/private key pairs $(y_{j}, P_{RSUj})$ . RSUs are constantly monitored by the RTA. Once an RSU is corrupted, it will be excluded from the system by the RTA and will be informed to its neighbor RSUs. If a compromised RSU is recovered, the RSU will be included and informed to its neighbor RSUs. RSUs broadcast their own public keys and neighbor RSUs’ information (e.g. the identities and public keys of normal RSUs, the identities of corrupted RSUs) regularly.

The registration of the vehicle is executed as follows:

R1: Assume each vehicle obtains a unique identifier $I D_{vi}$ when it is purchased and obtains $p p_{vi}$ from the TA via secure channel, where $p p_{vi} = s \cdot H_{1} (I D_{vi})$ . Then the vehicle chooses $(x_{vi}, P_{vi})$ as its public/private key pairs and sends $E_{P_{RTA}} (P_{vi}, I D_{vi}, SI G_{x_{vi}} (P_{vi}, I D_{vi}))$ to the RTA.

R2: Upon receiving message $E_{P_{RTA}} (P_{vi}, I D_{vi}, SI G_{x_{vi}} (P_{vi}, I D_{vi}))$ , the RTA decrypts $D_{λ} (P_{vi}, I D_{vi}, SI G_{x_{vi}} (P_{vi}, I D_{vi}))$ and checks signature $SI G_{x_{vi}} (P_{vi}, I D_{vi})$ . If the signature is true, the RTA computes $QI D_{vi} = H_{1} (I D_{vi})$ and then stores the tuple $(P_{vi}, QI D_{vi}, I D_{vi})$ in its database and sends $E_{P_{vi}} (QI D_{vi}, SI Q_{λ} (QI D_{vi}))$ to the vehicle.

R3: After receiving $E_{P_{vi}} (QI D_{vi}, T, SI G_{λ} (QI D_{vi}, T))$ , the vehicle decrypts messages with its $x_{vi}$ and verifies signature with the public key $P_{RTA}$ . If the signature is true, the registration in the RTA is successful.

Pseudonym allocation phase

To achieve conditional privacy-preserving, the random short-term pseudonyms are adopted in our proposed scheme. The short-term pseudonym allocation mechanism of the proposed scheme allows a vehicle to require short-term pseudonyms from a new RSU if it comes within the communication range of the RSU. Then the vehicle uses its new pseudonyms to communicate with others when it is in the coverage of the RSU. The pseudonym allocation steps are described as follows:

P1: The vehicle $I D_{vi}$ selects current time $T_{vi}$ , where $T_{vi}$ is a time with the precision of an hour and the pseudonym with $T_{vi}$ expires an hour later, and then sends message $E_{P_{RSU}} (T_{vi}, loc, P_{vi}, si g_{x_{vi}} (T_{vi}, loc, P_{vi}))$ to RSU for new short-term pseudonym, where loc is the location of the vehicle that is generated by GPS.

P2: Upon receiving message $E_{P_{RSU}} (T_{vi}, loc, P_{vi}, si g_{x_{vi}} (T_{vi}, loc, P_{vi}))$ , the RSU decrypts the message with its private key y and checks the validity of the signature $si g_{x_{vi}} (T_{vi}, loc, P_{vi})$ and loc. If the signature is valid and loc is within its communication range, the RSU requires the RTA to check whether that the $P_{vi}$ is in the RTA’s database. If it does not exist, the RSU terminates this session. Else, the RSU obtains the corresponding $QI D_{vi}$ and sends $E_{p_{vi}} (PI D_{vi}, P_{vi}, SI G_{y} (PI D_{vi}, P_{vi}))$ to the vehicle.

P3: When receiving responding message, the vehicle decrypts the message with its own secret key $x_{vi}$ and checks whether the received ${PI D_{vi}, P_{vi}}$ is the same as its own ${PI D_{vi}, P_{vi}}$ . If not, the vehicle terminates the session. Else, the vehicle checks whether the signature of the message is valid or not. If it is not, the vehicle terminates this session, or the vehicle sends message $E_{P_{RSU}} (QI D_{vi}, P_{vi}, si g_{x_{vi}} (QI D_{vi}, P_{vi}))$ to the RSU.

P4: Upon receiving message $E_{P_{RSU}} (QI D_{vi}, P_{vi}, si g_{x_{vi}} (QI D_{vi}, P_{vi}))$ , the RSU decrypts the message and checks the validity of the signature. If the signature is not valid, the RSU terminates this session. Else, the RSU selects t random numbers $u_{1}, u_{2}, \dots, u_{t} \in Z_{q}^{*}$ and then computes $PI D_{vi} = u_{i} \cdot P$ and $k_{vi} = u_{i} + y \cdot H_{2} (PI D_{vi}, P_{RSU}, T_{vi})$ for each $u_{i}$ , that is, it will generate t short-term pseudonyms and the corresponding partial secret keys, where t is a small integer decided by RTA according to the actual requirements. Let $[PI D_{vi}, k_{vi}]_{t}$ denote the t short-term pseudonyms and the corresponding partial secret keys. Then the RSU stores the t tuple ${PI D_{vi}, P_{vi}}$ in RTA’s database for later real identity tracing and sends $E_{p_{vi}} ([PI D_{vi}, k_{vi}]_{t}, SI G_{y} ([PI D_{vi}, k_{vi}]_{t}))$ to the vehicle.

P5: When receiving message $E_{p_{vi}} ([PI D_{vi}, k_{vi}]_{t}, SI G_{y} ([PI D_{vi}, k_{vi}]_{t}))$ , the vehicle decrypts the message and checks whether the signature of the message is valid or not. If it is valid, the vehicle stores $[PI D_{vi}, k_{vi}, T_{vi}]_{t}$ in secret. Else, the vehicle drops this message.

The schematic flow of pseudonym allocation phase is shown in Figure 2.

Figure 2.

The progress of the pseudonym allocation.

Message signing phase

After the above pseudonym allocation phase, the vehicle $I D_{vi}$ can communicate with others (including RSUs and other vehicles) by the new random pseudonyms $[PI D_{vi}, k_{vi}, T_{vi}]_{t}$ before the pseudonyms expired when it is in the communication range of the current RSU. Note that $T_{vi}$ is the same in the t pseudonyms; however, $T_{vi}$ will not leak the privacy of the vehicles due to the coarse-grained time. Of course, if the pseudonyms have been used up, the vehicle can obtain new pseudonyms from RSUs again through repeating the pseudonym allocation phase. The message signing phase is described as follows.

To send a message $m_{i}$ , the vehicle selects current timestamp $T_{i}$ , a random number $r_{i} \in Z_{q}^{*}$ , and a pseudonym $PI D_{vi}$ from $[PI D_{vi}, k_{vi}]_{t}$ and then computes $R_{i} = r_{i} \cdot P$ , $h_{mi} = H_{3} (m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, P_{RSU})$ , where $h_{ki} = H_{4} (m_{i}, PI D_{vi}, T_{i}, T_{vi}, R_{i}, P_{vi}, p p_{vi})$ and $T_{i}$ is a time with the precision of a millisecond. Finally, the vehicle signs the message as $δ_{i} = h_{mi} \cdot r_{i} + h_{ki} \cdot k_{vi}$ and broadcasts the message ${m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, δ_{i}}$ to the others.

Message verification phase

Upon receiving message ${m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, δ_{i}}$ , the verifier (an RSU or a vehicle) checks whether the timestamps $T_{vi}$ and $T_{i}$ are fresh or not. If not, the verifier drops this message. Else, it computes $h_{ui} = H_{2} (PI D_{vi}, P_{RSU}, T_{vi})$ and $h_{mi} = H_{3} (m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, P_{RSU})$ and then checks whether the message satisfies the single message verification equation (1)

δ_{i} \cdot P = h_{m i} \cdot R_{i} + h_{k i} \cdot P I D_{v i} + h_{k i} \cdot h_{u i} \cdot P_{R S U}

(1)

If so, the verifier accepts it, else drops it.

Due to $h_{ui} = H_{2} (PI D_{vi}, P_{RSU}, T_{vi})$ , $h_{mi} = H_{3} (m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, P_{RSU})$ , $R_{i} = r_{i} \cdot P$ , $PI D_{vi} = u_{i} \cdot P$ , $P_{RSU} = yP$ , and $k_{vi} = u_{i} + y \cdot h_{ui}$ , the derivation process of equation (1) is described as follows

\begin{array}{l} δ_{i} \cdot P = (h_{m i} \cdot r_{i} + h_{k i} \cdot k_{v i}) \cdot P \\ = h_{m i} \cdot r_{i} \cdot P + h_{k i} \cdot (u_{i} + y \cdot h_{u i}) \cdot P \\ = h_{m i} \cdot R_{i} + h_{k i} \cdot u_{i} \cdot P + h_{k i} \cdot h_{u i} \cdot y \cdot P \\ = h_{m i} \cdot R_{i} + h_{k i} \cdot P I D_{v i} + h_{k i} \cdot h_{u i} \cdot P_{R S U} \end{array}

Therefore, it can prove that the single message verification is correct.

To improve the efficiency of message verification, the proposed scheme provides a function to batch message verification, which enables the verifier to verify multiple messages simultaneously. Assume the verifier has received n messages ${m_{1}, PI D_{v 1}, T_{1}, T_{v 1}, h_{k 1}, R_{1}, δ_{1}}$ , ${m_{2}, PI D_{v 2}, T_{2}, T_{v 2}, h_{k 2}, R_{2}, δ_{2}}$ , …, ${m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, δ_{i}}$ , …, ${m_{n}, PI D_{vn}, T_{n}, T_{vn}, h_{kn}, R_{n}, δ_{n}}$ at the same time. The verifier can verify the n messages as the following steps:

B1: The verifier checks whether the timestamps $T_{i}$ and $T_{vi}$ of the n messages are fresh or not. If the message is not fresh, the verifier drops this message.

B2: To avoid false acceptation in batch verification, the small exponent test technology^8,35 is adopted in our proposed scheme, where a vector including some small integers is used to detect any modifications in a batch of signatures. Assume there are n messages needed to be checked. The verifier selects a vector $μ = {μ_{1}, μ_{2}, \dots, μ_{i}, \dots μ_{n}}$ , where $μ_{i}$ is a random integer in $[1, η]$ , where $η$ is a very small integer that has few computation overhead in scale multiplication operation.²⁰

B3: The verifier computes $h_{mi} = H_{4} (m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, P_{RSU})$ and $h_{ui} = H_{2} (PI D_{vi}, P_{RSU}, T_{vi})$ for each message and then checks whether the n signatures can satisfy equation (2) or not

\begin{array}{l} (\sum_{i = 1}^{n} μ_{i} \cdot δ_{i}) \cdot P = \sum_{i = 1}^{n} (μ_{i} \cdot h_{m} \cdot R_{i}) \\ + \sum_{i = 1}^{n} (μ_{i} \cdot h_{k i} \cdot P I D_{v i}) + (\sum_{i = 1}^{n} μ_{i} \cdot h_{k i} \cdot h_{u i}) \cdot P_{R S U} \end{array}

(2)

If it holds, the verifier accepts these messages. Otherwise, there is at least one invalid message in these messages. The invalid message detection algorithm proposed in Huang et al.²³ is adopted to detect invalid messages. For more details, please refer to Huang et al.²³

Due to $h_{ui} = H_{2} (PI D_{vi}, P_{RSU}, T_{vi})$ , $h_{mi} = H_{3} (m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, P_{RSU})$ , $R_{i} = r_{i} \cdot P$ , $PI D_{vi} = u_{i} \cdot P$ , $P_{RSU} = y \cdot P$ , and $k_{vi} = u_{i} + y \cdot h_{ui}$ , the derivation process of equation (2) is described as follows

\begin{array}{l} (\sum_{i = 1}^{n} μ_{i} \cdot δ_{i}) \cdot P = (\sum_{i = 1}^{n} μ_{i} \cdot (h_{m i} \cdot r_{i} + h_{k i} \cdot k_{v i})) \cdot P \\ = \sum_{i = 1}^{n} (μ_{i} \cdot h_{m i} \cdot r_{i} \cdot P + μ_{i} \cdot h_{k i} \cdot (u_{i} + y \cdot h_{u i}) \cdot P) \\ = \sum_{i = 1}^{n} (μ_{i} \cdot h_{m i} \cdot R_{i} + μ_{i} \cdot h_{k i} \cdot u_{i} \cdot P + μ_{i} \cdot h_{k i} \cdot h_{u i} \cdot y \cdot P) \\ = \sum_{i = 1}^{n} (μ_{i} \cdot h_{m i} \cdot R_{i} + μ_{i} \cdot h_{k i} \cdot P I D_{v i} + μ_{i} \cdot h_{k i} \cdot h_{u i} \cdot P_{R S U}) \\ = \sum_{i = 1}^{n} (μ_{i} \cdot h_{m i} \cdot R_{i}) + \sum_{i = 1}^{n} (μ_{i} \cdot h_{k i} \cdot P I D_{v i}) + (\sum_{i = 1}^{n} μ_{i} \cdot h_{k i} \cdot h_{u i}) \cdot P_{R S U} \end{array}

Therefore, it can prove that the batch message verification is correct.

Identity extraction phase

When the valid message ${m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, δ_{i}}$ is involved a controversial matter, the KGC and RTA can execute the following steps to extract the real identity of message generator:

E1: The RTA searches $PI D_{vi}$ in its database to obtain the corresponding $P_{vi}$ and then obtains ${QI D_{vi}, I D_{v}, P_{vi}}$ . Finally, the RTA sends ${QI D_{vi}, P_{vi}, I D_{vi}}$ to the KGC.

E2: When receiving ${QI D_{vi}, P_{vi}, I D_{vi}}$ , the KGC computes ${pp}_{vi}^{*} = s \cdot H_{1} (I D_{vi})$ and $h_{ki}^{*} = H_{4} (m_{i}, PI D_{vi}, T_{i}, T_{vi}, R_{i}, P_{vi}, {pp}_{vi}^{*})$ and then checks whether $h_{ki}^{*}$ is equal to $h_{ki}$ in the message or not. If it is, the KGC can confirm that the $I D_{vi}$ is the real generator of the message ${m_{i}, PI D_{vi}, T_{i}, h_{ki}, R_{i}, δ_{i}}$ . Otherwise, the message generator is the RSU (e.g. corrupted RSU).

Security analysis

In this section, the security proof of the proposed scheme is analyzed, and then the proposed scheme is demonstrated to meet the security requirements of VANETs. ECC^41,42 is widely used in the design of authentication schemes. The security of ECC is according to a famous complex assumption about ECC, that is, elliptic curve discrete logarithm problem (ECDLP): Given two random points P and Q on $E / E_{p}$ , where $Q = xP$ , $x \in Z_{p}^{*}$ . It is difficult to calculate x from Q.

According to security assumption in section “Background,” RSUs are trustable entities in message signing and verification phase. Therefore, we mainly show that the proposed scheme is able to be unforgeable against an adaptive chosen message during the message signing phase.

Theorem 1

The proposed scheme is existentially unforgeable against an adaptive chosen message under the random oracle model.

Proof

Assume an adversary $A$ could forge a signature ${PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, δ_{i}}$ on message $m_{i}$ . Assume an instance $(P, Q = xP)$ is given a ECDLP for two points P and Q on $E / E_{p}$ . Then we establish a game between the adversary $A$ and a challenger $C$ , which is able to solve the ECDLP with non-negligible probability.

Setup. $C$ runs setup progress and establishes system parameters $paras = {E_{p} (a, b), p, q, G, P, H_{1}, H_{2}, H_{3}, H_{4}, P_{pub}, E_{pk} (.) / D_{sk} (.), SIG (.)}$ and then constructs and maintains four lists, that is, $L_{h 1}$ with form of $〈 α, τ_{1} 〉$ , $L_{h 2}$ with form of $〈 PI D_{vi}, P_{RSU}, T_{vi}, τ_{2} 〉$ , $L_{h 3}$ with form of $〈 m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, P_{RSU}, τ_{3} 〉$ , which contains the queries and answers of the four hash-oracles and is empty initially. Next, $C$ sets $P_{RSU} = Q = xP$ as the public key of the current RSU in the game. Finally, $C$ sends paras to $A$ .

h₁-Oracle. When $A$ makes query $α$ , $C$ checks whether the tuple $〈 α, τ_{1} 〉$ is already in $L_{h 1}$ or not. If it is, $C$ sends $τ_{1} = h_{1} (α)$ to $A$ . Otherwise, $C$ randomly selects $τ_{1} \in Z_{q}^{*}$ and then adds $〈 α, τ_{1} 〉$ to $L_{h 1}$ . Finally, $C$ sends $τ_{1} = h_{1} (α)$ to $A$ .

h₂-Oracle. When $A$ makes query ${PI D_{vi}, P_{RSU}, T_{vi}}$ , $C$ checks whether the tuple $〈 PI D_{vi}, P_{RSU}, T_{vi}, τ_{2} 〉$ is already in $L_{h 2}$ . If so, $C$ sends $τ_{2} = h_{2} (PI D_{vi}, P_{RSU}, T_{vi})$ to $A$ . Otherwise, $C$ randomly selects $τ_{2} \in Z_{q}^{*}$ and adds $〈 PI D_{vi}, P_{RSU}, T_{vi}, τ_{2} 〉$ to $L_{h 2}$ . Finally, $C$ sends $τ_{2} = h_{2} (PI D_{vi}, P_{RSU}, T_{vi})$ to $A$ .

h₃-Oracle. When $A$ makes query ${m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, P_{RSU}}$ , $C$ checks whether the tuple $〈 m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, P_{RSU} 〉$ is already in $L_{h 3}$ . If so, $C$ sends $τ_{3} = H_{3} (m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, P_{RSU})$ to $A$ . Otherwise, $C$ randomly selects $τ_{3} \in Z_{q}^{*}$ and adds $〈 m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, P_{RSU}, τ_{3} 〉$ to $L_{h 3}$ . Finally, $C$ sends $τ_{3} = H_{3} (m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, P_{RSU})$ to $A$ .

Sign-Oracle. When $A$ makes sign-query on message ${m_{i}, T_{vi}, T_{i}}$ , $C$ chooses $δ_{i}, h_{mi}, h_{ki}, h_{ui} \in Z_{p}^{*}$ , $PI D_{vi} \in G$ at random, and computes $R_{i} = (δ_{i} \cdot P - h_{ki} \cdot h_{ui} \cdot P_{RSU} - h_{ki} \cdot PI D_{vi}) \cdot h_{mi}^{- 1}$ . Then $C$ adds the $〈 PI D_{vi}, P_{RSU}, T_{vi}, τ_{2} 〉$ to $L_{h 2}$ and $〈 m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, P_{RSU}, τ_{3} 〉$ to $L_{h 3}$ . Finally, $C$ sends ${m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, δ_{i}}$ to $A$ . All responses to the Sign-Oracle are valid because the message ${m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, δ_{i}}$ answered from $C$ can satisfy the single message verification equation.

Output. Finally, $A$ outputs a message ${m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, δ_{i}}$ with non-negligible probability. $C$ verifies the message by the following equation

δ_{i} \cdot P = h_{m i} \cdot R_{i} + h_{k i} \cdot P I D_{v i} + h_{k i} \cdot h_{u i} \cdot P_{R S U}

(3)

If it does not hold, $C$ terminates this progress.

According to the forgery lemma,⁴³ the adversary $A$ is able to output another valid message ${m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, δ_{i}^{*}}$ if $A$ redoes the process with another choice of h₂-Oracle (let it be $h_{ui}^{*}$ ). In this case, the message satisfies

δ_{i}^{*} \cdot P = h_{mi} \cdot R_{i} + h_{ki} \cdot PI D_{vi} + h_{ki} \cdot h_{ui}^{*} \cdot P_{RSU}

(4)

According to equations (3) and (4), it can deduce as follows

\begin{matrix} (δ_{i} - δ_{i}^{*}) \cdot P = δ_{i} \cdot P - δ_{i}^{*} \cdot P \\ = h_{ki} (h_{ui} - h_{ui}^{*}) \cdot P_{RSU} \\ = h_{ki} \cdot (h_{ui} - h_{ui}^{*}) \cdot x \cdot P \end{matrix}

(5)

From equation (5), we could obtain

(δ_{i} - δ_{i}^{*}) = h_{ki} \cdot (h_{ui} - h_{ui}^{*}) \cdot x mod q

(6)

Now, $C$ outputs $(δ_{i} - δ_{i}^{*}) \cdot h_{ki}^{- 1} \cdot (h_{ui} - h_{ui}^{*})^{- 1}$ as the answer of the given instance of the ECDLP. The probability of solving the problem is analyzed as the following events:

E1: $C$ terminates the game in any Send-query.

E2: $C$ outputs a valid Req message.

E3: $PI D_{i}$ and $PI D_{I}$ are the same.

Let $n_{s}$ and $n_{h 2}$ be the queried times of Send and h₂-oracle executed in the game, respectively. According to the definition of the game, we can get $\Pr [E 1] \geq (1 - 1 / (n_{s} - 1))^{n_{s}}$ , $\Pr [E 2 | E 1] \geq ε$ , and $\Pr [E 3 | E 2 \land E 1] \geq 1 / n_{h 2}$ . Therefore, the probability that $C$ can solve the ECDLP is

\begin{matrix} \Pr [E 1 \land E 2 \land E 3] = \Pr [E 3 | E 2 \land E 1] \cdot \Pr [E 2 | E 1] \cdot \Pr [E 1] \\ = {(1 - \frac{1}{n_{s} - 1})}^{n_{s}} \cdot (n_{h 2})^{- 1} \cdot ε \end{matrix}

(7)

Obviously, the probability cannot be non-negligible. It contradicts with the hardness of the ECDLP in the game. Therefore, it can prove that the proposed scheme is secure against forgery under adaptive chosen message attack in random oracle model.

Next, we show that the proposed scheme meets the security requirements of VANETs mentioned in section “Security requirements.”

Message authentication

The message authentication is a basic security requirement of VANETs. According to Theorem 1, an attacker cannot forge a valid message in the proposed scheme if the ECDLP is hard. A message can be authenticated by checking whether the message meets verification $δ_{i} \cdot P = h_{mi} \cdot R_{i} + h_{ki} \cdot PI D_{vi} + h_{ki} \cdot h_{ui} \cdot P_{RSU}$ . Therefore, the proposed scheme can achieve message authentication for VANETs.

Conditional privacy-preserving

In the proposed scheme, the real identity of the vehicle is involved in $p p_{vi}$ and $P_{vi}$ , However, $p p_{vi}$ and $P_{vi}$ are hidden in $k_{ki}$ during message signing progress. An adversary cannot reveal $p p_{vi}$ or $P_{vi}$ from $h_{ki}$ in random oracle model. On the contrary, the RTA and the KGC can reveal the real identity of message generator if it is necessary by the way proposed in section “Identity extraction phase.” Therefore, the proposed scheme can meet the conditional privacy-preserving for VANETs.

Resistance to attacks

A secure authentication scheme should be able to resist all kinds of security attacks.⁴⁴ Next, we show that the proposed scheme is resistant to modification attack, impersonation attack, relay attack, and so on.

Modification attack

If an attacker makes some modifications on a message ${m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, δ_{i}}$ , he or she must forge a new signature $δ_{i}^{*}$ to pass the authentication of the verifiers. However, according to Theorem 1, the modification of $δ_{i}^{*}$ on the message could not satisfy verification equation (1) with a non-negligible probability in the random oracle model.

Impersonation attack

To impersonate a vehicle, the attacker must forge a message ${m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, δ_{i}}$ to meet the verification equation (1). Based on Theorem 1, the attacker forges such a message. The verifiers could detect this kind of attack easily by checking whether the messages received are able to make the verification equation hold. Therefore, the proposed scheme is resistant to the impersonation attack.

Man-in-the-middle attack

The proposed scheme provides authentication between the verifier and the sender for VANETs. If an attacker launches a man-in-middle attack, he or she must forge messages to communicate with the verifier and the sender, respectively. However, according to Theorem 1, it is impossible for the attacker to launch this kind of attack. Therefore, the proposed scheme is secure against the man-in-the-middle attack.

Replay attack

In the proposed scheme, each message ${m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, δ_{i}}$ includes two timestamps $T_{i}$ and $T_{vi}$ . The verifiers are able to find the replay attacks by checking the freshness of $T_{i}$ and $T_{vi}$ . Therefore, the proposed scheme is secure against the replay attack. Based on the previous security analysis, we can conclude that the proposed scheme could meet all security requirements of VANETs.

Performance analysis and comparison

In this section, we will evaluate the proposed scheme by comparing it with Horng et al.’s³⁵ scheme and Malhi and Batra’s³⁷ scheme in terms of computational and communication cost.

Computation cost analysis and comparison

The crypto-operations of Horng et al.’s³⁵ scheme and Malhi and Batra’s³⁷ scheme are built on bilinear pairings, while the crypto-operations of our proposed scheme are built on the non-super singular elliptic curve. To guarantee the justice of computation comparison, the crypto-operations of the three schemes should achieve the same security level in the same environments. The method of computation evaluation for VANETs proposed in He et al.⁷ is adopted in this article. In He et al.,⁷ the bilinear pairing on the security level of 80 bits is constructed as follows: $\bar{e} : G_{1} \times G_{1} \to G_{T}$ , where $G_{1}$ is an additive group that is generated by a point $\bar{P}$ on a super singular elliptic curve $\bar{E} : y^{2} = x^{3} + x mod \bar{p}$ with embedding degree 2 and order $\bar{q}$ . $\bar{p}$ is a 512-bit primer number and $\bar{q} = 2^{159} + 2^{17} + 1$ is a 160-bit Solinas prime number, and equation $\bar{p} + 1 = 12 \bar{q} \bar{r}$ holds; the ECC on the security level of 80 bits is constructed as follows: an additive group G with order q that is generated by a point P on a non-singular elliptic curve $E : y^{2} = x^{3} + ax + b mod p$ , where p and q are two 160-bit prime number and $a, b \in Z_{q}^{*}$ . The cryptographic operations and their corresponding abbreviations and execution times in the four authentication schemes are listed in Table 2.⁷ The column named ‘Abbr.’ denotes abbreviations of cryptographic operations. $T_{bp}$ denotes a bilinear pairing operation. $T_{b . m}$ , $T_{b . sm}$ , and $T_{b . a}$ denote a normal scale multiplication operation, a small-scale multiplication operation, and a point addition operation related to bilinear pairing, respectively. $T_{e . m}$ , $T_{e . sm}$ , and $T_{e . a}$ denote a normal scale multiplication operation, a small-scale multiplication operation, and a point addition operation related to ECC, respectively. The exclusive-or operations (XOR) and concatenate operations are negligible in the following analysis of computation cost because their execution time is much less than that of a hash to number function operation.

Table 2.

The cryptographic operations and corresponding execution time.

Cryptographic operation		Abbr.	Time (ms)
Operations related to bilinear pairing	$\bar{e} (P, Q)$ , where $P, Q \in G_{1}$	$T_{bp}$	4.2110
	xP, where $P \in G_{1}, x \in Z_{\hat{q}}^{*}$	$T_{b . m}$	1.7090
	$λ_{i} P$ , where $λ_{i} \in [1, τ]$ , $P \in G_{1}$	$T_{b . sm}$	0.0535
	$P + Q$ , where $P, Q \in G_{1}$	$T_{b . a}$	0.0071
Operations related to ECC	xP, where $P \in G, x \in Z_{q}^{*}$	$T_{e . m}$	0.4420
	$λ_{i} P$ , where $λ_{i} \in [1, τ]$ , $P \in G$	$T_{e . sm}$	0.0138
	$P + Q$ , where $P, Q \in G$	$T_{e . a}$	0.0018
MapToPoint hash function		$T_{H}$	4.406
One-way hash function		$T_{h}$	0.0001

For simplicity, let MSP, SMV, and BMV denote the message signing phase, the single message verification phase, and the batch message verification phase, respectively. In Horng et al.’s³⁵ scheme, the scalar multiplication and point addition operation are built based on a super singular elliptic curve. The MSP of Horng et al.’s³⁵ scheme consists of five scalar multiplication operations, one point addition operation, two operations of MapToPoint hash function, and one operation of one-way hash function. So the total computation cost of MSP is $5 T_{b . m} + 1 T_{b . a} + 2 T_{H} + 1 T_{h}$ . The SMV of Horng et al.’s³⁵ scheme consists of two bilinear pairing operations, two scalar multiplication operations, one point addition operation, one operation of MapToPoint hash function, and one operation of one-way hash function. So the total computation cost of SMV is $2 T_{bp} + 2 T_{b . m} + 1 T_{b . a} + 1 T_{H} + 1 T_{h}$ . The BMV (assuming batch verification for n messages) of Horng et al.’s³⁵ scheme consists of two bilinear pairing operations, $2 n$ scalar multiplication operations, n operations of MapToPoint hash function, and n operations of one-way hash function. So the total computation cost of BMV is $2 T_{bp} + 2 n T_{b . m} + n T_{H} + n T_{h}$ . We can draw the computation cost of Malhi and Batra³⁷ scheme in the same. For simplicity, we do not present the detailed analysis for the two schemes. According to the execution time in Table 2, we get the results of computation cost of the three schemes in MSP, SMV, and BMV, respectively, as shown in Table 3.

Table 3.

The computation cost of four authentication schemes for VANETs.

	Horng et al.’s³⁵ scheme	Malhi and Batra’s³⁷ scheme	Our proposed scheme
MSP	$\begin{matrix} 5 T_{b . m} + 1 T_{b . a} \\ + 2 T_{H} + 1 T_{h} \\ \approx 11.1539 ms \end{matrix}$	$\begin{matrix} 4 T_{b . m} + 2 T_{b . a} \\ + 2 T_{h} \\ \approx 7.4702 ms \end{matrix}$	$\begin{matrix} 2 T_{e . m} + 2 T_{h} \\ \approx 0.1942 ms \end{matrix}$
SMV	$\begin{matrix} 2 T_{bp} + 2 T_{b . m} \\ + 1 T_{b . a} + 1 T_{H} + 1 T_{h} \\ \approx 13.7051 ms \end{matrix}$	$\begin{matrix} 3 T_{bp} + 3 T_{b . m} \\ + 1 T_{bp . a} + 2 T_{h} \\ \approx 19.1828 ms \end{matrix}$	$\begin{matrix} 3 T_{e . m} + 2 T_{e . a} \\ + 2 T_{h} \\ \approx 0.5864 ms \end{matrix}$
BMV	$\begin{matrix} 2 T_{bp} + 2 n T_{b . m} \\ + n T_{H} + n T_{h} \\ \approx 4.6411 n + 13.7051 ms \end{matrix}$	$\begin{matrix} 3 T_{bp} + 3 n T_{b . m} \\ + n T_{b . a} + 3 n T_{h} \\ \approx 5.599 n + 13.584 ms \end{matrix}$	$\begin{matrix} (2 n + 2) T_{e . m} \\ + 2 n T_{e . a} + 2 n T_{h} \\ \approx 0.392 n + 0.388 ms \end{matrix}$

In our proposed scheme, the scalar multiplication and point addition operation are built on the non-singular elliptic curve. The MSP of the proposed scheme consists of one scalar multiplication operations and two one-way hash function operations. Therefore, the total computation cost of MSP is $1 T_{e . m} + 2 T_{h}$ . The SMV of the proposed scheme consists of three scalar multiplication operations, two point addition operations, and two one-way hash function operations. Therefore, the total computation cost of SMV is $3 T_{e . m} + 2 T_{e . a} + 2 T_{h}$ . The BMV for n messages of the proposed scheme consists of $2 n + 2$ scalar multiplication operations, $2 n$ point addition operations, and $2 n$ one-way hash function operations. So the total computation cost of BMV is $(2 n + 2) T_{e . m} + 2 n T_{e . a} + 2 n T_{h}$ . The results of computation cost of our proposed scheme in MSP, SMV, and BMV are shown in Table 3.

As shown in Table 3, the computation cost time of MSP of our proposed scheme is 0.1942 ms, which decreases by 98.2% and 97.4%, respectively, when compared with the computation cost time of MSP in Horng et al.’s³⁵ scheme and Malhi and Batra’s³⁷ scheme. Meanwhile, the computation cost time of SMV of our proposed scheme is 0.5864 ms, which decreases by 95.7% and 96.9%, respectively, when compared with the computation cost time of SMV of Horng et al.’s³⁵ scheme and Malhi and Batra’s³⁷ scheme. As for BMV, the computation costs of batch verification for 50 messages of Horng et al.’s³⁵ scheme, Malhi and Batra’s scheme,³⁷ and our proposed scheme are 399.62, 269.34, and 45.27 ms, respectively, which means that our proposed schemes has 88.67% and 83.19% improvements over Horng et al.’s³⁵ scheme and Malhi and Batra’s³⁷ scheme, respectively. The improvement on computation cost of our proposed scheme is shown in Table 4.

Table 4.

The improvement on computation cost of our proposed scheme over other schemes.

	MSP	SMV	BMV (50 messages)
Horng et al.’s³⁵ scheme	98.2%	95.7%	88.67%
Malhi and Batra’s³⁷ scheme	97.4%	96.9%	83.19%

Figure 3 illustrates the computation costs of BMV phase for the different number of messages. As shown in Figure 3, our proposed scheme is more efficient than Malhi et al’s scheme and Horng et al’s scheme in BMV, regardless of the number of messages.

Figure 3.

The computation costs of BMV for the number of messages.

Communication cost analysis and comparison

In this section, the proposed scheme is compared with Horng et al.’s³⁵ scheme and Malhi and Batra’s³⁷ scheme, in terms of communication cost. Like the analysis in the previous section, the size of $\bar{p}$ is 64 bytes, so the size of an element in $G_{1}$ is 128 bytes; likewise, the size of p is 20 bytes, so the size of an element in G is 40 bytes. Assume the sizes of a timestamp and the output of a one-way hash function to be 4 and 20 bytes, respectively. The original traffic messages are not considered in the comparison of communication cost because they are the same as each authentication scheme. The comparison of communication costs is listed in Table 3.

As shown in Table 5, the size of single message excluding $m_{i}$ of Horng et al.’s scheme is $128 \times 3 = 384 bits$ , which includes three elements in $G_{1}$ ( $I D_{i, 1}, I D_{i 2}, δ_{i} \in G_{1}$ , $128 \times 3 bits$ ). The size of single message excluding $m_{i}$ of Malhi et al.’s scheme is $128 \times 4 + 4 = 516 bits$ , which includes four elements in $G_{1}$ ( $PS 1, P_{vi}, U, V \in G_{1}$ , $128 \times 4 bits$ ) and one timestamp (T, 4 bits). The size of single message excluding $m_{i}$ of our proposed scheme is $40 \times 3 + 8 + 20 = 184 bytes$ , which includes three elements in G ( $PI D_{vi}, h_{ki}, R_{i} \in G$ , $40 \times 3 = 120 bits$ ), two timestamps ( $T_{i}, T_{vi}$ , 8 bits), and one hash function’s output ( $δ_{i} \in Z_{q}$ , 20 bits). Therefore, our proposed scheme incurs much lower communication cost than other similar schemes for VANETs.

Table 5.

The comparison of communication cost.

Scheme	The component of single message	Size (bytes)
Horng et al.’s³⁵ scheme	${m_{i}, I D_{i, 1}, I D_{i 2}, δ_{i}}$	384
Malhi and Batra’s³⁷ scheme	${m_{i}, PS 1, P_{vi}, T, U_{i}, V_{i}}$	516
Our proposed scheme	${m_{i}, PI D_{vi}, T_{i}, T_{vi}, h_{ki}, R_{i}, δ_{i}}$	148

Tip: the size excludes $m_{i}$ .

Conclusion

In this article, a novel location-based CPPA scheme for VANETs is proposed. The proposed scheme utilizes the location information to allocate vehicles’ partial secret keys, and the vehicles could sign messages with unrelated pseudonyms to hide its real identity. Unlike the existing authentication schemes for VANETs, no TPDs and bilinear pairing operations are involved in the proposed scheme. Security analysis shows that the proposed scheme meets the security requirements of VANETs. Compared with the recently proposed similar authentication schemes, the proposed scheme greatly reduces the computation and communication costs to more than 90% and 50%, respectively, with the guarantee of security and privacy preservation. Therefore, the proposed scheme solves the challenge well and is more practical for VANETs. To improve the efficiency of message authentication, next, we will research on cooperating authentication scheme among vehicles for VANETs.

Footnotes

Academic Editor: Muhammad Khurram Khan

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported by Natural Science Foundation of China (61472287, 61572370), Science and Technology Support Program of Hubei Province (2015CFA068) and Science and Technology Plan Projects of Wuhan City (2016060101010047).

References

Kakkasageri

Manvi

SS.

Information management in vehicular ad hoc networks: a review. J Netw Comput Appl 2014; 39: 334–350.

Bitam

Mellouk

Zeadally

VANET-cloud: a generic cloud computing model for vehicular ad hoc networks. IEEE Wirel Commun 2015; 22(1): 96–102.

Grover

Alvin

Seungbae

Efficient authentication approach for highly dynamic vehicular ad hoc networks. Int J Ad Hoc Ubiq Co 2015; 19(3–4): 193–207.

Zhang

Cheng

. Vehicles meet infrastructure: toward capacity–cost tradeoffs for vehicular access networks. IEEE T Intell Transp 2013; 14(3): 1266–1277.

Engoulou

Bellaïche

Pierre

. VANET security surveys. Comput Commun 2014; 44: 1–13.

Verma

Hasbullah

Kumar

Prevention of DoS attacks in VANET. Wirel Person Commun 2013; 73(1): 95–126.

Zeadally

. An efficient identity-based conditional privacy-preserving authentication scheme for vehicular ad-hoc networks. IEEE T Inf Foren Sec 2015; 10(12): 1681–2691.

Guizani

ACPN: a novel authentication framework with conditional privacy-preservation and non-repudiation for VANETs. IEEE T Parall Distr 2015; 26(4): 938–948.

Lin

Sun

. GSIS: a secure and privacy preserving protocol for vehicular communications. IEEE T Veh Technol 2007; 56(6): 3442–3456.

10.

Lin

Zhu

. ECPP: efficient conditional privacy preservation protocol for secure vehicular communications. In: Proceedings of the 27th IEEE conference on computer communications (INFOCOM 2008), Phoenix, AZ, 13–18 April 2008. New York: IEEE.

11.

Zhang

Solanas

. A scalable robust authentication protocol for secure vehicular communications. IEEE T Veh Technol 2010; 59(4): 1606–1617.

12.

Zhu

Jiang

Wang

. Efficient privacy-preserving authentication for vehicular ad hoc networks. IEEE T Veh Technol 2014; 63(2): 907–919.

13.

Liu

Yuen

. Improvements on an authentication scheme for vehicular sensor networks. Expert Syst Appl 2014; 41(5): 2559–2564.

14.

Raya

Hubaux

. The security of vehicular ad hoc networks. In: Proceedings of the 3rd ACM workshop on Security of ad hoc and sensor networks, Alexandria, VA, 7 November 2005. New York: ACM.

15.

Freudiger

Raya

Féllegyházi

. Mix-zones for location privacy in vehicular networks. In: Proceedings of the ACM workshop on wireless networking for intelligent transportation systems (WiN-ITS), Vancouver, BC, Canada, 14 August 2007.

16.

Zhang

Lin

. RAISE: an efficient RSU-aided message authentication scheme in vehicular communication networks. In: Proceedings of the IEEE international conference on communications (ICC’08), Beijing, China, 19–23 May 2008. New York: IEEE.

17.

Zhang

. Privacy-preserving vehicular communication authentication with hierarchical aggregation and fast response. IEEE T Comput 2016; 65: 2562–2574.

18.

Zhang

Lin

. An efficient identity-based batch verification scheme for vehicular sensor networks. In: Proceedings of the 27th IEEE conference on computer communications (INFOCOM 2008), Phoenix, AZ, 13–18 April 2008. New York: IEEE.

19.

Shim

An efficient conditional privacy-preserving authentication scheme for vehicular sensor networks. IEEE T Veh Technol 2012; 61(4): 1874–1883.

20.

Lee

Lai

YM.

Toward a secure batch verification with group testing for VANET. Wirel Netw 2013; 19(6): 1441–1449.

21.

Zhang

Liu

On the security of a secure batch verification with group testing for VANET. Int J Netw Secur 2014; 16(5): 355–362.

22.

Bayat

Barmshoory

Rahimi

. A secure authentication scheme for VANETs with batch verification. Wirel Netw 2015; 21(5): 1733–1743.

23.

Huang

Yeh

Chien

HY.

ABAKA: an anonymous batch authenticated and key agreement scheme for value-added services in vehicular ad hoc networks. IEEE T Veh Technol 2011; 60(1): 248–262.

24.

Chaum

Van Heyst

Group signatures. In: Davies

(ed.) Advances in cryptology—EUROCRYPT’91. Lecture notes in computer science. Berlin, Heidelberg: Springer, 1991, pp.257–265.

25.

Boneh

Shacham

Group signatures with verifier-local revocation. In: Proceedings of the 11th ACM conference on computer and communications security (CCS’04), Washington, DC, 25–29 October 2004, pp.168–177. New York: ACM.

26.

Hao

Cheng

Zhou

. A distributed key management framework with cooperative message authentication in VANETs. IEEE J Sel Area Comm 2011; 29(3): 616–629.

27.

Shamir

Identity-based cryptosystems and signature schemes. In: Blakley

Chaum

(eds) Advances in cryptology—CRYPTO 1984. Lecture notes in computer science. Berlin, Heidelberg: Springer, 1984, pp.47–53.

28.

Xie

Zhang

. Efficient and secure authentication scheme with conditional privacy-preserving for VANETs. Chin J Electron 2016; 25(5): 950–956.

29.

Tsai

An efficient conditional privacy-preserving authentication scheme for vehicular sensor networks without pairings. IEEE T Intell Transp 2016; 17(5): 1319–1328.

30.

Xie

Shen

. EIAS-CP: new efficient identity-based authentication scheme with conditional privacy-preserving for VANETs. Telecommun Syst. Epub ahead of print 13 September 2016. DOI: 10.1007/s11235-016-0222-y.

31.

Samara

Al-Salihy

Sures

. Security issues and challenges of Vehicular Ad Hoc Networks (VANET). In: Proceedings of the 4th IEEE international conference on new trends in information science and service science (NISS), Gyeongju, South Korea, 11–13 May 2010, pp.393–398. New York: IEEE.

32.

Zhang

Qin

. APPA: aggregate privacy-preserving authentication in vehicular ad hoc networks. In: Proceedings of the 14th Information security conference (ISC 2011), Xi’an, China, 26–29 October 2011, pp.293–308. New York: ACM.

33.

IBM 4764 PCI-X Cryptographic Coprocessor, https://www.ibm.com/support/knowledgecenter/POWER6/iphcd/fc4764.htm

34.

Chim

Yiu

Hui

LCK

. SPECS: secure and privacy enhancing communications schemes for VANETs. Ad Hoc Netw 2011; 9(2): 189–203.

35.

Horng

Tzeng

Pan

. b-SPECS+: batch verification for secure pseudonymous authentication in VANET. IEEE T Inf Foren Sec 2013; 8(11): 1860–1875.

36.

Xue

Ding

LPA: a new location-based privacy-preserving authentication protocol in VANET. Secur Commun Netw 2012; 5(1): 69–78.

37.

Malhi

Batra

Privacy-preserving authentication framework using bloom filter for secure vehicular communications. Int J Inf Secur 2015; 15: 433–453.

38.

Freeman

Scott

Teske

A taxonomy of pairing-friendly elliptic curves. J Cryptol 2010; 23(2): 224–280.

39.

Kumar

Shen

. One-to-many authentication for access control in mobile pay-TV systems. Sci China: Inform Sci 2016; 59(5): 1–14.

40.

Wang

Robust biometrics-based authentication scheme for multi-server environment. IEEE Syst J 2015; 9(3): 816–823.

41.

Miller

. Use of elliptic curves in cryptography. In: Williams

(ed.) Advances in cryptology—CRYPTO ’85 proceedings (CRYPTO 1985). Lecture notes in computer science. Berlin, Heidelberg: Springer, 1985, pp.417–426.

42.

Koblitz

Elliptic curve cryptosystem. J Math Comput 1987; 48: 203–209.

43.

Pointcheval

Stern

. Security proofs for signature schemes. In: Maurer

(ed.) EUROCRYPT 1996: advances in cryptology—EUROCRYPT’96. Berlin, Heidelberg: Springer, 1996, pp.387–398.

44.

Zeadally

An analysis of RFID authentication schemes for internet of things in healthcare environment using elliptic curve cryptography. IEEE Internet Thing J 2015; 2(1): 72–83.