# Efficient Certificateless Aggregate Signature Scheme for Performing Secure Routing in VANETs

Authors: Zhiyan Xu; Debiao He; Neeraj Kumar; Kim-Kwang Raymond Choo
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Certificateless public key cryptosystem solves both the complex certificate management problem in the public key cryptosystem based on the PKI and the key escrow issue in the public key cryptosystem based on identity. The aggregator can compressn different signatures with respect to n messages from n signers into an aggregate signature, which can help communication equipments to save a lot of bandwidth and computing resources. Therefore, the certificateless aggregate signature (CLAS) scheme is particularly well suited to address secure routing authentication issues in resource-constrained vehicular ad hoc networks. Unfortunately, most of the existing CLAS schemes have problems with security vulnerabilities or high computation and communication overheads. To avoid the above issues and better solve the secure routing authentication problem in vehicular ad hoc networks, we present a new CLAS scheme and give the formal security proof of our scheme under the CDH assumption in the random oracle model. We then evaluate the performance of our proposed CLAS scheme, and the results demonstrate that our proposal is more practical in resource-constrained vehicular ad hoc networks.


---

## Body

## 1. Introduction

Vehicular ad hoc networks (VANETs) have drawn comprehensive attention in recent years as they help enhance driving safety and optimize transportation systems [1, 2]. Figure 1 shows a typical VANET architecture in a vehicle-road cooperative system. The VANET is based on sensor detection and wireless communication technology to obtain vehicle road information, which is usually composed of road trusted authorities (TAs), road side units (RSUs) along the roads, and on-board units (OBUs) installed in the vehicles. Through vehicle-vehicle and vehicle-road information exchange and sharing, the traffic control center can effectively understand the traffic environment, further realize the intelligent cooperation between vehicles and the infrastructure, and finally achieve the goal of optimizing system resources and improving road traffic.Figure 1
A typical VANET architecture.Just as everything has two sides, VANETs are bringing convenience to people’s lives while also facing great security challenges. On the one hand, mobile VANETs, by exchanging information between vehicles, can enhance the safety of the vehicle and thus ensure passenger safety. On the other hand, dynamic topology and lack of centralized management features make it difficult for users to identify nodes that have malicious behavior in VANETs. VANETs may suffer from malicious attacks such as message tampering, false message sending, and denial of service (DOS) [3]. This means that, in a VANET, there may be malicious nodes broadcasting false information to other nodes and attempting to disrupt route discovery or data transmission, and because the VANET is a network where vehicles are constantly changing positions, secure routing is essential.To defend against the intruder’s attack, VANETs’ security design should meet the security attributes such as authenticity, privacy, and integrity. Among them, authenticity can ensure the reliability of a message by correctly identifying the identity of the sender, which can be used to solve the problem of secure routing authentication. Privacy refers to the private communication by using pseudonyms between communication entities. Integrity is the mechanism by which information cannot be tampered with or discarded as it is transmitted from the sender to the receiver. The above attributes are important factors that enable the public to accept and successfully deploy VANETs.Digital signature [4, 5] can provide routing authentication, integrity detection, and nonrepudiation. Anyone should be able to verify the validity of the signature through the signer’s public key, which helps to achieve efficient and secure communication between nodes in the VANET. However, RSUs and traffic control centers in the VANET (generally verified by TAs) all need to verify a large number of route-related signatures in high-density communication scenarios [2], which will result in higher computational burden for nodes, especially for the node in resource-constrained networks. In these situations, it is best to limit the digital signature’s communication requirements (i.e., size). One accepted solution is the aggregate signature technology which is the best choice to solve the above problems.Because the aggregate signature can reduce the node authentication overhead and the certificateless cryptosystem can solve certificate management and key escrow problems existing in the traditional cryptosystem, many researchers combine certificateless cryptography and aggregate signature to further propose various CLAS schemes. The CLAS can not only prevent the routing information from being forged, tampered, and impersonated but also ensure the integrity of the routing information and provide authentication and nonrepudiation for the routing information sender. In this paper, we put forward a CLAS scheme for the practical application environment of the VANETs.


### 1.1. Our Research Contributions

In this paper, we put forward a novel CLAS scheme which could better support the reliable routing information delivery in the highly dynamic VANETs. The main contributions of this paper are summarized as follows:(i)
Firstly, we define a typical VANET architecture for an emergency linkage scheduling environment, which is more close to the actual application scenario.(ii)
Secondly, we present a CLAS scheme for VANETs, and our new scheme can provide secure routing for VANETs while meeting the security requirements.(iii)
Finally, we prove the security and evaluate the performance of the newly proposed CLAS scheme.


### 1.2. Organization of the Paper

The remainder of this paper is organized as follows: Section2 describes the related work. Section 3 gives the problem statement related to our paper, and then we present details of the proposed CLAS scheme in Section 4. Furthermore, in Sections 5 and 6, the security proof and the performance analysis are presented. Finally, we give the conclusion of our work in Section 7.


## 1.1. Our Research Contributions

In this paper, we put forward a novel CLAS scheme which could better support the reliable routing information delivery in the highly dynamic VANETs. The main contributions of this paper are summarized as follows:(i)
Firstly, we define a typical VANET architecture for an emergency linkage scheduling environment, which is more close to the actual application scenario.(ii)
Secondly, we present a CLAS scheme for VANETs, and our new scheme can provide secure routing for VANETs while meeting the security requirements.(iii)
Finally, we prove the security and evaluate the performance of the newly proposed CLAS scheme.


## 1.2. Organization of the Paper

The remainder of this paper is organized as follows: Section2 describes the related work. Section 3 gives the problem statement related to our paper, and then we present details of the proposed CLAS scheme in Section 4. Furthermore, in Sections 5 and 6, the security proof and the performance analysis are presented. Finally, we give the conclusion of our work in Section 7.


## 2. Related Works

To achieve the identity authentication of the message sender and then establish a trust relationship between the nodes, many digital signature schemes have been put forward successively. In a traditional PKI-based public key cryptosystem [6–8], each user has a key pair, public key, and private key, where the former remains public and the latter remains secret. To ensure the correspondence between the user’s public key and his/her identity, the certificate authority (CA) needs to issue and maintain a certificate for the user, which involves various certificate management issues such as certificate distribution, storage, and revocation.In the identity-based public key cryptosystem (ID-PKC) [9–12], the public key is selected by the user himself/herself, and the user’s private key is produced by the private key generator (PKG) based on his/her identity information. Because no certificate is required, the ID-PKC can eliminate the problem of certificate management in the PKI. However, since the PKG can obtain any user’s private key, the ID-PKC suffers from a key escrow issue which means it must be fully trusted by all users, and this assumption is too strong in some applications.To solve the problems existing in the above two cryptosystems, researchers in [13] first put forward a certificateless public key cryptosystem (CL-PKC). In the CL-PKC, the user’s public key is produced by the user himself/herself, and the user’s full private key is generated by the cooperation between the KGC and the user. The former is responsible for generating the partial private key based on the user’s identity, and the latter is responsible for generating the secret value. Therefore, CL-PKC can not only solve the complex certificate management problem in the PKI-based cryptography but also solve the inherent key escrow issue in the identity-based cryptography [14].The advantages of the CL-PKC have aroused the enthusiasm of researchers, and many certificateless signature (CLS) schemes have been proposed [2, 15, 16]. Huang et al. [15] demonstrated that the CLS scheme proposed in [13] could not resist the public key replacement attack and further proposed an improved CLS scheme. Yum and Lee [2] introduced a generic CLS construction. However, Hu et al. [16] indicated that their scheme is insecure and further proposed an improved CLS scheme. Au et al. [17] proposed an enhanced security model that allows the malicious KGC to produce key pairs in any way. Nevertheless, the certificateless signature schemes proposed in [18, 19] have been found to be insecure against malicious KGC attacks.Boneh et al. [20] proposed the concept of aggregate signature in Eurocrypt 2003. The aggregator can compress n different signatures with respect to n messages from n different signers into an aggregate signature. The verifier can authenticate the multiple senders simply by verifying the short aggregate signature, which can save the bandwidth and computational cost of mobile devices in VANETs. Because aggregate signatures greatly shorten the length of the signature, they are especially suitable for applications in resource-constrained VANETs.Gong et al. [21] combined the certificateless public-key cryptosystem with the aggregate signature and then proposed the first CLAS scheme, but they did not present the formal security proof of the scheme. After the groundbreaking work [21], many CLAS schemes [22–27] were proposed for various practical application scenarios. Zhang and Zhang [22] redefined the concept and security model for the CLAS scheme and proposed a new CLAS scheme, but their scheme has been proven to not resist malicious KGC attacks.Xiong et al. [23] proposed a CLAS scheme, but He et al. [24] found that their scheme was falsifiable and further put forward a new CLAS scheme. The researchers [26, 27] have found that the CLAS scheme proposed in [25] is insecure for malicious KGC attacks. Horng et al. [28] proposed a CLAS scheme, but we found that the scheme cannot resist any type of adversary in the certificateless security model and the signature is falsifiable. More recently, Li et al. [29] demonstrated that there is a security defect in the CLAS scheme proposed in [24] and further put forward an improved CLAS scheme.


## 3. Problem Statement

In this section, we first describe the bilinear map and relational difficult problems and then introduce the system model of our proposed CLAS scheme. Finally, the system components of the CLAS scheme are given.


### 3.1. Bilinear Map

Suppose thatG1 and G2 are two cyclic groups, where prime number q is the order of G1 and G2 and P is the generator of G1. e:G1×G1⟶G2 is a bilinear map. For all P,Q,S∈G1, a,b∈Zq∗, and e should satisfy the following properties:(1)
Bilinearity:eP,Q+S=eP,QeP,S and eaP,bQ=eabP,Q=eP,abQ.(2)
Nondegeneracy: there existsP∈G1 such that eP,P≠1.(3)
Computability: there exists an efficient algorithm to calculateeP,Q.


