1 Introduction

Ad-Hoc Network is a representative of today’s advanced wireless application. It has some advantages, such as having fewer infrastructures, arranging a Local Area Network (LAN) quickly, and allowing its members to join and leave easily. Because of these reasons, Ad-Hoc Network has become the first of choice network model for a real-time LAN. This network model is especially suitable for an environment that changes frequently or that does not have enough infrastructure, e.g. in a disaster area or a transportation system [1–3].

Vehicular Ad-Hoc Network (VANET) is an application of Ad-Hoc Network for vehicle communication. Each vehicle uses a device, called on-board units (OBUs), to communicate with one another. The same device can also be used to communicate with the roadside unit (RSU) or other infrastructures [4–6]. To support this, there are two types of VANET: Vehicle-to-Vehicle (V2V) communication and Vehicle to RSU (V2R) communication [4, 6–12]. With the help of V2V, people can obtain more information and use the information to achieve road safety, such as maintaining a distance from other vehicles. Furthermore, a group can establish simple communication networks and allow members to communicate with one another. People can also communicate with RSU by V2R to download files from the Internet or inquire neighborhood location information, such as the closest gas station and restaurant. In addition, users can query RSU about the local situation to avoid traffic jams. Because RSU is an infrastructure, it can be an Internet node. Hence, people can use Internet services to upload or download files through RSU. On the other hand, traffic management could be done easily by combining the traffic system and the VANET system. Because RSU can collect and monitor traffic flow information, the traffic system can predict the traffic flow and control traffic signals to regulate the flow in real time. If necessary, traffic system can also cooperate with the public affair vehicles, such as ambulances or fire engines, to improve the efficiency of performing any urgent task.

The security issues in VANET are particularly important, because VANET provides people with many applications and traffic experience for their daily life. The applications of VANET are in general grouped into two categories: safety and non-safety applications [11, 13–15]. The non-safety applications are usually related to local information and traffic information. One of VANET’s security challenges is avoiding wrong messages, such as falsified messages, replayed messages, or malicious messages. The wrong messages maybe cause some poor situations such as the following:

  1. 1.

    Wrong traffic flow messages: The wrong traffic flow message may result in the traffic management system making wrong decisions. The wrong decision will cause the traffic lights of the heavy side to stay red and the other side to stay green.

  2. 2.

    Wrong traffic stat messages: The wrong traffic stat message may mislead driver into a traffic jam, and the traffic will be more heavier.

  3. 3.

    Wrong vehicles messages: The wrong vehicles message may make the driver misread the safe distance, and crash into other vehicles.

  4. 4.

    Falsified messages: If an adversary falsifies a public affair vehicle signal, such as an ambulance’s signal, he/she may compel the traffic light to cooperate with him/her and harm the driving right of other drivers.

Because VANET improves the traffic experience substantially, any secure leak of VANET may cause inestimable harms to the traffic system. To ensure both the integrity of the messages and non-repudiation is indispensable. A simple solution is to sign each message with a digital signature before the message is sent. In 1976, Diffie and Hellman proposed an idea about public-key cryptography [16]. Two years later, Rivest et al. [17] proposed a novel scheme to accomplish Diffie–Hellman’s idea, called RSA algorithm. In 2007, Raya and Hubaux [9] proposed appropriate security architecture for VANET. There is a PKI (Public Key Infrastructure) certificate issues in their scheme. The RSU and the OBU can mutually authenticate by means of the other’s public key and establish a session key for communication. However, most of the traditional signature schemes verify the received signatures one by one. When the traffic is heavy, the verifier will receive a lot of signatures. Verifying a large number of signatures sequentially will take a long time, and the information with the signature will be delayed. Because the traffic situations are always changing, real time response is a very important issue for the traffic information [7, 8, 18]. If the information is obsolete, it cannot explain the real traffic situation and help people or traffic management system make decisions, and the information will lose its value [4, 6, 11, 12].

