# Secure Certificateless Authentication and Road Message Dissemination Protocol in VANETs

Authors: Haowen Tan; Dongmin Choi; Pankoo Kim; Sungbum Pan; Ilyong Chung
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

As a crucial component of Internet-of-Thing (IoT), vehicular ad hoc networks (VANETs) have attracted increasing attentions from both academia and industry fields in recent years. With the extensive VANETs deployment in transportation systems of more and more countries, drivers’ driving experience can be drastically improved. In this case, the real-time road information needs to be disseminated to the correlated vehicles. However, due to inherent wireless communicating characteristics of VANETs, authentication and group key management strategies are indispensable for security assurance. Furthermore, effective road message dissemination mechanism is of significance. In this paper, we address the above problems by developing a certificateless authentication and road message dissemination protocol. In our design, certificateless signature and the relevant feedback mechanism are adopted for authentication and group key distribution. Subsequently, message evaluating and ranking strategy is introduced. Security analysis shows that our protocol achieves desirable security properties. Additionally, performance analysis demonstrates that the proposed protocol is efficient compared with the state of the art.


---

## Body

## 1. Introduction

Vehicular ad hoc networks (VANETs) are distributed, self-organized wireless networks constructed by vehicles and nearby road-side units (RSUs). The real-time dynamic communication enables efficient and durative information exchange between vehicles and RSUs. Hence, intelligent transportation system (ITS) is achievable with the widely implementation of VANETs [1, 2]. A variety of VANET-based applications, which can be mainly classified into safety-related applications and commercial-oriented applications, not only enhance the driving safety but also provide better driving experience. Typical safety-related applications include emergency vehicle warnings, traffic congestion report, road accident informing, and speed monitoring [3, 4]. Commercial-oriented applications provide convenience service and entertainment applications such as weather forecast, information broadcasting of nearby petrol stations and restaurants, navigation, and Internet access.In general, a basic VANET consists of three important components: the trusted authority (TA), road-side units (RSUs), and vehicles [5–7]. Considered as both the application provider and key server, TA is responsible for providing various services to vehicles through RSUs. Moreover, pivotal secret key assignment, along with the user management for correlated vehicles, is conducted by TA. The RSUs are deployed by the road sides one after another. Commonly, RSUs are built aside the road in every kilometer. Thus the effective range of VANET system can cover each section of the road. In this case, RSUs are considered as the communication bridge connecting TA and vehicles, which provides timely transmission of vital personal data. To a certain degree, RSUs have the capability of conducting computation and storing essential information in its memories [8]. The vehicle performs as both terminal customer and information collector. In other words, useful information including traffic congestion and emergency road condition is forwarded to the corresponded RSU. Each vehicle is equipped with an onboard unit (OBU), which conducts all the computation and communication [9, 10]. Compared with regular wireless sensor networks [11], vehicle’s high mobility is the unique characteristic of VANETs.In VANETs, the data exchange between TA and RSUs are via secure wired connection, where the adopted cryptographic strategies guarantee transmission security and message confidentiality. Meanwhile, vehicle-to-vehicle (V2V) communication and vehicle-to-RSU (V2R) communication are conducted through open wireless channel, which employs the dedicated short-range communications (DSRC) [12–14]. On the one hand, the moving vehicle can carry out interactive data exchange with specific RSU through V2R communication. On the other hand, one vehicle is capable of sharing essential messages with other vehicles in its vicinity through V2V communication. In this way, a VANET with high connectivity can be built accordingly [15].As a particular variant of wireless sensor networks, apparently the VANETs suffer from multiple charted and uncharted security attacks [9, 14]. In V2V and V2R communications, the transmitted messages may be eavesdropped, blocked, or even forged by malicious devices. Hence, significant user information is revealed to the attacker accordingly, which compromises the whole VANET and brings severe user privacy disclosure issue [1, 13]. Under this circumstance, proper authentication strategies are required so as to provide security and privacy assurance. Moreover, high mobility feature of the vehicles brings uncertainty to the communication process, which should also be taken into consideration.Among the aforementioned safety-related applications, road message dissemination is one of the essential functions for VANET [16]. With the assistance of RSUs and remote server, the vehicles of the same VANET could share necessary driving-related information with each other. By analyzing the acquired traffic information of current areas, the driver is able to make better driving decisions such as choosing the best navigation route ahead of time. Furthermore, occurrences of road accidents and traffic jams can be drastically reduced [9]. Thus, the drivers’ driving experience is improved.In VANETs, typical road message management strategies are mainly composed of information collection and dissemination. First, the road messages are reported by the participating vehicles through OBUs [17]. Afterwards, the acquired messages will be processed and then disseminated to the legitimate vehicles. In some VANETs scenarios, TA arranges all the road messages collected from RSUs via wired transmission [18]. Meanwhile, in decentralized VANETs scenarios, most of the computation and storing are done in the RSU side [7], while TA performs as the key generation center (KGC). Consequently, in particular dense scenarios with large amounts of emerging vehicles, the decentralized architecture could reduce the computation overload and storage complexity in TA.As described above, authentication strategies are necessary during road message dissemination [4, 19]. Furthermore, the characteristic group communication between RSU and vehicles is indispensable, which enables convenient data exchange. In this case, the group key shared between RSU and all the legitimate vehicles is required. Note that the group key distribution should be conducted after mutual authentication [6, 20].As for message dissemination in practical VANETs occasions, two channels are required [21], namely, the official channel and normal channel. Official channel is provided by governmental agencies, where the broadcast road information is precise and trustworthy. Note that this channel is assumed to be based on real-time monitoring with satellites and road cameras. Thus it is precise and trustworthy. Meanwhile, normal channel is the more ordinary way, where the road information is gathered from normal vehicles. In this case, some of the vehicles are assumed to be benign devices which transmit precise messages, while the rest are negative vehicles [22]. Note that the negative vehicles may report trivial or even false information to the VANET system. For this consideration, with the purpose of guaranteeing the dissemination exactitude, impartial and effective message evaluation mechanism is necessary [23]. For instance, in extreme scenarios with massive road messages to be disseminated, before dissemination, it is necessary for the RSUs to aggregate and evaluate the acquired road messages before dissemination. Hence the RSUs could broadcast in a particular sequence according to the significance and reliability of each message. Urgent and authentic road messages can be broadcast in the first place.During the message dissemination of the entire VANETs, the accuracy and efficiency of message dissemination closely depend on the participating vehicles [15, 24]. Hence, it is vital to deploy appropriate rewarding strategy so as to motivate the drivers’ enthusiasm on reporting [20, 25]. For example, coupons or discounts on certain commodities can be granted to the trustworthy drivers with timely and precise reporting records. In other words, the drivers are encouraged with incentives, which is of great benefit to the entire VANET.In this paper, we propose a secure certificateless authentication and road message dissemination protocol in vehicular ad hoc networks. Our nontrivial efforts can be summarized as follows:(i) Secure Certificateless Authentication Scheme for Group Key Distribution. With the purpose of enhancing transmission security, we adopt the bilinear pairing based on elliptic curve into our authentication scheme. Hence, the active vehicles within the effective range can be identified and then allocated with the group key. The proposed scheme yields desirable security properties.(ii) Road Message Priority Management and Dissemination Mechanism. The encrypted road messages are delivered to the corresponding RSU. The received road message is evaluated based on both the vehicle priority and the assessment. In this way, accuracy and efficiency of the messages dissemination process are provided. Hence, the drivers can timely arrange their routes according to the delivered road information.(iii) Security and Performance Analysis. The formal security analysis is provided, involving some necessary proofs on resistance to the existing malicious attacks. Furthermore, performance analysis emphasizing the transmission overload and computation cost is hereby presented.The remainder of this paper is organized as follows. Section2 provides brief description of the related research achievements. Section 3 introduces some necessary preliminary works and the designed system model in order for the reader to obtain better understanding of this topic. Section 4 presents the proposed secure certificateless authentication scheme in detail. Section 5 describes the proposed road message dissemination scheme. Section 6 demonstrates the security analysis. Section 7 displays the performance analysis. The conclusion is drawn in Section 8.


## 2. Related Work