### 3.2. Complexity Assumption

#### 3.2.1. Computational Diffie–Hellman (CDH) Problem

Given a generatorP of an additive cyclic group G1 with the order q and a random instance aP,bP, it is difficult to calculate abP, where a and b remain unknown.


#### 3.2.2. Computational Diffie–Hellman (CDH) Assumption

There does not exist adversaryA, and the CDH problem can be decided in probabilistic polynomial time with a nonnegligible probability ε, where ε>0 is a very small number.


### 3.3. System Model

In this paper, we take the application of VANETs in the emergency linkage scheduling (ELS) environment as an example and give the corresponding VANET architecture that is shown in Figure2. There are six types of entities in the VANET architecture: on-board unit (OBU), road side unit (RSU), key generation center (KGC), emergency command center (ECC), signature aggregator (SA), and trusted authority (TA). The entities are specifically defined as follows.Figure 2
Architecture of a VANET in the ELS environment.


#### 3.3.1. On-Board Unit

On-board unit is a device installed in the vehicle. LetIDi denote the identity and SKi,PKi denote the key pair of an OBU. Each OBU can use its private key to generate a signature for the relevant routing information and then send the signature to the signature aggregator.


#### 3.3.2. Road Side Unit

Road side unit is a device installed on the side of the road, which can generate signatures for related messages, realize the exchange and sharing of the vehicle-road information, and further provide local real-time traffic information to the emergency command center.


#### 3.3.3. Key Generator Center

Key generator center is a device that is responsible for generating system parametersparams and the partial private key Di for each OBU or RSU corresponding to his/her identity and then secretly sends Di to the OBU or RSU.


#### 3.3.4. Emergency Command Center

Emergency command center is a device with strong computing power and plenty of storage space, which can obtain information on the accident scene and surrounding road conditions from OBUs or RSUs through the vehicle network emergency linkage system and further give corresponding emergency measures to improve rescue efficiency.


#### 3.3.5. Signature Aggregator

Signature aggregator refers to a certain computing power of a device. It is responsible for collecting a single route-related signature from OBUs or RSUs and then generating an aggregate signature and sending it to the corresponding TA.


#### 3.3.6. Trusted Authority

Trusted authority is a device with a certain computing power. It is responsible for verifying the route-related aggregate signature and then outputting a verification result.


### 3.4. System Components

Our CLAS scheme for performing secure routing in VANETs is a collection of the following seven polynomial time algorithms:(i)
Setup1k⟶params,s,Ppub is a probabilistic algorithm executed by the KGC, where k is the security parameter, params is the system parameter list, s is the system master key, and Ppub is the system master public key.(ii)
Partial-Key-Genparams,IDi⟶Di is a probabilistic algorithm executed by the KGC, where params is the system parameter list, IDi∈0,1∗ is a user’s identity, and Di is the partial private key corresponding to the user’s identity IDi.(iii)
User-Key-Genparams,Di⟶SKi,PKi is a randomized algorithm executed by the user with identity IDi, where params is the system parameter list, Di is the partial private key corresponding to the identity IDi, and SKi,PKi is the key pair of the user with the identity IDi.(iv)
Signparams,SKi,PKi,IDi,mi⟶σi is a randomized algorithm executed by the signer, where params is the system parameter list, SKi,PKi is the key pair of the signer, IDi is the signer’s identity, mi is the message, and σi is the signature on the message mi.(v)
Verifyparams,IDi,mi,PKi,σi⟶“0”,“1” is a probabilistic algorithm executed by the verifier, where params is the system parameter list, IDi is the signer’s identity, PKi is the public key of the signer, mi is the message, and σi is the signature on the message mi; 1 or 0 is the output to indicate whether the signature σi is validated.(vi)
Aggregateparams,IDi,mi,PKi,σi1≤i≤n⟶σ is a deterministic algorithm executed by the signature aggregator, where params is the system parameter list, IDi is the signer’s identity, PKi is the public key of the signer, mi is the message, and σi is the signature on the message mi.(vii)
Aggregate-Verifyparams,IDi,mi,PKi,σ1≤i≤n⟶“0”,“1” is a deterministic algorithm executed by the aggregate verifier, where params is the system parameter list and σ is the aggregate signature on the message mi with the identity IDi and the public key PKi. 1 or 0 is the output to indicate whether the aggregate signature σ is validated.


## 3.1. Bilinear Map

Suppose thatG1 and G2 are two cyclic groups, where prime number q is the order of G1 and G2 and P is the generator of G1. e:G1×G1⟶G2 is a bilinear map. For all P,Q,S∈G1, a,b∈Zq∗, and e should satisfy the following properties:(1)
Bilinearity:eP,Q+S=eP,QeP,S and eaP,bQ=eabP,Q=eP,abQ.(2)
Nondegeneracy: there existsP∈G1 such that eP,P≠1.(3)
Computability: there exists an efficient algorithm to calculateeP,Q.


## 3.2. Complexity Assumption

### 3.2.1. Computational Diffie–Hellman (CDH) Problem

Given a generatorP of an additive cyclic group G1 with the order q and a random instance aP,bP, it is difficult to calculate abP, where a and b remain unknown.


### 3.2.2. Computational Diffie–Hellman (CDH) Assumption

There does not exist adversaryA, and the CDH problem can be decided in probabilistic polynomial time with a nonnegligible probability ε, where ε>0 is a very small number.


## 3.2.1. Computational Diffie–Hellman (CDH) Problem

Given a generatorP of an additive cyclic group G1 with the order q and a random instance aP,bP, it is difficult to calculate abP, where a and b remain unknown.


## 3.2.2. Computational Diffie–Hellman (CDH) Assumption

There does not exist adversaryA, and the CDH problem can be decided in probabilistic polynomial time with a nonnegligible probability ε, where ε>0 is a very small number.


## 3.3. System Model

In this paper, we take the application of VANETs in the emergency linkage scheduling (ELS) environment as an example and give the corresponding VANET architecture that is shown in Figure2. There are six types of entities in the VANET architecture: on-board unit (OBU), road side unit (RSU), key generation center (KGC), emergency command center (ECC), signature aggregator (SA), and trusted authority (TA). The entities are specifically defined as follows.Figure 2
Architecture of a VANET in the ELS environment.


### 3.3.1. On-Board Unit

On-board unit is a device installed in the vehicle. LetIDi denote the identity and SKi,PKi denote the key pair of an OBU. Each OBU can use its private key to generate a signature for the relevant routing information and then send the signature to the signature aggregator.


### 3.3.2. Road Side Unit

Road side unit is a device installed on the side of the road, which can generate signatures for related messages, realize the exchange and sharing of the vehicle-road information, and further provide local real-time traffic information to the emergency command center.


### 3.3.3. Key Generator Center

Key generator center is a device that is responsible for generating system parametersparams and the partial private key Di for each OBU or RSU corresponding to his/her identity and then secretly sends Di to the OBU or RSU.


### 3.3.4. Emergency Command Center

Emergency command center is a device with strong computing power and plenty of storage space, which can obtain information on the accident scene and surrounding road conditions from OBUs or RSUs through the vehicle network emergency linkage system and further give corresponding emergency measures to improve rescue efficiency.


### 3.3.5. Signature Aggregator

Signature aggregator refers to a certain computing power of a device. It is responsible for collecting a single route-related signature from OBUs or RSUs and then generating an aggregate signature and sending it to the corresponding TA.


### 3.3.6. Trusted Authority

Trusted authority is a device with a certain computing power. It is responsible for verifying the route-related aggregate signature and then outputting a verification result.


## 3.3.1. On-Board Unit

On-board unit is a device installed in the vehicle. LetIDi denote the identity and SKi,PKi denote the key pair of an OBU. Each OBU can use its private key to generate a signature for the relevant routing information and then send the signature to the signature aggregator.


## 3.3.2. Road Side Unit

Road side unit is a device installed on the side of the road, which can generate signatures for related messages, realize the exchange and sharing of the vehicle-road information, and further provide local real-time traffic information to the emergency command center.


## 3.3.3. Key Generator Center

Key generator center is a device that is responsible for generating system parametersparams and the partial private key Di for each OBU or RSU corresponding to his/her identity and then secretly sends Di to the OBU or RSU.


## 3.3.4. Emergency Command Center

Emergency command center is a device with strong computing power and plenty of storage space, which can obtain information on the accident scene and surrounding road conditions from OBUs or RSUs through the vehicle network emergency linkage system and further give corresponding emergency measures to improve rescue efficiency.


## 3.3.5. Signature Aggregator

Signature aggregator refers to a certain computing power of a device. It is responsible for collecting a single route-related signature from OBUs or RSUs and then generating an aggregate signature and sending it to the corresponding TA.


## 3.3.6. Trusted Authority

Trusted authority is a device with a certain computing power. It is responsible for verifying the route-related aggregate signature and then outputting a verification result.


## 3.4. System Components