To solve the verification bottleneck problem, a lot of related schemes have been proposed. In 1990, Fiat proposed the first batch cryptography scheme based on RSA [19]. In 2007, Lin et al. [18] proposed a group signature scheme based on bilinear pairing to improve the authentication efficiency. Because the verifier can verify multiple signatures simultaneously in Lin et al.’s scheme, the cost of computation time will not grow linearly with the amount of the signature. Unfortunately, Lin et al.’s scheme uses a lot of exponent operations, and it has complex computing process. In 2011, Zhang et al. [11] and Huang et al. [20] proposed a new scheme respectively. Both of their schemes are based on bilinear pairing and use addition operations to batch verify multiple signatures simultaneously. As an addition operation is simpler than any exponent operations, both of the two schemes are more efficient. Hence, batch verifying is more efficient than single verifying when the verifier has to verify a large number of signatures.

However, Zhang et al.’s scheme has some weaknesses. First, Zhang et al.’s scheme is vulnerable to the replaying-attack. Because of this weakness, an adversary can simulate a fake situation, such as a traffic jam, by collecting the vehicle messages and signatures in the corresponding situation and replaying them. Second, Zhang et al.’s scheme doesn’t achieve the signature non-repudiation. A malicious driver can broadcast wrong information to mislead other drivers and repudiate the behavior when the traffic manager traces him/her by his/her signature. In Huang et al.’s scheme, which is known as ABAKA, the scheme also doesn’t achieve the signature non-repudiation. Wang and Zhang [21] pointed out this weakness in 2012. Hence, ABAKA is not suitable for VANET. The details of ABAKA can refer to [20]. For this reason, we want to propose an improved scheme to enhance the security and keep the efficiency of Zhang et al.’s scheme. The improved scheme can make the VANET information verification be more suitable.

In this paper, we will describe the weaknesses of Zhang et al.’s scheme, and propose an improved scheme. The paper is organized as follows. In Sect. 2, we present the background and preliminaries, which includes the network model and equipment, security requirements, and the bilinear maps. After that, we describe the Zhang et al.’s scheme in Sect. 3 and provide our analysis in Sect. 4. In Sect. 5, we will propose an improved scheme and present an analysis of the proposed scheme in Sect. 6. Finally, we conclude the paper in Sect. 7.

2 Background and preliminaries

2.1 Network model and equipment

A two-layer vehicular network model was introduced in some recent articles [11, 20, 22]. The top layer consists of a trust authority (TA) and application servers. We assume that TA can be completely trusted, and it is responsible for pre-assigning secure information for each vehicle. Most of the time, TA is off-line with other vehicles, and responsible for tracing the real identity of vehicles in case that disputes happens. The application servers for non-safety applications, such as traffic management center, communicate with RSUs and provide services or information. In the lower layer, vehicles and RSUs can communicate with one another based on DSRC protocol [23]. Each vehicle has its own public and private key-pairs for signing each message before the message is sent. Messages and signatures will be sent to the sender’s neighboring RSU, and the RSUs will verify the digital signatures after receiving those information. Each vehicle has to be equipped with a tamper-proof device, which is a secure storage for secrets. We assume that the tamper-proof device is always credible and its information is never been disclosed. The device will pre-load some secure values, such as real identity of vehicle and secret key of system. The computing process of vehicle is also included in this device and the value is never disclosed.

2.2 Security requirements

Communication security is crucial to protect the privacy of the users. In VANET communication, security issues are also very important. In this field, we can generalize three security requirements as follows [12, 22].

  1. 1.

    Message authentication: Ensuring that a message was sent from a legitimate user and the integrity of message wasn’t broken is a primary issue.

  2. 2.

    User privacy preserving: In VANET, communications are always transmitted via a wireless network. Compared to a wire network, wireless is easier intercepted, overheard, and traced. The system has to protect the privacy of a legitimate user, including the user’s real identity or other individual information.

  3. 3.

    Audit-ability: To avoid the inside user using the user privacy preserving to broadcast malicious message which maybe mislead other legitimate user, systems should have a mechanism for retrieving the real identity of a malicious user.

2.3 Bilinear maps

Our proposed scheme in this paper is based on bilinear pairing, which is briefly introduced in this section [11, 18, 24, 25].

  • Let G be a cyclic additive group generated by P, and G T be a cyclic multiplicative group. G and G T have the same prime order q, that means \( \left| G \right| = \left| {G_{T} } \right| \).

  • Let \( \hat{e}:G \times G \to G_{T} \) be a bilinear map.