In order to provide enhanced authentication and secure transmission in VANETs, various cryptographic techniques have been deployed in existing researches [2, 3, 6, 16, 26–28]. In 2009, Studer et al. [3] developed a hybrid VANET authentication mechanism (VAST) based on the elliptic curve digital signature algorithm (ECDSA) [29] and TESLA [30] with the purpose of providing fast and extensible authentication and nonrepudiation. Subsequently, emphasizing group authentication and conditional privacy, Zhang et al. [26] proposed a scalable decentralized group authentication protocol, where certain vehicle is able to verify anonymous messages from neighboring vehicles. Motivated by chameleon hash signature based on elliptic curve, in 2011, Huang et al. [27] designed pseudonymous authentication-based conditional privacy protocol (PACP), which adopts the pseudonyms for anonymous communication. Similarly, ABAKA [6] with batch verification was proposed by Huang et al. After that, Lu et al. [28] presented a dynamic privacy-preserving key management scheme (DIKE) enabling both vehicle anonymous authentication and double-registration detection. Guo et al. [2] designed a privacy-preserving anonymous authentication protocol with vehicle unlinkability and authority trackability in 2014, where high efficiency and desired security properties can be achieved accordingly. Afterwards, multiple authentication and group key management protocols in VANETs have been designed recently [8, 31].Specifically, identity-based encryption, which was first presented by Shamir [33] for certificate management of KGC, has been widely implemented in VANETs authentication protocols. In 2007, Lin et al. [34] combined group signature with identity-based cryptography in the proposed GSIS protocol. Hence, appropriate traceability toward specific vehicle is achieved. After that, Zhang et al. [15] designed an identity-based batch signature verification scheme in VANETs, where multiple signatures can be simultaneously verified in one RSU. Nevertheless, this scheme suffers from replay attack [35]. Subsequently, Sun et al. [5] constructed an identity-based security framework in order to address the misbehavior issue in VANET system. In 2012, Shim [9] developed an identity-based conditional privacy-preserving authentication scheme (CPAS) supporting fast batch verification. However, the proposed protocol is vulnerable to modification attack [36]. Another signature scheme for VANETs, named EIBS [37], was proposed in 2015, where the RSUs perform as the certificate verifiers in order to decrease the computation overload in TA side. Moreover, the anonymity of the legitimate vehicle is provided by using pseudo identity instead of real identity. Hence, the vehicle privacy is preserved. Aiming to decrease the computational complexity, He et al. [10] designed an identity-based conditional privacy-preserving authentication scheme in VANETs. With relatively limited computation and communication requirements, the proposed protocol is suitable for practical VANETs applications.With the purpose of addressing the key escrow issue in identity-based public key cryptography system (ID-PKC), certificateless public key cryptography (CL-PKC) was first introduced by Al-Riyami and Paterson [38] in 2003. In CL-PKC design, the private partial keys are, respectively, generated by the semitrusted key generation center (KGC) and the user itself. Multiple certificateless authentication protocols were proposed afterwards [25, 39]. Thereafter, Li and Wang [17] presented a fast certificateless authentication scheme (RCS) employing bilinear pairing, where particular vehicles are selected as the assistance to the relevant RSUs. In this case, the transmission overload can be alleviated. Afterwards, Xiong and Qin proposed a certificateless encryption scheme and another certificateless signature scheme with efficient revocation against short-term key exposure in [40]. In 2016, Peng [1] designed an anonymous authentication protocol based on certificateless signature scheme, which provides conditional privacy and mutual authentication.Furthermore, as the crucial and unique feature of VANETs, message dissemination has been studied due to its promising advantages in both safety-related and commercial-oriented applications. Focusing on commercial advertisements dissemination, Tseng et al. [7] adopted Reed-Solomon Code in the incentive scheme through interactions between vehicles. Similarly, a cooperative message authentication scheme [18] is developed to alleviate the verification overload in the RSU side, where the legitimate vehicles are responsible for message verification in the vicinity. Thereafter, in order to achieve high reliability and low dissemination delay at the same time, density-aware emergency message extension protocol (DEEP) [22] is constructed. As illustrated, emergency warning messages can be timely delivered to all the vehicles within the operating range, which could drastically improve driving safety. As one of the significant services offered by VANETs, RSU-assisted navigation is studied by Chim et al. in [20]. In the assumption, the real-time road conditions are used to compute a better route for the requesting vehicles. The privacy of the drivers can be protected with the advantages of anonymous credential. In [23], Milojevic and Rakocevic developed a location-aware data aggregation mechanism for real-time observation and efficient message dissemination. The communication cost is minimized with the use of intelligent passive clustering and adaptive broadcasting. For improving the accuracy of the delivered message, the aggregated information is arranged by real-time spatiotemporal database refreshing. Recently, Liu et al. presented a cloud-assisted message downlink dissemination scheme (CMDS) under a developed VANET-cellular heterogeneous framework combining cloud computing [21, 41].


## 3. Model Definition and Preliminaries

In this section, some necessary preliminaries are introduced with the purpose of facilitating the readers’ understanding, including the definition of bilinear pairing and hash function. Subsequently, the corresponding notations, the system model, and network assumptions are illustrated.


### 3.1. Bilinear Pairing

LetGO and GN be two additive cyclic groups of a large prime order P. A map function e^:GO×GO→GN is a bilinear pairing if it satisfies the three properties below:(1)
Bilinear: for∀M,N∈GO and ∀a,b∈ZP∗, there is e^(aM,bN)=e^(M,N)ab. In addition, for ∀M,N,Y∈GO, there are e^(M+N,Y)=e^(M,Y)e^(N,Y) and e^(M,N+Y)=e^(M,N)e^(M,Y).(2)
Nondegeneracy: for∃M,N∈GO, there is e^(M,N)≠1.(3)
Computability: for∀M,N∈GO, there is an efficient algorithm to compute e^(M,N).In order to prove the security of our schemes, the following intractable problems are briefly presented as(1)
discrete logarithm problem (DLP): for∀M,N∈GO, it is difficult to find an integer a∈ZP∗, such that M=aN holds;(2)
computational Diffie-Hellman problem (CDHP): for∀M,aM,bM∈GO, it is difficult to compute abM;(3)
decisional Diffie-Hellman problem (DDHP): for∀M,aM,bM,cM∈GO and ∀a,b,c∈ZP∗, it is difficult to decide whether c=abmodP holds;(4)
pairing inversion problem (PIP): for a pairinge^ and ∀c∈ZP∗, it is difficult to find M,N∈GO, such that e^(M,N)=c holds.


### 3.2. Hash Function

A one-way hash function is considered to be secure if the following properties can be satisfied [42]:(1)
Inputting a messagex of arbitrary length, it is easy to compute a message digest of a fixed length output h(x).(2)
Giveny, it is difficult to compute x=h-1(y).(3)
Givenx, it is computationally infeasible to find x′≠x such that h(x′)=h(x) holds.


### 3.3. Notations

The notations and the brief description are listed in Notations.


### 3.4. System Model

The structure of VANET system of our design is shown in Figure1, where the whole VANET system is composed of three entities: the trusted authority (TA), the road-side units (RSUs), and the vehicles. Descriptions of these entities are, respectively, illustrated below.Figure 1
System Model.Trusted Authority (TA) is a trustworthy management center in charge of all the involving RSUs and vehicles. The vital system operations, including vehicle registration, assignment, and secret key generation, are all conducted by TA. Additionally, TA stores the significant user data in its memory. Hence, TA is assumed to have adequate storage and computing capability. Moreover, performing as both the trustworthy verifier and key generation center, TA is infeasible to be compromised by the adversaries. Thus various services can be securely presented to the designated vehicles. In this case, the group key is necessary for secure message exchange.Road-side units (RSUs) are vital VANET infrastructure implemented at the roadside, which perform as the sole intermediaries between TA and vehicles. RSUs are responsible for verifying the vehicles. Furthermore, the group key issued by TA will also be delivered by RSUs. Note that RSUs are assumed to have adequate storage in order to manage the acquired data. Hence, in our scheme, the gathered road messages are stored and managed in RSUs. In general, RSUs are connected with TA in a secure wired way. However, since the RSUs are placed along the roadside far from TA, it is possible that these RSUs may be physically compromised. In this case, the stored user information may be illegally acquired [20]. For this consideration, the RSUs are assumed to be semitrusted devices.Vehicles are referred to as terminal users of the VANET system. It is designed to be both service receiver and information collector. In other words, with the implemented OBU, each vehicle is able to receive the broadcasting messages. Meanwhile, the vehicle reports real-time road information to RSU wirelessly. In this case, it is essential to adopt effective cryptographic strategies in order to guarantee the secure transmission. Furthermore, each vehicle is equipped with a tamper-proof device (TPD), where the corresponding secrets and derived group key are stored. In our system model, each driver is relevant to certain vehicles during the registration to TA. Every time when the driver activates the vehicles, his/her fingerprint and the assigned certification card are verified. This way, the driver and the correlative vehicle are closely connected. Consequently, for better description, the driver, the OBU, and the vehicle are considered the same entity in this paper.


### 3.5. Network Assumption

As illustrated in Figure1, TA manages all the operative RSUs of the VANET system through wired communication. Various safe strategies deployed for TA-RSU communication guarantee the security of the key data exchange. Therefore, the vehicle secret keys can be securely delivered to the correlative RSUs. However, it is possible that some RSUs are compromised physically since they are far from the TA. In this way, the distributed vehicle secret keys are illegally acquired by the adversaries, which could damage both the VANET system and the user privacy. Considered as semitrusted devices, it is not appropriate for the RSUs to manage all the vehicle-related secret keys. As a result, we assume in this paper the TA-RSU communication channel is safe for data transmission, while the RSU itself may be damaged, which results in vehicle information disclosure.Two types of wireless communication are displayed in the proposed system model, including the vehicle-to-vehicle communication (V2V) and the vehicle-to-RSU communication (V2R). Due to the inherent wireless transmission characteristics, both V2V and V2R communication suffer from charted and uncharted attacks. In a nutshell, the V2V communication is used for information sharing and cooperative data processing between the neighboring vehicles. While the V2R communication emphasizes longitudinal message acquisition and feedback between vehicle and RSU. Note that in our scheme the operative vehicles safely exchange messages with RSUs on road condition using the derived group key.


