Unlinkable and Revocable Signcryption Scheme for VANETs

Abstract

Vehicular ad-hoc networks (VANETs) can significantly improve the level of urban traffic management. However, the sender unlinkability has become an intricate issue in the field of VANETs’ encryption. As the sender signcrypts a message, the receiver has to use the sender’s identity or public key to decrypt it. Consequently, the sender can be traced using the same identity or public key, which poses some security risks to the sender. To address this issue, we present an unlinkable and revocable signcryption scheme (URSCS), where an efficient and powerful signcryption mechanism is adopted for communication. The sender constructs a polynomial to generate a unique session key for each communication, which is then transmitted to a group of receivers, enabling the same secret message to be sent to multiple receivers. Each time a secret message is sent, a new key pair is generated, and an anonymization mechanism is introduced to conceal the true identity of the vehicle, thus preventing malicious attackers from tracing the sender through the public key or the real identity. With the introduction of the identification public key, this scheme supports either multiple receivers or a single receiver, where the receiver can be either road side units (RSUs) or vehicles. Additionally, a complete revocation mechanism is constructed with extremely low communication overhead, utilizing the Chinese remainder theorem (CRT). Formal and informal security analyses demonstrate that our URSCS scheme meets the expected security and privacy requirements of VANETs. The performance analysis shows that our URSCS scheme outperforms other represented schemes.

1. Introduction

With the increasing popularity of cars in ordinary families and the increasing complexity of urban roads, traffic accidents have become a major risk factor in modern society [1]. In order to reduce the traffic dangers encountered by people in daily life and improve the efficiency of information sharing between vehicles, VANETs have emerged [2]. Vehicles move at high speeds, and VANETs mainly use the dedicated short-range communications (DSRC) protocol [3], so it is easy for malicious attackers to listen, intercept, modify, and re-transmit messages [4], which poses great security risks to VANETs. Therefore, ensuring the legitimacy of the information source, ensuring that the received message is not tampered with, and ensuring the secret transmission of the message have become basic requirements in the field of vehicle networking security [5,6,7].

In recent years, signcryption technology has proven capable of completing the above three required functions in one operation simultaneously, which greatly reduces communication and computation overhead [8]. It has been widely used, especially in multi-receiver scenarios, such as VANETs, mobile communication devices, wireless body area networks, and maritime transportation systems. However, the traditional multi-receiver signcryption technology requires the sender to negotiate with each receiver and send different ciphertext, which significantly reduces the efficiency of message transmission [9,10,11,12,13,14,15,16,17]. Additionally, there is a problem that can be traced back to the sender. When the same sender sends multiple messages, it needs to use its own private key for signcryption, and the receiver uses the public key or real identity of the sender for unsigncryption. Therefore, malicious attackers can trace the sender based on the same public key or real identity used in the process of multiple signcryption. In order to solve this problem, Liang et al. [18] first proposed a scheme with multiple receivers and unlinkable to senders. An anonymous transmission is taken each time a message is sent and a key pair is updated by the sender, and uses CRT to transmit the public session key. However, their scheme can only be used for one-to-many transmission for road side units (RSUs).

In the context of VANETs, malicious vehicles will send malicious messages for various reasons, leading to various traffic problems. Therefore, TCC’s ability to track and revoke malicious vehicles is particularly important [19]. In VANETs, for the implementation of the revocation mechanism, the schemes [20,21,22] allocate a revocation list to each vehicle, resulting in high storage overhead for the entire system. At the same time, TCC needs to frequently update the revocation list to all vehicles, which also incurs high communication overhead. Scheme [18] implements revocation mechanisms by constructing polynomials, but since the number of parameters in the publicly disclosed revocation public key equals the number of vehicles, this method consequently faces the problem of high transmission overhead. In a resource-constrained VANET environment, a revocation mechanism can only be practically feasible if its cost is sufficiently low.

With the motivation of addressing the aforementioned issues, this paper proposes an unlinkable and revocable signcryption scheme (URSCS). Our main contributions are listed as follows:

• For the first time, in the scenario of vehicle networking, our URSCS scheme truly realizes the unlinkable communication for the sender in one-to-many or one-to-one modes at the same time. By introducing the identification of public and private key pairs instead of real identities, the receivers can be either the vehicles or the RSUs. In order to achieve unlinkability of the sender, our URSCS scheme takes the following approach: First, we provide conditional privacy through a pseudonym mechanism, which effectively hides the true identity of the vehicle, so that malicious attackers cannot track the sender through the real identity. Second, the vehicle updates its key pair and pseudonym before each signcryption, ensuring that a malicious attacker cannot link the sender to the message based on the public keys or pseudonyms;
• Based on CRT, we propose a comprehensive revocation key update mechanism that incurs low communication costs. Regardless of the number of vehicles within the domain covered by a Traffic Control Center (TCC), the revocation key information transmitted remains at 96 bytes. Consequently, the TCC can efficiently remove malicious vehicles from the system and promptly update the revocation public key to prevent them from transmitting further harmful information. Additionally, by incorporating several time thresholds, our URSCS scheme effectively prevents malicious vehicles from continuing to send messages, even if their revocation keys are reassigned to new vehicles;
• We conduct formal and informal security analyses of our URSCS scheme, which show that our scheme satisfies various security requirements and can effectively resist various known potential attacks;
• Rigorous performance evaluation confirms that with the increase in the number of receiving ends, the communication and computation overhead of the proposed URSCS scheme has significant advantages compared with other related schemes.

The remainder of this paper is organized as follows: the related works are introduced in Section 2. Some preliminaries are briefly introduced in Section 3, including the elliptic curve cryptosystem, classical hard problems, and the basic concepts of CRT. Section 4 outlines the system model and security and privacy goals of our URSCS scheme. The detailed design of our URSCS scheme is described in Section 5. And the security analysis and performance assessment are presented in Section 6 and Section 7, respectively. Finally, we conclude this paper in Section 8.

2. Related Work

In this section, we will extensively discuss the security techniques involved in transmitting information over an open channel, mainly focusing on signcryption, revocability, anonymity, and unlinkability.

2.1. Signcryption

Zheng Yuliang [23] first introduced a new cryptographic primitive named signcryption, performing both signature and encryption, and simultaneously ensuring the authentication, integrity, and confidentiality of the message. Compared to the sign-then-encrypt method, this mechanism also reduced the computation overhead and communication overhead, making it suitable for resource-constrained application scenarios [24,25]. In 2003, Al-Riyami et al. proposed a new cryptography primitive called certificateless public key cryptography in [26], which addresses both the certificate management problem in traditional public key infrastructure (PKI) [27] and the key escrow problem in identity-based cryptosystems [28]. Specifically, a certificateless public key cryptography system divides a user’s public key and private key into two parts. The key generation center (KGC) generates only part of the public key and private key for the user, while the other part is generated by the user themselves, and the part generated by the user is referred to as the secret value. In 2008, Barbosa Manuel and Farshim Pooya proposed the first certificateless signcryption (CLSC) scheme [29], which combines the certificateless cryptosystem and signcryption. Since then, researchers have proposed a number of CLSC schemes [30,31,32,33]. However, these schemes are based on bilinear pairing operations, and due to the high computation cost of bilinear pairing, they are unsuitable for devices with limited computational resources, such as on-board units (OBUs) in vehicles.

In order to accommodate resource-constrained scenarios such as the VANETs, many researchers began designing certificateless signcryption schemes without pairing operations. Cui et al. designed a new certificateless aggregate signcryption scheme [34], successfully eliminating the expensive pairing operation and thereby improving computational efficiency. However, Zhan et al. pointed out that Cui et al.’s protocol is not guaranteed to be unforgeable under the second type of attack. They subsequently designed a new CLSC scheme [35] which addresses the presence of unforgeability in the second type of attack. Since then, many unpaired certificateless signcryption schemes, such as [36,37,38], have been developed and applied in numerous resource-constrained scenarios. However, these schemes also face certain challenges. For instance, the scheme proposed by Shen et al. [36] does not incorporate a revocation mechanism, and Yu and Ren’s scheme [37] has been proven unable to withstand signature forgery attacks and collusion attacks. Recently, a considerable number of signcryption-based schemes have been developed by numerous researchers for multi-receiver scenarios, aiming to boost communication and computation performance [8,11,12,13,14,15,16,17]. However, these schemes still suffer from all kinds of shortcomings. Specifically, the schemes [11,14,15], and Ref. [38] lacked sender unlinkability, enabling the receiver to associate the sender with a fixed public key, and Ref. [16] failed to provide sender anonymity due to the sender communicating openly with their real identity. In addition, a handful of schemes, specifically [8,17], lacked both a tracing and revocation mechanism.

2.2. Revocability

In order to solve the vehicle revocation problem, many researchers have proposed anonymity-based conditional privacy schemes with revocation function [20,21,22]. However, in these schemes, to ensure anonymity and unlinkability, the vehicle needs to be pre-loaded with a large number of anonymous public keys and certificates. However, one of the challenges with this type of scheme is the large scale of certificate revocation lists (CRL), resulting in increased storage and verification costs. When a vehicle is revoked, its certificate is added to the CRL, further increasing its size and thus exacerbating transmission delays. Therefore, the scale of the CRL and the cost of exhaustive search become important constraints of this revocation mechanism.

Shim et al. proposed a conditional privacy-preserving authentication scheme based on public key cryptography [39], where public identities are used to verify the legitimacy of vehicle identities, and vehicle anonymity is achieved through two trusted agents, namely, the trace authority and the private key generator. However, Wang et al. [40] pointed out that Shim and Kyung-Ah’s scheme [39] would incur significant computational and communication costs with an increase in the number of vehicles, and the revocation process could not meet the requirements of V2V communication, and proposed an enhanced security certificateless conditional privacy-preserving authentication scheme with revocation [40]. However, since the vehicle keys are all generated by the trusted authority, there is an issue with key escrow.

2.3. Anonymity and Unlinkability

In VANETs, anonymity means that no one can infer the sender’s identity information from the received message. Unlinkability ensures that no one (including the recipients of the messages) can determine whether two transmitted messages come from the same vehicle [18]. Currently, many researchers have proposed numerous authentication schemes for user anonymity [11,35,41,42,43,44]. However, most existing schemes in VANETs cannot fully achieve sender unlinkability. Specifically, the receiver must use the sender’s identity or public key to complete the verification process. Consequently, the receiver can link different messages to the same sender through the invariant elements, identity, or public key within the messages. For example, in [42], a new certificate-based identity authentication scheme was proposed to enhance the security of vehicular networks. However, when the sender is the same, the signing and verification process always uses the same pseudonym, allowing attackers to link multiple messages to the same sender through the identical pseudonym. Gayathri et al. [43] proposed a pairing-free certificateless authentication scheme to achieve batch verification in VANETs; however, each signature message generated by user $I{D}_i$ contains an immutable parameter $R_i$, an attacker can determine whether two messages are from the same sender by checking if the parameters in the signatures are equal. Liang et al. [18] achieved the first truly sender-unlinkable multi-receiver signcryption scheme. However, in Liang’s scheme, the real ID of the receiver must be used when transmitting information, which means that the receivers can only be RSUs, and V2V communication cannot be guaranteed.

3. Preliminaries

This section will provide a detailed introduction to the Chinese remainder theorem, the elliptic curve cryptosystem, and classic hardness assumptions.

3.1. Chinese Remainder Theorem (CRT)

The CRT is an important tool in number theory used to solve a class of problems related to systems of modular congruence equations. Consider a modular congruence system as follows.

