A Bilinear Mapping Based Ring Signature Scheme with Batch Verification for Applications in VANETs

Abstract

Nowadays, the traditional transportation systems are being replaced by the Vehicular Ad-hoc Networks (VANETs) based intelligent transportation system. In VANETs, vehicles communicate by sending messages over the open environment, which leads to danger of different privacy and security issues, so it becomes necessary to prevent those messages from various privacy and security attacks. To prevent from those attacks, a new certificateless ring signature scheme is proposed in this paper. The proposed technique uses the concept of batch verification. The formal security analysis of the proposed scheme is done using RoR model. We use the AVISPA tool to show the formal security verification of the proposed scheme to prove that the scheme is resistant to active and passive attacks. In the performance analysis, the proposed scheme is compared with the existing schemes and the results show that our scheme has less computation cost and communication cost.

Introduction

The expeditious development in the field of communication and technology has been making the transportation systems more intelligent. The Intelligent Transportation Systems (ITS) are developed to solve the traffic problems [1] occurred due to the conventional transportation system. The ITS reduces the accidents and increases the safety of the drivers by transmitting the messages over the network. If any message contains the malicious information or it get altered, then it may lead to the serious problems in the road including accidents and traffic congestion. So, it is necessary to secure the messages and this can be done by using different signature schemes and authentication techniques [2, 3].

In intelligent transportation system, the VANETs comprise mainly three components: mobile On Board Units (OBUs) on cars, static Road Side Units (RSUs) and a central unit called Trusted Root Authority (TRA). In the network, vehicles can communicate with each other or with infrastructure through the VANETs for sending messages and authentication. Mainly, there are two types of communication involved in the VANETs i.e., Vehicle-to-Vehicle(V2V) and Vehicle-to-Infrastructure(V2I). In former, the communication takes place between the OBUs of the vehicles while in the latter, OBUs of the vehicles and the RSU or TRA communicate to exchange the messages. While exchanging the information between the units over the network, there may be a threat that the data can be altered by the attackers and cause the serious harm. Message modification is one of the challenges along with the driver or vehicles privacy. For secure communication between the vehicles, many signature and conditional privacy preserving authentication schemes are specially developed for the VANETs. In these schemes, vehicles send signatures along with the messages to the receiver and on receiving the signatures and their corresponding messages from the sender, receiver verifies the single message or the bunch of messages using the verification algorithms proposed in the schemes. These schemes [4, 5, 6, 7, 8–9] are using different cryptographic structures like public-key [10] and identity [11]. Some of the schemes [4, 5–6] are using group signatures but these group signatures are replaced by the ring signatures as in the group signature, members are static which is not a good choice for the VANETs. And also the schemes are adopting the concept of batch verification [12] for reducing the computation overhead. In this paper, we propose a bilinear mapping based certificateless ring signature scheme with batch verification for applications in VANETs to reduce the communication cost and computational cost. Its formal security analysis is performed by RoR model and formal security verification is done by AVISPA tool, which shows that it is resistant to passive and active attacks.

Rest of the paper is arranged as follows. Section 2 overviews the existing signature schemes for the VANETs. In Sect. 3, some preliminary notions are defined and Sect. 4 describes our proposed scheme. The security analysis of the proposed scheme is done using the RoR and AVSIPA in Sect. 5. Section 6 discusses the comparison between our scheme and the related existing schemes. Lastly, the paper is concluded in the Sect. 7.

Literature Survey

Researchers come up with different solutions to resolve the different issues like privacy and security issues of VANET. The solutions use the different cryptographic structure like public key infrastructure, identity based signature, group and ring signatures. For ease of readiness, the existing work for ensuring privacy preservation in VANETs architecture has been divided into mainly four categories based on public key infrastructure, identity, group and ring. We have summarized the existing schemes in Table 1. In the first category, the schemes [7, 8–9] use the Public Key-based Infrastructure (PKI) [10]. The Vehicles and RSUs use the anonymous certificates issued by trusted authorities with maintaining the user anonymity and integrity. The issue in these schemes occurs with TRA as it suffers from the overburden of memory as TRA stores and manages the vehicles certificates.

The second category contains the schemes [13, 14, 15–16] based on identity signature [11] and these schemes reduce the requirement of the storage by the PKI. Identity-based signature uses the public information of vehicles as the public key. The information can be anything related to the vehicle such as names, contact numbers, email addresses, etc. The problem in identity-based signature is inherent key escrow property.

In the third category, we have clustered the schemes [4, 5–6, 17, 18, 19, 20–21] which are constructed on the concept of group signatures which is very different from the all the previous schemes. Chaum and Heyst [22] propose the first scheme based on group signature. In these schemes, only one member of the group is allowed to sign a message on the behalf of whole group. But in case of contention, group manager can disclose the identity of the signer. There is one disadvantage while signing the message, the group members cannot be added or removed as groups are static [23]. The group signature come usually with a set-off between anonymity and group size.

The fourth category includes the schemes [24, 25, 26, 27, 28, 29–30] which are based on the ring signature. Rivest et al. [31] solve the issues in group signature by introducing a new concept called ring signature. Ring signature provides more advantages than group signature including no group manager, strong traceability and anonymity. The ring signature may be certificate or certificateless. The certificate ring signature is inefficient in terms of space and time as it requires the transfer and verification of n certificates. Due to this inefficiency, the ring signature works in VANET.

To reduce the computation overhead in individual verification of several messages simultaneously, researchers have used the concept of batch verification. The paper [12] defines a batch verification method in which a sequence of exponential is verified by the probabilistic batch verifiers. This concept yields faster speed than the naive re-computation method. Recently researchers [5, 17, 32] have integrated the batch verification concept with different signature schemes to reduce the verification time significantly.

Table 1. Literature survey

Schemes	Categories	Batch-verification	Shortcomings
[7]	Public key based signature	No	Certificate management is time consuming inefficient scheme
[4]	Group based signature	No	No practical implementation suffers from non-repudiation
[5]	Group based signature	Yes	No collusion resistant high communication overhead
[13]	Identity based signature	No	High complexity, large storage required suffer from key escrow problem different authentication mechanism for RSUs vehicles
[17]	Group based signature	Yes	Not defined the communication and computation cost suffer from impersonation and replay attack
[18]	Group based signature	No	Involved complex operations relatively high computation and communication cost
[19]	Group based signature	No	No conditional privacy preservation does not provide unforgeability group leader can be compromised
[20]	Group based signature	Yes	High computation and communication overhead
[33]	Identity based signature	Yes	High computational overhead
[9]	Public key based signature	No	High computation and communication cost
[21]	Group based signature	No	Finding and revoking malicious vehicle is time consuming
[24]	Ring based signature	No	Communication and computation cost is not provided
[25]	Ring based signature	No	High system complexity
[26]	Ring based signature	No	Need certificate revocation list management regular checking of public keys in CRL
[27]	Ring based signature	No	Not able to revoke malicious vehicles
[6]	Identity based signature	Yes	Suffers from non-repudiation
[14]	Identity based signature	Yes	No identity anonymity
[8]	Public key based signature	No	High computational and communication overhead vulnerable to modification and replay attack
[16]	Identity based signature	Yes	No identity anonymity, high communication high computation cost
[32]	Ring based signature	Yes	Not efficient for individual verification

Preliminaries

In this section, we define a basic concept of a VANET architecture, its security requirement, bilinear mapping, framework of the proposed scheme and its security model as follow.

System Architecture

The basic VANET architecture consists of the three components OBUs, RSUs and TRA as shown in Fig. 1. These components are described as below:

• OBU: These communication devices are pre-installed on the vehicles. The OBUs can be used for exchanging the traffic related messages and the information like identity, speed, etc. of the vehicle between the RSU and OBUs.

• RSU: Road side units are the fixed units installed on the sides of the road. When RSU, OBU and TRA want to communicate, then RSU can be used as mediator between the OBU and TRA. The RSU sends different parameters to the TRA whenever it is required and also performs the verification procedure to send messages to TRA.

• TRA: It is a trusted root authority. It is known as the central authority in the VANETs. TRA can be used in VANETs to generate the public parameters and other necessary information. TRA receives the data and messages from the RSU and then broadcast the messages. It is used to manage the network.

[See PDF for image]

Fig. 1

