A Lightweight Quantum-Secure Authentication and Key Agreement Protocol for Vehicular Ad-Hoc Networks

1  Introduction

The rapid advancement of the Internet of Things has accelerated the integration of physical and digital systems, enabling intelligent transportation systems as a cornerstone of smart cities [1]. Within this ecosystem, vehicular ad hoc networks (VANETs) facilitate real-time communication among vehicles and roadside units (RSUs) to improve traffic safety, driving efficiency, and autonomous decision making. Vehicles equipped with onboard units (OBUs) continuously exchange safety-critical messages through vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) communications to support cooperative awareness and proactive hazard avoidance. Despite these advantages, vehicular communications operate over an open and highly dynamic environment, making them vulnerable to numerous security and privacy threats as adversaries can launch message forgery, impersonation, replay, tracking, or denial-of-service (DoS) attacks that compromise communication reliability and road safety [2]. Consequently, authentication and key agreement (AKA) protocols are indispensable for ensuring that only legitimate entities participate in communication while preserving message authenticity, integrity, confidentiality, and user privacy.

Existing solutions predominantly rely on public-key cryptography (PKC), particularly elliptic curve cryptography (ECC), which provides strong classical security but incurs considerable computational overhead due to heavy operations, such as frequent signature generation, verification, and certificate management [3]. Blockchain-based authentication frameworks further improve trust decentralization and auditability [4,5] often using PKC primitives, but their consensus protocols and transaction validation introduce additional communication and computational latency that limits their applicability in real-time vehicular environments. Moreover, classical PKC schemes are fundamentally vulnerable to quantum attacks enabled by Shor’s algorithm [6], motivating the transition toward post-quantum authentication mechanisms. Recent lightweight authentication schemes reduce computational complexity by replacing expensive public-key operations with symmetric cryptographic primitives, offering reduced computational complexity with quantum resistance [7]. However, many of these approaches often depend on centralized architectures or static shared secrets, creating scalability bottlenecks and increasing the impact of long-term key compromise. In particular, reliance on a central authority during real-time authentication introduces single points of failure and increases susceptibility to black-hole and DoS attacks. In light of these limitations, achieving a balanced design that simultaneously ensures security, privacy, scalability, and efficiency, while remaining resilient to emerging quantum threats remains an open research problem.

To overcome the above research challenge, this paper proposes the first decentralized and lightweight post-quantum hash-based AKA protocol that combines Blom’s key pre-distribution scheme [8] with the Module-Lattice-Based Key Encapsulation Mechanism (ML-KEM) standardized by the National Institute of Standards and Technology (NIST) [9], for VANETs and Internet of Vehicles (IoV) environments. Unlike conventional approaches, the proposed protocol eliminates real-time dependence on a central authority during authentication, thereby reducing latency and removing critical bottlenecks. The Blom’s scheme enables efficient pairwise key establishment through lightweight polynomial evaluations during routine authentication, whereas ML-KEM provides quantum-resistant protection for credential distribution and infrastructure-assisted key establishment. In addition, temporary pseudonymous identities protect user privacy through anonymity and unlinkability. To safeguard cryptographic credentials against physical compromise, vehicles and RSUs are assumed to be equipped with tamper-proof devices (TPDs).

The key contributions of this work are summarized below:

1.   A lightweight and decentralized post-quantum AKA protocol supporting secure mutual authentication across V2V, vehicle-to-RSU (V2R), and RSU-to-RSU (R2R) communications without requiring real-time involvement of the trusted authority (TA), which is also adaptable to various networking applications.

2.   A hybrid key establishment framework that combines Blom’s symmetric scheme with ML-KEM to achieve efficient pairwise authentication while providing quantum-resistant credential distribution.

3.   A forward secure and privacy-preserving authentication mechanism based on temporary pseudonym identities and session-specific keys to limit long-term credential exposure, while supporting a periodic security parameter refresh strategy and conditional traceability.

4.   Formal security verifications, complemented by hardware computation benchmarking and NS-3 simulations demonstrating strong resistance against classical and quantum attacks while achieving low computation and communication costs with high scalability over existing schemes.

The remainder of this paper is organized as follows. Section 2 introduces the background and system models. Section 3 reviews the related literature. Section 4 presents the proposed protocol phases. Section 5 provides formal and informal security analyses. Section 6 evaluates cryptographic performance, while Section 7 presents the NS-3 simulation results before concluding the paper in Section 8.

2  Preliminaries

We describe the preliminaries for system and threat models, security goals, and computation tools.

2.1 System Model

The proposed system architecture considers a typical VANET environment primarily with the TA, RSU, and vehicles that interact to enable vehicular safety communications.

TA: A centralized authority that manages the network with sufficient capacities to register all vehicles and RSUs in a given location (e.g., country or state) and provide security updates to them. TA is the secured trust anchor assumed to be trustworthy and it uses secure channels to interact with vehicles and RSUs. Furthermore, TA has the ability to trace any misbehaving entity and revoke its credentials when needed.

RSU: Fixed infrastructure devices positioned along the roadway, RSUs monitor traffic conditions and disseminate safety information to vehicles within their communication ranges. RSUs can also communicate among themselves to exchange long-range traffic data with each other, and act as intermediaries to facilitate communication between the TA and vehicles, particularly during security updates and misbehavior reports.

Vehicle: Mobile entities equipped with OBUs, vehicles communicate with one another and with RSUs. Vehicles process exchanged safety information to maintain a cooperative driving environment.

2.2 Threat Model

Vehicles and RSUs communicate through insecure wireless channels and they remain vulnerable to various attacks. Therefore, an adversary (𝒜) has the following capabilities:

•   𝒜 can observe vehicular communications to track vehicle behaviors or identities (privacy violation).

•   𝒜 can intercept transmitted messages, drop, or modify them to mislead receivers (Man-in-the-Middle).

•   𝒜 can generate fake messages and broadcast them to attempt unauthorized authentications (forgery).

•   𝒜 can retransmit previously captured valid messages to attempt unauthorized authentications (replay).

•   𝒜 can attempt to extract stored secret keys from a legitimate entity to use them (physical compromise).

•   𝒜 can launch resource-exhaustion attacks by flooding with excessive messages (denial-of-service–DoS).

Assumption 1: TA is the trust anchor and its database is protected against attack capabilities of 𝒜. TPDs are secured and 𝒜 cannot extract any useful information from a TPD in a realistic time. All entities use a synchronized clock to enable message freshness and other timely operations.

2.3 Security Objectives

To counter the aforementioned threats, the proposed protocol aims to achieve the following objectives:

•   Mutual Authentication: Entities verify each other’s identity before establishing communication sessions.

•   Message Integrity: A receiver verifies whether the content of a transmitted message has been modified or not, and rejects manipulated messages. Therefore, 𝒜 should not be able to forge any valid message.

•   Privacy Preservation: Vehicles and RSUs communicate without exposing their real identities. Therefore, 𝒜 should not be able to derive a real identity or link different messages to the same sender to trace it.

•   Session Key Agreement: Vehicles and RSUs establish unique session keys per communication instance to ensure confidentiality and forward secrecy. Thus, 𝒜 should not be able to derive a valid session key.

•   Resistance to Common Attacks: The protocol should resist common attacks such as replay attacks, storage compromise attacks, and brute force attacks under both classical and quantum computers.

2.4 Security Primer for Computation Tools

The proposed protocol employs Blom’s scheme, ML-KEM together with an authenticated encryption with associated data (AEAD) mechanism, and lightweight cryptographic operations based on the secure hash algorithm (SHA-256) complemented by the bitwise exclusive-OR (XOR). These primitives collectively provide efficient mutual authentication, secure credential distribution, and low-latency session key establishment.

Definition 1(ML-KEM): Let (EK,DK)=MLKEM.KGen() be a valid ML-KEM key pair. For any encapsulated secret K as (C,K)=MLKEM.Encaps(EK), the decapsulation algorithm correctly recovers the same shared secret, K=MLKEM.Decaps(DK,C), except with negligible probability. This correctness follows the deterministic design of ML-KEM. Moreover, the ML-KEM security relies on reduction to the hardness of the Module Learning With Errors (M-LWE) problem, proving that no probabilistic polynomial-time adversary can distinguish the encapsulated shared secret from a uniformly random value, even under adaptive chosen-ciphertext attacks. Consequently, the ML-KEM is assumed fully quantum secure under the hardness of M-LWE.

Definition 2(AEAD): Given a symmetric key K, the AEAD encryption algorithm protects the confidentiality and integrity of a plaintext M by producing a ciphertext C=AEAD.EncK(M). The corresponding decryption algorithm can efficiently recover the original message as M=AEAD.DecK(C) or output ⊥ if the ciphertext has been modified. In the proposed protocol, AEAD and ML-KEM are complementary such that ML-KEM establishes temporary symmetric keys that are immediately used by AEAD to protect secret credentials and domain keys.