$$\left\{\begin{array}{c}x\equiv t_1(mod{k}_1)\hfill \\ x\equiv t_2(mod{k}_2)\hfill \\ x\equiv t_3(mod{k}_3)\hfill \\ ⋮\hfill \\ x\equiv t_n(mod{k}_n)\hfill \end{array}\right.$$

(1)

where $t_1,t_2,\dots ,t_n$ are given n integers, and $k_1,k_2,\dots ,k_n$ are n coprime positive integers. If the congruence system (1) has a solution, then through the CRT, we can obtain a unique solution $x={\sum }_{i=1}^n{t}_i{K}_i{K}_i^{-1}$, where $K_i={\prod }_{j=1,j\ne i}^n{K}_j$, $K_i^{-1}$ is the multiplicative inverse of $K_i$ modulo $k_i$. In this paper, the CRT is not used to solve for x in the congruence system; rather, its principles are employed to transmit public parameters.

3.2. Elliptic Curve Cryptosystem ECC

Assume $F_p$ is a finite field defined by modulo p, where p is a large prime number. We define an elliptic curve E over $F_p$, which is in the form of a set of points $\{\left(x,y\right)\in {\left(F_p\right)}^2|y^2\equiv x^3+ax+b\left(modp\right),4a^3+27b^2\ne 0\left(modp\right)\}$, where a and b are elements of $F_p$. And, the combination of an infinite point O along with every point on E comprises an additive elliptic curve group G, that possesses a prime order q. This group G satisfies the subsequent properties:

Point addition: For any P, $Q\in G$, the following conditions hold: if $P=Q$, $2P=P+Q$; if $P=-Q$, $O=P+Q$; and if $P\ne Q$, $R=P+Q$, where $-R$ is the intersection of elliptic curve E and the straight line connecting P and Q, R is the inverse of $-R$ on G.

Scale multiplication: Given $P\in G$ and $n\in Z_q^{*}$, $nP=P+P+\cdots +P$ (n times).

3.3. Hard Problems

Elliptic Curve Discrete Logarithm Problem (ECDLP): Given P, $\alpha P\in G$, it is hard to compute the value of $\alpha$ in a probabilistic polynomial-time (PPT), where $\alpha \in Z_q^{*}$.

Computational Diffie–Hellman Problem (CDHP): Given P, $\alpha P$, $\beta P\in G$, it is hard to compute $\alpha \beta P$ in a PPT, where $\alpha$, $\beta \in Z_q^{*}$.

4. System Model and Security Requirements

4.1. System Model

As shown in Figure 1, there are mainly three entities in our URSCS scheme: TCC, RSU, and Vehicle. Due to the huge geographical coverage of VANETs, we assume the existence of multiple TCCs. Communication between vehicles, as well as between vehicles and RSUs, is achieved through open dedicated short-range wireless signals, while communication between RSUs and between TCC and RSUs is performed through wired communication.

TCC: It is assumed to be a trusted and secure entity with unlimited computational capability. It is mainly responsible for the initialization of the entire network, network management, registration of vehicles and RSUs, generating partial private keys, pseudonyms, revocation keys for vehicles, and it can track and revoke malicious vehicles.

RSU: Installed on both sides of various roads, it is a semi-honest entity, meaning it faithfully executes various instructions of the system, but it also tends to be curious and collects various information about the system. Its main responsibilities include collecting, decrypting, forwarding, and verifying the encrypted information of surrounding vehicles, as well as forwarding information from the TCC.

Vehicle: Each vehicle is eligible to be included in the system only after registering with the TCC. Furthermore, each vehicle must be equipped with a tamper-proof device (TPD) and an OBU to securely store and process sensitive data. Vehicles collect real-time traffic data, signciphers the information, and transmit the generated ciphertext to designated entity sets. At the same time, vehicles are always ready to receive instructions from the TCC and RSUs and respond promptly.

Figure 1 illustrates the system architecture within the scope of a single TCC. Communication between vehicles, as well as between vehicles and RSUs, is achieved through open dedicated short-range wireless signals, while communication between RSUs and between TCC and RSUs is performed through wired communication.

4.2. Definition of URSCS

Our URSCS system is mainly composed of the following ten algorithms, and we will introduce their basic definitions one-by-one. For the convenience of reading, the relevant symbols used in our URSCS scheme and their corresponding meanings are summarized in

Table 1. Definition of notations.

Notation	Definition
$msk$,$MPK$	System master secret key, system master public key
b	Master revocation secret key
$(B,batValue)$	Master revocation public key
$V_j$	The jth vehicle
$RS{U}_j$	The jth RSU
$rs{k}_j$	Revocation secret key of $V_j$
$SK$	Session key
$is{k}_j$	Identification secret key of $V_j$ or $RS{U}_j$
$IP{K}_j$	Identification public key of $V_j$ or $RS{U}_j$
$(s{k}_j,P{K}_j)$	Key pair of the entity with $V_j$
$(y_j,Y_j)$	Partial key pair of the entity with $V_j$
$RI{D}_j$	Real Identity of $V_j$
$PI{D}_j$	Pseudonym of $V_j$
m	Message
$mod$	Modulo operation
$H(.)$	Cryptographic hash functions
t	Timestamp
$REV$	Identification public key set of receivers
⊕	XOR operation
$\left|\right|$	Concatenation of string
$\epsilon$	Ciphertext in multiple recipients scenario.
$\xi$	Ciphertext in single recipient scenario.

.

$(params,msk)\leftarrow Setup\left(k\right)$: On input security parameter k, the system initialization algorithm, which is run by the TCC, returns the public parameter $params$ and the system master secret key $msk$.

$(rsk,isk,IPK)\leftarrow VelRegister\left(RID\right)$: On input the real identity $RID$ of the registration vehicle, the vehicle registration algorithm, which is run by the TCC, computes the revocation secret key $rsk$, identification secret key $isk$, and identification public key $IPK$ for the registration vehicle.

$(isk,IPK)\leftarrow RSURegister\left(RID\right)$: On input the real identity $RID$ of the registration RSU, the RSU registration algorithm, which is run by the TCC, generates the identification secret key $isk$ and identification public key $IPK$ for the registration RSU.

$\left({\{s{k}_j,P{K}_j\}}_{j=1}^n\right)\leftarrow GenMK\left(RID\right)$: On input the real identity $RID$ of the vehicle, the vehicle’s key generation algorithm, which is run by the vehicles, generates a set of corresponding key pairs ${\{s{k}_j,P{K}_j\}}_{j=1}^n$.

$({\left\{PI{D}_j\right\}}_{j=1}^n,{\left\{pp{k}_j\right\}}_{j=1}^{n}or\perp )\leftarrow GenPIDandPPK(RID,{\left\{P{K}_j\right\}}_{j=1}^n,msk)$: On input the system master secret key $msk$, the real identity $RID$ and a set corresponding public keys ${\left\{P{K}_j\right\}}_{j=1}^n$, the vehicle’s pseudonyms and partial keys generation algorithm, which is run by the TCC, generates a set of corresponding pseudonyms ${\left\{PI{D}_j\right\}}_{j=1}^n$ and a set of corresponding partial private keys ${\left\{pp{k}_j\right\}}_{j=1}^n$.

$(b,B,batVal)\leftarrow GenRovSK(count,{\left\{rs{k}_j\right\}}_{j=1}^{count})$: On input the number of all legal vehicles in the current TCC domain $count$ and the corresponding revocation keys for each legal vehicle ${\left\{rs{k}_j\right\}}_{j=1}^{count}$, the revocation key generation algorithm, which is run by the TCC, computes the revocation master key b, the corresponding master revocation public key $(B,batVal)$.

$\left(\epsilon \right)\leftarrow MulSignCrypt(m,PI{D}_s,s{k}_s,P{K}_s,y_s,Y_s,rs{k}_s,REV={\left\{IP{K}_j\right\}}_{j=1}^u)$: On input the message m, the pseudonym of the sender $PI{D}_s$, the sender’s keys: $s{k}_s,P{K}_s,y_s,Y_s,rs{k}_s$, and a set of receivers consisting of vehicles and RSUs $REV$, the multi-receiver signcryption algorithm, which is run by the RSUs or vehicles, generates a ciphertext $\epsilon$.

$(mor\perp )\leftarrow MulDeSignCrypt\left(\epsilon \right)$: On input a ciphertext $\epsilon$, the multi-receiver designcryption algorithm, which is run by the RSUs or vehicles, outputs a message $mor\perp$.

$\left(\xi \right)\leftarrow SigSignCrypt(m,PI{D}_s,s{k}_s,P{K}_s,y_s,Y_s,rs{k}_s,IP{K}_j)$: On input the message m, the pseudonym of the sender $PI{D}_s$, the sender’s keys: $s{k}_s,P{K}_s,y_s,Y_s$, the revocation key of the sender $rs{k}_s$, and the identity public key of the sender $IP{K}_j$, the single-receiver signcryption algorithm, which is run by vehicles, generates a ciphertext $\xi$.

$(mor\perp )\leftarrow SigDeSignCrypt\left(\xi \right)$: On input the ciphertext $\xi$, the single-receiver designcryption algorithm, which is run by the RSUs or vehicles, outputs a message $mor\perp$.

4.3. Security and Privacy Goals

In this section, we elaborate on the critical security and privacy goals that must be achieved to ensure the safe operation of VANETs. These goals are paramount as they directly impact the trustworthiness of VANETs.

Authentication: Ensuring that all communication participants, including vehicles and RSU, are legitimate. Specifically, receivers (including both vehicles and RSUs) must be able to validate that the sending entities (vehicles) are genuine and not impersonating other legitimate nodes.

Data Confidentiality: In the VANET, sensitive data should be transmitted exclusively in encrypted (ciphertext) form over open channels to minimize the risk of information disclosure. Only authorized recipients with the corresponding decryption key can access and view the original data, thereby ensuring confidentiality and preventing eavesdroppers from deciphering the content of intercepted messages.

Data Integrity: To guarantee the correctness and dependability of information transmitted across V2I and V2V in the VANETs, receivers (including both vehicles and RSUs) must be able to validate that the data have not been maliciously tampered with or altered in any way during transmission. This ensures that the data received is identical to the data sent, thereby maintaining data integrity.

Anonymity: Vehicles employ pseudonyms for message transmission, leveraging a secure anonymity system that safeguards against linking or identifying the actual cars or drivers behind the data. This approach ensures that, apart from the TCC, no other party can infer the real identities of vehicles based solely on their pseudonyms.

Unlinkability: In VANETs, the unlinkability ensures that there is no discernible linkage between multiple signcrypted messages transmitted by the same vehicle. This mechanism effectively obscures the connection between messages, preventing any entity from distinguishing or inferring whether two captured messages originate from the same sender. As a result, privacy is significantly enhanced, as the identity and actions of individual vehicles remain unlinkable within the network.

Traceability: In the case of a dispute arising or the detection of malicious activity, exclusive access to trace the actual identity of vehicles engaged in such behavior, based on their pseudonyms, is granted solely to the TCC.

Revocability: Upon detection of malicious behavior, TCC has the authority to revoke the access of offending vehicles from the system, effectively disabling their ability to transmit any further valid information.

Resistance to Various Attacks: Our URSCS scheme must exhibit resilience against a broad spectrum of known attack vectors, encompassing impersonation attacks, replay attacks, ephemeral secret leakage attacks, man-in-the-middle attacks, and other potential threats that pose risks to the system’s integrity and confidentiality.

4.4. Security Model

According to the authors of [14], in certificateless signcryption schemes, there are two types of attackers. The $TypeI$ attacker can replace a user’s public key but cannot obtain the system’s master secret key. The $TypeII$ attacker possesses the system’s master secret key but cannot replace a user’s public key. In both cases, the signcryption scheme should achieve indistinguishability under adaptive chosen ciphertext attacks (IND-CCA2) and existential unforgeability against chosen message attacks (EU-CMA). For readability, we denote ${\mathcal{A}}_1^i$ as $TypeI$ attacker, where ${\mathcal{A}}_1^1$ attacks confidentiality, and ${\mathcal{A}}_1^2$ attacks unforgeability; we denote ${\mathcal{A}}_2^i$ as $TypeII$ attacker, where ${\mathcal{A}}_2^1$ attacks the confidentiality, and ${\mathcal{A}}_2^2$ attacks unforgeability.

4.4.1. Definition 1—Confidentiality (IND-CCA2-Secure)

If any PPT attackers ${\mathcal{A}}_1^1$ and ${\mathcal{A}}_2^1$ cannot win with a non-negligible advantage in the subsequent two games, Game I and Game $II$, then a URSCS scheme is IND-CCA2-Secure.

Game I: This game is played between an adversary ${\mathcal{A}}_1^1$ and a challenger $\mathcal{C}$. The specific process is as follows.

Initialization: Challenger $\mathcal{C}$ executes the initialization function $Setup\left(k\right)$, obtains the system parameters $params$ and the system master secret key $msk$, $\mathcal{C}$ sends the $params$ to adversary ${\mathcal{A}}_1^1$, and secretly retains the $msk$.

Phase 1: $\mathcal{C}$ selects a vehicle with the real identity $RI{D}^{*}$ as the sender and chooses a set of receivers with identification public key $RE{V}^{*}={\left\{IP{K}_j^{*}\right\}}_{j=1}^u$.

$\mathcal{C}$ sends the selected $RI{D}^{*}$ and $RE{V}^{*}={\left\{IP{K}_j^{*}\right\}}_{j=1}^u$ to opponent ${\mathcal{A}}_1^1$, then ${\mathcal{A}}_1^1$ submits some hash queries to challenger $\mathcal{C}$.

${\mathcal{A}}_1^1$ submits some oracle queries, and $\mathcal{C}$ responds with relevant inquiry results, but these results cannot contain information related to the sender’s private key and $msk$.

Challenge: ${\mathcal{A}}_1^1$ selects two messages $m_1,m_2$ of equal length and submits them to $\mathcal{C}$. Then, $\mathcal{C}$ randomly chooses a number $\beta \in \{0,1\}$ and performs the $MulSignCrypt(m_{\beta },PI{D}_s^{*},s{k}_s^{*},P{K}_s^{*},y_s^{*},Y_s^{*},rs{k}_s^{*},RE{V}^{*}={\left\{IP{K}_j^{*}\right\}}_{j=1}^u)$ function. Finally, $\mathcal{C}$ sends the signcryption ciphertext ${\epsilon }^{*}$ to ${\mathcal{A}}_1^1$.

Phase 2: After obtaining the signcryption ciphertext ${\epsilon }^{*}$, ${\mathcal{A}}_1^1$ submits another set of oracle queries, excluding $MulDeSignCrypt\left({\epsilon }^{*}\right)$.

Guess: ${\mathcal{A}}_1^1$ outputs a guessed value ${\beta }^{*}$. If ${\beta }^{*}=\beta$, then ${\mathcal{A}}_1^1$ wins the game.

Probability Advantage: The probability advantage of ${\mathcal{A}}_1^1$ can be defined as: $Ad{v}_{{\mathcal{A}}_1^1}^{IND-CCA2}\left(k\right)=|Pr[{\beta }^{*}=\beta ]-1/2|$.

Game $II$: This game is played between the adversary ${\mathcal{A}}_2^1$ and $\mathcal{C}$. The specific process is as follows.

Initialization: $\mathcal{C}$ executes the initialization function $Setup\left(k\right)$, obtains the system parameters $params$ and the system master private key $msk$, $\mathcal{C}$ sends the them to adversary ${\mathcal{A}}_2^1$.

The intermediate process is similar to Game I, but ${\mathcal{A}}_2^1$ is not allowed to submit an oracle query to the $\mathcal{C}$ regarding the replacement of public keys.

Guess: ${\mathcal{A}}_2^1$ outputs a guessed value ${\beta }^{*}$. If ${\beta }^{*}=\beta$, then ${\mathcal{A}}_2^1$ wins the game.

Probability Advantage: The probability advantage of ${\mathcal{A}}_2^1$ can be defined as: $Ad{v}_{{\mathcal{A}}_2^1}^{IND-CCA2}\left(k\right)=|Pr[{\beta }^{*}=\beta ]-1/2|$.

4.4.2. Definition 2—Unforgeability (EUF-CMA-Secure)

If any PPT attackers ${\mathcal{A}}_1^2$ and ${\mathcal{A}}_2^2$ cannot win with a non-negligible advantage in the subsequent two games, Game $III$ and Game $IV$, then a URSCS scheme is EUF-CMA-Secure.

Game $III$: This game is played between the adversary ${\mathcal{A}}_1^2$ and $\mathcal{C}$. The specific process is as follows.

Initialization: Initialization is similar to Game I.

Inquiry: ${\mathcal{A}}_1^2$ submits oracle queries, and $\mathcal{C}$ returns relevant results.

Forgery: ${\mathcal{A}}_1^2$ outputs a forged ciphertext ${\epsilon }^{*}$ with $RI{D}^{*}$ and $RE{V}^{*}={\left\{IP{K}_j^{*}\right\}}_{j=1}^u$. If the forged ciphertext ${\epsilon }^{*}$ can be decrypted correctly by any recipient, ${\mathcal{A}}_1^2$ wins the game.

Probability Advantage: The probability advantage of ${\mathcal{A}}_1^2$ can be defined as: $Ad{v}_{{\mathcal{A}}_1^2}^{EUF-CMA}\left(k\right)=Pr[MulDeSignCrypt\left({\epsilon }^{*}\right)\ne \perp ]$.

Game $IV$: This game is played between the adversary ${\mathcal{A}}_2^2$ and $\mathcal{C}$. The specific process is as follows.

Initialization: Initialization is similar to Game $II$.

Inquiry: ${\mathcal{A}}_2^2$ submits oracle queries, and $\mathcal{C}$ returns relevant results.

Forgery: ${\mathcal{A}}_2^2$ outputs a forged ciphertext ${\epsilon }^{*}$ with $RI{D}^{*}$ and $RE{V}^{*}={\left\{IP{K}_j^{*}\right\}}_{j=1}^u$. If the forged ciphertext ${\epsilon }^{*}$ can be decrypted correctly by any recipient, ${\mathcal{A}}_2^2$ wins the game.

Probability Advantage: The probability advantage of ${\mathcal{A}}_2^2$ can be defined as:

$Ad{v}_{{\mathcal{A}}_2^2}^{EUF-CMA}\left(k\right)=Pr[MulDeSignCrypt\left({\epsilon }^{*}\right)\ne \perp ]$.

5. The Proposed URSCS Scheme

5.1. Basic Algorithms

This section introduces the implementation details of basic algorithms one-by-one, which will be used to construct our URSCS scheme in Section 5.2.

(1) $(params,msk)\leftarrow Setup\left(k\right):$ Given a security parameter k, the TCC generates an elliptic curve G with a generator P and order q. It chooses a random element $msk\in Z_q^{*}$ as the system’s master private key and generates the corresponding master public key $MPK=mskP$. Then, it generates six cryptographic hash functions: $H_1:G\to {\{0,1\}}^{\left|ID\right|}$, $H_2:G\times {\{0,1\}}^{\left|ID\right|}\times G\times G\to Z_q^{*}$, $H_3:G\times G\times G\times {\{0,1\}}^{\left|ID\right|}\times G\to Z_q^{*}$, $H_4:Z_q^{*}\times G\times {\{0,1\}}^{\left|ID\right|}\to {\{0,1\}}^{2\left|G\right|+\left|m\right|}$, $H_5:G\times {\{0,1\}}^{\left|ID\right|}\times {\{0,1\}}^{*}\times {\{0,1\}}^m\times G\times G\times G\times Z_q^{*}\to Z_q^{*}$, and $H_6:G\times G\times {\{0,1\}}^{\left|ID\right|}\to {\{0,1\}}^{2\left|G\right|+\left|m\right|}$, where $\left|ID\right|$ represents the length of the real ID and is determined by security parameter, $\left|G\right|$ is the length of the string representation of a point on the elliptic curve, and $\left|m\right|$ represents the length of a single message and is determined by security parameter. Then, TCC obtains the system’s master secret key $msk$ and the common parameters $params=\{G,P,MPK,H_1,H_2,H_3,H_4,H_5,H_6\}$.

(2)$(isk,IPK)\leftarrow RSURegister\left(RID\right):$ TCC chooses a random element $isk\in Z_q^{*}$ as the identification secret key of RSU and generates the corresponding identification public key $IPK=iskP$.

(3)$(rsk,isk,IPK)\leftarrow VelRegister\left(RID\right):$ When a vehicle with real identity $RID$ requests registration, TCC first generates a revocation key $rsk$ for the vehicle as follows: TCC maintains a pool of prime numbers $PoolPN$, each of which is unique, and when a vehicle needs to be assigned a revocation key, one is taken from the $PoolPN$ and assigned to it. Then, the real identity $RID$ of the vehicle and its corresponding revocation key $rsk$ are saved to the association table of TCC in the form of $(RID,rsk,true)$, where the value $true$ indicates that the current vehicle is legal. This mechanism allows TCC to quickly retrieve the revocation key of any vehicle when necessary, while maintaining a record of the vehicle’s legitimacy status. When a vehicle is judged as malicious, its corresponding entity will be changed to $(RID,rsk,false)$, and the associated revocation key $rsk$ is sent to the revocation pool $PoolREV$ with the form $(rsk,t_{rev})$, where $t_{rev}$ indicates the timestamp of revocation. When a vehicle needs to be allocated a revocation key, but the prime numbers in $PoolPN$ have been exhausted, it is necessary to obtain a prime number from $PoolREV$, and the prime number needs to be checked to see if its revocation time exceeds threshold $T_{rev}$. If the revocation time has exceeded $T_{rev}$, it can be reused; otherwise, the process will continue to wait. Since the survival time of each pseudonym, $T_{pid}$, is less than $T_{rev}$, if a malicious vehicle’s revocation key has been revoked for longer than $T_{rev}$, it means that the pseudonyms generated by the malicious vehicle before it was revoked are no longer available. This mechanism ensures that malicious vehicles cannot continue sending messages after their revocation keys have been reassigned to new vehicles. For more details, one can refer to Section 6.1.7. Subsequently, TCC selects a random number $isk\in Z_q^{*}$ as the identification secret key and generates the corresponding identification public key $IPK=iskP$.

(4)$({\{s{k}_j,P{K}_j\}}_{j=1}^n)\leftarrow GenMK(RID):$ The vehicle with real identity $RID$ selects n random numbers ${\left\{s{k}_j\right\}}_{j=1}^n\in Z_q^{*}$ as private keys, generates the corresponding n public keys ${\{P{K}_j=s{k}_{j}P\}}_{j=1}^n$, keeps ${\left\{s{k}_j\right\}}_{j=1}^n$ in secret, and publishes ${\left\{P{K}_j\right\}}_{j=1}^n$.

(5)$({\left\{PI{D}_j\right\}}_{j=1}^n,{\left\{pp{k}_j\right\}}_{j=1}^{n}or\perp )\leftarrow GenPIDandPPK(RID,{\left\{P{K}_j\right\}}_{j=1}^n,msk):$ The vehicle transmits its own real identity $RID$ and a set of public keys ${\left\{P{K}_j\right\}}_{j=1}^n$ to TCC, and TCC can verify whether the vehicle is legal by checking the association table $(RID,rsk,true/false)$. If the value in the association table corresponding to the $RID$ and $rsk$ is $true$, then TCC performs the following procedure, otherwise TCC returns ⊥.

• TCC generates a set of pseudonyms containing n elements ${\left\{PI{D}_j\right\}}_{j=1}^n$ associated with $RID$, each of which is structured as $PI{D}_j=(PI{D}_j^1,PI{D}_j^2,t_j^{pid})$, where $t_j^{pid}$ is the timestamp used to control the lifetime of $PID$, $PI{D}_j^1=x_{j}P$, $PI{D}_j^2=RID\oplus H_1(mskPI{D}_j^1)$, and $x_j\in Z_q^{*}$.
• TCC randomly chooses n random elements $z_j\in Z_q^{*}$, obtains n points $Y_j=z_{j}P$ on the corresponding elliptic curve, and then computes $h_j=H_2(PI{D}_j,Y_j,P{K}_j)$ and $y_j=z_j+h_{j}msk$, for $j=1,\cdots ,n$, hence, TCC obtains a set of partial public-private key pairs ${\{pp{k}_j=(y_j,Y_j)\}}_{j=1}^n$.

(6)$(b,B,batVal)\leftarrow GenRovSK(count,{\left\{rs{k}_j\right\}}_{j=1}^{count}):$ The $count$ here represents the number of existing legal vehicles in the TCC domain, and ${\left\{rs{k}_j\right\}}_{j=1}^{count}$ are the corresponding revocation secret keys for each legal vehicle. When there are vehicles joining or exiting, the value $count$ would be automatically changed accordingly. TCC first selects a random prime number $b\in PoolPN$ as the master revocation secret key and then removes b from the $PoolPN$. When the system needs to be allocated a master revocation secret key, but the prime numbers in $PoolPN$ have been exhausted, the handling mechanism employed is identical to the $VelRegister$ method. TCC generates $B=bP$ and utilizes CRT to construct other parts of the master revocation public key, calculating $\alpha ={\prod }_{j=1}^{count}rs{k}_j,{\alpha }_j=\alpha /rs{k}_j$. TCC computes the multiplicative inverse ${\theta }_j$ of ${\alpha }_j$ modulo $rs{k}_j$, satisfying ${\theta }_j{\alpha }_j\equiv 1mod(rs{k}_j)$. Since $rs{k}_j$ are different prime numbers, $rs{k}_j$ and ${\alpha }_j$ are coprime, which implies that the multiplicative inverse ${\theta }_j$ of ${\alpha }_j$ modulo $rs{k}_j$ exists. Next, TCC calculates $Sum={\sum }_{j=1}^{count}{\theta }_j{\alpha }_j$ and $batVal=bSum$. Finally, TCC secretly keeps the master revocation secret key b and makes $(B,batVal)$ public.

(7)$(\epsilon )\leftarrow MulSignCrypt(m,PI{D}_s,s{k}_s,P{K}_s,y_s,Y_s,rs{k}_s,REV={\left\{IP{K}_j\right\}}_{j=1}^u):$ Assume that vehicle $V_s$ needs to send message m to a group of entities $REV$. Vehicle $V_s$ selects a set of unused $(PI{D}_s,s{k}_s,P{K}_s,y_s,Y_s)$, and performs the following calculations, removing these parameters from the vehicle parameter pool. The vehicle calculates the revocation master key $b=batValmodrs{k}_s$, which is equivalent to the master revocation secret key b that is selected by TCC. The equivalence can be validated as follows.

$$\begin{array}{cc}\hfill b& =batValmodrs{k}_s\hfill \\ \hfill & =(bSum)modrs{k}_s\hfill \\ \hfill & =(b\sum _{j=1}^{count}{\theta }_j{\alpha }_j)modrs{k}_s\hfill \\ \hfill & =(b({\theta }_1\prod _{j=2}^{count}rs{k}_j+{\theta }_2\prod _{j=1,j\ne 2}^{count}rs{k}_j+\cdots +{\theta }_s\hfill \\ & \prod _{j=1,j\ne s}^{count}rs{k}_j+\cdots +{\theta }_{count}\prod _{j=1}^{count-1}rs{k}_j))modrs{k}_s\hfill \\ \hfill & =(b({\theta }_s\prod _{j=1,j\ne s}^{count}rs{k}_j))modrs{k}_s\hfill \\ \hfill & =b.\hfill \end{array}$$

(2)

In Equation (2), the values of the intermediate variables are set at the TCC side as follows: $\alpha ={\prod }_{j=1}^{count}rs{k}_j$, ${\alpha }_j=\alpha /rs{k}_j$, ${\theta }_j{\alpha }_j\equiv 1mod(rs{k}_j),sum={\sum }_{j=1}^{count}{\theta }_j{\alpha }_j$, $batVal=bsum$. Obviously, the master revocation secret key b calculated by the sending vehicle is the same as b set by the TCC.

Then, vehicle $V_s$ selects a random number $r\in Z_q^{*}$, and calculates $R=rP$. For each identity public key $IP{K}_j\in REV$, vehicle $V_s$ calculates ${\omega }_j=(r+b)IP{K}_j$ and $k_j=H_3({\omega }_j,IP{K}_j,PI{D}_s,R)$. Then, it randomly selects a session key $SK\in Z_q^{*}$, constructs a polynomial $f(x)={\prod }_{j=1}^u(x-k_j)+SK=a_0+a_1{x}^1+a_2{x}^2+\cdots +a_{u-1}{x}^{u-1}+x^u$, and calculates the ciphertext $C=H_4(SK,PI{D}_s)\oplus (P{K}_s\left|\right|Y_s\left|\right|m)$. The vehicle then selects a timestamp t and calculates $d_1=H_5(PI{D}_s,t,m,P{K}_s,Y_s,R,1)$, $d_2=H_5(PI{D}_s,t,m,P{K}_s,Y_s,R,2)$, $d_3=H_5(PI{D}_s,t,m,P{K}_s,Y_s,R,3)$, $\rho =r+d_1{y}_s+d_{2}s{k}_s+d_{3}b$. The vehicle can obtain the signcrypted information $\epsilon =(PI{D}_s,C,\rho ,t,R,a_0,a_1,\dots ,a_{u-1})$, which is broadcast to all entities, including many vehicles or RSUs.

(8)$(mor\perp )\leftarrow MulDeSignCrypt(\epsilon ):$ Assuming that vehicle $V_j$ receives the signcrypted message $\epsilon$, it first checks the validity of the timestamp t. If the timestamp has expired, it returns ⊥, rejecting the signcrypt information. If the timestamp is valid, the vehicle obtains the timestamp $t_s^{pid}$ from $PI{D}_s$, and then verifies whether the existence time of the $PI{D}_s$ exceeds threshold $T_{pid}$. If the existence time exceeds $T_{pid}$, it returns ⊥; otherwise, it continues to perform the following operations. Note that $T_{pid}$ should be less than $T_{rev}$ to prevent malicious vehicles from continuing to send messages after their revocation keys are reassigned to the new vehicles.

Vehicle $V_j$ uses the master revocation public key B, its own identity private key $is{k}_j$, the identity public key $IP{K}_j$, R and $PI{D}_s$ from the signcrypted message to calculate ${\omega }_j=is{k}_j(R+B)$, $k_j=H_3({\omega }_j,IP{K}_j,PI{D}_s,R)$, and constructs a polynomial $f(x)=a_0+a_1{x}^1+a_2{x}^2+\cdots +a_{u-1}{x}^{u-1}+x^u$ according to the received elements $a_0,a_1,\dots ,a_{u-1}$. Then vehicle $V_j$ calculates the session key $SK=f(k_j)$, $(P{K}_s,Y_s,m)=H_4(SK,PI{D}_s)\oplus C$, and computes $d_1=H_5(PI{D}_s,t,m,P{K}_s,Y_s,R,1)$, $d_2=H_5(PI{D}_s,t,m,P{K}_s,Y_s,R,2)$, $d_3=H_5(PI{D}_s,t,m,P{K}_s,Y_s,R,3)$, $h_s=H_2(PI{D}_s,Y_s,P{K}_s)$. Vehicle $V_j$ verifies if Equation (3) holds.

$$\begin{array}{cc}\hfill \rho P& =R+d_1{Y}_s+d_1{h}_{s}MPK+d_{2}P{K}_s+d_{3}B\hfill \end{array}$$

(3)

If the equality in (3) holds, it accepts the message m; otherwise, it rejects the message. If the target receiving vehicle is the same as the current receiving vehicle $V_j$, the calculated values will be the same as those of the sending vehicle. The correctness of Equation (3) can be validated as follows.

$$\begin{array}{cc}\hfill L.H.S.& =(r+d_1{y}_s+d_{2}s{k}_s+d_{3}b)P\hfill \\ \hfill & =rP+d_1{y}_{s}P+d_{2}s{k}_{s}P+d_{3}bP\hfill \\ \hfill & =R+d_1{y}_{s}P+d_{2}P{K}_s+d_{3}B\hfill \\ \hfill & =R+d_1{z}_{s}P+d_1{h}_{s}mskP+d_{2}P{K}_s+d_{3}B\hfill \\ \hfill & =R+d_1{Y}_s+d_1{h}_{s}MPK+d_{2}P{K}_s+d_{3}B\hfill \\ \hfill & =R.H.S.\hfill \end{array}$$

(4)

In Equation (4), the intermediate variables were set at the sending side as follows: $\rho =r+d_1{y}_s+d_{2}s{k}_s+d_{3}b$, $B=bP$, $R=rP$, $y_s=z_s+h_{s}msk$, $h_s=H_2(PI{D}_s,Y_s,P{K}_s)$, $Y_s=z_{s}P$, and the values $d_1$, $d_2$, and $d_3$ on the sending side are: $d_1=H_5(PI{D}_s,t,m,P{K}_s,Y_s,R,1)$, $d_2=H_5(PI{D}_s,t,m,P{K}_s,Y_s,R,2)$, $d_3=H_5(PI{D}_s,t,m,P{K}_s,Y_s,R,3)$.

(9)$(\xi )\leftarrow SigSignCrypt(m,PI{D}_s,s{k}_s,P{K}_s,y_s,Y_s,rs{k}_s,IP{K}_r):$ Assume that vehicle $V_s$ needs to send message m to a specific vehicle or RSU. The vehicle calculates the revocation master key $b=batValmodrs{k}_s$, which would be equivalent to the master revocation secret key b that is selected by TCC. Then, it selects a random number $r\in Z_q^{*}$ and calculates $R=rP$. Next, vehicle $V_s$ selects a set of unused parameters $(PI{D}_s,s{k}_s,P{K}_s,y_s,Y_s)$, performs the following steps, and removes these parameters from the vehicle parameter pool. Using the identity public key $IP{K}_j$ of the receiving vehicle or RSU, it calculates ${\omega }_j=(r+b)IP{K}_j$, and computes the ciphertext $C=H_6({\omega }_j,PI{D}_s)\oplus (P{K}_s\left|\right|Y_s\left|\right|m)$. The vehicle then selects a timestamp t and calculates $d_1=H_5(PI{D}_s,t,m,P{K}_s,Y_s,R,1)$, $d_2=H_5(PI{D}_s,t,m,P{K}_s,Y_s,R,2)$, $d_3=H_5(PI{D}_s,t,m,P{K}_s,Y_s,R,3)$, $\rho =r+d_1{y}_s+d_{2}s{k}_s+d_{3}b$. The vehicle can obtain the signcryption information $\xi =(PI{D}_s,C,\rho ,t,R)$, which is broadcast to all entities.

(10)$(mor\perp )\leftarrow SigDeSignCrypt(\xi ):$ Assuming that vehicle $V_j$ receives the signcrypted message $\xi$, it first checks the validity of the timestamp t. If the timestamp has expired, it returns ⊥, rejecting the signcrypt information. If the timestamp is valid, the vehicle obtains the timestamp $t_s^{pid}$ from $PI{D}_s$, and then verifies whether the existence time of the $PI{D}_s$ exceeds threshold $T_{pid}$. If the existence time exceeds $T_{pid}$, it returns ⊥; otherwise, it continues to perform the following steps. The vehicle uses the master revocation public key B, its own identification private key $is{k}_j$, the identification public key $IP{K}_j$, the random point R and $PI{D}_s$ from the signcrypted message to calculate ${\omega }_j=is{k}_j(R+B)$, $(P{K}_s\left|\right|Y_s\left|\right|m)=H_6({\omega }_j,PI{D}_s)\oplus C$, and computes $d_1=H_5(PI{D}_s,t,m,P{K}_s,Y_s,R,1)$, $d_2=H_5(PI{D}_s,t,m,P{K}_s,Y_s,R,2)$, $d_3=H_5(PI{D}_s,t,m,P{K}_s,Y_s,R,3)$, $h_s=H_2(PI{D}_s,Y_s,P{K}_s)$. Vehicle $V_j$ verifies if Equation (5) holds.

$$\begin{array}{c}\hfill \rho P=R+d_1{Y}_s+d_1{h}_{s}MPK+d_{2}P{K}_s+d_{3}B\end{array}$$

(5)

If true, it accepts the message m; otherwise, it rejects the message. The validity of Equation (5) can be proved as in Equation (4).

5.2. URSCS Construction

This section utilizes the algorithms detailed in the previous section to form our URSCS scheme. It consists of five stages, namely, initialization, registration, signcryption, designcryption, as well as trace and revocation.

5.2.1. Initialization

First, TCC executes the system initialization algorithm $Setup\left(k\right)$, obtaining the system master key $msk$ and system public parameters $params=\{G,P,MPK,H_1,H_2,H_3,H_4,H_5,H_6\}$. Next, it publicly discloses $params$ and secretly holds the system master key $msk$.

5.2.2. Registration

The vehicle sends its real identity $RID$ to TCC to request registration. TCC executes the $VelRegister\left(RID\right)$ algorithm, generates the identification secret key $isk$, the identification public key $IPK$, and the revocation key $rsk$. TCC sends $isk$, $IPK$, and $rsk$ to the registering vehicle through a secure channel. The vehicle secretly stores $isk$ and $rsk$ within the tamper-proof device of the OBU and publishes the identification public key $IPK$. $RID$ cannot be disclosed, so the $IPK$ is used instead of the $RID$ as the long-term identity and made public to all entities.

The RSU sends its $RID$ to TCC to request registration. TCC executes the $RSURegister\left(RID\right)$ algorithm, generates the identification secret key $isk$ and the identification public key $IPK$. TCC then sends $isk$ and $IPK$ to the registering RSU through a secure channel. The RSU secretly keeps the $isk$ and publishes the $IPK$. In the multi-receiver signcryption scenario, the receivers can be either vehicles or RSUs. To unify the identifiers of the receivers, the identification public keys of the RSUs are used to replace their real IDs.

The registered vehicle executes the vehicle key generation algorithm $GenMK(RID)$, generating a set of public-private key pairs: $({\left\{s{k}_j\right\}}_{j=1}^n$, ${\left\{P{K}_j\right\}}_{j=1}^n)$. The vehicle sends $RID$ and ${\left\{P{K}_j\right\}}_{j=1}^n$ to the TCC to request generation of pseudonyms and partial keys. Upon receiving this request, TCC executes the $GenPIDandPPK(RID,{\left\{P{K}_j\right\}}_{j=1}^n,msk)$ algorithm, verifies the legitimacy of the requesting vehicle, then generates a set of pseudonyms ${\left\{PI{D}_j\right\}}_{j=1}^n$ and a set of partial keys ${\left\{pp{k}_j\right\}}_{j=1}^n$, and sends these pseudonyms and partial keys to the requesting vehicle through a secure channel. And then, to facilitate information retrieval, the vehicle correctly matches each pseudonym with its corresponding public-private key pair and partial key pair, and stores them in a secure pool as $(PI{D}_j,s{k}_j,P{K}_j,pp{k}_j)$. To ensure unlinkability, the vehicle consumes one of these tuples $(PI{D}_j,s{k}_j,P{K}_j,pp{k}_j)$ each time it sends a message.

TCC executes the revocation key generation algorithm $GenRovSK(count,{\left\{rs{k}_j\right\}}_{j=1}^{count})$, thereby obtaining the current system’s master revocation secret key b, master revocation public key B, and the auxiliary value $batVal$. Finally, TCC secretly keeps the master revocation secret key b and publishes $(B,batVal)$.

5.2.3. Signcryption

Vehicles can signcrypt messages for multiple recipients or a single recipient.

In the multiple recipients scenario, each time a vehicle sends a message, it first selects a pseudonym and a key tuple $(PI{D}_s,s{k}_s,P{K}_s,y_s,Y_s)$ from the secure pool, and removes this pseudonym and its related key pair from the pool. When the pseudonyms and key tuples in the pool are about to be depleted, the vehicle re-executes the $GenMK\left(RID\right)$ algorithm and requests TCC to execute the $GenPIDandPPK(RID,{\left\{P{K}_j\right\}}_{j=1}^n,msk)$ algorithm to replenish the pool. The vehicle selects specific recipients $REV={\left\{IP{K}_j\right\}}_{j=1}^u$, and executes the multi-recipient signcryption algorithm $MulSignCrypt(m,PI{D}_s,s{k}_s,P{K}_s,y_s,Y_s,rs{k}_s,REV)$ to obtain the signcrypted information $\epsilon$, and broadcasts it to multiple recipients.

In the single-recipient scenario, each time a vehicle sends a message, it first selects a pseudonym and a key tuple $(PI{D}_s,s{k}_s,P{K}_s,y_s,Y_s)$ from the secure pool. The vehicle selects a specific recipient and executes the single-recipient signcryption algorithm $SigSignCrypt(m,PI{D}_s,s{k}_s,P{K}_s,y_s,Y_s,rs{k}_s,IP{K}_j)$, obtains and broadcasts the signcrypted information $\xi$. The management of pseudonyms and keys in the secure pool is the same as in the multi-recipient signcryption scenario.

5.2.4. Designcryption

The designcryption stage also includes multi-recipient designcryption and single-recipient designcryption.

In multi-recipient designcryption, only the recipient specified by the sender can obtain the correct session key $SK$ and successfully designcryption the message if ${\omega }_j=is{k}_j(R+B)$ calculated by the recipient matches ${\omega }_j=(r+b)IP{K}_j$ calculated by the sender.

Single-recipient designcryption shares the same principles as in multi-recipient designcryption and is omitted here.

5.2.5. Trace and Revocation

If an RSU or vehicle detects suspicious behavior from a malicious vehicle, it can submit the corresponding pseudonym $PI{D}_f=(PI{D}_f^1,PI{D}_f^2,t_f^{pid})$ to TCC. Then, TCC calculates $RI{D}_f=PI{D}_f^2\oplus H_1(mskPI{D}_f^1)$ using the system master secret key $msk$ and the pseudonym $PI{D}_f$ to obtain $RI{D}_f$ of the malicious vehicle.

Then, TCC receives the revocation secret key $rs{k}_f$ from the association pair $(RI{D}_f,rs{k}_f,$ $true)$ of the association table, removes the $rs{k}_f$ of the malicious vehicle from the revocation key set ${\left\{rs{k}_j\right\}}_{j=1}^{count}$, and adds it to $PoolREV$ as $(rs{k}_f,t_{rev})$, then changes the association pair $(RI{D}_f,rs{k}_f,true)$ to $(RI{D}_f,rs{k}_f,false)$. TCC then randomly selects a new master revocation secret key $b^{new}$ and calculates $B^{new}=b^{new}P$. By employing CRT, TCC re-executes the procedure of generating the remaining part of the master revocation public key, the specific implementation procedure can be found in the $GenRovSK$ algorithm described in Section 5.1. Note that the revocation secret key of the malicious vehicle has been deleted, so $\alpha ={\prod }_{j=1}^{count-1}rs{k}_j$, where $count$ represents the number of legitimate vehicle. Finally, TCC secretly keeps the new master revocation secret key $b^{new}$ and publishes the new master revocation public key $(B^{new},batVa{l}^{new})$. The vehicle whose revocation secret key $rs{k}_f$ has been deleted cannot obtain the latest master revocation secret key $b^{new}$ using $batVa{l}^{new}$ mod $rs{k}_f$, but other normal vehicles can.

6. Security Analysis

In this section, we provide the informal security analysis, and formal security proof of the proposed URSCS scheme.

6.1. Informal Security Analysis

We show that the proposed scheme URSCS meets the security and privacy goals proposed in Section 4.3.

6.1.1. Authentication

In the proposed URSCS scheme, only the legitimate vehicle can obtain revocation secret key $rsk$ through registration; furthermore, only the legitimate vehicle can obtain the master revocation secret key b using $rsk$ and send messages. From another perspective, only legitimate vehicles can obtain their own secret keys and compute $\rho$ using their own secret keys, and receivers can verify the validity of $\rho$ using the sender’s public key, the system’s master public key, and the system’s master revocation public key. The formal security analysis, Theorems 3 and 4, also demonstrate the unforgeability of signatures under the CDHP. Therefore, our URSCS scheme achieves vehicle authentication, ensuring that senders are legitimate vehicles in the system.

6.1.2. Data Confidentiality

The confidentiality of message m is protected by the session key $SK$. The sender encrypts m as $C=H_4(SK,PI{D}_s)\oplus (P{K}_s\left|\right|Y_s\left|\right|m)$, and only the legitimate recipient can compute the session key $SK$, and then obtain the decrypted message $(P{K}_s\left|\right|Y_s\left|\right|m)=H_4(SK,PI{D}_s)\oplus C$. Additionally, formal security proofs of Theorems 1 and 2 would demonstrate that if the CDHP is hard to solve, then malicious users cannot obtain the real data, ensuring the confidentiality of the data.

6.1.3. Data Integrity

As shown in Section 5.1, the recipient needs to calculate the hash values $d_1$, $d_2$, and $d_3$ before receiving the message in designcryption process. Since $d_1$, $d_2$, and $d_3$ are calculated in the same manner at both the sender’s and receiver’s ends, for example, the calculation method for $d_1$ at both ends is $d_1=H_5(PI{D}_s,t,m,P{K}_s,Y_s,R,1)$. The message m is one of the inputs to the hash function $H_5$. Suppose the message m is tampered with during transmission, the hash values $d_1$, $d_2$, $d_3$ calculated at the sender’s end will be different from those calculated by the recipient, and the verification process will fail. Therefore, our scheme ensures data integrity.

6.1.4. Anonymity

In our URSCS scheme, a pseudonym mechanism is employed to achieve sender anonymity. To extract RID, an attacker needs to calculate $RID=PI{D}^2\oplus H_1\left(mskPI{D}^1\right)$; therefore, the attacker must obtain $msk$ or solve the ECDLP problem. Since only TCC knows the system’s master secret key $msk$, and the ECDLP is hard to solve, the adversary cannot infer the real $RID$ from $PID$. Thus, our scheme achieves sender anonymity.

On the other hand, the identification public key $IPK$ is used to replace real $RID$ for message reception. Other than the sender, no other entity can infer the message recipient from intercepted ciphertext messages. Therefore, our URSCS achieves receiver anonymity.

6.1.5. Unlinkability

Our URSCS scheme achieves anonymity by hiding the $RID$ under $PID$. In generating pseudonyms, each pseudonym is calculated using a random number x. When a vehicle performs the signcryption function, the random numbers $SK,r,t$ are used; thus, no adversary can link any vehicle through pseudonyms or ciphertexts from the same sender. Furthermore, even if the malicious vehicles obtain the public keys from the ciphertexts, they cannot link to the vehicle through the public keys because the vehicle needs to fetch a new pseudonym and the corresponding public-private key from the security pool before each signcryption operation. Therefore, our URSCS achieves unlinkability.

6.1.6. Traceability

In the event of a dispute or the discovery of malicious behavior, TCC can obtain the true identity of the vehicle through the equation $RI{D}_f=PI{D}_f^2\oplus H_1\left(mskPI{D}_f^1\right)$, where $RI{D}_f$ is the real identity of the malicious vehicle and $PI{D}_f=(PI{D}_f^1,PI{D}_f^2,t_f^{pid})$ is the pseudonym of the malicious vehicle. Thus, our URSCS system can achieve tracking functionality while maintaining the anonymity of vehicles.

6.1.7. Revocability

After tracking the malicious vehicle $V_f$, TCC removes the revocation key $rs{k}_f$ of $V_f$ from the revocation secret key set ${\left\{rs{k}_j\right\}}_{j=1}^{count}$ and adds it to $PoolREV$. Then, TCC randomly selects a new master revocation secret key $b^{new}$ and calculates $B^{new}=b^{new}P$. Next, TCC uses the CRT to construct the other part of the master revocation public key, and calculates $\alpha ={\prod }_{j=1}^{count-1}rs{k}_j$; thus, the revocation secret key of $V_f$ has been removed. Then, TCC calculates ${\alpha }_j=\alpha /rs{k}_j$, finds the multiplicative inverse ${\theta }_j$ of ${\alpha }_{j}modrs{k}_j$, and computes $Sum={\sum }_{j=1}^{count-1}{\theta }_j{\alpha }_j$, $batVa{l}^{new}=b^{new}Sum$. Finally, the TCC retains the master revocation secret key $b^{new}$ secretly and publishes the master revocation public key $(B^{new},batVa{l}^{new})$. $V_f$ can no longer obtain the latest master revocation secret key $b^{new}$ through $batVa{l}^{new}modrs{k}_f$; thus, $V_f$ will be unable to send valid messages again.

In our URSCS scheme, if $rs{k}_f$ is reallocated to a new vehicle, it implies that the existing time of $rs{k}_f$ in the revocation pool $PoolREV$ has exceeded threshold $T_{rev}$, as the threshold $T_{pid}$ is less than the threshold $T_{rev}$; therefore, the pseudonyms of $V_f$ cannot be used, and this method is used to prevent malicious vehicles from continuing to send messages after their revocation keys are reassigned to the new vehicles.

6.1.8. Resistance to Impersonation Attacks

In our URSCS scheme, the malicious vehicle $V_f$ with real identity $RI{D}_f$ can intercept the master revocation public key B, and the ciphertext $\epsilon =(PI{D}_s,C,\rho ,t,R)$, but it cannot obtain the private key $(y_s,s{k}_s)$ of vehicle $V_s$ with the pseudonym $PI{D}_s$. If the malicious vehicle wants to impersonate vehicle $V_s$, it may attempt to use its key pair $(s{k}_f,P{K}_f,y_f,Y_f)$ and the pseudonym $PI{D}_s$ of a legitimate vehicle $V_s$ to send information, since $y_f=z_f+H_2(PI{D}_f,Y_f,P{K}_f)msk$ (which contains the pseudonym $PI{D}_f$ of the malicious vehicle). However, the malicious vehicle passed $PI{D}_s$ to the recipients, the receivers need to compute $h_s=H_2(PI{D}_s,Y_f,P{K}_f)$, and this will not satisfy the verification Equation (3). Therefore, our URSCS scheme can resist impersonation attacks.

6.1.9. Resistance to Replay Attacks

In our scheme, each transmitted ciphertext $\epsilon =(PI{D}_s,C,\rho ,t,R)$ contains a timestamp t. After receiving these messages, the receiver can determine if a replay attack has occurred by checking their timestamps. Therefore, our scheme can resist replay attacks.

6.1.10. Resistance to Ephemeral Secret Leakage Attacks

In our scheme, the session key $SK$ is randomly chosen by the sender for each transmission. Due to the randomness of the session key and the lack of correlation between the session keys chosen for different transmissions, even if a specific session key is disclosed, it does not threaten the already created session keys or those to be created. Therefore, our scheme ensures the freshness of the session keys, can resist ephemeral secret leakage attacks, and also possesses forward and backward security.

6.1.11. Resistance to Man-in-the-Middle Attacks

Since our scheme achieves authentication and integrity guarantee, it can resist man-in-the-middle attacks.

In the same manner, we have analyzed the security and privacy goals achieved by schemes [8,13,17,18].

Table 2. Comparison of security properties.

Security Indicators	[8]	[13]	[17]	[18]	Ours
Authentication	✓	✓	✓	✓	✓
Confidentiality	✓	✓	✓	✓	✓
Integrity	✓	✓	✓	✓	✓
Vehicle Anonymity	✓	✕	✓	✓	✓
Receiver Anonymity	✓	✓	✓	✓	✓
Unlinkability	✓	✕	✓	✓	✓
Traceability	✓	✕	✕	✓	✓
Revocability	✕	✕	✕	✓	✓
Resis-Imper	✓	✓	✓	✓	✓
Resis-Replay	✓	✓	✕	✓	✓
Resis-ESL	✓	✓	✓	✓	✓
Resis-Man	✓	✓	✓	✓	✓

✓ indicates that the security function is enabled; ✕ that the security function is not enabled.

elaborates on the comparison of these properties between our USS-MR scheme and similar schemes, namely [8,13,17,18]. The identifiers Resis-Imper, Resis-Replay, Resis-ESL, and Resis-Man represent resistance to impersonation attacks, resistance to replay attacks, resistance to ephemeral secret leakage attacks, and resistance to man-in-the-middle attacks, respectively. As shown in Table 2, only our URSCS scheme and scheme [18] can meet all security and privacy goals.

6.2. Formal Security Proof

6.2.1. Confidentiality

Our URSCS scheme achieves confidentiality as shown in Theorems 1 and 2.

Theorem 1.

Assume that ${\mathcal{A}}_1^1$ can win Game I with non-negligible advantage δ, then $\mathcal{C}$ can solve CDHP with non-negligible advantage ${\delta }^{\prime }$.

Proof of Theorem 1.

Assume that challenger $\mathcal{C}$ obtains an instance of the CDHP $(P,\kappa P,\tau P)$ and attempts to compute $\kappa \tau P$. The interaction between $\mathcal{C}$ and ${\mathcal{A}}_1^1$ is as follows.

Initialization: $\mathcal{C}$ executes the initialization algorithm $Setup\left(k\right)$ to generate system parameters $params=\{G,P,MPK,H_1,H_2,H_3,H_4,H_5\}$, where $MPK=\kappa P$, and sends the system parameters $params$ to ${\mathcal{A}}_1^1$.

Phase 1: $\mathcal{C}$ selects a sender with real identity $RI{D}^{*}$ and u receivers with real identities $REVID{s}^{*}={\left\{RI{D}_j^{*}\right\}}_{j=1}^u$ for ${\mathcal{A}}_1^1$. $\mathcal{C}$ executes the algorithm $VelRegister\left(RI{D}_j^{*}\right)$ or $RSURegister\left(RI{D}_j^{*}\right)$ where $j\in \{1,2,\dots ,u\}$ to obtain ${\{is{k}_j^{*},IP{K}_j^{*}\}}_{j=1}^u$. $\mathcal{C}$ publishes the receivers’ identification public keys $RE{V}^{*}={\left\{IP{K}_j^{*}\right\}}_{j=1}^u$ and keeps the private keys of the receivers privately.

$\mathcal{C}$ executes the algorithm $GenMK\left(RI{D}^{*}\right)$ to obtain ${\{s{k}_j^{*},P{K}_j^{*}\}}_{j=1}^n$ and executes the algorithm $GenPIDandPPK(RI{D}^{*},{\left\{P{K}_j^{*}\right\}}_{j=1}^n,msk)$ to obtain ${\{PI{D}_j^{*},PP{K}_j^{*}\}}_{j=1}^n$. $\mathcal{C}$ keeps five lists $L_{H1}$, $L_{H2}$, $L_{H3}$, $L_{H4}$, which are initially empty, and $L_{H5}$. Then, ${\mathcal{A}}_1^1$ adaptively conducts a polynomially bounded number of queries as follows.

${\mathbf{H}}_{\mathbf{1}}\mathbf{Query}:$ $\mathcal{C}$ receives $PI{D}_j^{*}$. If there exists a corresponding tuple $(PI{D}_j^{1*},{\lambda }_j)$ in $L_{H1}$, $\mathcal{C}$ sends ${\lambda }_j$ to ${\mathcal{A}}_1^1$; otherwise, $\mathcal{C}$ selects ${\lambda }_j\in {\{0,1\}}^{\left|ID\right|}$ and sends ${\lambda }_j$ to ${\mathcal{A}}_1^1$. Also, the tuple $(PI{D}_j^{1*},{\lambda }_j)$ is inserted into the list $L_{H1}$.

${\mathbf{H}}_{\mathbf{2}}\mathbf{Query}:$ $\mathcal{C}$ receives $\{PI{D}_j^{*},Y_j^{*},P{K}_j^{*}\}$. If there exists a corresponding tuple $(PI{D}_j^{*},Y_j^{*},P{K}_j^{*},h_j)$ in $L_{H2}$, $\mathcal{C}$ sends $h_j$ to ${\mathcal{A}}_1^1$; otherwise, $\mathcal{C}$ selects $h_j\in Z_q^{*}$ and sends $h_j$ to ${\mathcal{A}}_1^1$. Also, the tuple $(PI{D}_j^{*},Y_j^{*},P{K}_j^{*},h_j)$ is inserted into the list $L_{H2}$.

${\mathbf{H}}_{\mathbf{3}}\mathbf{Query}:$ $\mathcal{C}$ receives $\{{\omega }_r^{*},IP{K}_r^{*},PI{D}_j^{*},R\}$. If there exists a corresponding tuple $({\omega }_r^{*},IP{K}_r^{*},PI{D}_j^{*},R,k_j)$ in $L_{H3}$, $\mathcal{C}$ sends $k_j$ to ${\mathcal{A}}_1^1$; otherwise, $\mathcal{C}$ selects $k_j\in Z_q^{*}$ and sends $k_j$ to ${\mathcal{A}}_1^1$. Also, the tuple $({\omega }_r^{*},IP{K}_r^{*},PI{D}_j^{*},R,k_j)$ is inserted into the list $L_{H3}$.

${\mathbf{H}}_{\mathbf{4}}\mathbf{Query}:$ $\mathcal{C}$ receives $\{SK,PI{D}_j^{*}\}$. If there exists a corresponding tuple $(SK,PI{D}_j^{*},{\mu }_j)$ in $L_{H4}$, $\mathcal{C}$ sends ${\mu }_j$ to ${\mathcal{A}}_1^1$; otherwise, $\mathcal{C}$ selects ${\mu }_j\in {\{0,1\}}^{2\left|G\right|+\left|M\right|}$ and sends ${\mu }_j$ to ${\mathcal{A}}_1^1$. Also, the tuple $(SK,PI{D}_j^{*},{\mu }_j)$ is inserted into the list $L_{H4}$.

${\mathbf{H}}_{\mathbf{5}}\mathbf{Query}:$ $\mathcal{C}$ receives $\{PI{D}_j^{*},t,m,P{K}_j^{*},Y_j^{*},R\}$. If there exists a corresponding tuple $(PI{D}_j^{*},t,m,P{K}_j,Y_j,R,d_1,d_2,d_3)$ in $L_{H5}$, $\mathcal{C}$ sends $(d_1,d_2,d_3)$ to ${\mathcal{A}}_1^1$; otherwise, $\mathcal{C}$ selects $d_1\in Z_q^{*},d_2\in Z_q^{*},d_3\in Z_q^{*}$ and sends $(d_1,d_2,d_3)$ to ${\mathcal{A}}_1^1$. Also, the tuple $(PI{D}_j^{*},t,m,P{K}_j,Y_j,R,d_1,d_2,d_3)$ is inserted into the list $L_{H5}$.

$\mathcal{C}$ keeps three empty lists $L_{rk}$, $L_{vk}$, and $L_{ppk}$. Next, $\mathcal{C}$ responds to hash oracles queries from ${\mathcal{A}}_1^1$ as follows.

revokeKeyExtractQuery: Upon receiving $RID$, if $RID=RI{D}^{*}$, $\mathcal{C}$ terminates the game; otherwise, $\mathcal{C}$ checks if there exists a corresponding tuple $(RID,isk,IPK,rsk)$ in $L_{rk}$. If true, $\mathcal{C}$ sends $rsk$ to ${\mathcal{A}}_1^1$; otherwise, $\mathcal{C}$ randomly selects a prime number $rsk$ and sends it to ${\mathcal{A}}_1^1$. Also, $\mathcal{C}$ inserts the tuple $(RID,isk,IPK,rsk)$ into $L_{rk}$.

secretValueExtractQuery: Upon receiving $RID$, if $RID=RI{D}^{*}$, $\mathcal{C}$ terminates the game; otherwise, $\mathcal{C}$ checks if there exists a corresponding tuple $(RID,s{k}_j,P{K}_j)$ in $L_{vk}$. If true, $\mathcal{C}$ sends $s{k}_j$ to ${\mathcal{A}}_1^1$; otherwise, $\mathcal{C}$ randomly selects a $s{k}_j\in Z_q^{*}$, calculates $P{K}_j=s{k}_{j}P$, and sends $s{k}_j$ to ${\mathcal{A}}_1^1$. Also, $\mathcal{C}$ inserts the tuple $(RID,s{k}_j,P{K}_j)$ into $L_{vk}$.

publicValueExtractQuery: Upon receiving $RID$, if $RID=RI{D}^{*}$, $\mathcal{C}$ terminates the game; otherwise, $\mathcal{C}$ checks if there exists a corresponding tuple $(RID,s{k}_j,P{K}_j)$ in $L_{vk}$. If such a tuple exists, $\mathcal{C}$ sends $P{K}_j$ to ${\mathcal{A}}_1^1$; otherwise, $\mathcal{C}$ randomly selects a $s{k}_j\in Z_q^{*}$, calculates $P{K}_j=s{k}_{j}P$, and sends $P{K}_j$ to ${\mathcal{A}}_1^1$. Also, $\mathcal{C}$ inserts the tuple $(RID,s{k}_j,P{K}_j)$ into $L_{vk}$.

partialPrivateKeyQuery: Upon receiving $RID$, if $RID=RI{D}^{*}$, $\mathcal{C}$ terminates the game; otherwise, $\mathcal{C}$ checks if there exists a corresponding tuple $(RID,P{K}_j,PI{D}_j,pp{k}_j)$ in $L_{ppk}$. If such a tuple exists, $\mathcal{C}$ sends $pp{k}_j$ to ${\mathcal{A}}_1^1$; otherwise, $\mathcal{C}$ randomly selects $z_j\in Z_q^{*}$ and computes $Y_j=z_{j}P$, randomly selects $PID\in G$, then $\mathcal{C}$ executes $H_{2}Query$ to obtain $h_j$, and sends $pp{k}_j=(y_j=z_j+\kappa h_j,Y_j)$ to ${\mathcal{A}}_1^1$. Also, $\mathcal{C}$ inserts the tuple $(RID,P{K}_j,PI{D}_j,pp{k}_j)$ into $L_{ppk}$.

replacePublicKeyQuery: ${\mathcal{A}}_1^1$ randomly selects $(Y_j,P{K}_j)$ within an appropriate range to replace the complete public key $(Y_j^{\prime },P{K}_j^{\prime })$ of identity $RID$. If $RID=RI{D}^{*}$, then $\mathcal{C}$ stops the game; otherwise, $\mathcal{C}$ updates the list $L_{vk}$ with $(RID,s{k}_j,P{K}_j^{\prime })$, and updates the list $L_{ppk}$ with $(RID,P{K}_j,PI{D}_j,pp{k}_j^{\prime })$.

mulSignCryptQuery: Upon receiving $PI{D}_j$, $RE{V}^{*}={\left\{IP{K}_j^{*}\right\}}_{j=1}^u$ and m, $\mathcal{C}$ makes the following response:

(a) If $PI{D}_j\ne PI{D}_j^{*}$, challenger $\mathcal{C}$ makes $revokeKeyExtractQuery$, $secretValueExtractQuery$, $publicValueExtractQuery$, and $partialPrivateKeyQuery$ to obtain $(s{k}_j,P{K}_j,pp{k}_j,rsk)$. Next, $\mathcal{C}$ runs $MulSignCrypt(m,PI{D}_s,s{k}_s,P{K}_s,y_s,Y_s,rs{k}_s,REV={\left\{IP{K}_j\right\}}_{j=1}^u)$ to get $\epsilon =(PI{D}_s,C,\rho ,t,R,a_0,a_1,\dots ,a_{u-1})$, then sends it to ${\mathcal{A}}_1^1$.

(b) Otherwise, $\mathcal{C}$ randomly chooses $r,sk,{\left\{k_j\right\}}_{j=1}^u,t,d_1,d_2,d_3\in Z_q^{*}$ and $\zeta \in {\{0,1\}}^{2\left|G\right|+\left|m\right|}$. Next, $\mathcal{C}$ calculates $b=batValmodrsk$, $R=rP$, ${\omega }_j=(r+b)IP{K}_j,(j=1,2,\dots ,u)$, constructs a polynomial $f\left(x\right)={\prod }_{j=1}^u(x-k_j)+SK=a_0+a_1{x}^1+a_2{x}^2+\cdots +a_{u-1}{x}^{u-1}+x^u$, and calculates the ciphertext $C=\zeta \oplus \left(P{K}_s\right|\left|Y_s\right|\left|m\right)$, and $\rho =r+d_1{y}_s+d_{2}s{k}_s+d_{3}b$. Then, it updates $L_{H3}$, $L_{H4}$, and $L_{H5}$. Finally, $\mathcal{C}$ sends $\epsilon =(PI{D}_s,C,\rho ,t,R,a_0,a_1,\dots ,a_{u-1})$ to ${\mathcal{A}}_1^1$.

mulDeSignCryptQuery: Upon receiving $\epsilon =(PI{D}_j,C,\rho ,t,R,a_0,a_1,\dots ,a_{u-1})$ to ${\mathcal{A}}_1^1$, $\mathcal{C}$ obtains $h_j$,$r,sk,{\left\{k_j\right\}}_{j=1}^u,t,d_1,d_2,d_3\in Z_q^{*}$ and $\zeta \in {\{0,1\}}^{2\left|G\right|+\left|m\right|}$ from $L_{H2}$, $L_{H3}$, $L_{H4}$, and $L_{H5}$. And $\mathcal{C}$ calculates ${\{{\omega }_j=s{k}_j(R+B)\}}_{j=1}^u$, and constructs a polynomial $f\left(x\right)=a_0+a_1{x}^1+a_2{x}^2+\cdots +a_{u-1}{x}^{u-1}+x^u$ using the received polynomial coefficients: $a_0,a_1,\dots ,a_{u-1}$. Then $\mathcal{C}$ calculates the session key $SK=f\left(k_j\right)$, $(P{K}_s,Y_s,m)=\zeta \oplus C$. Finally, $\mathcal{C}$ sends $(P{K}_s,Y_s,m)$ to ${\mathcal{A}}_1^1$.

Challenge: After the above queries, ${\mathcal{A}}_1^1$ generates $m_0,m_1$, $PIDs$, and $REV={\left\{IP{K}_j\right\}}_{j=1}^u$, then sends them to $\mathcal{C}$, where $m_0$ and $m_1$ are two messages of different content and equal length. Next, $\mathcal{C}$ selects $\beta \in \{0,1\}$. $\mathcal{C}$ randomly chooses $r,sk,{\left\{k_j\right\}}_{j=1}^u,t,d_1,d_2,d_3\in Z_q^{*}$ and $\zeta \in {\{0,1\}}^{2\left|G\right|+\left|m\right|}$. Next, $\mathcal{C}$ calculates $b=batValmodrsk$, $R=rP$, ${\{{\omega }_j=(r+b)IP{K}_j\}}_{j=1}^u$, constructs a polynomial $f\left(x\right)={\prod }_{j=1}^u(x-k_j)+SK=a_0+a_1{x}^1+a_2{x}^2+\cdots +a_{u-1}{x}^{u-1}+x^u$, and calculates the ciphertext $C=\zeta \oplus \left(P{K}_s\right|\left|Y_s\right|\left|m_{\beta }\right)$, and $\rho =r+d_1{y}_s+d_{2}s{k}_s+d_{3}b$. Then, it stores them in $L_{H3}$, $L_{H4}$, and $L_{H5}$, respectively. Finally, $\mathcal{C}$ sends ${\epsilon }^{*}=(PI{D}_s,C,\rho ,t,R,a_0,a_1,\dots ,a_{u-1})$ to ${\mathcal{A}}_1^1$.

Phase 2: ${\mathcal{A}}_1^1$ can execute the same series of above queries except for $mulDeSignCryptQuery\left({\epsilon }^{*}\right)$.

Guess: ${\mathcal{A}}_1^1$ guesses a bit $\beta \in \{0,1\}$ and wins the game if $\beta ={\beta }^{\prime }$.

If ${\mathcal{A}}_1^1$ wants to succeed, it must obtain correct keys ${\left\{k_j\right\}}_{j=1}^u$ and the corresponding ${\left\{{\omega }_j\right\}}_{j=1}^u$. Then, $\mathcal{C}$ outputs the solution of CDHP: $\kappa \tau P={\left(d_1{h}_j\right)}^{-1}\rho P{K}_j+(\kappa \rho -{\omega }_j){\left(d_1{d}_2\right)}^{-1}P-(\kappa +s{k}_j)({\left(h_j\right)}^{-1}{Y}_j+{\left(d_1{h}_j\right)}^{-1}{d}_{2}P{K}_j)-(\kappa +s{k}_j)(1-batVal)b{\left(d_2{h}_j\right)}^{-1}$. Thus, $\mathcal{C}$ can solve CDHP with an advantage $\delta ={\delta }^{\prime }$ in time $t^{\prime }<t+O(Q_{pk}+Q_s+Q_u)$. □

Theorem 2.

Assume that ${\mathcal{A}}_2^1$ can win Game I with non-negligible advantage δ, then $\mathcal{C}$ can solve CDHP with non-negligible advantage ${\delta }^{\prime }$.

Proof of Theorem 2.

Suppose challenger $\mathcal{C}$ obtains an instance of the CDHP problem $(P,\kappa P,\tau P)$ and attempts to compute $\kappa \tau P$. $\mathcal{C}$ and ${\mathcal{A}}_2^1$ can perform the same interactions as Theorem 1. In this game ${\mathcal{A}}_2^1$ knows $msk=\kappa$, but it cannot initiate $replacePublicKeyQuery$.

Guess: ${\mathcal{A}}_2^1$ guesses a bit $\beta \in \{0,1\}$ and wins the game if $\beta ={\beta }^{\prime }$.

If ${\mathcal{A}}_2^1$ wants to succeed, it must obtain correct keys ${\left\{k_j\right\}}_{j=1}^u$ and the corresponding ${\left\{{\omega }_j\right\}}_{j=1}^u$. Then, $\mathcal{C}$ outputs the solution of CDHP: $\kappa \tau P=(\kappa \rho P-{\omega }_{j}P-\kappa d_1{Y}_j-d_{2}P{K}_j+(1-d_{3}B)){\left(d_1\right)}^{-1}$. Thus, $\mathcal{C}$ can solve CDHP with an advantage $\delta ={\delta }^{\prime }$ in time $t^{\prime }<t+O(Q_{pk}+Q_s+Q_u)$. □

6.2.2. Unforgeability

Our scheme can achieve unforgeability, which is shown in Theorems 3 and 4.

Theorem 3.

Assume that ${\mathcal{A}}_1^2$ can win Game $III$ with non-negligible advantage δ, then $\mathcal{C}$ can solve CDHP with non-negligible advantage ${\delta }^{\prime }$.

Proof of Theorem 3.

Suppose challenger $\mathcal{C}$ obtains a CDHP instance $(P,\kappa P,\tau P)$ and attempts to compute $\kappa \tau P$. $\mathcal{C}$ and ${\mathcal{A}}_1^2$ can perform the same interactions as stage 1 and stage 2 in Theorem 1.

Forgery: ${\mathcal{A}}_1^2$ outputs a forgery ${\epsilon }^{{*}^{\prime }}=(PI{D}_s^{*},C^{*},{\rho }^{*},t^{*},R^{*},a_0,a_1,\dots ,a_{u-1})$ with $PI{D}_s^{*}$. And ${\mathcal{A}}_1^2$ cannot query the secret key on $PI{D}_s^{*}$. If the equation $R^{*}={\rho }^{*}P-d_1{Y}_j^{*}-d_1{h}_j^{*}bP-d_2(s{k}_j+\kappa )P-d_{3}B$ holds, ${\mathcal{A}}_1^2$ will succeed. Finally, $\mathcal{C}$ receives the forged signature ${\epsilon }^{{*}^{\prime }}=(PI{D}_s^{*},C^{*},{\rho }^{*}=r^{*}+d_1{y}^{*}+d_2(s{k}_j+\kappa )+d_{3}b,t^{*},R^{*},a_0,a_1,\dots ,a_{u-1})$.

After the relevant queries are executed, the corresponding public key with the same identity will be changed. Therefore, $\mathcal{C}$ can forge a signature with an advantage ${\delta }^{\prime }=\delta$ in time $t^{\prime }<t+O(Q_{pk}+Q_s+Q_u)$. □

Theorem 4.

Assume that ${\mathcal{A}}_2^2$ can win Game $IV$ with non-negligible advantage δ, then $\mathcal{C}$ can solve CDHP with non-negligible advantage ${\delta }^{\prime }$.

Proof of Theorem 4.

Assume that challenger $\mathcal{C}$ obtains a CDHP instance $(P,\kappa P,\tau P)$ and attempts to compute $\kappa \tau P$. $\mathcal{C}$ and ${\mathcal{A}}_2^2$ can perform the same interactions as stage 1 and stage 2 in Theorem 2.

Forgery: ${\mathcal{A}}_2^2$ outputs a forgery ${\epsilon }^{{*}^{\prime }}=(PI{D}_s^{*},C^{*},{\rho }^{*},t^{*},R^{*},a_0,a_1,\dots ,a_{u-1})$ with $PI{D}_s^{*}$. And ${\mathcal{A}}_2^2$ cannot query the secret key on $PI{D}_s^{*}$. If the equation $R^{*}={\rho }^{*}P-d_1{Y}_j^{*}-d_1{h}_j^{*}\kappa P-d_2(s{k}_j+\tau )P-d_{3}B$ holds, ${\mathcal{A}}_2^2$ will succeed. Finally, $\mathcal{C}$ receives the forged signature ${\epsilon }^{{*}^{\prime }}=(PI{D}_s^{*},C^{*},{\rho }^{*}=r^{*}+d_1{y}^{*}+d_2(s{k}_j+\tau )+d_{3}b,t^{*},R^{*},a_0,a_1,\dots ,a_{u-1})$.

After the relevant queries are executed, the corresponding public key with the same identity will be changed. Therefore, $\mathcal{C}$ can forge a signature with an advantage ${\delta }^{\prime }=\delta$ in time $t^{\prime }<t+O(Q_{pk}+Q_s+Q_u)$. □

7. Performance Evaluation

In this section, we evaluate the performance of our URSCS scheme, and then compare computation overheads and communication overheads of our URSCS with those of the state-of-the-art provably secure signcryption schemes, specifically Yang et al., 2022 [8], Yang et al., 2022 [13], Deng 2020, [17], Liang et al., 2023 [18]. Since the registration phase is a one-time process in the scenario of VANETs, the computation and communication overheads can be neglected; therefore, we focus on the signcryption phase (the signcryption of messages during one-to-many communication) and the unsigncryption phase.

7.1. Computation Overhead

To calculate the computational overhead, we conducted simulations using a pairing-based cryptography library and a multi-precision integer and rational arithmetic C/C++ library. The execution times for common cryptographic operations were obtained by averaging multiple execution times with different input values. We denote the execution time of a modular exponentiation operation as $T_{mod}$, the execution time of a scale multiplication on ECC as $T_{me}$, the execution time of a point addition on ECC as $Tae$, the execution time of a bilinear mapping operation as $T_{bm}$, the execution time of a scale multiplication on bilinear pairing as $T_{mbm}$, and the execution time of a hash operation as $T_h$. Additionally, the execution times of those operations on a desktop equipped with an 11th Gen Intel(R) Core(TM) i7-11800H processor operating at 2.30 GHz and 16.0 GB of RAM are summarized in

Table 3. Execution time of basic operations.

Notation	Description	Run Time (ms)
$T_m$	Modular exponentiation	0.224
$T_{me}$	Scale multiplication on ECC	0.518
$T_{ae}$	Point addition on ECC	0.018
$T_{bm}$	Bilinear mapping operation	5.917
$T_{mbm}$	Scale multiplication on bilinear pairing	1.919
$T_h$	Hash operation	0.002

. The execution times of other operations, such as hashing, are so small that they can be neglected compared to the operations mentioned above; therefore, their times are not considered in our experiments.

In our URSCS scheme, the signcryption phase requires $u+1$ scalar multiplications operations on ECC, $u+4$ hash operations, where u represents the number of receivers, so the signcryption cost of our scheme is $(u+1)T_{me}+(u+4)T_h$. Similarly, the unsigncryption phase needs $5u$ point addition operations on ECC, $6u$ scalar multiplications operations on ECC, $6u$ hash operations. Thus, the unsigncryption cost of our scheme is $5u{T}_{ae}+6u{T}_{me}+6u{T}_h$, and the total computation cost of our scheme can be expressed as $(7u+1)T_{me}+(7u+4)T_h+5u{T}_{ae}$.

In scheme Yang et al., 2022 [8], the signcryption needs $6u$ scalar multiplication operations on ECC, $4u$ point addition operations on ECC, and $5u$ hash operations, so the signcryption cost is $6u{T}_{me}+4u{T}_{ae}+5u{T}_h$. Similarly, the unsigncryption needs $3u$ scalar multiplication operations on ECC, $5u-4$ point addition operations on ECC, $4u+3$ hash operations, and 5 bilinear pairing operations, so the unsigncryption cost is $3u{T}_{me}+(5u-4)T_{ae}+(4u+3)T_h+5T_{bm}$, and the total computation cost of scheme Yang et al., 2022 [8] is $9u{T}_{me}+(9u-4)T_{ae}+(9u+3)T_h+5T_{bm}$.

In scheme Yang et al., 2022 [13], the signcryption phase needs $3u$ scalar multiplication operations on ECC, u point addition operations on ECC, u modular exponentiation operations, and $3u$ hash operations, so the signcryption cost is $3u{T}_{me}+u{T}_{ae}+u{T}_m+3u{T}_h$. Similarly, the unsigncryption phase needs $3u$ scalar multiplication operations on ECC, $3u$ point addition operations on ECC, $3u$ hash operations, and u bilinear pairing operations, so the unsigncryption cost is $3u{T}_{me}+3u{T}_{ae}+3u{T}_h+u{T}_{bm}$. Then, the total computation cost of scheme Yang et al., 2022 [13] is $6u{T}_{me}+4u{T}_{ae}+u{T}_m+6u{T}_h+u{T}_{bm}$.

In scheme Deng 2020, [17], the signcryption phase needs $2u+3$ scalar multiplication operations on ECC and u bilinear pairing operations, so the signcryption cost is $(2u+3)T_{me}+u{T}_{bm}$. Similarly, the unsigncryption phase needs one bilinear pairing operation and one modular exponentiation operation, so the unsigncryption cost is $T_{bm}+T_m$. Then, the total computation cost of scheme Deng 2020, [17] is $(u+1)T_{bm}+(2u+3)T_{me}+T_m$.

In scheme Liang et al., 2023 [18], the signcryption phase needs $u+1$ scalar multiplication operations on ECC, $u+4$ hash operations. So the signcryption cost is $(u+1)T_{me}+(u+4)T_h$. Similarly, the unsigncryption phase needs $6u$ scalar multiplication operations on ECC, $5u$ point addition operations on ECC, and $6u$ hash operations, so the unsigncryption cost is $6u{T}_{me}+5u{T}_{ae}+6u{T}_h$. Then, the total computation cost of schemeLiang et al., 2023 [18] is $(7u+1)T_{me}+(7u+4)T_h+5u{T}_{ae}$.

Also,

Table 4. Comparison of computation overhead.

Scheme	Signcryption (ms)	UnSigncryption (ms)	Total Cost (ms)
Ours	$(u+1)T_{me}+(u+4)T_h$	$5u{T}_{ae}+6u{T}_{me}+6u{T}_h$	$(7u+1)T_{me}+(7u+4)T_h+5u{T}_{ae}$
Yang et al., 2022 [8]	$6u{T}_{me}+4u{T}_{ae}+5u{T}_h$	$3u{T}_{me}+(5u-4)T_{ae}+(4u+3)T_h+5T_{bm}$	$9u{T}_{me}+(9u-4)T_{ae}+(9u+3)T_h+5T_{bm}$
Yang et al., 2022 [13]	$3u{T}_{me}+u{T}_{ae}+u{T}_m+3u{T}_h$	$3u{T}_{me}+3u{T}_{ae}+3u{T}_h+u{T}_{bm}$	$6u{T}_{me}+4u{T}_{ae}+u{T}_m+6u{T}_h+u{T}_{bm}$
Deng 2020, [17]	$(2u+3)T_{me}+u{T}_{bm}$	$T_{bm}+T_m$	$(u+1)T_{bm}+(2u+3)T_{me}+T_m$
Liang et al., 2023 [18]	$(u+1)T_{me}+(u+4)T_h$	$6u{T}_{me}+5u{T}_{ae}+6u{T}_h$	$(7u+1)T_{me}+(7u+4)T_h+5u{T}_{ae}$

shows the total computation cost of each algorithm, respectively. The experimental comparison is depicted in Figure 2, where the number of receivers has increased from 0 to 30. This figure evidently shows that our scheme has apparent advantages over schemes Yang et al., 2022 [8], Yang et al., 2022 [13], Deng 2020, [17]. The efficiency of scheme Liang et al., 2023 [18] is similar to that of our scheme, but its receivers are limited to RSUs, while the receivers of our scheme can be both RSUs and vehicles, with greater flexibility.

7.2. Communication Overhead

In this section, given a secure length of 128 bits [13], we compared the communication overhead of our URSCS scheme with those of the state-of-the-art provably secure signcryption schemes, specifically Yang et al., 2022 [8], Yang et al., 2022 [13], Deng 2020, [17], Liang et al., 2023 [18]. In schemes based on bilinear pairing, the size of the element in $G_T$ is 128 bytes, namely $\left|G_T\right|=128$ bytes; while in schemes based on ECC, the size of the elements in G is 64 bytes, namely $\left|G\right|=64$ bytes. The size of the elements in $Z_q^{*}$, real identity, message, the timestamp are 32 bytes, 32 bytes, 32 bytes, 4 bytes, respectively, namely $\left|Z_q^{*}\right|=32$ bytes, $\left|RID\right|=32$ bytes, $\left|m\right|=32$ bytes, $\left|t\right|=4$ bytes.

In our URSCS scheme, during the processes of signcryption and unsigncryption, the information that needs to be transmitted is $\epsilon =(PI{D}_s,C,\rho ,t,R,a_0,a_1,\dots ,a_{u-1})$, where the size of pseudonym $PI{D}_s=(PI{D}_s^1=x_{s}P,PI{D}_s^2=RID\oplus H_1\left(mskPI{D}_s^1\right),t_s^{pid})$ is $(64+32+4)=100$ bytes, the size of ciphertext $C=H_4(SK,PI{D}_s)\oplus (P{K}_s\left|\right|Y_s\left|\right|m)$ is $(64+64+32)=160$ bytes, and u indicates the number of receivers. So the total communication overhead is $(64+32+4)+(64+64+32)+32+4+64+32u$ = $360+32u$ bytes.

We utilized the same method to compute the communication overheads of the schemes [8,13,17,18], where the results are illustrated in Figure 3 and

Table 5. Comparison of communication overhead.

Scheme	Communication Overhead (bytes)
Ours	$(u+1)\left|Z_q^{*}\right|+4\left|G\right|+\left|m\right|+2\left|t\right|+\left|RID\right|=360+32u$
Yang et al., 2022 [8]	$(2u+1)\left|G\right|+u(Z_q^{*}+\left|m\right|)=64+192u$
Yang et al., 2022 [13]	$u\left|G\right|+u\left|m\right|=96u$
Deng 2020, [17]	$(u+1)\left|Z_q^{*}\right|+2\left|G\right|+\left|C\right|=208+32u$
Liang et al., 2023 [18]	$2\left|Z_q^{*}\right|+4\left|G\right|+\left|m\right|+\left|t\right|+\left|RID\right|=388$

. Compared to other schemes, our approach has lower communication overhead. Although the communication overhead of the scheme Liang et al., 2023 [18] is lower than that of our scheme, but it did not consider the issue of elements needing to be coprime in the CRT, and it also has the limitation that messages can only be sent to RSUs. Similarly, although scheme Deng 2020, [17] has lower communication overhead, its computational cost is too high, and it lacks tracking and revocation functions.

7.3. Comparison of Revocation Public Key Transmission Overhead

Scheme Liang et al., 2023 [18] is the most outstanding unlinkable multi-recipient scheme with revocation mechanism so far. However, the implementation of its revocation key mechanism requires the construction of a complex polynomial. The number of coefficients of the polynomial is the same as the number of vehicles. The master revocation public key parameters to be transmitted are $\{B,a_0,a_1,a_2,...,a_{count-1}\}$, where B is a point on the discrete elliptic curve group, and $a_0,a_1,a_2,...,a_{count-1}\in Z_q^{*}$, which are the coefficients of the polynomial. Therefore, the communication overhead for transmitting the master revocation public key parameters is $64+32count$ bytes. When there are a large number of vehicles within the domain of a TCC, such as 100,000 vehicles, the master revocation public key parameters generated at one time will include 100,001 numbers. On the other hand, the update of the master revocation public key is relatively frequent. When a vehicle joins the TCC’s domain or a vehicle needs to be revoked, the master revocation secret key and master revocation public key need to be updated again. Thus, the overhead of scheme Liang et al., 2023 [18] in transmitting the master revocation public key is significant.

To reduce the communication overhead of transmitting the revocation public key, we present a new revocation key mechanism based on CRT. The revocation public key parameters to be transmitted are $(B,batVal)$, where B is a point on the discrete elliptic curve group, and $batVal\in Z_q^{*}$. Regardless of the number of vehicles within the TCC domain, the communication overhead for transmitting the master revocation public key parameters is fixed, namely 96 bytes $(64+32)$. Thus, our URSCS scheme has an absolute advantage in the transmission overhead of the revocation public key. Figure 4 demonstrates the apparent advantage of our scheme in transmission overhead of transmitting the revocation public key.

8. Conclusions

Based on the advantages of certificateless and signcryption, we developed a secure multi-receiver unlinkable communication scheme, allowing a sender to send the same signcryption information to multiple receivers, which can be either vehicles or RSUs. Through anonymous transmission and the instant update of key pairs when sending messages, our scheme ensures that malicious attackers cannot trace the sender through multiple messages originating from the same source, thereby achieving the unlinkability of the sender. Moreover, this paper also constructed a revocation key mechanism with low communication cost by utilizing CRT. Furthermore, the comprehensive security analysis demonstrated that our scheme exhibits superior security performance. In comparison with the state-of-the-art schemes, our scheme has low communication overhead and computation overhead. Note that this scheme solely focuses on a secure multi-receiver communication scheme under only one TCC, and the secure communication among various TCCs remains unexplored in this paper, which will be a key focus of our future research.