Our CLAS scheme for performing secure routing in VANETs is a collection of the following seven polynomial time algorithms:(i)
Setup1k⟶params,s,Ppub is a probabilistic algorithm executed by the KGC, where k is the security parameter, params is the system parameter list, s is the system master key, and Ppub is the system master public key.(ii)
Partial-Key-Genparams,IDi⟶Di is a probabilistic algorithm executed by the KGC, where params is the system parameter list, IDi∈0,1∗ is a user’s identity, and Di is the partial private key corresponding to the user’s identity IDi.(iii)
User-Key-Genparams,Di⟶SKi,PKi is a randomized algorithm executed by the user with identity IDi, where params is the system parameter list, Di is the partial private key corresponding to the identity IDi, and SKi,PKi is the key pair of the user with the identity IDi.(iv)
Signparams,SKi,PKi,IDi,mi⟶σi is a randomized algorithm executed by the signer, where params is the system parameter list, SKi,PKi is the key pair of the signer, IDi is the signer’s identity, mi is the message, and σi is the signature on the message mi.(v)
Verifyparams,IDi,mi,PKi,σi⟶“0”,“1” is a probabilistic algorithm executed by the verifier, where params is the system parameter list, IDi is the signer’s identity, PKi is the public key of the signer, mi is the message, and σi is the signature on the message mi; 1 or 0 is the output to indicate whether the signature σi is validated.(vi)
Aggregateparams,IDi,mi,PKi,σi1≤i≤n⟶σ is a deterministic algorithm executed by the signature aggregator, where params is the system parameter list, IDi is the signer’s identity, PKi is the public key of the signer, mi is the message, and σi is the signature on the message mi.(vii)
Aggregate-Verifyparams,IDi,mi,PKi,σ1≤i≤n⟶“0”,“1” is a deterministic algorithm executed by the aggregate verifier, where params is the system parameter list and σ is the aggregate signature on the message mi with the identity IDi and the public key PKi. 1 or 0 is the output to indicate whether the aggregate signature σ is validated.


## 4. Our Proposed CLAS Scheme

To improve the security of routing information in VANETs, we propose a new CLAS scheme. Compared to previous works, our new scheme strives to achieve the following two goals: (1) to ensure the unforgeability of the signature scheme and (2) to improve the performance of the scheme. Our CLAS scheme includes seven phases:Setup, Partial-Key-Gen, User-Key-Gen, Sign, Verify, Aggregate, and Aggregate-Verify. The scheme details are described below.


### 4.1. Setup

The KGC generates system parameters after obtaining the security parameterk by executing the following operations:(1)
The KGC generates two cyclic groupsG1 and G2 with the order q, where q is a prime number. P is a generator of G1. e:G1×G1⟶G2 is a bilinear pairing.(2)
The KGC randomly selectss∈Zq∗ as the master key and calculates Ppub=sP as the public key.(3)
The KGC selects four hash functions:H1:0,1∗⟶G1, H2:0,1∗⟶G1, h1:0,1∗⟶Zq∗, and h2:0,1∗⟶Zq∗.(4)
The KGC maintainss secret and params=G1,G2,P,e,q,Ppub,H1,H2,h1,h2 public.


### 4.2. Partial-Key-Gen

The KGC produces the user’s partial private key by executing the following operations:(1)
GivenIDi as a user’s identity, the KGC first calculates Qi=H1IDi and then computes the user’s partial private key Di=s⋅Qi.(2)
The KGC secretly sendsDi to the corresponding user.


### 4.3. User-Key-Gen

A user with the identityIDi generates his/her full private key and public key by executing the following operations:(1)
The user randomly selectsxi∈Zq∗ as the secret value.(2)
The user setsSKi=Di,xi as a user’s full private key.(3)
The user computesPKi=xiP as a user’s public key.


### 4.4. Sign

A signer with the identityIDi produces a signature σi on the message mi by executing the following operations:(1)
The signer inputs system parametersparams, signature key pairs SKi,PKi, and the message mi.(2)
The signer selectswi∈Zq∗ randomly and then computes Wi=wiP.(3)
The signer computesαi=h1IDi,PKi,Wi, βi=h2mi,IDi,PKi,Wi, and Z=H2Ppub.(4)
The signer computesVi=αiDi+wi+βixiZ.(5)
The signer outputsσi=Wi,Vi as the signature on the message mi.


### 4.5. Verify

The verifier verifies the signatureσi=Wi,Vi on the message mi with identity IDi by executing the following operations:(1)
The verifier computesαi=h1IDi,PKi,Wi, βi=h2mi,IDi,PKi,Wi, Qi=H1IDi, and Z=H2Ppub.(2)
The verifier verifies the following:(1)eVi,P=eαiQi,PpubeWi+βiPKi,Z.(3)
If equation (1) holds, it emits 1 and the verifier accepts σi; otherwise, it emits 0 and the verifier rejects σi.


### 4.6. Aggregate

The aggregator generates the aggregate signature σ from user-message-public key-signature pairsIDi,mi,PKi,σi1≤i≤n by executing the following operations:(1)
The aggregator inputsn tuples IDi,mi,PKi,σi, where 1≤i≤n.(2)
The aggregator computesV=∑i=1nVi.(3)
The aggregator outputsσ=W,V as the aggregate signature, where W=W1,W1,…,Wn.


### 4.7. Aggregate-Verify

The aggregate verifier verifies the validity of the aggregate signatureσ=W,V by executing the following operations:(1)
The aggregate verifier inputs the tuplesIDi,mi,PKi,σi1≤i≤n and the aggregate signature σ=W,V.(2)
The aggregate verifier computesZ=H2Ppub; furthermore, for 1≤i≤n, the aggregate verifier computes Qi=H1IDi, αi=h1IDi,PKi,Wi, and βi=h2mi,IDi,PKi,Wi.(3)
The aggregate verifier verifies the following:(2)eV,P=e∑i=1nαiQi,Ppube∑i=1nWi+βiPKi,Z.(4)
If equation (2) holds, it emits 1 and the verifier accepts the aggregate signature σ; otherwise, it emits 0 and the verifier rejects σ.Our proposed CLAS scheme is correct if and only if the single signature and aggregate signature generated using our scheme can satisfy equations (1) and (2), respectively, where the correctness of the scheme is elaborated as follows:(3)eVi,P=eαiDi+wi+βixiZ,P=eαisQi,Pewi+βixiZ,P=eαiQi,sPewi+βixiP,Z=eαiQi,PpubewiP+βixiP,Z=eαiQi,PpubeWi+βiPKi,Z,eV,P=e∑i=1nαiDi+wi+βixiZ,P=e∑i=1nαisQi,Pe∑i=1nwi+βixiZ,P=e∑i=1nαiQi,sPe∑i=1nwi+βixiP,Z=e∑i=1nαiQi,Ppube∑i=1nWi+βiPKi,Z.


## 4.1. Setup

The KGC generates system parameters after obtaining the security parameterk by executing the following operations:(1)
The KGC generates two cyclic groupsG1 and G2 with the order q, where q is a prime number. P is a generator of G1. e:G1×G1⟶G2 is a bilinear pairing.(2)
The KGC randomly selectss∈Zq∗ as the master key and calculates Ppub=sP as the public key.(3)
The KGC selects four hash functions:H1:0,1∗⟶G1, H2:0,1∗⟶G1, h1:0,1∗⟶Zq∗, and h2:0,1∗⟶Zq∗.(4)
The KGC maintainss secret and params=G1,G2,P,e,q,Ppub,H1,H2,h1,h2 public.


## 4.2. Partial-Key-Gen

The KGC produces the user’s partial private key by executing the following operations:(1)
GivenIDi as a user’s identity, the KGC first calculates Qi=H1IDi and then computes the user’s partial private key Di=s⋅Qi.(2)
The KGC secretly sendsDi to the corresponding user.


## 4.3. User-Key-Gen

A user with the identityIDi generates his/her full private key and public key by executing the following operations:(1)
The user randomly selectsxi∈Zq∗ as the secret value.(2)
The user setsSKi=Di,xi as a user’s full private key.(3)
The user computesPKi=xiP as a user’s public key.


## 4.4. Sign

A signer with the identityIDi produces a signature σi on the message mi by executing the following operations:(1)
The signer inputs system parametersparams, signature key pairs SKi,PKi, and the message mi.(2)
The signer selectswi∈Zq∗ randomly and then computes Wi=wiP.(3)
The signer computesαi=h1IDi,PKi,Wi, βi=h2mi,IDi,PKi,Wi, and Z=H2Ppub.(4)
The signer computesVi=αiDi+wi+βixiZ.(5)
The signer outputsσi=Wi,Vi as the signature on the message mi.


## 4.5. Verify

The verifier verifies the signatureσi=Wi,Vi on the message mi with identity IDi by executing the following operations:(1)
The verifier computesαi=h1IDi,PKi,Wi, βi=h2mi,IDi,PKi,Wi, Qi=H1IDi, and Z=H2Ppub.(2)
The verifier verifies the following:(1)eVi,P=eαiQi,PpubeWi+βiPKi,Z.(3)
If equation (1) holds, it emits 1 and the verifier accepts σi; otherwise, it emits 0 and the verifier rejects σi.


## 4.6. Aggregate

The aggregator generates the aggregate signature σ from user-message-public key-signature pairsIDi,mi,PKi,σi1≤i≤n by executing the following operations:(1)
The aggregator inputsn tuples IDi,mi,PKi,σi, where 1≤i≤n.(2)
The aggregator computesV=∑i=1nVi.(3)
The aggregator outputsσ=W,V as the aggregate signature, where W=W1,W1,…,Wn.


## 4.7. Aggregate-Verify

The aggregate verifier verifies the validity of the aggregate signatureσ=W,V by executing the following operations:(1)
The aggregate verifier inputs the tuplesIDi,mi,PKi,σi1≤i≤n and the aggregate signature σ=W,V.(2)
The aggregate verifier computesZ=H2Ppub; furthermore, for 1≤i≤n, the aggregate verifier computes Qi=H1IDi, αi=h1IDi,PKi,Wi, and βi=h2mi,IDi,PKi,Wi.(3)
The aggregate verifier verifies the following:(2)eV,P=e∑i=1nαiQi,Ppube∑i=1nWi+βiPKi,Z.(4)
If equation (2) holds, it emits 1 and the verifier accepts the aggregate signature σ; otherwise, it emits 0 and the verifier rejects σ.Our proposed CLAS scheme is correct if and only if the single signature and aggregate signature generated using our scheme can satisfy equations (1) and (2), respectively, where the correctness of the scheme is elaborated as follows:(3)eVi,P=eαiDi+wi+βixiZ,P=eαisQi,Pewi+βixiZ,P=eαiQi,sPewi+βixiP,Z=eαiQi,PpubewiP+βixiP,Z=eαiQi,PpubeWi+βiPKi,Z,eV,P=e∑i=1nαiDi+wi+βixiZ,P=e∑i=1nαisQi,Pe∑i=1nwi+βixiZ,P=e∑i=1nαiQi,sPe∑i=1nwi+βixiP,Z=e∑i=1nαiQi,Ppube∑i=1nWi+βiPKi,Z.