Vanet

Security Requirements

In the VANETs, security is the top most requirement. Security requirements includes mainly conditional privacy preserving authentication, integrity, non-repudiation and traceability.

• Authentication: There must be an authentication mechanism for both the vehicles and messages. This ensures that the message must not been modified by the malicious vehicle.

• Privacy: If the identity of the vehicle is revealed, then it becomes dangerous to the vehicle as the attacker can use his/her identity in a wrong deed like sending the malicious messages to other vehicles. So, it is necessary to have a mechanism which ensures the privacy of the vehicle.

• Non-repudiation: There may be a case when a vehicle denies that the message is not send by him. So, the RTA must have the mechanism which can be used to prove that the message has been send by the same vehicle while preserving the privacy of the vehicle.

• Traceability: The malevolent vehicles can send the messages which either can harm the vehicles in the network or the entire network. So, the administrator must have the power to rescind the services of that vehicles and prevent the network.

Bilinear Mapping

Bilinear mapping is a mathematical concept that plays a crucial role in various cryptographic schemes and protocols. It involves pairing operations between elements of two mathematical groups, and it exhibits certain advantageous properties that make it particularly useful in the field of cryptography. Bilinear maps possess homomorphic properties, allowing operations to be performed on the outputs of the map that correspond to operations on the inputs. This property is especially valuable in cryptographic constructions, such as homomorphic encryption and digital signatures. Cryptographic protocols built on bilinear maps often exhibit efficiency in terms of computational and communication costs. This efficiency is crucial for practical deployment in resource-constrained environments, such as those encountered in IoT (Internet of Things) or mobile applications. Bilinear maps play a significant role in batch verification techniques, especially in the context of signature schemes. Batch verification allows multiple signatures to be verified simultaneously, leading to computational efficiency and reduced overhead.

Let the two groups $G_{\mathit{add}}$ with a generator X and $G_{\mathit{mul}}$ be additive and multiplicative group of same order $p>2^k$ respectively. Then a bilinear mapping $e:G_{\mathit{add}}\times G_{\mathit{add}}\to G_{\mathit{mul}}$ satisfies the following properties:

• Bilinearity: For all $m,n\in {Z_p}^{\ast }$ and $X,Y\in G_{\mathit{add}}$, $e\left(m,X,,,n,Y\right)=e{\left(X,,,Y\right)}^{\mathit{mn}}$

• Non-degeneracy: $e\left(X,,,Y\right)\ne 1$

• Computability: $e\left(X,,,Y\right)$ can be computed efficiently for all $X,Y\in G_{\mathit{add}}$

Definition 1

The Computational Diffie–Hellman(CDH) Problem: The goal is to compute the abP for a given Group G with a generator X and a tuple (aP, bP) for unknown $a,b\in Z_q^{\ast }$ under CDH assumption in G if no polynomial time algorithm solves the CDH problem with a probability at least $ϵ$.

Definition 2

The Decisional Diffie Hellman(DDH) Problem: The goal is to decide whether Y=abX for a given Group G with a generator X and a tuple (aP,bP, Y) for unknown $a,b\in Z_q^{\ast }$ and $Y\in G$ under the assumption that no adversary decides Y in at least $ϵ$ time.

Framework for Proposed Scheme

The proposed scheme consists of the following five phases:

• Initial Setup Phase: It is run by TRA to generate the output parameters vars.

• Registration and Key Generation: It is run by the OBU and RSUs to register themselves with TRA and obtain Keys.

• Certificateless ring Signature: It is run by OBUs to sign the message.

• Individual Verification: It is run by the RSUs to verify the single message.

• Batch Verification: It is run by the RSUs to verify the messages in batch.

Security Model

For the security analysis of the proposed model, we are assuming three adversaries: Eve I, Eve II and Eve III having following capabilities: The Eve I can substitute the entities public key with the key of his own choice and the entities partial private key cannot be extracted by Eve I. The Eve II has not the ability to replace the entities public key but can extract the entities private key. The Eve III cannot able to recognise the real signer with a negligible probability 1/n despite having the knowledge of all ring members public key. We have modelled the three games between an opponent and an Eve belongs to I, II, III for the security analysis of the proposed scheme. Eves can execute the listed queries to oracle with a polynomial time limitation.

• Query$H_i$($Q_{h_i}$): Opponent return the hashes for the inputs.

• Query 1($Q_1$): On receiving the request of entities public key by the Eve, the opponent returns the same.

• Query ($Q_2$): On receiving the request of entities partial private key by the Eve, the opponent returns the same.

• Query ($Q_3$): On receiving the request of entities private key by the Eve, the opponent returns the same.

• Query ($Q_4$): The Eve generates a new public key for the entity ID. And then the opponent substitutes the current public key with the newly generated key.

• Query ($Q_5$): The opponent generates the signature for the Eve’s request. The Eve selects message, set of entities identities and their corresponding public key and sends them to the opponent.

Unforgeability:

Game I: Unforgeability of scheme against Eve I

Definition 3

If there is no eve which wins the Game I in polynomial time with a non-negligible probability, so the proposed scheme is said to be unforgeable against the Eve I.

In the Game I, initially the opponent executes the initial setup algorithm to produce the system parameter vars and sends to the attacker Eve I and master secret key which it keeps secret. The Eve I runs the queries $Q_1,Q_2,Q_3,Q_4,Q_5$ sequentially to generate the certificateless signature. The eve wins the Game I if the listed three conditions are satisfied:

• Eve cannot request for the partial-private key of any entities in $L_{\mathit{ID}}$.

• Certificate less signature queries has never been executed to generate the signature.

• The forged signature is valid.

Game II: Unforgeability of scheme against Eve II

Definition 4

If there is no eve which wins the Game II in polynomial time with a non-negligible probability, so the proposed scheme is said to be unforgeable against the Eve II.

In the Game II, initially the opponent executes the initial setup algorithm to produce the system parameter vars and master secret key. The opponent sends both of them to the attacker Eve II. The Eve II runs the queries $Q_1,Q_4,Q_5$ sequentially to generate the certificateless signature. The attacker eve wins the Game I if the listed three conditions are satisfied:

• Eve cannot request for the private key of any entities in $L_{\mathit{ID}}$.

• Certificate less signature queries has never been executed to generate the signature.

• The forged signature is valid.

Anonymity:

Game III: Anonymity against Eve III

Definition 5

Despite having unrestricted computational resources, the receiver cannot recognise the actual signer with the probability less than 1/n.

The opponent sends the vars and the $T_{\mathit{msk}}$ to the attacker Eve III. The vars and $T_{\mathit{msk}}$ are generated by the opponent using the initial setup algorithm of the proposed model. To win the Game III, the eve must satisfy the following conditions:

• Attacker return two ID of different entities$I{D}_u$, u belongs to 0,1 and message to the opponent.

• The opponent chooses one ID randomly $I{D}_u$, u belongs to 0,1 and sends the certificateless signature of the corresponding entity to the attacker eve.

• Eve outputs a bit belongs to 0,1 and wins the game if and only if $u=u^{\prime }$.

Proposed Scheme

Before discussing our proposed bilinear mapping based ring signature scheme for VANETs, we present the notations used in the paper in Table 2. The presented Fig. 2 illustrates the process of certificateless ring signature generation, individual verification, and batch verification within a cryptographic system. In the certificateless ring signature generation phase, the On-Board Unit (OBU) initiates the signing process by randomly selecting a secret value and computing various cryptographic components, including hash functions and unique keys. The result is an individualized signature, denoted as $\sigma j$, containing elements such as $H{T}_j$, $T_j$, and $U_j$, which is then sent to the RSU for verification. In the individual verification phase, the RSU computes ${H_{3_j}}^{{}^{\prime }}$ and evaluates an equation involving the signature and public keys. If the equation holds true, the RSU accepts the message; otherwise, it rejects it.