Definition 3(Blom): Let f(x,y) be a chosen bivariate symmetric polynomial of degree d over a finite field Fp with prime order p, such that f(x,y)=f(y,x) for all x,y∈Fp. By definition, f(x,y) can be expressed as:

f(x,y)=∑i=0d∑j=0daijxiyj(modp)(1)

where aij∈Fp is the coefficient matrix satisfying aij=aji for all 0≤i,j≤d. Therefore, f(x,y) allows any two distinct nodes to independently compute an identical algebraic factor using their local polynomial slices.

Let two legitimate nodes with identifiers IDi and IDj possess the polynomial shares gi(y)=f(IDi,y) and gj(y)=f(IDj,y), respectively given by TA. To verify each other’s identifier, the first node computes Kij=gi(IDj)=f(IDi,IDj), while the second computes Kji=gj(IDi)=f(IDj,IDi). Since f(x,y) is symmetric, any two legitimate nodes can independently derive the same algebraic factor such that f(IDi,IDj)=f(IDj,IDi) and Kij=Kji if and only if gi(y) and gj(y) were provided by the same TA. As long as the coefficient matrix aij remains secret, the Blom’s scheme inherits the information-theoretic security: any adversary possessing at most d polynomial shares (g1(y),g2(y),⋯,gd(y)) gains no information about uncompromised pairwise keys. Moreover, the Blom’s construction does not rely on algebraic problems vulnerable to Shor’s algorithm, making the derived shared factor secure against currently known quantum attacks with sufficiently large prime order p.

Definition 4(SHA-256): The hash function, denoted ℋ(.), performs one-way mathematical operations on any arbitrary input to produce a fixed-length output that is hard to reverse or collide. Given two inputs x1 and x2:

One way: Given a hash value y1=ℋ(x1), reversing this function to recover x1 such that x1=ℋ−1(y1) is computationally hard. Likewise, for Y=ℋ(x1∥x2), knowing both Y and x1 does not reveal the unknown x2 (∥ denotes concatenation). Consequently, finding a preimage of an n-bit hash requires classically testing 2n operations, while the best known quantum attacks (e.g., Grover’s algorithm) reduce this complexity to about 2n/2. Therefore, SHA-256 offers a classical and quantum resistance of 2256 and 2128 operations, respectively.

Collision resistance: with distinct inputs x1≠x2, it is computationally hard to find ℋ(x1)=ℋ(x2). Due to the Birthday search across an n-bit output space, an adversary can evaluate approximately 2n/2 random inputs to achieve a 50% probability of finding a hash collision. Thus SHA-256 bounds a 2128 collision complexity.

Avalanche effect: A small change in the input produces a statistically independent output. Hence, knowing ℋ(x1) does not provide meaningful information about ℋ(x2) even when x1 and x2 differ by only one bit.

Definition 5(XOR): Let x1 and x2 be two binary strings of equal length k. The bitwise XOR operation produces an output string denoted y=x1⊕x2, where the i-th bit y[i]=x1[i]⊕x2[i], satisfying self-invertibility and commutativity such that x1=y⊕x2 and x2=y⊕x1. While XOR itself does not provide cryptographic security, combining it with secure hash outputs and secret keys prevents unauthorized recovery of protected data.

3  Related Works

In this section, we review related AKA protocols for vehicular networks, classifying them into three categories: PKC-based, blockchain-assisted, and lightweight symmetric-key-based approaches.

PKC-based approaches have been widely adopted due to their ability to provide public verifiability. In particular, ECC is predominantly used through digital signatures with or without certificate-based authentication. For instance, AKA protocols in [10–12] rely on ECC signatures and bilinear pairings, often supporting signature aggregation to enable batch authentication and group session key establishment. Although these techniques reduce authentication delay in dense vehicular environments, they introduce practical limitations where a single invalid signature may invalidate the entire aggregated verification process or, if verification succeeds, allow a malicious participant to obtain the group session key. Alternatively, Hoque et al. [13], Raghav et al. [14], and Yang et al. [15] have proposed individual AKA protocols that combine ECC with hash functions to reduce authentication latency while supporting V2V, V2R/V2I, and/or R2R communications. Jayashree and Santhosh Kumar [16] further combine ECC with bilinear pairing, providing enhanced security at the expense of significantly higher computational overhead. Despite the classical security guarantees, PKC-based schemes incur substantial computational overhead due to repeated heavy public-key operations and their mathematical problems remain fundamentally vulnerable to quantum attacks based on Shor’s algorithm, limiting their long-term applicability.

Blockchain-assisted authentication has emerged as an alternative for decentralized trust management. Dwivedi et al. [17] and Lin and Jhuang [18] integrate blockchain with ECC to realize batch and certificateless authentication, respectively. Noh et al. [19] propose a non-interactive blockchain-based authentication framework for one-time entity verification, whereas Zhao et al. [20] combine zero-knowledge proofs, smart contracts, and Merkle trees for cross-domain authentication. Zhao et al. [21] further employ homomorphic encryption and ECC for anonymous authentication with dynamic pseudonym updates. More recently, Yan et al. [22] adopt lattice-based cryptography to achieve quantum resistance within a blockchain architecture. Lu et al. [23] integrate blockchain with Merkle Patricia Trees to support privacy-preserving authentication and certificate revocation. Although blockchain improves trust decentralization and auditability, these schemes suffer from transaction latency, consensus overhead, scalability limitations, and dependence on reliable connectivity, making them less suitable for latency-sensitive vehicular communications.

Lightweight symmetric-key AKA protocols replace expensive public-key operations to reduce computational complexity. Wazid et al. [24] proposed a cluster-based framework that reduces repeated authentication but introduces communication overhead and potential single points of failure through cluster-head management. Aman et al. [25] and Kim et al. [26] improve authentication efficiency using RSU-assisted and two-factor authentication mechanisms, respectively, whereas decentralized protocols have also been proposed to improve scalability [27–30], with several incorporating biometric authentication to strengthen user verification. Although these approaches significantly reduce computational overhead and naturally resist Shor’s algorithm, many continue to depend on centralized infrastructures, static pre-shared symmetric keys, limiting scalability, forward secrecy, and resilience against long-term key compromise.

Overall, existing AKA protocols exhibit complementary strengths and limitations. PKC-based schemes provide strong classical security but incur high computational overhead and remain vulnerable to quantum attacks, while blockchain-assisted approaches offer decentralized trust at the cost of significant communication and processing latency. Lightweight hash-based protocols improve authentication efficiency but often depend on centralized infrastructures or static shared secrets, limiting scalability and long-term security. Table 1 summarizes the security and privacy comparison of representative schemes.

Although most existing methods support V2R/V2I authentication, secure session key establishment, message integrity, impersonation resistance, and formal security verification, many do not natively support V2V and R2R communications. While anonymity is generally preserved, the schemes in [14,22] expose real identities to communicating peers, and several methods fail to ensure unlinkability by transmitting a static identifier across multiple authentication sessions. Moreover, the protocols in [22,26] continuously rely on an intermediate authority to achieve V2R authentication, while [21] depends on RSU availability to achieve V2R authentication before enabling V2V authentications. These central entity-dependent architectures create a risk of single points of failure. Although replay protection is commonly achieved using timestamps, methods like [21,22] do not bind timestamps to message authentication, allowing replay with refreshed timestamps. In addition, the schemes in [14,22,26] provide no explicit protection against storage compromise. Finally, ECC-based methods like [13,14,21] remain vulnerable to quantum attacks. In sum, the proposed protocol offers a more robust and balanced security profile by combining hash functions, Blom’s scheme, and ML-KEM to provide decentralized, low-latency, and quantum-secure authentication with dynamic privacy preservation, periodic credential updates, and support for V2V, V2R, and R2R communications.

4  Proposed AKA Design

Fig. 1 illustrates the vehicular network architecture, in which the proposed AKA protocol enables post-quantum and low-latency mutual authentication and session key establishment for V2V, V2R, and R2R communications using ML-KEM for secure key encapsulation and Blom’s key pre-distribution scheme for efficient pairwise key derivation. The proposed AKA protocol consists of six phases. First, the TA initializes the system by generating the global cryptographic parameters. Second, it registers vehicles and RSUs by assigning pseudonymous identities, generating their Blom polynomial shares, and securely distributing these credentials using ML-KEM. Third, neighboring entities perform mutual authentication and establish a pairwise session key using their polynomial shares and fresh timestamps, which is then used to protect subsequent unicast safety messages, while temporary pseudonyms preserve user privacy. Fourth, each RSU securely distributes its domain key to vehicles within its coverage area through ML-KEM encapsulation, enabling secure RSU-domain broadcast communications. Fifth, the protocol periodically renews security credentials to mitigate long-term key compromise. Finally, it preserves network integrity by identifying and revoking malicious nodes. The notations used throughout the protocol are summarized in Table 2.

Figure 1: Network model for vehicular authentication.

4.1 System Initialization Phase

