# A Certificateless Anonymous Cross-Domain Authentication Scheme Assisted by Blockchain for Internet of Vehicles

Authors: Xueyan Liu; Li Wang; Linpeng Li; Xiaoyan Zhang; Shufen Niu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

With the development of the Internet of Things and the increase of intelligent vehicles, the Internet of Vehicles (IoVs) have been widely used in the information communication such as road and traffic conditions. However, heavy overhead of certificate management, high computing load of identity and message authentication, and the privacy disclosure of vehicle nodes have hindered the development of intelligent transportation. In this study, we propose a certificateless cross-domain anonymous authentication scheme based on blockchain for IoVs. Specifically, the vehicle identity information is authenticated by the first roadside unit (RSU), and transactions are recorded permanently and immutably in the blockchain to reduce the repeated authentication load of other RSUs. To achieve conditional privacy, the trusted authority (TA) generates pseudonyms for each registered user. The relation between the pseudonym and the real identity is kept confidential by the TA and only can only be revealed in case of disputes. Meanwhile, the private key of the vehicle is generated anonymously on the basis of certificateless technology and the pairing-free signature verification. Correctness and security proof demonstrate that our proposed scheme is provably secure and can withstand different types of attacks. A simulation environment has been built to test the packet loss rate and delay of messages in the network. Results show that the proposed scheme is more efficient than the related schemes.


---

## Body

## 1. Introduction

With the rapid development and maturity of the Internet of Things, the Internet of Vehicles (IoVs), as the basic technology of intelligent transportation system, have received extensive attention and research from academia and the industry. IoVs provide a safer driving environment by allowing vehicles to communicate with one another or with roadside infrastructure to improve road safety, driving conditions, and comfort for road users.IoVs are formed by the combination of vehicles and intelligent network equipment, which is composed of a high-speed mobile wireless ad hoc networks. Figure1 shows the typical IoV environment, including trusted authority (TA), roadside units (RSUs), vehicles, and the Internet. The communication is carried out by vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I), in which valuable driving information and exchange traffic-related information are shared to improve driving and passenger safety [1].Figure 1
IoV network model.IoVs bring safety and provide various entertainment information services for drivers and passengers. However, at the same time, it will inevitably generate massive data and face many information security challenges. Firstly, given the openness and fragility of wireless networks, the messages transmitted in IoV system are vulnerable to various attacks, such as modification or impersonation. Moreover, the privacy of vehicles has also been greatly threatened, such as exposing user behaviour tracks. Secondly, the vehicles in IoVs move at high speed, and the communication bandwidth is minimal, which requires that vehicle identity and message authentication in IoVs to have lower computation and communication overhead. In addition, tens of thousands of vehicles and their onboard devices will realise the sharing and interaction of vehicle or driving data through the IoVs. This exchange results in massive data, which will inevitably cause high communication overhead and reduce the performance of each entity in the IoV system. Of course, it also leads to the increase of packet loss rate.To solve the traffic-related message security problems in IoVs, researchers propose authentication schemes based on public key infrastructure (PKI), identity-based cryptography (IBC), and certificateless cryptography (CLC). In the schemes based on PKI, to manage users’ public keys, a certification authority must store many certificates. Therefore, the RSUs require sufficient computation and storage capacity to validate these certificates. To alleviate the certificate management problem caused by PKI, IBC is introduced into the IoVs. In identity-based authentication schemes, the public key derives from the user’s identity information, and the private key generator (PKG) has no certificate storage load. However, PKG can use the user’s private key to forge the user’s signature and thus cause a key escrow problem. To solve this problem, Al-Riyami and Paterson proposed CLC in 2003 [2]. Then, the researchers also proposed the corresponding CLC-based authentication schemes.Some certificateless signature schemes use bilinear pairing operation with a large amount of computation; hence, they are unsuitable for IoV environment with low delay. Therefore, a signature scheme with low delay and minimal computation is urgently needed to improve the performance of all aspects in IoVs.


### 1.1. Motivation and Contributions

Zheng et al. [3] proposed a traceable distributed IoV system framework based on blockchain technology by adopting the authentication scheme between vehicles and RSUs. However, there are two problems in the authentication stage of this scheme:Problem 1.
When a vehicle reaches the range of each RSU on the road, it sends an authentication request to the RSU containing the pseudonym and the corresponding public key to achieve identity authentication by each RSU. This frequent and repeated operation cannot meet the low communication requirements and low computation requirements in the IoV system, which increases the system burden.Problem 2.
After determining the authenticity of the vehicle identity, the RSU initiates the random integer negotiation process and sends the vehicle a random integer encrypted by the vehicle’s public key and stored in the on-board unit (OBU). However, this phase only considers the communication between the vehicle and the first RSU in a particular area. When the vehicle enters the next RSU area, this process will be repeated and the storage load of OBU will be increased.Therefore, on the basis of the work of Zheng et al. [3], we propose a certificateless anonymous cross-domain authentication scheme assisted by blockchain, and its main contributions are as follows:
(1)
To preserve the privacy of vehicles, the TA distributes pseudonyms to each vehicle for the whole communication process. The key generation centre (KGC) generates partial private keys of the vehicle, and the vehicle combines partial private keys with its secret values to generate the actual private keys to solve the key escrow problem and void heavy certificate verification load(2)
To overcome Problems1 and 2, the vehicle sends the verification information calculated by itself and the pseudonym assigned by the TA to the first RSU, and only the first RSU negotiates a random integer with the vehicle. Then, the RSU packages the negotiated random integer and other contents on the blockchain built by the RSUs to realise cross-domain authentication and reduce the computational overhead caused by repeated signature authentication(3)
The homomorphic signature without bilinear pairing is adopted to improve the efficiency of RSUs verifying messages(4)
When a malicious event occurs, according to the openness and transparency of the blockchain, other vehicles can report the malicious event to RSUs. The RSUs will present the pseudoidentity of the malicious vehicle to TA. Finally, the TA traces the true identity from the user list, revokes the user, and updates the user list accordingly


### 1.2. Organization

This research is organized as follows. Section2 presents the existing related work. Section 3 shows the background knowledge and describes the system model. Section 4 shows the basic construction. Security proof and performance evaluation will be given in Section 5 and Section 6. The last section makes a conclusion.


## 1.1. Motivation and Contributions

Zheng et al. [3] proposed a traceable distributed IoV system framework based on blockchain technology by adopting the authentication scheme between vehicles and RSUs. However, there are two problems in the authentication stage of this scheme:Problem 1.
When a vehicle reaches the range of each RSU on the road, it sends an authentication request to the RSU containing the pseudonym and the corresponding public key to achieve identity authentication by each RSU. This frequent and repeated operation cannot meet the low communication requirements and low computation requirements in the IoV system, which increases the system burden.Problem 2.
After determining the authenticity of the vehicle identity, the RSU initiates the random integer negotiation process and sends the vehicle a random integer encrypted by the vehicle’s public key and stored in the on-board unit (OBU). However, this phase only considers the communication between the vehicle and the first RSU in a particular area. When the vehicle enters the next RSU area, this process will be repeated and the storage load of OBU will be increased.Therefore, on the basis of the work of Zheng et al. [3], we propose a certificateless anonymous cross-domain authentication scheme assisted by blockchain, and its main contributions are as follows:
(1)
To preserve the privacy of vehicles, the TA distributes pseudonyms to each vehicle for the whole communication process. The key generation centre (KGC) generates partial private keys of the vehicle, and the vehicle combines partial private keys with its secret values to generate the actual private keys to solve the key escrow problem and void heavy certificate verification load(2)
To overcome Problems1 and 2, the vehicle sends the verification information calculated by itself and the pseudonym assigned by the TA to the first RSU, and only the first RSU negotiates a random integer with the vehicle. Then, the RSU packages the negotiated random integer and other contents on the blockchain built by the RSUs to realise cross-domain authentication and reduce the computational overhead caused by repeated signature authentication(3)
The homomorphic signature without bilinear pairing is adopted to improve the efficiency of RSUs verifying messages(4)
When a malicious event occurs, according to the openness and transparency of the blockchain, other vehicles can report the malicious event to RSUs. The RSUs will present the pseudoidentity of the malicious vehicle to TA. Finally, the TA traces the true identity from the user list, revokes the user, and updates the user list accordingly


## 1.2. Organization

This research is organized as follows. Section2 presents the existing related work. Section 3 shows the background knowledge and describes the system model. Section 4 shows the basic construction. Security proof and performance evaluation will be given in Section 5 and Section 6. The last section makes a conclusion.


## 2. Related Works

Anonymous identity authentication is a typical method to preserve vehicle privacy in IoVs. Many researchers have studied and proposed privacy preservation authentication schemes in IoVs based on the basic idea of using digital pseudonyms as a unique identifier to authenticate without any personal identity information. Firstly, in PKI-based scheme, certificate authorities need to generate multiple anonymous public-private key pairs and certificates for each OBU and prestore them in tamper-proof devices (TPD) [4, 5]. Therefore, it is difficult to manage and store a large number of public-private key pairs and related certificates, which also increases the complexity of maintenance and management.To solve the above problems, scholars have designed a variety of IBC-based schemes. IBC was first launched by Shamir in 1984 [6]. It sets the entity’s digital identity as a public key, eliminating the need for the key infrastructure, and KGC uses the primary key to generate the entity’s private key. Although such schemes avoid PKI’s certificate management problems, they often need to carry out time-consuming pairing operations [7] and introduce key escrow problems. Song et al. proposed a batch authentication scheme using elliptic curve bilinear pairs and pointed out the existing security risks. By improving the program of Song et al. [8], an identity-based batch verification security scheme [9] with bilinear pairing-free is proposed. However, in these identity-based schemes, the main problem is that KGC uses its master key to generate a key for a vehicle entity. It cannot ensure nonrepudiation because KGC abuses the vehicle’s access ability to sign and decrypt any message, resulting in key escrow problems.To address these problems of key escrow and certificate management, Al-Riyami and Paterson introduced a certificateless-based mechanism in 2003 [2]. Yao et al. [10] proposed a certificateless anonymous authentication mechanism named CLMA. The mechanism applies the key exchange technology supporting password authentication based on ring fault-tolerant learning problems, which can provide mutual authentication when vehicles access vehicle cloud services through RSUs. Xu et al. [11] proposed a certificateless authentication protocol named SE-CLASA, which does not rely on a fully trusted third party; the signature scheme supports aggregation, which can resist information injection attacks. Malhi and Batra [12] proposed a new certificateless aggregate signature scheme for VANETs with constant pairing computations. However, vehicles need to be registered repeatedly in different regional transportation authority management areas, and the amount of registration calculation is relatively high. In 2018, Wang and Teng [13] proposed a verifiable and secure certificateless aggregate signature algorithm in VANETs. However, Yang et al. [14] pointed out that the study by Wang and Teng [13] was not secure and proposed an improved certificateless aggregate signature scheme. Zhao and Zhang [15] proposed an authenticable privacy preservation scheme based on certificateless ring signcryption, but this scheme used a time-consuming bilinear pairing operation. Hathal et al. [16] presented a certificateless and lightweight authentication scheme. In their work, they introduced authentication tokens to reduce the burden of certificate management. However, the authentication of each vehicle node requires the participation of TA, so a bottleneck problem arises.Yang et al. [17] proposed a method of using blockchain to protect the data privacy of IoVs. Although this method is also based on certificateless cryptography system to realise the signature and authentication of blockchain transactions, combined with edge computing devices, it proposed a fine-grained data access control method with an efficient partially hidden access strategy. Ali et al. [18] also proposed a certificateless signature scheme based on blockchain, but many bilinear pairings are used in both schemes to verify the signature and are unsuitable for IoV systems with low delay and computational complexity. Bagga et al. [19] proposed blockchain-based batch authentication protocol for Internet of Vehicles, in which vehicles and RSUs can be added dynamically. Unfortunately, at the registration stage of vehicles and RSUs, TA generates certificates for them and a certificate management problem arises. In addition, the real identity, pseudoidentity, certificate, and part of private key of the vehicle and RSU are all generated by TA, so the calculation pressure of TA is large. Subsequently, Ren et al. [20] proposed an efficient and privacy-preserving certificateless public key signature scheme based on the blockchain. Although their scheme added two blockchains to the structure to protect the identity privacy of vehicles, it did not describe the construction of the blockchain network.At present, many scholars have put forward a lot of other types of signature verification schemes, such as 6G-enabled VANETs [21] and anonymous signature-based authentication [22]. However, most of them have some problems, such as key management, high computational, and communicational costs. Consequently, we utilize the certificateless cryptosystem to solve the key escrow problem, and a pairing-free authentication method is used for efficiency consideration. Furthermore, we introduce blockchain technology to achieve transparency and nontamperability of transaction information and reduce duplicate certification load.