Moving on to batch verification, the RSU aggregates individual signatures into a collective signature $\sigma$, calculated by summing up the individual components. The RSU then checks the validity of the batch signature using a verification equation involving aggregated components and public keys. If the equation is valid, the RSU accepts the entire set of messages; otherwise, it rejects them collectively. This batch verification process enhances efficiency by allowing the RSU to verify multiple signatures simultaneously. The entire cryptographic workflow ensures the integrity and authenticity of messages in a distributed communication system while preserving the privacy and security of the communicating entities. The stepwise description given below involves the TRA producing the output parameters and generating the key pair, OBU randomly selecting values, computing various cryptographic components, and sending the resulting signature to the RSU. The RSU, in turn, performs computations on received signatures, verifies equations, and either accepts or rejects the individual or batch of messages based on the outcomes of these verifications. These processes collectively contribute to the security and authenticity of messages transmitted in a vehicular communication environment.

Table 2. Notations used in the proposed scheme

Notations	Description
p	Prime number
s	Security parameter
$G_{\mathit{add}},G_{\mathit{mul}}$	Additive and multiplicative group of order of $p{2}^s$ respectively
$z_p^{\ast }$	Multiplicative group of order of p
$h_i,i=1,2,3,4,5$	Hash function
$m_k$	Message to be signed
$T_{\mathit{pbk}}$	System public key
$T_{\mathit{msk}}$	System master key
vars	$\{G_{\mathit{add}},G_{\mathit{mul}},X,p,T_{\mathit{pbk}},h_i\}$
$I{D}_k$	Identity of the entity k
$P{K}_k$	Public key for $I{D}_k$
$PS{K}_k$	Partial private key for $I{D}_k$
$S{K}_k$	Private key for $I{D}_k$
$L_k={\cup }_{k=1}^n{\{ID\}}_k$	List of identities of all ring members
$L_{\mathit{PK}}={\cup }_{k=1}^n{\{PK\}}_k$	List of public key of all ring members

[See PDF for image]

Fig. 2

Flow diagram

Initial Setup Phase TRA selects a parameter k and creates system parameters $\{G_{\mathit{add}},G_{\mathit{mul}},X,p,T_{\mathit{pbk}},H_i\}$ and master key $T_{\mathit{msk}}$. In the Initial Setup phase, the following steps are performed by TRA:

TRA:

• Take two groups, $G_{\mathit{add}}$ with generator X and $G_{\mathit{mul}}$ of the same order where $p>2^s$, along with a bilinear map e defined such that $G_{\mathit{add}}\times G_{\mathit{add}}\to G_{\mathit{mul}}$.

• Choose $r\in {\mathbb{Z}}_p^{\ast }$ as $T_{\mathit{msk}}$, and then compute the system public key as $T_{\mathit{pbk}}=rX\in G_{\mathit{add}}$.

• Choose five hash functions $\{h_i,i=1,2,3,4,5\}$, such that $h_1:{\{0,1\}}^{\ast }\to G_{\mathit{add}}$, $h_2:{\{0,1\}}^{\ast }\times G_{\mathit{add}}\times G_{\mathit{add}}\times G_{\mathit{add}}\to {\mathbb{Z}}_p^{\ast }$, $h_3:{\{0,1\}}^{\ast }\to {\mathbb{Z}}_p^{\ast }$, $h_4:{\{0,1\}}^{\ast }\to {\mathbb{Z}}_p^{\ast }$, and $h_5:{\{0,1\}}^{\ast }\to {\mathbb{Z}}_p^{\ast }$.

• Keep the Master Key r private and publicize the variables $vars=\{G_{\mathit{add}},G_{\mathit{add}},X,p,T_{\mathit{pbk}},h_i,i=1,2,3,4,5\}$.

This summarizes the key actions taken during the initial setup phase, providing a clear overview of the steps involved.

Registration & Key Generation This phase is responsible for registering the entity to the TRA and TRA is going to generate public–private key pair as shown for each registered entity. In the Registration and Key Generation phase, the entities TRA, RSU, and OBU perform the following steps:

RSU and OBU:

1. Entity identity $E_k$ is represented by $I{D}_k\in {\{0,1\}}^{\ast }$.

2. Create hash $W_k=h_1(I{D}_k)\in G_{\mathit{add}}$.

3. Choose a secret value $v_k\in {\mathbb{Z}}_p^{\ast }$.

4. Compute $V_k=v_k{W}_k\in G_{\mathit{add}}$ and $D_k=v_{k}X\in G_{\mathit{add}}$.

5. Send both $(V_k,D_k)$ to TRA for registration.

TRA:

1. Choose a secret value $o_k$ and compute $O_k=o_{k}X\in G_{\mathit{add}}$.

2. Calculate $H_{1_k}=h_2(I{D}_k,V_k,D_k,O_k)\in {\mathbb{Z}}_p^{\ast }$.

3. Calculate $PS{K}_k=r{H}_{1_k}{W}_k\in G_{\mathit{add}}$.

4. Send $O_k$, $PS{K}_k$, and $H_{1_k}$ to entity $E_k$.

RSU and OBU:

1. Receive $O_k$, $PS{K}_k$, and $H_{1_k}$ from TRA.

2. Store $P{K}_k=(V_k,D_k)$ and $S{K}_k=(v_k,PS{K}_k)$.

This summarizes the registration and key generation process, detailing the specific actions taken by each entity involved.

Certificateless Ring Signature Entity signs message and sends it to RSU. There are n ring members $L_{\mathit{ID}}=\left\{I,D_1,,,I,D_2,,,I,D_3,,,.,.,.,,,I,D_n\right\}$ and corresponding public key $L_{\mathit{PK}}=\left\{P,K_1,,,P,K_2,,,P,K_3,,,.,.,.,,,P,K_n\right\}$. The signer $I{D}_j$ has private key $S{K}_j$ and public key $P{K}_j$. $I{D}_j$ can sign message $m_j$, on behalf of ring members $L_{\mathit{ID}}$ and public key $L_{\mathit{PK}}$ using its private key $S{K}_j$. In the Certificateless Ring Signature phase, the OBU performs the following steps:

OBU:

1. The OBU $I{D}_j$ randomly selects $t_j\in {\mathbb{Z}}_p^{\ast }$.

2. Computes $H_{2_j}=h_5(m_j\Vert PS{K}_j\Vert P{K}_j\Vert t_j)\in {\mathbb{Z}}_p^{\ast }$.

3. Computes $t_j=H_{1_j}(t_j+H_{2_j})V_j\in G_{\mathit{add}}$.

4. For all $P{K}_k\in L_{\mathit{PK}}$, $I{D}_j$ randomly picks $T_K\in G_{\mathit{add}}$ for each $k\in \{1,2,...,n\}\backslash \{j\}$.

5. Computes $H_{T_j}={\sum }_{k=1}^n{h}_4(m_j\Vert T_k)\in {\mathbb{Z}}_p^{\ast }$.

6. Computes $H_{3_j}=h_5(m_j\Vert L_{\mathit{ID}}\Vert L_{\mathit{PK}}\Vert H_{T_j})\in {\mathbb{Z}}_p^{\ast }$.

7. Computes $U_j=(t_j+H_{2_j})H_{3_j}{v}_{j}PS{K}_j\in G_{\mathit{add}}$.

8. Sends ${\sigma }_j=(H_{T_j},T_j,U_j)$ to the receiver $I{D}_r$.

This summarizes the steps involved in the Certificateless Ring Signature process, detailing the actions taken by the OBU during the generation of the ring signature.

Individual Verification This algorithm is run by the receiver to verify the single message. In the Individual Verification phase, the entity RSU performs the following steps:

RSU:

1. Computes ${H_{3_j}}^{{}^{\prime }}=h_5(m_j\Vert L_{\mathit{ID}}\Vert L_{\mathit{PK}}\Vert H_{T_j})\in {\mathbb{Z}}_p^{\ast }$.

2. RSU $I{D}_r$ verifies the following equation: $$\begin{array}{c}\hfill e(U_j,X)=e({H_{3_j}}^{{}^{\prime }},T_j,T_{\mathit{pbk}})\end{array}$$ If the above equation holds, the receiver accepts the message $m_j$; otherwise, it rejects it.

This describes the individual verification process performed by the RSU, focusing on the verification equation and the decision-making based on its outcome. Similar steps can be followed by other entities involved.

Batch Verification Run by the receiver $I{D}_r$. RSU receives the set of certificateless signature $L_{\sigma }={\bigcup }_{j=1}^n{\sigma }_j$ on the set of user messages $L_m={\bigcup }_{j-1}^n{m}_j$ from the set of signer set $L_{\mathit{ID}}$, where j is the index of signer in the same ring list.