Before network deployment, the TA initializes the system parameters. It first selects a unique identity IDTA and randomly generates two secrets (X,Y) to derive the master secret key KTA=ℋ(IDTA∥X) and a global authorization key Kauthg=ℋ(IDTA∥Y). The TA then selects a large prime p defining the finite field Fp and generates a symmetric coefficient matrix A=(aij)d×d to construct the Blom’s symmetric polynomial f(x,y) as defined in Eq. (1). It also specifies the message freshness threshold ΔT and security update interval Tup. The TA securely stores KTA, A, and f(x,y), while distributing Kauthg to registered vehicles and RSUs for lightweight message filtering before full authentication. Finally, the TA selects the ML-KEM and AEAD schemes (e.g., the Advanced Encryption Standard in Galois/Counter Mode (AES-GCM)).

4.2 Registration Phase

The TA registers all vehicles and RSUs in offline or via secure channels following the same procedure but with their respective credentials as shown in Fig. 2. The registration steps are detailed as follows:

Figure 2: Vehicle and RSU registration.

Step 1: Each vehicle (Vi) has a unique identity (IDVi) and is expected to authenticate its user (e.g., using the method in [31]) to prevent illegal use. Before joining the network, Vi generates a registration ML-KEM encapsulation/decapsulation key pair as (EKVireg,DKVireg)=MLKEM.KGen(), and requests registration by sending its real identity and its public key to the TA as M1={IDVi,EKVi} (same for RSUs).

Step 2: TA receives the registration request M1 and verifies the vehicle’s real identity (IDVi). It then generates a registration timestamp (RTVi) and derives a pseudonym identity PIDVi=ℋ(RTVi∥IDVi∥KTA) for the vehicle to enable anonymous communications while preserving conditional traceability by TA. Next, the TA evaluates the symmetric bivariate polynomial at x=PIDVi to generate the vehicle’s identity-bound polynomial share gVi(y) as defined in Eq. (2). To securely distribute the registration credentials, the TA uses the vehicle’s encapsulation key EKVireg to generate a shared secret Ks protected into a ciphertext CK via the ML-KEM algorithm, which is then used to secure the registration tuple {PIDVi,gVi(y),Kauthg} to produce a ciphertext CVi via a quantum-secure symmetric encryption algorithm as in Eq. (3). Subsequently, TA derives a verification code Reg1=ℋ(CK∥CVi∥IDTA∥p), stores (IDVi,RTVi,PIDVi,EKVireg) in its database and finally returns the registration response M2={CK,CVi,IDTA,ΔT,p,Reg1}.

gVi(y)=f(PIDVi,y)=∑j=0d(∑i=0daij(PIDVi)i)yj(modp)(2)

(CK,Ks)=MLKEM.Encaps(EKVireg);CVi=AEAD.EncKs(PIDVi∥gVi(y)∥Kauthg)(3)

Step 3: Upon receiving M2, the vehicle verifies the verification code Reg1 and recovers the shared secret through ML-KEM decapsulation to decrypts CVi as in Eq. (4). The vehicle then stores sensitive registration data {DKVireg,PIDVi,gVi(y),Kauthg} in its TPD and terminates the registration process.

Ks=MLKEM.Decaps(DKVireg,CK);{PIDVi,gVi(y),Kauthg}=AEAD.DecKs(CVi)(4)

4.3 Mutual Authentication and Session Key Establishment

After completing the registration phase, any two neighboring vehicles Vi and Vj can mutually authenticate each other and establish a shared session key without requiring further assistance from the TA. As illustrated in Fig. 3a, each vehicle stores its pseudonymous identity PID, the TA identity IDTA, the global authorization key Kauthg, the authentication validity interval ΔT, and the update period Tup in its TPD. The authentication protocol combines temporary identities, timestamp verification, and Blom’s key pre-distribution to provide anonymous mutual authentication while establishing a common session key.

Figure 3: Mutual authentication and key agreement phase: (a) vehicle-to-vehicle and (b) RSU-to-RSU.

Step 1: When vehicle Vi intends to communicate with vehicle Vj, it first generates a fresh timestamp T1 and computes a temporary identity TIDVi=PIDVi⊕ℋ(Kauthg∥T1), which conceals its real pseudonym from external observers. It then uses the global authorization key to compute the authentication token Auth1=ℋ(TIDVi∥T1∥Kauthg), and transmits the authentication request to vehicle Vj as M1={TIDVi,T1,Auth1}.

Step 2: Upon receiving M1, vehicle Vj records the current timestamp T2 and verifies whether the received message satisfies the freshness condition |T2−T1|≤ΔT. If valid, it recomputes the authentication token Auth2=ℋ(TIDVi∥T1∥Kauthg), and compares it with the received value. Successful verification indicates the sender is authorized allowing Vj to proceed and recover the pseudonym PIDVi=TIDVi⊕ℋ(Kauthg∥T1). Using its stored Blom polynomial share, Vj computes the pairwise secret Kji=gVj(PIDVi)(modp), which is further used to derive the temporary authentication key Kauthji=ℋ(Kji∥Kauthg∥T2). Vehicle Vj then generates its own temporary identity TIDVj=PIDVj⊕ℋ(Kauthg∥T2), computes the authentication token Auth3=ℋ(TIDVj∥T2∥Kauthji), and replies with message M2={TIDVj,T2,Auth3}.

Step 3: After receiving M2, vehicle Vi first verifies the timestamp freshness by checking whether |T3−T2|≤ΔT. It subsequently reconstructs the responder’s pseudonym and also computes the pairwise secret Kij=gVi(PIDVj)(modp). According to the properties of Blom’s key pre-distribution scheme, both vehicles independently obtain the same pairwise secret, such that Kij=Kji. Therefore, vehicle Vi derives the temporary authentication key Kauthij=ℋ(Kij∥Kauthg∥T2), which is unique and only known to the two vehicles (Vi and Vj) preventing session impersonation by other insider entities. The vehicle then computes Auth4=ℋ(TIDVj∥T2∥Kauthij) and verifies the received authentication token by comparing Auth4 with Auth3. If vehicle Vj is successfully authenticated, vehicle Vi computes the confirmation token as Auth5=ℋ(Kij∥T3) and sends the message M3={T3,Auth5} to vehicle Vj.

Step 4: Finally, vehicle Vj verifies the received confirmation by checking whether Auth5=ℋ(Kji∥T3). Since Kij=Kji, successful verification confirms that both vehicles are effectively registered by the same TA and the exchanged pseudonym identities are legitimate leading to the same pairwise secret. Therefore, they have mutually authenticated each other and both entities can independently derive the same session key as SKij=ℋ(PIDVi∥PIDVj∥Kij∥T3), which is securely stored in their respective TPDs and subsequently used to protect their V2V communications in the active session.

Note that this mutual authentication and session key establishment procedure is applicable for all direct vehicular communication modes, including the V2V (Fig. 3a), R2R (Fig. 3b), and V2R (Fig. 4a) interactions. Each session key is valid only for one active session due to the inclusion of a fresh session timestamp, which prevents key reuse across different communication sessions and mitigates session key capture attacks.

Figure 4: Vehicle-to-RSU authentication phase: (a) session key agreement and (b) domain key sharing.

4.4 V2R Mutual Authentication and Domain Key Distribution

When a vehicle enters the communication range of an RSU, they execute the mutual V2R authentication process where the RSU uses the ML-KEM encapsulation to securely distribute its domain broadcast key to the vehicle as illustrated in Fig. 4b. Consequently, authenticated vehicles can securely receive broadcast traffic messages within the RSU coverage area. In addition, vehicles and RSUs can achieve unicast communications when necessary by executing a mutual authentication and session key establishment as shown in Fig. 4a.

Step 0: Each RSU Rk independently generates its domain key KRkD=ℋ(PIDRk∥IDTA∥ZRk∥TRk) using a fresh random secret ZRk and current timestamp TRk, which can be periodically updated for security.

Step 1: To initiate the authentication process, vehicle Vi generates the current timestamp T1 and a fresh ML-KEM encapsulation/decapsulation key pair (EKVi,DKVi). It then computes the temporary identity TIDVi=PIDVi⊕ℋ(Kauthg∥T1) and the authentication token Auth1=ℋ(TIDVi∥EKVi∥T1∥Kauthg). The authentication request M1={TIDVi,EKVi,T1,Auth1} is subsequently transmitted to the RSU Rk.

Step 2: After receiving M1, the RSU verifies the freshness of the received timestamp and authenticates the vehicle Vi by recomputing the received authentication token. Upon successful verification, the RSU Rk reconstructs the vehicle pseudonym, computes the Blom pairwise secret Kki=gRk(PIDVi)(modp), and derives the temporary authentication key Kauthki=ℋ(Kki∥Kauthg∥T2). The RSU Rk then generates its temporary identity TIDRk=PIDRk⊕ℋ(Kauthg∥T2), uses the vehicle’s ML-KEM encapsulation key to generate a shared secret as (CK,Ks)=MLKEM.Encaps(EKVi) and encrypts its current domain broadcast key CRk=AEAD.EncKs(KRkD). Finally, the RSU computes the authentication token Auth2=ℋ(TIDRk∥T2∥CK∥CRk∥Kauthki) and sends the response M2={TIDRk,T2,CK,CRk,Auth2} to the requesting vehicle.