## 3.1. Bilinear Pairing

LetGO and GN be two additive cyclic groups of a large prime order P. A map function e^:GO×GO→GN is a bilinear pairing if it satisfies the three properties below:(1)
Bilinear: for∀M,N∈GO and ∀a,b∈ZP∗, there is e^(aM,bN)=e^(M,N)ab. In addition, for ∀M,N,Y∈GO, there are e^(M+N,Y)=e^(M,Y)e^(N,Y) and e^(M,N+Y)=e^(M,N)e^(M,Y).(2)
Nondegeneracy: for∃M,N∈GO, there is e^(M,N)≠1.(3)
Computability: for∀M,N∈GO, there is an efficient algorithm to compute e^(M,N).In order to prove the security of our schemes, the following intractable problems are briefly presented as(1)
discrete logarithm problem (DLP): for∀M,N∈GO, it is difficult to find an integer a∈ZP∗, such that M=aN holds;(2)
computational Diffie-Hellman problem (CDHP): for∀M,aM,bM∈GO, it is difficult to compute abM;(3)
decisional Diffie-Hellman problem (DDHP): for∀M,aM,bM,cM∈GO and ∀a,b,c∈ZP∗, it is difficult to decide whether c=abmodP holds;(4)
pairing inversion problem (PIP): for a pairinge^ and ∀c∈ZP∗, it is difficult to find M,N∈GO, such that e^(M,N)=c holds.


## 3.2. Hash Function

A one-way hash function is considered to be secure if the following properties can be satisfied [42]:(1)
Inputting a messagex of arbitrary length, it is easy to compute a message digest of a fixed length output h(x).(2)
Giveny, it is difficult to compute x=h-1(y).(3)
Givenx, it is computationally infeasible to find x′≠x such that h(x′)=h(x) holds.


## 3.3. Notations

The notations and the brief description are listed in Notations.


## 3.4. System Model

The structure of VANET system of our design is shown in Figure1, where the whole VANET system is composed of three entities: the trusted authority (TA), the road-side units (RSUs), and the vehicles. Descriptions of these entities are, respectively, illustrated below.Figure 1
System Model.Trusted Authority (TA) is a trustworthy management center in charge of all the involving RSUs and vehicles. The vital system operations, including vehicle registration, assignment, and secret key generation, are all conducted by TA. Additionally, TA stores the significant user data in its memory. Hence, TA is assumed to have adequate storage and computing capability. Moreover, performing as both the trustworthy verifier and key generation center, TA is infeasible to be compromised by the adversaries. Thus various services can be securely presented to the designated vehicles. In this case, the group key is necessary for secure message exchange.Road-side units (RSUs) are vital VANET infrastructure implemented at the roadside, which perform as the sole intermediaries between TA and vehicles. RSUs are responsible for verifying the vehicles. Furthermore, the group key issued by TA will also be delivered by RSUs. Note that RSUs are assumed to have adequate storage in order to manage the acquired data. Hence, in our scheme, the gathered road messages are stored and managed in RSUs. In general, RSUs are connected with TA in a secure wired way. However, since the RSUs are placed along the roadside far from TA, it is possible that these RSUs may be physically compromised. In this case, the stored user information may be illegally acquired [20]. For this consideration, the RSUs are assumed to be semitrusted devices.Vehicles are referred to as terminal users of the VANET system. It is designed to be both service receiver and information collector. In other words, with the implemented OBU, each vehicle is able to receive the broadcasting messages. Meanwhile, the vehicle reports real-time road information to RSU wirelessly. In this case, it is essential to adopt effective cryptographic strategies in order to guarantee the secure transmission. Furthermore, each vehicle is equipped with a tamper-proof device (TPD), where the corresponding secrets and derived group key are stored. In our system model, each driver is relevant to certain vehicles during the registration to TA. Every time when the driver activates the vehicles, his/her fingerprint and the assigned certification card are verified. This way, the driver and the correlative vehicle are closely connected. Consequently, for better description, the driver, the OBU, and the vehicle are considered the same entity in this paper.


## 3.5. Network Assumption

As illustrated in Figure1, TA manages all the operative RSUs of the VANET system through wired communication. Various safe strategies deployed for TA-RSU communication guarantee the security of the key data exchange. Therefore, the vehicle secret keys can be securely delivered to the correlative RSUs. However, it is possible that some RSUs are compromised physically since they are far from the TA. In this way, the distributed vehicle secret keys are illegally acquired by the adversaries, which could damage both the VANET system and the user privacy. Considered as semitrusted devices, it is not appropriate for the RSUs to manage all the vehicle-related secret keys. As a result, we assume in this paper the TA-RSU communication channel is safe for data transmission, while the RSU itself may be damaged, which results in vehicle information disclosure.Two types of wireless communication are displayed in the proposed system model, including the vehicle-to-vehicle communication (V2V) and the vehicle-to-RSU communication (V2R). Due to the inherent wireless transmission characteristics, both V2V and V2R communication suffer from charted and uncharted attacks. In a nutshell, the V2V communication is used for information sharing and cooperative data processing between the neighboring vehicles. While the V2R communication emphasizes longitudinal message acquisition and feedback between vehicle and RSU. Note that in our scheme the operative vehicles safely exchange messages with RSUs on road condition using the derived group key.


## 4. Proposed Secure Certificateless Authentication Scheme

In a nutshell, two principal factors are taken into consideration in this paper: the secure authentication and road message management mechanism, which will be, respectively, discussed in two sections. In this section, we describe the proposed secure certificateless authentication scheme between RSU and vehicles. The proposed scheme can be clarified into three different phases, includinginitialization phase,authentication phase, andgroup key distribution phase. Accordingly, some nontrivial preparations are made in the initialization phase. Subsequently, verification on the vehicles is conducted in the following authentication phase. Finally, the generated group key is allocated to the legitimate vehicle.Our design adopts the certificateless encryption strategy based on elliptic curve cryptography (ECC). Note that the corresponding public keys have been previously revealed to the devices. Meanwhile, the confidential information is assigned to vehicle during registration. Based on this, the adopted cryptographic techniques are available, which could provide adequate security assurance for the VANET system. Emphasizing the authentication between RSU and vehicle, we describe our scheme in the scenario involving single RSU and single vehicle. Note that the scheme for regular VANET scenarios with multiple RSUs and vehicles is similar.


### 4.1. Initialization Phase

Necessary preliminary works are conducted in the initialization phase, which can be generally classified into user registration and key information allocation. It is desirable that each vehicle should register to TA first. After that, TA assigns the secret information to the corresponding vehicle. Moreover, TA stores the drivers’ personal information such as the car plate number, the contact information, and the address. LetQH be the generator of a cyclic additive group GH and id be the unique identifier for vehicle. Additionally, TA adopts secure hash functions h:{0,1}∗×GH→ZP∗, where ZP∗ is defined as a nonnegative integer set less than the large prime number P. Hence, TA generates the secret key Rid for each vehicle illustrated as(1)Rid=hid,QH,which is allocated to the relevant vehicle after user registration. Note that the secret keys of all the registered vehicles are securely stored in TA’s database. At the same time, TA chooses a random integer sRSU∈ZP∗ as the RSU private key. Let G1 be the cyclic additive group generated by P with the order q. Hence the RSU public key can be computed according to(2)QRSU=sRSUP.It is worth noting that the RSU public key QRSU, the generator P, the hash function h, and G1 will be published to all the devices, while the private key sRSU is kept secret during the entire process.Now we assume that the registered vehicle approaches the working range of a fixed RSU. If certain vehicle wants to receive services from the VANET system, identification and key assignment are essential. In this assumption, the vehicle choosessv∈ZP∗ as its partial private key. Then the corresponding partial public key Qv is defined as(3)Qv=svP,where P is the system parameter as mentioned above. Subsequently, Request,Qv,id are delivered to RSU.After deriving the partial public keyQv, RSU requests TA for the secret key Rid of vehicle id. Let H:{0,1}∗×G1→G1 denote the secure hash function. Related computations can be conducted for partial key generation as follows:(4)Qid=Hid,QRSUC=RidsRSUQid.Thereafter, the generated C is delivered to vehicle. Hence the vehicle derives the partial private key su according to(5)su=Rid-1C=sRSUQid.At this point, the public key set for vehicle can be displayed asQv,id. Meanwhile, the relevant private key set is defined as sv,su. Note that the two partial private keys are, respectively, decided by RSU and vehicle. In other words, RSU has no access to sv, so that the privacy protection based on certificateless cryptography is achieved even if RSU is compromised by attackers.


### 4.2. Authentication Phase