In the Batch Verification phase, the entity RSU performs the following steps:

RSU:

1. Compute $\cup ={\sum }_{j=1}^n{U}_j$.

2. Produce the aggregate signature $\sigma =\{H_{T_1},...H_{T_n},T_1,...T_n,U\}$.

3. For $\forall j=\{1,...,n\}$, calculate ${H_{3_j}}^{{}^{\prime }}=h_5(m_j\Vert L_{\mathit{ID}}\Vert L_{\mathit{PK}}\Vert H_{T_j})$.

4. RSU verifies the following equation: $$\begin{array}{c}\hfill e(U,X)=e\left(\sum _{j=1}^n,{H_{3_j}}^{{}^{\prime }},T_j,T_{\mathit{pbk}}\right)\end{array}$$ If the above equation is valid, RSU accepts the message $L_m$; otherwise, it rejects it.

This summarizes the batch verification process performed by the RSU, emphasizing the aggregation of signatures and the verification equation to validate the batch of messages. Similar steps can be followed by the other entities involved.

Proof of Verification:

$$\begin{array}{c}\text{Individual Signature:}e\left(U_j,X\right)=e\left(\left(t_j+H_{2_j}\right)H_{3_j}{v}_{j}PS{K}_j,X\right)\\ =e\left(\left(t_j+H_{2_j}\right)H_{3_j}{v}_j,r{H}_{1_j}{W}_j,X\right)\\ =e\left(H_{3_j}{H}_{1_j}\left(t_j+H_{2_j}\right)v_j{W}_j,rX\right)\\ =e\left(H_{3_j}{H}_{1_j}\left(t_j+H_{2_j}\right)V_j,P_{\mathit{pbk}}\right)\\ =e\left(H_{3_j}{T}_j,P_{\mathit{pbk}}\right)\\ \end{array}$$

$$\begin{array}{c}\text{Batch Signature:}e\left(U,X\right)=e\left(\sum _{j=1}^n{U}_j,X\right)\\ =e\left(\sum _{j=1}^n\left(t_j+H_{2_j}\right)H_{3_j}{v}_{j}PS{K}_j,X\right)\\ =e\left(\sum _{j=1}^n\left(t_j+H_{2_j}\right)H_{3_j}{v}_{j}r{H}_{1_j}{W}_j,X\right)\\ =e\left(\sum _{j=1}^n{H}_{3_j}{H}_{1_j}\left(t_j+H_{2_j}\right)v_j{W}_j,rX\right)\\ =e\left(\sum _{j=1}^n{H}_{3_j}{H}_{1_j}\left(t_j+H_{2_j}\right)V_j,P_{\mathit{pbk}}\right)\\ =e\left(\sum _{j=1}^n{H}_{3_j}{T}_j,P_{\mathit{pbk}}\right)\\ \end{array}$$

Table 3. Queries run by Eve I

Queries	Eve 1	Opponent
$Q_{h_1}$	Sends a request $Q_{h_1}$ on $I{D}_k$	Prepares the $Lis{t}_1$ of tuple $\left(I,D_k,,,W_k\right)$ If $I{D}_k$ is on list 1, returns $W_k$ from $Lis{t}_1$. Else, execute the following steps: If $I{D}_k$ is same as $I{D}^{\ast }$, then assign $W_k$ with bX and returns $W_k$ to Eve I and adds tuple $\left(I,D_k,,,W_k\right)$ to $Lis{t}_1$. If $I{D}_k$ is not same as $I{D}^{\ast }$, then assigns $u_{H_1}X$ with $h_1\left(I,D_k\right)$ where $u_{H_1}$ is randomly chosen from $z_p^{\ast }$ and returns $u_{H_1}X$ to Eve I and adds tuple $\left(I,D_k,,,U_{H_1},X\right)$ to $Lis{t}_1$
$Q_{h_2}$	Sends a request $Q_{h_2}$ on $\left(I,D_k,,,V_k,,,D_k,,,O_k\right)$	Prepares the $Lis{t}_1$ of tuple $\left(I,D_k,,,V_k,,,D_k,,,O_k,,,H_{1_k}\right)$ If $\left(I,D_k,,,V_k,,,D_k,,,O_k,,,H_{1_k}\right)$ is on $Lis{t}_2$, returns $H_{1_k}$ from $Lis{t}_2$. Else, assigns $H_{1_k}$ with $h_2\left(I,D_k,,,V_k,,,D_k,,,O_k\right)$ where $H_{1_k}$ is randomly selected from $z_p^{\ast }$. and returns $H_{1_k}$ and adds the tuple $\left(I,D_k,,,V_k,,,D_k,,,O_k,,,H_{1_k}\right)$ to the $Lis{t}_2$
$Q_{h_3}$	Sends a request $Q_{h_3}$ on $\left(m_k,,,P,S,K_k,,,P,K_k,,,t_k\right)$	Prepares the $Lis{t}_3$ of tuple $\left(m_k,,,P,S,K_k,,,P,K_k,,,t_k,,,H_{2_k}\right)$ If $\left(m_k,,,P,S,K_k,,,P,K_k,,,t_k,,,H_{2_k}\right)$ is on $Lis{t}_3$, returns $H_{2_k}$ from $Lis{t}_3$. Else, $H_{2_k}$ belongs to $z_p^{\ast }$ and assign $H_{2_k}$ with $h_3\left(m_k,∥P,S,K_k∥,P,K_k,∥t_k∥\right)$ and returns $H_{2_k}$ to Eve 1 and adds $\left(m_k,,,P,S,K_k,,,P,K_k,,,t_k,,,H_{2_k}\right)$tuple to the $Lis{t}_3$
$Q_{h_4}$	Sends a request $Q_{h_4}$ on $\left(m_j,,,T_1,,,.,.,.,,,T_{j-1},,,T_{j+1},,,.,.,.,,,T_n\right)$	Prepares a $Q_{h_4}$ of tuple $Q_{h_4}$ on $\left(m_j,,,T_1,,,.,.,.,,,T_{j-1},,,T_{j+1},,,.,.,.,,,T_n,,,H_{T_j}\right)$ If $Q_{h_4}$ on $\left(m_j,,,T_1,,,.,.,.,,,T_{j-1},,,T_{j+1},,,.,.,.,,,T_n,,,H_{T_j}\right)$ is on $Lis{t}_4$, returns $H_{T_j}$ from $Lis{t}_4$. Else, assigns $H_{T_j}$ with ${\sum }_{j=1}^n{h}_4\left(m_j,||,T_k\right),\forall 1,2,..,n-\{j\}$ where $H_{T_j}$ is randomly chosen from $z_p^{\ast }$ and returns $H_{T_j}$ and adds to the $Lis{t}_4$
$Q_{h_5}$	Sends a request $Q_{h_4}$ on $\left(m_j,,,L_{\mathit{ID}},,,L_{\mathit{PK}},,,H_{T_j},,,H_{3_j}\right)$	Prepares a $Lis{t}_5$ of tuple $\left(m_j,,,L_{\mathit{ID}},,,L_{\mathit{PK}},,,H_{T_j},,,H_{3_j}\right)$. If $\left(m_j,,,L_{\mathit{ID}},,,L_{\mathit{PK}},,,H_{T_j},,,H_{3_j}\right)$ is on $Lis{t}_5$, returns $H_{3_j}$ from $Lis{t}_5$. Else, choose $H_{3_j}$ belongs to $z_p^{\ast }$ assigns $H_{3_j}$ with $h_5\left(m_k,||,L_{\mathit{ID}},||,L_{\mathit{PK}},||,H_{T_j}\right)$. And returns $H_{3_j}$ and insert the tuple to the $Lis{t}_5$
$Q_1$	Sends a request $Q_1$ on $I{D}_k$	Prepares $Lis{t}_T$ of tuple $\left(I,D_k,,,v_k,,,V_k,,,D_k,,,P,S,K_k\right)$ If $Lis{t}_T$ contains $\left(I,D_k,,,v_k,,,V_k,,,D_k,,,,\ast \right)$, returns $\left(v_k,,,D_k\right)$ Else, choose $v_k$ belongs to ${Z_p}^{\ast }$ and executes $q_{h_1}$ to get $W_k$ from $Lis{t}_1$ and returns $\left(v_k,,,W_k,,,v_k,X\right)$ insert$\left(I,D_k,,,v_k,,,V_k,,,D_k,,,,\ast \right)$ to the $Lis{t}_T$
$Q_2$	Sends a request $Q_2$ on $I{D}_k$	Substitutes the current public key $\left(v_k,,,D_k\right)$ with $\left({V_k}^{{}^{\prime }},{D_k}^{{}^{\prime }}\right)$ and insert with $\left(I,D_k,,,v_k,,,{V_k}^{{}^{\prime }},{D_k}^{{}^{\prime }},,,,\ast \right)$ to $Lis{t}_T$
$Q_3$	Sends a request $Q_3$ on $I{D}_k$	If $I{D}_k$ is same as $I{D}_{\ast }$, Game I fails. If $I{D}_k$ is not same as the $I{D}_{\ast }$, if $PS{K}_K$ is in $Lis{t}_T$, then returns the $PS{K}_K$ from $Lis{t}_T$. Else, get $u_{H_1}$ and $H_{1_k}$ from $Lis{t}_1$, $Lis{t}_2$ respectively. Assigns $PS{K}_k$ with $u_{H_1}{H}_{1_k}aX$, returns $PS{K}_k$ and insert $\left(I,D_k,,,,\ast ,,,,\ast ,,,,\ast ,,,P,S,K_k\right)$ to $Lis{t}_T$
$Q_4$	Sends a request $Q_4$ on $I{D}_k$	If $\left(I,D_k,,,v_k,,,V_k,,,D_k,,,P,S,K_k\right)$, returns $\left(v_k,,,P,S,K_k\right)$
$Q_5$	Selects a set of ring members $L_{\mathit{ID}}$ and their corresponding public keys to generate a signature, Sends request $Q_5$ with message	Selects a signer randomly $j\in \left\{1,,,2,,,.,.,.,,,n\right\}$ and signer chooses $t_j$ belongs to ${Z_p}^{\ast }$ calculate $H_{2_j}$ belongs to ${Z_p}^{\ast }$,$H_{2_j}=h_3\left(m_j,∥P,S,K_j∥,P,K_j,||,t_j\right)$ using $Lis{t}_3$ Calculate $T_j=H_{1_j}\left(t_j,+,H_{2_j}\right)V_j$ belongs to $G_{\mathit{add}}$. And user $Lis{t}_2$ for $H_{1_j}$ for all $P{K}_k$ belongs to $L_{\mathit{PK}}$, chooses $T_k$ belongs to $G_{\mathit{add}}$, for all k belongs to $\left(1,,,2,,,.,.,.,,,n\right)\backslash \left\{j\right\}$, computes $H_{T_j}$ belongs to ${Z_p}^{\ast }$, where ${Z_p}^{\ast }$ and find $H_{T_j}$ in $Lis{t}_4$. Calculate $H_{3_j}$ belongs to ${Z_p}^{\ast }$ where $H_{3_j}=h_5\left(m_j,∥L_{\mathit{ID}}∥,L_{\mathit{PK}},||,H_{T_j}\right)$, for $H_{3_j}$ finds in $Lis{t}_5$. Cassigns $U_j=\left(v_j,+,H_{2_j}\right)H_{3_j}{v}_{j}PS{K}_j$ belongs to $G_{\mathit{add}}$. Returns $\alpha =\left(T_j,,,U_j,,,H_{3_j}\right)$ on $m_j$