Step 3: Upon receiving the response M2, vehicle Vi verifies the freshness of the received timestamp and reconstructs the RSU pseudonym. It then computes the Blom pairwise secret Kik=gVi(PIDRk)(modp). Due to the symmetry property of Blom’s polynomial, both entities obtain the same secret Kik=Kki. The vehicle derives Kauthki=ℋ(Kik∥Kauthg∥T2) and verifies Auth2 to confirm the authenticity of the RSU Rk. It then decapsulates the received ML-KEM ciphertext using its private decapsulation key Ks=MLKEM.Decaps(DKVi,CK) to recover the RSU domain broadcast key KRkD=AEAD.DecKs(CRk). The vehicle securely stores the recovered domain key KRkD in its TPD and optionally sends an acknowledgement confirming successful key reception. After completion of this phase, Vi becomes an authenticated member of the RSU domain and can securely receive subsequent broadcast traffic messages protected by KRkD.

4.5 Security Update Phase

To limit the long-term exposure of cryptographic material, the proposed scheme incorporates a periodic security update mechanism. This phase primarily refreshes the global authorization key Kauthg, which is shared among registered vehicles and RSUs for lightweight authorization check before further verification.

Re-initialization: The TA achieves an offline re-initialization before any update period following the steps in Section 4.1. It refreshes the global authorization key Kauthg,new for each update interval and reconstructs the symmetric bivariate polynomial fnew(x,y) to renew entities’ Blom polynomial shares gVinew(y) only when required. The updated parameters replace the previous ones after the current Tup expires.

Distribution: TA announces the security update period Tup to allow credential refresh in advance. Each entity can send an update request Ureq={TIDVi,T1} before Tup ends, where TIDVi=PIDVi⊕ℋ(Kauthg∥T1). Upon receiving the request, the TA verifies the entity’s legitimacy, protects the refreshed credentials using ML-KEM and AEAD with the entity’s registered encapsulation key EKVireg, and returns the response Uresp={CK,CVi,Auth1}, where (CK,Ks)=MLKEM.Encaps(EKVireg), CVi=AEAD.EncKs(gVinew(y)∥Kauthg,new), and Auth1=ℋ(CK∥CVi). Since EKVireg belongs to a legitimate entity, only the intended receiver possessing the corresponding decapsulation key DKVireg can recover the protected credentials, preventing unauthorized entities from requesting updates on behalf of legitimate participants. During the transition period, entities continue using their current credentials until Tup expires. After the update deadline, all legitimate vehicles and RSUs switch to the refreshed parameters for subsequent authentication operations. This coordinated update strategy prevents credential inconsistencies and ensures continuous network availability.

4.6 Revocation Phase

The proposed protocol provides conditional traceability, allowing the TA to identify and revoke malicious or compromised entities while preserving the anonymity of legitimate users.

Misbehavior Reporting: When a vehicle or RSU detects invalid behavior or suspicious activity, it forwards the corresponding authentication messages as evidence to the TA for verification.

Identity Tracing and Revocation: Upon receiving a valid misbehavior report, the TA reconstructs the reported pseudonym as PID=TID⊕ℋ(Kauthg∥T) using the corresponding timestamp and authorization key. TA then maps the identified pseudonym to the associated real identity from its registration database. If the reported entity is confirmed as malicious, its pseudonym PID is added to the revocation list (RL).

Revocation Dissemination: To enable a dynamic revocation enforcement, the TA immediately publishes the RL after every update to be accessible by RSUs. Each RSU frequently broadcasts the latest RL to vehicles within its communication range, enabling them to verify whether the received pseudonym belongs to the current revocation list before initiating mutual authentication. Since vehicles and RSUs cannot forge valid pseudonyms, any entity associated with a revoked pseudonym is immediately rejected by legitimate peers even if its previous credentials remain valid within the current update interval Tup. Therefore, revoked entities are excluded from new session key establishments and subsequent security updates.

5  Security Analysis

In this section, we analyze the security guarantees of the proposed AKA protocol through an informal analysis and a formal correctness analysis and a formal security verification.

5.1 Informal Security Analysis

5.1.1 Mutual Authentication and Message Integrity

The proposed protocol provides mutual authentication between communicating entities through a challenge-response mechanism based on hash verification and Blom’s pairwise secret computation. During authentication, each entity validates the received authentication token using the derived pairwise secret and the global authorization key. Since only legitimate nodes possess valid polynomial shares and authentication parameters, an adversary cannot generate a valid authentication response. Consequently, both communicating parties are assured of each other’s legitimacy before establishing a session key. Moreover, the computed hash-based authentication token assures that any modification of an intercepted message changes the hash input and causes the receiver’s verification to fail. Therefore, forged or modified messages are detected and discarded to preserve message integrity against man-in-the-middle attacks.

5.1.2 Privacy (Anonymity and Unlinkability)

In the proposed protocol, the real identity ID of a communicating entity is never transmitted directly during authentication. Instead, the TA assigns each legitimate vehicle and RSU a unique pseudonymous identity (PID) during registration. Since recovering ID from PID requires knowledge of the TA master key KTA and the one-way property of the hash function, an adversary cannot infer the real identity from intercepted messages. Moreover, every authentication session generates a temporary identity TID=PID⊕ℋ(Kauthg∥T), using the global authorization key and a fresh timestamp, which produces different authentication messages in different sessions to ensure that intercepted messages cannot be correlated by an external attacker to identify or track a particular vehicle over time. Therefore, the proposed protocol preserves both anonymity and unlinkability of legitimate vehicles and RSUs.

5.1.3 Replay Attacks Resistance

Every authentication message includes a fresh timestamp that is verified upon reception using the condition |Tr−Ts|≤ΔT, where Ts and Tr denote the sending and receiving timestamps, respectively. Any replayed message outside the valid time interval is immediately rejected. Even if an adversary modifies the timestamp, the associated authentication token becomes invalid because it is computed over the original timestamp. Consequently, the proposed protocol effectively prevents replay attacks.

5.1.4 Impersonation (Even from Insider) Attack Resistance

An adversary attempting to impersonate a legitimate vehicle or RSU must generate valid authentication messages and establish a valid session key. External adversaries cannot accomplish this because they lack the required authorization key Kauthg and legitimate Blom’s polynomial shares gi(y). However, compromise of Kauthg alone may allow an external adversary to bypass the initial authorization verification and initiate the pairwise authentication process. Nevertheless, possessing Kauthg is insufficient even for insiders to fully impersonate another legitimate entity or establish a valid session key, which requires the entity-specific gi(y) to compute the Blom pairwise secret Kij=gi(PIDj)(modp). Therefore, the proposed scheme resists complete impersonation attacks under the assumption that legitimate entities’ TA-issued polynomial shares remain protected. Thus, a compromise of Kauthg is considered a partial credential exposure that affects preliminary message filtering only but does not reveal pairwise authentication secrets or session keys.

5.1.5 Resistance to Node Capture and Storage Intrusion

The proposed protocol protects sensitive authentication parameters, including pseudonymous identities, polynomial shares, authorization keys, and session keys, by storing them in trusted TPDs. These tamper-resistant hardware modules significantly reduce the risk of unauthorized extraction of cryptographic material through physical attacks. Furthermore, the protocol inherits the threshold security property of Blom’s key pre-distribution scheme. Specifically, compromising up to d legitimate vehicles or RSUs reveals only their individual polynomial shares and provides no information about the secret polynomial or uncompromised pairwise secrets. An adversary must compromise at least d+1 distinct nodes to reconstruct the secret polynomial. Therefore, the combined use of secure hardware and Blom’s threshold property provides strong resistance against storage intrusion and node capture attacks.

5.1.6 Resistance to Session Key Capture Attacks

In the proposed protocol, the session key is never transmitted over the communication channel. Instead, both communicating entities independently derive the identical fresh session key from their polynomial shares, pseudonym identities, and fresh timestamps after successful mutual authentication. Consequently, each session key is unique and independent of previously established session keys, ensuring that even if an adversary compromises a session key, it cannot derive past or future session keys without compromising the Blom’s polynomial share. Moreover, a fresh ML-KEM key pair is generated whenever it is used during credential or domain key distribution, preventing the reuse of cryptographic material across sessions and further limiting the impact of key compromise. Therefore, the protocol is secure against session key attacks.

5.1.7 Brute Force Attack Resistance

The proposed protocol employs SHA-256 and ML-KEM to protect its authentication parameters, requiring approximately 2256 operations under classical computation to recover secret values through exhaustive search. Even under Grover’s quantum search algorithm, the effective complexity remains 2128, providing a sufficient post-quantum security margin. Hence, the protocol is resistant to brute-force attacks.

