With the rapid advancement of drone technology, Unmanned Aerial Vehicle (UAV) networks have been widely deployed in critical fields such as logistics, crop monitoring, remote sensing, and disaster management. UAVs serve as aerial relay nodes, facilitating efficient communication for ground User Equipment (UE) clusters. The proliferation of 5G and future network environments further expands the application boundaries of UAV networks. However, due to their inherent high dynamics, resource-constrained nodes, and unstable communication links, UAV networks face numerous challenges in communication security and efficiency. For instance, when multiple UEs simultaneously initiate access authentication requests to a UAV, the computational load on the UAV increases significantly. Additionally, the system is 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 to achieve rapid mutual authentication and key agreement between UAVs and UEs.
Existing batch authentication protocols generally lack fault tolerance. If any invalid authentication information is present in the access requests, it often leads to the failure of the entire batch authentication, thereby reducing overall authentication efficiency. Some improved schemes that introduce error detection mechanisms face practical challenges, such as difficulty in accurately locating invalid signatures, complex error detection processes, and high resource consumption, which cannot meet the dual requirements of high real-time performance and reliability in UAV networks. Furthermore, current mainstream authentication systems, such as those based on Public Key Infrastructure (PKI) and Identity-Based Signature (IBS), still have structural defects like cumbersome certificate management or key escrow risks, limiting their adaptability and scalability in dynamic heterogeneous environments. Certificateless Signature (CLS)-based authentication systems primarily address point-to-point communication and struggle to handle high-concurrency scenarios where UE clusters simultaneously access UAV networks.
To address these issues, this paper 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, not only avoiding the certificate management problems of traditional PKI systems but also aggregating multiple signatures into a short signature, significantly reducing verification overhead, which is particularly suitable for resource-constrained UAV scenarios. To enhance the fault tolerance of the protocol, a group testing-based error detection mechanism is designed to quickly detect and locate invalid access authentication requests when batch authentication fails, avoiding the rejection of valid requests and improving overall authentication efficiency and system robustness.
The main contributions of this paper are as follows: (1) Design of an efficient batch authentication mechanism: Based on CLAS technology, a batch authentication protocol that supports concurrent access and does not require bilinear pairing operations is constructed, significantly reducing UAV computational overhead and improving authentication efficiency. (2) Proposal of a rapid error detection mechanism: Introducing the concept of group testing, a method for detecting invalid requests with high localization accuracy and low resource overhead is designed, effectively solving the problems of inaccurate identification of erroneous requests and excessive error detection times in traditional schemes, significantly improving the success rate of batch authentication and system stability.
The remainder of this paper is organized as follows: Section 2 reviews related work, including batch authentication schemes and error-detecting batch authentication schemes. Section 3 outlines the system model, security model, and security requirements of the scheme. Section 4 details the proposed scheme. Section 5 provides security analysis and proofs. Section 6 conducts performance analysis. Finally, Section 7 concludes the paper.
Related Work
In recent years, to address the growing communication security needs in UAV networks, extensive research has focused on the design of identity authentication mechanisms and batch authentication protocols. Existing research 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 mainly include security authentication mechanisms based on PKI, IBS, and CLS. PKI binds public keys to identities through digital certificates and has a mature key management system, widely used in UAV communication environments. 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, which uses PKI to achieve 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, resulting in high deployment costs in highly dynamic UAV networks. To address certificate management issues and improve the deployment efficiency of authentication systems in dynamic networks, researchers proposed IBS-based schemes. This method generates public keys using users’ unique identity information, avoiding the complex certificate distribution and revocation operations in traditional PKI systems. Jan et al. proposed an authentication protocol that integrates 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 solve the certificate management issues in PKI schemes and the key escrow problem in IBS schemes, researchers proposed CLS schemes. The CLS system splits the private key into a user-private part and a part generated by the Key Generation Center (KGC), eliminating the reliance on certificates while avoiding the key escrow risk in traditional IBS schemes, making it an important authentication mechanism in UAV communication environments in recent years. Semal et al. proposed a CLS-based group authentication and key agreement protocol for untrusted UAV networks. This scheme supports bidirectional authentication with low computational overhead and high security in resource-constrained, heterogeneous UAV environments. Li et al. further proposed a lightweight CLS authentication protocol without bilinear pairing operations, significantly improving the authentication efficiency and deployability of UAV networks through pairing-free structures. Although CLS-based schemes achieve a good balance between authentication efficiency and key security, these schemes primarily focus on point-to-point authentication scenarios and struggle to support high-concurrency environments where UE clusters simultaneously access UAVs, limiting their practical efficiency.
To adapt to high-concurrency environments where UE clusters simultaneously access UAVs, researchers combined CLS with aggregate signature technology to propose the CLAS mechanism. Priyanka et al. proposed a CLAS-based batch authentication scheme for vehicular ad-hoc networks. Samra et al. proposed a conditional privacy-preserving authentication scheme for vehicular ad-hoc networks 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. proposed a conditional privacy-preserving scheme based on elliptic curve cryptography for vehicular ad-hoc networks using CLAS without bilinear pairings, achieving batch authentication. However, these CLAS schemes, while enabling efficient batch authentication, generally overlook the identification of invalid requests after authentication failure. They lack the ability to identify and locate invalid requests in authentication failure scenarios. If a single invalid request exists, the entire batch must be re-authenticated, leading to significant resource waste and limiting the protocol’s effectiveness in practical high-density concurrent access scenarios. Therefore, introducing fault tolerance mechanisms and efficient error detection capabilities within the CLAS framework has become a key direction for further research.
Addressing the fault tolerance issue in batch authentication, existing research has attempted to introduce 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, has high computational load, and limits the maximum number of faulty signatures. Thais et al. proposed an unbounded fault-tolerant aggregate signature scheme based on nested uncovered families, which has no limit on the number of faulty signatures. However, during error detection, the process is complex and requires many detection attempts. In terms of introducing fault tolerance thresholds, Wang et al. proposed a CLS-based authentication scheme combined with a fuzzy batch verification mechanism for UAV networks, introducing fault tolerance properties to improve authentication efficiency. However, this scheme cannot detect invalid signatures. Based on the above related work, it can be seen that existing fault-tolerant batch authentication schemes still have room for improvement in error identification efficiency, computational complexity, and practical deployment capability, especially lacking lightweight error detection mechanisms suitable for resource-constrained UAV network scenarios.
This paper combines CLAS with group testing to design a batch authentication and key agreement protocol that supports rapid error localization. This scheme not only improves overall authentication efficiency but also significantly reduces the computational and communication overhead of UAVs when handling invalid requests, enhancing the practicality of the protocol.
System Model and Problem Description
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 as follows.
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 legitimate identity of the UAV. During system establishment, UEs must send their real identities to the CC for registration and participate in authentication using pseudonyms during communication to ensure anonymity. UAVs are responsible for receiving access requests from multiple UEs, aggregating multiple authentication requests, using the CLAS mechanism 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 uses the CLAS mechanism for aggregate signature authentication. Simultaneously, to effectively address the batch authentication failure caused by illegal UE access, the system introduces a group testing-based error detection mechanism, ensuring authentication efficiency while maintaining security and fault tolerance.
Security Model
To systematically evaluate the security of the protocol 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 (Adv1): 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 (Adv2): 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: The attacker Adv can access the following five oracles. Reveal Partial Private Key Oracle: Upon receiving Adv’s query, the challenger ζ takes PIDi as input, computes psk_{PIDi}, and sends it to Adv. Create User Oracle: Upon receiving Adv’s query, the challenger ζ takes PIDi as input, computes vpk_{PIDi}, and sends it to Adv. Reveal Private Key Oracle: Upon receiving Adv’s query, the challenger ζ takes PIDi as input, computes vsk_{PIDi}, and sends it to Adv. Replace Public Key Oracle: Adv inputs PIDi and vpk’_{PIDi}, replacing the current public key vpk_{PIDi} with the desired public key vpk’_{PIDi}. Signature Oracle: Upon receiving Adv’s query, the oracle returns a valid signature σ based on PIDi, vpk_{PIDi}, and message m.
Security Definitions: The unforgeability of the scheme is defined through two games defined between the challenger ζ and the attacker Adv. Game 1 is conducted between the challenger ζ and the attacker Adv1. Initialization Phase: In the initialization phase, the challenger ζ runs the setup algorithm to obtain parameters, secret value s, and master public key. Then, the challenger ζ sends the parameters and master public key to the attacker Adv1 and retains the secret value s. Query Phase: In the query phase, Adv1 queries the Reveal Partial Private Key Oracle, Create User Oracle, Reveal Private Key Oracle, Replace Public Key Oracle, and Signature Oracle. Forgery Phase: Finally, Adv1 outputs a signature σ* corresponding to message m*, PIDi*, and vpk_{PIDi*}. Adv1 wins this game if: (a) σ* is a valid signature; (b) PIDi* 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 Adv1 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 ζ and Adv2. Initialization Phase: The challenger ζ 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 Adv2. Query Phase: Adv2 queries the Create User Oracle, Reveal Private Key Oracle, and Signature Oracle. Forgery Phase: Finally, Adv2 outputs a signature σ* corresponding to message m*, PIDi*, and vpk_{PIDi*}. Adv2 wins this game if: (a) σ* is a valid signature; (b) PIDi* 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 Adv2 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 goals. The specific security goals are as follows: Message Authenticity: After receiving a signed message, the receiver can confirm the legitimacy and integrity of the message 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 that requires holding someone accountable, 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 purposes, 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, generate an elliptic curve E: y^2 = x^3 + ax + b mod p, where a, b ∈ Z_p* and 4a^3 + 27b^2 ≠ 0 mod p. The CC selects a point P at infinity as the base point of the elliptic curve. The KGC selects a random number s ∈ Z_p* as the master private key and computes the master public key P_pub = s · P. The CC selects a random number b ∈ Z_p* as the master private key and computes the master public key T_pub = b · P. Additionally, the KGC generates a public-private key pair for the UAV. The KGC and CC select three hash functions H1, H2, H3: {0,1}* → Z_p*. The KGC randomly selects q_UAV ∈ Z_p*, computes pk_UAV = q_UAV · P as the UAV’s public key, and computes sk_UAV = (ID_UAV || pk_UAV) · h1 · s as the UAV’s private key, where h1 = H1(ID_UAV, pk_UAV). UEs send their real identities RIDi to the CC for registration. Finally, the CC and KGC publish the system parameters {P, p, q, E, G, H1, H2, H3, P_pub, T_pub, pk_UAV}.
Pseudonym and Partial Private Key Generation
In this phase, the CC generates pseudonyms for UEs, and the KGC generates partial private keys for UEs. First, the UE randomly selects t_i and computes PID_i1 = t_i · P, Key_i = RID_i ⊕ t_i · T_pub, and sends the pseudonym request message {PID_i1, Key_i} to the CC. After receiving the pseudonym request message, the CC first computes Key_i ⊕ PID_i1 · b to verify the UE’s legitimate identity. After verification, the CC computes the pseudonym PID_i2 = H1(RID_i || PID_i1, b · T_pub), and the pseudonym set PID_i = {PID_i1, PID_i2, ΔT_i}, where ΔT_i is the validity period of the pseudonym. The CC sends PID_i to the KGC via a secure channel. After receiving it, the KGC randomly selects r_i, computes R_i = r_i · P, and computes the partial private key psk_{PIDi} = (r_i + s · K_i) mod p, where K_i = H1(PID_i, R_i, P_pub). The KGC sends {psk_{PIDi}, R_i, PID_i} to the UE. After receiving it, the UE verifies psk_{PIDi} · P = R_i + K_i · P_pub to verify the integrity and validity of the message.
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 · P, Q_i = R_i + H2(PID_i, X_i) · X_i. The UE’s public key is vpk_{PIDi} = (Q_i, R_i), and the private key is vsk_{PIDi} = (psk_{PIDi}, 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 to send to the UAV. After receiving the request, the UAV verifies the validity of the pseudonym and timestamp, and then verifies the legitimacy of the UE’s identity based on the signature information. After authentication is passed, 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. Finally, both parties complete mutual authentication and key agreement.
First, the UE sends an access authentication request message to the UAV. The UE selects a random number Tsk_{UEi} as the temporary private key and computes the temporary public key Tpk_{UEi} = Tsk_{UEi} · P. The UE randomly selects u_i, computes U_i = u_i · P, h2_i = H2(PID_i, X_i), h3_i = H3(PID_i, M_i, vpk_{PIDi}, U_i, T_i), S_i = (Tsk_{UEi} + u_i + h3_i · (psk_{PIDi} + h2_i · x_i)) mod q, and σ_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_{PIDi}, M_i, T_i, Tpk_{UEi}, σ_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 = H1(PID_i, R_i, P_pub), h3_i = H3(PID_i, M_i, vpk_{PIDi}, U_i, T_i), and verifies S_i · P = Tpk_{UEi} + U_i + h3_i · (Q_i + K_i · P_pub) to determine the UE’s legitimate identity. If verification fails, the authentication process is terminated. After verification, the UAV generates a random number Tsk_UAV as the temporary private key and computes the temporary public key Tpk_UAV = Tsk_UAV · P. The UAV computes the session key with the UE as SK_{UAV-UEi} = Tsk_UAV · Tpk_{UEi}. The UAV computes h2_UAV = H2(ID_UAV, Tpk_UAV, T_UAV), v_UAV = Tsk_UAV + h2_UAV · 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 = H1(PID_i, R_i, P_pub), h3_i = H3(PID_i, M_i, vpk_{PIDi}, U_i, T_i), and using the system parameters P_pub = s · P, the UE’s temporary public key Tpk_{UEi} = Tsk_{UEi} · P, the random number U_i = u_i · P generated by the UE, and the UE’s public key vpk_{PIDi} = (Q_i, R_i), the UE’s legitimate identity is verified. From psk_{PIDi} = r_i + s · K_i, Q_i = R_i + H2(PID_i, X_i) · X_i, and X_i = x_i · P, we have:
$$S_i \cdot P = (Tsk_{UEi} + u_i + h3_i \cdot (psk_{PIDi} + h2_i \cdot x_i)) \cdot P = Tpk_{UEi} + U_i + h3_i \cdot (R_i + K_i \cdot P_{pub} + h2_i \cdot X_i) = Tpk_{UEi} + U_i + h3_i \cdot (Q_i + K_i \cdot P_{pub})$$
If the equation holds, it indicates that the UE is a legitimate user, and authentication passes; otherwise, the UE is an illegal user, and authentication fails.
After receiving the access authentication response message, the UE first verifies the timestamp T_UAV. Then, it computes h1_UAV = H1(ID_UAV, pk_UAV), h2_UAV = H2(ID_UAV, Tpk_UAV, T_UAV), and verifies the equation v_UAV · P = Tpk_UAV + h2_UAV · pk_UAV + h1_UAV · H1(ID_UAV, pk_UAV) · 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 as SK_{UAV-UEi} = Tsk_{UEi} · Tpk_UAV. At this point, the single UE has completed access authentication and established a session key with the UAV.
Correctness Analysis: In the UE’s authentication process of the UAV, by computing h1_UAV = H1(ID_UAV, pk_UAV), h2_UAV = H2(ID_UAV, Tpk_UAV, T_UAV), and using the system parameters P_pub = s · P, the UAV’s temporary public key Tpk_UAV = Tsk_UAV · P, and the UAV’s public key pk_UAV = q_UAV · P, the UAV’s legitimate identity is verified. From sk_UAV = (ID_UAV || pk_UAV) · h1_UAV · s, we have:
$$v_{UAV} \cdot P = (Tsk_{UAV} + h2_{UAV} \cdot sk_{UAV}) \cdot P = Tpk_{UAV} + h2_{UAV} \cdot (q_{UAV} \cdot P + h1_{UAV} \cdot s \cdot P) = Tpk_{UAV} + h2_{UAV} \cdot pk_{UAV} + h1_{UAV} \cdot H1(ID_{UAV}, pk_{UAV}) \cdot P_{pub}$$
If the equation holds, it indicates that the UAV is legitimate, and authentication passes; otherwise, the UAV is illegal, and authentication fails.
Batch Authentication and Key Agreement Phase
When the UAV receives access authentication requests from multiple UEs, it performs batch authentication on these access authentication requests. When the UAV receives n access authentication requests {PID_i, vpk_{PIDi}, M_i, T_i, Tpk_{UEi}, σ_i} from UE1, UE2, …, UEn, it first verifies that each pseudonym PID_i is within the validity period and verifies each timestamp T_i, computes K_i = H1(PID_i, R_i, P_pub), h3_i = H3(PID_i, M_i, vpk_{PIDi}, U_i, T_i). Then, it aggregates these access authentication request messages by computing S = Σ_{i=1}^n S_i. The aggregate signature is σ_agg = (U_1, U_2, …, U_n, S). The UAV performs batch authentication by verifying the equation S · P = Σ_{i=1}^n Tpk_{UEi} + Σ_{i=1}^n U_i + Σ_{i=1}^n h3_i · (Q_i + K_i · P_pub). If authentication fails, it indicates that there are illegal users in the UE cluster, and the UAV will proceed to batch authentication error detection. After authentication is passed, 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 · P. The UAV computes the session key with each UE as SK_{UAV-UEi} = Tsk_UAV · Tpk_{UEi}. Then, the UAV computes h2_UAV = H2(ID_UAV, Tpk_UAV, T_UAV), v_UAV = Tsk_UAV + h2_UAV · 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 h1_UAV = H1(ID_UAV, pk_UAV), h2_UAV = H2(ID_UAV, Tpk_UAV, T_UAV), and verifies the equation v_UAV · P = Tpk_UAV + h2_UAV · pk_UAV + h1_UAV · H1(ID_UAV, pk_UAV) · 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 as SK_{UAV-UEi} = Tsk_{UEi} · Tpk_UAV. At this point, the UAV has completed batch authentication for the UEs and established session keys with each authenticated UE.
Correctness Analysis: In the UAV’s verification process of the aggregate signature σ_agg = (U_1, U_2, …, U_n, S), by computing K_i = H1(PID_i, R_i, P_pub), h3_i = H3(PID_i, M_i, vpk_{PIDi}, U_i, T_i), and using the system parameters P_pub = s · P, each UE’s temporary public key Tpk_{UEi} = Tsk_{UEi} · P, the random number U_i = u_i · P generated by each UE, and each UE’s public key vpk_{PIDi} = (Q_i, R_i), the validity of the aggregate signature is verified. From psk_{PIDi} = r_i + s · K_i, Q_i = R_i + H2(PID_i, X_i) · X_i, and X_i = x_i · P, we have:
$$h3_i \cdot (psk_{PIDi} + h2_i \cdot x_i) \cdot P = h3_i \cdot (r_i \cdot P + s \cdot K_i \cdot P + h2_i \cdot x_i \cdot P) = h3_i \cdot (R_i + K_i \cdot P_{pub} + h2_i \cdot X_i) = h3_i \cdot (Q_i + K_i \cdot P_{pub})$$
Thus:
$$S \cdot P = \sum_{i=1}^n S_i \cdot P = \sum_{i=1}^n (Tpk_{UEi} + U_i + h3_i \cdot (Q_i + K_i \cdot P_{pub})) = \sum_{i=1}^n Tpk_{UEi} + \sum_{i=1}^n U_i + \sum_{i=1}^n h3_i \cdot (Q_i + K_i \cdot P_{pub})$$
If the equation holds, it indicates that every UE is a legitimate user, and batch authentication passes; otherwise, there are illegal users in the UE cluster, batch authentication fails, and the UAV will proceed to batch authentication error detection.
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 × n matrix, where t is a multiple of d. For each column of matrix M, arbitrarily select t/d rows, set their corresponding values to 1, and set the remaining rows to 0 to construct matrix M. When t ≥ 2d log(e n / d) + log n, the matrix constructed by the above method is (d, d-)-separable.
Then, perform a two-phase 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 phase, these signatures are aggregated into 2t signatures for verification, obtaining 2d potentially invalid signatures. In the second phase, 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 analyzed for non-formal security, proven to be unforgeable under the random oracle model, and formally verified using Tamarin.
Non-Formal Security Analysis
This section analyzes the security goals satisfied by the proposed scheme from the perspective of UAV network security requirements using non-formal methods.
Message Authenticity: In the scheme, before the UE sends the access authentication request message to the UAV, it must be signed with S_i. The UAV verifies whether the message comes from a legitimate UE and whether it has been tampered with or forged by malicious attackers by verifying S_i · P = Tpk_{UEi} + U_i + h3_i · (Q_i + K_i · P_pub). Before the UAV sends the access authentication response message to the UE, it must be signed with v_UAV. The UE verifies whether the message comes from a legitimate UAV and whether it has been tampered with or forged by malicious attackers by verifying v_UAV · P = Tpk_UAV + h2_UAV · pk_UAV + h1_UAV · H1(ID_UAV, pk_UAV) · P_pub.
Conditional Identity Privacy: In the scheme, the UE uses the pseudonym PID_i = {PID_i1, PID_i2, ΔT_i} for communication. Attackers cannot obtain the UE’s real identity from the pseudonym.
Traceability: In the scheme, when a dispute arises, the CC can compute RID_i = H1(PID_i2, PID_i1, b · T_pub) from the pseudonym PID_i = {PID_i1, PID_i2, ΔT_i} to obtain the UE’s real identity, where b is the CC’s private key. Therefore, the scheme has traceability.
Unlinkability: In the scheme, the UE sends {PID_i, vpk_{PIDi}, M_i, T_i, Tpk_{UEi}, σ_i} to the UAV. Since the signature σ_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. The message receiver verifies the timestamp to detect the freshness of the message, resisting replay attacks. Forgery Attack: In the scheme, before the UE sends the access authentication request message to the UAV, it must be signed with S_i. Before the UAV sends the access authentication response message to the UE, it must be signed with v_UAV. Therefore, it can detect whether the message comes 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. 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 Adv1 and Adv2 defined in Chapter 3, this section proves the security of the proposed scheme through games between the challenger ζ and the attackers Adv1 and Adv2.
Theorem 1: Under the random oracle model, assuming the Elliptic Curve Discrete Logarithm Problem (ECDLP) is hard, then this scheme is secure under adaptive chosen message attacks, chosen identity attacks, and public key replacement attacks by Type I attacker Adv1.
Proof: Assume an attacker Adv1 can forge a message {PID_i, vpk_{PIDi}, M_i, T_i, Tpk_{UEi}, σ_i} with σ_i = (U_i, S_i). By constructing a challenger ζ that runs the subroutine Adv1 with a non-negligible probability to solve ECDLP. Given an ECDLP instance (P, Q = s · P), the challenger ζ will simulate oracles and play the following game with attacker Adv1.
System Initialization Phase: The challenger ζ executes the system initialization program, randomly selects s ∈ Z_p*, computes P_pub = s · P. Set P_pub = Q, generate system public parameters {P, p, q, E, G, H1, H2, H3, P_pub, T_pub}, and send the parameters to attacker Adv1.
H3 Query: The challenger ζ maintains a list L_H3, initially empty, with element type {PID_i, M_i, T_i, h3_i}. When attacker Adv1 requests a query about PID_i, the challenger ζ checks if L_H3 contains {PID_i, M_i, T_i, h3_i}. If it exists, the challenger ζ returns h3_i. If not, the challenger ζ selects a random value h3_i ∈ Z_p* as the response and stores {PID_i, M_i, T_i, h3_i} in L_H3.
User Creation: The challenger ζ maintains a list L_PK, initially empty, with element type {PID_i, psk_{PIDi}, vpk_{PIDi}, vsk_{PIDi}}. When attacker Adv1 requests a query about PID_i, the challenger ζ checks if L_PK contains {PID_i, psk_{PIDi}, vpk_{PIDi}, vsk_{PIDi}}. If it exists, the challenger ζ returns vpk_{PIDi}. If not, perform the following operations: The challenger ζ randomly selects r_i, b_i, x_i ∈ Z_p*, sets R_i = r_i · P + b_i · P, K_i = -r_i mod q, psk_{PIDi} = b_i, vsk_{PIDi} = x_i, vpk_{PIDi} = x_i · P. The equation psk_{PIDi} · P = R_i + K_i · P_pub holds. Store {PID_i, psk_{PIDi}, vpk_{PIDi}, vsk_{PIDi}} in L_PK and return vpk_{PIDi} to Adv1.
Partial Private Key: When attacker Adv1 requests a partial private key query about PID_i, the challenger ζ checks if L_PK contains {PID_i, psk_{PIDi}, vpk_{PIDi}, vsk_{PIDi}}. If it exists, the challenger ζ returns psk_{PIDi}. If not, the challenger ζ returns ⊥.
User Private Key: When attacker Adv1 requests a private key query about PID_i, the challenger ζ checks if L_PK contains {PID_i, psk_{PIDi}, vpk_{PIDi}, vsk_{PIDi}}. If it exists, the challenger ζ returns vsk_{PIDi}. If not, the challenger ζ returns ⊥.
User Public Key Replacement: When attacker Adv1 requests a public key replacement query about PID_i, the challenger ζ checks if L_PK contains {PID_i, psk_{PIDi}, vpk_{PIDi}, vsk_{PIDi}}. If it exists, the challenger ζ updates vpk_{PIDi} to vpk’_{PIDi}.
Signature Query: When attacker Adv1 requests a signature query about PID_i, the challenger ζ computes S_i such that S_i · P = Tpk_{UEi} + U_i + h3_i · (Q_i + K_i · P_pub), and returns S_i to attacker Adv1.
Output: Finally, attacker Adv1 outputs {PID_i*, vpk_{PIDi*}, M_i*, T_i*, Tpk_{UEi*}, σ_i*} with σ_i* = (U_i*, S_i*). It satisfies S_i* · P = Tpk_{UEi*} + U_i* + h3_i* · (Q_i* + K_i* · P_pub). Attacker Adv1 replays the above process to forge another valid message {PID_i*, vpk_{PIDi*}, M_i*, T_i*, Tpk_{UEi*}, σ_i*} with σ_i* = (U_i*, S_i*), satisfying S_i* · P = Tpk_{UEi*} + U_i* + h3_i* · (Q_i* + K_i* · P_pub). According to these two equations, we have:
$$(S_i^* – S_i) \cdot P = (h3_i^* – h3_i) \cdot (K_i^* – K_i) \cdot P_{pub} = (h3_i^* – h3_i) \cdot (K_i^* – K_i) \cdot s \cdot P$$
Thus:
$$S_i^* – S_i = (h3_i^* – h3_i) \cdot (K_i^* – K_i) \cdot s$$
The challenger ζ outputs s = (S_i^* – S_i) / ((h3_i^* – h3_i) · (K_i^* – K_i)) to solve the given ECDLP instance; otherwise, the game fails.
Therefore, under the random oracle model and ECDLP assumption, this scheme is secure under attacks by Type I attacker Adv1.
Theorem 2: Under the random oracle model, assuming ECDLP is hard, then this scheme is secure under adaptive chosen message attacks and chosen identity attacks by Type II attacker Adv2.
Proof: Assume an attacker Adv2 can forge a message {PID_i, vpk_{PIDi}, M_i, T_i, Tpk_{UEi}, σ_i} with σ_i = (U_i, S_i). By constructing a challenger ζ that runs the subroutine Adv2 with a non-negligible probability to solve ECDLP. Given an ECDLP instance (P, Q = x · P), the challenger ζ will simulate oracles and play the following game with attacker Adv2.
System Initialization Phase: The challenger ζ executes the system initialization program, randomly selects s ∈ Z_p*, computes P_pub = s · P. Set P_pub = Q, generate system public parameters {P, p, q, E, G, H1, H2, H3, P_pub, T_pub}, and send the public parameters and s to attacker Adv2.
H2 Query: The challenger ζ maintains a list L_H2, initially empty, with element type {PID_i, M_i, T_i, h2_i}. When attacker Adv2 requests a query about PID_i, the challenger ζ checks if L_H2 contains {PID_i, M_i, T_i, h2_i}. If it exists, the challenger ζ returns h2_i. If not, the challenger ζ selects a random value h2_i ∈ Z_p* as the response and stores {PID_i, M_i, T_i, h2_i} in L_H2.
H3 Query: The challenger ζ maintains a list L_H3, initially empty, with element type {PID_i, M_i, T_i, h3_i}. When attacker Adv2 requests a query about PID_i, the challenger ζ checks if L_H3 contains {PID_i, M_i, T_i, h3_i}. If it exists, the challenger ζ returns h3_i. If not, the challenger ζ selects a random value h3_i ∈ Z_p* as the response and stores {PID_i, M_i, T_i, h3_i} in L_H3.
User Creation: The challenger ζ maintains a list L_PK, initially empty, with element type {PID_i, psk_{PIDi}, vpk_{PIDi}, vsk_{PIDi}}. When attacker Adv2 requests a query about PID_i, the challenger ζ checks if L_PK contains {PID_i, psk_{PIDi}, vpk_{PIDi}, vsk_{PIDi}}. If it exists, the challenger ζ returns vpk_{PIDi}. If not, perform the following operations: The challenger ζ randomly selects r_i, x_i ∈ Z_p*, sets R_i = r_i · P, K_i = H1(PID_i, R_i, P_pub), psk_{PIDi} = (r_i + s · K_i) mod q, vsk_{PIDi} = ⊥, vpk_{PIDi} = x_i · P = x_i · Q. The equation psk_{PIDi} · P = R_i + K_i · P_pub holds. Store {PID_i, psk_{PIDi}, vpk_{PIDi}, vsk_{PIDi}} in L_PK and return vpk_{PIDi} to Adv2.
Partial Private Key: When attacker Adv2 requests a partial private key query about PID_i, the challenger ζ checks if L_PK contains {PID_i, psk_{PIDi}, vpk_{PIDi}, vsk_{PIDi}}. If it exists, the challenger ζ returns psk_{PIDi}. If not, the challenger ζ performs a user creation query and returns psk_{PIDi}.
User Private Key: When attacker Adv2 requests a private key query about PID_i, the challenger ζ checks if L_PK contains {PID_i, psk_{PIDi}, vpk_{PIDi}, vsk_{PIDi}}. If it exists, the challenger ζ returns vsk_{PIDi}. If not, the challenger ζ returns ⊥.
Signature Query: When attacker Adv2 requests a signature query about PID_i, the challenger ζ computes S_i such that S_i · P = Tpk_{UEi} + U_i + h3_i · (Q_i + K_i · P_pub), and returns S_i to attacker Adv2.
Output: Finally, attacker Adv2 outputs {PID_i*, vpk_{PIDi*}, M_i*, T_i*, Tpk_{UEi*}, σ_i*} with σ_i* = (U_i*, S_i*). It satisfies S_i* · P = Tpk_{UEi*} + U_i* + h3_i* · psk_{PIDi*} · P + h3_i* · h2_i* · x_i* · P. Attacker Adv2 replays the above process to forge another valid message {PID_i*, vpk_{PIDi*}, M_i*, T_i*, Tpk_{UEi*}, σ_i*} with σ_i* = (U_i*, S_i*), satisfying S_i* · P = Tpk_{UEi*} + U_i* + h3_i* · psk_{PIDi*} · P + h3_i* · h2_i* · x_i* · P. According to these two equations, we have:
$$(S_i^* – S_i) \cdot P = (h3_i^* – h3_i) \cdot (h2_i^* \cdot x_i^* – h2_i \cdot x_i) \cdot P = (h3_i^* – h3_i) \cdot (h2_i^* \cdot x_i^* – h2_i \cdot x_i) \cdot x \cdot P$$
Thus:
$$S_i^* – S_i = (h3_i^* – h3_i) \cdot (h2_i^* \cdot x_i^* – h2_i \cdot x_i) \cdot x$$
The challenger ζ outputs x = (S_i^* – S_i) / ((h3_i^* – h3_i) · (h2_i^* · x_i^* – h2_i · x_i)) to solve the given ECDLP instance; otherwise, the game fails.
Therefore, under the random oracle model and ECDLP assumption, this scheme is secure under attacks by Type II attacker Adv2.
Formal Verification
In this section, the formal verification tool Tamarin is used to perform formal analysis on 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 that need 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 Setup rule represents the system setup phase, generating system parameters for the system, UE, and UAV. The UE_1 rule represents the process where the UE generates and sends an access authentication request. The UAV_1 rule 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 UE_2 rule 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 figure below. During the formal verification, 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.
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 pairs, use bilinear pair e: G1 × G1 → G2 to achieve 80-bit security strength, where G1 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 q.
For schemes based on elliptic curve cryptography, use the 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, q are two 160-bit primes, a, b ∈ 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 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 paper uses 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, 16GB memory, 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 3T_BPM + 3T_H + T_BPA + 2T_s = 3×1.7975 + 3×0.0001 + 0.0099 + 2×0.442 = 5.3925 + 0.0003 + 0.0099 + 0.884 = 6.2867 ms. The verifier verifying a single signature needs to perform 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 = 5×1.7975 + 3×0.0001 + 0.0099 = 8.9875 + 0.0003 + 0.0099 = 8.9977 ms. The verifier verifying n signatures needs to perform 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 = (2n+1)×1.7975 + 2n×0.0099 + n×0.442 + 2n×0.0001 = (3.595n + 1.7975) + 0.0198n + 0.442n + 0.0002n = 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 = 2×1.7975 + 0.0099 + 3×0.0001 + 3×0.442 = 3.595 + 0.0099 + 0.0003 + 1.326 = 4.9312 ms. The verifier verifying a single signature needs to perform 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 = 3×1.6447 + 2×1.7975 + 0.0001 = 4.9341 + 3.595 + 0.0001 = 8.5292 ms. The verifier verifying n signatures needs to perform 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 = 3n×1.6447 + 2n×0.0099 + 1.7975 = 4.9341n + 0.0198n + 1.7975 = 4.9539n + 1.7975 ms.
In literature [23], the vehicle computing a single signature needs to perform 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 = 2×1.7975 + 4×0.0099 + 5×0.0001 = 3.595 + 0.0396 + 0.0005 = 3.6351 ms. The verifier verifying a single signature needs to perform four one-way hash functions, 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 = 4×0.0001 + 0.0099 + 7×1.7975 = 0.0004 + 0.0099 + 12.5825 = 12.5928 ms. The verifier verifying n signatures needs to perform 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 nT_H + (2n+5)T_BPM + (6n+1)T_BPA = n×0.0001 + (2n+5)×1.7975 + (6n+1)×0.0099 = 0.0001n + 3.595n + 8.9875 + 0.0594n + 0.0099 = 3.6545n + 8.9974 ms.
In literature [24], the user computing a single signature needs to perform 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 = 3×1.7975 + 2×0.442 + 2×0.0001 = 5.3925 + 0.884 + 0.0002 = 6.2767 ms. Verifying a single signature needs to perform 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 = 4×1.7975 + 2×0.0099 + 2×0.0001 = 7.19 + 0.0198 + 0.0002 = 7.21 ms. The verifier verifying n signatures needs to perform 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 = (2n+2)×1.7975 + (2n+2)×0.0099 + 2n×0.442 = (3.595n + 3.595) + (0.0198n + 0.0198) + 0.884n = 4.4988n + 3.6148 ms.
In this scheme, the UE computing a single signature needs to perform two scalar multiplication operations. Therefore, the computational cost to generate a single signature is 2T_s = 2×0.442 = 0.884 ms. The verifier verifying a single signature needs to perform 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×1.7975 + 3×0.0099 = 5.3925 + 0.0297 = 5.4222 ms. The verifier verifying n signatures needs to perform 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 = (2n+1)×1.7975 + (4n-3)×0.0099 = 3.595n + 1.7975 + 0.0396n – 0.0297 = 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 comparison scheme, the proposed scheme reduces the computational overhead by 67% in signature generation and by 25% in single signature verification. The comparison of computational overhead for generating a single signature and verifying a single signature is shown in Figure 4. The batch authentication computational overhead of the proposed scheme is reduced 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] | 3T_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 | nT_H + (2n+5)T_BPM + (6n+1)T_BPA |
| 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 p are 64 bytes and 20 bytes respectively, the element sizes in G1 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 Z_p* is 20 bytes.
In literature [21], the message sent by the vehicle is {PID_i, R_i, m_i, T_i, σ_i}, where PID_i ∈ G1, R_i ∈ G1, σ_i ∈ Z_p*, T_i is the timestamp. The total communication overhead is 2|G1| + |Z_p*| + |timestamp| = 2×128 + 20 + 4 = 256 + 20 + 4 = 280 bytes.
In literature [22], the message sent by the vehicle is {PID_j, K1, K_v, m, R1, R_b, σ, δ_j}, where K1, K_v, R1, R_b, σ ∈ G1, δ_j ∈ Z_p*, TS_j is the timestamp. The total communication overhead is 5|G1| + |Z_p*| + |timestamp| = 5×128 + 20 + 4 = 640 + 20 + 4 = 664 bytes.
In literature [23], the message sent by the vehicle is {S1_k, S2_k, m_k, L_k, N_k, T_k, W_k, Z_k, σ_k}, where S1_k, S2_k, L_k, N_k, T_k, W_k, Z_k ∈ G1, σ_k ∈ Z_p*. The total communication overhead is 7|G1| + |Z_p*| = 7×128 + 20 = 896 + 20 = 916 bytes.
In literature [24], the message sent by the user is {PID_i,j, R_i,j, U_i,j, M_i,j, T_i, σ_i,j, δ_i,j}, where PID_i,j, R_i,j, U_i,j ∈ G1, M_i,j, δ_i,j ∈ Z_p*, T_i is the timestamp. The total communication overhead is 3|G1| + 2|Z_p*| + |timestamp| = 3×128 + 2×20 + 4 = 384 + 40 + 4 = 428 bytes.
In this scheme, the message sent by the UAV is {PID_i, vpk_{PIDi}, T_i, Tpk_{UEi}, σ_i}, where PID_i, vpk_{PIDi}, Tpk_{UEi} ∈ G1, σ_i ∈ Z_p*. Therefore, the communication overhead of this scheme is 3|G1| + |Z_p*| + |timestamp| = 3×128 + 20 + 4 = 384 + 20 + 4 = 408 bytes.
The communication overhead comparison of all schemes is shown in Table 2. Compared with the optimal comparison scheme, the proposed scheme reduces the communication overhead by 4.7%. 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, σ_i} | 280 |
| Maurya et al. [22] | {PID_j, K1, K_v, m, R1, R_b, σ, δ_j} | 664 |
| Dwivedi et al. [23] | {S1_k, S2_k, m_k, L_k, N_k, T_k, W_k, Z_k, σ_k} | 916 |
| Cui et al. [24] | {PID_i,j, R_i,j, U_i,j, M_i,j, T_i, σ_i,j, δ_i,j} | 428 |
| Proposed Scheme | {PID_i, vpk_{PIDi}, T_i, Tpk_{UEi}, σ_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 batch authentication fails, given n access authentication requests and at most d invalid access authentication requests.
In the traditional binary search-based scheme [24], the error detection complexity is O(d log(n)). The error detection method proposed in literature [12] based on d-disjoint matrices has an error detection complexity of O(d^2 log(n/d)). The error detection complexity of this scheme based on (d, d-)-separable matrices is O(d log(n/d)). Although the traditional binary search-based scheme requires fewer error detection times, the error detection method based on binary search cannot run in parallel and can only aggregate sequentially according to binary search, 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 when d=2, d=5, and d=10. From Figure 6, it can be seen that 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 paper addresses the issues of poor fault tolerance and insufficient error detection capability 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, this 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 group testing to construct an 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 paper conducts non-formal security analysis of the proposed scheme, provides security proofs under the random oracle model, and performs formal verification in 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.