## 3. Preliminaries

In this section, we will present cryptographic materials, system models, adversary models, design objectives, and symbols.


### 3.1. Cryptography Materials

#### 3.1.1. Elliptic Curve

Suppose that the symbolE/Fp denotes an elliptic curve E over a prime finite field Fp, where p is a large prime number. The curve E is defined as follows:
(1)y2=x3+ax+bmodp.Such thata,b∈Fp and Δ=4a3+27b2modp≠0. The points on E/Fp and a point at infinity O construct a cyclic additive group:
(2)G=x,y:x,y∈Fp,Ex,y=0∪O.A scalar multiplication overE/Fp can be computed as follows [23]:
(3)tP=P+P+⋯+Pttimes,in which t∈Fp and P∈G.


#### 3.1.2. Elliptical Curve Discrete Logarithm Problem (ECDLP)

G is a finite cyclic group of prime order p defined on elliptic curve E, pP is the generator of group G. Suppose that there is a random point Q in group G, and solve s so that it satisfies Q=sP.


### 3.2. Certificateless Cryptosystem

The concept of certificateless encryption and signature was first proposed by Al-Riyami and Paterson, which solves the issue of key escrow in IBC. The basic idea of certificateless encryption and signature is that KGC generates a partial private key for the user. The user’s private key is jointly generated by the user and KGC. The user selects a secret value and combines it with the partial private key to generate the user’s full private key. KGC does not know the user’s complete private key, thus avoiding the problem of key escrow. The versatile definition of certificateless encryption and signature scheme consists of five algorithms, and the user public/secret key pair can be generated independently by the user even before obtaining the user partial key from the KGC [24]. Next, the definition of certificateless signature scheme will be presented:
(i)
Setup (master key generation): on input security parameter1λ, it generates a master public/secret key pair mpk,msk. The system parameter params is broadcasted to the other entities(ii)
PartialKeyGen (user partial key generation): on inputmsk and user identity ID, it generates a user partial key dID(iii)
UserKeyGen (user key generation): on inputmpk and user identity ID, it generates a user/private key pair pkID,xID(iv)
CL_Sign (signature generation): on input user private keyxID, user partial key dID, and message m, it generates a signature σ(v)
CL_Ver (signature verification): on inputmpk, user identity ID, user public key pkID, message m, and signature σ, it returns 1 or 0 for accept or reject, respectivelyCertificateless public key cryptography does not need certificate management and requires less load. Therefore, it is more suitable for mobile security applications with low broadband requirements and low energy consumption.


### 3.3. Blockchain

Blockchain originates from a paper published by Nakamoto in 2008 [25]. It is a distributed ledger on a peer-to-peer network, with each node storing and backing up complete ledger information. As shown in Figure 2, it is a data structure that connects the generated data blocks sequentially in chronological order, a decentralized shared ledger that cannot be tampered and forged. Blockchain is an effective technology to deal with vehicle management and data transmission. A reasonable construction of vehicle blockchain network framework can effectively solve many problems in IoVs, such as broadcast conflict, resource scheduling, and privacy preservation. Therefore, promoting the deep integration of blockchain technology and IoVs is the inevitable trend of IoV development.Figure 2
Blockchain structure.Each node user in the blockchain system can create a smart contract by publishing a transaction and use programming to set the smart contract as its own ownership transfer rules, transaction methods, and state transition functions. The blockchain verifies the correctness and integrity of the signature message data obtained by the RSUs through the deployed smart contract. When the data is correct, the smart contract is triggered to return the correct verification result. Otherwise, an error verification is returned.The distributed ledger is encrypted using a Merkle tree. In this paper, we have only covered chronological Merkle tree (CMT). As shown in Figure3, all transactions are hashed and stored chronologically in the CMT. Only the root hash is contained in the blockchain. In our proposed scenario, the transactions broadcast by RSUs are permanently recorded in the CMT, making the activities of each entity in the IoVs transparent and verifiable to the authorities.Figure 3
The structure of chronological Merkle tree.


### 3.4. System Model

Based on the framework of Zheng et al., we propose a certificateless anonymous cross-domain authentication system assisted by blockchain. Therefore, the entity is divided into five types: TA, KGC, cloud server (CS), RSUs, and vehicles (V). In the VANET system, the RSUs communicate with the TA through wired, while they communicate with the vehicles in its areas through wireless. This system has overcome two problems discussed in Section1, and at the same time, with the participation of blockchain technology, the framework has the characteristics of reliability and security, reducing the dependence of traditional solutions on TA or KGC. The IoV network model is shown in Figure 4.
(1)
TA: it is a fully trusted authority with unlimited computing resources and storage space. It is responsible for generating public/private keys and system parameters, registering vehicles, assigning pseudonyms to vehicles, and providing identity anonymity in vehicle communication(2)
KGC: it is not fully trusted entity. It is responsible for building and allocating partial private keys for anonymous vehicles in IoVs(3)
CS: it is responsible for managing the pseudonyms of vehicles issued by TA to facilitate identity verification and decentralized storage of transaction details including traffic information released by vehicles(4)
RSUs: it is deployed on the roadside as a bridge between TA, KGC, and vehicles. All RSUs establish a blockchain network as peer nodes. The blockchain network is in charge of the collective maintenance of blockchain data and broadcasting messages to vehicles along the road. The first RSU of each area verifies the identity of vehicles through V2I communication and submits the verification result, which is recorded on the chain after verification. After receiving the signature message, each RSU is responsible for verifying the signature of message. It will be recorded in the blockchain after verification(5)
Vehicle: the vehicle is equipped with an OBU to collect, calculate, and communicate traffic-related information. The device has its own clock to generate the correct timestamp. It is responsible for storing privacy information in the TPD of the vehicle and broadcasting information to the vehicle and nearby RSUs. In addition, vehicles can report malicious vehicles to RSUsFigure 4
System model of the proposed scheme.


### 3.5. Adversary Model

Assume that TA and RSUs are trusted entities. The vehicle is equipped with TPD, so the adversary cannot read, write, or delete the contents of the TPD. This scheme is using the ideas of certificateless cryptography. Therefore, the user’s public key has not been certificated. In the adversary model, adversaries have the right to replace the user’s public key with the illegal public key chosen by themselves. Moreover, since KGC knows the system master key, which can calculate all part of the user private key, but he cannot replace the user’s public key. Therefore, we divide the adversary types into two categories. The adversary of type I simulates a malicious user who can request and replace the public key in the system. The adversary of type II is an internal attacker who has access to the KGC’s master key and acts as a malicious but passive KGC.


### 3.6. Notations

The notations used in this paper are given in Table1.Table 1
Summary of notations.
NotationDescriptionViTheith vehicleGAn elliptic curve groupλSecurity parametersTA’s master secret keyuKGC’s master secret keyTpubTA’s public keyKpubKGC’s public keyhiA hash functionRIDiVi real identityPIDiVi pseudoidentity generated by TApskiVi partial private keyVpubiVi public keySKiVi private keyNRjAn integer negotiated between theVi and RSUjMiA message generated byViσiA signature onMi


### 3.7. Design Goals

According to IoVs and practical application requirements, the new scheme shall meet the following properties:(1)Message authentication: it ensures that the received message has not been modified or forged in the process of communication(2)Anonymity: in this scheme, only TA can obtain the real identity of the vehicle. Other vehicles in IoVs and adversary cannot identify the real identity of the sender by analyzing multiple messages sent by the same vehicle(3)Unlinkability: an attacker cannot find that multiple messages are from the same sender, and all pseudonyms should not reveal any connection between them(4)Traceability and revocation: TA can track out the real identity of the vehicle sending malicious messages and revoke the malicious vehicle(5)Unforgeability: any attacker cannot forge a legitimate signature(6)Resilience to other attacks: blockchain-assisted certificateless anonymous authentication schemes should be able to withstand various common attacks in IoVs (such as impersonation, modification, replay, and man-in-the-middle attacks)


## 3.1. Cryptography Materials

### 3.1.1. Elliptic Curve

Suppose that the symbolE/Fp denotes an elliptic curve E over a prime finite field Fp, where p is a large prime number. The curve E is defined as follows:
(1)y2=x3+ax+bmodp.Such thata,b∈Fp and Δ=4a3+27b2modp≠0. The points on E/Fp and a point at infinity O construct a cyclic additive group:
(2)G=x,y:x,y∈Fp,Ex,y=0∪O.A scalar multiplication overE/Fp can be computed as follows [23]:
(3)tP=P+P+⋯+Pttimes,in which t∈Fp and P∈G.


### 3.1.2. Elliptical Curve Discrete Logarithm Problem (ECDLP)

G is a finite cyclic group of prime order p defined on elliptic curve E, pP is the generator of group G. Suppose that there is a random point Q in group G, and solve s so that it satisfies Q=sP.


## 3.1.1. Elliptic Curve