## 5. Security Analysis

In this section, we analyze the security of our proposed CLAS scheme. We first give the security model of a CLAS scheme and then prove that our proposal can satisfy signature unforgeability under the security model. At last, we demonstrate a comparative summary of the security between our CLAS scheme and three recently published CLAS schemes.


### 5.1. Security Model

There exist two types of adversaries in the CLAS security model:AI and AII. AI simulates an outside attacker, who cannot obtain the system master key but can replace any user’s public key. AII simulates a KGC, an internal attacker, who can obtain the system master key but cannot replace any user’s public key.Definition 1.
The security model of a CLAS scheme is defined by two games (denoted by Game1 and Game2) played between an adversaryA∈AI,AII and a challenger C; more details are defined below.
A can access the following six random oracle machines in the security model.


#### 5.1.1. Setup

C executes the Setup algorithm to generate the system master key s and params. For different types of adversaries, C will make a corresponding response.


#### 5.1.2. Reveal-Partial-Key

When the challengerC receives a partial private key query from A for a user with the identity IDi, C first checks if IDi=IDtu holds. If it holds, it aborts; otherwise, it checks if there is a record corresponding to the identity IDi in the list LD. If it exists, then Di is sent to A; otherwise, it generates Di, sends it to A, and stores it in the list LD.


#### 5.1.3. Reveal-Secret-Key

When the challengerC receives a secret value query from A for a user with the identity IDi, C first checks if IDi=IDtu holds. If it holds, it aborts; otherwise, it checks if there is a record corresponding to the identity IDi in the list Lx. If it exists, then xi is sent to A; otherwise, it generates xi, sends it to A, and stores it in the list Lx.


#### 5.1.4. Reveal-Public-Key

When the challengerC receives a public key query from A for a user with the identity IDi, C first checks if there is a record corresponding to the identity IDi in the list LPK. If it exists, then PKi is sent to A; otherwise, it generates PKi, sends it to A, and stores it in the list LPK.


#### 5.1.5. Replace-Public-Key

When the challengerC receives a query that replaces the public key on the identity IDi with A′s choice of public key PKi∗, C first checks if there is a record corresponding to the identity IDi in the list LPK. If it exists, then it updates the corresponding item IDi,xi,PKi,Di to IDi,xi,PKi∗,Di in the list LPK; otherwise, it aborts.


#### 5.1.6. Sign

When the challengerC receives a signature query on the message mi with the signer’s identity IDi, C first checks whether the target user IDi has been created. If the user IDi has not been created, it aborts; otherwise, if the target user IDi has been created and the related user public key PKi has not been replaced, then a valid signature σi is returned; otherwise, if the target user IDi has been created and the corresponding user public key PKi has been replaced with PKi∗, then a signature σi∗ is returned.We next define two games to describe two different types of attackers in the CLAS scheme.(1) Game1. The challenger C interacts with the adversary AI as follows:(1)
C inputs a security parameter k and generates the system master key s and the system parameter list params by running the Setup algorithm. Then, C sends params to AI and keeps s secret.(2)
Ai can access any hash oracle and Reveal‐Partial‐Key, Reveal‐Secret‐Key, Reveal‐Public‐Key, Replace‐Public‐Key, and Sign queries at any phase.(2) Forgery. AI outputs an aggregate signature σ∗ with respect to n pairs IDi∗,mi∗,PKi∗,σi∗, where 1≤i≤n. We say that AI wins Game1 if and only if the following conditions are met:(1)
σ∗ is a valid aggregate signature with respect to pairs IDi∗,mi∗,PKi∗,σi∗, where 1≤i≤n.(2)
The targeted identityIDi∗ has not been submitted during the Reveal‐Partial‐Key query.(3)
IDi∗,mi∗ has not been submitted during the Sign query.(3) Game2. The challenger C interacts with the adversary AII as follows:(1)
C inputs a security parameter k and generates the system master key s and the system parameter list params by running the Setup algorithm. Then, C returns params and s to AII.(2)
AII can access any hash oracle and Reveal‐Partial‐Key, Reveal‐Public‐Key, and Sign queries at any phase.(4) Forgery. AII outputs an aggregate signature σ∗ with respect to pairs IDi∗,mi∗,PKi∗,σi∗, where 1≤i≤n. We say that AII wins Game2 if and only if the following conditions are met:(1)
σ∗ is a valid aggregate signature with respect to user-message-public key-signature pairs IDi∗,mi∗,PKi∗,σi∗, where 1≤i≤n.(2)
The targeted identityIDi∗ has not been submitted during the Reveal‐Secret‐Key query.(3)
IDi∗,mi∗ has not been submitted during the Sign query.


### 5.2. Security Proof

