CHAM-CLAS: A Certificateless Aggregate Signature Scheme with Chameleon Hashing-Based Identity Authentication for VANETs

Abstract

Vehicular ad hoc networks (VANETs), which are the backbone of intelligent transportation systems (ITSs), facilitate critical data exchanges between vehicles. This necessitates secure transmission, which requires guarantees of message availability, integrity, source authenticity, and user privacy. Moreover, the traceability of network participants is essential as it deters malicious actors and allows lawful authorities to identify message senders for accountability. This introduces a challenge: balancing privacy with traceability. Conditional privacy-preserving authentication (CPPA) schemes are designed to mitigate this conflict. CPPA schemes utilize cryptographic protocols, including certificate-based schemes, group signatures, identity-based schemes, and certificateless schemes. Due to the critical time constraints in VANETs, efficient batch verification techniques are crucial. Combining certificateless schemes with batch verification leads to certificateless aggregate signature (CLAS) schemes. In this paper, cryptanalysis of Xiong’s CLAS scheme revealed its vulnerabilities to partial key replacement and identity replacement attacks, alongside mathematical errors in the batch verification process. Our proposed CLAS scheme remedies these issues by incorporating an identity authentication module that leverages chameleon hashing within elliptic curve cryptography (CHAM-CLAS). The signature and verification modules are also redesigned to address the identified vulnerabilities in Xiong’s scheme. Additionally, we implemented the small exponents test within the batch verification module to achieve Type III security. While this enhances security, it introduces a slight performance trade-off. Our scheme has been subjected to formal security and performance analyses to ensure robustness.

1. Introduction

In the contemporary global pursuit of intelligent cities, the Internet of Things (IoT) is the primary facilitator of device connectivity and communication, through which an immeasurable amount of data exchange and utilization occurs. A particular use case of the IoT is the Internet of Vehicles (IoV), which encapsulates cooperative intelligent transportation systems (C-ITSs) that employ vehicular ad hoc networks (VANETs). VANETs are self-organized networks that enable communication between the constituents of any C-ITS, namely vehicles, pedestrians, roadside units (RSUs), and possibly governing entities, which we will refer to as trusted authorities (TAs) [1,2]. The primary objective of a C-ITS is to facilitate a safer and more comfortable driving experience for all of its constituents by allowing vehicles to sense their surrounding environments and pool their collective resources to make reliable decisions [3].

The primary standards employed in vehicular communications are the Dedicated Short-Range Communications (DSRC) standard developed in the US and the Intelligent Transportation System (ITS-G5) protocol created by the European Telecommunications Standards Institute (ETSI) [3]. However, recent years have witnessed the emergence of a competitive alternative, Cellular Vehicle-to-Everything (C-V2X), which promises lower latency and high vehicle speed support [4]. Furthermore, developments to DSRC and C-V2X are already underway in pursuit of better efficiency and scalability, and new technologies like 802.11bd and New Radio V2X [5] promise to meet the stringent requirements of a maximum packet error rate of 10% with a minimum transmission radius of 300 m.

Owing to the significance of the data shared between different C-ITS constituents, guaranteeing security is as important as optimizing performance, since any breach with malicious intent can have disastrous consequences. Therefore, authentication, confidentiality, integrity, privacy, and revocability are non-negotiable security requirements to ensure the proper functioning of VANETs.

To that effect, a multitude of works have strived to create conditional privacy-preserving authentication (CPPA) schemes, which can be broadly classified into certificate-based schemes/public key infrastructure (PKI) schemes, identity-based schemes (IB), group signature (GS)-based schemes and certificateless (CL) schemes. Furthermore, to support scenarios of large vehicular densities, techniques to verify a batch of digital signatures simultaneously have been developed. This has led to the transformation of IB and CL schemes into identity-based batch verification (IBV) schemes and certificateless aggregated signature (CLAS) schemes, respectively.

Many recent CLAS schemes fail to guarantee adequate identity authentication, resulting in collusion, repudiation, and impersonation attacks. Furthermore, the same schemes fail to properly include a revocation check that prevents TA-revoked members from re-accessing the VANET. We show that these deficiencies exist in the recently published CLAS scheme [6] by Xiong and propose an alternative scheme that averts the associated risks and better meets VANET security requirements.

Accordingly, our contributions can be summarized as follows:

1-

We cryptanalyze Xiong’s scheme and point out that it cannot meet VANET security requirements.

2-

We propose an alternative CLAS scheme with an added identity authentication module based on chameleon hashing [7]. This module prevents repudiation attacks and fake identity attacks and ensures that revoked vehicles are denied access to the VANET.

3-

We conduct a formal security and performance analysis of our scheme.

The rest of this paper is set out as follows. Section 2 introduces a brief review of related works. Section 3 summarizes the background information, including VANET security requirements, cryptographic primitives utilized in the proposed scheme, and the network model. Section 4 presents a brief overview of Xiong’s scheme [6] as well as our cryptanalysis, suggested attacks, and modified scheme. Section 5 presents the formal security analysis of our proposed scheme. Section 6 presents the performance analysis of our scheme. Section 7 presents conclusions and future directions. A list of notations can be found in

Table 1. Notations and definitions.

Notation	Definition
CA	Central Authority
CH	Chameleon Hash
C-ITS	Cooperative Intelligent Transportation System
CL	Certificateless (Scheme)
CLAS	Certificateless Aggregate Signature (Scheme)
CPPA	Conditional Privacy-Preserving Authentication
DSRC	Dedicated Short-Range Communications
EC(C)	Elliptic Curve (Cryptography)
ECDLP	Elliptic Curve Discrete Logarithm Problem
GS	Group Signature
IBC	Identity-Based Cryptography
IBV	Identity-Based Batch Verification (Scheme)
IDS	Intrusion Detection Systems
KGC	Key Generation Center
OBU	On-Board Unit
PKI	Public Key Infrastructure
PID	Pseudo-Identity
PWD	Password
RID	Real Identity
RSU	Roadside Unit
TA/TTP	Trusted Authority/Trusted Third Party
TPD	Tamper Proof Device
TRA/TRM	Tracing Authority/Tracing Manager
VANET	Vehicular Ad Hoc Network
V2I	Vehicle-to-Infrastructure
V2V	Vehicle-to-Vehicle
V2X	Vehicle-to-Everything