Suppose that the symbolE/Fp denotes an elliptic curve E over a prime finite field Fp, where p is a large prime number. The curve E is defined as follows:
(1)y2=x3+ax+bmodp.Such thata,b∈Fp and Δ=4a3+27b2modp≠0. The points on E/Fp and a point at infinity O construct a cyclic additive group:
(2)G=x,y:x,y∈Fp,Ex,y=0∪O.A scalar multiplication overE/Fp can be computed as follows [23]:
(3)tP=P+P+⋯+Pttimes,in which t∈Fp and P∈G.


## 3.1.2. Elliptical Curve Discrete Logarithm Problem (ECDLP)

G is a finite cyclic group of prime order p defined on elliptic curve E, pP is the generator of group G. Suppose that there is a random point Q in group G, and solve s so that it satisfies Q=sP.


## 3.2. Certificateless Cryptosystem

The concept of certificateless encryption and signature was first proposed by Al-Riyami and Paterson, which solves the issue of key escrow in IBC. The basic idea of certificateless encryption and signature is that KGC generates a partial private key for the user. The user’s private key is jointly generated by the user and KGC. The user selects a secret value and combines it with the partial private key to generate the user’s full private key. KGC does not know the user’s complete private key, thus avoiding the problem of key escrow. The versatile definition of certificateless encryption and signature scheme consists of five algorithms, and the user public/secret key pair can be generated independently by the user even before obtaining the user partial key from the KGC [24]. Next, the definition of certificateless signature scheme will be presented:
(i)
Setup (master key generation): on input security parameter1λ, it generates a master public/secret key pair mpk,msk. The system parameter params is broadcasted to the other entities(ii)
PartialKeyGen (user partial key generation): on inputmsk and user identity ID, it generates a user partial key dID(iii)
UserKeyGen (user key generation): on inputmpk and user identity ID, it generates a user/private key pair pkID,xID(iv)
CL_Sign (signature generation): on input user private keyxID, user partial key dID, and message m, it generates a signature σ(v)
CL_Ver (signature verification): on inputmpk, user identity ID, user public key pkID, message m, and signature σ, it returns 1 or 0 for accept or reject, respectivelyCertificateless public key cryptography does not need certificate management and requires less load. Therefore, it is more suitable for mobile security applications with low broadband requirements and low energy consumption.


## 3.3. Blockchain

Blockchain originates from a paper published by Nakamoto in 2008 [25]. It is a distributed ledger on a peer-to-peer network, with each node storing and backing up complete ledger information. As shown in Figure 2, it is a data structure that connects the generated data blocks sequentially in chronological order, a decentralized shared ledger that cannot be tampered and forged. Blockchain is an effective technology to deal with vehicle management and data transmission. A reasonable construction of vehicle blockchain network framework can effectively solve many problems in IoVs, such as broadcast conflict, resource scheduling, and privacy preservation. Therefore, promoting the deep integration of blockchain technology and IoVs is the inevitable trend of IoV development.Figure 2
Blockchain structure.Each node user in the blockchain system can create a smart contract by publishing a transaction and use programming to set the smart contract as its own ownership transfer rules, transaction methods, and state transition functions. The blockchain verifies the correctness and integrity of the signature message data obtained by the RSUs through the deployed smart contract. When the data is correct, the smart contract is triggered to return the correct verification result. Otherwise, an error verification is returned.The distributed ledger is encrypted using a Merkle tree. In this paper, we have only covered chronological Merkle tree (CMT). As shown in Figure3, all transactions are hashed and stored chronologically in the CMT. Only the root hash is contained in the blockchain. In our proposed scenario, the transactions broadcast by RSUs are permanently recorded in the CMT, making the activities of each entity in the IoVs transparent and verifiable to the authorities.Figure 3
The structure of chronological Merkle tree.


## 3.4. System Model

Based on the framework of Zheng et al., we propose a certificateless anonymous cross-domain authentication system assisted by blockchain. Therefore, the entity is divided into five types: TA, KGC, cloud server (CS), RSUs, and vehicles (V). In the VANET system, the RSUs communicate with the TA through wired, while they communicate with the vehicles in its areas through wireless. This system has overcome two problems discussed in Section1, and at the same time, with the participation of blockchain technology, the framework has the characteristics of reliability and security, reducing the dependence of traditional solutions on TA or KGC. The IoV network model is shown in Figure 4.
(1)
TA: it is a fully trusted authority with unlimited computing resources and storage space. It is responsible for generating public/private keys and system parameters, registering vehicles, assigning pseudonyms to vehicles, and providing identity anonymity in vehicle communication(2)
KGC: it is not fully trusted entity. It is responsible for building and allocating partial private keys for anonymous vehicles in IoVs(3)
CS: it is responsible for managing the pseudonyms of vehicles issued by TA to facilitate identity verification and decentralized storage of transaction details including traffic information released by vehicles(4)
RSUs: it is deployed on the roadside as a bridge between TA, KGC, and vehicles. All RSUs establish a blockchain network as peer nodes. The blockchain network is in charge of the collective maintenance of blockchain data and broadcasting messages to vehicles along the road. The first RSU of each area verifies the identity of vehicles through V2I communication and submits the verification result, which is recorded on the chain after verification. After receiving the signature message, each RSU is responsible for verifying the signature of message. It will be recorded in the blockchain after verification(5)
Vehicle: the vehicle is equipped with an OBU to collect, calculate, and communicate traffic-related information. The device has its own clock to generate the correct timestamp. It is responsible for storing privacy information in the TPD of the vehicle and broadcasting information to the vehicle and nearby RSUs. In addition, vehicles can report malicious vehicles to RSUsFigure 4
System model of the proposed scheme.


## 3.5. Adversary Model

Assume that TA and RSUs are trusted entities. The vehicle is equipped with TPD, so the adversary cannot read, write, or delete the contents of the TPD. This scheme is using the ideas of certificateless cryptography. Therefore, the user’s public key has not been certificated. In the adversary model, adversaries have the right to replace the user’s public key with the illegal public key chosen by themselves. Moreover, since KGC knows the system master key, which can calculate all part of the user private key, but he cannot replace the user’s public key. Therefore, we divide the adversary types into two categories. The adversary of type I simulates a malicious user who can request and replace the public key in the system. The adversary of type II is an internal attacker who has access to the KGC’s master key and acts as a malicious but passive KGC.


## 3.6. Notations

The notations used in this paper are given in Table1.Table 1
Summary of notations.
NotationDescriptionViTheith vehicleGAn elliptic curve groupλSecurity parametersTA’s master secret keyuKGC’s master secret keyTpubTA’s public keyKpubKGC’s public keyhiA hash functionRIDiVi real identityPIDiVi pseudoidentity generated by TApskiVi partial private keyVpubiVi public keySKiVi private keyNRjAn integer negotiated between theVi and RSUjMiA message generated byViσiA signature onMi


## 3.7. Design Goals

According to IoVs and practical application requirements, the new scheme shall meet the following properties:(1)Message authentication: it ensures that the received message has not been modified or forged in the process of communication(2)Anonymity: in this scheme, only TA can obtain the real identity of the vehicle. Other vehicles in IoVs and adversary cannot identify the real identity of the sender by analyzing multiple messages sent by the same vehicle(3)Unlinkability: an attacker cannot find that multiple messages are from the same sender, and all pseudonyms should not reveal any connection between them(4)Traceability and revocation: TA can track out the real identity of the vehicle sending malicious messages and revoke the malicious vehicle(5)Unforgeability: any attacker cannot forge a legitimate signature(6)Resilience to other attacks: blockchain-assisted certificateless anonymous authentication schemes should be able to withstand various common attacks in IoVs (such as impersonation, modification, replay, and man-in-the-middle attacks)


## 4. Concrete Scheme

In this section, we describe a concrete construction of our scheme, which consists of seven phases: system initialization phase, registration phase, partial key generation phase, key generation phase, identity authentication phase, message publishing and validation phase, and tracking.


### 4.1. System Initialization Phase

This phase is executed by TA and KGC which inputs a security parameterλ and generates parameters q,P,G.(1)TA selects a master secret keys∈Zq∗ which is a random number and sets Tpub=sP as its master public key(2)KGC selectsu∈Zq∗ randomly as its master secret key and sets Kpub=uP as its master public key(3)TA chooses five distinct cryptographic hash functionsh1:0,1∗⟶Zq∗,h2×Zq∗×G⟶0,1∗,h3,Zq∗⟶0,1∗,h4,G×Zq∗⟶Zq∗,h5,Zq∗⟶0,1∗.(4)TA publishes system parametersparams=G,P,Tpub,Kpub,h1,h2,h3,h4,h5. The TA and KGC keep master secret keys s and u secretly, respectively


### 4.2. Registration Phase

VehicleVi with identity RIDi initiates a registration request. First, TA checks the existence of the real identity of the vehicle. If it exists, H1i=h1RIDiTregis calculated, where Treg is the registration time of the vehicle. Then, randomly select t∈Zq∗ and compute the pseudonymPIDi=tH1imodq. Upload the pseudonym information H1i,PIDi,PIDis,Treg to the user list ULwhich is put in the blockchain, and store a tuple RIDi,H1i,PIDi,Treg in TA’s database. Finally, H1i,PIDi are sent to the vehicle. Figure 5 shows the registration process.Figure 5
Distribution of registration data.


### 4.3. Partial Key Generation Phase

VehicleVi requests the partial key from KGC with its pseudonym PIDi. Once received PIDi from vehicle Vi, KGC works as follows:(1)The KGC first looks up the user listUL obtained from blockchain to ensure that PIDi is present in UL, which means that PIDi has not been revoked by TA(2)IfPIDi is found in UL, KGC computes pski=u+PIDi⋅smodq and H2i=h2PIDipski−1P(3)KGC setspski as the partial private key and sends H2i to the CS via the secure channel


### 4.4. Key Generation Phase

After receiving partial keyspski from KGC, vehicle Vi first verifies its correctness through the calculation equation epskiP,P=eKpub+PIDiTpub,P. Next, it selects xi∈Zq∗ randomly and computes and publishes public key Vpubi=xiP, and the private key is SKi=xi,pski.


### 4.5. Identity Authentication Phase