The bilinear map satisfies the following properties:

  1. 1.

    Bilinear: For all \( P, \, Q, \, R \in G,\,\hat{e}(Q, \, P + R) = \hat{e}(P \, + \, R, \, Q) = \hat{e}(Q, \, P) \cdot \, \hat{e}(Q, \, R) \). Let \( a,b \in Z^{*} q,\hat{e}(aQ, \, bP) = \hat{e}(bQ, \, aP) = \hat{e}(Q, \, P)^{ab} \).

  2. 2.

    Non-degenerate: There exist P, Q∈G such that \( \hat{e}(P, \, Q) \ne 1_{GT} \). where \( 1_{{{\text{G}}_{\text{T}} }} \) is the identity element of G T .

  3. 3.

    Computable: There is an efficient algorithm to compute \( \hat{e}(Q, \, P) \) for any \( P, \, Q \in G. \)

The bilinear map can be constructed by the modification on elliptic curves [18, 24, 25]. It also possesses the characteristic of elliptic curves as follows. Let P, Q ∈ G and a ∈ Z * q, Q = aP, and {P, Q} are known. Finding the integer a from Q and P is the elliptic curve discrete logarithm problem (ECDLP).

3 Review of Zhang et al.’s scheme

There are three subsections in Zhang et al.’s scheme [11], including (a) key generation and pre-distribution, (b) pseudo identity generation and message signing, and (c) message verification. The notation is shown in Table 1. We briefly describe them as follows.

Table 1 Notation of this paper
Full size table

3.1 Key generation and pre-distribution

In Zhang et al.’s scheme, TA is responsible for setting up the system parameters for each vehicle and RSU as follows.

  1. 1.

    Let G be a cyclic additive group generated by P, and G T be a cyclic multiplicative group and G and G T have the same prime order q. After that, let \( \hat{e}:G \times G \to G_{T} \) be a bilinear map.

  2. 2.

    Choose two random numbers \( \{ s_{1} ,s_{2} \} \in Z^{*} q \) as its two master keys, and compute \( P_{pub1} = s_{1} P,P_{pub2} = s_{2} P \) as its public keys. These two master keys {s 1 , s 2 } of the TA are pre-loaded in each vehicle’s tamper-proof device.

  3. 3.

    The public parameters {G, G T , q, P, P pub1 , P pub2 } are pre-loaded in each RSU and vehicle.

  4. 4.

    Each vehicle is assigned its real identity, denoted as RID∈G, and password, denoted as PWD. Both RID and PWD are stored in the tamper-proof device.

3.2 Pseudo identity generation and message signing

To achieve user anonymity, each vehicle has to generate a pseudonym before commutation. The details of this phase are shown as follows.

  1. 1.

    The vehicle V i inputs its unique real identity RID i and the password PWD i to initiate a pseudo identity generation process.

  2. 2.

    After verifying RID i and PWD i , TPD chooses a random number r and computes pseudo \( ID^{i} = \left\{ {ID_{1}^{i} , ID_{2}^{i} } \right\} \) and \( SK^{i} = \left\{ {SK_{1}^{i} , SK_{2}^{i} } \right\} \).

    $$ \begin{aligned} ID_{1}^{i} = & rP \\ ID_{2}^{i} = & RID_{i} \oplus H\left( {rP_{pub1} } \right) \\ SK_{1}^{i} = & s_{ 1} ID_{1}^{i} \\ SK_{2}^{i} = & s_{2} H\left( {ID_{1}^{i} \parallel ID_{2}^{i} } \right) \\ \end{aligned} $$
  3. 3.

    After that, TPD outputs ID i and SK i, and V i can sign messages by using those values.

  4. 4.

    Each message M i has to be signed before sent. V i signs M i as \( \sigma_{i} = SK_{1}^{i} + h\left( {M_{i} } \right) SK_{2}^{i} \). Subsequently, V i sends the final message {ID i, M i , σ i } to its neighboring RSU.