5.1.8 Resistance to Flooding Attacks

The protocol minimizes the computational impact of flooding attacks through early message validation. Received messages first undergo timestamp verification to immediately discard stale messages before any expensive cryptographic operation is performed, while authentication relies primarily on lightweight hash computations and Blom polynomial evaluations. Furthermore, the decentralized authentication process eliminates continuous dependence on the TA, reducing the risk of bottlenecks and distributed DoS attacks.

5.2 Formal Security Verification Using BAN Logic

To prove the structural correctness and cryptographic soundness of the proposed mutual authentication and key agreement mechanism, a formal deductive analysis is conducted using Burrows-Abadi-Needham (BAN) Logic [32]. This analysis verifies that the participating nodes can securely establish a common session key (SKij) while ensuring mutual authentication, freshness, and protection against entity impersonation.

Notation 1: Let P and Q be two communicating entities; X and Y be information; and K be a security key. The standard syntactic operators of BAN logic are defined as follows:

•   P⟷KQ: K is a secret key shared between P and Q.

•   {X}K: The information X is encrypted using the key K.

•   P⇒X: P controls or has jurisdiction over the information X.

•   #(X): The information X is fresh.

•   P∣∼X: P once said the information X.

•   Q⊲X: Q sees the information X.

•   Q∣≡X: Q believes the information X is true.

•   P⇌YQ: Y is a shared secret known only to principals P and Q.

•   ⟨X⟩Y: Formula X is combined with the secret parameter Y.

•   (X,Y): X and Y form a compound message.

The foundational inference rules of BAN logic applied in this proof include:

R1: The message meaning rule:  If P∣≡(P⟷KQ) and P⊲{X}K then P∣≡Q∣∼X

R2: The nonce-verification rule:  If P∣≡#(X) and P∣≡Q∣∼X then P∣≡Q∣≡X

R3: The jurisdiction rule:  If P∣≡(Q⇒X) and P∣≡Q∣≡X then P∣≡X

R4: The freshness rule:  If P∣≡#(X) then P∣≡#(X,Y)

R5: The belief rule:  If P∣≡X and P∣≡Y then P∣≡(X,Y)

Assumption 2: The verification proof is evaluated under the following initial beliefs and baseline assumptions regarding parameter distribution and clock synchronization:

A1 (the sender can verify timestamp freshness): Vi∣≡#(T1),Vi∣≡#(T2),Vi∣≡#(T3)

A2 (the receiver can verify timestamp freshness): Vj∣≡#(T1),Vj∣≡#(T2),Vj∣≡#(T3)

A3 (each entity received the global authorization key): Vi∣≡Vi⟷KauthgVj and Vj∣≡Vi⟷KauthgVj

A4 (each entity received its secret polynomial slice): Vi∣≡Vi⇌gVi(y)TA and Vj∣≡Vj⇌gVj(y)TA

By the Blom’s mathematical structure in Definition 3, evaluating local secret polynomial slices creates a unique, mutually verifiable pairwise secret Kij=Kji. This yields the following critical jurisdiction assumptions:

A5 (Pairwise Secret Ownership Authority): Vi∣≡(Vj⇒Vi⟷KijVj) and Vj∣≡(Vi⇒Vi⟷KjiVj)

Assumption 3: The actual over-the-air protocol packets (M1,M2,M3) are converted into their idealized logical forms to capture the exact cryptographic assertions transmitted between vehicle Vi and vehicle Vj:

Idealized M1 (Vi→Vj): {PIDVi,T1}Kauthg

Idealized M2 (Vj→Vi): {PIDVj,T2,Vi⟷KjiVj}Kauthjiwhere Kauthji=ℋ(Kji∥Kauthg∥T2)

Idealized M3 (Vi→Vj): {T3}Kij

Theorem 1: To confirm that the session key configuration is fully secure and mutually authenticated, the deductive analysis must satisfy the following four fundamental security goals:

G1: Vj∣≡Vi∣≡(PIDVi): The receiver Vj authenticates the origin of the request message M1.

G2: Vi∣≡Vj∣≡(PIDVj): The sender Vi authenticates the origin of the response message M2.

G3: Vi∣≡Vi⟷SKijVj: Vi confirms that it successfully establishes a session key SKij with Vj.

G4: Vj∣≡Vi⟷SKijVj: Vj confirms that it successfully establishes a session key SKij with Vi.

Proof of Theorem 1: The step-by-step application of BAN logic inference rules proceeds as follows:

Analysis of Message M1: Vehicle Vj intercepts the initiation request message M1 from the open channel:

S1: Vj◃{PIDVi,T1}Kauthg

By applying the Message Meaning Rule to S1 combined with the global initialization in A3, we derive:

S2: Vj∣≡Vi⟷KauthgVj, Vj◃{PIDVi,T1}KauthgVj∣≡Vi∣∼(PIDVi,T1)

Because vehicle Vj independently confirms the clock freshness of timestamp T1 via A2, the Freshness Rule implies that the entire composite statement is fresh: if Vj∣≡#(T1) then Vj∣≡#(PIDVi,T1). Applying the Nonce Verification Rule to S2 combined with the message freshness yields:

S3: Vj∣≡#(PIDVi,T1), Vj∣≡Vi∣∼(PIDVi,T1)Vj∣≡Vi∣≡(PIDVi,T1)

Based on the Belief Rule, we can decompose the belief components from S3 to directly achieves Goal 1:

S4: Vj∣≡Vi∣≡(PIDVi)(Goal 1 Attained)

Analysis of Message M2: Once Vi is successfully authenticated, Vj extracts PIDVi and computes the temporary key Kauthji to build message M2. Vehicle Vi intercepts M2:

S5: Vi◃{PIDVj,T2,Vi⟷KjiVj}Kauthji

Since Kauthji is directly derived using the symmetric pairwise factor Kij=Kji known only to Vi and Vj, Vi believes that Kauthji is a valid channel key. Applying the Message Meaning Rule with S5 gives:

S6: Vi∣≡Vi⟷KauthjiVj, Vi◃{PIDVj,T2,Vi⟷KjiVj}KauthjiVi∣≡Vj∣∼(PIDVj,T2,Vi⟷KjiVj)

By referencing the timestamp freshness of T2 via A1, applying the Nonce Verification Rule to S6 yields:

S7: Vi∣≡#(PIDVj,T2,Vi⟷KjiVj), Vi∣≡Vj∣∼(PIDVj,T2,Vi⟷KjiVj)Vi∣≡Vj∣≡(PIDVj,T2,Vi⟷KjiVj)

Breaking down the conjunction vector in S7 based on the Belief Rule achieves Goal 2:

S8: Vi∣≡Vj∣≡(PIDVj)(Goal 2 Attained)

Concurrently, parsing the remaining element from S7 yields:

S9: Vi∣≡Vj∣≡(Vi⟷KjiVj)

Applying the Jurisdiction Rule to S9 using the initial network authority setting in A5 establishes:

S10: Vi∣≡(Vj⇒Vi⟷KijVj), Vi∣≡Vj∣≡(Vi⟷KjiVj)Vi∣≡Vi⟷KijVj

Analysis of Message M3: Vehicle Vi returns the confirmation message, which Vj captures from the channel:

S11: Vj◃{T3}Kij

Because Vj has already proven the origin belief of PIDVi in S4, it relies on the polynomial properties in A4 that govern the pairwise key derivation from local parameters, leading to the key boundary belief:

S12: Vj∣≡Vi⟷KjiVj

By applying the Message Meaning Rule to S11 and S12 yields: S13:Vj∣≡Vi⟷KjiVj, Vj◃{T3}KijVj∣≡Vi∣∼T3.

By integrating the freshness check T3 via A2, the Nonce Verification Rule verifies Vi’s active state:

S14: Vj∣≡#(T3), Vj∣≡Vi∣∼T3Vj∣≡Vi∣≡T3

Session Key Establishment: The final session key is computed as SKij=ℋ(PIDVi∥PIDVj∥Kij∥T3). Since vehicle Vi has verified the identity and active presence of Vj via S8, and holds a secure belief regarding the symmetric key component Kij from S10, it can securely assert belief over the derived session key:

S15: Vi∣≡Vi⟷SKijVj(Goal 3 Attained)

Similarly, because vehicle Vj has verified the identity and active presence of Vi via S4, and holds a secure belief regarding the symmetric key component Kji from S12, it asserts identical belief over the derived session key structure, satisfying Goal 4:

S16: Vj∣≡Vi⟷SKijVj(Goal 4 Attained)

Conclusion: The BAN logic verification confirms mutual authentication, message freshness, and session key establishment under the assumed trust conditions. The use of timestamps ensures protection against replay attacks, while the derivation of identity-bound temporary keys prevents adversarial impersonation and message forgery, validating the correctness of the protocol in satisfying its intended security properties. □

5.3 Formal Security Verification via AVISPA