During identity authentication, the vehicleVi communicates with the RSUs by using its own pseudonym, and neither the RSUs nor the CS learns to acquire the vehicle’s real identity. Figure 6 shows the identity authentication process.
(1)
When the vehicleVi comes in the range of first RSUj in a region, it sends an authentication request with its own PIDi and Vi computes pski−1P and then sends it and PIDi to RSUj. In order to determine whether the Vi is legal, RSUj computes H2i′=hPIDipski−1P and sends the result to CS, and CS queries whether it is equal to its stored H2i. If the vehicle is legal, CS sends the result back to RSUj, and finally, RSUj broadcasts the authentication result into blockchain network and which will be recorded on the blockchain after verification(2)
After determining the authenticity of the vehicle identity, theRSUj initiates the random integer negotiation process, which sends a random integer NRj encrypted by the vehicles’ public key Vpubi to the vehicle Vi(3)
The vehicle receives the ciphertext and decrypts it with its private key. After obtainingNRj, to determine whether the vehicle receives NRj from RSUj and its integrity, the vehicle Vi has to select another random integer MVi, computes H3i=h3NRjMVi, and sends H3iMVi to RSUj. To ensure the integrity of the transaction information, it will perform h3 operation according to NRj and received MVi. If the result is consistent with the H3i computed by the vehicle Vi, an integer NRj is negotiated between the vehicle Vi and the RSUj. Finally, the vehicle stores the NRjin OBU for later message publishing(4)
In order to let the vehicle communicates conveniently with other RSUs, theRSUj computes Lij=MVi−1NRj and packages PIDi, Vpubi, and Lij into a transaction Tx1=PIDiVpubiLij and then records on the blockchain indicating that NRj can be used by other RSUs in a certain region and the identity of vehicle Vi has been verified; that is, other RSUs do not need to repeatedly verify the identity of vehicle ViFigure 6
The identity authentication process.


### 4.6. Message Publishing and Validation Phase

After identity authentication phase, the vehicleVi can publish message and the RSUj should verify them. Figure 7 is the scenario of message publishing and validation.
(1)
The vehicleVi computes NP=NRjP and H4i=h4NPMiPIDiTi where Ti is the timestamp of the signature stage. Vi selects bi∈Zq∗ randomly and computesBi=biP, MP=MViP, and Ai=NRjpski+xi+biH4i. Then, the signature of the message Mi is σi=Ai,Bi,Mp. Vehicle Vi sends Mi,σi,PIDi,Ti to RSUj(2)
RSUs deploy a smart contract to verify the correctness and integrity of signature message data(3)
Blockchain nodes execute the algorithm. At first, theRSUj determines the freshness of time stamp Ti. If Ti is not fresh, the message is discarded, and the operation is stopped. Otherwise, RSUj computes H4i′=h4MVi−1NRjMViPMiPIDiTi. If H4i′≠H4i, then it determines whether (4) is valid. If so, RSUj accepts Mi,σi,PIDi,Ti:(4)AiP−BiH4i=NRjKpub+PIDiTpub+VpubiH4i.Figure 7
The message publishing and validation phase.The following is the proof of correctness:(5)AiP−BiH4=NRjpskiP+xi+biH4iP−BiH4i=NRju+PIDisP+xiH4iP+biH4iP−BiH4i=NRjKpub+PIDiTpub+VpubiH4i+BiH4i−BiH4i=NRjKpub+PIDiTpub+VpubiH4i(4)
The smart contract validates the data through a function interface and returns the correct resultTrue only when H4i′=H4i and AiP−BiH4i=NRjKpub+PIDiTpub+VpubiH4i. Otherwise, the error result False is returned. The smart contract verification algorithm in signature message verification phase can be written in Solidity language, and the content of the intelligent contract verification algorithm is roughly as shown in Algorithm 1(5)
If the verification is successful,RSUj packages the transaction Tx2=H4iMiPIDiTi, divides the transaction into several parts and stores them in different CS, and then performs h5 operation on Tx2 and stores it in the blockchain as CMT. Finally, the transaction is broadcasted to each nodeAlgorithm 1: Smart contract algorithm in verification phase.
Input:Mi,σi,PIDi,TiOutput: True or False1:  begin2:  ifTi is not fresh then3:   throw;4:  ifH4i′≠H4i then5:   throw;6: ifAiP−BiH4i=NRjKpub+PIDiTpub+VpubiH4i then7:  return True;8: end if


### 4.7. Tracking

When traffic conditions are safe, but it is inconsistent with the transaction information, other vehicles can report the vehicles who published the false message. The RSUs then report the pseudoidentityPIDi=tH1imodq of the malicious vehicle to TA. TA traces the real identity RIDi from his database by computing H1i=h1RIDiTreg and revokes the user information H1i,PIDi,PIDis,Treg to update the user list UL accordingly. Finally, the RSU broadcasts the malicious vehicle and new UL to the blockchain.


## 4.1. System Initialization Phase

This phase is executed by TA and KGC which inputs a security parameterλ and generates parameters q,P,G.(1)TA selects a master secret keys∈Zq∗ which is a random number and sets Tpub=sP as its master public key(2)KGC selectsu∈Zq∗ randomly as its master secret key and sets Kpub=uP as its master public key(3)TA chooses five distinct cryptographic hash functionsh1:0,1∗⟶Zq∗,h2×Zq∗×G⟶0,1∗,h3,Zq∗⟶0,1∗,h4,G×Zq∗⟶Zq∗,h5,Zq∗⟶0,1∗.(4)TA publishes system parametersparams=G,P,Tpub,Kpub,h1,h2,h3,h4,h5. The TA and KGC keep master secret keys s and u secretly, respectively


## 4.2. Registration Phase

VehicleVi with identity RIDi initiates a registration request. First, TA checks the existence of the real identity of the vehicle. If it exists, H1i=h1RIDiTregis calculated, where Treg is the registration time of the vehicle. Then, randomly select t∈Zq∗ and compute the pseudonymPIDi=tH1imodq. Upload the pseudonym information H1i,PIDi,PIDis,Treg to the user list ULwhich is put in the blockchain, and store a tuple RIDi,H1i,PIDi,Treg in TA’s database. Finally, H1i,PIDi are sent to the vehicle. Figure 5 shows the registration process.Figure 5
Distribution of registration data.


## 4.3. Partial Key Generation Phase

VehicleVi requests the partial key from KGC with its pseudonym PIDi. Once received PIDi from vehicle Vi, KGC works as follows:(1)The KGC first looks up the user listUL obtained from blockchain to ensure that PIDi is present in UL, which means that PIDi has not been revoked by TA(2)IfPIDi is found in UL, KGC computes pski=u+PIDi⋅smodq and H2i=h2PIDipski−1P(3)KGC setspski as the partial private key and sends H2i to the CS via the secure channel


## 4.4. Key Generation Phase

After receiving partial keyspski from KGC, vehicle Vi first verifies its correctness through the calculation equation epskiP,P=eKpub+PIDiTpub,P. Next, it selects xi∈Zq∗ randomly and computes and publishes public key Vpubi=xiP, and the private key is SKi=xi,pski.


## 4.5. Identity Authentication Phase

During identity authentication, the vehicleVi communicates with the RSUs by using its own pseudonym, and neither the RSUs nor the CS learns to acquire the vehicle’s real identity. Figure 6 shows the identity authentication process.
(1)
When the vehicleVi comes in the range of first RSUj in a region, it sends an authentication request with its own PIDi and Vi computes pski−1P and then sends it and PIDi to RSUj. In order to determine whether the Vi is legal, RSUj computes H2i′=hPIDipski−1P and sends the result to CS, and CS queries whether it is equal to its stored H2i. If the vehicle is legal, CS sends the result back to RSUj, and finally, RSUj broadcasts the authentication result into blockchain network and which will be recorded on the blockchain after verification(2)
After determining the authenticity of the vehicle identity, theRSUj initiates the random integer negotiation process, which sends a random integer NRj encrypted by the vehicles’ public key Vpubi to the vehicle Vi(3)
The vehicle receives the ciphertext and decrypts it with its private key. After obtainingNRj, to determine whether the vehicle receives NRj from RSUj and its integrity, the vehicle Vi has to select another random integer MVi, computes H3i=h3NRjMVi, and sends H3iMVi to RSUj. To ensure the integrity of the transaction information, it will perform h3 operation according to NRj and received MVi. If the result is consistent with the H3i computed by the vehicle Vi, an integer NRj is negotiated between the vehicle Vi and the RSUj. Finally, the vehicle stores the NRjin OBU for later message publishing(4)
In order to let the vehicle communicates conveniently with other RSUs, theRSUj computes Lij=MVi−1NRj and packages PIDi, Vpubi, and Lij into a transaction Tx1=PIDiVpubiLij and then records on the blockchain indicating that NRj can be used by other RSUs in a certain region and the identity of vehicle Vi has been verified; that is, other RSUs do not need to repeatedly verify the identity of vehicle ViFigure 6
The identity authentication process.


## 4.6. Message Publishing and Validation Phase

After identity authentication phase, the vehicleVi can publish message and the RSUj should verify them. Figure 7 is the scenario of message publishing and validation.
(1)
The vehicleVi computes NP=NRjP and H4i=h4NPMiPIDiTi where Ti is the timestamp of the signature stage. Vi selects bi∈Zq∗ randomly and computesBi=biP, MP=MViP, and Ai=NRjpski+xi+biH4i. Then, the signature of the message Mi is σi=Ai,Bi,Mp. Vehicle Vi sends Mi,σi,PIDi,Ti to RSUj(2)
RSUs deploy a smart contract to verify the correctness and integrity of signature message data(3)
Blockchain nodes execute the algorithm. At first, theRSUj determines the freshness of time stamp Ti. If Ti is not fresh, the message is discarded, and the operation is stopped. Otherwise, RSUj computes H4i′=h4MVi−1NRjMViPMiPIDiTi. If H4i′≠H4i, then it determines whether (4) is valid. If so, RSUj accepts Mi,σi,PIDi,Ti:(4)AiP−BiH4i=NRjKpub+PIDiTpub+VpubiH4i.Figure 7
The message publishing and validation phase.The following is the proof of correctness:(5)AiP−BiH4=NRjpskiP+xi+biH4iP−BiH4i=NRju+PIDisP+xiH4iP+biH4iP−BiH4i=NRjKpub+PIDiTpub+VpubiH4i+BiH4i−BiH4i=NRjKpub+PIDiTpub+VpubiH4i(4)
The smart contract validates the data through a function interface and returns the correct resultTrue only when H4i′=H4i and AiP−BiH4i=NRjKpub+PIDiTpub+VpubiH4i. Otherwise, the error result False is returned. The smart contract verification algorithm in signature message verification phase can be written in Solidity language, and the content of the intelligent contract verification algorithm is roughly as shown in Algorithm 1(5)
If the verification is successful,RSUj packages the transaction Tx2=H4iMiPIDiTi, divides the transaction into several parts and stores them in different CS, and then performs h5 operation on Tx2 and stores it in the blockchain as CMT. Finally, the transaction is broadcasted to each nodeAlgorithm 1: Smart contract algorithm in verification phase.
Input:Mi,σi,PIDi,TiOutput: True or False1:  begin2:  ifTi is not fresh then3:   throw;4:  ifH4i′≠H4i then5:   throw;6: ifAiP−BiH4i=NRjKpub+PIDiTpub+VpubiH4i then7:  return True;8: end if


## 4.7. Tracking