In the section, we will prove that our proposed CLAS scheme is secure under the security model presented in Section5.1. Our security proof consists of the following two parts: (1) the CLAS scheme is unforgeable to type 1 adversary AI and (2) the CLAS scheme is unforgeable to type 2 adversary AII.Theorem 1.
Our proposed CLAS scheme is existentially unforgeable against the adversaryAI, if the CDH problem is difficult to solve in G1.Proof.
We can prove the unforgeability of our CLAS scheme againstAi with Game1 that involves an adversary AI and a simulator C.
Given a random instance of the CDH problemP,Q1=aP,Q2=bP, where P is a generator of G1, our goal is to calculate the value of abP by solving the CDH problem. The specific proof process is as follows:(i)
Setup:C randomly selects IDtu as the identity of the target user challenged, sets Ppub=Q1=aP, and generates and sends the system parameter params=G1,G2,P,e,q,Ppub,H1,H2,h1,h2 to AI. AI executes the following queries.(ii)
H1 query: C maintains a list LH1 whose structure is IDi,ηi,ζi,Qi, and all the elements in LH1 are initialized to null. When C receives a query with the identity IDi from Ai, it first checks whether the tuple IDi,ηi,ζi,Qi exists in LH1; if it exists, it sends Qi to AI; otherwise, C randomly selects ζi∈0,1 and ηi∈Zq∗. If ζi=0, Qi=ηiP; otherwise, if ζi=1, Qi=ηiQ2=ηibP. It sends Qi to Ai and stores IDi,ηi,ζi,Qi to LH1.(iii)
H2 query: C maintains a list LH2 whose structure is Ppub,ϑ,Z, and all the elements in LH2 are initialized to null. When C receives a query with Ppub from AI, it checks if a tuple Ppub,ϑ,Z exists in LH2; if it exists, it sends Z to AI; otherwise, C randomly selects ϑ∈Zq∗ and computes Z=ϑP. It sends Z to Ai and stores Ppub,ϑ,Z to LH2.(iv)
h1 query: C maintains a list Lh1 whose structure is IDi,PKi,Wi,αi, and all the elements in Lh1 are initialized to null. When C receives a query with the tuple IDi,PKi,Wi from AI, it checks whether a tuple IDi,PKi,Wi,αi exists in Lh1; if it exists, it sends αi to AI; otherwise, C randomly selects αi. It returns αi to AI and stores IDi,PKi,Wi,αi to Lh1.(v)
h2 query: C maintains a list Lh2 whose structure is mi,IDi,PKi,Wi,βi, and all the elements in Lh2 are initialized to null. When C receives a query with the tuple mi,IDi,PKi,Wi from AI, it checks if a tuple mi,IDi,PKi,Wi,βi exists in Lh2; if it exists, it sends βi to AI; otherwise, C randomly selects βi. It returns βi to AI and stores mi,IDi,PKi,Wi,βi to Lh2.(vi)
Reveal-Partial-Key queries:C maintains a list LD whose structure is IDi,Di, and all the elements in LD are initialized to null. When C receives a query with the identity IDi from AI, it first checks whether IDi=IDtu; if it holds, it outputs ⊥; otherwise, it checks if a tuple IDi,Di exists in LD; if it exists, it sends Di to AI; otherwise, C recalls the corresponding tuple IDi,ηi,ζi,Qi from the list LH1 and computes Di=ηiPpub=aηiP. It sends Di to AI and stores IDi,Di to LD.(vii)
Reveal-Secret-Key queries:C maintains a list Lx whose structure is IDi,xi, and all the elements in Lx are initialized to null. When C receives a query with the identity IDi from AI, it first checks whether IDi=IDtu; if it holds, it outputs ⊥; otherwise, it checks if a tuple IDi,xi exists in Lx; if it exists, it sends xi to AI; otherwise, C randomly selects xi. It sends xi to AI and stores xi to IDi,xi.(viii)
Reveal-Public-Key queries:C maintains a list LPK whose structure is IDi,PKi, and all the elements in LPK are initialized to null. When C receives a query with the identity IDi from AI, it first checks whether a tuple IDi,PKi exists in LPK; if it exists, it sends PKi to AI; otherwise, C accesses Lx to get xi and computes PKi=xiP. It sends PKi to AI and stores IDi,PKi to LPK.(ix)
Replace-Public-Key queries: whenC receives a query with the tuple IDi,PKi∗ from AI, in response, C replaces the real public key PKi of IDi with PKi∗ chosen by AI in LPK.(x)
Sign queries: whenC receives a query with the tuple mi,IDi,PKi from AI, C accesses LH1, LH2, Lh1, and Lh2 to get ζi, Qi, Z, αi, and βi respectively. Furthermore, C chooses a random wi∈Zq∗ and computes Wi=wiP; if ζi=0, C computes Vi=ηiαiP+wi+βixiϑP; otherwise, if ζi=1, C computes Vi=ηiαibP+wi+βixiϑP. C sends σi=Wi,Vi to AI as the signature on the message mi with the identity IDi and the public key PKi.(xi)
Forgery: finally,AI outputs a forged aggregate signature σ∗=W∗,V∗ from message-identity-public key pairs mi∗,IDi∗,PKi∗, where 1≤i≤n. If all ζi=0 holds, AI aborts; otherwise, without loss of generality, let IDtu=ID1, that is, ζ1=1, ζi=0, 2≤i≤n, and then the forged signature can make the following equation hold:(4)eV∗,P=e∑i=1nαi∗Qi∗,Ppube∑i=1nWi∗+βi∗PKi∗,Z,where Qi∗=ηi∗P 2≤i≤n, Q1∗=η1∗bP, Z=ϑP, V∗=∑i=1nVi∗, and W∗=W1∗,W2∗,…,Wn∗.
Furthermore, the derivation process is shown as(5)eV∗,P=e∑i=1nαi∗Di∗+wi∗+βi∗xi∗Z,P⟹eV∗,P=eα1∗aQ1∗,Pe∑i=2nαi∗aQi∗,Pe∑i=1nwi∗+βi∗xi∗Z,P⟹eα1∗aQ1∗,P=eV∗,Pe∑i=2nαi∗aQi∗,Pe∑i=1nwi∗+βi∗xi∗Z,P−1⟹eα1∗η1∗abP,P=eV∗,Pe∑i=2nαi∗aQi∗,Pe∑i=1nwi∗+βi∗xi∗Z,P−1⟹α1∗η1∗abP=V∗−∑i=2nαi∗aQi∗−∑i=1nwi∗+βi∗xi∗Z⟹abP=V∗−∑i=2nαi∗aQi∗−∑i=1nwi∗+βi∗xi∗Zα1∗η1∗−1.
However, this is in contradiction with the CDH assumption, so the single signature and the aggregate signature generated by our proposed scheme satisfy the unforgeability.Theorem 2.
Our proposed CLAS scheme is existentially unforgeable against the adversaryAII, if the CDH problem is difficult to solve in G1.Proof.
We can prove the unforgeability of our CLAS scheme againstAII with Game2 that involves an adversary AII and a simulator C.
Given a random instance of the CDH problemP,Q1=aP,Q2=bP, where P is the generator of G1, our goal is to calculate the value of abP by solving the CDH problem. The specific proof process is as follows:(i)
Setup:C randomly selects IDtu as the identity of the target user challenged, sets Ppub=λP, and generates and sends params=G1,G2,P,e,q,Ppub,H1,H2,h1,h2 and system master key λ to AII. AII executes the following queries: h1, h2, and Reveal-Secret-Value queries are the same as the corresponding queries in Theorem 1 Since AII can access the system master key, there is no need for the Reveal-Partial-Key queries and Replace-Public-Key queries.(ii)
H1 query: C maintains a list LH1 whose structure is IDi,ηi,Qi, and all the elements in LH1 are initialized to null. When C receives a query with the identity IDi from AII, it first checks whether the tuple IDi,ηi,Qi exists in LH1; if it exists, it sends Qi to AII; otherwise, C randomly selects ηi∈Zq∗, sets Qi=ηiP, sends Qi to AII, and stores IDi,ηi,Qi to LH1.(iii)
H2 query: C maintains a list LH2 whose structure is Ppub,ϑ,Z, and all the elements in LH2 are initialized to null. When C receives a query with Ppub from AII, it checks if a tuple Ppub,ϑ,Z exists in LH2; if it exists, it sends Z to AII; otherwise, C randomly selects ϑ∈Zq∗ and computes Z=ϑQ1=ϑaP. It sends Z to AII and stores Ppub,ϑ,Z to LH2.(iv)
Reveal-Public-Key queries:C maintains a list LPK whose structure is IDi,ζi,PKi, and all the elements in LPK are initialized to null. When C receives a query with the identity IDi from AII, it first checks whether a tuple IDi,ζi,PKi exists in LPK; if it exists, it sends PKi to AII; otherwise, C selects a random value ζi∈0,1; if ζi=0, C accesses Lx to get xi and computes PKi=xiP; otherwise, if ζi=1, C randomly chooses xi∈Zq∗ and computes PKi=xiQ2=xibP. It sends PKi to AII and stores IDi,ζi,PKi to LPK.(v)
Sign queries: whenC receives a query with the tuple mi,IDi,PKi from AII, C accesses LH1, LH2, Lh1, and Lh2 to get Qi, ζi, Z, αi, and βi, respectively. Furthermore, C chooses a random wi∈Zq∗ and computes Wi=wiP; if ζi=0, C computes Vi=λαiQi+wi+βixiZ; otherwise, if ζi=1, C computes Vi=λαiQi+wi+bβixiZ. It sends σi=Wi,Vi to AII as the signature on the message mi with the identity IDi and the public key PKi.(vi)
Forgery: finally,Aii outputs a forged aggregate signature σ∗=W∗,V∗ from message-identity-public key pairs mi∗,IDi∗,PKi∗, where 1≤i≤n. If all ζi=0 holds, AII aborts; otherwise, without loss of generality, let IDtu=ID1, that is, ζ1=1, ζi=0 2≤i≤n, and then the forged signature can make the following equation hold:(6)eV∗,P=e∑i=1nαi∗Qi∗,Ppube∑i=1nWi∗+βi∗PKi∗,Z,where Qi∗=ηi∗P, PK1∗=x1∗bP, PKi∗=xi∗P 2≤i≤n, Z=ϑaP, V∗=∑i=1nVi∗, and W∗=W1∗,W2∗,…,Wn∗.
Furthermore, the derivation process is shown as(7)eV∗,P=e∑i=1nαi∗Di∗+wi∗+βi∗xi∗Z,P⟹eV∗,P=e∑i=1nλαi∗Qi∗,Peβ1∗PK1∗,Ze∑i=1nWi∗+∑i=2nβi∗PKi∗,Z⟹eβ1∗PK1∗,Z=eV∗,Pe∑i=1nλαi∗Qi∗,Peϑa∑i=1nWi∗+∑i=2nβi∗PKi∗,P−1⟹β1∗x1∗ϑabP=V∗−∑i=1nλαi∗Qi∗−ϑa∑i=1nWi∗+∑i=2nβi∗PKi∗⟹abP=β1∗x1∗ϑ−1V∗−∑i=1nλαi∗Qi∗−ϑa∑i=1nWi∗+∑i=2nβi∗PKi∗.
However, this is in contradiction with the CDH assumption, so the single signature and the aggregate signature generated by our proposed scheme satisfy the unforgeability.


## 5.1. Security Model

There exist two types of adversaries in the CLAS security model:AI and AII. AI simulates an outside attacker, who cannot obtain the system master key but can replace any user’s public key. AII simulates a KGC, an internal attacker, who can obtain the system master key but cannot replace any user’s public key.Definition 1.
The security model of a CLAS scheme is defined by two games (denoted by Game1 and Game2) played between an adversaryA∈AI,AII and a challenger C; more details are defined below.
A can access the following six random oracle machines in the security model.


### 5.1.1. Setup

C executes the Setup algorithm to generate the system master key s and params. For different types of adversaries, C will make a corresponding response.


### 5.1.2. Reveal-Partial-Key

When the challengerC receives a partial private key query from A for a user with the identity IDi, C first checks if IDi=IDtu holds. If it holds, it aborts; otherwise, it checks if there is a record corresponding to the identity IDi in the list LD. If it exists, then Di is sent to A; otherwise, it generates Di, sends it to A, and stores it in the list LD.


### 5.1.3. Reveal-Secret-Key

When the challengerC receives a secret value query from A for a user with the identity IDi, C first checks if IDi=IDtu holds. If it holds, it aborts; otherwise, it checks if there is a record corresponding to the identity IDi in the list Lx. If it exists, then xi is sent to A; otherwise, it generates xi, sends it to A, and stores it in the list Lx.


### 5.1.4. Reveal-Public-Key

When the challengerC receives a public key query from A for a user with the identity IDi, C first checks if there is a record corresponding to the identity IDi in the list LPK. If it exists, then PKi is sent to A; otherwise, it generates PKi, sends it to A, and stores it in the list LPK.


### 5.1.5. Replace-Public-Key

When the challengerC receives a query that replaces the public key on the identity IDi with A′s choice of public key PKi∗, C first checks if there is a record corresponding to the identity IDi in the list LPK. If it exists, then it updates the corresponding item IDi,xi,PKi,Di to IDi,xi,PKi∗,Di in the list LPK; otherwise, it aborts.


### 5.1.6. Sign

When the challengerC receives a signature query on the message mi with the signer’s identity IDi, C first checks whether the target user IDi has been created. If the user IDi has not been created, it aborts; otherwise, if the target user IDi has been created and the related user public key PKi has not been replaced, then a valid signature σi is returned; otherwise, if the target user IDi has been created and the corresponding user public key PKi has been replaced with PKi∗, then a signature σi∗ is returned.We next define two games to describe two different types of attackers in the CLAS scheme.(1) Game1. The challenger C interacts with the adversary AI as follows:(1)
C inputs a security parameter k and generates the system master key s and the system parameter list params by running the Setup algorithm. Then, C sends params to AI and keeps s secret.(2)
Ai can access any hash oracle and Reveal‐Partial‐Key, Reveal‐Secret‐Key, Reveal‐Public‐Key, Replace‐Public‐Key, and Sign queries at any phase.(2) Forgery. AI outputs an aggregate signature σ∗ with respect to n pairs IDi∗,mi∗,PKi∗,σi∗, where 1≤i≤n. We say that AI wins Game1 if and only if the following conditions are met:(1)
σ∗ is a valid aggregate signature with respect to pairs IDi∗,mi∗,PKi∗,σi∗, where 1≤i≤n.(2)
The targeted identityIDi∗ has not been submitted during the Reveal‐Partial‐Key query.(3)
IDi∗,mi∗ has not been submitted during the Sign query.(3) Game2. The challenger C interacts with the adversary AII as follows:(1)
C inputs a security parameter k and generates the system master key s and the system parameter list params by running the Setup algorithm. Then, C returns params and s to AII.(2)
AII can access any hash oracle and Reveal‐Partial‐Key, Reveal‐Public‐Key, and Sign queries at any phase.(4) Forgery. AII outputs an aggregate signature σ∗ with respect to pairs IDi∗,mi∗,PKi∗,σi∗, where 1≤i≤n. We say that AII wins Game2 if and only if the following conditions are met:(1)
σ∗ is a valid aggregate signature with respect to user-message-public key-signature pairs IDi∗,mi∗,PKi∗,σi∗, where 1≤i≤n.(2)
The targeted identityIDi∗ has not been submitted during the Reveal‐Secret‐Key query.(3)
IDi∗,mi∗ has not been submitted during the Sign query.