To rigorously validate the security strength of the proposed AKA protocol against active malicious exploitation, a formal simulation is conducted using the industry-standard Automated Validation of Internet Protocols and Applications (AVISPA) tool [33]. Implementing a Dolev-Yao intruder model, AVISPA evaluates cryptographic transactions over an insecure channel where an adversary can intercept, modify, delete, or inject arbitrary messages. The architecture is formally modeled using the High-Level Protocol Specification Language (HLPSL), defining explicit state transitions, parameter spaces, and foundational network goals.

5.3.1 HLPSL Role Specifications

The proposed protocol is modeled in HLPSL using two primary roles: the initiator (Vi) and the responder (Vj/Rk). The initiator generates a fresh timestamp, constructs a temporary identity and authentication token, transmits the authentication request, verifies the responder’s reply, computes the pairwise secret using its Blom polynomial share, and finally derives the session key after successful mutual authentication. Similarly, the responder validates the received authentication request, verifies its freshness, computes the corresponding pairwise secret from its polynomial share, returns the authentication response, and independently derives the same session key upon validating the final confirmation message. Both roles are integrated into a session module and executed within an environment role that instantiates multiple concurrent sessions under the Dolev–Yao adversarial model. The intruder is assumed to possess public and compromised system parameters but has no access to entity-specific secrets, including the TA secrets and valid polynomial shares. Finally, the HLPSL specification defines the authentication and session key secrecy goals determined by polynomial shares, mutual identity and fresh timestamps verifications, and agreement on the established session key. The HLPSL specifications are provided in Fig. 5 to enable reproducibility.

Figure 5: HLPSL role specifications.

5.3.2 AVISPA Simulation Results and Analysis

The HLPSL specification is formally verified using the AVISPA framework with its two principal verification backends: the On-the-Fly Model Checker (OFMC) and Constraint-Logic-Based Attack Searcher (CL-AtSe), which systematically explore the protocol state space to identify potential attacks, including replay, man-in-the-middle, and impersonation attacks. As shown in Fig. 6a,b, both analyses return a SAFE verdict, indicating that no attack trace violates the specified secrecy and authentication goals. Furthermore, an insider attack was evaluated by assuming that the adversary compromises the global authorization key Kauthg. Under this assumption, AVISPA correctly reports an UNSAFE verdict, as illustrated in Fig. 6c. The generated attack trace shows that possession of Kauthg only allows the adversary to bypass the first authorization check, but subsequent pairwise verifications fail. These results confirm that the protocol preserves session-key secrecy and mutual authentication as long as the Blom polynomial shares remain unavailable to the attacker, while effectively limiting the impact of partial compromised global credentials.

Figure 6: AVISPA results: (a) normal under OFMC, (b) normal under CL-AtSe, and (c) compromise under OFMC.

6  Performance Evaluation

In this section, we discuss the computational and communication performances of the proposed protocol phases, while comparing it against existing representative AKA schemes (referenced as [13,14,21,22,26,29]).

6.1 Computational Overhead

To evaluate the computational overhead, cryptographic benchmarks were conducted on an Apple M2 processor (10 cores, 16 GB RAM) running Python 3.13, as summarized in Table 3. ECC, AES, SHA-256, and the pseudo-random function (PRF) were implemented using the cryptography (OpenSSL) library, while ML-KEM was evaluated using the pqcrypto library [34]. Additional benchmarks, including bitwise XOR, ECC modular arithmetic, Blom polynomial evaluation, Paillier homomorphic encryption, Arbiter Physical Unclonable Function (PUF) delay-path simulation, and Fuzzy Extractor operations, were implemented using native Python arithmetic. Execution times were measured with Python’s high-resolution time.perf_counter_ns() timer, and the mean, standard deviation, minimum, and maximum values performed on a baseline 32 bytes input data over 1000 executions are reported to ensure reproducible measurements.

Table 4 gives the estimated computational complexity, communication overhead, and authentication latency of the proposed protocol for each operational phase. During registration, the TA computes the entity’s credentials and securely delivers them using ML-KEM and AEAD security mechanisms, resulting in a one-time latency of approximately 0.175 ms and a communication overhead of 2456 bytes for registering a single entity. The session key establishment phase (in V2V, V2R, and R2R operations) is the most efficient, requiring only one Blom polynomial evaluation and lightweight hash and XOR operations at each vehicle, thereby achieving a latency of approximately 0.05 ms with only 184 bytes exchanged per authentication. In contrast, the domain key sharing in V2R authentication incurs higher latency of approximately 0.205 ms and communication overhead of 2448 bytes mainly due to the ML-KEM high footprint, which achieves a quantum-secure key sharing at the expense of communication overhead. However, the domain key sharing is less frequent compared to the normal V2V, V2R, and R2R communications, which can be achieved without high network congestion impact. The periodic security update phase is similar to the registration mechanism incurring a latency of 0.161 ms but with reduced communication cost to 1224 bytes depending on the credentials needed for renewal, wich has minimal impact on routine communications. Finally, the revocation phase introduces only a small communication overhead of 72 bytes to forward a malicious message, while its computational cost mainly depends on the investigation time at the TA end. Overall, the proposed design achieves an effective balance between post-quantum security, low authentication latency, and communication efficiency by reserving ML-KEM operations for infrequent management procedures and relying primarily on Blom’s key pre-distribution and hash computations during regular authentication.

6.2 Comparative Computational Scalability

Based on the estimated computational costs in Table 5, the proposed protocol (denoted by X) is compared with each related scheme (denoted by Y) using the percentage improvement 100(Y−X)/Y. As illustrated in Fig. 7a, the proposed protocol reduces the V2V computation time by 99.95% and 99.93% compared with the methods in [13] and [21], respectively, while achieving a 99.93% reduction in R2R computation compared with [13]. For V2R authentication, the proposed protocol achieves computation-time reductions of 99.72%, 99.90%, and 99.86% compared with [13,14], and [21], respectively. However, the methods in [26,29] achieve 59.02% and 69.75% lower computation in V2R mainly because of the ML-KEM integration in the proposed protocol. The computational cost was not evaluated for the protocol in [22] because its implementation relies on custom lattice-based operation that were not measured in our benchmarking. The significant reduction in computational cost in our protocol is achieved by confining the relatively expensive ML-KEM operations to registration, security updates, and V2R domain-key sharing, while frequent authentication relies primarily on lightweight Blom polynomial evaluations and SHA-256 computations. Consequently, the proposed protocol can theoretically support approximately 20,000 V2V and 4878 V2R authentications per second, demonstrating excellent scalability for dense vehicular environments, as shown in Fig. 7b, while improving resilience against network flooding and resource-exhaustion attacks.

Figure 7: Computation cost: (a) comparative overhead and (b) comparative scalability.

6.3 Comparative Communication Scalability

The communication cost is evaluated based on the total size of the exchanged authentication messages. During mutual authentication and session key establishment (V2V, V2R, and, R2R), the protocol exchanges three messages containing temporary identities (32 bytes), timestamps (8 bytes), and authentication tokens (32 bytes), resulting in a total communication overhead of 184 bytes. In contrast, the V2R domain key sharing phase additionally carries the ML-KEM public key (1184 bytes), the ML-KEM encapsulated ciphertext (1088 bytes), and the AEAD encrypted domain key (32 bytes), increasing the communication overhead to 2448 bytes. Table 5 compares the communication costs of different protocols. The proposed protocol reduces the V2V communication overhead by 8.46% and 87.08% compared with [13] and [21], respectively as visible in Fig. 8a, while achieving a 9.80% reduction in R2R compared with [13]. However, the V2R communication overhead is higher than that of existing classical schemes because of the transmission of ML-KEM public keys and ciphertexts required to provide quantum-resistant key sharing. This additional overhead represents a deliberate trade-off for post-quantum security and occurs only during infrastructure-assisted authentication, whereas the more frequent mutual authentication and session key establishment phases remain lightweight. Furthermore, the decentralized authentication architecture eliminates the need for blockchain interactions or frequent TA involvement, reducing the number of exchanged messages and allowing most cryptographic operations to be performed locally. Consequently, despite the increased V2R message size, the proposed protocol maintains low authentication latency while providing scalable and quantum-secure authentication for dense vehicular networks as shown in Fig. 8b.

Figure 8: Communication cost: (a) comparative overhead and (b) comparative scalability.

7  Network-Scale Simulation

7.1 Simulation Environment

The proposed protocol is evaluated using the NS-3 network simulator on macOS, with NetAnim employed for network visualization. The simulation models a dynamic V2X environment consisting of four static RSUs spaced 500 m apart and N∈[2,1000] vehicles randomly distributed over a 1 km2 area, moving at speeds between 5 and 25 m/s. Vehicles and RSUs perform frequent mutual authentication and session key establishment over Dedicated Short-Range Communication (DSRC) protocol (IEEE 802.11bd [35]) with a communication range of 500 m, capturing the dynamic formation and disruption of V2V and V2R links as vehicles move through RSU coverage areas. The simulation parameters are summarized in Table 6.