When traffic conditions are safe, but it is inconsistent with the transaction information, other vehicles can report the vehicles who published the false message. The RSUs then report the pseudoidentityPIDi=tH1imodq of the malicious vehicle to TA. TA traces the real identity RIDi from his database by computing H1i=h1RIDiTreg and revokes the user information H1i,PIDi,PIDis,Treg to update the user list UL accordingly. Finally, the RSU broadcasts the malicious vehicle and new UL to the blockchain.


## 5. Security Proof and Analysis

In this part, the security of our scheme under random oracle is proved, and we demonstrate that our basic scheme meets the security objectives in Section3. In other words, our architecture can provide integrity, anonymity, unlinkability, and so on.


### 5.1. Security Proof

Definition 3.
If adversaries A1 and A2 cannot win the following games with negligible probability in polynomial time, then the proposed scheme satisfies the Existential Unforgeability Against Adaptive Chosen Message Attack (EUF-CMA) in the random oracle model.Theorem 4.
If the running time of an adversary A1 with probability polynomial time in game 1 ist, execute Qii=1~4 hash queries, QPPK partial private key extraction queries, and QPK public key queries, and the advantage of forging a legal signature after Qσ signature queries is ε; then, the ECDLP problem can be solved with a probability of no less than ε/QPPK1−1/QPPKQPPK in t′≤t+OQ2+Q3+Q1+Q4+QPPK+QPK+Qσts time, and tsrepresents the time of one multiplication in group G.Proof of Theorem.
Challenger algorithm C first interacts with adversary A1 to generate an instance of the ECDLP problem, givenP,Q=aP, where a∈Zq∗,P∈G. The goal of challenger C is to solve for a. C interacts with A1, responds to all the queries of A1, and records these in the corresponding lists which are initially empty.
(i)
Setup: challenger C initializes system parameterG,P,Tpub,Kpub=Q,h1,h2,h3,h4,h5 and sends the system parameter to A1 and C randomly selects ID∗ as the challenge identity of the game. A1 makes the following inquiries:
(1)
h1 oracle: when A1 with an IDi performs this query to h1 oracle, C records the questions and answers between A1 and C through list L1=IDi,h1IDi,t. If C looks up the corresponding L1=IDi,h1IDi,t in L1, C returns h1IDi,t to A1; otherwise, C randomly picks h1IDi,t′∈Zq∗ and sends it to A1 and then adds IDi,h1IDi,t′ to the L1(2)
h2 oracle: when A1 with a PIDi performs this query to h2 oracle, C records the questions and answers between A1 and C through list L2=PIDi,pski−1P,ui. If C looks up the corresponding PIDi,pski−1P,ui in L2, C returns ui to A1; otherwise, C randomly picks ui∈Zq∗ and sends it to A1 and then adds PIDi,pski−1P,ui to the L2(3)
h3 oracle: when A1 with NRjMVi performs this query to h3 oracle, C records the questions and answers between A1 and C through list L3=NRjMVi,vi. If C looks up the corresponding NRjMVi,vi in L3, C returns vi to A1; otherwise, C randomly picks vi∈Zq∗ and sends it to A1 and then adds PIDi,pski−1P,ui to the L3(4)
h4 oracle: when A1 with NPMiPIDiTi performs this query to h4 oracle, C records the questions and answers between A1 and C through list L4=NPMiPIDiTi,wi. If C looks up the corresponding NPMiPIDiTi,wi in L4, C returns wi to A1; otherwise, C randomly picks wi∈Zq∗ and sends it to A1 and then adds NPMiPIDiTi,wi to the L4(5)
Partial-private key oracle: when A1 withPIDi performs this query to partial-private key oracle, C records the questions and answers between A1 and C through list Lpar=PIDi,pski. If C looks up the correspondingPIDi,pski in Lpar, C returns pski to A1; otherwise, if PIDi≠PIDi∗, C randomly picks pski∈Zq∗ and sends pski to A1 and then saves PIDi,pski in list Lpar. If PIDi=PIDi∗, C stops the game(6)
Public key oracle: when A1 withPIDi performs this query to partial-private key oracle, C records the questions and answers between A1 and C through list Lpub=PIDi,xi,Vpubi. If C looks up the corresponding PIDi,xi,Vpubi in Lpub, C returns Vpubi to A1; otherwise, if PIDi≠PIDi∗, C randomly picks xi∈Zq∗, let Vpubi=xiP and sends Vpubi to A1, and then saves PIDi,xi,Vpubi in list Lpub(7)
Secret value oracle: when A1 withPIDi performs this query to secret value oracle, if PIDi≠PIDi∗, C gives up and terminates the operation; otherwise, C looks for list Lpub, and if record PIDi,xi,Vpubi exists, C returns xi to A1. If not, C performs a public key query to generate tuple xi,Vpubi, returns xi to A1, and adds xi,Vpubi to the Lpub(8)
Replace public key oracle: when A1 withPIDi,Vpubi′ performs this query to replace public key oracle, C first finds the corresponding record PIDi,xi,Vpubi from Lpub. If it does not exist, C performs public key oracle with PIDi, replaces Vpubi with Vpubi′ freely selected by A1, and makes xi=⊥(9)
Signature oracle: A1 performs signature oracle withPIDi,Mi, and C recoversh1IDi,Treg, h2PIDipski−1P, and h3NRjMVi,h4NPMiPIDiTi from list L1,L2,L3,Lpar,Lpub; if PIDi≠PIDi∗, then C outputs the signature σi corresponding to message Mi and transmitsσi to A1; otherwise, C randomly picks bi∈Zq∗ and computes Bi=biP, MP=MViP, and Ai=NRjpski+xi+biH4i. σi=Ai,Bi,MP represents a correct signature of the signer to the messageMi. And then finally, C returns σi to A1(ii)
Forgery: finally, A1 prints a forged signature. IfPIDi≠PIDi∗, C stops the simulation; otherwise, C finds the corresponding signature information Mi,σi,PIDi,Ti from the prophecy query list, and if adversary A1 wins the game, then AiP−BiH4i=NRjKpub+PIDiTpub+VpubiH4i. Then, the bifurcation lemma [26] is used to obtain another two sets of valid signatures σiℓ,ℓ=2,3 in polynomial time, and these three signatures must satisfy AiP−BiH4i=NRjKpub+PIDiTpub+VpubiH4i. And because of Vpubi=xiP, Bi=biP, and Kpub=aP, there are three linearly independent equations:
(6)Aiℓ⋅P−BiℓH4i=NRjKpub+PIDiℓTpub+VpubiℓH4i,ℓ=1,2,3
Challenger C solves the solution of these three equations and takes thea output as the solution of the ECDLP problem.
In the partial private key extraction query, the probability of C not giving up is at least1−1/QPPKQPPK, and the probability of C not giving up in the forgery stage is at least 1/QPPK. Therefore, the probability of C successfully solving the problem is at least ε/QPPK1−1/QPPKQPPK. The running time of C is t′≤t+OQ2+Q3+Q1+Q4+QPPK+QPK+Qσts.Theorem 5.
If the running time of an adversary A2 with probability polynomial time in game 2 ist, execute Qii=1~4 hash queries, QX secret value queries, and QPK public key queries, and the advantage of forging a legal signature after Qσ signature queries is ε; then, the ECDLP problem can be solved with a probability of no less than ε/QPK1−1/QPKQPK+QX in t′≤t+OQ2+Q1+Q3+QPK+Qσts time, and ts represents the time of one multiplication in group G.The idea and method of proof are similar as that of Theorem4. A2 only has the ability of hash value inquiry, public key extraction inquiry, secret value inquiry, private key extraction inquiry, and signature inquiry but does not have the ability of public key substitution, so the proof process will not be repeated here.


### 5.2. Security Analysis

#### 5.2.1. Message Authentication

The RSU or any vehicle within the RSU domain can verify the messageMi by verifying the pseudoidentity PIDi of the vehicle and using its signature σi. In addition, under the condition that ECDLP is difficult, there is no polynomial-time adversary to forge valid signatures; that is, there is no probabilistic polynomial-time adversary to forge valid messages without using the private key of signature. Therefore, the receiver can verify the authenticity and integrity of message Mi,σi,PIDi,Ti by verifying whether H4i′ and H4i are equal to each other and whether (1) holds.


#### 5.2.2. Anonymity

The vehicleVi in the IoV environment with pseudoidentity PIDi sends a message Mi,σi,PIDi,Ti, where PIDi=tH1imodq, H1i=h1RIDiTreg, and Treg are the registration time of the vehicle, and t is randomly selected from Zq∗. To extract the real identity RIDi, the adversary should calculate H1i, and t is random. Obviously, it is impossible for the enemy to calculate the RIDi of vehicle Vi for discrete logarithm problem and one-way hash function. Therefore, the scheme guarantees the privacy of the vehicle.


#### 5.2.3. Unlinkability

The messageM and message M′ are signed by different private keys SKi, and the pseudoidentity PIDi is calculated by TA, PIDi=tH1imodq, where H1i is the hash value of the real identity RIDi and the registration time Treg, and t is a random number, so it is impossible for any adversary to link any pseudoidentity PIDi.


#### 5.2.4. Forward Security and Backward Security

In this scheme, if the adversary obtains the signed messageσi=Ai,Bi,Mp, where Ai=NRj⋅pski+xi+biH4i, Bi=biP, and MP=MViP, because bi is random, and NRjis a random integer secretly negotiated between the RSUj and vehicle Vi. So each signature is different and the adversary cannot infer a previous or subsequent signature message from the current signature message.


#### 5.2.5. Traceability

The proposed scheme provides conditional identity privacy preservation in IoVs. TA tracked and revealed the real identity of the malicious vehicle from its database. When a malicious vehicle with forged messages is found, the real identity of the malicious vehicle can be traced by TA. TA, as a trust authority, cannot tamper the real identity and the pseudoidentityPIDi of a malicious vehicle because tupleH1i,PIDi,PIDis,Treg of the vehicle is recorded in a blockchain.


#### 5.2.6. Cross-Domain Authentication

First, when the vehicleVi publishes a message Mi, it sends the signatureσi=Ai,Bi,Mp to the first RSU of Mi. If the verification is successful, a new transaction Tx2=H4iMiPIDiTi is generated and h5Tx2 is recorded on the blockchain and broadcasted to all the nodes. When other RSUs and vehicles in other RSUs receive the message Mi, they only need to look up the verification information related to the message from the chain. Second, only the first RSU negotiates a random integer NRj with a vehicle Vi, and a transaction Tx1=PIDiVpubiLij with Lij=MVi−1NRj, PIDi, and Vpubi is recorded on the blockchain. Therefore, when the vehicle Vi enters the next RSU range, if a new message is to be published, there is no need to renegotiate the random number.


#### 5.2.7. Resilience to Other Attacks