.

2. Related Works

As mentioned previously, CPPA schemes can be realized using various cryptographic approaches, including PKI, GS, IBV, or CLAS schemes.

PKI-based schemes typically involve significant overhead due to certificate storage and communication costs, not to mention the time-consuming process of certificate revocation checks. GS-based schemes also face challenges with revocation and high computational costs during signature verification.

In contrast, IB schemes are more efficient as they eliminate the need for certificate management. However, they suffer from the key escrow problem, where the key generation center (KGC) can access each member’s full private key.

CLAS schemes are a variant of IB schemes, where each member possesses a private key that combines a KGC-generated value and a secret value known only to the member. This resolves the key escrow issue, but it is at the expense of increased complexity in public key management, as the public key is no longer solely a function of publicly known information as in traditional IB systems. CLAS schemes are the most prominent tool for achieving CPPA, and significant recent literature has focused on deconstructing previous schemes and developing new ones with improved security.

CPPA schemes are an integral part of VANET security, and numerous surveys have been published in recent years [1,8,9,10] to extensively detail each scheme’s characteristics and conduct comparative analyses in terms of security and performance.

A survey specifically focused on CLAS schemes can be found in [11], which compares the performance of CLAS schemes based on bilinear pairings and CLAS schemes based on ECC. Since bilinear pairings are more computationally intensive and less efficient, we have implemented our CLAS scheme using ECC.

Our proposed scheme most closely resembles those of Zhao (2020) [12], Zhou (2023) [2], Zhu (2023) [13], Li (2020) [14], Thumbur (2020) [15], and finally Xiong (2022) [6], which we aim to analyze and improve in this paper. Accordingly, we will compare the performance of our scheme to those of existing schemes in Section 6.

3. Background

This section establishes the necessary background and prerequisites to our proposed scheme. We briefly overview the security requirements in Vehicular Ad hoc Networks (VANETs); then, we introduce the cryptographic primitives used in our scheme; and finally, we outline the network model upon which our scheme is based.

3.1. VANET Security Requirements

The aforementioned massive data exchange, which is the driving force behind the development of the Internet of Things (IoT) and the Internet of Vehicles (IoV), necessarily requires accompanying security measures to ensure the validity of the data before further use. The security requirements within VANETs are not uniform; instead, they are layered, with distinct demands and considerations at different levels.

Table 2. Security requirements across domains in VANETs.

Security Domain	Security Requirement	Solutions	Description
Communication Layer	Authentication	Digital signatures, PKI	Verify the identity of vehicles and infrastructure units.
	Data integrity	HMAC, digital signatures	Ensure data have not been tampered with during transmission.
	Confidentiality	Encryption (e.g., AES)	Protect sensitive information from eavesdropping.
	Non-repudiation	Digital signatures	Prevent entities from denying their actions.
	Access control	Role-based access control	Restrict access to network resources based on permissions.
Network Layer	Routing security	Secure routing protocols	Prevent malicious routing and forwarding of data.
	DoS and DDoS mitigation	Rate limiting, intrusion detection	Defend against denial-of-service attacks.
	Secure neighbor discovery	Cryptographic neighbor discovery	Ensure vehicles can trust the identity of neighbors.
Application Layer	Vehicle-to-vehicle (V2V)	Secure communication protocols	Secure communication between vehicles.
	Vehicle-to-infrastructure (V2I)	Secure communication with RSUs	Ensure trust in roadside units.
	Location privacy	Pseudonym management, mixed zones	Protect the privacy of vehicle location information.
	Over-the-air updates	Code signing, secure channels	Ensure security when updating software/firmware.
Key Management	Key generation and storage	Hardware security modules, key vaults	Securely create and store cryptographic keys.
	Key distribution	PKI, certificate revocation lists	Safely share keys with authorized entities.
	Key revocation	Certificate revocation lists	Deactivate compromised or unauthorized keys.
Trust Management	Reputation systems	Trustworthiness metrics	Assess the trustworthiness of other network entities.
	Anomaly detection	Intrusion detection systems	Detect and respond to unusual network behavior.
Physical Layer	Jamming resistance	Frequency hopping, signal strength analysis	Protect against signal jamming attacks.
	Secure hardware	Hardware security modules	Ensure the security of on-board vehicle equipment.
Regulatory Compliance	Compliance with standards	Adherence to industry standards	Meet legal and industry standards for VANET security.
	Privacy regulations	Data anonymization, consent management	Adhere to data protection laws and regulations.
Lifecycle Management	Secure deployment	Secure boot process, firmware signing	Ensure secure VANET deployment and initial setup.
	Monitoring and auditing	Security information and event management (SIEM)	Continuously monitor and audit network activities.
	Incident response	Incident response plans	Develop procedures to respond to security incidents.

comprehensively compares these layered security needs, categorized across various critical aspects. From the communication layer to the network and application layers, each aspect highlights the specific security demands, ensuring that VANETs operate securely and reliably. Key management, trust management, physical layer security, regulatory compliance, and lifecycle management aspects further underscore the multifaceted nature of securing VANETs. Understanding and addressing these diverse security requirements is essential to establish a resilient and trustworthy VANET ecosystem. Failure to do so could undermine the intended benefits and functionality of the IoT and IoV technologies.