After initialization, RSU conducts authentication on the requesting vehicle. In certain time pointt, we assume that vehicle starts to use the road message service. Then the following computation is conducted:(6)Q1=tQv=tsvP,which combines the current time with the partial public key. In addition, let G2 be the cyclic group of prime order s and e^:G1×G1→G2 be the bilinear pairing operator. Hence the vehicle gets the intermediate value Qid by(7)Qid=Hid,QRSU,where the vehicle identity id and RSU public key QRSU are known to vehicle. Subsequently, two necessary parameters r and v are generated as(8)r=e^QRSU,Qidv=ht∥r,Rid,where Rid is the secret key previously allocated to vehicle in the initialization. Accordingly, the signature U is generated based on(9)U=tvsvQid+su.At this point, vehicle sendsid,t,v,U to the RSU. In the RSU side, the validity of the received t and v will be verified first. Then RSU computes whether(10)r=?e^P,Ue^Q1,Qidvholds. The correctness is elaborated as follows:(11)e^P,Ue^Q1,Qidv=e^P,tvsvQid+sue^tQv,Qidv=e^P,ht∥r,RidtsvQid+sRSUQide^Qv,tQidht∥r,Rid=e^P,ht∥r,RidtsvQid+sRSUQide^svP,tQidht∥r,Rid=e^P,ht∥r,RidtsvQid+sRSUQide^P,tsvQidht∥r,Rid=e^P,ht∥r,RidtsvQide^P,sRSUQide^P,tsvQidht∥r,Rid=e^P,tsvQidht∥r,Ride^P,sRSUQide^P,tsvQidht∥r,Rid=e^P,sRSUQid=e^sRSUP,Qid=e^QRSU,Qid.If the delivered signature U passes the above verification, the validity of the requesting vehicle can be guaranteed. Thereafter, the authentication phase is completed.


### 4.3. Group Key Distribution Phase

After the authentication phase, the generated group key is distributed to the legitimate vehicle. It is worth emphasizing that the group key is assumed to be chosen by TA. Meanwhile, the key is delivered to RSUs in a secure way. In this way, when a certain vehicle travels from the effective range of one RSU to the next, the group key is always effective and can be continuously used.We assume that the secretK∈ZP∗ is randomly chosen by TA and then delivered to RSU. In certain time point T, RSU computes(12)W=KTQvF=hW∥v,suand sends W,F,T to vehicle. Note that the RSU could generate the partial private key su using the known information. In this way, the secret K is combined with current time stamp T and previously acquired intermediate value v.Similarly, the vehicle first compares the received valueF with the stored one. If F is valid, vehicle derives the secret by computing(13)N=T-1sv-1W=T-1sv-1KTQv=T-1Tsv-1svKP=KP.At this point, the final group key gk can be acquired according to(14)gk=hN=hKP.Therefore, the group key gk is successfully allocated to the legitimate vehicle. Note that gk will be used in the subsequent communication such as road message dissemination, reporting, and evaluation. The delivered packet format is as follows:(15)type,EgkERidm∥id∥TS,TS,where the transmitted message m is symmetrically encrypted using both Rid and the group key gk. Similarly, the current time stamp denoted as TS is adopted in the encryption. Note that Ex(y) represents the symmetric encryption on y using secret key x. Additionally, type indicates the type of m. For security consideration, the communication between vehicle and RSU adopts the assigned group key gk for encryption.


## 4.1. Initialization Phase

Necessary preliminary works are conducted in the initialization phase, which can be generally classified into user registration and key information allocation. It is desirable that each vehicle should register to TA first. After that, TA assigns the secret information to the corresponding vehicle. Moreover, TA stores the drivers’ personal information such as the car plate number, the contact information, and the address. LetQH be the generator of a cyclic additive group GH and id be the unique identifier for vehicle. Additionally, TA adopts secure hash functions h:{0,1}∗×GH→ZP∗, where ZP∗ is defined as a nonnegative integer set less than the large prime number P. Hence, TA generates the secret key Rid for each vehicle illustrated as(1)Rid=hid,QH,which is allocated to the relevant vehicle after user registration. Note that the secret keys of all the registered vehicles are securely stored in TA’s database. At the same time, TA chooses a random integer sRSU∈ZP∗ as the RSU private key. Let G1 be the cyclic additive group generated by P with the order q. Hence the RSU public key can be computed according to(2)QRSU=sRSUP.It is worth noting that the RSU public key QRSU, the generator P, the hash function h, and G1 will be published to all the devices, while the private key sRSU is kept secret during the entire process.Now we assume that the registered vehicle approaches the working range of a fixed RSU. If certain vehicle wants to receive services from the VANET system, identification and key assignment are essential. In this assumption, the vehicle choosessv∈ZP∗ as its partial private key. Then the corresponding partial public key Qv is defined as(3)Qv=svP,where P is the system parameter as mentioned above. Subsequently, Request,Qv,id are delivered to RSU.After deriving the partial public keyQv, RSU requests TA for the secret key Rid of vehicle id. Let H:{0,1}∗×G1→G1 denote the secure hash function. Related computations can be conducted for partial key generation as follows:(4)Qid=Hid,QRSUC=RidsRSUQid.Thereafter, the generated C is delivered to vehicle. Hence the vehicle derives the partial private key su according to(5)su=Rid-1C=sRSUQid.At this point, the public key set for vehicle can be displayed asQv,id. Meanwhile, the relevant private key set is defined as sv,su. Note that the two partial private keys are, respectively, decided by RSU and vehicle. In other words, RSU has no access to sv, so that the privacy protection based on certificateless cryptography is achieved even if RSU is compromised by attackers.


## 4.2. Authentication Phase

After initialization, RSU conducts authentication on the requesting vehicle. In certain time pointt, we assume that vehicle starts to use the road message service. Then the following computation is conducted:(6)Q1=tQv=tsvP,which combines the current time with the partial public key. In addition, let G2 be the cyclic group of prime order s and e^:G1×G1→G2 be the bilinear pairing operator. Hence the vehicle gets the intermediate value Qid by(7)Qid=Hid,QRSU,where the vehicle identity id and RSU public key QRSU are known to vehicle. Subsequently, two necessary parameters r and v are generated as(8)r=e^QRSU,Qidv=ht∥r,Rid,where Rid is the secret key previously allocated to vehicle in the initialization. Accordingly, the signature U is generated based on(9)U=tvsvQid+su.At this point, vehicle sendsid,t,v,U to the RSU. In the RSU side, the validity of the received t and v will be verified first. Then RSU computes whether(10)r=?e^P,Ue^Q1,Qidvholds. The correctness is elaborated as follows:(11)e^P,Ue^Q1,Qidv=e^P,tvsvQid+sue^tQv,Qidv=e^P,ht∥r,RidtsvQid+sRSUQide^Qv,tQidht∥r,Rid=e^P,ht∥r,RidtsvQid+sRSUQide^svP,tQidht∥r,Rid=e^P,ht∥r,RidtsvQid+sRSUQide^P,tsvQidht∥r,Rid=e^P,ht∥r,RidtsvQide^P,sRSUQide^P,tsvQidht∥r,Rid=e^P,tsvQidht∥r,Ride^P,sRSUQide^P,tsvQidht∥r,Rid=e^P,sRSUQid=e^sRSUP,Qid=e^QRSU,Qid.If the delivered signature U passes the above verification, the validity of the requesting vehicle can be guaranteed. Thereafter, the authentication phase is completed.


## 4.3. Group Key Distribution Phase

After the authentication phase, the generated group key is distributed to the legitimate vehicle. It is worth emphasizing that the group key is assumed to be chosen by TA. Meanwhile, the key is delivered to RSUs in a secure way. In this way, when a certain vehicle travels from the effective range of one RSU to the next, the group key is always effective and can be continuously used.We assume that the secretK∈ZP∗ is randomly chosen by TA and then delivered to RSU. In certain time point T, RSU computes(12)W=KTQvF=hW∥v,suand sends W,F,T to vehicle. Note that the RSU could generate the partial private key su using the known information. In this way, the secret K is combined with current time stamp T and previously acquired intermediate value v.Similarly, the vehicle first compares the received valueF with the stored one. If F is valid, vehicle derives the secret by computing(13)N=T-1sv-1W=T-1sv-1KTQv=T-1Tsv-1svKP=KP.At this point, the final group key gk can be acquired according to(14)gk=hN=hKP.Therefore, the group key gk is successfully allocated to the legitimate vehicle. Note that gk will be used in the subsequent communication such as road message dissemination, reporting, and evaluation. The delivered packet format is as follows:(15)type,EgkERidm∥id∥TS,TS,where the transmitted message m is symmetrically encrypted using both Rid and the group key gk. Similarly, the current time stamp denoted as TS is adopted in the encryption. Note that Ex(y) represents the symmetric encryption on y using secret key x. Additionally, type indicates the type of m. For security consideration, the communication between vehicle and RSU adopts the assigned group key gk for encryption.


## 5. Proposed Road Message Dissemination Scheme

In this section, we describe the corresponding road message dissemination scheme in detail. Meanwhile, the message evaluation and award mechanism are presented.


### 5.1. Road Message Reporting