(1) Impersonation Attack. In order to impersonate a registered vehicle, the enemy needs a valid signature for message Mi. Therefore, NP=NRjP, H4i=h4NPMiPIDiTi, Bi=biP,MP=MViP, and Ai=NRj⋅pski+xi+biH4i need to be calculated, where NRj is an integer to ensure the integrity of the transaction content negotiated between vehicle Vi and RSUj, and the adversary needs to know the private key used for signature. Therefore, in calculation, it is not feasible for the adversary to create another valid request message without knowing the above content. Therefore, the scheme is safe from vehicle simulation attacks.(2) Modification Attack. In the authentication phase, the freshness of the message is determined by the timestamp at the time of signing, and the message Mi,σi,PIDi,Ti sent by vehicle Vi has the timestamp Ti of the sender. Any nearby vehicle or RSU can check Ti to verify the freshness of the message. It prevents the message Mi,σi,PIDi,Ti from being repeatedly broadcast in the RSU domain, so the scheme protects against replay attacks.(3) Man-In-The-Middle Attack. Suppose an adversary intercepts a message Mi,σi,PIDi,Ti, and the adversary tries to create a valid signature in place of the vehicle to send to the RSU as an authentication request. However, it can be seen from the signature that the adversary needs to know NRj, bi, and MVi, and these parameters are embedded in the ECDLP difficulty problem, so the scheme is not subject to man-in-the-middle attack.(4) Replay Attack. For the signature σi=Ai,Bi,Mp of the message Mi and Ai=NRj⋅pski+xi+biH4i and H4i=h4NPMiPIDiTi, the message contains the current timestamp; when receiving a message, the RSU checks the validity of the message by comparing the received timestamp to the current timestamp. For valid message and its freshness, the difference between the timestamp should be a small value; therefore, by containing a timestamp in each message, one can ensure that the message is protected from replay attacks because no adversaries can successfully replay the intercepted message.


## 5.1. Security Proof

Definition 3.
If adversaries A1 and A2 cannot win the following games with negligible probability in polynomial time, then the proposed scheme satisfies the Existential Unforgeability Against Adaptive Chosen Message Attack (EUF-CMA) in the random oracle model.Theorem 4.
If the running time of an adversary A1 with probability polynomial time in game 1 ist, execute Qii=1~4 hash queries, QPPK partial private key extraction queries, and QPK public key queries, and the advantage of forging a legal signature after Qσ signature queries is ε; then, the ECDLP problem can be solved with a probability of no less than ε/QPPK1−1/QPPKQPPK in t′≤t+OQ2+Q3+Q1+Q4+QPPK+QPK+Qσts time, and tsrepresents the time of one multiplication in group G.Proof of Theorem.
Challenger algorithm C first interacts with adversary A1 to generate an instance of the ECDLP problem, givenP,Q=aP, where a∈Zq∗,P∈G. The goal of challenger C is to solve for a. C interacts with A1, responds to all the queries of A1, and records these in the corresponding lists which are initially empty.
(i)
Setup: challenger C initializes system parameterG,P,Tpub,Kpub=Q,h1,h2,h3,h4,h5 and sends the system parameter to A1 and C randomly selects ID∗ as the challenge identity of the game. A1 makes the following inquiries:
(1)
h1 oracle: when A1 with an IDi performs this query to h1 oracle, C records the questions and answers between A1 and C through list L1=IDi,h1IDi,t. If C looks up the corresponding L1=IDi,h1IDi,t in L1, C returns h1IDi,t to A1; otherwise, C randomly picks h1IDi,t′∈Zq∗ and sends it to A1 and then adds IDi,h1IDi,t′ to the L1(2)
h2 oracle: when A1 with a PIDi performs this query to h2 oracle, C records the questions and answers between A1 and C through list L2=PIDi,pski−1P,ui. If C looks up the corresponding PIDi,pski−1P,ui in L2, C returns ui to A1; otherwise, C randomly picks ui∈Zq∗ and sends it to A1 and then adds PIDi,pski−1P,ui to the L2(3)
h3 oracle: when A1 with NRjMVi performs this query to h3 oracle, C records the questions and answers between A1 and C through list L3=NRjMVi,vi. If C looks up the corresponding NRjMVi,vi in L3, C returns vi to A1; otherwise, C randomly picks vi∈Zq∗ and sends it to A1 and then adds PIDi,pski−1P,ui to the L3(4)
h4 oracle: when A1 with NPMiPIDiTi performs this query to h4 oracle, C records the questions and answers between A1 and C through list L4=NPMiPIDiTi,wi. If C looks up the corresponding NPMiPIDiTi,wi in L4, C returns wi to A1; otherwise, C randomly picks wi∈Zq∗ and sends it to A1 and then adds NPMiPIDiTi,wi to the L4(5)
Partial-private key oracle: when A1 withPIDi performs this query to partial-private key oracle, C records the questions and answers between A1 and C through list Lpar=PIDi,pski. If C looks up the correspondingPIDi,pski in Lpar, C returns pski to A1; otherwise, if PIDi≠PIDi∗, C randomly picks pski∈Zq∗ and sends pski to A1 and then saves PIDi,pski in list Lpar. If PIDi=PIDi∗, C stops the game(6)
Public key oracle: when A1 withPIDi performs this query to partial-private key oracle, C records the questions and answers between A1 and C through list Lpub=PIDi,xi,Vpubi. If C looks up the corresponding PIDi,xi,Vpubi in Lpub, C returns Vpubi to A1; otherwise, if PIDi≠PIDi∗, C randomly picks xi∈Zq∗, let Vpubi=xiP and sends Vpubi to A1, and then saves PIDi,xi,Vpubi in list Lpub(7)
Secret value oracle: when A1 withPIDi performs this query to secret value oracle, if PIDi≠PIDi∗, C gives up and terminates the operation; otherwise, C looks for list Lpub, and if record PIDi,xi,Vpubi exists, C returns xi to A1. If not, C performs a public key query to generate tuple xi,Vpubi, returns xi to A1, and adds xi,Vpubi to the Lpub(8)
Replace public key oracle: when A1 withPIDi,Vpubi′ performs this query to replace public key oracle, C first finds the corresponding record PIDi,xi,Vpubi from Lpub. If it does not exist, C performs public key oracle with PIDi, replaces Vpubi with Vpubi′ freely selected by A1, and makes xi=⊥(9)
Signature oracle: A1 performs signature oracle withPIDi,Mi, and C recoversh1IDi,Treg, h2PIDipski−1P, and h3NRjMVi,h4NPMiPIDiTi from list L1,L2,L3,Lpar,Lpub; if PIDi≠PIDi∗, then C outputs the signature σi corresponding to message Mi and transmitsσi to A1; otherwise, C randomly picks bi∈Zq∗ and computes Bi=biP, MP=MViP, and Ai=NRjpski+xi+biH4i. σi=Ai,Bi,MP represents a correct signature of the signer to the messageMi. And then finally, C returns σi to A1(ii)
Forgery: finally, A1 prints a forged signature. IfPIDi≠PIDi∗, C stops the simulation; otherwise, C finds the corresponding signature information Mi,σi,PIDi,Ti from the prophecy query list, and if adversary A1 wins the game, then AiP−BiH4i=NRjKpub+PIDiTpub+VpubiH4i. Then, the bifurcation lemma [26] is used to obtain another two sets of valid signatures σiℓ,ℓ=2,3 in polynomial time, and these three signatures must satisfy AiP−BiH4i=NRjKpub+PIDiTpub+VpubiH4i. And because of Vpubi=xiP, Bi=biP, and Kpub=aP, there are three linearly independent equations:
(6)Aiℓ⋅P−BiℓH4i=NRjKpub+PIDiℓTpub+VpubiℓH4i,ℓ=1,2,3
Challenger C solves the solution of these three equations and takes thea output as the solution of the ECDLP problem.
In the partial private key extraction query, the probability of C not giving up is at least1−1/QPPKQPPK, and the probability of C not giving up in the forgery stage is at least 1/QPPK. Therefore, the probability of C successfully solving the problem is at least ε/QPPK1−1/QPPKQPPK. The running time of C is t′≤t+OQ2+Q3+Q1+Q4+QPPK+QPK+Qσts.Theorem 5.
If the running time of an adversary A2 with probability polynomial time in game 2 ist, execute Qii=1~4 hash queries, QX secret value queries, and QPK public key queries, and the advantage of forging a legal signature after Qσ signature queries is ε; then, the ECDLP problem can be solved with a probability of no less than ε/QPK1−1/QPKQPK+QX in t′≤t+OQ2+Q1+Q3+QPK+Qσts time, and ts represents the time of one multiplication in group G.The idea and method of proof are similar as that of Theorem4. A2 only has the ability of hash value inquiry, public key extraction inquiry, secret value inquiry, private key extraction inquiry, and signature inquiry but does not have the ability of public key substitution, so the proof process will not be repeated here.


## 5.2. Security Analysis

### 5.2.1. Message Authentication

The RSU or any vehicle within the RSU domain can verify the messageMi by verifying the pseudoidentity PIDi of the vehicle and using its signature σi. In addition, under the condition that ECDLP is difficult, there is no polynomial-time adversary to forge valid signatures; that is, there is no probabilistic polynomial-time adversary to forge valid messages without using the private key of signature. Therefore, the receiver can verify the authenticity and integrity of message Mi,σi,PIDi,Ti by verifying whether H4i′ and H4i are equal to each other and whether (1) holds.


### 5.2.2. Anonymity

The vehicleVi in the IoV environment with pseudoidentity PIDi sends a message Mi,σi,PIDi,Ti, where PIDi=tH1imodq, H1i=h1RIDiTreg, and Treg are the registration time of the vehicle, and t is randomly selected from Zq∗. To extract the real identity RIDi, the adversary should calculate H1i, and t is random. Obviously, it is impossible for the enemy to calculate the RIDi of vehicle Vi for discrete logarithm problem and one-way hash function. Therefore, the scheme guarantees the privacy of the vehicle.


### 5.2.3. Unlinkability

The messageM and message M′ are signed by different private keys SKi, and the pseudoidentity PIDi is calculated by TA, PIDi=tH1imodq, where H1i is the hash value of the real identity RIDi and the registration time Treg, and t is a random number, so it is impossible for any adversary to link any pseudoidentity PIDi.


### 5.2.4. Forward Security and Backward Security

In this scheme, if the adversary obtains the signed messageσi=Ai,Bi,Mp, where Ai=NRj⋅pski+xi+biH4i, Bi=biP, and MP=MViP, because bi is random, and NRjis a random integer secretly negotiated between the RSUj and vehicle Vi. So each signature is different and the adversary cannot infer a previous or subsequent signature message from the current signature message.


### 5.2.5. Traceability