If V i broadcasts a malicious message, TA can trace the RID i of V i by computing \( RID_{i} = ID_{2}^{i} \oplus H(s_{1} ID_{1}^{i} ). \) Therefore, once a signature is in dispute, the TA has the tracing ability to find the RID of vehicle from the disputed message.

3.3 Message verification

The message verification process of Zhang et al.’s scheme has two versions: single message verification and batch message verification. We briefly describe them as follows.

3.3.1 Single message verification

When each RSU receives any final message, such as {ID i, M i , σ i } from a vehicle, it will verify the message’s validity. If \( \hat{e}(\upsigma_{i} , \, P) = \hat{e}\left( {ID_{1}^{i} , \, P_{pub1} } \right) \cdot \hat{e}\left( {h(M_{i} )H\left( {ID_{1}^{i} \parallel ID_{2}^{i} } \right),P_{pub2} } \right) \), the message is legal and unaltered. The proof is shown as follows.

$$ \begin{aligned} \hat{\text{e}}\left( {\sigma_{i} , P} \right) = &\, \hat{\text{e}}\left( {SK_{1}^{i} + h\left( {M_{i} } \right)SK_{2}^{i} , P} \right) \\ = &\, \hat{\text{e}}\left( {SK_{1}^{i} , P} \right) \cdot \hat{\text{e}}\left( {h\left( {M_{i} } \right)SK_{2}^{i} , P} \right) \\ = &\, \hat{\text{e}}\left( {s_{1} ID_{1}^{i} , P} \right) \cdot \hat{\text{e}}\left( {h\left( {M_{i} } \right)s_{2} H(ID_{1}^{i} \parallel ID_{2}^{i} ), P} \right) \\ = &\, \hat{\text{e}}\left( {ID_{1}^{i} , s_{1} P} \right) \cdot \hat{\text{e}}\left( {h\left( {M_{i} } \right)H(ID_{1}^{i} \parallel ID_{2}^{i} ), s_{2} P} \right) \\ = &\, \hat{\text{e}}\left( {ID_{1}^{i} , P_{pub1} } \right) \cdot \hat{\text{e}}(h(M_{i} )H(ID_{i}^{1} \parallel ID_{2}^{i} ), P_{pub2} ) \\ \end{aligned} $$

3.3.2 Batch message verification

If a RSU receives a number of large messages, denoted as \( \{ ID^{1} ,M_{1} ,\sigma_{1} \} , \, \{ ID^{2} ,M_{2} ,\sigma_{2} \} , \, \{ ID^{3} ,M_{3} ,\sigma_{3} \} \ldots \, \{ ID^{n} ,M_{n} ,\sigma_{n} \} \), in a short span, the RSU can verify the messages’ validity simultaneously by means of batch message verification. If \( \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} \sigma_{i} , P} \right) = \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} ID_{1}^{i} , P_{pub1} } \right) \cdot \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} (h\left( {M_{i} } \right)H(ID_{1}^{i} \parallel ID_{2}^{i} ),P_{pub2} } \right), \) the batch of messages is legal and unaltered. The proof of this equation is as follows:

$$ \begin{aligned} &\hat{e}\left( {\mathop \sum \limits_{i = 1}^{n} \sigma_{i} , P} \right) \\&\,= \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} (SK_{i}^{1} + h(M_{i} )SK_{i}^{2} ), P} \right) \\ &\,= \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} \left( { SK_{i}^{1} } \right), P} \right) \cdot \,\hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} \left( {h\left( {M_{i} } \right)SK_{i}^{2} } \right), P} \right) \\ &\,= \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} \left( {SK_{i}^{1} } \right), P} \right) \cdot \,\hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} (h\left( {M_{i} } \right)s_{2} H(ID_{1}^{i} \parallel ID_{2}^{i} )),P} \right) \\ &\,= \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} s_{1} ID_{1}^{i} , P} \right) \cdot \,\hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} (h\left( {M_{i} } \right)H(ID_{1}^{i} \parallel ID_{2}^{i} )),s_{2} P} \right) \\ &\,= \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} ID_{1}^{i} , s_{1} P} \right) \cdot \, \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} (h\left( {M_{i} } \right)H\left( {ID_{1}^{i} \parallel ID_{2}^{i} } \right)),P_{pub2} } \right) \\ &\,= \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} ID_{1}^{i} , P_{pub1} } \right) \cdot \,\hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} (h\left( {M_{i} } \right)H(ID_{1}^{i} \parallel ID_{2}^{i} )), P_{pub2} } \right) \\ \end{aligned} $$