To utilize the data exchanged between vehicles, the receiver must ensure three things:

• The sender is legitimate and trustworthy.
• The data have not been modified or tampered with.
• The message is temporally relevant and up-to-date.

On the other hand, the sender will only participate in the message exchange if they are assured that their identity privacy is preserved. They want to be sure that only a legitimate governing authority can derive their real identity from the pseudo-identity used in the message transmission.

A combination of cryptographic approaches and intrusion detection methods addresses these requirements. Cryptographic protection is the first line of defense, providing proactive protection against potential attacks and holding the attacker accountable. However, intrusion detection techniques may be employed for mitigation if an attack does occur. This paper focuses exclusively on the cryptographic methods used to preserve secure communications in VANETs. Intrusion detection in VANETs has also been extensively studied in contemporary literature, and reviews of the contributions can be found in [16,17,18].

3.2. Cryptographic Preliminaries

This section provides a brief overview of the cryptographic primitives employed in our scheme.

(1)

Elliptic curves

We assume $F_p$ denotes a finite field with prime order p for elliptic curve E with the equation $y^2=x^3+ax+b$ mod p, where $4a^3+27b^2\ne 0$ and $a,b \in F_p$. We presume that O denotes the point at infinity. The points of the ECC make an additive group G with order q and generator P.

Point addition: Let P and S be two random points on the ECC such that $\left(P, S\right)\in G$, where the point P generates the group G with sizeable prime order q. When $P \ne S$, $R=P+S$ can be computed, where R denotes the intersection point of curve E and line PS. When $P=S$, $R=P+S$ denotes the intersection of curve E with the tangent to E at P.

Scalar point multiplication: The scalar multiplication of E is defined as $mP=P+P+\cdots +P (m times),$ where $m\in Z_q^{*},m>0$.

Elliptic curve discrete logarithm problem (ECDLP): Given two random points P, Q ∈G on curve E, where $Q=xP,x\in Z_q^{*}$; it has proved difficult to calculate x given P, Q.

(2)

Chameleon Hashing

Chameleon hash functions were first proposed in 1998 [7] and are the foundational building block for chameleon signatures. Chameleon signatures facilitate the signer’s undeniable commitment to the contents of a signed document without allowing the recipient to disclose the contents to a third party without the signer’s consent.

Conceptually similar to undeniable signatures, chameleon signatures have the relative advantage of being non-interactive and not requiring zero-knowledge proofs. The key idea is that a sender’s signature allows the recipient to forge further signatures of the signer at the latter’s will. To achieve this, chameleon signatures employ a hash-then-sign method using chameleon hash functions, which are collision-resistant to all parties except those possessing the trapdoor.

In the original paper, two implementations of chameleon hash functions were proposed—one based on the intractability of factoring and the other on the discrete logarithm problem.

The latter methodology features a function $C{H}_y\left(m,r\right)=g^m{y}^r$ for the private key (trapdoor) x and the public key $y=g^x mod p$. Accordingly, the function is equivalent to $C{H}_y\left(m,r\right)=g^m*{\left(g^x\right)}^r=g^{m+xr}.$ To find a collision $r^{\prime }$ for any given message $m^{\prime }$, the owner of the private key $x$ solves $m+xr=m^{\prime }+x{r}^{\prime }$. Our scheme uses a conceptually similar model based on elliptic curve cryptography, discussed in greater detail in Section 3.

3.3. Network Model

The most common network architecture used to model VANET security is the two-layer model, which comprises a TA in the top layer and vehicles and RSUs in the bottom layer.

(1) Trusted authority (TA): Also known as the trusted third party (TTP) or the central authority (CA), the TA generally consists of a key generation center (KGC) and a tracing authority/tracing manager (TRA/TRM). The KGC generates public and private keys (or partial keys) for all members to enable digital signature verification. The TRM generates verifiable pseudo-identities for each member to enable traceability in the case of disputes. Some schemes propose redundant TAs with access to the same data repository to prevent single points of failure.

(2) Roadside units (RSUs): RSUs are connected to the TA via secure wired links and to vehicles via insecure wireless connections. Different schemes assume varying levels of RSU trustworthiness, with the predominant assumption being that RSUs are “honest but curious.” The role of RSUs varies across schemes, ranging from being mere gateways to relay messages between the TA and vehicles to acting as group managers that issue signing and verification keys to members within their domain and manage localized groups.

(3) Vehicles: Vehicles are assumed to be untrustworthy. They are equipped with on-board units (OBUs) that contain a tamper-proof device (TPD). Schemes diverge on the assumption of an ideal TPD (secure enough to store the system’s master secret key for self-authentication) or a realistic TPD (where only the user’s secret key is stored and authentication is performed elsewhere).

4. Xiong’s Scheme: Description, Cryptanalysis, and Our Proposed Improved Scheme

In this section, we provide a brief overview of Xiong’s scheme [6], followed by our cryptanalysis of the scheme, and finally, we propose our modified version of the scheme.

4.1. Overview of Xiong’s Scheme

Xiong’s scheme, like other CLAS (certificateless aggregate signature) schemes, comprises the following phases:

• Setup;
• Pseudo-identity generation;
• Partial private key generation;
• User secret key generation;
• Signing;
• Verification;
• Aggregate signature/batch verification.

Figure 1 provides a summary of Xiong’s scheme.

4.2. Cryptanalysis

The core purpose of any authentication scheme is to enable the receiver of a message to trust its contents. This is achieved through a transitive trust relationship, where the receiver verifies that a trusted authority (TA) deemed the sender trustworthy at a particular time and has not revoked its trust in them since (authentication). Furthermore, to deter any network member from initiating malicious actions, a mechanism is required to ensure their accountability and prevent them from later denying their actions (traceability and non-repudiation). Unfortunately, Xiong’s scheme does not meet these criteria, as detailed in the following analysis.