7.2 Simulation Metrics

The proposed protocol is evaluated using two performance metrics: the packet delivery ratio (PDR) and the end-to-end authentication latency. The PDR, defined in Eq. (5), measures the percentage of successfully received packets (Nrx) relative to the total transmitted packets (Ntx). The end-to-end authentication latency, given in Eq. (6), denotes the elapsed time from transmitting an authentication request to the successful establishment of a session key. It comprises the cryptographic processing delay (Tproc) and the network transmission delays for the request (Ttx) and response (Trx). The processing delay incorporates the benchmarked execution times of SHA-256, XOR, Blom’s polynomial evaluation, and ML-KEM operations, which are injected into the NS-3 event scheduler to emulate realistic cryptographic processing, while the transmission delays are directly measured from the simulated wireless channel. Together, these metrics assess the protocol’s reliability and real-time performance under varying vehicular network conditions.

PDR=(Nrx/Ntx)×100(5)

L=Ttx+Tproc+Trx(6)

7.3 Simulation Results

We first simulate the network by randomly distributing vehicles within a 1000 m × 1000 m free space and observed that the PDR score can degrade even in low-density conditions when some senders are placed outside of the receiver’s communication range as illustrated in Fig. 9a,b. Therefore, we reconfigured vehicles distribution such that senders are initially placed within the receiver’s communication range as illustrated in Fig. 9c, and observed that the PDR score became stable throughout topology variations. The impact of density and speed variations on the PDR and Latency are discussed below:

Figure 9: Visualization of the vehicular network simulation in the NetAnim environment: (a) low density with out-coverage senders, (b) high density with out-coverage senders, and (c) high density with full-coverage senders.

7.3.1 Impact of Vehicle Density Variation

This scenario tests the scalability constraints on a single vehicle and a single RSU when receiving authentication requests from multiple neighboring vehicles. Therefore, we maintain the vehicle speed to 20m/s and vary the vehicle density from 2 to 1000, while initially distributing them within the maximum 500m range. Fig. 10a shows that the proposed V2V authentication consistently achieves a PDR of nearly 100% across all network densities, demonstrating reliable message delivery between neighboring vehicles even under high densities because they move at the same speed and remain in the communication range of one another throughout the simulation. In contrast, the V2R PDR gradually decreases from 100% in sparse networks to approximately 67% at 1000 vehicles. This degradation can be expected because vehicles are moving away from static RSUs and may lose connectivity beyond the allowable range. Moreover, the increasing communication contention from simultaneous connected vehicles can also create channel congestion reduce communication performance. Nevertheless, the V2R communication maintains a satisfactory delivery performance even under highly dense traffic conditions. Fig. 10b illustrates the authentication latency under different vehicle densities. As expected, the authentication delay increases with the number of vehicles because of higher channel contention, packet queuing, and processing overhead. The V2V latency rises from approximately 0.5 ms with two vehicles to about 84 ms at 1000 vehicles, while the V2R latency increases from about 1.5 to 87 ms over the same range. Although authentication latency grows with network density due to long message queues, both communication modes remain within practical limits for vehicular authentication. Furthermore, the consistently higher PDR achieved by V2V and the moderate latency increase demonstrate that the proposed protocol scales efficiently with increasing network density while preserving reliable and timely authentication.

Figure 10: Density variations: (a) packet delivery ratio and (b) average end-to-end latency.

7.3.2 Impact of Vehicle Speed Variation

Unlike Scenario 1, this scenario fixes the network topology to two vehicles and one RSU while varying the vehicle speed from 5 to 25m/s to evaluate the impact of mobility on the proposed authentication protocol. Fig. 11a shows that the V2V communication consistently achieves a PDR of nearly 100% across the entire speed variation, indicating that the proposed authentication protocol maintains reliable direct communications despite increasing vehicle mobility. Since vehicles are moving at the same speed at a time, they remain in the communication range of one another throughout the simulation duration. In contrast, the V2R PDR experiences a slight decrease from nearly 100% at 5m/s to approximately 91% at 25m/s. This reduction is primarily attributed to the lack of connectivity as RSUs are fixed while vehicles are moving and may leave the RSU communication coverage before the simulation ends. Nevertheless, the obtained PDR demonstrates that the protocol maintains high communication reliability even under high-mobility conditions. The authentication latency results in Fig. 11b further demonstrate the protocol’s robustness against vehicle mobility. As the vehicle speed increases, the authentication delay grows only slightly, with the V2V latency increasing from approximately 0.22 to 0.34ms and the V2R latency from about 1.05 to 1.6ms. The consistently lower V2V latency results from the absence of infrastructure involvement, whereas V2R authentication incurs additional communication and processing overhead at the RSU. Overall, the modest latency increase confirms that the proposed protocol maintains efficient real-time authentication performance even in highly dynamic vehicular environments.

Figure 11: Speed variations: (a) packet delivery ratio and (b) average end-to-end latency.

8  Conclusion

Vehicular networks are a fundamental component of intelligent transportation systems, enabling secure and reliable communications for future smart cities. This paper presented a lightweight post-quantum authentication and key agreement protocol that combines Blom’s key pre-distribution scheme with ML-KEM to achieve efficient and quantum-resistant authentication across V2V, V2R, and R2R communications. By confining computationally intensive ML-KEM operations to registration and infrastructure-assisted key distribution while relying on lightweight Blom polynomial evaluations and SHA-256 hashing during routine authentication, the proposed protocol effectively balances security and efficiency. Security was validated through informal analysis, BAN logic, and AVISPA verification, demonstrating resistance against impersonation, replay, node capture, session key compromise, storage intrusion, and quantum attacks while preserving anonymity, unlinkability, and conditional traceability. Performance evaluation showed substantial reductions in computational cost up to 99.95% and communication overhead (8.46%–87.08%) compared with existing schemes. Although V2R communication incurs additional overhead due to ML-KEM ciphertext transmission, this trade-off enables post-quantum secure key establishment while maintaining low authentication latency. Furthermore, NS-3 simulations confirmed that the proposed protocol provides reliable packet delivery and low end-to-end authentication latency under varying vehicle densities and mobility conditions. Overall, the proposed protocol offers a scalable, secure, and practical post-quantum authentication framework for next-generation vehicular networks and other resource-constrained cyber-physical systems. Future work will investigate broadcast basic safety message authentication protocol using distributed RSU domain keys and implementation on real vehicular hardware platforms for more realistic deployments.

Acknowledgement: The authors acknowledge the support from the PASET-Regional Scholarship and Innovation Funds through the African Center of Excellence in Internet of Things (ACEIoT), the Google Africa PhD Fellowship, and the Carnegie Corporation of New York.

Funding Statement: The APC was funded by Carnegie Corporation of New York through the DOCTAS II Mobility Grant Award-Publication Support.

Author Contributions: The authors confirm contribution to the paper as follows: Conceptualization, methodology, and resources: Lasseni Coulibaly and Damien Hanyurwimfura; investigation, software, and formal analysis, Lasseni Coulibaly; writing—original draft preparation, Lasseni Coulibaly; writing—review and editing and validation: Damien Hanyurwimfura, Evariste Twahirwa, Abubakar Diwani and Lasseni Coulibaly; supervision: Damien Hanyurwimfura, Evariste Twahirwa and Abubakar Diwani; project administration: Damien Hanyurwimfura; funding acquisition: Lasseni Coulibaly and Damien Hanyurwimfura. All authors reviewed and approved the final version of the manuscript.

Availability of Data and Materials: The data that support the findings of this study are available upon request.

Ethics Approval: Not applicable.

Conflicts of Interest: The authors declare no conflicts of interest.

References

1. Muthuramalingam S, Bharathi A, Kumar SR, Gayathri N, Sathiyaraj R, Balamurugan B. IoT based intelligent transportation system (IoT-ITS) for global perspective: a case study. In: Balas VE, Solanki VK, Kumar R, Khari M, editors. Internet of Things and Big Data Analytics for Smart Generation. Cham, Switzerland: Springer; 2018. p. 279–300. doi:10.1007/978-3-030-04203-5_13. [Google Scholar] [CrossRef]

2. Coulibaly L, Hanyurwimfura D, Twahirwa E, Diwani A. A review of cybersecurity challenges and solutions for autonomous vehicles. Int J Adv Comput Sci Appl. 2025;16(2):850–66. doi:10.14569/ijacsa.2025.0160285. [Google Scholar] [CrossRef]

3. Muhammad M, Ali Safdar G. 5G-based V2V broadcast communications: a security perspective. Array. 2021;11(6):100084. doi:10.1016/j.array.2021.100084. [Google Scholar] [CrossRef]

4. Lai J, Zhang X, Liu S, Zhong S, Moshayedi AJ. Blockchain-based VANET edge computing-assisted cross-vehicle enterprise authentication scheme. Comput Commun. 2025;231(6):108040. doi:10.1016/j.comcom.2024.108040. [Google Scholar] [CrossRef]