Security Analysis

In this section, we show the formal security analysis of the proposed a scheme using the Real or Random model (ROR) and verify its security using Automated Validation of Internet Security Protocols (AVISPA).

Formal Security Analysis Using RoR

Theorem 1

The proposed scheme is unforgeable against Eve I where Eve I is allowed to run the queries in the random oracle model under the assumption that CDHP is intractable.

Proof

On receiving (aX, bX), the opponent has to determine the value of abX. System master secret key and system parameters are generated by the opponent. The generated vars sends to the Eve I. Eve I can execute the polynomial time oracle queries listed in Table 3.

Forgery: If the following conditions met, then the Eve I can successfully forge the signature:

• Eve I cannot run the $Q_3$ to extract the partial private key.

• Eve I do not execute the $Q_5$ to get the forged signature.

• A forged signature is valid if $e\left(U_j,,,X\right)=e\left(H_{3_j},,,T_j,,,T_{\mathit{pbk}}\right)$.

CDHP Solution: $U_j=\left(t_j,+,H_{2_j}\right)H_{3_j}{v}_{j}PS{K}_j=\left(t_j,+,H_{2_j}\right)H_{3_j}{v}_j{H}_{1_j}r{W}_j,r{W}_j=\frac{U_j}{\left(t_j,+,H_{2_j}\right)H_{3_j}{v}_j{H}_{1_j}}=abX$

Probabilistic Analysis: To solve the CDHP successfully by Opponent, We assume that Eve I can forge signature within time period t with the advantage of $ϵ$. and it never repeats the queries for same input. The probability of success of Opponent to solve CDHP is $\frac{1}{Q_{h_1}}$. Opponent can able to solve the CDHP problem with probability $\frac{ϵ}{Q_{h_1}}$ and it creates a contradiction with the hardness of CDHP. As a result, the proposed scheme is unforgeable against eve Eve I. $\square$

Theorem 2

The proposed scheme is unforgeable against Eve II where Eve II is allowed to run the queries in the random oracle model under the assumption that DDHP is intractable.

Proof

On receiving $\left(a,X,,,b,X,,,Y\right)$, the opponent has to determine the value of $Y=abX$. System master secret key and system parameters are generated by the opponent. The generated vars and master secret key sends to the Eve II. Eve II can execute the polynomial time oracle queries listed in Table 4.

Table 4. Queries run by Eve II