## 5.1.1. Setup

C executes the Setup algorithm to generate the system master key s and params. For different types of adversaries, C will make a corresponding response.


## 5.1.2. Reveal-Partial-Key

When the challengerC receives a partial private key query from A for a user with the identity IDi, C first checks if IDi=IDtu holds. If it holds, it aborts; otherwise, it checks if there is a record corresponding to the identity IDi in the list LD. If it exists, then Di is sent to A; otherwise, it generates Di, sends it to A, and stores it in the list LD.


## 5.1.3. Reveal-Secret-Key

When the challengerC receives a secret value query from A for a user with the identity IDi, C first checks if IDi=IDtu holds. If it holds, it aborts; otherwise, it checks if there is a record corresponding to the identity IDi in the list Lx. If it exists, then xi is sent to A; otherwise, it generates xi, sends it to A, and stores it in the list Lx.


## 5.1.4. Reveal-Public-Key

When the challengerC receives a public key query from A for a user with the identity IDi, C first checks if there is a record corresponding to the identity IDi in the list LPK. If it exists, then PKi is sent to A; otherwise, it generates PKi, sends it to A, and stores it in the list LPK.


## 5.1.5. Replace-Public-Key

When the challengerC receives a query that replaces the public key on the identity IDi with A′s choice of public key PKi∗, C first checks if there is a record corresponding to the identity IDi in the list LPK. If it exists, then it updates the corresponding item IDi,xi,PKi,Di to IDi,xi,PKi∗,Di in the list LPK; otherwise, it aborts.


## 5.1.6. Sign

When the challengerC receives a signature query on the message mi with the signer’s identity IDi, C first checks whether the target user IDi has been created. If the user IDi has not been created, it aborts; otherwise, if the target user IDi has been created and the related user public key PKi has not been replaced, then a valid signature σi is returned; otherwise, if the target user IDi has been created and the corresponding user public key PKi has been replaced with PKi∗, then a signature σi∗ is returned.We next define two games to describe two different types of attackers in the CLAS scheme.(1) Game1. The challenger C interacts with the adversary AI as follows:(1)
C inputs a security parameter k and generates the system master key s and the system parameter list params by running the Setup algorithm. Then, C sends params to AI and keeps s secret.(2)
Ai can access any hash oracle and Reveal‐Partial‐Key, Reveal‐Secret‐Key, Reveal‐Public‐Key, Replace‐Public‐Key, and Sign queries at any phase.(2) Forgery. AI outputs an aggregate signature σ∗ with respect to n pairs IDi∗,mi∗,PKi∗,σi∗, where 1≤i≤n. We say that AI wins Game1 if and only if the following conditions are met:(1)
σ∗ is a valid aggregate signature with respect to pairs IDi∗,mi∗,PKi∗,σi∗, where 1≤i≤n.(2)
The targeted identityIDi∗ has not been submitted during the Reveal‐Partial‐Key query.(3)
IDi∗,mi∗ has not been submitted during the Sign query.(3) Game2. The challenger C interacts with the adversary AII as follows:(1)
C inputs a security parameter k and generates the system master key s and the system parameter list params by running the Setup algorithm. Then, C returns params and s to AII.(2)
AII can access any hash oracle and Reveal‐Partial‐Key, Reveal‐Public‐Key, and Sign queries at any phase.(4) Forgery. AII outputs an aggregate signature σ∗ with respect to pairs IDi∗,mi∗,PKi∗,σi∗, where 1≤i≤n. We say that AII wins Game2 if and only if the following conditions are met:(1)
σ∗ is a valid aggregate signature with respect to user-message-public key-signature pairs IDi∗,mi∗,PKi∗,σi∗, where 1≤i≤n.(2)
The targeted identityIDi∗ has not been submitted during the Reveal‐Secret‐Key query.(3)
IDi∗,mi∗ has not been submitted during the Sign query.


## 5.2. Security Proof