The proposed scheme provides conditional identity privacy preservation in IoVs. TA tracked and revealed the real identity of the malicious vehicle from its database. When a malicious vehicle with forged messages is found, the real identity of the malicious vehicle can be traced by TA. TA, as a trust authority, cannot tamper the real identity and the pseudoidentityPIDi of a malicious vehicle because tupleH1i,PIDi,PIDis,Treg of the vehicle is recorded in a blockchain.


### 5.2.6. Cross-Domain Authentication

First, when the vehicleVi publishes a message Mi, it sends the signatureσi=Ai,Bi,Mp to the first RSU of Mi. If the verification is successful, a new transaction Tx2=H4iMiPIDiTi is generated and h5Tx2 is recorded on the blockchain and broadcasted to all the nodes. When other RSUs and vehicles in other RSUs receive the message Mi, they only need to look up the verification information related to the message from the chain. Second, only the first RSU negotiates a random integer NRj with a vehicle Vi, and a transaction Tx1=PIDiVpubiLij with Lij=MVi−1NRj, PIDi, and Vpubi is recorded on the blockchain. Therefore, when the vehicle Vi enters the next RSU range, if a new message is to be published, there is no need to renegotiate the random number.


### 5.2.7. Resilience to Other Attacks

(1) Impersonation Attack. In order to impersonate a registered vehicle, the enemy needs a valid signature for message Mi. Therefore, NP=NRjP, H4i=h4NPMiPIDiTi, Bi=biP,MP=MViP, and Ai=NRj⋅pski+xi+biH4i need to be calculated, where NRj is an integer to ensure the integrity of the transaction content negotiated between vehicle Vi and RSUj, and the adversary needs to know the private key used for signature. Therefore, in calculation, it is not feasible for the adversary to create another valid request message without knowing the above content. Therefore, the scheme is safe from vehicle simulation attacks.(2) Modification Attack. In the authentication phase, the freshness of the message is determined by the timestamp at the time of signing, and the message Mi,σi,PIDi,Ti sent by vehicle Vi has the timestamp Ti of the sender. Any nearby vehicle or RSU can check Ti to verify the freshness of the message. It prevents the message Mi,σi,PIDi,Ti from being repeatedly broadcast in the RSU domain, so the scheme protects against replay attacks.(3) Man-In-The-Middle Attack. Suppose an adversary intercepts a message Mi,σi,PIDi,Ti, and the adversary tries to create a valid signature in place of the vehicle to send to the RSU as an authentication request. However, it can be seen from the signature that the adversary needs to know NRj, bi, and MVi, and these parameters are embedded in the ECDLP difficulty problem, so the scheme is not subject to man-in-the-middle attack.(4) Replay Attack. For the signature σi=Ai,Bi,Mp of the message Mi and Ai=NRj⋅pski+xi+biH4i and H4i=h4NPMiPIDiTi, the message contains the current timestamp; when receiving a message, the RSU checks the validity of the message by comparing the received timestamp to the current timestamp. For valid message and its freshness, the difference between the timestamp should be a small value; therefore, by containing a timestamp in each message, one can ensure that the message is protected from replay attacks because no adversaries can successfully replay the intercepted message.


## 5.2.1. Message Authentication

The RSU or any vehicle within the RSU domain can verify the messageMi by verifying the pseudoidentity PIDi of the vehicle and using its signature σi. In addition, under the condition that ECDLP is difficult, there is no polynomial-time adversary to forge valid signatures; that is, there is no probabilistic polynomial-time adversary to forge valid messages without using the private key of signature. Therefore, the receiver can verify the authenticity and integrity of message Mi,σi,PIDi,Ti by verifying whether H4i′ and H4i are equal to each other and whether (1) holds.


## 5.2.2. Anonymity

The vehicleVi in the IoV environment with pseudoidentity PIDi sends a message Mi,σi,PIDi,Ti, where PIDi=tH1imodq, H1i=h1RIDiTreg, and Treg are the registration time of the vehicle, and t is randomly selected from Zq∗. To extract the real identity RIDi, the adversary should calculate H1i, and t is random. Obviously, it is impossible for the enemy to calculate the RIDi of vehicle Vi for discrete logarithm problem and one-way hash function. Therefore, the scheme guarantees the privacy of the vehicle.


## 5.2.3. Unlinkability

The messageM and message M′ are signed by different private keys SKi, and the pseudoidentity PIDi is calculated by TA, PIDi=tH1imodq, where H1i is the hash value of the real identity RIDi and the registration time Treg, and t is a random number, so it is impossible for any adversary to link any pseudoidentity PIDi.


## 5.2.4. Forward Security and Backward Security

In this scheme, if the adversary obtains the signed messageσi=Ai,Bi,Mp, where Ai=NRj⋅pski+xi+biH4i, Bi=biP, and MP=MViP, because bi is random, and NRjis a random integer secretly negotiated between the RSUj and vehicle Vi. So each signature is different and the adversary cannot infer a previous or subsequent signature message from the current signature message.


## 5.2.5. Traceability

The proposed scheme provides conditional identity privacy preservation in IoVs. TA tracked and revealed the real identity of the malicious vehicle from its database. When a malicious vehicle with forged messages is found, the real identity of the malicious vehicle can be traced by TA. TA, as a trust authority, cannot tamper the real identity and the pseudoidentityPIDi of a malicious vehicle because tupleH1i,PIDi,PIDis,Treg of the vehicle is recorded in a blockchain.


## 5.2.6. Cross-Domain Authentication

First, when the vehicleVi publishes a message Mi, it sends the signatureσi=Ai,Bi,Mp to the first RSU of Mi. If the verification is successful, a new transaction Tx2=H4iMiPIDiTi is generated and h5Tx2 is recorded on the blockchain and broadcasted to all the nodes. When other RSUs and vehicles in other RSUs receive the message Mi, they only need to look up the verification information related to the message from the chain. Second, only the first RSU negotiates a random integer NRj with a vehicle Vi, and a transaction Tx1=PIDiVpubiLij with Lij=MVi−1NRj, PIDi, and Vpubi is recorded on the blockchain. Therefore, when the vehicle Vi enters the next RSU range, if a new message is to be published, there is no need to renegotiate the random number.


## 5.2.7. Resilience to Other Attacks

(1) Impersonation Attack. In order to impersonate a registered vehicle, the enemy needs a valid signature for message Mi. Therefore, NP=NRjP, H4i=h4NPMiPIDiTi, Bi=biP,MP=MViP, and Ai=NRj⋅pski+xi+biH4i need to be calculated, where NRj is an integer to ensure the integrity of the transaction content negotiated between vehicle Vi and RSUj, and the adversary needs to know the private key used for signature. Therefore, in calculation, it is not feasible for the adversary to create another valid request message without knowing the above content. Therefore, the scheme is safe from vehicle simulation attacks.(2) Modification Attack. In the authentication phase, the freshness of the message is determined by the timestamp at the time of signing, and the message Mi,σi,PIDi,Ti sent by vehicle Vi has the timestamp Ti of the sender. Any nearby vehicle or RSU can check Ti to verify the freshness of the message. It prevents the message Mi,σi,PIDi,Ti from being repeatedly broadcast in the RSU domain, so the scheme protects against replay attacks.(3) Man-In-The-Middle Attack. Suppose an adversary intercepts a message Mi,σi,PIDi,Ti, and the adversary tries to create a valid signature in place of the vehicle to send to the RSU as an authentication request. However, it can be seen from the signature that the adversary needs to know NRj, bi, and MVi, and these parameters are embedded in the ECDLP difficulty problem, so the scheme is not subject to man-in-the-middle attack.(4) Replay Attack. For the signature σi=Ai,Bi,Mp of the message Mi and Ai=NRj⋅pski+xi+biH4i and H4i=h4NPMiPIDiTi, the message contains the current timestamp; when receiving a message, the RSU checks the validity of the message by comparing the received timestamp to the current timestamp. For valid message and its freshness, the difference between the timestamp should be a small value; therefore, by containing a timestamp in each message, one can ensure that the message is protected from replay attacks because no adversaries can successfully replay the intercepted message.


## 6. Performance Analysis

This section will give a function comparison, then analyze and calculate the communication costs of our scheme and related schemes, and make experimental simulation and analysis.In Table2, we first give a simplified comparison of functions between our scheme and other related schemes [3, 12, 19, 20] in terms of privacy, decentralization, multistorage, anonymity, unforgeability, and key escrow. We use the symbol “-” to represent that the corresponding property is not considered. In scheme [3], it realises the privacy protection, decentralization, multistorage, and anonymity of vehicles in the authentication process but does not provide unforgeability, nor could it avoid the key escrow. And in scheme [12], it does not consider decentralization and multistorage. The privacy protection, decentralization, and anonymity of vehicles are implemented in the scheme [19]. However, multistorage and key escrow are not considered. As to scheme [20], it achieved the privacy protection, decentralization, unforgeability, and avoided key escrow but did not have multistorage and anonymity. As shown in Table 2, our scheme satisfies all the above functions.Table 2
Function comparison.
SchemePrivacyDecentralizationMultistorageAnonymityUnforgeabilityKey escrowZheng et al. [3]YesYesYesYes-YesMalhi and Batra [12]Yes--YesYesNoBagga et al. [19]YesYesNoYesYesYesRen et al. [20]YesYesNoNoYesNoOursYesYesYesYesYesNo


### 6.1. Computational Cost Analysis

In terms of computational overhead, we analyze our scheme and compare it with the recent correlative signature schemes [3, 12, 19, 20] for signature generation and verification in V2I communication.We use a MIRACL simulation library in VS 2019. The simulation environment is Win1064 bit, and the hardware environment is Intel Core i5 3.10 GHz.Tbp denotes the execution time of a bilinear pairing operation, Tsm denotes the execution time of a scalar multiplication operation in G1, Tpa denotes the execution time of a point addition operation in G1, Tpm denotes the execution time of a point multiplication operation in G1, and hash operation is not considered for its low load. The addition and multiplication of points on an elliptic curve are performed under a nonsingular elliptic curve y2=x3+ux+vmodq, where 4u3+27v2≠0modq.Table3 shows the computation costs of the proposed scheme and schemes [12, 19, 20] in the signature and verification stage. As for scheme [3], it is defaulted that only legal vehicles can publish messages. Therefore, vehicles only submit messages without signing and RSU does not need to perform identity verification. Because only hash operation is included, the computation is very low, but this is exactly a security vulnerability. In [12], users need to perform four scalar multiplication operations and two point addition operations at the signing stage; that is, users need 4Tsm+2Tpa in total and RSUs need 3Tbp+3Tsm+Tpa. The computation cost is 3Tpm+3Tpa, 3Tbp+5Tpm+Tpa, 2Tsm, and 2Tbp+Tpa in [19, 20], respectively. Our proposed scheme needs three point multiplication operations on elliptic curves and one scalar multiplication (i.e., 3Tpm+2Tsm) in the signature process. In the verification process, the computational cost is 5Tpm+2Tpa. Our scheme is built on elliptic curves with less computation overhead. There is no bilinear pairing operation with higher computation overhead in the signature and verification phase. Only point and multiplication operations with lower computation overhead are used. Therefore, the computation overhead of this scheme is better than the other three schemes in the signature and verification phase.Table 3
Computation cost comparison.
SchemeSign (ms)Verify (ms)Zheng et al. [3]--Malhi and Batra [12]4Tsm+2Tpa3Tbp+3Tsm+TpaBagga et al. [19]3Tpm+3Tpa3Tbp+5Tpm+TpaRen et al. [20]2Tsm2Tbp+TpaOurs3Tpm+2Tsm5Tpm+2Tpa