Queries	Eve II	Opponent
$Q_{h_1}$	Sends a request $Q_{h_1}$ on $I{D}_k$	Prepares the $Lis{t}_1$ of tuple $\left(I,D_k,,,W_k\right)$ If $I{D}_k$ is on list 1, returns $W_k$ from $Lis{t}_1$. Else, execute the following steps: If $I{D}_k$ is same as $I{D}^{\ast }$, then assign $W_k$ with aX and returns $W_k$ to Eve II and adds tuple $\left(I,D_k,,,W_k\right)$ to $Lis{t}_1$. If $I{D}_k$ is not same as $I{D}^{\ast }$, then assigns $u_{H_1}X$ with $h_1\left(I,D_k\right)$ where $u_{H_1}$ is randomly chosen from $z_p^{\ast }$ and returns $u_{H_1}X$ to Eve I and adds tuple $\left(I,D_k,,,U_{H_1},X\right)$ to $Lis{t}_1$
$Q_{h_2}$	Sends a request $Q_{h_2}$ on $\left(I,D_k,,,V_k,,,D_k,,,O_k\right)$	Prepares the $Lis{t}_1$ of tuple $\left(I,D_k,,,V_k,,,D_k,,,O_k,,,H_{1_k}\right)$ If $\left(I,D_k,,,V_k,,,D_k,,,O_k,,,H_{1_k}\right)$ is on $Lis{t}_2$, returns $H_{1_k}$ from $Lis{t}_2$. Else, assigns $H_{1_k}$ with $h_2\left(I,D_k,,,V_k,,,D_k,,,O_k\right)$ where $H_{1_k}$ is randomly selected from $z_p^{\ast }$. and returns $H_{1_k}$ and adds the tuple $\left(I,D_k,,,V_k,,,D_k,,,O_k,,,H_{1_k}\right)$ to the $Lis{t}_2$
$Q_{h_3}$	Sends a request $Q_{h_3}$ on $\left(m_k,,,P,S,K_k,,,P,K_k,,,t_k\right)$	Prepares the $Lis{t}_3$ of tuple $\left(m_k,,,P,S,K_k,,,P,K_k,,,t_k,,,H_{2_k}\right)$ If $\left(m_k,,,P,S,K_k,,,P,K_k,,,t_k,,,H_{2_k}\right)$ is on $Lis{t}_3$, returns $H_{2_k}$ from $Lis{t}_3$. Else, $H_{2_k}$ belongs to $z_p^{\ast }$ and assign $H_{2_k}$ with $h_3\left(m_k,∥P,S,K_k∥,P,K_k,∥t_k∥\right)$ and returns $H_{2_k}$ to Eve I and adds $\left(m_k,,,P,S,K_k,,,P,K_k,,,t_k,,,H_{2_k},]\right)$tuple to the $Lis{t}_3$
$Q_{h_4}$	Sends a request $Q_{h_4}$ on $\left(m_j,,,T_1,,,.,.,.,,,T_{j-1},,,T_{j+1},,,.,.,.,,,T_n\right)$	Prepares a $Q_{h_4}$ of tuple $Q_{h_4}$ on $\left(m_j,,,T_1,,,.,.,.,,,T_{j-1},,,T_{j+1},,,.,.,.,,,T_n,,,H_{T_j}\right)$ If $Q_{h_4}$ on $\left(m_j,,,T_1,,,.,.,.,,,T_{j-1},,,T_{j+1},,,.,.,.,,,T_n,,,H_{T_j}\right)$ is on $Lis{t}_4$, returns $H_{T_j}$ from $Lis{t}_4$. Else, assigns $H_{T_j}$ with ${\sum }_{j=1}^n{h}_4\left(m_j,||,T_k\right),\forall 1,2,..,n-\{j\}$ where $H_{T_j}$ is randomly chosen from $z_p^{\ast }$ and returns $H_{T_j}$ and adds to the $Lis{t}_4$
$Q_{h_5}$	Sends a request $Q_{h_4}$ on $\left(m_j,,,L_{\mathit{ID}},,,L_{\mathit{PK}},,,H_{T_j},,,H_{3_j}\right)$	Prepares a $Lis{t}_5$ of tuple $\left(m_j,,,L_{\mathit{ID}},,,L_{\mathit{PK}},,,H_{T_j},,,H_{3_j}\right)$. If $\left(m_j,,,L_{\mathit{ID}},,,L_{\mathit{PK}},,,H_{T_j},,,H_{3_j}\right)$ is on $Lis{t}_5$, returns $H_{3_j}$ from $Lis{t}_5$. Else, choose $H_{3_j}$ belongs to $z_p^{\ast }$ assigns $H_{3_j}$ with $h_5\left(m_k,||,L_{\mathit{ID}},||,L_{\mathit{PK}},||,H_{T_j}\right)$. And returns $H_{3_j}$ and insert the tuple to the $Lis{t}_5$
$Q_1$	Sends a request $Q_1$ on $I{D}_k$	Prepares $Lis{t}_T$ of tuple $\left(I,D_k,,,v_k,,,V_k,,,D_k,,,P,S,K_k\right)$ If $Lis{t}_T$ contains $\left(I,D_k,,,v_k,,,V_k,,,D_k,,,,\ast \right)$, returns $\left(v_k,,,D_k\right)$ Else, If $I{D}_k$is same as $I{D}_{\ast }$, assign $V_k=D,D_k=bX$ returns $\left(V_k,,,D_k\right)$ to Eve II and adds $\left(I,D_k,,,v_k,,,V_k,,,D_k,,\ast ]\right)$ to $lis{t}_T$. If $I{D}_k$ is not same as $I{D}_{\ast }$, choose $v_k$ belongs to $z_p^{\ast }$ and executes $w_{H_1}$ to get $W_k$ from $Lis{t}_1$ and returns $\left(v_k,W_k,,,v_k,X\right)$ insert$\left(I,D_k,,,v_k,,,V_k,,,D_k,,,,\ast \right)$ to the $Lis{t}_T$
$Q_4$	Sends a request $Q_4$on $I{D}_k$	If $I{D}_k$is same as $I{d}^{\ast }$, Game II fails. If $I{D}_k$ is not same as the $I{d}^{\ast }$, if $\left(I,D_k,,,v_k,,,V_k,,,D_k,,,P,S,K_k\right)$ is in $Lis{t}_T$, then returns the $\left(V_k,,,P,S,K_k\right)$ Else, get $W_k$ and $H_{1_k}$ from $Lis{t}_1,Lis{t}_2$ respectively. Assigns $PS{K}_k$ with $r{H}_{1_k}{W}_k$, returns $\left(v_k,,,P,S,K_k\right)$ and insert $\left(I,D_k,,,,\ast ,,,,\ast ,,,,\ast ,P,S,K_k\right)$ to $Lis{t}_T$
$Q_5$	Selects a set of ring members $L_{\mathit{ID}}$ and their corresponding public keys to generate a signature, Sends request $Q_5$ with message	Selects a signer randomly $j\in \left\{1,,,2,,,.,.,.,,,n\right\}$ and signer chooses $t_j$ belongs to ${Z_p}^{\ast }$ calculate $H_{2_j}$ belongs to ${Z_p}^{\ast }$,$H_{2_j}=h_3\left(m_j,∥P,S,K_j∥,P,K_j,||,t_j\right)$ using $Lis{t}_3$ Calculate $T_j=H_{1_j}\left(t_j,+,H_{2_j}\right)V_j$ belongs to $G_{\mathit{add}}$. And user $Lis{t}_2$ for $H_{1_j}$ for all $P{K}_k$ belongs to $L_{\mathit{PK}}$, chooses $T_k$ belongs to $G_{\mathit{add}}$, for all k belongs to $\left(1,,,2,,,.,.,.,,,n\right)\backslash \left\{j\right\}$, computes $H_{T_j}$ belongs to ${Z_p}^{\ast }$, where ${Z_p}^{\ast }$ and find $H_{T_j}$ in $Lis{t}_4$. Calculate $H_{3_j}$ belongs to ${Z_p}^{\ast }$ where $H_{3_j}=h_5\left(m_j,∥L_{\mathit{ID}}∥,L_{\mathit{PK}},||,H_{T_j}\right)$, for $H_{3_j}$ finds in $Lis{t}_5$. C assigns $U_j=\left(v_j,+,H_{2_j}\right)H_{3_j}r{H}_{1_j}{V}_j$ belongs to $G_{\mathit{add}}$. Returns $\alpha =\left(T_j,,,U_j,,,H_{3_j}\right)$ on $m_j$

Forgery: If the following conditions met, then the Eve II can successfully forge the signature:

• Eve II cannot run the $Q_4$ to extract the private key.

• Eve II do not execute the $Q_5$ to get the forged signature.

• A forged signature is valid if $e\left(U_j,,,X\right)=e\left(H_{3_j},,,T_j,,,T_{\mathit{pbk}}\right))$.

DDHP solution: $W_j=aXand{D}_j=V_{j}X=bX,V_j=v_j{W}_j=abX,D=V_k$ Hence, $Y=abX$

Probabilistic Analysis: To solve the DDHP successfully by Opponent, we assume that Eve II can forge a signature with in time period t and the advantage of $ϵ$. Eve II never repeats $Q_{H_i}$ for same input. The probability of success of Opponent to solve DDHP is $\frac{1}{Q_1}$. Opponent can able to solve the DDHP problem with probability of atleast $\frac{ϵ}{Q_1}$. So, it creates a contradiction with the hardness of DDHP. As a result, the proposed scheme is unforgeable against Eve II. $\square$

Theorem 3

The proposed scheme provides unconditional anonymity.

Proof

In the proposed scheme, all the parameters for any message, receiver and ring member are independent and uniformly distributed. No Eve can identify the actual signer even if it has the unbounded computational power and all the private keys of the member with a non negligible probability. $\square$

Formal Security Verification Using AVISPA

We use the AVISPA tool to stimulate and analyze the proposed protocol. AVISPA (Automated Validation of Internet Security Protocols) is a web-based push and software tool for automatic verification and analysis of different security protocols. To analyze the protocol in the AVISPA, we specify the protocol in the HLPSL (High-Level Protocol Specification Language) with an extension of.hlpsl. HLPSL is a Language based on roles: basic roles and composition of basic roles. Each role is defined by initial parameters like send and receive channel, hash functions and etc. The tool comes with the four back ends: OFMC(On the Fly Model-Checker), Cl-AtSe(Constraint-Logic-based Attack Searcher), SATMC(SAT-based Model-Checker) and TA4SP(Tree Automata-based Protocol Analyzer) to verify the security protocols.