To guarantee the trustworthiness of a sender, digital signatures are used to incorporate a TA’s contribution along with some identifying information about the signer. CLAS (certificateless aggregate signature) schemes are built on the premise that signatures are trustworthy based on the partial private key generated by the key generation center (KGC), which is incorporated into the digital signature. To resist forgeability, the KGC uses its master secret key (denoted as $\mathit{s}$) and a randomly chosen value (denoted as ${\alpha }_i$) to create a partial private key pair that the user cannot replicate. In Xiong’s scheme, the equation $pp{k}_i=\left({\alpha }_i+s.Q_i\right)mod q$ achieves this property, seeing that during verification (by the user or subsequently by any receiver of the user’s messages), the equation $pp{k}_i.P\stackrel{?}{=}{A}_i+Q_i.P_{pub}$ is used. The idea is that the user cannot generate any pair $(pp{k}_i^{*},A_i^{*})$ to satisfy this equation since Qi.Ppub binds these two values together, and the user cannot generate this since it is a function of the KGC’s master secret $s$. While this is successfully implemented in Xiong’s partial private key generation module, it is not used correctly in their signature generation module since $A_i$ is no longer subsequently used at all. In fact, once the user $V_i$ receives $pp{k}_i,A_i$ from the KGC and performs the verification (to ensure that this is indeed a KGC-verified pair), the user can promptly discard $A_i$ since it does not come up again in any future modules. This renders the authentication property unsatisfactory since a malicious user can receive ppki,Ai from the KGC and then replace $pp{k}_i$ with $pp{k}_i^{*}$ in all subsequent calculations without being detected. The simple fix to that is to incorporate $A_i$ in the verification equation.

Moreover, the pseudo-identities are generated in the vehicle, assuming that the TPD is ideal and cannot be tampered with, which is an impractical assumption. This is apparent in the scheme since at no point is the identity of the user $V_i$ verified by any entity, which makes it possible for a malicious user, Oscar, to replace his $RI{D}_O$ with a fictitious value $RI{D}_O^{*}$ and accordingly compute $PI{D}_O^{*}$ and still pass verification.

The fact that a malicious user, Oscar, can replace their real identity and partial private key with fictitious values renders the scheme incapable of satisfying the requirements of authentication and non-repudiation. This intuitively opens the scheme to bogus and repudiation attacks since any user can broadcast fake information under fake identities without considering the legal consequences of their actions. The attacks are shown in Figure 2.

Finally, we point out a minor mistake in the batch verification module of the original scheme: $pk=v.P$ must become $p{k}^{*}=v.P_{pub}$ for the batch verification equation $\beta ={\beta }^{*}$ to work out. In their scheme, $\beta =H_4\left(T_{1}pk\left|\right|\dots \left|\right|T_{n}pk\right)$ and ${\beta }^{*}=H_4$, so to pass verification, we must ensure that $T_i.pk=v.{\phi }_i$. Since ${\phi }_i={\mathrm{h}}_{\mathrm{i}}{\mathrm{F}}_{\mathrm{i}}+{\mathrm{U}}_{\mathrm{i}}=T_i.P_{pub,}$. Therefore, $v.{\phi }_i=v.T_i.P_{pub}=T_i.p{k}^{*}$.

4.3. Our Improved Scheme

In our proposed scheme, we suggest the following improvements and modifications to avert the threats above:

(1)

Identity Authentication using Chameleon Hashing

We added an identity authentication module based on chameleon hashing to prevent an attacker from using a fake identity. The idea is to allow the KGC to ascertain that the TRM authenticates the pseudo-identity for generating a partial private key. The chameleon hashing procedure is carried out as follows.

During the setup phase, the trapdoor $x$ is first randomly chosen by the TRM, in addition to two random points $A,B$ on the elliptic curve. Then, a point $C$ is calculated as $C=A+x.B$. The trapdoor $x$ and the point $C$ are shared securely between the $TRM$ and the $KGC$. The $TRM$ assigns an elliptic curve point $D_i$ to each member with identity $I{D}_{1,i}$ by solving the equation $D_i=C-x.I{D}_{1,i}$. To prove to the KGC that they have obtained a legitimate identity from the TRM, the member submits $D_i$ and $I{D}_{1,i}$ to the KGC, which checks the equation $D_i+x: IDi\stackrel{?}{=}C$ before generating a partial private key for the user.

This guarantees that the partial private key is adopted with a legitimate pseudo-identity. It also gives the TRM a chance to review each member’s status before authenticating their identity, so revoked members are immediately excluded without being given the secret parameter Di, which they need to generate partial private keys.

(2)

Adjusting the individual verification equation to prevent partial private key switching

As stated earlier, the significance of the partial private key generation module is that it creates a key pair $(ppk, A_i)$ where $pp{k}_i=\left({\alpha }_i+s.h_{2_i}\right) mod q$ and $A_i={\alpha }_{i}P$. The idea is that any user cannot generate a partial private key that satisfies the equation since the KGC’s master secret $s$ links the two parameters. In Xiong’s scheme, $A_i$ is not included in the individual verification equation, which allows any member to replace $pp{k}_i$ with any other value without being detected during verification. In our proposed scheme, $A_i$ is included in the verification equation, which ensures that the ppk used in signing is an authentic KGC-granted key. This also implicitly ensures that the pseudo-identity used to sign the message is genuine, thanks to the chameleon hashing authentication module introduced above.

(3)

Small exponent test in batch verification

We adopted the batch verification equation and introduced the small exponent test to ensure resilience against CLAS Type III attacks, which involve inserting forged signatures into a batch of valid signatures without detection. Section 4 elaborates on this and is where we conduct a formal security analysis of our proposed scheme. We provide a summary of our improved scheme in Figure 3.