### 6.2. Communication Cost Analysis

To analyze the communication overhead of the proposed scheme and the related signature schemes [12, 19, 20], we analyze the communication overhead by considering the size of parameters. At the security level of 80 bytes, the p−length equation E:y2≡x3+xmodp is 64 bytes, and the elements on the circle group G occupy 128 bytes. We consider the size of the timestamp to be 4 bytes and the size of the normal hash function to be 20 bytes. Table 4 shows the communication costs of the proposed scheme and schemes [3, 12, 19, 20]. As can be seen from Table 4, the communication overhead of Zheng et al. is the lowest in these five schemes because only message is transmitted without signature. Then, our scheme is significantly lower than that of Bagga et al. and Ren et al. Although the communication cost of the proposed scheme is the same as that of Malhi and Batra, the computation is significantly lower than that of Malhi and Batra. Therefore, our scheme has more communication advantages.Table 4
Communication cost comparison.
SchemeSingle-Msg.n-Msg.Zheng et al. [3]316bytes316nbytesMalhi and Batra [12]536bytes536nbytesBagga et al. [19]664bytes664nbytesRen et al. [20]660bytes660nbytesOurs536bytes536nbytes


### 6.3. Experimental Simulation and Analysis

This section uses the MIRACL library to test the computation costs in Table3 in Visual Studio 2019. Figures 8 and 9 show the relationship between the number of message and the time consumed by the proposed scheme and the other three schemes in the signing and authentication process. It can be seen from Figures 8 and 9 that our scheme has no significant advantages in the signature phase but has obvious advantages in the verification phase, because in our scheme, only the message needs to be authenticated, rather than the vehicle identity needs to be authenticated. Specifically, the vehicle identity information is authenticated by the first RSU, and transactions are recorded permanently and immutably in the blockchain to reduce the repeated authentication load of other RSUs.Figure 8
Signature phase computation costs.Figure 9
Validation phase computation costs.Through theoretical analysis and simulation experiments, it is intuitive to see that with the increase of messages, the proposed scheme has certain efficiency advantages over the schemes [12, 19, 20].The packet loss rate and delay are tested according to the time and traffic of the scheme in the signature and verification stage. A scenario is simulated by using VanetMobiSim and NS-2, as shown in Figure10. The scenario is divided into four parts, and each part is managed by an RSU. The vehicle speed is controlled between 7 m/s and 45 m/s, the communication range is 400 m, the message interval is 80 ms, and the data packet sizes are 536 bytes, 664 bytes, 660 bytes, and 536 bytes, respectively.Figure 10
Scene simulation diagram.When testing the packet loss rate and time delay, set the number of vehicles to gradually increase from 5 to 95. The simulation results of packet loss rate are shown in Figure11. The packet loss rate in the four schemes is also gradually increasing as the increase of the number of vehicles. When the quantity of vehicles reaches a certain number, the packet loss rate tends to be stable. Compared with the other three schemes, our scheme has the lowest packet loss rate, which shows that our scheme has high efficiency. The delay results are shown in Figure 12. Although the delay of the four schemes increases gradually, the delay of our scheme is the smallest. Therefore, the communication timeliness of our schemer is higher than that of the other three schemes.Figure 11
Packet loss rate comparison.Figure 12
Delay comparison.To sum up, through theoretical analysis and simulation experiments, our scheme has certain advantages in traffic, computation, packet loss rate, and delay, so it is suitable for the IoVs with high security and high efficiency requirements.


## 6.1. Computational Cost Analysis

In terms of computational overhead, we analyze our scheme and compare it with the recent correlative signature schemes [3, 12, 19, 20] for signature generation and verification in V2I communication.We use a MIRACL simulation library in VS 2019. The simulation environment is Win1064 bit, and the hardware environment is Intel Core i5 3.10 GHz.Tbp denotes the execution time of a bilinear pairing operation, Tsm denotes the execution time of a scalar multiplication operation in G1, Tpa denotes the execution time of a point addition operation in G1, Tpm denotes the execution time of a point multiplication operation in G1, and hash operation is not considered for its low load. The addition and multiplication of points on an elliptic curve are performed under a nonsingular elliptic curve y2=x3+ux+vmodq, where 4u3+27v2≠0modq.Table3 shows the computation costs of the proposed scheme and schemes [12, 19, 20] in the signature and verification stage. As for scheme [3], it is defaulted that only legal vehicles can publish messages. Therefore, vehicles only submit messages without signing and RSU does not need to perform identity verification. Because only hash operation is included, the computation is very low, but this is exactly a security vulnerability. In [12], users need to perform four scalar multiplication operations and two point addition operations at the signing stage; that is, users need 4Tsm+2Tpa in total and RSUs need 3Tbp+3Tsm+Tpa. The computation cost is 3Tpm+3Tpa, 3Tbp+5Tpm+Tpa, 2Tsm, and 2Tbp+Tpa in [19, 20], respectively. Our proposed scheme needs three point multiplication operations on elliptic curves and one scalar multiplication (i.e., 3Tpm+2Tsm) in the signature process. In the verification process, the computational cost is 5Tpm+2Tpa. Our scheme is built on elliptic curves with less computation overhead. There is no bilinear pairing operation with higher computation overhead in the signature and verification phase. Only point and multiplication operations with lower computation overhead are used. Therefore, the computation overhead of this scheme is better than the other three schemes in the signature and verification phase.Table 3
Computation cost comparison.
SchemeSign (ms)Verify (ms)Zheng et al. [3]--Malhi and Batra [12]4Tsm+2Tpa3Tbp+3Tsm+TpaBagga et al. [19]3Tpm+3Tpa3Tbp+5Tpm+TpaRen et al. [20]2Tsm2Tbp+TpaOurs3Tpm+2Tsm5Tpm+2Tpa


## 6.2. Communication Cost Analysis

To analyze the communication overhead of the proposed scheme and the related signature schemes [12, 19, 20], we analyze the communication overhead by considering the size of parameters. At the security level of 80 bytes, the p−length equation E:y2≡x3+xmodp is 64 bytes, and the elements on the circle group G occupy 128 bytes. We consider the size of the timestamp to be 4 bytes and the size of the normal hash function to be 20 bytes. Table 4 shows the communication costs of the proposed scheme and schemes [3, 12, 19, 20]. As can be seen from Table 4, the communication overhead of Zheng et al. is the lowest in these five schemes because only message is transmitted without signature. Then, our scheme is significantly lower than that of Bagga et al. and Ren et al. Although the communication cost of the proposed scheme is the same as that of Malhi and Batra, the computation is significantly lower than that of Malhi and Batra. Therefore, our scheme has more communication advantages.Table 4
Communication cost comparison.
SchemeSingle-Msg.n-Msg.Zheng et al. [3]316bytes316nbytesMalhi and Batra [12]536bytes536nbytesBagga et al. [19]664bytes664nbytesRen et al. [20]660bytes660nbytesOurs536bytes536nbytes


## 6.3. Experimental Simulation and Analysis

This section uses the MIRACL library to test the computation costs in Table3 in Visual Studio 2019. Figures 8 and 9 show the relationship between the number of message and the time consumed by the proposed scheme and the other three schemes in the signing and authentication process. It can be seen from Figures 8 and 9 that our scheme has no significant advantages in the signature phase but has obvious advantages in the verification phase, because in our scheme, only the message needs to be authenticated, rather than the vehicle identity needs to be authenticated. Specifically, the vehicle identity information is authenticated by the first RSU, and transactions are recorded permanently and immutably in the blockchain to reduce the repeated authentication load of other RSUs.Figure 8
Signature phase computation costs.Figure 9
Validation phase computation costs.Through theoretical analysis and simulation experiments, it is intuitive to see that with the increase of messages, the proposed scheme has certain efficiency advantages over the schemes [12, 19, 20].The packet loss rate and delay are tested according to the time and traffic of the scheme in the signature and verification stage. A scenario is simulated by using VanetMobiSim and NS-2, as shown in Figure10. The scenario is divided into four parts, and each part is managed by an RSU. The vehicle speed is controlled between 7 m/s and 45 m/s, the communication range is 400 m, the message interval is 80 ms, and the data packet sizes are 536 bytes, 664 bytes, 660 bytes, and 536 bytes, respectively.Figure 10
Scene simulation diagram.When testing the packet loss rate and time delay, set the number of vehicles to gradually increase from 5 to 95. The simulation results of packet loss rate are shown in Figure11. The packet loss rate in the four schemes is also gradually increasing as the increase of the number of vehicles. When the quantity of vehicles reaches a certain number, the packet loss rate tends to be stable. Compared with the other three schemes, our scheme has the lowest packet loss rate, which shows that our scheme has high efficiency. The delay results are shown in Figure 12. Although the delay of the four schemes increases gradually, the delay of our scheme is the smallest. Therefore, the communication timeliness of our schemer is higher than that of the other three schemes.Figure 11
Packet loss rate comparison.Figure 12
Delay comparison.To sum up, through theoretical analysis and simulation experiments, our scheme has certain advantages in traffic, computation, packet loss rate, and delay, so it is suitable for the IoVs with high security and high efficiency requirements.


## 7. Conclusion and Future Research

On the basis of the scheme [3], we put forward an effective cross-domain certificateless anonymous authentication scheme based on blockchain by using pairing-free signature verification scheme. Our scheme reduces the computing cost of signature verification on RSUs, solves the key escrow problem in traditional authentication scheme, and improves the efficiency of V2I communication. In addition, the blockchain built by RSUs is introduced to the scheme, the vehicle identity and messages realise cross-domain authentication through a random integer negotiation process, and the blockchain stores the identity information of the vehicle and the authentication results of the signature. As a result, the load and delay caused by repeated identity and message authentication are prevented. Our scheme is provably secure and provides integrity, anonymity, privacy, traceability, revocation, and nonrepudiation. Experiments show that our scheme is efficient in terms of computation costs, latency, and packet loss rate for signature generation and verification.Compared with cloud computing, edge computing is very faster, reduces network latency, and is more reliable. Therefore, the future works are suggested to study anonymous authentication based on edge computing in IoVs.



---

*Source: 3488977-2022-11-21.xml*