We assume the scenario that a specific vehicle with identityid is within the effective range of a RSU. Note that the vehicle has successfully passed the authentication and acquired the group key gk. Subsequently, in a certain time point TS, the vehicle passes through a particular spot where road event occurs. For example, when the vehicle passes through the road accident scene, the driver could consider this accident as a road message and report it to the RSU. According to (15) in previous section, the RSU gets the packet involving the encrypted message and the detailed time point TS. The decryption process is as follows.First, the decryption with group keygk is conducted in the RSU side according to (16)DgkEgkERidm∥id∥TS=ERidm∥id∥TS.Next, RSU checks the time stampTS with the derived one in order to ensure that the received message is timely and effective. Additionally, id of the vehicle is derived. According to the aforementioned design, the RSU acquires the relevant secret Rid in its storage so that the transmitted road message m can be acquired according to(17)m=DRidERidm.At this point, the RSU is aware of the identity information of the reporting vehicle. Hence, according toid, RSU requests TA for the vehicle priority parameter, which is considered as the initial element in the message management process. In practical scenario with multiple vehicles existing in one RSU’s effective range, it is possible that more than one vehicles report the same road message to TA. For example, two vehicles V1 and V2 may successively pass through a certain accident scene. Hence, both of them report this event to RSU. In this case, the RSU stores this road message m in its storage and assigns the broadcast priority br(m) for m, which can be calculated using the priority of the two reporting vehicles as follows:(18)brm=12prid1+prid2,where the identifiers of V1 and V2 are denoted as id1 and id2, respectively. Meanwhile, the priorities of the two vehicles are pr(id1) and pr(id2). The calculated br(m) here represents the broadcast priority right after the two vehicles report the message. Moreover, among all the vehicles, it is assumed that only V1 and V2 report m to RSU such that br(m) is achieved as the average value of all the reporting vehicles’ priority.In a nutshell, we assume that the vehicle setV={Vi∣i∈[1,n],n∈N∗} denotes the n legitimate vehicles that have already passed the authentication process conducted by the effective RSU. Among these n vehicles, the vehicle subset RPm={Vj∣j∈[1,g],g∈N∗∧g≤n} consists of all the g vehicles that report road message m. Note that the identity of Vj is denoted as idj. Hence, the broadcast priority is pr(idj) and RPm⊆V holds. It is assumed that the g vehicles report message following the sequence of V1,…,Vg. Moreover, the road event Eventmloc is denoted as follows:(19)Eventmloc=loc,type,cont,which indicates that Eventmloc happened in location loc and the detailed information is showed in cont. Moreover, the event type is defined as type. In this way, the road message m contains the essential elements of Eventmloc.In our assumption, afterEventmloc occurred, within certain time interval g vehicles will report the event to the RSU. Hence, after RSU receives the road report from V1 for the first time, the broadcast priority is computed as br(m)=pr(id1). Similarly, the broadcast priority after RSU receives the road report for k (1≤k≤g) times, and br(m) can be computed as(20)brm=1k∑i=1kpridi,which is defined as the average vehicle priorities of all the reporting vehicles. Hence after Δt, the broadcast priority for m is(21)brm=1g∑i=1gpridi.Practically, one RSU handles multiple different road messages simultaneously. Therefore, each message will be assigned a broadcast priority and then stored in the storage. In our design, the creditability and accuracy of the road message are highly related to the reporter’s previous records. And the vehicle priority is able to reflect this property properly. Consequently, RSU sorts all these messages so that the reliable messages will be broadcast first.


### 5.2. Road Message Dissemination

As illustrated in the above section, the RSU manages all the road information within its effective range. Periodically, RSU broadcasts the messages in certain sequence. Note that all the road messages are encrypted using the distributed group keygk. Hence, only the registered vehicles can get access to this service. The aforementioned broadcast priority br(m) is roughly decided by reliability of the reporting vehicles. In this way, a predefined parameter W is set as the minimum requirement for message dissemination. That is to say, the messages m will be broadcast only if br(m)≥W. Otherwise it will be considered as unreliable information and then temporarily disabled from the broadcast list. In this case, in future, if other vehicles report the same message, br(m) will be compared with W again. After a predefined time interval, if br(m)<W, RSU permanently deletes the message in its storage. Following the above procedure, vehicles could acquire road messages in an accurate way. Thus the driving security can be improved with this service.


### 5.3. Evaluation and Priority Management

For practical consideration, an appropriate evaluation mechanism towards the road messages is necessary. In this subsection, we describe the proposed evaluation and priority management scheme. The value of the stored road message is decided by not only the reputation of the reporter but also the message itself. In order to achieve this, we assume that the vehicles have the capability of evaluating the received road messages. Following the above assumptions, the vehicle subsetRVm={Vl∣l∈[1,f],f∈N∗} denotes f vehicles who receive the road message m within time interval ΔtRC. After Vl∈RVm approaches the location loc where the road event Eventmloc happened, Vl could evaluate whether the received road information is correct, which helps improve the road report accuracy. The format of the evaluation message is as follows:(22)type,EgkEsuifNO∥assess∥id∥TSev,TSev,where the message type denoted as type here indicates that it is an evaluation message. ifNO denotes the assigned information number for message m. In addition, TSev is the current time stamp. Note that this evaluation will be sent back to RSU. According to(23)DgkEgkEsuifNO∥assess∥id∥TSev=EsuifNO∥assess∥id∥TSev,RSU checks the time stamp TSev with the derived one in order to ensure that the message is timely and effective. Additionally, id of the vehicle is derived. RSU acquires the relevant secret su in its storage so that the transmitted evaluation on message m can be acquired according to(24)DsuEsuifNO∥assess=ifNO∥assess.In this way, the evaluation can be combined tom according to ifNO. As a result, for road message m, the RSU could receive hm evaluation messages where hm≤f. For practical consideration, the assess can be analyzed using different state parameters such as sp∈{-2,-1,0,1,2}, where sp=2 means that assess is totally accurate and helpful, while sp=-2 means that assess is of no help and thus is considered as the fake message. The hm state parameters are {spu∣u∈[1,hm],u∈N∗}. During every certain period ΔtRD, RSU analyzes all the received evaluation messages and updates the broadcast priority following the steps below:(i)
Screening: firstly, RSU checks whether(25)RatemΔtRDspu>0≥Vholds, whereRatemΔtRD[spu>0] denotes the proportion of the received assess whose spu>0 among all the hm evaluation on m. Furthermore, V is the predefined system parameter according to different practical scenarios. In this case, if most of the users give negative assessments, m is considered as invalid information and must be discarded from the storage immediately.(ii)
Updating: secondly, the updating on broadcast priority is conducted as(26)br′m=brm+∑u=1hmpridu×spuhm=∑i=1gpridig+∑u=1hmpridu×spuhm,where[pr(idu)]u∈[1,hm] denotes the priority of hm vehicles.At this point, the updating process forΔtRD is completed. Similarly, after n time periods nΔtRD, the broadcast priority for m is(27)brnΔtRDm=∑i=1gpridig+∑i=1n∑u=1hmipridui×spuihmi,where hmi, pr(idui), and spui are the parameters in ith time periods iΔtRD. Note that the above process should be conducted for each stored road message in RSU. Hence, the broadcast sequence is updated. In future, after xΔtRD, m will be deleted if brxΔtRD(m)<N, where N is the preset system parameter.


### 5.4. Vehicle Priority Management

As illustrated above, the vehicle priority on vehicleid is pr(id), which is a significant user property in both the broadcast priority computing and updating processes. As a matter of fact, the reporting vehicle plays a crucial role in the message dissemination scheme. Hence, appropriate rewarding strategy is essential to motivate drivers’ enthusiasm on road situation reporting. The incentives will be given according to the vehicle priority. To achieve this, pr(id) will be updated according to the value of his reporting road message.We assume that road messagem is reported by several vehicles in B={vpi∣1≤i≤n,i∈N∗}. After a sufficient time period, for example, twenty-four hours, one road message m has been evaluated by multiple vehicles. According to (25) in the previous section, m is valid if(28)RatemΔtRDspu>0≥Vholds. In this way, pr(vpi) of all vpi∈B are updated as(29)prvpi=prvpi+1.In contrast, if m is evaluated to be invalid and discarded by RSU, pr(vpi) of all vpi∈B are updated as(30)prvpi=prvpi-1.Note that the driver could change it into incentives such as coupons of cooperative stores or scorecard in the road service area.


## 5.1. Road Message Reporting