5. Security Analysis

This section conducts a security analysis for our improved scheme. We introduce formal definitions and algorithm instantiations of CLAS systems, followed by CLAS’s security models and games. Then, we proceeded to obtain our formal security proof.

5.1. Definition of CLAS

Definition 1.

A CLAS comprises the following eight polynomial time algorithms, found in

Table 3. CLAS scheme algorithms.

Algorithm	Inputs	Outputs	By	Notations
Setup	$1^{\lambda }$	$s,\alpha , ppa$	$TA$	$1^{\lambda }:$$\mathrm{Security} \mathrm{Parameter}$ $s: \mathrm{KGC} \sec \mathrm{ret} \mathrm{key}$ $\alpha : \mathrm{TRM} \sec \mathrm{ret} \mathrm{key}$ $ppa: \mathrm{System} \mathrm{Parameters}$ $C,x: \mathrm{Chameleon} \mathrm{Hash} \mathrm{values}$ $RI{D}_i: \mathrm{The} \mathrm{real} \mathrm{identity} \mathrm{of} \mathrm{vehicle} V_i$ $pp{k}_i: \mathrm{Partial} \mathrm{Sec}\mathrm{ret} \mathrm{Key}$ $A_i: \mathrm{Partial} \mathrm{Public} \mathrm{Key}$ $x_i: \mathrm{User} \mathrm{Sec}\mathrm{ret} \mathrm{Key}$ $up{k}_i: \mathrm{User} \mathrm{Public} \mathrm{Key}$ $t_i: \mathrm{Timestamp}$ $M_i: \mathrm{Message}$ $d: \mathrm{Decision}$ ${\delta }_i,U_i:$ Signature
PIDGen	$ppa,RI{D}_i$	$PI{D}_i$	$V_i$
PIDAuth	$ppa,PI{D}_i,C,x$	$D_i$	$TRM$
PKGen	$ppa, s, PI{D}_i$	$A_i,pp{k}_i$	$KGC$
UKGen	$ppa$	$x_i,up{k}_i$	$V_i$
Sign	$ppa,I{D}_i,pp{k}_i,x_i,M_i$	${\delta }_i,U_i$	$V_i$
Verify	$ppa,I{D}_i,up{k}_i,m_i,A_i,{\delta }_i,U_i$	$d\in \left[\mathrm{0,1}\right]$	$V_j$
Batch Verify	${ppa,\left(I{D}_i,up{k}_i,m_i,A_i,{\delta }_i,U_i\right)}_{i=1\to n}$	$d\in [\mathrm{0,1}$]	$V_j$

.

5.2. Security Models of CLAS

To define security models of CLAS, we consider three types of adversary attacks according to their different abilities.

Type I attacks: The adversary has the target user’s secret value $x_i$ and can replace the user’s public key $up{k}_i$ with its choice. However, it does not know the KGC’s secret key $s$ and the user’s partial secret key ${ppk}_i$.

Type II attacks: The adversary owns the KGC’s secret key $s$ and can generate the user’s partial secret key $pp. However$, it does not know the user’s secret value $x_i$.

Type III attacks: The adversary knows all signers’ secret keys $x_i,pp{k}_i$. The adversary cannot provide any invalid signatures ${\sigma }_i$ that can be used for computing a valid aggregate signature $\sigma$.

The security of a CLAS scheme is captured by the following three games between a challenger $\mathcal{C}$ and adversaries ${\mathcal{A}}_1, {\mathcal{A}}_2, {\mathcal{A}}_3.$

The associated queries are outlined in

Table 4. CLAS scheme queries.

Query	Definition
Partial Key	$\mathrm{Given} \mathrm{a} \mathrm{user}\text{’}\mathrm{s} \mathrm{identity} I{D}_i$$, \mathcal{C}$$\mathrm{executes} \mathrm{PKGen} \mathrm{to} \mathrm{obtain} \mathrm{the} \mathrm{partial} \mathrm{key} pp{k}_i,A_i$$\mathrm{and} \mathrm{sends} \mathrm{it} \mathrm{to} \mathcal{A}.$
User Key	$\mathrm{Given} PI{D}_i$$, \mathcal{C}$$\mathrm{invokes} \mathrm{UKGen} \mathrm{to} \mathrm{obtain} \mathrm{user} \mathrm{key} x_i,up{k}_i$$\mathrm{and} \mathrm{sends} \mathrm{it} \mathrm{to} \mathcal{A}$.$\mathrm{Note} \mathrm{that} \mathcal{C}$$\mathrm{will} \mathrm{return} \perp$$\mathrm{to} \mathcal{A}$$\mathrm{if} I{D}_i$ has already appeared in the Public Key Replace query.
Public Key Replace	$\mathrm{Upon} \mathrm{receiving} \mathcal{A}$$\text{’}\mathrm{s} \mathrm{query} \mathrm{on} PI{D}_i$$, \mathcal{C}$$\mathrm{replaces} (up{k}_i,A_i)$$\mathrm{with} (up{k}_i^{\prime },A_i^{\prime })$$\mathrm{and} \mathrm{returns} (up{k^{\prime }}_i,A_i^{\prime })$$\mathrm{to} \mathcal{A}$.
Sign	$\mathrm{Upon} \mathrm{receiving} \mathcal{A}$$\text{’}\mathrm{s} \mathrm{query} \mathrm{on} \left(PI{D}_i,m_i\right)$$, \mathcal{C}$$\mathrm{executes} \mathrm{Sign} \mathrm{to} \mathrm{generate} \mathrm{a} \mathrm{signature} {\delta }_i,U_i$$\mathrm{and} \mathrm{returns} \mathrm{it} \mathrm{to} \mathcal{A}$.
Key Corrupt	$\mathrm{Upon} \mathrm{receiving} \mathrm{this} \mathrm{Query} \mathrm{on} PI{D}_i$$, \mathcal{C}$$\mathrm{executes} \mathrm{PKGen} \mathrm{and} \mathrm{UKGen} \mathrm{to} \mathrm{generate} \mathrm{the} \sec \mathrm{ret} \mathrm{key} (pp{k}_i,x_i)$$\mathrm{and} \mathrm{returns} \mathrm{it} \mathrm{to} {\mathcal{A}}_{3.}$
Aggregate Verify	$\mathrm{Upon} \mathrm{receiving} \mathrm{this} \mathrm{query} \mathrm{of} \delta$$\mathrm{on} {\left(PI{D}_i,A_i,up{k}_i,m_i,U_i\right)}_{i:1\to n}$$, \mathcal{C}$$\mathrm{executes} \mathrm{AggVerify} \mathrm{to} \mathrm{obtain} \mathrm{a} \mathrm{verification} \mathrm{decision} d\in \left[\mathrm{0,1}\right]$$\mathrm{and} \mathrm{returns} \mathrm{it} \mathrm{to} {\mathcal{A}}_3$