4 Cryptanalysis of Zhang et al.’s scheme

Zhang et al. proposed an efficient batch message verification to solve the verification bottleneck problem. However, the Zhang et al. scheme has two weaknesses, i.e. (a) it is vulnerable to the replaying attack and (b) it fails to achieve non-repudiation. The details of the two weaknesses of Zhang et al.’s scheme are shown as follows.

4.1 Replaying attack

Zhang et al.’s scheme is vulnerable to the replaying attack. We assume an adversary can intercept a public affair vehicle message and signature. He/she can replay the information to mislead the traffic management system when he/she needs. On the other situation, an adversary can intercept a lot of signatures from different vehicles when those vehicles are in a traffic jam, and replay those signatures to invent a fake traffic jam and mislead other vehicles in order to avoid the jammed sections.

4.2 Not achieving non-repudiation

Zhang et al.’s batch message verification is very efficient. However, the batch verification scheme has a leak, which allows the malicious user to deny his/her signatures. Assume a malicious user generates several different messages and signatures, such as {ID 1, M 1 , σ 1 }, {ID 2, M 2 , σ 2 }, {ID 3, M 3 , σ 3 }, and swaps their contents to become {ID 1, M 1 , σ 3 }, {ID 2, M2, σ 1 }, {ID 3, M 3 , σ 2 }. After that, the malicious user sent those changed messages and signatures to its neighboring RSU. If the RSU uses a batch message verification process to verify those signatures, it will consider that those changed messages and signatures are legal. The proof is shown as follows.

$$ \begin{aligned} \hat{\text{e}}\left( {\mathop \sum\limits_{i = 1}^{3} \sigma_{i} , P} \right) = &\, \hat{\text{e}} \left( {\sigma_{1} + \sigma_{2} + \sigma_{3} , P} \right) \\ = & \hat{\text{e}}\left( {\sigma_{3} + \sigma_{1} + \sigma_{2} , P} \right) \\ = & \,\hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{3} ID_{1}^{i} , P_{pub1} } \right) \cdot \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{3} h(M_{i} )H(ID_{1}^{i} \parallel ID_{2}^{i} ), P_{pub2} } \right) \\ \end{aligned} $$

Although the orders of those signatures have been changed, their sum remains the same. However, those messages and signatures cannot match each other obviously. These signatures can’t be passed if the RSU uses single message verification process to verify them one by one. For this reason, the malicious user can deny his/her signatures.

5 The proposed scheme

To overcome those weaknesses of Zhang et al.’s scheme, we propose an improved scheme. In our scheme, we extend the framework of Zhang et al.’s scheme. We also use a two-layer vehicular network model, and we require each vehicle to have a tamper-proof device. The notation of our scheme is also shown in Table 1.

Our scheme also includes key generation and pre-distribution, pseudo identity generation and message signing, and message verification. The differences between Zhang et al.’s scheme and our scheme are pseudo identity generation and message signing, and message verification. We explain them as follows.

5.1 Key generation and pre-distribution

In our scheme, TA is also responsible for setting up the system parameters for each vehicle and RSU. The process of this phase is the same as Zhang et al.’s scheme, and the difference is easily discerned in the subsequent subsections.

5.2 Pseudo identity generation and message signing