We assume the scenario that a specific vehicle with identityid is within the effective range of a RSU. Note that the vehicle has successfully passed the authentication and acquired the group key gk. Subsequently, in a certain time point TS, the vehicle passes through a particular spot where road event occurs. For example, when the vehicle passes through the road accident scene, the driver could consider this accident as a road message and report it to the RSU. According to (15) in previous section, the RSU gets the packet involving the encrypted message and the detailed time point TS. The decryption process is as follows.First, the decryption with group keygk is conducted in the RSU side according to (16)DgkEgkERidm∥id∥TS=ERidm∥id∥TS.Next, RSU checks the time stampTS with the derived one in order to ensure that the received message is timely and effective. Additionally, id of the vehicle is derived. According to the aforementioned design, the RSU acquires the relevant secret Rid in its storage so that the transmitted road message m can be acquired according to(17)m=DRidERidm.At this point, the RSU is aware of the identity information of the reporting vehicle. Hence, according toid, RSU requests TA for the vehicle priority parameter, which is considered as the initial element in the message management process. In practical scenario with multiple vehicles existing in one RSU’s effective range, it is possible that more than one vehicles report the same road message to TA. For example, two vehicles V1 and V2 may successively pass through a certain accident scene. Hence, both of them report this event to RSU. In this case, the RSU stores this road message m in its storage and assigns the broadcast priority br(m) for m, which can be calculated using the priority of the two reporting vehicles as follows:(18)brm=12prid1+prid2,where the identifiers of V1 and V2 are denoted as id1 and id2, respectively. Meanwhile, the priorities of the two vehicles are pr(id1) and pr(id2). The calculated br(m) here represents the broadcast priority right after the two vehicles report the message. Moreover, among all the vehicles, it is assumed that only V1 and V2 report m to RSU such that br(m) is achieved as the average value of all the reporting vehicles’ priority.In a nutshell, we assume that the vehicle setV={Vi∣i∈[1,n],n∈N∗} denotes the n legitimate vehicles that have already passed the authentication process conducted by the effective RSU. Among these n vehicles, the vehicle subset RPm={Vj∣j∈[1,g],g∈N∗∧g≤n} consists of all the g vehicles that report road message m. Note that the identity of Vj is denoted as idj. Hence, the broadcast priority is pr(idj) and RPm⊆V holds. It is assumed that the g vehicles report message following the sequence of V1,…,Vg. Moreover, the road event Eventmloc is denoted as follows:(19)Eventmloc=loc,type,cont,which indicates that Eventmloc happened in location loc and the detailed information is showed in cont. Moreover, the event type is defined as type. In this way, the road message m contains the essential elements of Eventmloc.In our assumption, afterEventmloc occurred, within certain time interval g vehicles will report the event to the RSU. Hence, after RSU receives the road report from V1 for the first time, the broadcast priority is computed as br(m)=pr(id1). Similarly, the broadcast priority after RSU receives the road report for k (1≤k≤g) times, and br(m) can be computed as(20)brm=1k∑i=1kpridi,which is defined as the average vehicle priorities of all the reporting vehicles. Hence after Δt, the broadcast priority for m is(21)brm=1g∑i=1gpridi.Practically, one RSU handles multiple different road messages simultaneously. Therefore, each message will be assigned a broadcast priority and then stored in the storage. In our design, the creditability and accuracy of the road message are highly related to the reporter’s previous records. And the vehicle priority is able to reflect this property properly. Consequently, RSU sorts all these messages so that the reliable messages will be broadcast first.


## 5.2. Road Message Dissemination

As illustrated in the above section, the RSU manages all the road information within its effective range. Periodically, RSU broadcasts the messages in certain sequence. Note that all the road messages are encrypted using the distributed group keygk. Hence, only the registered vehicles can get access to this service. The aforementioned broadcast priority br(m) is roughly decided by reliability of the reporting vehicles. In this way, a predefined parameter W is set as the minimum requirement for message dissemination. That is to say, the messages m will be broadcast only if br(m)≥W. Otherwise it will be considered as unreliable information and then temporarily disabled from the broadcast list. In this case, in future, if other vehicles report the same message, br(m) will be compared with W again. After a predefined time interval, if br(m)<W, RSU permanently deletes the message in its storage. Following the above procedure, vehicles could acquire road messages in an accurate way. Thus the driving security can be improved with this service.


## 5.3. Evaluation and Priority Management

For practical consideration, an appropriate evaluation mechanism towards the road messages is necessary. In this subsection, we describe the proposed evaluation and priority management scheme. The value of the stored road message is decided by not only the reputation of the reporter but also the message itself. In order to achieve this, we assume that the vehicles have the capability of evaluating the received road messages. Following the above assumptions, the vehicle subsetRVm={Vl∣l∈[1,f],f∈N∗} denotes f vehicles who receive the road message m within time interval ΔtRC. After Vl∈RVm approaches the location loc where the road event Eventmloc happened, Vl could evaluate whether the received road information is correct, which helps improve the road report accuracy. The format of the evaluation message is as follows:(22)type,EgkEsuifNO∥assess∥id∥TSev,TSev,where the message type denoted as type here indicates that it is an evaluation message. ifNO denotes the assigned information number for message m. In addition, TSev is the current time stamp. Note that this evaluation will be sent back to RSU. According to(23)DgkEgkEsuifNO∥assess∥id∥TSev=EsuifNO∥assess∥id∥TSev,RSU checks the time stamp TSev with the derived one in order to ensure that the message is timely and effective. Additionally, id of the vehicle is derived. RSU acquires the relevant secret su in its storage so that the transmitted evaluation on message m can be acquired according to(24)DsuEsuifNO∥assess=ifNO∥assess.In this way, the evaluation can be combined tom according to ifNO. As a result, for road message m, the RSU could receive hm evaluation messages where hm≤f. For practical consideration, the assess can be analyzed using different state parameters such as sp∈{-2,-1,0,1,2}, where sp=2 means that assess is totally accurate and helpful, while sp=-2 means that assess is of no help and thus is considered as the fake message. The hm state parameters are {spu∣u∈[1,hm],u∈N∗}. During every certain period ΔtRD, RSU analyzes all the received evaluation messages and updates the broadcast priority following the steps below:(i)
Screening: firstly, RSU checks whether(25)RatemΔtRDspu>0≥Vholds, whereRatemΔtRD[spu>0] denotes the proportion of the received assess whose spu>0 among all the hm evaluation on m. Furthermore, V is the predefined system parameter according to different practical scenarios. In this case, if most of the users give negative assessments, m is considered as invalid information and must be discarded from the storage immediately.(ii)
Updating: secondly, the updating on broadcast priority is conducted as(26)br′m=brm+∑u=1hmpridu×spuhm=∑i=1gpridig+∑u=1hmpridu×spuhm,where[pr(idu)]u∈[1,hm] denotes the priority of hm vehicles.At this point, the updating process forΔtRD is completed. Similarly, after n time periods nΔtRD, the broadcast priority for m is(27)brnΔtRDm=∑i=1gpridig+∑i=1n∑u=1hmipridui×spuihmi,where hmi, pr(idui), and spui are the parameters in ith time periods iΔtRD. Note that the above process should be conducted for each stored road message in RSU. Hence, the broadcast sequence is updated. In future, after xΔtRD, m will be deleted if brxΔtRD(m)<N, where N is the preset system parameter.


## 5.4. Vehicle Priority Management

As illustrated above, the vehicle priority on vehicleid is pr(id), which is a significant user property in both the broadcast priority computing and updating processes. As a matter of fact, the reporting vehicle plays a crucial role in the message dissemination scheme. Hence, appropriate rewarding strategy is essential to motivate drivers’ enthusiasm on road situation reporting. The incentives will be given according to the vehicle priority. To achieve this, pr(id) will be updated according to the value of his reporting road message.We assume that road messagem is reported by several vehicles in B={vpi∣1≤i≤n,i∈N∗}. After a sufficient time period, for example, twenty-four hours, one road message m has been evaluated by multiple vehicles. According to (25) in the previous section, m is valid if(28)RatemΔtRDspu>0≥Vholds. In this way, pr(vpi) of all vpi∈B are updated as(29)prvpi=prvpi+1.In contrast, if m is evaluated to be invalid and discarded by RSU, pr(vpi) of all vpi∈B are updated as(30)prvpi=prvpi-1.Note that the driver could change it into incentives such as coupons of cooperative stores or scorecard in the road service area.


## 6. Security Analysis

In this section, we analyze the security properties of the proposed authentication scheme. The security theorems as well as the corresponding proofs are given below.


### 6.1. Unforgeability against Chosen Message Attack