.

The security games are outlined in

Table 5. CLAS security games.

Phase	Game 1	Game 2	Game 3
$\mathrm{Adversary} \left(\mathcal{A}\right)$	${\mathcal{A}}_1$	${\mathcal{A}}_2$	${\mathcal{A}}_3$
Setup Phase	${\mathcal{A}}_1$$\mathrm{receives} ppa$	${\mathcal{A}}_2$$\mathrm{receives} s,ppa$	${\mathcal{A}}_3$$\mathrm{receives} ppa$
Query Phase	Partial Key, User Key, Public Key Replace, Sign	Partial Key, User Key, Sign	Key Corrupt, Aggregate Verify
Forgery	${\mathcal{A}}_1$$\mathrm{outputs} \mathrm{its} \mathrm{forgery} {\delta }_i^{*},U_i^{*}$$\mathrm{for} m_i^{*}$$\mathrm{under} (PI{D}_i^{*},A_i^{*},up{k}_i^{*})$.	${\mathcal{A}}_2$$\mathrm{outputs} \mathrm{its} \mathrm{forgery} {\delta }_i^{*},U_i^{*}\mathrm{f}\mathrm{o}\mathrm{r}{m}_i^{*}\mathrm{u}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{r}$ $(PI{D}_i^{*},A_i^{*},up{k}_i^{*}).$	${\mathcal{A}}_3$$\mathrm{outputs} \mathrm{a} \mathrm{forgery} {\delta }^{*}$$\mathrm{on} {\left(PI{D}_i^{*},U_i^{*},A_i,up{k}_i^{*},m_i^{*}\right)}_{i=1\to n}$.
$\mathcal{A}$ wins the game if	$\left(1\right) \mathrm{The} \mathrm{signature} {\delta }_i^{*},U_i^{*}$$\mathrm{is} \mathrm{valid} \mathrm{on} m_i^{*}$$\mathrm{under} PI{D}_i^{*},A_i^{*}$ $\mathrm{}\left(2\right) PI{D}_i^{*}$$\mathrm{and} (PI{D}_i^{*},m_i^{*})$ have not been submitted to the Partial Key and Sign query, respectively.	$\left(1\right) \mathrm{The} \mathrm{signature} {\delta }_i^{*},U_i^{*}$$\mathrm{is} \mathrm{valid} \mathrm{on} m_i^{*}$$\mathrm{under} PI{D}_i^{*},A_i^{*}$. $\left(2\right) PI{D}_i^{*}$$\mathrm{and} (PI{D}_i^{*},m_i^{*})$ have not been submitted to the User Key and Sign query, respectively.	$\left(1\right) \mathrm{All} \sin \mathrm{gle} \mathrm{signatures} \mathrm{are} \mathrm{compressed} \mathrm{into} \mathrm{the} \mathrm{valid} {\delta }^{*}$. (2) At least one single signature cannot pass through the verification equation.

.

Definition 2.

A CLAS scheme is existentially unforgeable under adaptive chosen message attacks (EUF-CMA) if the probability of any probabilistic polynomial time (PPT) adversary winning any of the above three games is negligible.

5.3. Security Proof

Theorem 1.

Our CLAS scheme is EUF-CMA secure against any Type I adversary if ECDLP is hard in the random oracle model (ROM).

Proof.

Let ${\mathcal{A}}_1$ be a Type I adversary who can break our underlying CLS scheme. We now construct another adversary $\mathcal{B}$ that can solve the ECDLP as the following:

Setup Phase:

$\mathcal{B}:$ Inputs security parameter $1^{\lambda }$ and generates $\left(G,q,P,P_{pub},T_{pub},H_{1\to 3 }\left(.\right)\right)$. It sets $I{D}^{*}$ as the challenged identity and maintains lists $L_{2\to 5}$ to store values queried by ${\mathcal{A}}_1$ as outlined in

Table 6. Query–response protocols between ${\mathcal{A}}_1$ and $\mathcal{B}:$.