In the section, we will prove that our proposed CLAS scheme is secure under the security model presented in Section5.1. Our security proof consists of the following two parts: (1) the CLAS scheme is unforgeable to type 1 adversary AI and (2) the CLAS scheme is unforgeable to type 2 adversary AII.Theorem 1.
Our proposed CLAS scheme is existentially unforgeable against the adversaryAI, if the CDH problem is difficult to solve in G1.Proof.
We can prove the unforgeability of our CLAS scheme againstAi with Game1 that involves an adversary AI and a simulator C.
Given a random instance of the CDH problemP,Q1=aP,Q2=bP, where P is a generator of G1, our goal is to calculate the value of abP by solving the CDH problem. The specific proof process is as follows:(i)
Setup:C randomly selects IDtu as the identity of the target user challenged, sets Ppub=Q1=aP, and generates and sends the system parameter params=G1,G2,P,e,q,Ppub,H1,H2,h1,h2 to AI. AI executes the following queries.(ii)
H1 query: C maintains a list LH1 whose structure is IDi,ηi,ζi,Qi, and all the elements in LH1 are initialized to null. When C receives a query with the identity IDi from Ai, it first checks whether the tuple IDi,ηi,ζi,Qi exists in LH1; if it exists, it sends Qi to AI; otherwise, C randomly selects ζi∈0,1 and ηi∈Zq∗. If ζi=0, Qi=ηiP; otherwise, if ζi=1, Qi=ηiQ2=ηibP. It sends Qi to Ai and stores IDi,ηi,ζi,Qi to LH1.(iii)
H2 query: C maintains a list LH2 whose structure is Ppub,ϑ,Z, and all the elements in LH2 are initialized to null. When C receives a query with Ppub from AI, it checks if a tuple Ppub,ϑ,Z exists in LH2; if it exists, it sends Z to AI; otherwise, C randomly selects ϑ∈Zq∗ and computes Z=ϑP. It sends Z to Ai and stores Ppub,ϑ,Z to LH2.(iv)
h1 query: C maintains a list Lh1 whose structure is IDi,PKi,Wi,αi, and all the elements in Lh1 are initialized to null. When C receives a query with the tuple IDi,PKi,Wi from AI, it checks whether a tuple IDi,PKi,Wi,αi exists in Lh1; if it exists, it sends αi to AI; otherwise, C randomly selects αi. It returns αi to AI and stores IDi,PKi,Wi,αi to Lh1.(v)
h2 query: C maintains a list Lh2 whose structure is mi,IDi,PKi,Wi,βi, and all the elements in Lh2 are initialized to null. When C receives a query with the tuple mi,IDi,PKi,Wi from AI, it checks if a tuple mi,IDi,PKi,Wi,βi exists in Lh2; if it exists, it sends βi to AI; otherwise, C randomly selects βi. It returns βi to AI and stores mi,IDi,PKi,Wi,βi to Lh2.(vi)
Reveal-Partial-Key queries:C maintains a list LD whose structure is IDi,Di, and all the elements in LD are initialized to null. When C receives a query with the identity IDi from AI, it first checks whether IDi=IDtu; if it holds, it outputs ⊥; otherwise, it checks if a tuple IDi,Di exists in LD; if it exists, it sends Di to AI; otherwise, C recalls the corresponding tuple IDi,ηi,ζi,Qi from the list LH1 and computes Di=ηiPpub=aηiP. It sends Di to AI and stores IDi,Di to LD.(vii)
Reveal-Secret-Key queries:C maintains a list Lx whose structure is IDi,xi, and all the elements in Lx are initialized to null. When C receives a query with the identity IDi from AI, it first checks whether IDi=IDtu; if it holds, it outputs ⊥; otherwise, it checks if a tuple IDi,xi exists in Lx; if it exists, it sends xi to AI; otherwise, C randomly selects xi. It sends xi to AI and stores xi to IDi,xi.(viii)
Reveal-Public-Key queries:C maintains a list LPK whose structure is IDi,PKi, and all the elements in LPK are initialized to null. When C receives a query with the identity IDi from AI, it first checks whether a tuple IDi,PKi exists in LPK; if it exists, it sends PKi to AI; otherwise, C accesses Lx to get xi and computes PKi=xiP. It sends PKi to AI and stores IDi,PKi to LPK.(ix)
Replace-Public-Key queries: whenC receives a query with the tuple IDi,PKi∗ from AI, in response, C replaces the real public key PKi of IDi with PKi∗ chosen by AI in LPK.(x)
Sign queries: whenC receives a query with the tuple mi,IDi,PKi from AI, C accesses LH1, LH2, Lh1, and Lh2 to get ζi, Qi, Z, αi, and βi respectively. Furthermore, C chooses a random wi∈Zq∗ and computes Wi=wiP; if ζi=0, C computes Vi=ηiαiP+wi+βixiϑP; otherwise, if ζi=1, C computes Vi=ηiαibP+wi+βixiϑP. C sends σi=Wi,Vi to AI as the signature on the message mi with the identity IDi and the public key PKi.(xi)
Forgery: finally,AI outputs a forged aggregate signature σ∗=W∗,V∗ from message-identity-public key pairs mi∗,IDi∗,PKi∗, where 1≤i≤n. If all ζi=0 holds, AI aborts; otherwise, without loss of generality, let IDtu=ID1, that is, ζ1=1, ζi=0, 2≤i≤n, and then the forged signature can make the following equation hold:(4)eV∗,P=e∑i=1nαi∗Qi∗,Ppube∑i=1nWi∗+βi∗PKi∗,Z,where Qi∗=ηi∗P 2≤i≤n, Q1∗=η1∗bP, Z=ϑP, V∗=∑i=1nVi∗, and W∗=W1∗,W2∗,…,Wn∗.
Furthermore, the derivation process is shown as(5)eV∗,P=e∑i=1nαi∗Di∗+wi∗+βi∗xi∗Z,P⟹eV∗,P=eα1∗aQ1∗,Pe∑i=2nαi∗aQi∗,Pe∑i=1nwi∗+βi∗xi∗Z,P⟹eα1∗aQ1∗,P=eV∗,Pe∑i=2nαi∗aQi∗,Pe∑i=1nwi∗+βi∗xi∗Z,P−1⟹eα1∗η1∗abP,P=eV∗,Pe∑i=2nαi∗aQi∗,Pe∑i=1nwi∗+βi∗xi∗Z,P−1⟹α1∗η1∗abP=V∗−∑i=2nαi∗aQi∗−∑i=1nwi∗+βi∗xi∗Z⟹abP=V∗−∑i=2nαi∗aQi∗−∑i=1nwi∗+βi∗xi∗Zα1∗η1∗−1.
However, this is in contradiction with the CDH assumption, so the single signature and the aggregate signature generated by our proposed scheme satisfy the unforgeability.Theorem 2.
Our proposed CLAS scheme is existentially unforgeable against the adversaryAII, if the CDH problem is difficult to solve in G1.Proof.
We can prove the unforgeability of our CLAS scheme againstAII with Game2 that involves an adversary AII and a simulator C.
Given a random instance of the CDH problemP,Q1=aP,Q2=bP, where P is the generator of G1, our goal is to calculate the value of abP by solving the CDH problem. The specific proof process is as follows:(i)
Setup:C randomly selects IDtu as the identity of the target user challenged, sets Ppub=λP, and generates and sends params=G1,G2,P,e,q,Ppub,H1,H2,h1,h2 and system master key λ to AII. AII executes the following queries: h1, h2, and Reveal-Secret-Value queries are the same as the corresponding queries in Theorem 1 Since AII can access the system master key, there is no need for the Reveal-Partial-Key queries and Replace-Public-Key queries.(ii)
H1 query: C maintains a list LH1 whose structure is IDi,ηi,Qi, and all the elements in LH1 are initialized to null. When C receives a query with the identity IDi from AII, it first checks whether the tuple IDi,ηi,Qi exists in LH1; if it exists, it sends Qi to AII; otherwise, C randomly selects ηi∈Zq∗, sets Qi=ηiP, sends Qi to AII, and stores IDi,ηi,Qi to LH1.(iii)
H2 query: C maintains a list LH2 whose structure is Ppub,ϑ,Z, and all the elements in LH2 are initialized to null. When C receives a query with Ppub from AII, it checks if a tuple Ppub,ϑ,Z exists in LH2; if it exists, it sends Z to AII; otherwise, C randomly selects ϑ∈Zq∗ and computes Z=ϑQ1=ϑaP. It sends Z to AII and stores Ppub,ϑ,Z to LH2.(iv)
Reveal-Public-Key queries:C maintains a list LPK whose structure is IDi,ζi,PKi, and all the elements in LPK are initialized to null. When C receives a query with the identity IDi from AII, it first checks whether a tuple IDi,ζi,PKi exists in LPK; if it exists, it sends PKi to AII; otherwise, C selects a random value ζi∈0,1; if ζi=0, C accesses Lx to get xi and computes PKi=xiP; otherwise, if ζi=1, C randomly chooses xi∈Zq∗ and computes PKi=xiQ2=xibP. It sends PKi to AII and stores IDi,ζi,PKi to LPK.(v)
Sign queries: whenC receives a query with the tuple mi,IDi,PKi from AII, C accesses LH1, LH2, Lh1, and Lh2 to get Qi, ζi, Z, αi, and βi, respectively. Furthermore, C chooses a random wi∈Zq∗ and computes Wi=wiP; if ζi=0, C computes Vi=λαiQi+wi+βixiZ; otherwise, if ζi=1, C computes Vi=λαiQi+wi+bβixiZ. It sends σi=Wi,Vi to AII as the signature on the message mi with the identity IDi and the public key PKi.(vi)
Forgery: finally,Aii outputs a forged aggregate signature σ∗=W∗,V∗ from message-identity-public key pairs mi∗,IDi∗,PKi∗, where 1≤i≤n. If all ζi=0 holds, AII aborts; otherwise, without loss of generality, let IDtu=ID1, that is, ζ1=1, ζi=0 2≤i≤n, and then the forged signature can make the following equation hold:(6)eV∗,P=e∑i=1nαi∗Qi∗,Ppube∑i=1nWi∗+βi∗PKi∗,Z,where Qi∗=ηi∗P, PK1∗=x1∗bP, PKi∗=xi∗P 2≤i≤n, Z=ϑaP, V∗=∑i=1nVi∗, and W∗=W1∗,W2∗,…,Wn∗.
Furthermore, the derivation process is shown as(7)eV∗,P=e∑i=1nαi∗Di∗+wi∗+βi∗xi∗Z,P⟹eV∗,P=e∑i=1nλαi∗Qi∗,Peβ1∗PK1∗,Ze∑i=1nWi∗+∑i=2nβi∗PKi∗,Z⟹eβ1∗PK1∗,Z=eV∗,Pe∑i=1nλαi∗Qi∗,Peϑa∑i=1nWi∗+∑i=2nβi∗PKi∗,P−1⟹β1∗x1∗ϑabP=V∗−∑i=1nλαi∗Qi∗−ϑa∑i=1nWi∗+∑i=2nβi∗PKi∗⟹abP=β1∗x1∗ϑ−1V∗−∑i=1nλαi∗Qi∗−ϑa∑i=1nWi∗+∑i=2nβi∗PKi∗.
However, this is in contradiction with the CDH assumption, so the single signature and the aggregate signature generated by our proposed scheme satisfy the unforgeability.


## 6. Security Comparisons and Performance Analysis

In this section, we first compare the security of the new CLAS scheme and the other three CLAS schemes and then further analyze the performance advantages of the new CLAS scheme by evaluating the computation overhead.


### 6.1. Security Comparisons

In the section, we compare the security of our proposed CLAS scheme with that of the other three CLAS schemes [21, 25, 29]. For ease of description, let AI and AII denote the type 1 and the type 2 adversaries, respectively. Furthermore, the two types of adversaries are divided into three levels [30], where Bi1 denotes general adversary, Bi2 denotes strong adversary, and Bi3 denotes superadversary, respectively, and i∈1,2; the value of i corresponds to the type i adversary. √ denotes it can satisfy the corresponding security requirement, and × denotes it cannot satisfy the corresponding security requirement. W denotes the weaker security, and S denotes the stronger security under the corresponding attack types. SP denotes the security performance. The security comparison of various schemes is shown in Table 1.Table 1
Security comparisons.
B
11
B
12
B
13
S
P
B
21
B
22
B
23
S
P
Gong et al.’s scheme [21]
×
√
×
S
√
×
×
W
Liu et al.’s scheme [25]
√
√
√
S
×
×
×
W
Li et al.’s scheme [29]
√
√
√
S
√
√
√
S
Our proposed scheme
√
√
√
S
√
√
√
SFrom Table1, we can find that the first two schemes (i.e., Gong et al.’s scheme [21] and Liu et al.’s scheme [25]) cannot meet all security attributes. Especially for Gong et al.’s two CLAS schemes [21], under the attacks of Ai and Aii adversaries, none of them could satisfy the security level of B3. In contrast, Li’s CLAS scheme and our proposed CLAS scheme can meet all the security requirements.


### 6.2. Performance Analysis