5. Zhang H, Zhao F. Cross-domain identity authentication scheme based on blockchain and PKI system. High Confid Comput. 2023;3(1):100096. doi:10.1016/j.hcc.2022.100096. [Google Scholar] [CrossRef]

6. Moody D, Robinson A. Cryptographic standards in the post-quantum era. IEEE Secur Privacy. 2022;20(6):66–72. doi:10.1109/msec.2022.3202589. [Google Scholar] [CrossRef]

7. Moody D, Perlner R, Regenscheid A, Robinson A, Cooper D. Transition to post-quantum cryptography standards. Gaithersburg, MD, USA: National Institute of Standards and Technology (NIST); 2024. NIST IR 8547 (IPD). doi:10.6028/NIST.IR.8547.ipd. [Google Scholar] [CrossRef]

8. Antony SNFMA, Bahari MFA. Implementation of elliptic curves in the polynomial Blom key pre-distribution scheme for wireless sensor networks and distributed ledger technology. J Sens Actuator Netw. 2023;12(1):15. doi:10.3390/jsan12010015. [Google Scholar] [CrossRef]

9. NIST.FIPS.203.Module-Lattice-Based Key-Encapsulation Mechanism Standard. Washington, DC, USA: National Institute of Standards and Technology; 2024. doi:10.6028/NIST.FIPS.203. [Google Scholar] [CrossRef]

10. Liu Z, Yao N, Bai S, Mai T. A cooperative ECC-based authentication protocol for VANETs. Sci Rep. 2025;15(1):40837. doi:10.1038/s41598-025-24663-8. [Google Scholar] [CrossRef]

11. Mei Q, Xiong H, Chen J, Yang M, Kumari S, Khan MK. Efficient certificateless aggregate signature with conditional privacy preservation in IoV. IEEE Syst J. 2021;15(1):245–56. doi:10.1109/jsyst.2020.2966526. [Google Scholar] [CrossRef]

12. Jiang H, Hua L, Wahab L. SAES: a self-checking authentication scheme with higher efficiency and security for VANET. Peer Peer Netw Appl. 2021;14(2):528–40. doi:10.1007/s12083-020-00997-0. [Google Scholar] [CrossRef]

13. Hoque A, Amin R, Ali Khan D. L-VAKMC: lightweight authentication and dynamic key agreement for VANET multi-entity communications. IEEE Trans Depend Secur Comput. 2026;23(2):4310–22. doi:10.1109/tdsc.2025.3645431. [Google Scholar] [CrossRef]

14. Raghav, Maurya C, Verma S. Certificateless federated authentication and key agreement in IoV. Comput Netw. 2026;277(4):112017. doi:10.1016/j.comnet.2026.112017. [Google Scholar] [CrossRef]

15. Yang Q, Zhu X, Wang X, Fu J, Zheng J, Liu Y. A novel authentication and key agreement scheme for internet of vehicles. Fut Gener Comput Syst. 2023;145(8):415–28. doi:10.1016/j.future.2023.03.037. [Google Scholar] [CrossRef]

16. Jayashree S, Santhosh Kumar SVN. LAPEP—lightweight authentication protocol with enhanced privacy for effective secured communication in vehicular ad-hoc network. Wirel Netw. 2024;30(1):151–78. doi:10.1007/s11276-023-03459-6. [Google Scholar] [CrossRef]

17. Dwivedi SK, Amin R, Vollala S, Das AK. Design of blockchain and ECC-based robust and efficient batch authentication protocol for vehicular ad-hoc networks. IEEE Trans Intell Transp Syst. 2024;25(1):275–88. doi:10.1109/tits.2023.3310514. [Google Scholar] [CrossRef]

18. Lin HT, Jhuang WL. Blockchain-based lightweight certificateless authenticated key agreement protocol for V2V communications in IoV. IEEE Internet Things J. 2024;11(16):27744–59. doi:10.1109/jiot.2024.3400320. [Google Scholar] [CrossRef]

19. Noh J, Kwon Y, Son J, Cho S. Blockchain-based one-time authentication for secure V2X communication against insiders and authority compromise attacks. IEEE Internet Things J. 2023;10(7):6235–48. doi:10.1109/jiot.2022.3224465. [Google Scholar] [CrossRef]

20. Zhao F, Ding H, Li C, Su Z, Liang G, Yang C. A blockchain-based efficient cross-domain authentication scheme for Internet of vehicles. Comput Mater Contin. 2024;80(1):567–85. doi:10.32604/cmc.2024.052233. [Google Scholar] [CrossRef]

21. Zhao J, Guo Y, Liao L, Wang D. A blockchain-based efficient traceability authentication scheme in VANET. Digit Commun Netw. 2025;11(5):1410–20. doi:10.1016/j.dcan.2025.04.013. [Google Scholar] [CrossRef]

22. Yan M, Bao Z, Li J, Tian H. Quantum-resistant blockchain-assisted certificateless authentication and three-party key agreement scheme for VANET. Expert Syst Appl. 2026;299(5):130163. doi:10.1016/j.eswa.2025.130163. [Google Scholar] [CrossRef]

23. Lu Z, Wang Q, Qu G, Zhang H, Liu Z. A blockchain-based privacy-preserving authentication scheme for VANETs. IEEE Trans VLSI Syst. 2019;27(12):2792–801. doi:10.1109/tvlsi.2019.2929420. [Google Scholar] [CrossRef]

24. Wazid M, Das AK, Kumar N, Odelu V, Goutham Reddy A, Park K, et al. Design of lightweight authentication and key agreement protocol for vehicular ad hoc networks. IEEE Access. 2017;5:14966–80. doi:10.1109/access.2017.2723265. [Google Scholar] [CrossRef]

25. Aman MN, Javaid U, Sikdar B. A privacy-preserving and scalable authentication protocol for the Internet of vehicles. IEEE Internet Things J. 2021;8(2):1123–39. doi:10.1109/jiot.2020.3010893. [Google Scholar] [CrossRef]

26. Kim C, Kwon D, Son S, Yu S, Park Y. An anonymous and efficient authentication scheme with conditional privacy preservation in Internet of vehicles networks. Mathematics. 2024;12(23):3756. doi:10.3390/math12233756. [Google Scholar] [CrossRef]

27. Vasudev H, Das D. An efficient authentication and secure vehicle-to-vehicle communications in an IoV. In: Proceedings of the 2019 IEEE 89th Vehicular Technology Conference (VTC2019-Spring); 2019 Apr 28–May 1; Kuala Lumpur, Malaysia. p. 1–5. doi:10.1109/vtcspring.2019.8746612. [Google Scholar] [CrossRef]

28. Nandy T, Idris MYI, Noor RM, Das AK, Li X, Ghani NA, et al. An enhanced lightweight and secured authentication protocol for vehicular ad-hoc network. Comput Commun. 2021;177:57–76. doi:10.1016/j.comcom.2021.06.013. [Google Scholar] [CrossRef]

29. Zhao Y, Wu L, Wang J, Li W, Jin J, Zhang Z, et al. LDSAV: lightweight and dynamically scalable authentication key agreement for vehicle-cloud collaboration. IEEE Trans Veh Technol. 2026;1–15. doi:10.1109/tvt.2026.3669949. [Google Scholar] [CrossRef]

30. Li X, Liu T, Obaidat MS, Wu F, Vijayakumar P, Kumar N. A lightweight privacy-preserving authentication protocol for VANETs. IEEE Syst J. 2020;14(3):3547–57. doi:10.1109/jsyst.2020.2991168. [Google Scholar] [CrossRef]

31. Coulibaly L, Hanyurwimfura D, Twahirwa E, Diwani A. A lightweight biometric-based user authentication protocol for self-driving vehicles. In: Proceedings of the 2024 1st International Conference on Cyber Security and Computing (CyberComp); 2024 Nov 6–7; Melaka, Malaysia. p. 144–9. doi:10.1109/cybercomp60759.2024.10913668. [Google Scholar] [CrossRef]

32. Burrows M, Abadi M, Needham R. A logic of authentication. ACM Trans Comput Syst. 1990;8(1):18–36. doi:10.1145/77648.77649. [Google Scholar] [CrossRef]

33. Viganò L. Automated security protocol analysis with the AVISPA tool. Electron Notes Theor Comput Sci. 2006;155(1):61–86. doi:10.1016/j.entcs.2005.11.052. [Google Scholar] [CrossRef]

34. Backbone Authors. Pqcrypto: post-quantum cryptography for python. 2026 [cited 2026 May 1]. Available from: https://pypi.org/project/pqcrypto/. [Google Scholar]

35. IEEE Std 80211bd-2022. IEEE standard for information technology, specific requirements part 11: wireless LAN medium access control (MAC) and physical layer (PHY) specifications amendment 5: enhancements for next generation V2X. Piscataway, NJ, USA: IEEE; 2023. p. 1–144. doi:10.1109/IEEESTD.2023.10063942. [Google Scholar] [CrossRef]