Notation	$$\mathbf{Query} \mathbf{by} {\mathcal{A}}_1$$	$$\mathcal{B}$$ Checks	Exists	Does Not Exist
$Z_2=(PI{D}_i,A_i)$	$H_2:$ Input: $Z_2$	$(Z_2,h_{2,i})\in L_2$	Returns $h_{2,i}$ to ${\mathcal{A}}_1$	Selects $h_{2,i}\in Z_q^{*}$ Adds $\left(Z_2,h_{2,i}\right)$ to$L_2$ Returns $h_{2,i}$ to ${\mathcal{A}}_1$
$Z_3=(M_i,PI{D}_i,t_i,up{k}_i)$	$H_3:$ Input $Z_3$	$(Z_3,h_{3,i})\in L_3$	Returns $h_{3,i}$ to ${\mathcal{A}}_1$	Selects $h_{3,i}\in Z_q^{*}$ Adds $\left(Z_3,h_{3,i}\right)$ to$L_3$ Returns $h_{3,i}$ to ${\mathcal{A}}_1$
$Z_4=(PI{D}_i,A_i,{ppk}_i)$	$PartialKey$ $Query:$ Input: $PI{D}_i$	$\left(PI{D}_i\ne PI{D}^{*}\right)$ $Z_4\in L_4$	Returns $Z_4$ to ${\mathcal{A}}_1$	Selects ${ppk}_i,h_{2,i}\in Z_q^{*}$ Sets $A_i={ppk}_{i}P-h_{2,i}{P}_{Pub}$ Sets $h_{2,i}=H_2(A_i,I{D}_{i,2})$ Adds $\left(I{D}_i,A_i,h_{2,i}\right)$ to$L_2$ Adds $Z_4$ to $L_4$ Outputs $Z_4$
$Z_5^{\prime }=(I{D}_i,x_i,{upk}_i,-,-)$	$UserKey$  $Query:$ Input: $PI{D}_i$	$\left(PI{D}_i\ne PI{D}^{*}\right)$ ${Z^{\prime }}_5\in L_5$	Returns $Z_5^{\prime }$ to ${\mathcal{A}}_1$	Selects $x_i\in Z_q^{*}$ Computes $up{k}_i=x_{i}P$ Adds $Z_5^{\prime }$ to$L_5$ Outputs $Z_5^{\prime }$
	$PubKey$  $Query:$ Input: $PI{D}_i$	Operates Partial key Query and User key Query. Returns $\left(up{k}_i,A_i\right)$ to ${\mathcal{A}}_1$
$Z_5=\left(I{D}_i,x_i,{upk}_i,\perp ,{upk}_i^{\prime }\right)$	$PubKey$  $ReplaceQuery:$ Input: $PI{D}_i$	Finds $Z_5^{\prime }$ in $L_5$ Replaces with $Z_5$
	$SignQuery:$ Input: $PI{D}_i,m_i$	$Checks:\left(PI{D}_i\ne PI{D}^{*}\right)$ Traverses $L_{2\to 5}$ to get $h_{2,i},h_{3,i},A_i,{upk}_i$ respectively. Selects ${\delta }_i\in Z_q^{*}$ Computes $U_i=h_{4,i}^{-1}({\delta }_{i}P-A_i-h_{3,i}up{k}_i-h_{2,i}{P}_{Pub})$ Sends ${\sigma }_i=\left({\delta }_i,U_i\right)$ to ${\mathcal{A}}_1$

□

Forgery Phase: ${\mathcal{A}}_1$ finally outputs a forgery ${\sigma }_i^{\mathrm{*}}=\left({\delta }_i^{\mathrm{*}},U_i^{\mathrm{*}}\right)$ on $m_i^{\mathrm{*}}$ under $I{D}^{\mathrm{*}}$. If $PI{D}_i=PI{D}_i^{\mathrm{*}}$, $\mathcal{B}$ aborts and admits failure; otherwise, ${\sigma }_i^{\mathrm{*}}$ is valid and we have ${\delta }_i^{\mathrm{*}}P=A_i+h_{3,i}^{\mathrm{*}}{upk}_i^{\mathrm{*}}+h_{2,i}^{\mathrm{*}}{P}_{Pub}+U_i^{\mathrm{*}}$.

By adopting the forking lemma [19], if $\mathcal{B}$ selects a different $hash$ and repeats the above process, ${\mathcal{A}}_1$ can output another forgery ${\sigma }_{i^{*}}^{\prime }=\left({\delta }_{i^{*}}^{\prime },U_i^{*}\right)$ on $m_i^{*}$.

Then, we have ${\delta }_i^{\mathrm{*}\prime }P=A_i+h_{3,i}^{\mathrm{*}}{upk}_i^{\mathrm{*}}+h_{2,i}^{\mathrm{*}\prime }{P}_{Pub}+U_i^{\mathrm{*}}$. Therefore, $\mathcal{B}$ can obtain a solution of ECDLP by computing $s=\left({\delta }_i^{\mathrm{*}}-{\delta }_i^{\mathrm{*}\prime }\right){\left(h_{2,i}^{\mathrm{*}}-h_{2,i}^{\mathrm{*}\prime }\right)}^{-1}$.

Proof.

$$\begin{array}{}{\delta }_i^{*}P-{\delta }_i^{{*}^{\prime }}P=h_{2,i}^{*}{P}_{Pub}-h_{2,i}^{{*}^{\prime }}{P}_{Pub}\text{→}P({\delta }_i^{*}-{\delta }_i^{{*}^{\prime }})=P_{Pub}(h_{2,i}^{*}-h_{2,i}^{{*}^{\prime }})\\ \text{→} \left({\delta }_i^{*}-{\delta }_i^{{*}^{\prime }}\right){\left(h_{2,i}^{*}-h_{2,i}^{{*}^{\prime }}\right)}^{-1}=P_{Pub}{P}^{-1}=s\end{array}$$

□

Theorem 2.

The CLAS scheme is EUF-CMA secure against any Type II adversary if ECDLP is hard in ROM.

The exact proof, as Theorem 1, is omitted for space considerations.

Theorem 3.

The CLAS scheme is secure against any Type III adversary.

Proof.