In this section, we performed a performance analysis of the newly proposed CLAS scheme by comparing the computation overhead of our scheme with that of Li et al.’s scheme. To achieve a credible security level, we selectq and p as 160-bit and 512-bit prime numbers, respectively. An Ate pairing e:G1×G1⟶G2 is used in our experiments, where G1 and G2 are two cyclic groups with the same order q, defined on the supersingular elliptic curve EFp:y2=x3+1.We have implemented Li et al.’s scheme and our new scheme with the MIRACL library [31] on a Lenovo computer with Windows 7 operating system. And its hardware configuration is Intel I5-3470 3.20 GHz CPU and 4G bytes of memory. For the sake of simplicity, we firstly define the corresponding relation-related symbol-operation-execution time, as shown in Table 2.Table 2
Symbol-operation-execution time.
Symbol
Operation
Timems
T
m
−
s
The time of executing a general hash operation inZq∗
0.0002
T
m
−
p
The time of executing a map-to-point operation inG1
9.773
T
e
c
c
−
p
a
The time of executing a point addition operation inG1
0.022
T
e
c
c
−
p
m
The time of executing a point multiplication operation inG1
3.740
T
b
p
The time of executing a bilinear pairing operation
11.515Because Setup,Partial-Key-Gen, and Private-Key-Gen phases are executed by the PKG or user, and all of them are one-time operation, we focus on the analysis and comparison of computational costs in Sign, Verify, Aggregate, and Aggregate-Verify phases. Since the addition and multiplication of numbers in Zq∗ will only generate less computational overhead, we can ignore them.In theSign phase, the user in Li et al.’s scheme needs to perform two general hash operations in Zq∗, one map-to-point hash operation in G1, three point addition operations in G1, and five point multiplication operations in G1. Therefore, the time for generating a signature in the Sign phase is 2Tm−s+Tm−p+3Tecc−pa+5Tecc−pm, whereas the user in our proposal needs to perform two general hash operations in Zq∗, one map-to-point hash operation in G1, two point addition operations in G1, and three point multiplication operations in G1. Therefore, the time for generating a signature in the Sign phase is 2Tm−s+Tm−p+2Tecc−pa+3Tecc−pm milliseconds.In theVerify phase, the verifier in Li et al.’s scheme needs to execute two general hash operations in Zq∗, two map-to-point hash operations in G1, two point addition operations in G1, two point multiplication operations in G1, and three bilinear pairing operations. Therefore, the time for verifying a signature in the Verify phase is 2Tm−s+2Tm−p+2Tecc−pa+2Tecc−pm+3Tbp, whereas the verifier in our proposal needs to perform two general hash operations in Zq∗, two map-to-point hash operations in G1, one point addition operation in G1, two point multiplication operations in G1, and three bilinear pairing operations. Therefore, the time for verifying a signature in the Verify phase is 2Tm−s+2Tm−p+Tecc−pa+2Tecc−pm+3Tbp milliseconds.In theAggregate phase, the aggregator in Li et al.’s scheme needs to execute n−1 point addition operations in G1, whereas the aggregator in our proposal needs to execute n−1 point addition operations in G1. We can find that the running time of the Aggregate phase in the two schemes is equal to n−1Tecc−pa milliseconds.In theAggregate−Verify phase, the aggregate verifier in Li et al.’s scheme needs to execute 2n general hash operations in Zq∗, n+1 map-to-point hash operations in G1, 4n−2 point addition operations in G1, 2n point multiplication operations in G1, and three bilinear pairing operations. Therefore, the running time of the Aggregate−Verify phase is 2nTm−s+n+1Tm−p+4n−2Tecc−pa+2nTecc−pm+3Tbp milliseconds, whereas the verifier in our proposal needs to perform 2n general hash operations in Zq∗, n+1 map-to-point hash operations in G1, 3n−2 point addition operations in G1, 2n point multiplication operations in G1, and three bilinear pairing operations. Therefore, the running time of the Aggregate−Verify phase is 2nTm−s+n+1Tm−p+3n−2Tecc−pa+2nTecc−pm+3Tbp milliseconds.Suppose thatn=100, that is, there are 100 signatures that need to be generated, verified, aggregated, and aggregate-verified. From the results in Figure 3, we can see that Li et al.’s scheme has the same computation overhead as our new CLAS scheme in the Aggregate phase, whereas in Sign, Verify, and Aggregate−Verify phases, the computation cost of our scheme is lower than that of Li et al.’s scheme. Especially in the Sign phase, the computation cost of our scheme is reduced by 26 percentage points compared with that of Li et al.’s scheme. In summary, our presented CLAS scheme reduces the computation cost while meeting security requirements.Figure 3
Computation cost comparisons.


## 6.1. Security Comparisons

In the section, we compare the security of our proposed CLAS scheme with that of the other three CLAS schemes [21, 25, 29]. For ease of description, let AI and AII denote the type 1 and the type 2 adversaries, respectively. Furthermore, the two types of adversaries are divided into three levels [30], where Bi1 denotes general adversary, Bi2 denotes strong adversary, and Bi3 denotes superadversary, respectively, and i∈1,2; the value of i corresponds to the type i adversary. √ denotes it can satisfy the corresponding security requirement, and × denotes it cannot satisfy the corresponding security requirement. W denotes the weaker security, and S denotes the stronger security under the corresponding attack types. SP denotes the security performance. The security comparison of various schemes is shown in Table 1.Table 1
Security comparisons.
B
11
B
12
B
13
S
P
B
21
B
22
B
23
S
P
Gong et al.’s scheme [21]
×
√
×
S
√
×
×
W
Liu et al.’s scheme [25]
√
√
√
S
×
×
×
W
Li et al.’s scheme [29]
√
√
√
S
√
√
√
S
Our proposed scheme
√
√
√
S
√
√
√
SFrom Table1, we can find that the first two schemes (i.e., Gong et al.’s scheme [21] and Liu et al.’s scheme [25]) cannot meet all security attributes. Especially for Gong et al.’s two CLAS schemes [21], under the attacks of Ai and Aii adversaries, none of them could satisfy the security level of B3. In contrast, Li’s CLAS scheme and our proposed CLAS scheme can meet all the security requirements.


## 6.2. Performance Analysis

In this section, we performed a performance analysis of the newly proposed CLAS scheme by comparing the computation overhead of our scheme with that of Li et al.’s scheme. To achieve a credible security level, we selectq and p as 160-bit and 512-bit prime numbers, respectively. An Ate pairing e:G1×G1⟶G2 is used in our experiments, where G1 and G2 are two cyclic groups with the same order q, defined on the supersingular elliptic curve EFp:y2=x3+1.We have implemented Li et al.’s scheme and our new scheme with the MIRACL library [31] on a Lenovo computer with Windows 7 operating system. And its hardware configuration is Intel I5-3470 3.20 GHz CPU and 4G bytes of memory. For the sake of simplicity, we firstly define the corresponding relation-related symbol-operation-execution time, as shown in Table 2.Table 2
Symbol-operation-execution time.
Symbol
Operation
Timems
T
m
−
s
The time of executing a general hash operation inZq∗
0.0002
T
m
−
p
The time of executing a map-to-point operation inG1
9.773
T
e
c
c
−
p
a
The time of executing a point addition operation inG1
0.022
T
e
c
c
−
p
m
The time of executing a point multiplication operation inG1
3.740
T
b
p
The time of executing a bilinear pairing operation
11.515Because Setup,Partial-Key-Gen, and Private-Key-Gen phases are executed by the PKG or user, and all of them are one-time operation, we focus on the analysis and comparison of computational costs in Sign, Verify, Aggregate, and Aggregate-Verify phases. Since the addition and multiplication of numbers in Zq∗ will only generate less computational overhead, we can ignore them.In theSign phase, the user in Li et al.’s scheme needs to perform two general hash operations in Zq∗, one map-to-point hash operation in G1, three point addition operations in G1, and five point multiplication operations in G1. Therefore, the time for generating a signature in the Sign phase is 2Tm−s+Tm−p+3Tecc−pa+5Tecc−pm, whereas the user in our proposal needs to perform two general hash operations in Zq∗, one map-to-point hash operation in G1, two point addition operations in G1, and three point multiplication operations in G1. Therefore, the time for generating a signature in the Sign phase is 2Tm−s+Tm−p+2Tecc−pa+3Tecc−pm milliseconds.In theVerify phase, the verifier in Li et al.’s scheme needs to execute two general hash operations in Zq∗, two map-to-point hash operations in G1, two point addition operations in G1, two point multiplication operations in G1, and three bilinear pairing operations. Therefore, the time for verifying a signature in the Verify phase is 2Tm−s+2Tm−p+2Tecc−pa+2Tecc−pm+3Tbp, whereas the verifier in our proposal needs to perform two general hash operations in Zq∗, two map-to-point hash operations in G1, one point addition operation in G1, two point multiplication operations in G1, and three bilinear pairing operations. Therefore, the time for verifying a signature in the Verify phase is 2Tm−s+2Tm−p+Tecc−pa+2Tecc−pm+3Tbp milliseconds.In theAggregate phase, the aggregator in Li et al.’s scheme needs to execute n−1 point addition operations in G1, whereas the aggregator in our proposal needs to execute n−1 point addition operations in G1. We can find that the running time of the Aggregate phase in the two schemes is equal to n−1Tecc−pa milliseconds.In theAggregate−Verify phase, the aggregate verifier in Li et al.’s scheme needs to execute 2n general hash operations in Zq∗, n+1 map-to-point hash operations in G1, 4n−2 point addition operations in G1, 2n point multiplication operations in G1, and three bilinear pairing operations. Therefore, the running time of the Aggregate−Verify phase is 2nTm−s+n+1Tm−p+4n−2Tecc−pa+2nTecc−pm+3Tbp milliseconds, whereas the verifier in our proposal needs to perform 2n general hash operations in Zq∗, n+1 map-to-point hash operations in G1, 3n−2 point addition operations in G1, 2n point multiplication operations in G1, and three bilinear pairing operations. Therefore, the running time of the Aggregate−Verify phase is 2nTm−s+n+1Tm−p+3n−2Tecc−pa+2nTecc−pm+3Tbp milliseconds.Suppose thatn=100, that is, there are 100 signatures that need to be generated, verified, aggregated, and aggregate-verified. From the results in Figure 3, we can see that Li et al.’s scheme has the same computation overhead as our new CLAS scheme in the Aggregate phase, whereas in Sign, Verify, and Aggregate−Verify phases, the computation cost of our scheme is lower than that of Li et al.’s scheme. Especially in the Sign phase, the computation cost of our scheme is reduced by 26 percentage points compared with that of Li et al.’s scheme. In summary, our presented CLAS scheme reduces the computation cost while meeting security requirements.Figure 3
Computation cost comparisons.


## 7. Conclusion

Digital signature can provide secure routing authentication, privacy protection, integrity, and nonrepudiation. To solve the above problems, several CLAS schemes have been introduced recently. Unfortunately, most existing CLAS schemes have been found to have security flaws or have unsatisfactory performance in computation and communication costs. To avoid the above issues and better fix the problem of secure routing authentication in resource-constrained VANETs, we put forward a new CLAS scheme. The security analysis demonstrates that the new CLAS scheme is provably secure and is able to satisfy the security attributes in VANETs. The specific performance evaluation shows that the new CLAS scheme can achieve a novel security level while reducing the computation cost. Our CLAS scheme is robust against all types of attacks, which makes it more suitable for performing secure routing in resource-constrained VANETs.



---

*Source: 5276813-2020-02-12.xml*