The procedure for running the AVISPA code is as followed: first write the protocol in HLPSL and then run the code with AVISPA, and AVISPA uses the HLPSL2IF translator to convert the code from HLPSL to IF format. And then choose one of the back ends to get the OF (Output Format) as shown in Fig. 3.

[See PDF for image]

Fig. 3

AVISPA

We have defined the three basic roles: one for TRA shown in Fig. 4, second for RSU shown in Fig. 5, third for OBU shown in Fig. 6, and then role of session and environment is defined which is shown in Fig. 7 in which we have defined the intruder knowledge and goals. We use the Dolev Yao threat model and OFMC for verifying the security of the proposed scheme. The output for the proposed scheme is shown in Fig. 8.

[See PDF for image]

Fig. 4

Role of TRA defined in proposed.hlpsl

[See PDF for image]

Fig. 5

Role of RSU defined in proposed.hlpsl

[See PDF for image]

Fig. 6

Role of OBU defined in proposed.hlpsl

[See PDF for image]

Fig. 7

Role of session and environment in defined proposed.hlpsl

[See PDF for image]

Fig. 8

Simulation result of the proposed scheme

Performance Evaluation

In this section, we evaluate the performance of the proposed scheme by calculating the computational and communication costs of the proposed scheme along with the existing schemes [32, 34, 35–36].

Computational Cost

The computational cost is defined as the total time taken by the different cryptographic operations in the three phases: Signature, Individual Verification and Batch Verification. In Table 5, we present the notations of different cryptographic operations. Table 6 shows the execution times for the different cryptographic operations. The proposed scheme uses two scalar point multiplication to generate the signature. The computational cost for the signature is $T_{\mathit{signature}}=2\times T_s=2\times 0.318=0.636ms.$ For verifying individually, the computation involves two bilinear pairing operation and one elliptic point scalar multiplication, so the total cost is $T_{\mathit{individualverify}}=2\times T_p+T_s=2\times 2.468+0.318=5.254ms$. For reducing the computational overhead in the individual verification, the concept of batch verification was introduced. The computational cost of batch verification is $T_{\mathit{batchverify}}=2\times T_p+n\times T_s=0.318n+4.936ms$. The computational cost of the proposed scheme and the existing schemes [32, 34, 35–36] is calculated in Table 7 and shown in Fig. 9. Table 8 shows that the computational cost involved in the Signature phase of our scheme and the existing schemes [32, 34, 35–36] are 0.636 ms, 13.7476 ms, 3.4198 ms, 17.3588 ms, 6.838 ms, respectively. The computational cost required by the proposed and the existing schemes [32, 34, 35–36] for verifying the individual message are 5.254 ms, 10.1328 ms, 13.5526 ms, 18.748 ms and 10.1328 ms, respectively. The computational cost involved in batch verification by the proposed scheme and the existing schemes [32, 34, 35–36] are 8.116 ms, 25.548 ms, 59.7136 ms, 73.819 ms and 10.1508 ms, respectively. From Fig. 9, it is clearly seen that our scheme has less computational cost than that of the existing schemes [32, 34, 35–36].

Table 5. Operations with their notations

Notations	Definition
N	Number of members in ring
$T_p$	Bilinear pairing operation
$T_h$	Hash function
$T_s$	Elliptic scalar point multiplication
$T_a$	Point addition
$T_e$	Exponent operations in G1
$T_i$	Modular inversion

Table 6. Operations with time in milliseconds

Cryptography operations	Execution time (ms)
$T_p$	2.4
$T_h$	0.334
$T_s$	0.318
$T_a$	0.001
$T_e$	0.311
$T_i$	0.09

Table 7. Computational cost comparison

Scheme	Signature (ms)	Individual verification (ms)	Batch verification (ms)
Liu and Wang [36]	13.7476	10.1328	1.7126n+8.422
Liu et al. [34]	3.4198	13.5526	5.1288n+8.4256
Wang and Yao [35]	17.3588	18.748	6.1186n+12.633
Bouakkaz et al. [32]	6.838	10.1328	0.0018n+10.1328
Proposed scheme	0.636	5.254	0.318n+4.936

[See PDF for image]

Fig. 9

Computational cost comparison

Communication Cost

The communication cost is defined as the total number of bytes transferred in the signature phase. We take the size of $G_{\mathit{add}}$ as 128 bytes and the hash function as 20 bytes to calculate the communication cost of our scheme and the existing schemes [32, 34, 35–36]. The proposed scheme generates the signature ${\sigma }_j=\left(H_{T_j},,,T_j,,,U_j\right)$ on the message $m_k$ using the certificateless-ring signature. The length of the signature is $2\times 128+20=276$ bytes. The communication cost of our scheme and the existing scheme is calculated in Table 8 and presented in Fig. 10. Table 8 shows that the communication cost of our scheme and the existing schemes [32, 34, 35–36] are 276 bytes, 408 bytes, 404 bytes, 516 bytes, 408 bytes, respectively. It is clear from Fig. 10 that our scheme has the least communication cost.

Table 8. Communication cost comparison

Scheme	Signature (bytes)
Liu and Wang [36]	408
Liu et al. [34]	404
Wang and Yao [35]	516
Bouakkaz et al. [32]	408
Proposed Scheme	276

[See PDF for image]

Fig. 10

Communication cost comparison

Conclusion

To protect the privacy of driver and prevent the malicious entities from modifying the message over the VANET, we have designed a ring signature scheme in this paper. The proposed scheme uses the certificateless ring signature for signature generation and then it verifies the multiple messages using the batch verification to lessen the computational overhead. The performance analysis clearly indicated that the proposed scheme has the least computational and communication cost as compared to the existing schemes. We have also done the security analysis of the scheme against the unforgeability and anonymity in the detail using the RoR and AVISPA tool. The future scope and applicability of a bilinear mapping based ring signature scheme with batch verification can be broad and impactful, especially in the field of cryptography, privacy-preserving technologies, and secure communication. This scheme finds potential applications in blockchain networks, where privacy is paramount, as well as in secure communication systems, such as Vehicular Ad Hoc Networks (VANETs) or Internet of Things (IoT) environments. As decentralized technologies continue to evolve, the bilinear mapping-based ring signature scheme with batch verification could play a crucial role in safeguarding user identities and ensuring the integrity of communications across various domains.

Author Contributions

Mr. Lalit wrote this manuscript and Dr. Devender Kumar reviewed it and gave his valuable suggestions to improve its quality.

Funding

No external funding.

Declarations

Conflict of interest

Authors have no conflicts of interest.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

References

1. Zear, A., Singh, P.K., & Singh, Y. (2016). Intelligent transport system: A progressive review. Indian Journal of Science and Technology.