To achieve user anonymity, each vehicle has to generate a pseudonym before commutation. In this subsection, we add a timestamp T i to overcome the replaying attack and use a one-way hash function h 2 () instead of the map to point function H(). The details of this phase are shown as follows.

  1. 1.

    The vehicle V i inputs its unique real identity RID i and the password PWD i to initiate pseudo identity generation process.

  2. 2.

    After verifying RID i and PWD i , TPD chooses a random number r, sets a current timestamp T i , and computes pseudo \( ID^{i} = \left\{ {ID_{1}^{i} , ID_{2}^{i} } \right\} \) and \( SK^{i} = \left\{ {SK_{1}^{i} , SK_{2}^{i} } \right\} \).

    $$ \begin{aligned} ID_{1}^{i} = & rP \\ ID_{2}^{i} = & RID_{i} \oplus H\left( {rP_{pub1} } \right) \\ SK_{1}^{i} = & s_{1} ID_{1}^{i} \\ SK_{2}^{i} = & s_{2} h_{2} \left( {ID_{1}^{i} \parallel ID_{2}^{i} \parallel T_{i} } \right)P \\ \end{aligned} $$
  3. 3.

    After that, TPD outputs ID i and SK i, and V i can sign messages using ID i and SK i.

  4. 4.

    Each message M i has to be signed before sent. V i signs M i as \( \sigma_{i} = SK_{1}^{i} + h\left( {M_{i} } \right)SK_{2}^{i} \). Subsequently, V i sends the final message {ID i, M i , σ i , T i } to its neighboring RSU.

If V i broadcasts a malicious message, TA can trace the RID i of V i by computing \( RID_{i} = ID_{2}^{i} \oplus H(s_{1} ID_{1}^{i} ). \) Therefore, once a signature is in dispute, the TA has the tracing ability to find the RID of vehicle from the disputed message.

5.3 Message verification

When each RSU receives any final message, such as {ID i, M i , σ i , T i } from a vehicle, it will check the message’s T i . If T r  − T i  < T Δ , RSU continues the verification process, or else rejects the final message. T r denotes the received-time of the message and T Δ denotes the predefined endurable transmission delay. The message verification process of our scheme also has two versions: single message verification and batch message verification. The details of these two versions are described as follows.

5.3.1 Single message verification

If the RSU just receives a few final messages in a span, it can verify the message’s validity one by one. For each signature, if \( \hat{\text{e}}\left( {\sigma_{i} , P} \right) = \hat{\text{e}}\left( {ID_{1}^{i} , P_{pub1} } \right) \cdot \hat{\text{e}}\left( {h\left( {M_{i} } \right)h_{2} \left( {ID_{1}^{i} \parallel ID_{2}^{i} \parallel T_{i} } \right)P, P_{pub2} } \right) \), the message is legal and unaltered. The proof of this equation is as follows.

$$ \begin{aligned} \hat{\text{e}}(\sigma_{i} , P) = &\, \hat{\text{e}}\left( {SK_{1}^{i} + h\left( {M_{i} } \right)SK_{2}^{i} , P} \right) \\= &\,\hat{\text{e}}(SK_{1}^{i} , P) \cdot \hat{\text{e}}(h\left( {M_{i} } \right)SK_{2}^{i} , P) \\ = & \,\hat{\text{e}}\left( {s_{1} ID_{1}^{i} , P} \right) \cdot \hat{\text{e}}\left( {h\left( {M_{i} } \right)s_{2} h_{2} \left( {ID_{1}^{i} \parallel ID_{2}^{i} \parallel T_{i} } \right)P, P} \right) \\ = & \,\hat{\text{e}}\left( {ID_{1}^{i} , s_{1} P} \right) \cdot \hat{\text{e}}\left( {h\left( {M_{i} } \right)h_{2} \left( {ID_{1}^{i} \parallel ID_{2}^{i} \parallel T_{i} } \right)P, s_{2} P} \right) \\ = & \,\hat{\text{e}}\left( {ID_{1}^{i} , P_{pub1} } \right) \cdot \hat{\text{e}}\left( {h\left( {M_{i} } \right)h_{2} \left( {ID_{1}^{i} \parallel ID_{2}^{i} \parallel T_{i} } \right)P, P_{pub2} } \right) \\ \end{aligned} $$

5.3.2 Batch message verification