We analyze the unforgeability against chosen message attack in the proposed protocol.Theorem 1.
The proposed certificateless authentication scheme is existentially unforgeable against adaptive chosen message attack under the assumption of random oracle model if and only if the CDHP is hard.Proof.
The security of unforgeability is formally defined through gameG1. Let A1 be a probabilistic polynomial time adversary. C1 denotes the challenger; h and H denote the random oracles. In order to solve CDHP problem, it is assumed that C1 is able to simulate all the related oracles. In G1, A1 can conduct the following corresponding queries to C1.
h Query. We assume that the adversary A1 itself does not have the ability to directly compute the hash function h(·). Hence, the response toh Query is simulated by maintaining a list Listh initialized to be empty. That is to say, when the oracle is queried with the input values t,r,Rid, if the query t,r,Rid already exists in Listh, C1 outputs v=h(t∥r,Rid) to A1. Otherwise, C1 chooses a random number v∈Z∗ and forwards it to A1. After that, t,r,Rid,v will be subsequently added to Listh.
Extract Query. The adversary A1 is able to query the partial private key of any given key set Qv,id. According to id, C1 outputs the partial private key su to A1.
H Query. A1 can query the random oracle H at any time. The response toH Query is simulated by maintaining a list ListH. Note that ListH is initialized to be empty. When the oracle H is queried with input values id,QRSU, if the query id,QRSU already exists in ListH, C1 outputs Qid=H(id,QRSU) to A1. Otherwise, C1 chooses a random number Qid∈Z∗ and forwards it to A1. After that, id,QRSU,Qid will be subsequently added to ListH.
Authenticating Query. C1 simulates the authenticating oracle by responding to the authenticating query as follows: (i)
C1 randomly chooses U∈G1 as the certificate and v∈Z∗ as the intermediate parameter.(ii)
C1 computes r=e^(P,U)/e^(Q1,Qid)v. If t,r,Rid,v already exists in Listh, C1 chooses other values and tries again.(iii)
C1 adds the above t,r,Rid,v to Listh.(iv)
C1 outputs id,t,v,U as the certificate.
According to theForking Lemma [43], A1 produces two valid certificates id,t,v,U and id,t,v′,U′ (v≠v′). In this case, (31)U=tvsvQid+suU′=tv′svQid+su,hold. Hence we can get(32)svQid=v-v′-1U-U′t.
In this way, we show that the CDHP problem can be solved. In other words, the attacker needs to solve the CDHP problem in order to forge the certificate. However, this contradicts the hardness of the CDHP problem [44, 45]. In conclusion, an attacker cannot forge the certificate in the authentication process [46, 47].


### 6.2. Resistance to Replay Attack

The replay attack is achieved by reusing the previous generated message to pass the current authentication process. The security property against replay attack is discussed in this section.Theorem 2.
During the certificateless authentication process, replay attack can be prevented. That is, the previous messages of the past authentication sessions cannot pass the current authentication process in RSU side.Proof.
We discuss the resistance to replay attack through gameG2. Similarly, let A2 be a probabilistic polynomial time adversary. It is assumed that, in time point T1, A2 has access to all the published system parameters as well as the transmitted messages from T0 to T1 (T0<T1). Randomly, A2 chooses the message id,Tr,vTr,UTr at time Tr∈[T0,T1]. At T1, A2 sends id,T1,vTr,UTr as the replaying message. Note that UTr=TrvTrsvQid+su. In this way, r≠e^(QRSU,Qid). Hence, the previous message cannot pass the current authentication.


### 6.3. Forward Security

In this section, we analyze the forward security property of the proposed protocol.Theorem 3.
The proposed authentication scheme provides forward security against adversary. That is, the adversary cannot pass the authentication with the acquired vehicle secret key from the compromised RSU.Proof.
We assume that the RSU has already been compromised by brute-force attack and all the stored key information is leaked to the adversaryA3. The secret key set {sui∣i∈[1,n]} denotes the private keys of all the n vehicles. In this case, A3 is able to use the derived partial private key su for certificate generation. However, the private key contains both su and sv, while sv is chosen by the vehicle itself. Due to the hardness of the aforementioned DLP problem, the probability that U=tvsvQid+su can be correctly computed is illustrated as 1/2ϖ, where ϖ is the size of sv. In general, the certificateless authentication property guarantees the forward security of the proposed scheme.


### 6.4. Session Key Establishment

In the system model of this paper, it is necessary to generate a shared session key between the RSU and vehicle so as to guarantee the data confidentiality and transmission security, which is analyzed as follows.Theorem 4.
In the proposed protocol, the shared session key is established after successfully authentication between RSU and vehicle.Proof.
According to the protocol design,K, along with the current time stamp and the previously acquired intermediate value v, is transmitted to the vehicle. In the vehicle side, the below derivation of K is conducted as N=T-1sv-1W=KP, where sv is stored in vehicle already. Note that the security assurance of the message transmission is based on the hardness of DLP problem. The final group key is generated and adopted to the following message transmission.


### 6.5. Mutual Authentication

In this section, we analyze the mutual authentication property in the proposed authentication protocol.Theorem 5.
The proposed protocol can provide mutual authentication between RSU and vehicle if the DLP problem is intractable.Proof.
During the authentication process, the RSU-to-vehicle security is preserved by the aforementioned certificateid,t,v,U, which has been discussed in the proof of Theorem 1. On the other hand, the vehicle-to-RSU security is based on the hardness of DLP problem. Specifically, F=h(W∥v,su) is contained in the delivered W,F,T and will be verified by the RSU with the known key information. Therefore, we could conclude that the proposed authentication scheme provides mutual authentication property.


## 6.1. Unforgeability against Chosen Message Attack

We analyze the unforgeability against chosen message attack in the proposed protocol.Theorem 1.
The proposed certificateless authentication scheme is existentially unforgeable against adaptive chosen message attack under the assumption of random oracle model if and only if the CDHP is hard.Proof.
The security of unforgeability is formally defined through gameG1. Let A1 be a probabilistic polynomial time adversary. C1 denotes the challenger; h and H denote the random oracles. In order to solve CDHP problem, it is assumed that C1 is able to simulate all the related oracles. In G1, A1 can conduct the following corresponding queries to C1.
h Query. We assume that the adversary A1 itself does not have the ability to directly compute the hash function h(·). Hence, the response toh Query is simulated by maintaining a list Listh initialized to be empty. That is to say, when the oracle is queried with the input values t,r,Rid, if the query t,r,Rid already exists in Listh, C1 outputs v=h(t∥r,Rid) to A1. Otherwise, C1 chooses a random number v∈Z∗ and forwards it to A1. After that, t,r,Rid,v will be subsequently added to Listh.
Extract Query. The adversary A1 is able to query the partial private key of any given key set Qv,id. According to id, C1 outputs the partial private key su to A1.
H Query. A1 can query the random oracle H at any time. The response toH Query is simulated by maintaining a list ListH. Note that ListH is initialized to be empty. When the oracle H is queried with input values id,QRSU, if the query id,QRSU already exists in ListH, C1 outputs Qid=H(id,QRSU) to A1. Otherwise, C1 chooses a random number Qid∈Z∗ and forwards it to A1. After that, id,QRSU,Qid will be subsequently added to ListH.
Authenticating Query. C1 simulates the authenticating oracle by responding to the authenticating query as follows: (i)
C1 randomly chooses U∈G1 as the certificate and v∈Z∗ as the intermediate parameter.(ii)
C1 computes r=e^(P,U)/e^(Q1,Qid)v. If t,r,Rid,v already exists in Listh, C1 chooses other values and tries again.(iii)
C1 adds the above t,r,Rid,v to Listh.(iv)
C1 outputs id,t,v,U as the certificate.
According to theForking Lemma [43], A1 produces two valid certificates id,t,v,U and id,t,v′,U′ (v≠v′). In this case, (31)U=tvsvQid+suU′=tv′svQid+su,hold. Hence we can get(32)svQid=v-v′-1U-U′t.
In this way, we show that the CDHP problem can be solved. In other words, the attacker needs to solve the CDHP problem in order to forge the certificate. However, this contradicts the hardness of the CDHP problem [44, 45]. In conclusion, an attacker cannot forge the certificate in the authentication process [46, 47].


## 6.2. Resistance to Replay Attack

The replay attack is achieved by reusing the previous generated message to pass the current authentication process. The security property against replay attack is discussed in this section.Theorem 2.
During the certificateless authentication process, replay attack can be prevented. That is, the previous messages of the past authentication sessions cannot pass the current authentication process in RSU side.Proof.
We discuss the resistance to replay attack through gameG2. Similarly, let A2 be a probabilistic polynomial time adversary. It is assumed that, in time point T1, A2 has access to all the published system parameters as well as the transmitted messages from T0 to T1 (T0<T1). Randomly, A2 chooses the message id,Tr,vTr,UTr at time Tr∈[T0,T1]. At T1, A2 sends id,T1,vTr,UTr as the replaying message. Note that UTr=TrvTrsvQid+su. In this way, r≠e^(QRSU,Qid). Hence, the previous message cannot pass the current authentication.


## 6.3. Forward Security

In this section, we analyze the forward security property of the proposed protocol.Theorem 3.
The proposed authentication scheme provides forward security against adversary. That is, the adversary cannot pass the authentication with the acquired vehicle secret key from the compromised RSU.Proof.
We assume that the RSU has already been compromised by brute-force attack and all the stored key information is leaked to the adversaryA3. The secret key set {sui∣i∈[1,n]} denotes the private keys of all the n vehicles. In this case, A3 is able to use the derived partial private key su for certificate generation. However, the private key contains both su and sv, while sv is chosen by the vehicle itself. Due to the hardness of the aforementioned DLP problem, the probability that U=tvsvQid+su can be correctly computed is illustrated as 1/2ϖ, where ϖ is the size of sv. In general, the certificateless authentication property guarantees the forward security of the proposed scheme.


## 6.4. Session Key Establishment