2. Ali, I; Hassan, A; Li, F. Authentication and privacy schemes for vehicular ad hoc networks (vanets): A survey. Vehicular Communications; 2019; [DOI: https://dx.doi.org/10.1016/j.vehcom.2019.02.002]

3. Engoulou, RG; Bellaïche, M; Pierre, S; Quintero, A. Vanet security surveys. Computer Communications; 2014; 44, pp. 1-13. [DOI: https://dx.doi.org/10.1016/j.comcom.2014.02.020]

4. Guo, J., Baugh, J.P., & Wang, S. (2007). A group signature based secure and privacy-preserving vehicular communication framework. In: 2007 Mobile Networking for Vehicular Environments, pp. 103–108. https://doi.org/10.1109/MOVE.2007.4300813.

5. Wasef, A., & Shen, X. (2010). Efficient group signature scheme supporting batch verification for securing vehicular networks. In: 2010 IEEE International Conference on Communications, pp. 1– 5. https://doi.org/10.1109/ICC.2010.5502136.

6. Zhang, L; Wu, Q; Solanas, A; Domingo-Ferrer, J. A scalable robust authentication protocol for secure vehicular communications. IEEE Transactions on Vehicular Technology; 2010; 59, 4 pp. 1606-1617. [DOI: https://dx.doi.org/10.1109/TVT.2009.2038222]

7. Vijayakumar, P., Azees, M., & Deborah, L.J. (2015). Cpav: Computationally efficient privacy preserving anonymous authentication scheme for vehicular ad hoc networks. 2015 IEEE 2nd International Conference on Cyber Security and Cloud Computing, 62–67.

8. Raya, M., & Hubaux, J.-P. (2005). The security of vehicular ad hoc networks. In: Proceedings of the 3rd ACM Workshop on Security of Ad Hoc and Sensor Networks. SASN ’05, pp. 11– 21. Association for Computing Machinery, New York, NY, USA. https://doi.org/10.1145/1102219.1102223 .

9. Azees, M; Vijayakumar, P; Deboarh, LJ. Eaap: Efficient anonymous authentication with conditional privacy-preserving scheme for vehicular ad hoc networks. Transactions on Intelligent Transportation Systems; 2017; 18, 9 pp. 2467-2476. [DOI: https://dx.doi.org/10.1109/TITS.2016.2634623]

10. Ullmann, M., Wieschebrink, C., & Kügler, D. (2015). Public key infrastructure and crypto agility concept for intelligent transportation systems.

11. Kamat, P., Baliga, A., & Trappe, W. (2006). An identity-based security framework for vanets. VANET ’06, pp. 94– 95. Association for Computing Machinery, New York, NY, USA. https://doi.org/10.1145/1161064.1161083 .

12. Hakuta, K; Katoh, Y; Sato, H; Takagi, T. Batch verification suitable for efficiently verifying a limited number of signatures. Information Security and Cryptology; 2012; 7839, pp. 425-440. [DOI: https://dx.doi.org/10.1007/978-3-642-37682-5_30]

13. Lu, H; Li, J; Guizani, M. A novel id-based authentication framework with adaptive privacy preservation for vanets. Computing, Communications and Applications Conference; 2012; [DOI: https://dx.doi.org/10.1109/ComComAp.2012.6154869]

14. Lo, NW; Tsai, J-L. An efficient conditional privacy-preserving authentication scheme for vehicular sensor networks without pairings. IEEE Transactions on Intelligent Transportation Systems; 2016; 17, pp. 1319-1328. [DOI: https://dx.doi.org/10.1109/TITS.2015.2502322]

15. Cui, J; Zhang, J; Zhong, H; Xu, Y. Spacf: A secure privacy-preserving authentication scheme for vanet with cuckoo filter. IEEE Transactions on Vehicular Technology; 2017; 66, 11 pp. 10283-10295. [DOI: https://dx.doi.org/10.1109/TVT.2017.2718101]

16. Wang, S; Yao, N. Liap: A local identity-based anonymous message authentication protocol in vanets. Computer Communications.; 2017; 112, pp. 154-164. [DOI: https://dx.doi.org/10.1016/j.comcom.2017.09.005]

17. Mamun, M.S.I., Miyaji, A.: An optimized signature verification system for vehicle ad hoc network. In: 2012 8th International Conference on Wireless Communications, Networking and Mobile Computing, pp. 1– 8 (2012). https://doi.org/10.1109/WiCOM.2012.6478425.

18. Yu, R; Kang, J; Huang, X; Xie, S; Zhang, Y; Gjessing, S. Mixgroup: Accumulative pseudonym exchanging for location privacy enhancement in vehicular social networks. IEEE Transactions on Dependable and Secure Computing; 2016; 13, 1 pp. 93-105. [DOI: https://dx.doi.org/10.1109/TDSC.2015.2399291]

19. Hasrouny, H., Bassil, C., Samhat, A.E., & Laouiti, A. (2015). Group-based authentication in v2v communications. 2015 Fifth International Conference on Digital Information and Communication Technology and its Applications (DICTAP), 173–177.

20. Shao, J; Lin, X; Lu, R; Zuo, C. A threshold anonymous authentication protocol for vanets. IEEE Transactions on Vehicular Technology; 2016; 65, 3 pp. 1711-1720. [DOI: https://dx.doi.org/10.1109/TVT.2015.2405853]

21. Rajput, U; Abbas, F; Eun, H; Oh, H. A hybrid approach for efficient privacy preserving authentication in vanet. IEEE Access; 2017; [DOI: https://dx.doi.org/10.1109/ACCESS.2017.2717999]

22. Chaum, D., & Heyst, E. (1991). Group signatures. In: Advances in Cryptology - EUROCRYPT ’91, Workshop on the Theory and Application of of Cryptographic Techniques, Brighton, UK, April 8-11, 1991, Proceedings. Lecture Notes in Computer Science, vol. 547, pp. 257– 265. Springer. https://doi.org/10.1007/3-540-46416-6_22

23. Meiklejohn, S. (2011). An exploration of group and ring signatures. UCSD Research Exam.

24. Chaurasia, BK; Verma, S. Conditional Privacy through Ring Signature in Vehicular Ad-Hoc Networks; 2011; Berlin, Heidelberg, Springer: [DOI: https://dx.doi.org/10.1007/978-3-642-22619-9_8]

25. Han, Y; Xue, N-N; Wang, B-Y; Zhang, Q; Liu, C-L; Zhang, W-S. Improved dual-protected ring signature for security and privacy of vehicular communications in vehicular ad-hoc networks. IEEE Access; 2018; 6, pp. 20209-20220. [DOI: https://dx.doi.org/10.1109/ACCESS.2018.2822806]

26. Liu, J; Yu, Y; Jia, J; Wang, S; Peiru, F; Wang, H; Zhang, H. Lattice-based double-preventing ring signature for security and privacy in vehicular ad-hoc networks. Tsinghua Science and Technology; 2019; 24, pp. 575-584. [DOI: https://dx.doi.org/10.26599/TST.2018.9010131]

27. Mundhe, P; Yadav, VK; Verma, S; Venkatesan, S. Efficient lattice-based ring signature for message authentication in vanets. IEEE Systems Journal; 2020; 14, 4 pp. 5463-5474. [DOI: https://dx.doi.org/10.1109/JSYST.2020.2980297]

28. Amir, NAS; Othman, WAM; Wong, KB. Securing an authenticated privacy preserving protocol in a group signature scheme based on a group ring. Mathematics; 2023; 11, 18 3918. [DOI: https://dx.doi.org/10.3390/math11183918]

29. Iqbal, A; Zubair, M; Khan, MA; Ullah, I; Ur-Rehman, G; Shvetsov, AV; Noor, F. An efficient and secure certificateless aggregate signature scheme for vehicular ad hoc networks. Future Internet; 2023; 15, 8 266. [DOI: https://dx.doi.org/10.3390/fi15080266]

30. Tian, M; Zhang, Y; Zhu, Y; Wang, L; Xiang, Y. Divrs: Data integrity verification based on ring signature in cloud storage. Computers and Security; 2023; 124, [DOI: https://dx.doi.org/10.1016/j.cose.2022.103002] 103002.

31. Rivest, RL; Shamir, A; Tauman, Y. Boyd, C. How to leak a secret. Advances in Cryptology – ASIACRYPT 2001; 2001; Berlin, Heidelberg, Springer: pp. 552-565. [DOI: https://dx.doi.org/10.1007/3-540-45682-1_32]

32. Bouakkaz, S; Semchedine, F. A certificateless ring signature scheme with batch verification for applications in vanet. Journal of Information Security and Applications; 2020; 55, [DOI: https://dx.doi.org/10.1016/j.jisa.2020.102669] 102669.

33. Tzeng, S-F; Horng, S-J; Li, T; Wang, X; Huang, P-H; Khan, MK. Enhancing security and privacy for identity-based batch verification scheme in vanets. IEEE Transactions on Vehicular Technology; 2017; 66, 4 pp. 3235-3248. [DOI: https://dx.doi.org/10.1109/TVT.2015.2406877]

34. Liu, J; Yu, Y; Zhao, Y; Jia, J; Wang, S. Au, MH; Yiu, SM; Li, J; Luo, X; Wang, C; Castiglione, A; Kluczniak, K. An efficient privacy preserving batch authentication scheme with deterable function for vanets. Network and System Security; 2018; Cham, Springer: pp. 288-303. [DOI: https://dx.doi.org/10.1007/978-3-030-02744-5_22]

35. Wang, S; Yao, N. Liap: A local identity-based anonymous message authentication protocol in vanets. Computer Communications; 2017; 112, pp. 154-164. [DOI: https://dx.doi.org/10.1016/j.comcom.2017.09.005]

36. Liu, F., & Wang, Q. (2019). Ibrs: An efficient identity-based batch verification scheme for vanets based on ring signature.