If a RSU receives a number of messages, denoted as {ID 1, M 1 , σ 1 , T 1 }, {ID 2, M 2 , σ 2 , T 2 }, {ID 3, M 3 , σ 3 , T 3 }…{ID n, M n , σ n , T n }, within a short span, the RSU can verify the messages’ validity simultaneously by batch message verification. In this subsection, we add a vector parameter Vec i to overcome the weaknesses of Zhang et al.’s scheme. Before batch message verification, the RSU distributes Vec i to each message and signature. The Vec i ’s value is a random number and ranges between 1 and x, where x is a small value and doesn’t make the overhead of computation. After that, the RSU starts the batch message verification. If

$$ \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} Vec_{i} \sigma_{i} , P} \right) = \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} Vec_{i} ID_{1}^{i} , P_{pub1} } \right) \cdot \hat{\text{e}}\left( {\left( {\mathop \sum \limits_{i = 1}^{n} Vec_{i} h\left( {M_{i} } \right)h_{2} \left( {ID_{1}^{i} \parallel ID_{2}^{i} \parallel T_{i} } \right)} \right)P, P_{pub2} } \right), $$

the batch of messages are legal and unaltered. The proof of this equation is as follows.

$$ \begin{aligned} &\hat{e}\left( {\mathop \sum \limits_{i = 1}^{n} Vec_{i} \sigma_{i} , P} \right)\\ &\,= \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} Vec_{i} \left( {SK_{1}^{i} + h\left( {M_{i} } \right)SK_{2}^{i} } \right), P} \right) \\ &\,= \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} Vec_{i} SK_{1}^{i} , P} \right) \cdot \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} Vec_{i}\,h\left( {M_{i} } \right)SK_{2}^{i} , P} \right) \\ &\,= \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} Vec_{i}\, s_{1} ID_{1}^{i} , P} \right) \cdot \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} Vec_{i}\, h\left( {M_{i} } \right)s_{2} h_{2} \left( {ID_{1}^{i} \parallel ID_{2}^{i} \parallel T_{i} } \right)P, P} \right) \\ &\,= \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} Vec_{i}\, s_{1} ID_{1}^{i} , P} \right) \cdot \hat{\text{e}}\left( {\left( {\mathop \sum \limits_{i = 1}^{n} Vec_{i}\, h\left( {M_{i} } \right)h_{2} \left( {ID_{1}^{i} \parallel ID_{2}^{i} \parallel T_{i} } \right)} \right)s_{2} P, P} \right) \\ &\,= \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} Vec_{i}\, ID_{1}^{i} , s_{1} P} \right) \cdot \hat{\text{e}}\left( {\left( {\mathop \sum \limits_{i = 1}^{n} Vec_{i}\, h\left( {M_{i} } \right)h_{2} \left( {ID_{1}^{i} \parallel ID_{2}^{i} \parallel T_{i} } \right)} \right)P, s_{2} P} \right) \\ &\,= \hat{\text{e}}\left( {\mathop \sum \limits_{i = 1}^{n} Vec_{i}\, ID_{1}^{i} , P_{pub1} } \right) \cdot \hat{\text{e}}\left( {\left( {\mathop \sum \limits_{i = 1}^{n} Vec_{i}\, h\left( {M_{i} } \right)h_{2} \left( {ID_{1}^{i} \parallel ID_{2}^{i} \parallel T_{i} } \right)} \right)P, P_{pub2} } \right) \\ \end{aligned} $$

6 Analysis of our scheme

6.1 Security analysis

In this section, we analyze the security of the proposed batch verification scheme in terms of the security requirements, which includes message authentication, user privacy preserving, and audit-ability, as follows.

  1. (1)

    Message authentication:

The message authentication is the most basic security requirement to ensure the legality of a message’s source and the integrity of a message in any communication. In our scheme, σ i not only uses a one-way hash function to pack the message M i , but also uses a current timestamp T i to generate \( SK_{2}^{i} \) in order to resist the replaying attack and ensures that the signature σ i is fresh. Our scheme also inherits the advantage of Zhang et al.’s scheme, includes that it is difficult to derive the private keys \( SK_{1}^{i} \) and \( SK_{2}^{i} \) by way of ID i, P pub1 , P pub2 , and P [11]. We not only overcome the replaying attack, but also propose a solution to the other problem, non-repudiation. In our scheme, we used a vector parameter Vec i to avoid user swap of the M i and σ i . If a malicious user wants to deny the signatures by swapping M i and σ i , his/her signatures will result in the batch message verification failing. Table 2 is a comparison between our scheme and other schemes which in the same field.