In the system model of this paper, it is necessary to generate a shared session key between the RSU and vehicle so as to guarantee the data confidentiality and transmission security, which is analyzed as follows.Theorem 4.
In the proposed protocol, the shared session key is established after successfully authentication between RSU and vehicle.Proof.
According to the protocol design,K, along with the current time stamp and the previously acquired intermediate value v, is transmitted to the vehicle. In the vehicle side, the below derivation of K is conducted as N=T-1sv-1W=KP, where sv is stored in vehicle already. Note that the security assurance of the message transmission is based on the hardness of DLP problem. The final group key is generated and adopted to the following message transmission.


## 6.5. Mutual Authentication

In this section, we analyze the mutual authentication property in the proposed authentication protocol.Theorem 5.
The proposed protocol can provide mutual authentication between RSU and vehicle if the DLP problem is intractable.Proof.
During the authentication process, the RSU-to-vehicle security is preserved by the aforementioned certificateid,t,v,U, which has been discussed in the proof of Theorem 1. On the other hand, the vehicle-to-RSU security is based on the hardness of DLP problem. Specifically, F=h(W∥v,su) is contained in the delivered W,F,T and will be verified by the RSU with the known key information. Therefore, we could conclude that the proposed authentication scheme provides mutual authentication property.


## 7. Performance Analysis

In this section, we present the performance analysis towards the proposed protocol. Our analysis on the performance mainly emphasizes the storage overhead, the computation cost, and the communication cost, which are the dominant factors in the proposed protocol.


### 7.1. Storage Overhead

In the proposed protocol, storage overhead is a crucial parameter for VANETs, especially for vehicles. Due to the inherent resource restriction, it is impractical for the vehicle to store massive key messages and communication data in its own memory. Moreover, the RSU is designed to handle both the key distribution and road message management simultaneously. As a result, the storage overhead in both the vehicle and RSU sides should be considered.As for the vehicle in the proposed protocol, some essential key information is previously stored during the registration includingid,Rid,Qv,sv,su. The published public key of RSU, namely, QRSU, as well as the intermediate value Qid,C, is also stored in vehicle. Moreover, the transmitted message r,v,U, and the necessary group key distribution value are stored, respectively, in the group key distribution phase. According to [48], we assume that the length of elements in GH and G1 is 256 bits. The lengths of relevant vehicle secret keys such as sv, su, and gk are 160 bits. Moreover, it is assumed than the lengths of the adopted time stamps and the identity of vehicle id are 32 bits and 24 bits each. In this way, the storage overhead for each vehicle is 24+256×5+160×7+32×3=2520 bits. Similarly, we assume that the number of vehicles in the RSU range is n. Consequently, the storage overhead in RSU side includes key information of RSU itself and secret messages of all the n vehicles. In this way, the storage overhead for the RSU is 256+160×3+32+n(24+256×4+160×3+32×2)=1592n+768 bits. The comparison with the state-of-the-art VANETs authentication protocols ICPA [10], DAKM [4], ABAP [8], and SAAP [32] is illustrated in Table 1.Table 1
Comparison of storage overhead.
Protocol ICPA [10] DAKM [4] ABAP [8] SAAP [32] Our protocol Storage (Vehicle) 2112 bits 2712 bits 3432 bits 2904 bits 2520 bits Storage (RSU) 1440 n + 1056 bits 1676 n + 1144 bits 1936 n + 1048 bits 2008 n + 2392 bits 1592 n + 768 bits


### 7.2. Computation Cost

In this section, we analyze the computation cost of the proposed protocol. The computation cost is defined as the time consumption for the group key distribution process. The comparison result with ICPA, DAKM, ABAP, and SAAP is given in Table2. We denote modulo operation as mod, exponential operation as Ex, and bilinear pairing as e^. Enc and Dec refer to encryption and decryption. Additionally, H, M, D, and A represent one-way hash function, multiplication operation, division operation, and addition operation, respectively. Finally, the point multiplication operation is dented as p.Table 2
Comparison of computation cost.
Protocol ICPA [10] DAKM [4] ABAP [8] SAAP [32] Our protocol Computation cost (vehicle) 3 p + 3 H + 2 A + 2 M + 2 m o d 1 D e c + m o d + 1 E n c 1 D e c + 4 p + 2 H + 2 A + D 10 p + 5 H + 4 A + M 4 p + 3 H + e ^ + A + 3 M Computation cost (RSU) 3 n M + ( 2 n + 2 ) p + 2 A 3 E n c + 2 n M + n D + ( n - 1 ) A 2 n H + 2 n p + 2 n M + 3 n e ^ + n A 4 n H + ( 8 n + 1 ) p + n M + 3 n A 2 n H + 2 n p + 2 n M + 2 n e ^ + n E x


### 7.3. Communication Cost

The communication cost refers to the time consumption for message transmission. In this subsection, we consider the required communication passes for RSU to successfully authenticate vehicles. The comparison result on communication cost is given in Table3.Table 3
Comparison of communication cost.
Protocol ICPA [10] DAKM [4] ABAP [8] SAAP [32] Our protocol Computation rounds 4 n + 2 4 n + 1 4 n + 1 4 n + 4 4 n


## 7.1. Storage Overhead

In the proposed protocol, storage overhead is a crucial parameter for VANETs, especially for vehicles. Due to the inherent resource restriction, it is impractical for the vehicle to store massive key messages and communication data in its own memory. Moreover, the RSU is designed to handle both the key distribution and road message management simultaneously. As a result, the storage overhead in both the vehicle and RSU sides should be considered.As for the vehicle in the proposed protocol, some essential key information is previously stored during the registration includingid,Rid,Qv,sv,su. The published public key of RSU, namely, QRSU, as well as the intermediate value Qid,C, is also stored in vehicle. Moreover, the transmitted message r,v,U, and the necessary group key distribution value are stored, respectively, in the group key distribution phase. According to [48], we assume that the length of elements in GH and G1 is 256 bits. The lengths of relevant vehicle secret keys such as sv, su, and gk are 160 bits. Moreover, it is assumed than the lengths of the adopted time stamps and the identity of vehicle id are 32 bits and 24 bits each. In this way, the storage overhead for each vehicle is 24+256×5+160×7+32×3=2520 bits. Similarly, we assume that the number of vehicles in the RSU range is n. Consequently, the storage overhead in RSU side includes key information of RSU itself and secret messages of all the n vehicles. In this way, the storage overhead for the RSU is 256+160×3+32+n(24+256×4+160×3+32×2)=1592n+768 bits. The comparison with the state-of-the-art VANETs authentication protocols ICPA [10], DAKM [4], ABAP [8], and SAAP [32] is illustrated in Table 1.Table 1
Comparison of storage overhead.
Protocol ICPA [10] DAKM [4] ABAP [8] SAAP [32] Our protocol Storage (Vehicle) 2112 bits 2712 bits 3432 bits 2904 bits 2520 bits Storage (RSU) 1440 n + 1056 bits 1676 n + 1144 bits 1936 n + 1048 bits 2008 n + 2392 bits 1592 n + 768 bits


## 7.2. Computation Cost

In this section, we analyze the computation cost of the proposed protocol. The computation cost is defined as the time consumption for the group key distribution process. The comparison result with ICPA, DAKM, ABAP, and SAAP is given in Table2. We denote modulo operation as mod, exponential operation as Ex, and bilinear pairing as e^. Enc and Dec refer to encryption and decryption. Additionally, H, M, D, and A represent one-way hash function, multiplication operation, division operation, and addition operation, respectively. Finally, the point multiplication operation is dented as p.Table 2
Comparison of computation cost.
Protocol ICPA [10] DAKM [4] ABAP [8] SAAP [32] Our protocol Computation cost (vehicle) 3 p + 3 H + 2 A + 2 M + 2 m o d 1 D e c + m o d + 1 E n c 1 D e c + 4 p + 2 H + 2 A + D 10 p + 5 H + 4 A + M 4 p + 3 H + e ^ + A + 3 M Computation cost (RSU) 3 n M + ( 2 n + 2 ) p + 2 A 3 E n c + 2 n M + n D + ( n - 1 ) A 2 n H + 2 n p + 2 n M + 3 n e ^ + n A 4 n H + ( 8 n + 1 ) p + n M + 3 n A 2 n H + 2 n p + 2 n M + 2 n e ^ + n E x


## 7.3. Communication Cost

The communication cost refers to the time consumption for message transmission. In this subsection, we consider the required communication passes for RSU to successfully authenticate vehicles. The comparison result on communication cost is given in Table3.Table 3
Comparison of communication cost.
Protocol ICPA [10] DAKM [4] ABAP [8] SAAP [32] Our protocol Computation rounds 4 n + 2 4 n + 1 4 n + 1 4 n + 4 4 n


## 8. Conclusion

Emphasizing the secure authentication and road message dissemination in VANETs, a secure certificateless authentication and road message dissemination protocol is proposed in this paper. In our design, certificateless cryptographic technique is employed for authentication and key distribution. Subsequently, an appropriate road message dissemination mechanism is designed. The security analysis and performance evaluation are given accordingly. The proposed protocol is suitable for practical VANET scenarios and is capable of providing timely road information services, which improves both the user safety and the driving experience.



---

*Source: 7978027-2018-05-20.xml*