Type III security of a CLAS scheme states that the scheme must resist information injection attacks in the aggregate verification phase. For instance, assume two malicious vehicles generate two valid signatures ${\delta }_1$ and ${\delta }_2$ and inject $c$ and $-c$ in them, respectively. The batch verifier cannot detect this since $c$ is countered by $-c$ in the aggregation phase. In our scheme, we utilize the simplified small exponent test in the aggregation process. By doing so, the randomness of $x_i$ necessitates that the verifier can detect any modification to the single signature δi. The rigorous proof can be found in [20]. Hence, Type III security is achieved. □

Theorem 4.

The CLAS scheme achieves CPP.

Proof.

The anonymity of the vehicle is ensured by the pseudo-identity $I{D}_i$. Note that $PI{D}_i=(I{D}_{i,,1},I{D}_{i,2},V{T}_i)$, where $I{D}_{i,1}=k_{i}P$, $I{D}_{i,2}=RI{D}_i⨁H_1(k_i.T_{Pub}|\left|V{T}_i\right)$ and $V{T}_i$ is the validity period. To extract the real identity $RI{D}_i$ from $I{D}_{i,2,}$ the adversary needs to compute $H_1(k_i.T_{Pub}|\left|V{T}_i\right)$. Since $k_i$ is only known to $V_i$ (the owner of $RI{D}_i)$ and securely transmitted to the TRA during the PID generation phase, it is impossible for an adversary to extract $RI{D}_i$ from $I{D}_{i,1},I{D}_{i,2}$. Since $k_i$ is a random value that changes for every pseudonym, our scheme guarantees unlinkability since no two pseudo-identities can be traced back to the same real identity. Hence, this scheme achieves conditional privacy preservation since only the TRA can extract the real identity from a pseudo-identity, and no adversary can link two different pseudonyms to the same signer. □

This concludes our security analysis. In the following section, we conduct a performance analysis of our scheme and compare it to other ECC-based CLAS schemes.

6. Performance Analysis of Comparable CLAS Schemes

To ensure consistency, we evaluated all the schemes using the operation execution times reported in [2]. The authors employed the MIRACL cryptography library to measure the execution times on an Intel i5-6600 processor running at 3.3 GHz, with 8 GB of memory and a Windows operating system. The execution times they obtained are presented in

Table 7. Execution time of basic operations.

Symbol	Notation	Time (ms)
$T_{m_{ecc}}$	Scalar multiplication in ECC	0.3158
$T_{a_{ecc}}$	Addition in ECC	0.0026
$T_h$	Hash operation	0.0008

.

Next, we evaluated the seven schemes in

Table 8. Performance comparison of ECC-based CLAS schemes.

Scheme		${\mathit{T}}_{{\mathit{m}}_{\mathit{e}\mathit{c}\mathit{c}}}$	${\mathit{T}}_{{\mathit{a}}_{\mathit{e}\mathit{c}\mathit{c}}}$	${\mathit{T}}_{\mathit{h}}$	Total
Zhao 2020 [12]	$S:$	$1$		$2^{*}$	$0.3174$
	$BV:$	$2n+1^{*}$	$3n^{*}$	$2n^{*}$	$0.641n+0.3518$
Zhou 2023 [2]	$S:$	$1$		$2$	$0.3174$
	$BV:$	$3n+1^{*}$	$3n-3^{*}$	$3n$	$0.9576n+0.308$
Zhu 2023 [13]	$S:$	$1$		$2$	$0.3174$
	$BV:$	$3n+2^{*}$	$3n^{*}$	$3n$	$0.9576n+0.6316$
Li 2020 [14]	$S:$	$1$		$3$	$0.3182$
	$BV:$	$2n+3^{*}$	$2n^{*}$	$3n$	$0.6392n+0.9474$
Li 2023 [21]	$S:$	$4^{*}$	$1^{*}$	$1^{*}$	$1.4106$
	$BV:$	$2n+2$	$3n$	$3n$	$0.6418n+0.6316$
Thumbur 2020 [15]	$S:$	$1$		$2$	$0.3174$
	$BV:$	$2n+1$	$3n-1$	$2n^{*}$	$0.641n+0.3132$
Xiong 2022 [6]	$S:$	$1^{*}$		$1^{*}$	$0.3166$
	$BV:$	$3n+1^{*}$	$2n-1^{*}$	$2$	$0.9542n+0.3148$
Our scheme	$S:$	$1$		$1$	$0.3166$
	$BV:$	$3n+2$	$3n$	$n$	$0.956n+0.6316$

n: number of operations. Time is measured in milliseconds.

to obtain the number of operations required to execute each scheme. The starred values indicate that we derived these through our analysis of the schemes, as they differed from the values stated in the authors’ performance analysis or were not provided by the authors at all. Our study focused on individual signatures and batch verifications, as particular (sequential) verification times are unlikely to occur in practical scenarios, except in scenarios with very low vehicle density, where the verification speed is insignificant due to the relatively few verifications that must be executed.

Batch verification times are compared in Figure 4.

Our scheme is comparable to Xiong’s in terms of performance but offers much more robust security guarantees. We note that our scheme’s performance is inferior to the schemes proposed by Zhao, Li, and Thumbur due to our use of the small exponent test. While this test incurs a higher computational cost, it is a necessary measure to prevent Type III attacks.

7. Conclusions and Future Work

This paper presents a cryptanalysis of Xiong’s recently published CLAS scheme [6]. We identify the causes of vulnerabilities in the original scheme and propose countermeasures. Based on this, we construct a new certificateless aggregate signature scheme, CHAM-CLAS, which addresses the identified issues. Finally, we conduct security and performance analyses of our proposed scheme.

While our scheme offers stronger security guarantees, it suffers from relative inefficiency due to the added cost of the small exponent test. This test must preserve batch verification capability against Type III attacks. One future research direction involves investigating approaches to achieve the same security level as our scheme but at a lower computational cost and simulating network performance. Additionally, we would like to explore the contextualization of our CLAS scheme within a blockchain-based VANET security system in future work.