Table 2 Security comparison
Full size table
  1. (2)

    User privacy preserving:

If an adversary attempts to use the information, which is intercepted from public communicating environment, to trace a specific user, he/she needs to determine the relation between each communication. In our scheme, all of information sent by a user is changed in each communication. Therefore, a person’s ID i is converted by an unknown random number r. For this reason, we claim our scheme both achieves and preserves the user anonymity and user privacy.

  1. (3)

    Audit-ability:

To avoid the user privacy preserving abused by the malicious behaviors, the malicious user should have TA traceability, where the traceability is also called conditional privacy [6]. In the proposed scheme, the TA can trace the RID i of V i as the Sect. 5.2 explains. When a user attempts to use malicious information to mislead others, the TA can trace the RID of the malicious user, and stop the right of the malicious user.

6.2 Performance evaluation

We evaluate the performance of our scheme in this section. Verification delay is the most important issue, which may affect the value of information. The different calculations in our scheme include one point multiplication over an elliptic curve, notated T mul , map to point hash operation, notated T mtp , and pairing operation, notated T par . We adopt the MNT curve [11, 20, 26], which embeds degree k = 6 and 160-bit q, running on an Intel Pentium IV 3.0 GHZ machine. The following results are obtained: T mul is 0.6 ms, T par is 4.5 ms, and T mtp is 0.6 ms. We compare the computational complexity of our scheme with Zhang et al.’s scheme and ABAKA in Table 3. Although our scheme has to compute\( Vec_{i} \sigma_{i} \), \( Vec_{i} ID_{1}^{i} \), and \( Vec_{i} h\left( {M_{i} } \right)h_{2} (ID_{1}^{i} \parallel ID_{2}^{i} \parallel T_{i} ) \), the range of Vec i is vary small, such as 1–10, and the cost of Vec i ’s computation is negligible. In fact, the real program design can use addition operation instead of multiplication operation, such as letting \( \sigma_{i} \) plus Vec i times instead of computing \( Vec_{i} \sigma_{i} \). On the other hand, we use a one-way hash function h 2 () instead of the map to point function H() and reduce point multiplication over an elliptic curve to improve the performance. Hence, the efficiency of our scheme is more efficient than Zhang et al.’s scheme.

Table 3 Comparison of three schemes in term of the computational complexity
Full size table

We use the results of the MNT curve and the value of performance comparison to forecast the effect on the batch verification delay of compared schemes in Fig. 1. We let x-axis mean the number of verifying signatures (n) and y-axis mean the delay time (unit: ms). The left side of Fig. 1 is the situation while n is small (range: 1–40), and the right side is the situation while n is large (range: 100–1,000). We can find the slope of our scheme is the lowest. In Fig. 1, although the effect of our scheme isn’t the best when n is lower than 10, it is faster than others when n becomes larger. When n is 100, the delay of ABAKS’s batch verification is 120.6 ms, Zhang’s is 133.5 ms and our scheme’s is 14.1 ms. When n is 1,000, the delay of ABAKS’s batch verification is 1,200.6 ms, Zhang et al.’s scheme is 1,213.5 ms and our scheme’s still maintains 14.1 ms; obviously, our scheme is the best. In addition, our scheme is more secure than ABAKA and Zhang et al.’s scheme. For this reason, our scheme is the most suitable for VANET.

Fig. 1
figure 1

Effect on the batch verification delay. x-axis: the number of verifying signatures (n), y-axis: the delay time (unit: ms)

Full size image

7 Conclusions

With the present day communication technology development, VANET can be regarded as the “predictable” technology. In this paper, we proposed an improved batch scheme for VANET, which overcame the weaknesses of Zhang et al.’s scheme and maintain the efficiency. The scheme is designed to improve the quality of traffic. In the future, we would like to further enhance the features of batch scheme for VANET, such as identifying illegal signatures, designing new schemes in order to gain more efficiency.