In recent years, the rapid advancement of drone technology has led to the widespread deployment of Unmanned Aerial Vehicle (UAV) networks in various critical fields such as logistics, agriculture, remote sensing, and disaster management. These networks leverage UAVs as aerial relay nodes to facilitate efficient communication among ground user equipment (UE) clusters. With the proliferation of 5G and future network environments, the application boundaries of UAV networks have expanded significantly. However, due to their inherent characteristics like high mobility, resource constraints, and unstable communication links, UAV networks face numerous challenges in terms of communication security and efficiency. For instance, when multiple UEs simultaneously initiate access authentication requests to a UAV, the computational load on the UAV increases substantially, making the system vulnerable to security threats such as replay attacks and forgery attacks. Therefore, there is an urgent need to design an efficient, secure, and fault-tolerant batch authentication protocol that enables rapid mutual authentication and key agreement between UAVs and UEs.
Existing batch authentication protocols often lack robustness in fault tolerance. If any invalid authentication information is present in the access requests, it can lead to the failure of the entire batch authentication process, thereby reducing overall efficiency. Some improved schemes that incorporate error detection mechanisms face practical challenges, such as difficulty in accurately locating invalid signatures and complex, resource-intensive error detection processes. These limitations hinder their applicability in UAV networks, which demand high real-time performance and reliability. Moreover, mainstream authentication systems, such as those based on Public Key Infrastructure (PKI) and Identity-Based Signature (IBS), suffer from structural drawbacks like cumbersome certificate management or key escrow risks, limiting their adaptability and scalability in dynamic heterogeneous environments. Certificateless signature (CLS)-based authentication systems, while addressing some issues, are primarily designed for point-to-point communication and struggle to handle high-concurrency scenarios where UE clusters simultaneously access UAV networks.
To address these challenges, this article proposes an efficient batch authentication and key agreement protocol that combines certificateless aggregate signature (CLAS) technology with group testing methods. CLAS technology effectively integrates the advantages of certificateless cryptography and aggregate signatures, eliminating the certificate management issues of traditional PKI systems and aggregating multiple signatures into a single short signature, thereby significantly reducing verification overhead—particularly suitable for resource-constrained UAV scenarios. To enhance the protocol’s fault tolerance, a group testing-based error detection mechanism is designed to quickly identify and locate invalid access authentication requests in case of batch authentication failure, avoiding the rejection of valid requests and improving overall authentication efficiency and system robustness.
The main contributions of this work are as follows: First, an efficient batch authentication mechanism is designed based on CLAS technology, constructing a batch authentication protocol that supports concurrent access without bilinear pairing operations, significantly reducing UAV computational overhead and improving authentication efficiency. Second, a rapid error detection mechanism is introduced by incorporating group testing concepts, developing a method with high localization accuracy and low resource consumption for detecting invalid requests. This effectively addresses the issues in traditional schemes where erroneous requests cannot be accurately identified and error detection requires excessive iterations, thereby enhancing the success rate of batch authentication and system stability.
The remainder of this article is organized as follows: Section 2 reviews related work, including batch authentication schemes and those with error detection capabilities. Section 3 outlines the system model, security model, and security requirements. Section 4 details the proposed scheme. Section 5 provides security analysis and proofs. Section 6 conducts performance analysis, and Section 7 concludes the article.
Related Work
In recent years, to address the growing communication security demands in UAV networks, extensive research has focused on identity authentication mechanisms and batch authentication protocols. Existing studies can be broadly categorized into three types: authentication schemes based on traditional encryption systems, efficient batch authentication schemes based on CLAS, and fault-tolerant batch authentication schemes with error detection capabilities.
Authentication protocols based on traditional encryption systems primarily include PKI, IBS, and CLS-based security mechanisms. PKI binds public keys to identities through digital certificates, offering a mature key management system widely used in UAV communication environments. For example, Jadhav et al. proposed a PKI-based lightweight authentication and encryption mechanism for ground-air link environments with limited computational resources. Alladi et al. designed the SecAuthUAV protocol, employing PKI for mutual authentication between UAVs and ground stations, as well as between UAVs, enhancing the security and flexibility of UAV networks. However, PKI schemes suffer from complex key management and difficulties in certificate revocation, leading to high deployment costs in highly dynamic UAV networks. To address certificate management issues and improve deployment efficiency in dynamic networks, researchers have proposed IBS-based schemes. This method generates public keys using users’ unique identity information, avoiding the complex certificate distribution and revocation operations of traditional PKI systems. Jan et al. introduced an authentication protocol combining IBS and aggregate signatures for military-grade scenarios, improving verification efficiency while simplifying key management. Wani et al. constructed an IBS-based identity authentication mechanism for UAV communication systems in heterogeneous networks. However, these IBS-based schemes face the key escrow problem. To resolve the certificate management issues of PKI and the key escrow problems of IBS, researchers proposed CLS schemes. The CLS system splits private keys into user-specific parts and parts generated by a Key Generation Center (KGC), eliminating the reliance on certificates while avoiding key escrow risks in traditional IBS schemes, making it an important authentication mechanism in UAV communication environments. Semal et al. proposed a CLS-based group authentication and key agreement protocol for untrusted UAV networks, supporting low computational overhead and high-security bidirectional authentication in resource-constrained, heterogeneous UAV environments. Li et al. further presented a lightweight CLS authentication protocol without bilinear pairing operations, significantly improving authentication efficiency and protocol deployability in UAV networks through pairing-free structures. Although CLS-based schemes achieve a good balance between authentication efficiency and key security, they are primarily designed for point-to-point authentication scenarios and struggle to support high-concurrency environments where UE clusters simultaneously access UAVs.
To adapt to high-concurrency scenarios where UE clusters simultaneously access UAVs, researchers have combined CLS with aggregate signature technology to propose CLAS mechanisms. Priyanka et al. introduced a CLAS-based batch authentication scheme for vehicular ad-hoc networks (VANETs). Samra et al. proposed a conditional privacy-preserving authentication scheme for VANETs using CLAS technology, but the bilinear pairing operations introduced some delays in signature authentication. To improve the efficiency of signature generation and authentication, Ali et al. presented a pairing-free CLAS-based conditional privacy-preserving scheme for VANETs using elliptic curve cryptography, achieving batch authentication. However, these CLAS schemes generally overlook the identification of invalid requests after authentication failure, lacking the ability to identify and locate invalid requests in such scenarios. If a single invalid request exists, the entire batch must be re-authenticated, leading to significant resource wastage and limiting the protocol’s practical application in high-density concurrent access scenarios. Therefore, introducing fault tolerance mechanisms and efficient error detection capabilities within the CLAS framework has become a key research direction.
Addressing the fault tolerance issue in batch authentication, existing research has attempted to incorporate error detection mechanisms to identify invalid signatures or introduce fault tolerance thresholds to allow authentication to pass even in the presence of a certain number of invalid signatures. In terms of error detection mechanisms, Hartung et al. proposed an error detection method based on d-disjoint matrices, where the verification process can output a list of valid messages, but the scheme is complex, computationally intensive, and limits the maximum number of faulty signatures. Thais et al. introduced an unbounded fault-tolerant aggregate signature scheme based on nested covering-free families, which imposes no limit on the number of faulty signatures. However, the error detection process is complex and requires numerous iterations. In terms of introducing fault tolerance thresholds, Wang et al. proposed an authentication scheme for UAV networks combining CLS with fuzzy batch verification mechanisms, incorporating fault tolerance properties to improve authentication efficiency. However, this scheme cannot detect invalid signatures. Based on the above related work, it is evident that existing fault-tolerant batch authentication schemes still have room for improvement in terms of error identification efficiency, computational complexity, and practical deployment capability, particularly lacking lightweight error detection mechanisms suitable for resource-constrained UAV network scenarios.
This article combines CLAS with group testing to design a batch authentication and key agreement protocol that supports rapid error localization. The scheme not only enhances overall authentication efficiency but also significantly reduces the computational and communication overhead of UAVs when handling invalid requests, improving the protocol’s practicality.
System Model and Problem Description
System Model
In the context of UAV networks, a batch authentication and key agreement protocol for communication between UAVs and UE clusters is constructed. The model includes four entities: UE, UAV, Control Center (CC), and KGC. The specific system model is illustrated in the provided figure.
In the system model, the CC is fully trusted and responsible for system initialization, user registration, generating and distributing pseudonyms for UEs, and tracking illegal user identities. The KGC is responsible for generating public-private key pairs for UAVs and partial private keys for UEs. UEs, as communication initiators, send access authentication requests to UAVs and receive response messages from UAVs, authenticating the UAVs’ legitimate identities. During system establishment, UEs must send their real identities to the CC for registration and use pseudonyms during communication to ensure anonymity. UAVs are responsible for receiving multiple UE access requests, aggregating these requests, using CLAS mechanisms to reduce authentication overhead, completing batch authentication, and negotiating session keys with each UE.
Under this model, batch authentication is adopted to support scenarios where UE clusters concurrently access through UAV nodes. To alleviate the computational burden on UAVs during batch authentication, the system employs CLAS mechanisms for aggregate signature authentication. Simultaneously, to effectively address batch authentication failures caused by illegal UE access, a group testing-based error detection mechanism is introduced, ensuring authentication efficiency while maintaining security and fault tolerance.
Security Model
To systematically evaluate the protocol’s security under the random oracle model, this section describes the random oracle model, defines the attacker’s capabilities, and based on this, defines the conditions for the scheme to satisfy security.
Attacker Categories
Based on the attacker’s behavior, two types of attackers are considered.
Type I Attacker ($\mathcal{A}_{1}$): The attacker can compromise the UE’s secret value or replace any UE’s public key with a value of their choice but cannot access the KGC’s master key.
Type II Attacker ($\mathcal{A}_{2}$): The attacker can access the KGC’s master key but cannot replace any UE’s public key or generate partial private keys for UEs.
Oracles
This section defines the following five oracles that the attacker $\mathcal{A}$ can access.
Reveal Partial Private Key Oracle: Upon receiving a query from $\mathcal{A}$, the challenger $\mathcal{C}$ takes $PID_i$ as input, computes $psk_{PID_i}$, and sends it to $\mathcal{A}$.
Create User Oracle: Upon receiving a query from $\mathcal{A}$, the challenger $\mathcal{C}$ takes $PID_i$ as input, computes $vpk_{PID_i}$, and sends it to $\mathcal{A}$.
Reveal Private Key Oracle: Upon receiving a query from $\mathcal{A}$, the challenger $\mathcal{C}$ takes $PID_i$ as input, computes $vsk_{PID_i}$, and sends it to $\mathcal{A}$.
Replace Public Key Oracle: $\mathcal{A}$ inputs $PID_i$ and $vpk_{PID_i}’$, replacing the current public key $vpk_{PID_i}$ with the desired public key $vpk_{PID_i}’$.
Signature Oracle: Upon receiving a query from $\mathcal{A}$, the oracle returns a valid signature $\sigma$ based on $PID_i$, $vpk_{PID_i}$, and message $m$.
Security Definitions
This section defines the unforgeability of the scheme through two games defined between the challenger $\mathcal{C}$ and the attacker $\mathcal{A}$.
Game 1 is conducted between the challenger $\mathcal{C}$ and the attacker $\mathcal{A}_{1}$, with the following specific steps:
Initialization Phase: In the initialization phase, the challenger $\mathcal{C}$ runs the setup algorithm to obtain parameters, secret value $s$, and master public key. Then, $\mathcal{C}$ sends the parameters and master public key to $\mathcal{A}_{1}$, retaining the secret value $s$.
Query Phase: In the query phase, $\mathcal{A}_{1}$ queries the reveal partial private key oracle, create user oracle, reveal private key oracle, replace public key oracle, and signature oracle.
Forgery Phase: Finally, $\mathcal{A}_{1}$ outputs a signature $\sigma^*$ corresponding to message $m_i^*$, $PID_i^*$, and $vpk_{PID_i}^*$. $\mathcal{A}_{1}$ wins this game if the following conditions are met: (a) $\sigma^*$ is a valid signature; (b) $PID_i^*$ has not been queried to the partial private key oracle and private key oracle; (c) the signature oracle has never been called during the game.
Definition 1: If no attacker $\mathcal{A}_{1}$ can win Game 1 with a non-negligible probability within polynomial time $t$, then this authentication scheme satisfies Type I security.
Game 2 is conducted between the challenger $\mathcal{C}$ and $\mathcal{A}_{2}$, with the following specific steps:
Initialization Phase: The challenger $\mathcal{C}$ runs the initialization algorithm to generate system parameters, secret value $s$, and master public key. The system parameters and master public key are provided to $\mathcal{A}_{2}$.
Query Phase: $\mathcal{A}_{2}$ queries the create user oracle, reveal private key oracle, and signature oracle.
Forgery Phase: Finally, $\mathcal{A}_{2}$ outputs a signature $\sigma^*$ corresponding to message $m_i^*$, $PID_i^*$, and $vpk_{PID_i}^*$. $\mathcal{A}_{2}$ wins this game if the following conditions are met: (a) $\sigma^*$ is a valid signature; (b) $PID_i^*$ has not been queried to the reveal private key oracle to obtain the private key; (c) the signature oracle has never been called.
Definition 2: If no attacker $\mathcal{A}_{2}$ can win Game 2 with a non-negligible probability within polynomial time $t$, then this authentication scheme satisfies Type II security.
Security Goals
To ensure the security of the authentication protocol in UAV network environments, the protocol design must meet a series of core security objectives. The specific security goals are as follows:
Message Authenticity: After receiving a signed message, the recipient can confirm the message’s legitimacy and integrity through authentication, i.e., the message is sent by a legitimate user and has not been modified or tampered with by malicious attackers.
Conditional Identity Privacy: The real identity of the message sender is anonymous during communication, and no third party, except the CC, can obtain their real identity from the anonymity.
Traceability: When there is controversy over the message source or an accident occurs requiring accountability, the CC can obtain the real identity of the message sender.
Unlinkability: Malicious attackers cannot associate two or more messages from the same entity.
Resistance to Multiple Traditional Attacks: Attackers cannot obtain relevant information through certain traditional attacks to achieve their goals, such as replay attacks, forgery attacks, and man-in-the-middle attacks.
Batch Authentication and Key Agreement Protocol Based on Certificateless Aggregate Signature Technology
This section details the proposed batch authentication scheme. The scheme is divided into six phases: system setup, pseudonym and partial private key generation, UE key pair generation, mutual authentication and key agreement, batch authentication and key agreement, and batch authentication error detection.
System Setup Phase
In the system setup phase, the CC and KGC generate necessary system parameters. The CC and KGC select two large primes $p$ and $q$, generating an elliptic curve $E: y^2 = x^3 + ax + b \mod p$, where $a, b \in \mathbb{Z}_p^*$ and $4a^3 + 27b^2 \mod p \neq 0$. The CC selects a point $P$ at infinity as the base point of the elliptic curve. The KGC selects a random number $s \in \mathbb{Z}_p^*$ as the master private key and computes the master public key $P_{pub} = s \cdot P$. The CC selects a random number $b \in \mathbb{Z}_p^*$ as the master private key and computes the master public key $T_{pub} = b \cdot P$. Additionally, the KGC generates a public-private key pair for the UAV. The KGC and CC select three hash functions $H_1, H_2, H_3: \{0,1\}^* \rightarrow \mathbb{Z}_p$. The KGC randomly selects $q_{UAV} \in \mathbb{Z}_p^*$, computes $pk_{UAV} = q_{UAV} \cdot P$ as the UAV’s public key, and computes $sk_{UAV} = (q_{UAV} + H_1(ID_{UAV} \parallel pk_{UAV}) \cdot s$ as the UAV’s private key. The UE sends its real identity $RID_i$ to the CC for registration. Finally, the CC and KGC publish the system parameters $\{P, p, q, E, G, H_1, H_2, H_3, P_{pub}, T_{pub}, pk_{UAV}\}$.
Pseudonym and Partial Private Key Generation
In this phase, the CC generates pseudonyms for the UE, and the KGC generates partial private keys for the UE. First, the UE randomly selects $t_i$ and computes $PID_{i,1} = t_i \cdot P$, $Key_i = RID_i \oplus t_i \cdot T_{pub}$, sending the pseudonym request message $\{PID_{i,1}, Key_i\}$ to the CC. After receiving the pseudonym request message, the CC first computes $Key_i \oplus PID_{i,1} \stackrel{?}{=} RID_i \cdot b$ to verify the UE’s legitimate identity. After verification, the CC computes the pseudonym $PID_{i,2} = H_1(RID_i \oplus b \cdot T_{pub}, \Delta T_i)$, pseudonym $PID_i = \{PID_{i,1}, PID_{i,2}, \Delta T_i\}$, where $\Delta T_i$ is the validity period of the pseudonym. The CC sends $PID_i$ to the KGC via a secure channel. Upon receipt, the KGC randomly selects $r_i$, computes $R_i = r_i \cdot P$, and computes the partial private key $psk_{PID_i} = (r_i + s \cdot K_i) \mod p$, where $K_i = H_1(PID_i, R_i, P_{pub})$. The KGC sends $\{psk_{PID_i}, R_i, PID_i\}$ to the UE. After receiving it, the UE verifies $psk_{PID_i} \cdot P \stackrel{?}{=} R_i + K_i \cdot P_{pub}$ to verify the message’s integrity and validity.
UE Key Pair Generation
In this phase, the UE generates its own public-private key pair. The UE randomly selects $x_i$ as the secret value, computes $X_i = x_i \cdot P$, $Q_i = R_i + H_2(PID_i, X_i) \cdot X_i$. The UE’s public key is $vpk_{PID_i} = (Q_i, R_i)$, and the private key is $vsk_{PID_i} = (psk_{PID_i}, x_i)$.
Mutual Authentication and Key Agreement Phase
This phase involves mutual authentication and key agreement between a single UE and the UAV. The specific process mainly includes the following steps: The UE first generates temporary public and private keys and constructs an access authentication request message sent to the UAV. After receiving the request, the UAV verifies the pseudonym’s validity and timestamp, then verifies the UE’s legitimate identity based on the signature information. After successful authentication, the UAV generates its own temporary key and computes the session key, then returns an access authentication response message. After receiving the response, the UE completes authentication and computes the session key, ultimately completing mutual authentication and key agreement between both parties. The specific process is shown in the provided figure.
First, the UE sends an access authentication request message to the UAV. The UE selects a random number $Tsk_{UE_i}$ as the temporary private key and computes the temporary public key $Tpk_{UE_i} = Tsk_{UE_i} \cdot P$. The UE randomly selects $u_i$, computes $U_i = u_i \cdot P$, $h_{2,i} = H_2(PID_i, X_i)$, $h_{3,i} = H_3(PID_i, M_i, vpk_{PID_i}, U_i, T_i)$, $S_i = (u_i + Tsk_{UE_i} \cdot (h_{3,i} + h_{2,i} \cdot (psk_{PID_i} + x_i))) \mod q$, $\sigma_i = (U_i, S_i)$. Here, $T_i$ is the timestamp, and $M_i$ is the message to be signed. The UE sends the access authentication request $\{PID_i, vpk_{PID_i}, M_i, T_i, \sigma_i, Tpk_{UE_i}\}$ to the UAV.
After receiving the access authentication request, the UAV first verifies that the pseudonym $PID_i$ is within the validity period and verifies the timestamp $T_i$. Then, it computes $K_i = H_1(PID_i, R_i, P_{pub})$, $h_{3,i} = H_3(PID_i, M_i, vpk_{PID_i}, U_i, T_i)$, and verifies $S_i \cdot P \stackrel{?}{=} U_i + Tpk_{UE_i} \cdot (h_{3,i} + Q_i + K_i \cdot P_{pub})$ to determine the UE’s legitimate identity. If verification fails, the authentication process is terminated. After successful verification, the UAV generates a random number $Tsk_{UAV}$ as the temporary private key and computes the temporary public key $Tpk_{UAV} = Tsk_{UAV} \cdot P$. The UAV computes the session key with the UE $SK_{UAV-UE_i} = Tsk_{UAV} \cdot Tpk_{UE_i}$. The UAV computes $h_{2,UAV} = H_2(ID_{UAV}, Tpk_{UAV}, T_{UAV})$, $v_{UAV} = Tsk_{UAV} + h_{2,UAV} \cdot sk_{UAV}$. Here, $T_{UAV}$ is the current timestamp. The UAV sends the access authentication response message $\{Tpk_{UAV}, ID_{UAV}, pk_{UAV}, T_{UAV}, v_{UAV}\}$ to the UE.
Correctness Analysis: In the UAV’s authentication process of a single message, by computing $K_i = H_1(PID_i, R_i, P_{pub})$, $h_{3,i} = H_3(PID_i, M_i, vpk_{PID_i}, U_i, T_i)$, using system parameters $P_{pub} = s \cdot P$, the UE’s temporary public key $Tpk_{UE_i} = Tsk_{UE_i} \cdot P$, the random number $U_i = u_i \cdot P$ generated by the UE, and the UE’s public key $vpk_{PID_i} = (Q_i, R_i)$, the UE’s legitimate identity is verified. From $psk_{PID_i} = r_i + s \cdot K_i$, $Q_i = R_i + H_2(PID_i, X_i) \cdot X_i$, and $X_i = x_i \cdot P$, Equation (1) is derived. If Equation (1) holds, it indicates that the UE is a legitimate user, and authentication passes; otherwise, the UE is an illegal user, and authentication fails.
$$S_i \cdot P = (u_i + Tsk_{UE_i} \cdot (h_{3,i} + h_{2,i} \cdot (psk_{PID_i} + x_i))) \cdot P = U_i + Tpk_{UE_i} \cdot (h_{3,i} + Q_i + K_i \cdot P_{pub})$$ (1)
After receiving the access authentication response message, the UE first verifies the timestamp, computes $h_{1,UAV} = H_1(ID_{UAV}, pk_{UAV})$, $h_{2,UAV} = H_2(ID_{UAV}, Tpk_{UAV}, T_{UAV})$, and verifies the equation $v_{UAV} \cdot P \stackrel{?}{=} Tpk_{UAV} + h_{2,UAV} \cdot pk_{UAV} + h_{1,UAV} \cdot H_1(ID_{UAV} \parallel pk_{UAV}) \cdot P_{pub}$ to determine the UAV’s legitimate identity. If verification fails, the authentication process is terminated. If verification passes, the UE computes the session key with the UAV $SK_{UAV-UE_i} = Tsk_{UE_i} \cdot Tpk_{UAV}$. At this point, the single UE completes access authentication and establishes a session key with the UAV.
Correctness Analysis: In the UE’s authentication of the UAV’s legitimate identity, by computing $h_{1,UAV} = H_1(ID_{UAV}, pk_{UAV})$, $h_{2,UAV} = H_2(ID_{UAV}, Tpk_{UAV}, T_{UAV})$, using system parameters $P_{pub} = s \cdot P$, the UAV’s temporary public key $Tpk_{UAV} = Tsk_{UAV} \cdot P$, and the UAV’s public key $pk_{UAV} = q_{UAV} \cdot P$, the UAV’s legitimate identity is verified. From $sk_{UAV} = q_{UAV} + H_1(ID_{UAV} \parallel pk_{UAV}) \cdot s$, Equation (2) is derived. If Equation (2) holds, it indicates that the UAV is legitimate, and authentication passes; otherwise, the UAV is illegal, and authentication fails.
$$v_{UAV} \cdot P = (Tsk_{UAV} + h_{2,UAV} \cdot sk_{UAV}) \cdot P = Tpk_{UAV} + h_{2,UAV} \cdot (pk_{UAV} + h_{1,UAV} \cdot P_{pub})$$ (2)
Batch Authentication and Key Agreement Phase
When the UAV receives access authentication requests from multiple UEs, it performs batch authentication on these requests. When the UAV receives $n$ access authentication requests $\{PID_i, vpk_{PID_i}, M_i, T_i, \sigma_i, Tpk_{UE_i}\}$ from $UE_1, UE_2, \ldots, UE_n$, it first sequentially verifies whether the pseudonyms $PID_i$ are within the validity period and verifies the timestamps $T_i$, computes $K_i = H_1(PID_i, R_i, P_{pub})$, $h_{3,i} = H_3(PID_i, M_i, vpk_{PID_i}, U_i, T_i)$. Then, it aggregates these access authentication request messages by computing $S = \sum_{i=1}^{n} S_i$. The aggregate signature is $\sigma_{agg} = (U_1, U_2, \ldots, U_n, S)$. The UAV performs batch authentication by verifying the equation $S \cdot P \stackrel{?}{=} \sum_{i=1}^{n} U_i + \sum_{i=1}^{n} Tpk_{UE_i} \cdot (h_{3,i} + Q_i + K_i \cdot P_{pub})$. If authentication fails, it indicates the presence of illegal users in the UE cluster, and the UAV will proceed to batch authentication error detection. After successful authentication, the UAV negotiates session keys with each UE. The UAV generates a random number $Tsk_{UAV}$ as the temporary private key and computes the temporary public key $Tpk_{UAV} = Tsk_{UAV} \cdot P$. The UAV computes the session key with each UE $SK_{UAV-UE_i} = Tsk_{UAV} \cdot Tpk_{UE_i}$. Then, the UAV computes $h_{2,UAV} = H_2(ID_{UAV}, Tpk_{UAV}, T_{UAV})$, $v_{UAV} = Tsk_{UAV} + h_{2,UAV} \cdot sk_{UAV}$. Here, $T_{UAV}$ is the UAV’s timestamp. The UAV sends the access authentication response message $\{Tpk_{UAV}, ID_{UAV}, pk_{UAV}, T_{UAV}, v_{UAV}\}$ to each UE.
After receiving the access authentication response message, the UE first verifies the timestamp, computes $h_{1,UAV} = H_1(ID_{UAV}, pk_{UAV})$, $h_{2,UAV} = H_2(ID_{UAV}, Tpk_{UAV}, T_{UAV})$, and verifies the equation $v_{UAV} \cdot P \stackrel{?}{=} Tpk_{UAV} + h_{2,UAV} \cdot pk_{UAV} + h_{1,UAV} \cdot H_1(ID_{UAV} \parallel pk_{UAV}) \cdot P_{pub}$ to determine the UAV’s legitimate identity. If verification fails, the authentication process is terminated. If verification passes, the UE computes the session key with the UAV $SK_{UAV-UE_i} = Tsk_{UE_i} \cdot Tpk_{UAV}$. At this point, the UAV completes batch authentication of the UEs and establishes session keys with each authenticated UE.
Correctness Analysis: In the UAV’s verification of the aggregate signature $\sigma_{agg} = (U_1, U_2, \ldots, U_n, S)$, by computing $K_i = H_1(PID_i, R_i, P_{pub})$, $h_{3,i} = H_3(PID_i, M_i, vpk_{PID_i}, U_i, T_i)$, using system parameters $P_{pub} = s \cdot P$, each UE’s temporary public key $Tpk_{UE_i} = Tsk_{UE_i} \cdot P$, the random number $U_i = u_i \cdot P$ generated by each UE, and each UE’s public key $vpk_{PID_i} = (Q_i, R_i)$, the validity of the aggregate signature is verified. From $psk_{PID_i} = r_i + s \cdot K_i$, $Q_i = R_i + H_2(PID_i, X_i) \cdot X_i$, and $X_i = x_i \cdot P$, Equation (3) is derived. From Equation (3), Equation (4) is derived. If Equation (4) holds, it indicates that each UE is a legitimate user, and batch authentication passes; otherwise, it indicates the presence of illegal users in the UE cluster, batch authentication fails, and the UAV will proceed to batch authentication error detection.
$$h_{2,i} \cdot (psk_{PID_i} + x_i) \cdot P = h_{2,i} \cdot (r_i \cdot P + s \cdot K_i \cdot P + x_i \cdot P) = h_{2,i} \cdot (R_i + K_i \cdot P_{pub} + X_i) = h_{2,i} \cdot (Q_i + K_i \cdot P_{pub})$$ (3)
$$S \cdot P = \sum_{i=1}^{n} S_i \cdot P = \sum_{i=1}^{n} (U_i + Tpk_{UE_i} \cdot (h_{3,i} + h_{2,i} \cdot (psk_{PID_i} + x_i))) \cdot P = \sum_{i=1}^{n} U_i + \sum_{i=1}^{n} Tpk_{UE_i} \cdot (h_{3,i} + Q_i + K_i \cdot P_{pub})$$ (4)
Batch Authentication Error Detection Phase
When batch authentication verification fails, the batch authentication error detection phase is entered. For $n$ signatures, with at most $d$ invalid signatures, a group testing method based on $(d, d)$-separable matrices is used to detect invalid signatures.
First, construct a $(d, d)$-separable matrix $M$. The matrix $M$ is a $2t \times n$ matrix, where $t$ is a multiple of $d$. For each column of matrix $M$, arbitrarily select $t/d$ rows and set their corresponding values to 1, while setting the remaining rows to 0, to construct matrix $M$. When $t \geq 2d \log(n) + \log(e \cdot d \cdot n)$, the matrix constructed by the above method is $(d, d)$-separable.
Then, perform a two-stage error detection process. According to matrix $M$, aggregate these signatures into $2t$ signatures. Each row of matrix $M$ represents an aggregate signature, formed by aggregating the signatures where the corresponding column is 1. In the first stage, these signatures are aggregated into $2t$ signatures for verification, obtaining $2d$ potentially invalid signatures. In the second stage, these $2d$ signatures are individually verified to obtain the list of invalid signatures, completing the detection of invalid signatures.
Security Analysis
In this chapter, the proposed scheme is subjected to informal security analysis, proven to be unforgeable under the random oracle model, and formally verified using Tamarin.
Informal Security Analysis
This section analyzes the security goals satisfied by the proposed scheme from the perspective of UAV network security requirements using informal methods.
Message Authenticity: In the scheme, before the UE sends an access authentication request message to the UAV, it must be signed with $S_i$. The UAV verifies $S_i \cdot P \stackrel{?}{=} U_i + Tpk_{UE_i} \cdot (h_{3,i} + Q_i + K_i \cdot P_{pub})$ to determine whether the message is from a legitimate UE and whether it has been modified or forged by malicious attackers. Before the UAV sends an access authentication response message to the UE, it must be signed with $v_{UAV}$. The UE verifies $v_{UAV} \cdot P \stackrel{?}{=} Tpk_{UAV} + h_{2,UAV} \cdot pk_{UAV} + h_{1,UAV} \cdot H_1(ID_{UAV} \parallel pk_{UAV}) \cdot P_{pub}$ to determine whether the message is from a legitimate UAV and whether it has been modified or forged by malicious attackers.
Conditional Identity Privacy: In the scheme, the UE uses the pseudonym $PID_i = \{PID_{i,1}, PID_{i,2}, \Delta T_i\}$ for communication, and attackers cannot obtain the UE’s real identity from the pseudonym.
Traceability: In the scheme, when controversial situations arise, the CC can compute $RID_i = PID_{i,2} \oplus H_1(b \cdot T_{pub}, \Delta T_i)$ to obtain the UE’s real identity from the pseudonym $PID_i = \{PID_{i,1}, PID_{i,2}, \Delta T_i\}$, where $b$ is the CC’s private key. Therefore, the scheme has traceability.
Unlinkability: In the scheme, the UE sends $\{PID_i, vpk_{PID_i}, M_i, T_i, \sigma_i, Tpk_{UE_i}\}$ to the UAV. Since the signature $\sigma_i$ contains the random number $u_i$, attackers cannot associate two messages from the same UE. Therefore, the scheme satisfies unlinkability.
Resistance to Multiple Traditional Attacks:
Replay Attack: In the scheme, the signature generation phase uses timestamps $T_i$ or $T_{UAV}$ to ensure that each signature is the latest message, and the message receiver verifies the timestamp to detect message freshness, resisting replay attacks.
Forgery Attack: In the scheme, before the UE sends an access authentication request message to the UAV, it must be signed with $S_i$. Before the UAV sends an access authentication response message to the UE, it must be signed with $v_{UAV}$. Therefore, it can detect whether the message is from a legitimate UE, resisting forgery attacks.
Man-in-the-Middle Attack: In the scheme, both the UAV and the UE must sign messages before sending them, and attackers cannot impersonate legitimate UAVs and UEs. Even if attackers eavesdrop on messages during access authentication, they cannot obtain the session key between the UAV and the UE. Therefore, the scheme can resist man-in-the-middle attacks.
Security Proof
According to the two types of attackers $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ defined in Chapter 3, this section proves the security of the proposed scheme through games between the challenger $\mathcal{C}$ and attackers $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$.
Theorem 1: Under the random oracle model, assuming the Elliptic Curve Discrete Logarithm Problem (ECDLP) is hard, the proposed scheme is secure against adaptive chosen message attacks, chosen identity attacks, and public key replacement attacks by Type I attacker $\mathcal{A}_{1}$.
Proof: Suppose an attacker $\mathcal{A}_{1}$ can forge a message $\sigma = \{PID_i, vpk_{PID_i}, M_i, T_i, U_i, S_i\}$ by constructing a challenger $\mathcal{C}$ that runs subroutine $\mathcal{A}_{1}$ with a non-negligible probability to solve ECDLP. Given an ECDLP problem instance $(P, Q = s \cdot P)$, the challenger $\mathcal{C}$ simulates oracles and interacts with attacker $\mathcal{A}_{1}$ as follows.
System Initialization Phase: The challenger $\mathcal{C}$ executes the system initialization program, randomly selects $s \in \mathbb{Z}_q^*$, computes $P_{pub} = s \cdot P$. Let $P_{pub} = Q$, generate system public parameters $\{P, p, q, E, G, H_1, H_2, H_3, P_{pub}, T_{pub}\}$, and send the parameters to attacker $\mathcal{A}_{1}$.
$H_3$ Query: The challenger $\mathcal{C}$ maintains a list $L_{H_3}$, initially empty, with element type $\{PID_i, M_i, T_i, h_{3,i}\}$. When attacker $\mathcal{A}_{1}$ requests a query about $PID_i$, $\mathcal{C}$ checks if $L_{H_3}$ contains $\{PID_i, M_i, T_i, h_{3,i}\}$. If it exists, $\mathcal{C}$ returns $h_{3,i}$. If not, $\mathcal{C}$ selects a random value $h_{3,i} \in \mathbb{Z}_q^*$ as response and stores $\{PID_i, M_i, T_i, h_{3,i}\}$ in $L_{H_3}$.
User Creation: The challenger $\mathcal{C}$ maintains a list $L_{PK}$, initially empty, with element type $\{PID_i, psk_{PID_i}, vpk_{PID_i}, vsk_{PID_i}\}$. When attacker $\mathcal{A}_{1}$ requests a query about $PID_i$, $\mathcal{C}$ checks if $L_{PK}$ contains $\{PID_i, psk_{PID_i}, vpk_{PID_i}, vsk_{PID_i}\}$. If it exists, $\mathcal{C}$ returns $vpk_{PID_i}$. If not, $\mathcal{C}$ performs the following operations: randomly select $r, b, x_i \in \mathbb{Z}_q^*$, set $R_i = r \cdot P + b \cdot P$, $K_i = -r \mod q$, $psk_{PID_i} = b$, $vsk_{PID_i} = x_i$, $vpk_{PID_i} = x_i \cdot P$. The equation $psk_{PID_i} \cdot P = R_i + K_i \cdot P_{pub}$ holds. Store $\{PID_i, psk_{PID_i}, vpk_{PID_i}, vsk_{PID_i}\}$ in $L_{PK}$ and return $vpk_{PID_i}$ to $\mathcal{A}_{1}$.
Partial Private Key: When attacker $\mathcal{A}_{1}$ requests a partial private key query for $PID_i$, the challenger $\mathcal{C}$ checks if $L_{PK}$ contains $\{PID_i, psk_{PID_i}, vpk_{PID_i}, vsk_{PID_i}\}$. If it exists, $\mathcal{C}$ returns $psk_{PID_i}$. If not, $\mathcal{C}$ returns $\perp$.
User Private Key: When attacker $\mathcal{A}_{1}$ requests a private key query for $PID_i$, the challenger $\mathcal{C}$ checks if $L_{PK}$ contains $\{PID_i, psk_{PID_i}, vpk_{PID_i}, vsk_{PID_i}\}$. If it exists, $\mathcal{C}$ returns $vsk_{PID_i}$. If not, $\mathcal{C}$ returns $\perp$.
User Public Key Replacement: When attacker $\mathcal{A}_{1}$ requests a public key replacement query for $PID_i$, the challenger $\mathcal{C}$ checks if $L_{PK}$ contains $\{PID_i, psk_{PID_i}, vpk_{PID_i}, vsk_{PID_i}\}$. If it exists, $\mathcal{C}$ updates $vpk_{PID_i}$ to $vpk_{PID_i}’$.
Signature Query: When attacker $\mathcal{A}_{1}$ requests a signature query for $PID_i$, the challenger $\mathcal{C}$ computes $S_i$ such that $S_i \cdot P = U_i + Tpk_{UE_i} \cdot (h_{3,i} + Q_i + K_i \cdot P_{pub})$, returning $S_i$ to attacker $\mathcal{A}_{1}$.
Output: Finally, attacker $\mathcal{A}_{1}$ outputs $\sigma^* = \{PID_i^*, vpk_{PID_i}^*, M_i^*, T_i^*, U_i^*, S_i^*\}$ satisfying $S_i^* \cdot P = U_i^* + Tpk_{UE_i}^* \cdot (h_{3,i}^* + Q_i^* + K_i^* \cdot P_{pub})$. Attacker $\mathcal{A}_{1}$ replays the above process to forge another valid message $\sigma^* = \{PID_i^*, vpk_{PID_i}^*, M_i^*, T_i^*, U_i^*, S_i^*\}$, satisfying $S_i^* \cdot P = U_i^* + Tpk_{UE_i}^* \cdot (h_{3,i}^* + Q_i^* + K_i^* \cdot P_{pub})$. From these two equations, we obtain:
$$(S_i – S_i^*) \cdot P = (h_{3,i} – h_{3,i}^*) \cdot (K_i – K_i^*) \cdot P = (h_{3,i} – h_{3,i}^*) \cdot (K_i – K_i^*) \cdot s \cdot P$$ (5)
$$S_i – S_i^* = (K_i – K_i^*) \cdot s$$ (6)
The challenger $\mathcal{C}$ outputs $s = (K_i – K_i^*)^{-1} \cdot (S_i – S_i^*)$ to solve the given ECDLP instance; otherwise, the game fails.
Therefore, under the random oracle model and ECDLP assumption, the scheme is secure against Type I attacker $\mathcal{A}_{1}$.
Theorem 2: Under the random oracle model, assuming ECDLP is hard, the proposed scheme is secure against adaptive chosen message attacks and chosen identity attacks by Type II attacker $\mathcal{A}_{2}$.
Proof: Suppose an attacker $\mathcal{A}_{2}$ can forge a message $\sigma = \{PID_i, vpk_{PID_i}, M_i, T_i, U_i, S_i\}$ by constructing a challenger $\mathcal{C}$ that runs subroutine $\mathcal{A}_{2}$ with a non-negligible probability to solve ECDLP. Given an ECDLP problem instance $(P, Q = x \cdot P)$, the challenger $\mathcal{C}$ simulates oracles and interacts with attacker $\mathcal{A}_{2}$ as follows.
System Initialization Phase: The challenger $\mathcal{C}$ executes the system initialization program, randomly selects $s \in \mathbb{Z}_q^*$, computes $P_{pub} = s \cdot P$. Let $P_{pub} = Q$, generate system public parameters $\{P, p, q, E, G, H_1, H_2, H_3, P_{pub}, T_{pub}\}$, and send the public parameters and $s$ to attacker $\mathcal{A}_{2}$.
$H_2$ Query: The challenger $\mathcal{C}$ maintains a list $L_{H_2}$, initially empty, with element type $\{PID_i, M_i, T_i, h_{2,i}\}$. When attacker $\mathcal{A}_{2}$ requests a query about $PID_i$, $\mathcal{C}$ checks if $L_{H_2}$ contains $\{PID_i, M_i, T_i, h_{2,i}\}$. If it exists, $\mathcal{C}$ returns $h_{2,i}$. If not, $\mathcal{C}$ selects a random value $h_{2,i} \in \mathbb{Z}_q^*$ as response and stores $\{PID_i, M_i, T_i, h_{2,i}\}$ in $L_{H_2}$.
$H_3$ Query: The challenger $\mathcal{C}$ maintains a list $L_{H_3}$, initially empty, with element type $\{PID_i, M_i, T_i, h_{3,i}\}$. When attacker $\mathcal{A}_{2}$ requests a query about $PID_i$, $\mathcal{C}$ checks if $L_{H_3}$ contains $\{PID_i, M_i, T_i, h_{3,i}\}$. If it exists, $\mathcal{C}$ returns $h_{3,i}$. If not, $\mathcal{C}$ selects a random value $h_{3,i} \in \mathbb{Z}_q^*$ as response and stores $\{PID_i, M_i, T_i, h_{3,i}\}$ in $L_{H_3}$.
User Creation: The challenger $\mathcal{C}$ maintains a list $L_{PK}$, initially empty, with element type $\{PID_i, psk_{PID_i}, vpk_{PID_i}, vsk_{PID_i}\}$. When attacker $\mathcal{A}_{2}$ requests a query about $PID_i$, $\mathcal{C}$ checks if $L_{PK}$ contains $\{PID_i, psk_{PID_i}, vpk_{PID_i}, vsk_{PID_i}\}$. If it exists, $\mathcal{C}$ returns $vpk_{PID_i}$. If not, $\mathcal{C}$ performs the following operations: randomly select $r, x_i \in \mathbb{Z}_q^*$, set $R_i = r \cdot P$, $K_i = H_1(PID_i, R_i, P_{pub})$, $psk_{PID_i} = (r + s \cdot K_i) \mod q$, $vsk_{PID_i} = \perp$, $vpk_{PID_i} = x_i \cdot P = x_i \cdot Q$. The equation $psk_{PID_i} \cdot P = R_i + K_i \cdot P_{pub}$ holds. Store $\{PID_i, psk_{PID_i}, vpk_{PID_i}, vsk_{PID_i}\}$ in $L_{PK}$ and return $vpk_{PID_i}$ to $\mathcal{A}_{2}$.
Partial Private Key: When attacker $\mathcal{A}_{2}$ requests a partial private key query for $PID_i$, the challenger $\mathcal{C}$ checks if $L_{PK}$ contains $\{PID_i, psk_{PID_i}, vpk_{PID_i}, vsk_{PID_i}\}$. If it exists, $\mathcal{C}$ returns $psk_{PID_i}$. If not, $\mathcal{C}$ performs a user creation query and returns $psk_{PID_i}$.
User Private Key: When attacker $\mathcal{A}_{2}$ requests a private key query for $PID_i$, the challenger $\mathcal{C}$ checks if $L_{PK}$ contains $\{PID_i, psk_{PID_i}, vpk_{PID_i}, vsk_{PID_i}\}$. If it exists, $\mathcal{C}$ returns $vsk_{PID_i}$. If not, $\mathcal{C}$ returns $\perp$.
Signature Query: When attacker $\mathcal{A}_{2}$ requests a signature query for $PID_i$, the challenger $\mathcal{C}$ computes $S_i$ such that $S_i \cdot P = U_i + Tpk_{UE_i} \cdot (h_{3,i} + Q_i + K_i \cdot P_{pub})$, returning $S_i$ to attacker $\mathcal{A}_{2}$.
Output: Finally, attacker $\mathcal{A}_{2}$ outputs $\sigma^* = \{PID_i^*, vpk_{PID_i}^*, M_i^*, T_i^*, U_i^*, S_i^*\}$ satisfying $S_i^* \cdot P = U_i^* + Tpk_{UE_i}^* \cdot (h_{3,i}^* + psk_{PID_i}^* \cdot P + h_{2,i}^* \cdot x_i \cdot P)$. Attacker $\mathcal{A}_{2}$ replays the above process to forge another valid message $\sigma^* = \{PID_i^*, vpk_{PID_i}^*, M_i^*, T_i^*, U_i^*, S_i^*\}$, satisfying $S_i^* \cdot P = U_i^* + Tpk_{UE_i}^* \cdot (h_{3,i}^* + psk_{PID_i}^* \cdot P + h_{2,i}^* \cdot x_i \cdot P)$. From these two equations, we obtain:
$$(S_i – S_i^*) \cdot P = (h_{3,i} – h_{3,i}^*) \cdot P + (h_{2,i} \cdot x_i – h_{2,i}^* \cdot x_i^*) \cdot P = (h_{3,i} – h_{3,i}^*) \cdot P + (h_{2,i} \cdot x_i – h_{2,i}^* \cdot x_i^*) \cdot x \cdot P$$ (7)
$$S_i – S_i^* = (h_{3,i} – h_{3,i}^*) + (h_{2,i} \cdot x_i – h_{2,i}^* \cdot x_i^*) \cdot x$$ (8)
The challenger $\mathcal{C}$ outputs $x = (h_{2,i} \cdot x_i – h_{2,i}^* \cdot x_i^*)^{-1} \cdot (S_i – S_i^* – (h_{3,i} – h_{3,i}^*))$ to solve the given ECDLP instance; otherwise, the game fails.
Therefore, under the random oracle model and ECDLP assumption, the scheme is secure against Type II attacker $\mathcal{A}_{2}$.
Formal Verification
In this section, the formal verification tool Tamarin is used to perform formal analysis of the proposed scheme. Tamarin is a symbolic analysis tool based on multiset rewriting rules and first-order logic. Tamarin has a built-in Dolev-Yao model and a series of security theories supporting common cryptographic functions. In Tamarin, ‘All’ represents universal quantification, ‘Ex’ represents existential quantification, ‘#’ represents the prefix of time variables, ‘Fr(~x)’ represents the generation of fresh value x, ‘F(t1, t2, …, tn)’ represents the form of facts, ‘rule’ represents the specific protocol to be verified, and ‘lemma’ represents the security properties to be proven based on the action facts defined in ‘rule’.
In the Tamarin model of this scheme, two basic roles are defined. Among them, UE represents the UE in the scheme, and UAV represents the UAV in the scheme. During the formal verification process, the scheme is modeled as four rules: Setup, UE_1, UAV_1, and UE_2. Among them, the rule Setup represents the system setup phase, generating system parameters for the system, UE, and UAV. The rule UE_1 represents the process where the UE generates and sends an access authentication request. The rule UAV_1 represents the process where the UAV receives the access authentication request, verifies the access authentication request, computes the session key, and generates and sends the access authentication response. The rule UE_2 represents the process where the UE receives the access authentication response, verifies the access authentication response, and computes the session key. The formal verification result of the scheme is shown in the provided figure. During the formal verification process, four lemmas are used to verify the security of the scheme. The lemma UAV_auth_UE verifies whether the UAV can authenticate the UE. The lemma UE_auth_UAV verifies whether the UE can authenticate the UAV. The lemmas ExecutableRequest and ExecutableConfirm ensure that the lemmas are not vacuously true due to the model’s inability to execute. The proposed scheme can successfully achieve authentication from UE to UAV and from UAV to UE, as shown in the figure.
Performance Analysis
This chapter analyzes the computational cost, communication cost, and error detection complexity of the proposed scheme and compares it with other related literature [21-24].
For schemes based on bilinear pairing, use bilinear pairing $e: G_1 \times G_1 \rightarrow G_2$ to achieve 80-bit security strength, where $G_1$ is an additive group generated by point $P$. Point $P$ is defined on a q-order supersingular elliptic curve $E: y^2 = x^3 + x \mod p$ with embedding degree 2, where $p$ is a 512-bit prime, $q$ is a 160-bit Solinas prime, and satisfies $p + 1 = 12r \cdot q$.
For schemes based on elliptic curve cryptography, use a q-order additive group $G$ generated by point $P$ defined on a non-singular elliptic curve $E: y^2 = x^3 + ax + b \mod p$ to achieve 80-bit security strength, where $p$ and $q$ are two 160-bit primes, $a, b \in \mathbb{Z}_p^*$.
Computational Overhead
This section analyzes the computational efficiency of the proposed scheme and compares it with other batch authentication literature [21-24]. For ease of comparison, let $T_{BP}$ be the time consumed to perform a bilinear pairing operation, $T_H$ be the time consumed to perform a one-way hash function operation, $T_{MTP}$ be the time consumed to perform a Map-to-point hash function operation, $T_{BPA}$ be the time consumed to perform an elliptic curve addition operation, $T_{BPM}$ be the time consumed to perform an elliptic curve multiplication operation, $T_s$ be the time consumed to perform a scalar multiplication operation, and $T_e$ be the time consumed to perform an exponentiation operation. This article adopts the experimental data from schemes [7, 25], i.e., $T_H = 0.0001$ ms, $T_{MTP} = 4.1091$ ms, $T_{BP} = 1.6447$ ms, $T_{BPA} = 0.0099$ ms, $T_{BPM} = 1.7975$ ms, $T_s = 0.442$ ms, $T_e = 0.6$ ms. The experiment uses the MIRACL cryptographic library, running on an Intel Core i5 2.90 GHz, 16 GB RAM, Windows 7 operating system.
In literature [21], the vehicle needs to perform one elliptic curve multiplication operation, three one-way hash function operations, one elliptic curve addition operation, and two scalar multiplication operations. Therefore, the computational cost to generate a single signature is $T_{BPM} + 3T_H + T_{BPA} + 2T_s = 2.6917$ ms. The verifier verifying a single signature requires five elliptic curve multiplication operations, three one-way hash function operations, and one elliptic curve addition operation. Therefore, the computational cost to verify a single signature is $5T_{BPM} + 3T_H + T_{BPA} = 8.9977$ ms. The verifier verifying $n$ signatures requires $2n+1$ elliptic curve multiplication operations, $2n$ elliptic curve addition operations, $n$ scalar multiplication operations, and $2n$ one-way hash operations. Therefore, the computational cost to verify $n$ signatures is $(2n+1)T_{BPM} + 2nT_{BPA} + nT_s + 2nT_H = (4.057n + 1.7975)$ ms.
In literature [22], the vehicle needs to perform three one-way hash operations, three scalar multiplication operations, two elliptic curve multiplication operations, and one elliptic curve addition operation. Therefore, the computational cost to generate a single signature is $2T_{BPM} + T_{BPA} + 3T_H + 3T_s = 4.9312$ ms. The verifier verifying a single signature requires three bilinear pairing operations, two elliptic curve multiplication operations, and one one-way hash function operation. Therefore, the computational cost to verify a single signature is $3T_{BP} + 2T_{BPM} + T_H = 8.5292$ ms. The verifier verifying $n$ signatures requires $3n$ bilinear pairing operations, $2n$ elliptic curve addition operations, and one elliptic curve multiplication operation. Therefore, the computational cost to verify $n$ signatures is $3nT_{BP} + 2nT_{BPA} + T_{BPM} = (8.5291n + 1.7975)$ ms.
In literature [23], the vehicle computing a single signature requires five one-way hash operations, four elliptic curve addition operations, and two elliptic curve multiplication operations. Therefore, the computational cost to generate a single signature is $2T_{BPM} + 4T_{BPA} + 5T_H = 3.6351$ ms. The verifier verifying a single signature requires four one-way hash function operations, one elliptic curve addition operation, and seven elliptic curve multiplication operations. Therefore, the computational cost to verify a single signature is $4T_H + T_{BPA} + 7T_{BPM} = 12.5928$ ms. The verifier verifying $n$ signatures requires $n$ one-way hash operations, $2n+5$ elliptic curve multiplication operations, and $6n+1$ elliptic curve addition operations. Therefore, the computational cost to verify $n$ signatures is $(2n+5)T_{BPM} + (6n+1)T_{BPA} + nT_H = (3.6644n + 8.9974)$ ms.
In literature [24], the user computing a single signature requires three elliptic curve multiplication operations, two scalar multiplication operations, and two one-way hash operations. Therefore, the computational cost to generate a single signature is $3T_{BPM} + 2T_s + 2T_H = 6.2767$ ms. Verifying a single signature requires two one-way hash operations, four elliptic curve multiplication operations, and two elliptic curve addition operations. Therefore, the computational cost to verify a single signature is $4T_{BPM} + 2T_{BPA} + 2T_H = 7.21$ ms. The verifier verifying $n$ signatures requires $2n+2$ elliptic curve multiplication operations, $2n+2$ elliptic curve addition operations, and $2n$ scalar multiplication operations. Therefore, the computational cost to verify $n$ signatures is $(2n+2)T_{BPM} + (2n+2)T_{BPA} + 2nT_s = (4.4988n + 3.6148)$ ms.
In this scheme, the UE computing a single signature requires two scalar multiplication operations. Therefore, the computational cost to generate a single signature is $2T_s = 2 \times 0.442 = 0.884$ ms. The verifier verifying a single signature requires three elliptic curve addition operations and three elliptic curve multiplication operations. Therefore, the computational cost to verify a single signature is $3T_{BPM} + 3T_{BPA} = 3 \times 1.7975 + 3 \times 0.0099 = 5.4222$ ms. The verifier verifying $n$ signatures requires $2n+1$ elliptic curve multiplication operations and $4n-3$ elliptic curve addition operations. Therefore, the computational cost to verify $n$ signatures is $(2n+1)T_{BPM} + (4n-3)T_{BPA} = (3.6346n + 1.7678)$ ms.
The computational overhead of schemes [21-24] and the proposed scheme is shown in Table 1. Compared with the optimal comparative scheme, the proposed scheme reduces the computational overhead by 67% in signature generation and by 25% in single signature verification. The comparison of single signature generation and single signature verification computational overhead is shown in Figure 4. The proposed scheme reduces the batch authentication computational overhead by 16%. The relationship between batch authentication time and the number of verified signatures is shown in Figure 5. Therefore, the proposed scheme has better performance in terms of computational overhead.
| Scheme | Signature | Single Signature Authentication | n Signatures Authentication |
|---|---|---|---|
| Yan et al. [21] | $T_{BPM} + 3T_H + T_{BPA} + 2T_s$ | $5T_{BPM} + 3T_H + T_{BPA}$ | $(2n+1)T_{BPM} + 2nT_{BPA} + nT_s + 2nT_H$ |
| Maurya et al. [22] | $2T_{BPM} + T_{BPA} + 3T_H + 3T_s$ | $3T_{BP} + 2T_{BPM} + T_H$ | $3nT_{BP} + 2nT_{BPA} + T_{BPM}$ |
| Dwivedi et al. [23] | $2T_{BPM} + 4T_{BPA} + 5T_H$ | $4T_H + T_{BPA} + 7T_{BPM}$ | $(2n+5)T_{BPM} + (6n+1)T_{BPA} + nT_H$ |
| Cui et al. [24] | $3T_{BPM} + 2T_s + 2T_H$ | $4T_{BPM} + 2T_{BPA} + 2T_H$ | $(2n+2)T_{BPM} + (2n+2)T_{BPA} + 2nT_s$ |
| Proposed Scheme | $2T_s$ | $3T_{BPM} + 3T_{BPA}$ | $(2n+1)T_{BPM} + (4n-3)T_{BPA}$ |
Communication Overhead
This section will compare the communication overhead of the proposed scheme with literature [21-24]. Since the sizes of $p$ and $q$ are 64 bytes and 20 bytes respectively, the element sizes in $G_1$ and $G$ are 128 bytes and 40 bytes respectively. Additionally, according to He et al. [26], the size of a common timestamp is 4 bytes, the output of a one-way hash function is 20 bytes, and the size of $\mathbb{Z}_p^*$ is 20 bytes.
In literature [21], the message sent by the vehicle is $\{PID_i, R_i, m_i, T_i, \sigma_i\}$, where $\{PID_i, R_i\} \in G_1$, $\{\sigma_i, m_i\} \in \mathbb{Z}_p^*$, $T_i$ is the timestamp. The total communication overhead is $2|G_1| + 2|\mathbb{Z}_p^*| + |T_i| = 2 \times 128 + 2 \times 20 + 4 = 428$ bytes.
In literature [22], the message sent by the vehicle is $\{PID_j, K_1, K_v, m, R_1, R_b, \sigma, \delta_j\}$, where $\{K_1, K_v, R_1, R_b, \sigma\} \in G_1$, $\{\delta_j, m\} \in \mathbb{Z}_p^*$, $TS_{V_j}$ is the timestamp. The total communication overhead is $5|G_1| + 2|\mathbb{Z}_p^*| + |T| = 5 \times 128 + 2 \times 20 + 4 = 684$ bytes.
In literature [23], the message sent by the vehicle is $\{S_{k1}, S_{k2}, m_k, L_k, N_k, T_k, W_k, Z_k, \sigma_k\}$, where $\{S_{k1}, S_{k2}, L_k, N_k, T_k, W_k, Z_k\} \in G_1$, $\{\sigma_k, m_k\} \in \mathbb{Z}_p^*$. The total communication overhead is $7|G_1| + 2|\mathbb{Z}_p^*| = 7 \times 128 + 2 \times 20 = 916$ bytes.
In literature [24], the message sent by the user is $\{PID_{i,j}, R_{i,j}, U_{i,j}, M_i, T_i, \sigma_i, \delta_{i,j}\}$, where $\{PID_{i,j}, R_{i,j}, U_{i,j}\} \in G_1$, $\{\delta_{i,j}, M_i\} \in \mathbb{Z}_p^*$, $T_i$ is the timestamp. The total communication overhead is $3|G_1| + 2|\mathbb{Z}_p^*| + |T| = 3 \times 128 + 2 \times 20 + 4 = 428$ bytes.
In this scheme, the message sent by the UAV is $\{PID_i, vpk_{PID_i}, T_i, \sigma_i, Tpk_{UE_i}\}$, where $\{PID_i, vpk_{PID_i}, Tpk_{UE_i}\} \in G_1$, $\{\sigma_i\} \in \mathbb{Z}_p^*$. Therefore, the communication overhead of this scheme is $3|G_1| + |\mathbb{Z}_p^*| + |T| = 3 \times 128 + 20 + 4 = 408$ bytes.
The communication overhead comparison of all schemes is shown in Table 2. Compared with the optimal comparative scheme, the proposed scheme reduces the communication overhead by 4%. The comparison shows that the proposed scheme has better performance in terms of communication overhead.
| Scheme | Message | Communication Cost (bytes) |
|---|---|---|
| Yan et al. [21] | $\{PID_i, R_i, m_i, T_i, \sigma_i\}$ | 428 |
| Maurya et al. [22] | $\{PID_j, K_1, K_v, m, R_1, R_b, \sigma, \delta_j\}$ | 684 |
| Dwivedi et al. [23] | $\{S_{k1}, S_{k2}, m_k, L_k, N_k, T_k, W_k, Z_k, \sigma_k\}$ | 916 |
| Cui et al. [24] | $\{PID_{i,j}, R_{i,j}, U_{i,j}, M_i, T_i, \sigma_i, \delta_{i,j}\}$ | 428 |
| Proposed Scheme | $\{PID_i, vpk_{PID_i}, T_i, \sigma_i, Tpk_{UE_i}\}$ | 408 |
Error Detection Times Comparison
This section will compare the proposed scheme, the literature [12] based on d-disjoint matrices, and the traditional literature [24] based on binary search, in terms of the number of detections required to detect erroneous access authentication requests when receiving $n$ access authentication requests and there are at most $d$ invalid access authentication requests, and when batch authentication fails.
In the traditional scheme based on binary search [24], the error detection complexity is $O(d \log_2(n))$. The error detection method proposed in scheme [12] based on d-disjoint matrices has an error detection complexity of $O(d^2 \log_2(n))$. The proposed scheme based on $(d, d)$-separable matrices has an error detection complexity of $O(d \log_2(n))$. Although the traditional scheme based on binary search requires fewer error detection times, the error detection method based on binary search cannot run in parallel and can only aggregate sequentially according to the binary search method, verifying aggregate signatures one by one, resulting in long error detection times. The comparison of error detection times is shown in Figure 6, comparing the error detection complexity of the three schemes under $d=2$, $d=5$, and $d=10$ respectively. Among them, $d=2$ considers the scenario where the scheme is applied in a secure communication environment, where there are few illegal users, so the maximum number of invalid access authentication requests is set to 2. $d=5$ considers the scenario where the scheme is applied in a general communication environment, where there are a certain number of illegal users, so the maximum number of invalid access authentication requests is set to 5. $d=10$ considers the scenario where the scheme is applied in a dangerous communication environment, where there are many illegal users, so the maximum number of invalid access authentication requests is set to 10. By setting $d$ to 2, 5, and 10 respectively, the application of the proposed scheme in different communication environments is considered. As can be seen from Figure 6, the proposed scheme has the lowest error detection complexity in all three cases. Through comparison, it is concluded that this scheme has the lowest error detection complexity, the highest authentication efficiency, and the best performance.
Conclusion
This article addresses the issues of poor fault tolerance and insufficient error detection capabilities in traditional batch authentication protocols in UAV networks under multi-user high-concurrency access scenarios, proposing an efficient batch authentication and key agreement protocol that combines CLAS with group testing. On one hand, the scheme constructs a CLAS batch authentication protocol that supports concurrent access and rapid signature verification, reducing the system’s computational and communication overhead. On the other hand, it introduces a group testing-based efficient error detection mechanism that can quickly identify invalid requests in authentication failure scenarios, avoiding the rejection of valid requests, and improving overall authentication success rate and system robustness. In terms of security, this article conducts informal security analysis of the proposed scheme, provides security proofs under the random oracle model, and performs formal verification under Tamarin, demonstrating the security of the proposed scheme. In performance evaluation, comparison with existing mainstream schemes shows that the proposed scheme exhibits better performance in terms of computational overhead, communication cost, and error detection complexity. The proposed scheme ensures authentication security while balancing system overhead and fault tolerance capability, providing an efficient and secure solution for UE concurrent access authentication in resource-constrained UAV networks.