# Reattack of a Certificateless Aggregate Signature Scheme with Constant Pairing Computations

Authors: Hang Tu; Debiao He; Baojun Huang
Journal: The Scientific World Journal
 (2014)

---

## Abstract

A new attack against a novel certificateless aggregate signature scheme with constant pairing computations is presented. To enhance security, a new certificateless signature scheme is proposed first. Then a new certificateless aggregate signature scheme with constant pairing computations based on the new certificateless signature scheme is presented. Security analysis shows that the proposed certificateless aggregate signature scheme is provably secured in the random oracle.


---

## Body

## 1. Introduction

The concept of aggregate signature (AS) scheme was first introduced by Boneh et al. [1] in 2003. Such a scheme greatly reduces the computational and communication overhead since it could aggregate n signatures on n distinct messages from n distinct users into a single signature and check the correctness through a verification operation. The AS scheme is very useful in real-world applications. For example, in the scenario of the secure Border Gateway Protocol (BGP) [2], each router successively signs its own segment of a path in the network and then forwards the collection of signatures associated with the path to the next router. The AS scheme can be used to compress these signatures into a single one and hence reduce the overheads of both bandwidth and computation required in the original secure BGP. Similarly, in the scenario of the Vehicular Ad Hoc Networks (VANETs) [3], each vehicle or roadside unit (RSU) has to verify around 500–2000 messages per second. The AS scheme can be used to compress these messages into a single one and check the correctness through a verification operation. To satisfy different applications, many AS schemes based on the traditional public key cryptography (TPKC) and identity-based public key cryptography (ID-based PKC) have been proposed.It is well known that a certificate, generated by a trusted third party, is needed to bind a user’s identity and its public key in the TPKC. However, the management of these certificates becomes more and more difficult with the growth of users’ number. To solve the problem, Shamir [4] introduced the concept of the ID-based PKC. In such cryptography, the user’s identity, such as name, email address, and telephone number, is his public key and his private key is generated by the key generation centre (KGC) using his identity. However, the key escrow problem exists in the ID-based PKC since the KGC know the user’s private key. In 2003, Al-Riyami and Paterson [5] developed the concept of the CLPKC to solve the key escrow problem in the ID-PKC. In CLPKC, the KGC only generates a partial private key for a user and the full private key of the user is a combination of his partial private key and some secret value chosen by the user himself. Recently, CLPKC attracted much attention and many certificateless encryption (CLE) schemes [6–8], certificateless key agreement (CLKA) schemes [9–11], certificateless signcryption (CLSC) schemes [12, 13], and certificateless signature (CLS) schemes [14–16] were proposed.To satisfy the applications in certificateless environment, the certificateless aggregate signature (CLAS) scheme has attracted much attention. Several CLAS schemes [17–23] have been proposed by different researchers. However, most of these schemes [17–20, 23] have computational complexity for pairing computations that grows linearly with the number of signers, which deviates from the main goals of aggregate signatures. Besides, both of the schemes [20, 22] of Zhang et al. require certain synchronization; that is, all signers must share the same synchronized clocks to generate aggregate signature. It is easy to say that it is difficult to achieve synchronization in many communication scenarios. Shim [24] pointed out that L. Zhang and F. Zhang’s scheme [20] is vulnerable to the coalition attack. Xiong et al. [25] found that Hu et al.’s scheme [21] cannot provide unforgeability. Very recently, Xiong et al. [25] proposed a certificateless signature (CLS) scheme and constructed a new CLAS scheme using that CLS scheme. Compared to previous CLAS schemes, Xiong et al.’s CLAS scheme is very efficient in computation, and the verification procedure needs only a very small constant number of pairing operations, independent of the number of aggregated signatures. Besides, their scheme does not require synchronization for aggregating randomness. Unfortunately, He et al. [26] pointed out that Xiong et al.’s CLAS scheme is insecure against a Type II adversary by giving concrete attack. However, He et al. did not give countermeasure to enhance security. In this paper, we propose a new attack against Xiong et al.’s CLAS scheme; that is, a Type II adversary could forge legal signature for any message. To improve security, we also propose an improved CLAS scheme.The organization of the paper is sketched as follows. Section2 gives some preliminaries of the paper. Sections 3 and 4 review and analyze Xiong et al.’s scheme. Section 5 gives our improved scheme. Sections 6 and 7 discuss security and performance analysis of our scheme. At last, we give some conclusion in Section 8.


## 2. Preliminaries

### 2.1. Bilinear Pairing

LetG1 be a cyclic additive group of prime order q and G2 a cyclic multiplicative group of the same order q. We let P denote the generator of G1. A bilinear pairing is a map e:G1×G1→G2 which satisfies the following properties.(1)
Bilinearity(1)e(aQ,bR)=e(Q,R)ab,where Q,R∈G1, a,b∈Zq*.(2)
Nondegeneracy(2)e(P,P)≠1G2.(3)
Computability: there is an efficient algorithm to computee(Q,R) for all Q,R∈G1.The Weil and Tate pairings associated with supersingular elliptic curves or abelian varieties can be modified to create such admissible pairings. The following problems are assumed to be intractable within polynomial time.Computational Diffie-Hellman (CDH) Problem. Given aP,bP∈G1, the task of CDH problem is to compute abP, where P denotes the generator of G1.


### 2.2. Formal Model of CLS and CLAS

In this subsection, we will review the definition and security notions specified in [25], only with slight notational differences. There are two kinds of adversaries in the CLS scheme and the CLAS scheme, that is, the Type I adversary 𝒜1 and the Type II adversary 𝒜2. The adversary 𝒜1 is not able to access the master key but he could replace public keys at his will. The adversary 𝒜2 represents a malicious KGC who generates partial private key of users. 𝒜2 could have access to the master key of KGC, but he is not able to replace public keys. The following are five oracles which can be accessed by the adversaries.(i)
CreateUser: Given an identity IDi, if IDi has already been created, nothing is to be carried out. Otherwise, the oracle generates the partial private key pskIDi, the secret key uskIDi, and the public key upkIDi. It then stores the tuple (IDi,pskIDi,upkIDi,uskIDi) into a list L. In both cases, pskIDi is returned.(ii)
RevealPartialKey: On input of an identity IDi, the oracle searches L for a corresponding entry to IDi. If it is not found, ⊥ is returned; otherwise, the corresponding pskIDi is returned.(iii)
RevealSecertKey: On input of an identity IDi, the oracle searches L for a corresponding entry to IDi. If it is not found, ⊥ is returned; otherwise, the corresponding uskIDi is returned.(iv)
ReplaceKey: On input of an identity IDi and a user public/secret key pair (upkIDi′,uskIDi′), the oracle searches L for the entry of IDi. If it is not found, nothing will be carried out. Otherwise, the oracle updates (IDi,pskIDi,upkIDi,uskIDi) to (IDi,pskIDi,upkIDi′,uskIDi′).(v)
Sign: On input of a message mi for IDi, the signing oracle proceeds in one of the three cases below.
(a)
A valid signatureσi returned if IDi has been created but the user public/secret key pair (uskIDi,upkIDi) has not been replaced.(b)
IfIDi has not been created, a symbol ⊥ is returned.(c)
If the user public/secret key pair ofIDi has been replaced with say (upkIDi′,uskIDi′), then the oracle returns the result of Sign(uskIDi′,pskIDi′,mi).The security for a CLS scheme and a CLAS scheme is defined via the following two games separately.Game 1.
The first game is performed between a challenger𝒞 and an adversary 𝒜∈{𝒜1,𝒜2} for a CLS scheme as follows.(i)
𝒞 executesMasterKeyGen to get master private/public key pair (mpk,msk).(ii)
𝒜 can adaptively issue theCreateUser,RevealPartialKey,RevealSecertKey,ReplaceKey, and Sign queries to 𝒞.(iii)
𝒜 is to output a message mi* and a signature σi* corresponding to a target identity IDi* and a public key upkIDi*.We say that𝒜 wins Game 1, if and only if the following three conditions hold.(1)
σi* is a valid signature on messages mi* under identities IDi* and the corresponding public key upkIDi*.(2)
If𝒜 is 𝒜1, the identity IDi* has not submitted toRevealPartialKey queries to get the partial private key pskIDi*. If 𝒜 is 𝒜2, IDi* has not submitted toRevealSecertKey queries orReplaceKey queries to get the secret key uskIDi*.(3)
The oracleSign has never been queried with (IDi*,mi*).Definition 1.
A CLS scheme is said to be secure if there is no probabilistic polynomial-time adversary𝒜∈{𝒜1,𝒜2}, which wins Game 1 with nonnegligible advantage.Game 2.
The second game is performed between a challenger𝒞 and an adversary 𝒜∈{𝒜1,𝒜2} for a CLAS scheme as follows.(i)
𝒞 executesMasterKeyGen to get master private/public key pair (mpk,msk).(ii)
𝒜 can adaptively issue theCreateUser,RevealPartialKey,RevealSecertKey,ReplaceKey, andSign queries to 𝒞.(iii)
𝒜 outputs a set of n users whose identities are from the set LID*={ID1*,…,IDn*} and corresponding public keys from the set Lupk*={upk1*,…,upkn*}, n messages Lm*={m1*,…,mn*}, and an aggregate signature σ*.We say that𝒜 wins Game 2, if and only if the following three conditions hold.(1)
σi* is a valid aggregate signature on messages {m1*,…,mn*} under identities {ID1*,…,IDn*} and the corresponding public key {upk1*,…,upkn*}.(2)
If𝒜 is 𝒜1, at least one of the identities IDi* has not submitted toRevealPartialKey queries to get the partial private key pskIDi*. If 𝒜 is 𝒜2, at least one of IDi* has not been submitted toRevealSecertKey queries orReplaceKey queries to get the secret key uskIDi*.(3)
The oracleSign has never been queried with (IDi*,mi*).Definition 2.
A CLAS scheme is said to be secure if there is no probabilistic polynomial-time adversary𝒜∈{𝒜1,𝒜2}, which wins Game 2 with nonnegligible advantage.


## 2.1. Bilinear Pairing

LetG1 be a cyclic additive group of prime order q and G2 a cyclic multiplicative group of the same order q. We let P denote the generator of G1. A bilinear pairing is a map e:G1×G1→G2 which satisfies the following properties.(1)
Bilinearity(1)e(aQ,bR)=e(Q,R)ab,where Q,R∈G1, a,b∈Zq*.(2)
Nondegeneracy(2)e(P,P)≠1G2.(3)
Computability: there is an efficient algorithm to computee(Q,R) for all Q,R∈G1.The Weil and Tate pairings associated with supersingular elliptic curves or abelian varieties can be modified to create such admissible pairings. The following problems are assumed to be intractable within polynomial time.Computational Diffie-Hellman (CDH) Problem. Given aP,bP∈G1, the task of CDH problem is to compute abP, where P denotes the generator of G1.


## 2.2. Formal Model of CLS and CLAS

In this subsection, we will review the definition and security notions specified in [25], only with slight notational differences. There are two kinds of adversaries in the CLS scheme and the CLAS scheme, that is, the Type I adversary 𝒜1 and the Type II adversary 𝒜2. The adversary 𝒜1 is not able to access the master key but he could replace public keys at his will. The adversary 𝒜2 represents a malicious KGC who generates partial private key of users. 𝒜2 could have access to the master key of KGC, but he is not able to replace public keys. The following are five oracles which can be accessed by the adversaries.(i)
CreateUser: Given an identity IDi, if IDi has already been created, nothing is to be carried out. Otherwise, the oracle generates the partial private key pskIDi, the secret key uskIDi, and the public key upkIDi. It then stores the tuple (IDi,pskIDi,upkIDi,uskIDi) into a list L. In both cases, pskIDi is returned.(ii)
RevealPartialKey: On input of an identity IDi, the oracle searches L for a corresponding entry to IDi. If it is not found, ⊥ is returned; otherwise, the corresponding pskIDi is returned.(iii)
RevealSecertKey: On input of an identity IDi, the oracle searches L for a corresponding entry to IDi. If it is not found, ⊥ is returned; otherwise, the corresponding uskIDi is returned.(iv)
ReplaceKey: On input of an identity IDi and a user public/secret key pair (upkIDi′,uskIDi′), the oracle searches L for the entry of IDi. If it is not found, nothing will be carried out. Otherwise, the oracle updates (IDi,pskIDi,upkIDi,uskIDi) to (IDi,pskIDi,upkIDi′,uskIDi′).(v)
Sign: On input of a message mi for IDi, the signing oracle proceeds in one of the three cases below.
(a)
A valid signatureσi returned if IDi has been created but the user public/secret key pair (uskIDi,upkIDi) has not been replaced.(b)
IfIDi has not been created, a symbol ⊥ is returned.(c)
If the user public/secret key pair ofIDi has been replaced with say (upkIDi′,uskIDi′), then the oracle returns the result of Sign(uskIDi′,pskIDi′,mi).The security for a CLS scheme and a CLAS scheme is defined via the following two games separately.Game 1.
The first game is performed between a challenger𝒞 and an adversary 𝒜∈{𝒜1,𝒜2} for a CLS scheme as follows.(i)
𝒞 executesMasterKeyGen to get master private/public key pair (mpk,msk).(ii)
𝒜 can adaptively issue theCreateUser,RevealPartialKey,RevealSecertKey,ReplaceKey, and Sign queries to 𝒞.(iii)
𝒜 is to output a message mi* and a signature σi* corresponding to a target identity IDi* and a public key upkIDi*.We say that𝒜 wins Game 1, if and only if the following three conditions hold.(1)
σi* is a valid signature on messages mi* under identities IDi* and the corresponding public key upkIDi*.(2)
If𝒜 is 𝒜1, the identity IDi* has not submitted toRevealPartialKey queries to get the partial private key pskIDi*. If 𝒜 is 𝒜2, IDi* has not submitted toRevealSecertKey queries orReplaceKey queries to get the secret key uskIDi*.(3)
The oracleSign has never been queried with (IDi*,mi*).Definition 1.
A CLS scheme is said to be secure if there is no probabilistic polynomial-time adversary𝒜∈{𝒜1,𝒜2}, which wins Game 1 with nonnegligible advantage.Game 2.
The second game is performed between a challenger𝒞 and an adversary 𝒜∈{𝒜1,𝒜2} for a CLAS scheme as follows.(i)
𝒞 executesMasterKeyGen to get master private/public key pair (mpk,msk).(ii)
𝒜 can adaptively issue theCreateUser,RevealPartialKey,RevealSecertKey,ReplaceKey, andSign queries to 𝒞.(iii)
𝒜 outputs a set of n users whose identities are from the set LID*={ID1*,…,IDn*} and corresponding public keys from the set Lupk*={upk1*,…,upkn*}, n messages Lm*={m1*,…,mn*}, and an aggregate signature σ*.We say that𝒜 wins Game 2, if and only if the following three conditions hold.(1)
σi* is a valid aggregate signature on messages {m1*,…,mn*} under identities {ID1*,…,IDn*} and the corresponding public key {upk1*,…,upkn*}.(2)
If𝒜 is 𝒜1, at least one of the identities IDi* has not submitted toRevealPartialKey queries to get the partial private key pskIDi*. If 𝒜 is 𝒜2, at least one of IDi* has not been submitted toRevealSecertKey queries orReplaceKey queries to get the secret key uskIDi*.(3)
The oracleSign has never been queried with (IDi*,mi*).Definition 2.
A CLAS scheme is said to be secure if there is no probabilistic polynomial-time adversary𝒜∈{𝒜1,𝒜2}, which wins Game 2 with nonnegligible advantage.


## 3. Review of Xiong et al.’s Schemes

### 3.1. Xiong et al.’s CLS Scheme

In this subsection, we will briefly review Xiong et al.’s CLS scheme. Their CLS scheme consists of five algorithms:MasterKeyGen,PartialKeyGen, UserKeyGen, Sign, andVerify. The detail of these algorithms is described as follows.MasterKeyGen. Given a security parameter k, KGC runs the algorithm as follows.(1)
Generate a cyclic additive groupG1 and a cyclic multiplicative group G2 with prime order q.(2)
Generate two generatorsP, Q of G1 and an admissible pairing e:G1×G1→G2.(3)
Generate a random numbers∈Zq* and compute Ppub=sP.(4)
Choose cryptographic hash functionsH1:{0,1}*→G1 and H2:{0,1}*→Zq*.(5)
KGC publishes the system parameters{q,G1,G2,e,P,Q,Ppub,H1,H2} and key the master key s secretly.PartialKeyGen. Given a user’s identity IDi, KGC computes the user’s partial private key pskIDi=sQIDi and transmits it to the user secretly, where QIDi=H1(IDi).UserKeyGen. The user with identity IDi selects a random number xIDi∈Zq* as his secret key uskIDi and computes his public key as upkIDi=uskIDi·P.Sign. Given a message mi, the partial private key pskIDi, the secret key uskIDi, the user with identity IDi, and the corresponding public key upkIDi, perform the following steps to generate a signature.(1)
Generate a random numberri∈Zq* and compute Ui=riP.(2)
Computehi=H2(mi,IDi,upkIDi,Ui), Vi=pskIDi+hi·ri·Ppub+hi·xIDi·Q.(3)
Output (Ui,Vi) as the signature on mi.Verify. Given a signature (Ui,Vi) of message mi on identity IDi and corresponding public key upkIDi:   (1)
ComputeQIDi=H1(IDi) and hi=H2(mi,IDi,upkIDi,Ui).(2)
Verifye(Vi,P)=e(hi·Ui+QIDi,Ppub)e(hi·upkIDi,Q) holds or not. If it holds, accept the signature.


### 3.2. Xiong et al.’s CLAS Scheme

In this subsection, we will briefly review Xiong et al.’s CLAS scheme. Their CLAS scheme consists of six algorithms:MasterKeyGen, PartialKeyGen, UserKeyGen, Sign, Aggregate, andAggregateVerify. The first four algorithms are the same as those in their CLS scheme. The detail of the other two algorithms is described as follows.Aggregate. For an aggregating set of n users {𝒰1,…,𝒰n} with identities {ID1,…,IDn}, corresponding public keys {upk1,…,upkn}, and message-signature pairs {(m1,σ1=(U1,V1)),…,(mn,σn=(Un,Vn))} from {𝒰1,…,𝒰n}, respectively, the aggregate signature generator computes V=∑i=1nVi and outputs σ=(U1,…,U2,V) as an aggregate signature.AggregateVerify. To verify an aggregate signature σ=(U1,…,U2,V) signed by n users {𝒰1,…,𝒰n} with identities {ID1,…,IDn} and the corresponding public keys {upk1,…,upkn} on messages {m1,…,mn}, the verifier performs the following steps.(1)
ComputeQIDi=H1(IDi) and hi=H2(mi,IDi,upkIDi,Ui) for i=1,…,n.(2)
Verifye(V,P)=e(∑i=1n(hi·Ui+QIDi),Ppub)e(∑i=1nhi·upkIDi,Q) holds or not. If it holds, accept the signature.


## 3.1. Xiong et al.’s CLS Scheme

In this subsection, we will briefly review Xiong et al.’s CLS scheme. Their CLS scheme consists of five algorithms:MasterKeyGen,PartialKeyGen, UserKeyGen, Sign, andVerify. The detail of these algorithms is described as follows.MasterKeyGen. Given a security parameter k, KGC runs the algorithm as follows.(1)
Generate a cyclic additive groupG1 and a cyclic multiplicative group G2 with prime order q.(2)
Generate two generatorsP, Q of G1 and an admissible pairing e:G1×G1→G2.(3)
Generate a random numbers∈Zq* and compute Ppub=sP.(4)
Choose cryptographic hash functionsH1:{0,1}*→G1 and H2:{0,1}*→Zq*.(5)
KGC publishes the system parameters{q,G1,G2,e,P,Q,Ppub,H1,H2} and key the master key s secretly.PartialKeyGen. Given a user’s identity IDi, KGC computes the user’s partial private key pskIDi=sQIDi and transmits it to the user secretly, where QIDi=H1(IDi).UserKeyGen. The user with identity IDi selects a random number xIDi∈Zq* as his secret key uskIDi and computes his public key as upkIDi=uskIDi·P.Sign. Given a message mi, the partial private key pskIDi, the secret key uskIDi, the user with identity IDi, and the corresponding public key upkIDi, perform the following steps to generate a signature.(1)
Generate a random numberri∈Zq* and compute Ui=riP.(2)
Computehi=H2(mi,IDi,upkIDi,Ui), Vi=pskIDi+hi·ri·Ppub+hi·xIDi·Q.(3)
Output (Ui,Vi) as the signature on mi.Verify. Given a signature (Ui,Vi) of message mi on identity IDi and corresponding public key upkIDi:   (1)
ComputeQIDi=H1(IDi) and hi=H2(mi,IDi,upkIDi,Ui).(2)
Verifye(Vi,P)=e(hi·Ui+QIDi,Ppub)e(hi·upkIDi,Q) holds or not. If it holds, accept the signature.


## 3.2. Xiong et al.’s CLAS Scheme

In this subsection, we will briefly review Xiong et al.’s CLAS scheme. Their CLAS scheme consists of six algorithms:MasterKeyGen, PartialKeyGen, UserKeyGen, Sign, Aggregate, andAggregateVerify. The first four algorithms are the same as those in their CLS scheme. The detail of the other two algorithms is described as follows.Aggregate. For an aggregating set of n users {𝒰1,…,𝒰n} with identities {ID1,…,IDn}, corresponding public keys {upk1,…,upkn}, and message-signature pairs {(m1,σ1=(U1,V1)),…,(mn,σn=(Un,Vn))} from {𝒰1,…,𝒰n}, respectively, the aggregate signature generator computes V=∑i=1nVi and outputs σ=(U1,…,U2,V) as an aggregate signature.AggregateVerify. To verify an aggregate signature σ=(U1,…,U2,V) signed by n users {𝒰1,…,𝒰n} with identities {ID1,…,IDn} and the corresponding public keys {upk1,…,upkn} on messages {m1,…,mn}, the verifier performs the following steps.(1)
ComputeQIDi=H1(IDi) and hi=H2(mi,IDi,upkIDi,Ui) for i=1,…,n.(2)
Verifye(V,P)=e(∑i=1n(hi·Ui+QIDi),Ppub)e(∑i=1nhi·upkIDi,Q) holds or not. If it holds, accept the signature.


## 4. Cryptanalysis of Xiong et al.’s Scheme

Shim [24] claimed that both of their schemes are provably secure against two types of adversary in the random oracle model. However, in this section, we will disprove their claims by giving two concrete attacks.


### 4.1. Attack against Xiong et al.’s CLS Scheme

Shim [24] claimed their CLS scheme is semantically secure against Type II adversary. Unfortunately, it is not true, since there is a polynomial time Type II adversary 𝒜2 who can always win Game 1 through either of the following two attacks.In Xiong et al.’s CLS scheme, the system parameters{q,G1,G2,e,P,Q,Ppub,H1,H2} are generated by KGC. Let a Type II adversary 𝒜2 be a malicious KGC. Then 𝒜2 could choose a random t and compute Q=tP, when he generates the system parameters. After that, 𝒜2 could forge a legal signature of any message.(1)
The Type II adversary𝒜2 has the master key s. Then, he could compute a user 𝒰i’s partial private key pskIDi=sQIDi, where QIDi=H1(IDi).(2)
For any messagemi, 𝒜2 generates a random number ri∈Zq* and computes Ui=riP, hi=H2(mi,IDi,upkIDi,Ui) and Vi=pskIDi+hi·ri·Ppub+hi·t·upkIDi.(3)
𝒜2 outputs (Ui,Vi) as the signature on mi.SinceQ=tP, Ui=riP, and Vi=pskIDi+hi·ri·Ppub+hi·t·upkIDi, we could have
(3)e(Vi,P)=e(Vi=pskIDi+hi·ri·Ppub+hi·t·upkIDi,P)=e(pskIDi+hi·ri·Ppub,P)e(hi·t·upkIDi,P)=e(sQIDi+hi·ri·sP,P)e(hi·upkIDi,t·P)=e(hi·Ui+QIDi,sP)e(hi·upkIDi,Q)=e(hi·Ui+QIDi,Ppub)e(hi·upkIDi,Q).Then, we know that (Ui,Vi) is a legal signature on mi. Besides, IDi has not been submitted toRevealSecertKey queries orReplaceKey queries to get the secret key uskIDi* and the oracle Sign has never been queried with (IDi,mi). So the Type II adversary 𝒜2 wins Game 1.Therefore, Xiong et al.’s CLS scheme is not secure against attacks of the Type II adversary.


### 4.2. Attack against Xiong et al.’s CLAS Scheme

Shim [24] claimed their CLAS scheme is semantically secure against Type II adversary. Unfortunately, it is not true, since there exists a polynomial time Type II adversary 𝒜2, who can always win Game 2 through either of the following two attacks.In Xiong et al.’s CLAS scheme, the system parameters{q,G1,G2,e,P,Q,Ppub,H1,H2} are generated by KGC. Let a Type II adversary 𝒜2 be a malicious KGC. Then 𝒜2 could choose a random t and compute Q=tP, when he generates the system parameters. After that, 𝒜2 could forge an aggregate signature.Let{𝒰1,…,𝒰n} be an aggregating set of n users with identities {ID1,…,IDn} and the corresponding public keys {upk1,…,upkn}.(1)
Fori=1,2,…,n, 𝒜2 does the following five substeps to generate a legal signature (Ui,Vi) on a message mi.
(i)
The Type II adversary𝒜2 has the master key s. Then, he could compute a user 𝒰i’s partial private key pskIDi=sQIDi, where QIDi=H1(IDi).(ii)
For any messagemi, 𝒜2 generates a random number ri∈Zq* and computes Ui=riP, hi=H2(mi,IDi,upkIDi,Ui), and Vi=pskIDi+hi·ri·Ppub+hi·t·upkIDi.(iii)
𝒜2 outputs (Ui,Vi) as the signature on mi.(2)
𝒜2 computes V=∑i=1nVi.(3)
𝒜2 outputs σ=(U1,…,Un,V) as an aggregate signature.From the analysis in the above subsection, we know that(Ui,Vi) satisfies the equation e(Vi,P)=e(hi·Ui+QIDi,sPpub)e(hi·upkIDi,Q), where Q=tP and Vi=pskIDi+hi·ri·Ppub+hi·t·upkIDi. Then we could have that
(4)e(V,P)=e(∑i=1nVi,P)=e(∑i=1n(pskIDi+hi·ri·Ppub+hi·t·upkIDi),P)=e(∑i=1n(pskIDi+hi·ri·Ppub),P)×e(∑i=1nhi·t·upkIDi,P)=e(∑i=1n(hi·Ui+QIDi),Ppub)×e(∑i=1nhi·upkIDi,Q).Thus, we know thatσ=(U1,…,Un,V) is a legal aggregate signature on messages {m1,…,mn}. Besides, for any i∈{1,…,n},IDi has not been submitted toRevealSecertKey queries orReplaceKey queries to get the secret key uskIDi* and the oracleSign has never been queried with (IDi,mi). So the Type II adversary 𝒜2 wins Game 2.Therefore, Xiong et al.’s CLAS scheme is not secure against attacks of the Type II adversary.


## 4.1. Attack against Xiong et al.’s CLS Scheme

Shim [24] claimed their CLS scheme is semantically secure against Type II adversary. Unfortunately, it is not true, since there is a polynomial time Type II adversary 𝒜2 who can always win Game 1 through either of the following two attacks.In Xiong et al.’s CLS scheme, the system parameters{q,G1,G2,e,P,Q,Ppub,H1,H2} are generated by KGC. Let a Type II adversary 𝒜2 be a malicious KGC. Then 𝒜2 could choose a random t and compute Q=tP, when he generates the system parameters. After that, 𝒜2 could forge a legal signature of any message.(1)
The Type II adversary𝒜2 has the master key s. Then, he could compute a user 𝒰i’s partial private key pskIDi=sQIDi, where QIDi=H1(IDi).(2)
For any messagemi, 𝒜2 generates a random number ri∈Zq* and computes Ui=riP, hi=H2(mi,IDi,upkIDi,Ui) and Vi=pskIDi+hi·ri·Ppub+hi·t·upkIDi.(3)
𝒜2 outputs (Ui,Vi) as the signature on mi.SinceQ=tP, Ui=riP, and Vi=pskIDi+hi·ri·Ppub+hi·t·upkIDi, we could have
(3)e(Vi,P)=e(Vi=pskIDi+hi·ri·Ppub+hi·t·upkIDi,P)=e(pskIDi+hi·ri·Ppub,P)e(hi·t·upkIDi,P)=e(sQIDi+hi·ri·sP,P)e(hi·upkIDi,t·P)=e(hi·Ui+QIDi,sP)e(hi·upkIDi,Q)=e(hi·Ui+QIDi,Ppub)e(hi·upkIDi,Q).Then, we know that (Ui,Vi) is a legal signature on mi. Besides, IDi has not been submitted toRevealSecertKey queries orReplaceKey queries to get the secret key uskIDi* and the oracle Sign has never been queried with (IDi,mi). So the Type II adversary 𝒜2 wins Game 1.Therefore, Xiong et al.’s CLS scheme is not secure against attacks of the Type II adversary.


## 4.2. Attack against Xiong et al.’s CLAS Scheme

Shim [24] claimed their CLAS scheme is semantically secure against Type II adversary. Unfortunately, it is not true, since there exists a polynomial time Type II adversary 𝒜2, who can always win Game 2 through either of the following two attacks.In Xiong et al.’s CLAS scheme, the system parameters{q,G1,G2,e,P,Q,Ppub,H1,H2} are generated by KGC. Let a Type II adversary 𝒜2 be a malicious KGC. Then 𝒜2 could choose a random t and compute Q=tP, when he generates the system parameters. After that, 𝒜2 could forge an aggregate signature.Let{𝒰1,…,𝒰n} be an aggregating set of n users with identities {ID1,…,IDn} and the corresponding public keys {upk1,…,upkn}.(1)
Fori=1,2,…,n, 𝒜2 does the following five substeps to generate a legal signature (Ui,Vi) on a message mi.
(i)
The Type II adversary𝒜2 has the master key s. Then, he could compute a user 𝒰i’s partial private key pskIDi=sQIDi, where QIDi=H1(IDi).(ii)
For any messagemi, 𝒜2 generates a random number ri∈Zq* and computes Ui=riP, hi=H2(mi,IDi,upkIDi,Ui), and Vi=pskIDi+hi·ri·Ppub+hi·t·upkIDi.(iii)
𝒜2 outputs (Ui,Vi) as the signature on mi.(2)
𝒜2 computes V=∑i=1nVi.(3)
𝒜2 outputs σ=(U1,…,Un,V) as an aggregate signature.From the analysis in the above subsection, we know that(Ui,Vi) satisfies the equation e(Vi,P)=e(hi·Ui+QIDi,sPpub)e(hi·upkIDi,Q), where Q=tP and Vi=pskIDi+hi·ri·Ppub+hi·t·upkIDi. Then we could have that
(4)e(V,P)=e(∑i=1nVi,P)=e(∑i=1n(pskIDi+hi·ri·Ppub+hi·t·upkIDi),P)=e(∑i=1n(pskIDi+hi·ri·Ppub),P)×e(∑i=1nhi·t·upkIDi,P)=e(∑i=1n(hi·Ui+QIDi),Ppub)×e(∑i=1nhi·upkIDi,Q).Thus, we know thatσ=(U1,…,Un,V) is a legal aggregate signature on messages {m1,…,mn}. Besides, for any i∈{1,…,n},IDi has not been submitted toRevealSecertKey queries orReplaceKey queries to get the secret key uskIDi* and the oracleSign has never been queried with (IDi,mi). So the Type II adversary 𝒜2 wins Game 2.Therefore, Xiong et al.’s CLAS scheme is not secure against attacks of the Type II adversary.


## 5. Our CLS Scheme and CLAS Scheme

### 5.1. Our CLS Scheme

Like Xiong et al.’s CLS scheme does, our CLS scheme also consists of five algorithms:MasterKeyGen, PartialKeyGen, UserKeyGen, Sign, andVerify. The detail of these algorithms is described as follows.MasterKeyGen. Given a security parameter k, KGC runs the algorithm as follows.(1)
Generate a cyclic additive groupG1 and a cyclic multiplicative group G2 with prime order q.(2)
Generate a generatorP of G1 and an admissible pairing e:G1×G1→G2.(3)
Generate a random numbers∈Zq* and compute Ppub=sP.(4)
Choose cryptographic hash functionsH1,H2,H3:{0,1}*→G1 and H4,H5:{0,1}*→Zq*.(5)
KGC publishes the system parametersparams={q,G1,G2,e,P,Ppub,H1,H2,H3,H4,H5} and key the master key s secretly.PartialKeyGen. Given a user’s identity IDi, KGC computes the user’s partial private key pskIDi=sQIDi and transmits it to the user secretly, where QIDi=H1(IDi).UserKeyGen. The user with identity IDi selects a random number xIDi∈Zq* as his secret key uskIDi and computes his public key as upkIDi=uskIDi·P.Sign. Given a message mi, the partial private key pskIDi, the secret key uskIDi, the user with identity IDi, and the corresponding public key upkIDi, perform the following steps to generate a signature.(1)
Generate a random numberri∈Zq* and compute Ui=riP.(2)
ComputeW=H2(params), T=H3(params), hi=H4(mi,IDi,upkIDi,Ui), and ki=H5(mi,IDi,upkIDi,Ui).(3)
Compute,Vi=pskIDi+hi·xIDi·W+ki·ri·T.(4)
Output (Ui,Vi) as the signature on mi.Verify. Given a signature (Ui,Vi) of message mi on identity IDi and corresponding public key upkIDi, consider the following.(1)
ComputeQIDi=H1(IDi), W=H2(params), T=H3(params), hi=H4(mi,IDi,upkIDi,Ui), and ki=H5(mi,IDi,upkIDi,Ui).(2)
Verifye(Vi,P)=e(QIDi,Ppub)e(hi·upkIDi,W)e(kiUi,T) holds or not. If it holds, accept the signature.


### 5.2. Our CLAS Scheme

Like Xiong et al.’s CLAS scheme does, our CLAS scheme also consists of six algorithms:MasterKeyGen, PartialKeyGen, UserKeyGen, Sign, Aggregate, andAggregateVerify. The first four algorithms are the same as those in our CLS scheme. The detail of other two algorithms is described as follows.Aggregate. For an aggregating set of n users {𝒰1,…,𝒰n} with identities {ID1,…,IDn}, corresponding public keys {upk1,…,upkn}, and message-signature pairs {(m1,σ1=(U1,V1)),…,(mn,σn=(Un,Vn))} from {𝒰1,…,𝒰n}, respectively, the aggregate signature generator computes V=∑i=1nVi and outputs σ=(U1,…,Un,V) as an aggregate signature.AggregateVerify. To verify an aggregate signature σ=(U1,…,Un,V) signed by n users {𝒰1,…,𝒰n} with identities {ID1,…,IDn} and the corresponding public keys {upk1,…,upkn} on messages {m1,…,mn}, the verifier performs the following steps.(1)
ComputeQIDi=H1(IDi), W=H2(params), T=H3(params), hi=H4(mi,IDi,upkIDi,Ui), and ki=H5(mi,IDi,upkIDi,Ui) for i=1,…,n.(2)
Verifye(V,P)=e(∑i=1nQIDi,Ppub)e(∑i=1nhi·upkIDi,Q)e(∑i=1nki·Ui,T) holds or not. If it holds, accept the signature.


## 5.1. Our CLS Scheme

Like Xiong et al.’s CLS scheme does, our CLS scheme also consists of five algorithms:MasterKeyGen, PartialKeyGen, UserKeyGen, Sign, andVerify. The detail of these algorithms is described as follows.MasterKeyGen. Given a security parameter k, KGC runs the algorithm as follows.(1)
Generate a cyclic additive groupG1 and a cyclic multiplicative group G2 with prime order q.(2)
Generate a generatorP of G1 and an admissible pairing e:G1×G1→G2.(3)
Generate a random numbers∈Zq* and compute Ppub=sP.(4)
Choose cryptographic hash functionsH1,H2,H3:{0,1}*→G1 and H4,H5:{0,1}*→Zq*.(5)
KGC publishes the system parametersparams={q,G1,G2,e,P,Ppub,H1,H2,H3,H4,H5} and key the master key s secretly.PartialKeyGen. Given a user’s identity IDi, KGC computes the user’s partial private key pskIDi=sQIDi and transmits it to the user secretly, where QIDi=H1(IDi).UserKeyGen. The user with identity IDi selects a random number xIDi∈Zq* as his secret key uskIDi and computes his public key as upkIDi=uskIDi·P.Sign. Given a message mi, the partial private key pskIDi, the secret key uskIDi, the user with identity IDi, and the corresponding public key upkIDi, perform the following steps to generate a signature.(1)
Generate a random numberri∈Zq* and compute Ui=riP.(2)
ComputeW=H2(params), T=H3(params), hi=H4(mi,IDi,upkIDi,Ui), and ki=H5(mi,IDi,upkIDi,Ui).(3)
Compute,Vi=pskIDi+hi·xIDi·W+ki·ri·T.(4)
Output (Ui,Vi) as the signature on mi.Verify. Given a signature (Ui,Vi) of message mi on identity IDi and corresponding public key upkIDi, consider the following.(1)
ComputeQIDi=H1(IDi), W=H2(params), T=H3(params), hi=H4(mi,IDi,upkIDi,Ui), and ki=H5(mi,IDi,upkIDi,Ui).(2)
Verifye(Vi,P)=e(QIDi,Ppub)e(hi·upkIDi,W)e(kiUi,T) holds or not. If it holds, accept the signature.


## 5.2. Our CLAS Scheme

Like Xiong et al.’s CLAS scheme does, our CLAS scheme also consists of six algorithms:MasterKeyGen, PartialKeyGen, UserKeyGen, Sign, Aggregate, andAggregateVerify. The first four algorithms are the same as those in our CLS scheme. The detail of other two algorithms is described as follows.Aggregate. For an aggregating set of n users {𝒰1,…,𝒰n} with identities {ID1,…,IDn}, corresponding public keys {upk1,…,upkn}, and message-signature pairs {(m1,σ1=(U1,V1)),…,(mn,σn=(Un,Vn))} from {𝒰1,…,𝒰n}, respectively, the aggregate signature generator computes V=∑i=1nVi and outputs σ=(U1,…,Un,V) as an aggregate signature.AggregateVerify. To verify an aggregate signature σ=(U1,…,Un,V) signed by n users {𝒰1,…,𝒰n} with identities {ID1,…,IDn} and the corresponding public keys {upk1,…,upkn} on messages {m1,…,mn}, the verifier performs the following steps.(1)
ComputeQIDi=H1(IDi), W=H2(params), T=H3(params), hi=H4(mi,IDi,upkIDi,Ui), and ki=H5(mi,IDi,upkIDi,Ui) for i=1,…,n.(2)
Verifye(V,P)=e(∑i=1nQIDi,Ppub)e(∑i=1nhi·upkIDi,Q)e(∑i=1nki·Ui,T) holds or not. If it holds, accept the signature.


## 6. Security Analysis

### 6.1. Security Analysis of Our CLS Scheme

In this section, we analyze the security of our CLS scheme. The following lemmas and theorem are proposed.Lemma 3.
If Type I adversary𝒜1 wins Game 1 with nonnegligible probability ε, then one could construct an algorithm to solve the CDH problem in G1 with nonnegligible probability.Proof.
Given an instance(X=xP,Y=yP) of the CDH problem in G1, we will construct an algorithm 𝒞 to compute xyP, where x,y∈Zq* and they are unknown to 𝒞. At first, 𝒞 picks an identity IDI at random as the challenged identity in this game, sets the master public key Ppub=X, selects the system parameters params={G1,G2,e,P,Ppub,H1,H2,H3,H4,H5}, and returns the parameters to 𝒜1. Then 𝒞 answers 𝒜1’s query as follows.           (i)
H1query: 𝒞 maintains a list LH1 of form 〈IDi,aIDi,QIDi〉. When 𝒜1 makes this query on IDi, 𝒞 does as follows.
(a)
If the listLH1 contains a tuple 〈IDi,aIDi,QIDi〉, 𝒞 returns QIDi to 𝒜1.(b)
Otherwise, ifIDi=IDI, 𝒞 picks a random aIDi∈Zn*, computes QIDi=aIDiY, adds 〈IDi,aIDi,QIDi〉 to LH1, and returns QIDi to 𝒜1.(c)
Otherwise (IDi≠IDI), 𝒞 picks a random aIDi∈Zn*, computes QIDi=aIDiP, adds 〈IDi,aIDi,QIDi〉 to LH1, and returns QIDi to 𝒜1.(ii)
H2query: 𝒞 maintains a list LH2 of form 〈mi,bi,Wi〉. When 𝒜1 makes this query on mi, 𝒞 does as follows.
(a)
If the listLH2 contains a tuple 〈mi,bi,Wi〉, 𝒞 returns Wi to 𝒜1.(b)
Otherwise,𝒞 picks a random bi∈Zn*, computes Wi=biP, adds 〈mi,bi,Wi〉 to LH2, and returns Wi to 𝒜1.(iii)
H3query: 𝒞 maintains a list LH3 of form 〈mi,ci,Ti〉. When 𝒜1 makes this query on mi, 𝒞 does as follows.
(a)
If the listLH3 contains a tuple 〈mi,ci,Ti〉, 𝒞 returns Ti to 𝒜1.(b)
Otherwise,𝒞 picks a random ci∈Zn*, computes Ti=ciX, adds 〈mi,ci,Ti〉 to LH3, and returns Ti to 𝒜1.(iv)
H4query: 𝒞 maintains a list LH4 of form 〈mi,IDi,upkIDi,Ui,hi〉. When 𝒜1 makes this query on (mi,IDi,upkIDi,Ui), 𝒞 does as follows.
(a)
If the listLH4 contains a tuple 〈mi,IDi,upkIDi,Ui,hi〉, 𝒞 returns hi to 𝒜1.(b)
Otherwise,𝒞 picks a random hi∈Zn*, returns hi to 𝒜1, and adds 〈mi,IDi,upkIDi,Ui,hi〉 to LH4.(v)
H5query: 𝒞 maintains a list LH5 of form 〈mi,IDi,upkIDi,Ui,ki〉. When 𝒜1 makes this query on (mi,IDi,upkIDi,Ui), 𝒞 does as follows.
(a)
If the listLH5 contains a tuple 〈mi,IDi,upkIDi,Ui,ki〉, 𝒞 returns ki to 𝒜1.(b)
Otherwise,𝒞 picks a random ki∈Zn*, returns ki to 𝒜1, and adds 〈mi,IDi,upkIDi,Ui,hi〉 to LH5.(vi)
CreateUser: 𝒞 maintains a list LU of form 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉. When 𝒜1 makes this query on IDi, 𝒞 does as follows.
(a)
If the listLU contains a tuple 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉, 𝒞 returns upkIDi to 𝒜1.(b)
Otherwise, ifIDi=IDI, 𝒞 gets QIDI=aIDIY by making H1 query with IDI and sets pskIDI←⊥. 𝒞 selects a random number xIDi∈Zq* as his secret key uskIDi and computes his public key as upkIDi=uskIDi·P. At last, 𝒞 adds 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 to LU and returns upkIDi to 𝒜1.(c)
Otherwise (IDi≠IDI), 𝒞 gets QIDi=aIDi·P by making H1 query with IDi and sets pskIDi=aIDi·Ppub. 𝒞 selects a random number xIDi∈Zq* as his secret key uskIDi and computes his public key as upkIDi=uskIDi·P. At last, 𝒞 adds 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 to LU and returns upkIDi to 𝒜1.(vii)
RevealPartialKey: when 𝒜1 makes this query on IDi, 𝒞 does as follows.
(a)
IfIDi=IDI, 𝒞 stops the simulation.(b)
Otherwise (IDi≠IDI), 𝒞 looks up the list LU for the tuple 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 and returns pskIDi to 𝒜1.(viii)
RevealSecertKey: when 𝒜1 makes this query on IDi, 𝒞 looks up the list LU for the tuple 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 and returns uskIDi to 𝒜1.(ix)
ReplaceKey: when 𝒜1 makes this query on (IDi,upkIDi′), 𝒞 looks up the list LU for the tuple 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉. 𝒞 sets uskIDi←⊥ and replaces upkIDi with upkIDi′.(x)
Sign: when 𝒜1 makes this query on (mi,IDi), 𝒞 does as follows.
(a)
IfIDi=IDI, 𝒞 looks up lists LH1 and LU and for tuples 〈IDi,aIDi,QIDi〉 and 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 separately, where QIDi=aIDiY and upkIDi may have been replaced by 𝒜1. 𝒞 makes H2 query and H3 query with params and gets tuples 〈params,bi,W〉 and 〈params,ci,T〉, where W=biP and T=ciX. 𝒞 generates three random numbers hi,ki,ri∈Zq*, computes Ui=ki-1(ri·P-aIDi·ci-1·Y), Vi=ri·T+hi·bi·upkIDi, and sets H4(mi,IDi,upkIDi,Ui)←hi, H5(mi,IDi,upkIDi,Ui)←ki. At last, 𝒞 adds tuples 〈mi,IDi,upkIDi,Ui,hi〉 and 〈mi,IDi,upkIDi,Ui,ki〉 to LH4 and LH5 separately and returns (Ui,Vi) to 𝒜1. It is easy to say (Ui,Vi) satisfies the equation e(Vi,P)=e(QIDi,Ppub)e(hi·upkIDi,W)e(kiUi,T).(b)
Otherwise (IDi≠IDI), 𝒞 looks up lists LH1 and LU and for tuples 〈IDi,aIDi,QIDi〉 and 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 separately, where QIDi=aIDiP and upkIDi may have been replaced by (𝒜1). 𝒞 makes H2 query and H3 query with params and gets tuples 〈params,bi,W〉 and 〈params,ci,T〉, where W=biP and T=ciX. 𝒞 generates a random number ri∈Zq* and computes Ui=riP, hi=H4(mi,IDi,upkIDi,Ui), ki=H5(mi,IDi,upkIDi,Ui), and Vi=pskIDi+hi·bi·upkIDi+ki·ri·T. At last, 𝒞 returns (Ui,Vi) to 𝒜1. It is easy to say (Ui,Vi) satisfies the equation e(Vi,P)=e(QIDi,Ppub)e(hi·upkIDi,W)e(kiUi,T).
Finally,𝒜1 outputs a tuple (IDi,mi,σi) as its forgery, where σi=(Ui,Vi). If IDi≠IDI, 𝒞 stops the simulation. From the forgery lemma [27], if we have a replay of 𝒞 with the same random tape but different choice of H4 and H5, 𝒜1 will output another three signatures. The following two equations hold since both of the two signatures are valid:
(5)e(Vi,P)=e(QIDi,Ppub)e(hi·upkIDi,W)e(kiUi,T),e(Vi′,P)=e(QIDi,Ppub)e(hi′·upkIDi,W)e(ki′Ui,T).
𝒞 looks up lists LH1 and LU and for tuples 〈IDi,aIDi,QIDi〉 and 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 separately, where QIDi=aIDiP and upkIDi may have been replaced by 𝒜1. 𝒞 makes H2 query and H3 query with params and gets tuples 〈params,bi,W〉 and 〈params,ci,T〉, where W=biP and T=ciX. At last, 𝒞 returns (ki(Vi′-bi·hi′·upkIDi)-ki′(Vi-bi·hi·upkIDi))/aIDi(ki-ki′) as the solution of CDH problem.Analysis. We show that 𝒞 solves the given instance of the CDH problem with the probability η. To do so, we analyze the three events that result in 𝒞’s success.E1: 𝒞 does not abort in all the queries of RevealPartialKey.E2: 𝒜1 can forge a legal signature σi=(Ui,Vi).E3: the outputted tuple (IDi,mi,σi) satisfies IDi=IDI.From the simulation we know thatPr[E1]≥(1-(1/qH1))qRPK, Pr[E2∣E1]≥ε, Pr[E3∣E1∧E2]≥(1/qH1), where qH1 and qRPK denote the numbers of H1 queries and RevealPartialKey queries separately. Then, the probability that 𝒞 solves the CDH problem is
(6)η=Pr⁡[E1∧E2∧E3]=Pr[E1]Pr⁡[E2∣E1]Pr[E3∣E1∧E2]≥1qH1(1-1qH1)qEPPKε.Then𝒞 could solve the CDH problem with a nonnegligible probability since ε is nonnegligible. This contradicts the hardness of the CDH problem. Therefore, our CLS scheme is existentially unforgeable against Type I adversary in random oracle model under the assumption that the CDH problem is hard.Lemma 4.
If there is a Type I adversary𝒜2 wins Game 1 with nonnegligible probability ε. Then we could construct an algorithm 𝒞 to solve the CDH problem in G1 with nonnegligible probability.Proof.
Given an instance(X=xP,Y=yP) of the CDH problem in G1, we will construct an algorithm 𝒞 to compute xyP, where x,y∈Zq* and they are unknown to 𝒞. At first, 𝒞 picks an identity IDI at random as the challenged identity in this game, generates a random number s∈Zq* as the master key, sets the master public key Ppub=sP, selects the system parameters params={G1,G2,e,P,Ppub,H1,H2,H3,H4,H5}, and returns the master key and the parameters to 𝒜2. Then 𝒞 answers 𝒜2’s query as follows.            (i)
H1query: 𝒞 maintains a list LH1 of form 〈IDi,aIDi,QIDi〉. When 𝒜1 makes this query on IDi, 𝒞 does as follows.
(a)
If the listLH1 contains a tuple 〈IDi,aIDi,QIDi〉, 𝒞 returns QIDi to 𝒜2.(b)
Otherwise,𝒞 picks a random aIDi∈Zn*, computes QIDi=aIDiP, adds 〈IDi,aIDi,QIDi〉 to LH1, and returns QIDi to 𝒜2.(ii)
H2query:𝒞 maintains a list LH2 of form 〈mi,bi,Wi〉. When 𝒜2 makes this query on mi, 𝒞 does as follows.
(a)
If the listLH2 contains a tuple 〈mi,bi,Wi〉, 𝒞 returns Wi to 𝒜2.(b)
Otherwise,𝒞 picks a random bi∈Zn*, computes Wi=biX, adds 〈mi,bi,Wi〉 to LH2, and returns Wi to 𝒜2.(iii)
H3query: 𝒞 maintains a list LH3 of form 〈mi,ci,Ti〉. When 𝒜2 makes this query on mi, 𝒞 does as follows.
(a)
If the listLH3 contains a tuple 〈mi,ci,Ti〉, 𝒞 returns Ti to 𝒜2.(b)
Otherwise,𝒞 picks a random ci∈Zn*, computes Ti=ciX, adds 〈mi,ci,Ti〉 to LH3, and returns Ti to 𝒜2.(iv)
H4query: 𝒞 maintains a list LH4 of form 〈mi,IDi,upkIDi,Ui,hi〉. When 𝒜2 makes this query on (mi,IDi,upkIDi,Ui), 𝒞 does as follows.
(a)
If the listLH4 contains a tuple 〈mi,IDi,upkIDi,Ui,hi〉, 𝒞 returns hi to 𝒜2.(b)
Otherwise,𝒞 picks a random hi∈Zn*, returns hi to 𝒜2, and adds 〈mi,IDi,upkIDi,Ui,hi〉 to LH4.(v)
H5query: 𝒞 maintains a list LH5 of form 〈mi,IDi,upkIDi,Ui,ki〉. When 𝒜2 makes this query on (mi,IDi,upkIDi,Ui), 𝒞 does as follows.
(a)
If the listLH5 contains a tuple 〈mi,IDi,upkIDi,Ui,ki〉, 𝒞 returns ki to 𝒜2.(b)
Otherwise,𝒞 picks a random ki∈Zn*, returns ki to 𝒜2, and adds 〈mi,IDi,upkIDi,Ui,hi〉 to LH5.(vi)
CreateUser: 𝒞 maintains a list LU of form 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉. When 𝒜2 makes this query on IDi, 𝒞 does as follows.
(a)
If the listLU contains a tuple 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉, 𝒞 returns upkIDi to 𝒜2.(b)
Otherwise, ifIDi=IDI, 𝒞 gets QIDI=aIDIP by making H1 query with IDI and computes pskIDI=sQIDI. 𝒞 sets uskIDi←⊥ and upkIDi←Y. At last, 𝒞 adds 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 to LU and returns upkIDi to 𝒜2.(c)
Otherwise (IDi≠IDI), 𝒞 gets QIDi=aIDi·P by making H1 query with IDi and computes pskIDI=sQIDI. 𝒞 selects a random number xIDi∈Zq* as his secret key uskIDi and computes his public key as upkIDi=uskIDi·P. At last, 𝒞 adds 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 to LU and returns upkIDi to 𝒜1.(vii)
RevealPartialKey: when 𝒜2 makes this query on IDi, 𝒞 looks up the list LU for the tuple 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 and returns pskIDi to 𝒜2.(viii)
RevealSecertKey: when 𝒜2 makes this query on IDi, 𝒞 does as follows.
(a)
IfIDi=IDI, 𝒞 stops the simulation.(b)
Otherwise (IDi≠IDI), 𝒞 looks up the list LU for the tuple 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 and returns uskIDi to 𝒜2.(ix)
Sign: when 𝒜1 makes this query on (mi,IDi), 𝒞 does as follows.
(a)
IfIDi=IDI, 𝒞 looks up lists LH1 and LU and for tuples 〈IDi,aIDi,QIDi〉 and 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 separately, where QIDi=aIDiP and upkIDi may have been replaced by 𝒜2. 𝒞 makes H2 query and H3 query with params and gets tuples 〈params,bi,W〉 and 〈params,ci,T〉, where W=biX and T=ciX. 𝒞 generates three random numbers hi,ki,ri∈Zq*, computes Ui=ki-1(ri·P-bi·ci-1·hi·Y), Vi=ri·T+aIDi·s·upkIDi, and sets H4(mi,IDi,upkIDi,Ui)←hi, H5(mi,IDi,upkIDi,Ui)←ki. At last, 𝒞 adds tuples 〈mi,IDi,upkIDi,Ui,hi〉 and 〈mi,IDi,upkIDi,Ui,ki〉 to LH4 and LH5 separately and returns (Ui,Vi) to 𝒜2. It is easy to say (Ui,Vi) satisfies the equation e(Vi,P)=e(QIDi,Ppub)e(hi·upkIDi,W)e(kiUi,T).(b)
Otherwise (IDi≠IDI), 𝒞 acts according to the description of the algorithm Sign since he knows both of uskIDi and pskIDi.
Finally,𝒜2 outputs a tuple (IDi,mi,σi) as its forgery, where σi=(Ui,Vi). If IDi≠IDI, 𝒞 stops the simulation. From the forgery lemma [27], if we have a replay of 𝒞 with the same random tape but different choice of H4 and H5, 𝒜2 will output another signatures. The following two equations hold since both of the two signatures are valid:
(7)e(Vi,P)=e(QIDi,Ppub)e(hi·upkIDi,W)e(kiUi,T),e(Vi′,P)=e(QIDi,Ppub)e(hi′·upkIDi,W)e(ki′Ui,T).
𝒞 looks up lists LH1 and LU and for tuples 〈IDi,aIDi,QIDi〉 and 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 separately, where QIDi=aIDiP. 𝒞 makes H2 query and H3 query with params and gets tuples 〈params,bi,W〉 and 〈params,ci,T〉, where W=biX and T=ciX. At last, 𝒞 returns (ki(Vi′-s·QIDi)-ki′(Vi-s·QIDi))/bi(hi′ki-hiki′) as the solution of CDH problem.Analysis. We show that 𝒞 solves the given instance of the CDH problem with the probability η. To do so, we analyze the three events that result in 𝒞’s success.E1: 𝒞 does not abort in all the queries of RevealSecertKey.E2: 𝒜1 can forge a legal signature σi=(Ui,Vi).E3: the outputted tuple (IDi,mi,σi) satisfies IDi=IDI.From the simulation we know thatPr[E1]≥(1-(1/qH1))qRSK, Pr[E2∣E1]≥ε, Pr[E3∣E1∧E2]≥(1/qH1), where qH1 and qRSK denote the numbers of H1 queries and RevealSecertKey queries separately. Then, the probability that 𝒞 solves the CDH problem is
(8)η=Pr⁡[E1∧E2∧E3]=Pr[E1]Pr⁡[E2∣E1]Pr[E3∣E1∧E2]≥1qH1(1-1qH1)qRSKε.Then𝒞 could solve the CDH problem with a nonnegligible probability since ε is nonnegligible. This contradicts the hardness of the CDH problem. Therefore, our CLS scheme is existentially unforgeable against a Type II adversary in random oracle model under the assumption that the CDH problem is hard.From the above two lemmas, we could get the following theorem.Theorem 5.
The CLS scheme is secure against adaptively chosen warrant attacks and chosen message and identity attacks in the random oracle model if the CDH problem inG1 is intractable.


### 6.2. Security Analysis of Our CLAS Scheme

For the security of our CLAS scheme, we have the following theorem.Theorem 6.
The CLAS scheme is secure against adaptively chosen warrant attacks and chosen message and identity attacks in the random oracle model if the CDH problem inG1 is intractable.Proof.
Suppose there is an adversary𝒜∈{𝒜1,𝒜2} who could win Game 2 with nonnegligible probability. We could construct another adversary, who could win Game 1 with nonnegligible probability, through the method described in Theorem 2 of Xiong et al.’s work [25]. We have shown that no adversary could win Game 1 with nonnegligible probability in the above theorem. Therefore, our CLAS scheme is secure against adaptively chosen warrant attacks and chosen message and identity attacks in the random oracle model if the CDH problem in G1 is intractable.


## 6.1. Security Analysis of Our CLS Scheme

In this section, we analyze the security of our CLS scheme. The following lemmas and theorem are proposed.Lemma 3.
If Type I adversary𝒜1 wins Game 1 with nonnegligible probability ε, then one could construct an algorithm to solve the CDH problem in G1 with nonnegligible probability.Proof.
Given an instance(X=xP,Y=yP) of the CDH problem in G1, we will construct an algorithm 𝒞 to compute xyP, where x,y∈Zq* and they are unknown to 𝒞. At first, 𝒞 picks an identity IDI at random as the challenged identity in this game, sets the master public key Ppub=X, selects the system parameters params={G1,G2,e,P,Ppub,H1,H2,H3,H4,H5}, and returns the parameters to 𝒜1. Then 𝒞 answers 𝒜1’s query as follows.           (i)
H1query: 𝒞 maintains a list LH1 of form 〈IDi,aIDi,QIDi〉. When 𝒜1 makes this query on IDi, 𝒞 does as follows.
(a)
If the listLH1 contains a tuple 〈IDi,aIDi,QIDi〉, 𝒞 returns QIDi to 𝒜1.(b)
Otherwise, ifIDi=IDI, 𝒞 picks a random aIDi∈Zn*, computes QIDi=aIDiY, adds 〈IDi,aIDi,QIDi〉 to LH1, and returns QIDi to 𝒜1.(c)
Otherwise (IDi≠IDI), 𝒞 picks a random aIDi∈Zn*, computes QIDi=aIDiP, adds 〈IDi,aIDi,QIDi〉 to LH1, and returns QIDi to 𝒜1.(ii)
H2query: 𝒞 maintains a list LH2 of form 〈mi,bi,Wi〉. When 𝒜1 makes this query on mi, 𝒞 does as follows.
(a)
If the listLH2 contains a tuple 〈mi,bi,Wi〉, 𝒞 returns Wi to 𝒜1.(b)
Otherwise,𝒞 picks a random bi∈Zn*, computes Wi=biP, adds 〈mi,bi,Wi〉 to LH2, and returns Wi to 𝒜1.(iii)
H3query: 𝒞 maintains a list LH3 of form 〈mi,ci,Ti〉. When 𝒜1 makes this query on mi, 𝒞 does as follows.
(a)
If the listLH3 contains a tuple 〈mi,ci,Ti〉, 𝒞 returns Ti to 𝒜1.(b)
Otherwise,𝒞 picks a random ci∈Zn*, computes Ti=ciX, adds 〈mi,ci,Ti〉 to LH3, and returns Ti to 𝒜1.(iv)
H4query: 𝒞 maintains a list LH4 of form 〈mi,IDi,upkIDi,Ui,hi〉. When 𝒜1 makes this query on (mi,IDi,upkIDi,Ui), 𝒞 does as follows.
(a)
If the listLH4 contains a tuple 〈mi,IDi,upkIDi,Ui,hi〉, 𝒞 returns hi to 𝒜1.(b)
Otherwise,𝒞 picks a random hi∈Zn*, returns hi to 𝒜1, and adds 〈mi,IDi,upkIDi,Ui,hi〉 to LH4.(v)
H5query: 𝒞 maintains a list LH5 of form 〈mi,IDi,upkIDi,Ui,ki〉. When 𝒜1 makes this query on (mi,IDi,upkIDi,Ui), 𝒞 does as follows.
(a)
If the listLH5 contains a tuple 〈mi,IDi,upkIDi,Ui,ki〉, 𝒞 returns ki to 𝒜1.(b)
Otherwise,𝒞 picks a random ki∈Zn*, returns ki to 𝒜1, and adds 〈mi,IDi,upkIDi,Ui,hi〉 to LH5.(vi)
CreateUser: 𝒞 maintains a list LU of form 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉. When 𝒜1 makes this query on IDi, 𝒞 does as follows.
(a)
If the listLU contains a tuple 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉, 𝒞 returns upkIDi to 𝒜1.(b)
Otherwise, ifIDi=IDI, 𝒞 gets QIDI=aIDIY by making H1 query with IDI and sets pskIDI←⊥. 𝒞 selects a random number xIDi∈Zq* as his secret key uskIDi and computes his public key as upkIDi=uskIDi·P. At last, 𝒞 adds 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 to LU and returns upkIDi to 𝒜1.(c)
Otherwise (IDi≠IDI), 𝒞 gets QIDi=aIDi·P by making H1 query with IDi and sets pskIDi=aIDi·Ppub. 𝒞 selects a random number xIDi∈Zq* as his secret key uskIDi and computes his public key as upkIDi=uskIDi·P. At last, 𝒞 adds 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 to LU and returns upkIDi to 𝒜1.(vii)
RevealPartialKey: when 𝒜1 makes this query on IDi, 𝒞 does as follows.
(a)
IfIDi=IDI, 𝒞 stops the simulation.(b)
Otherwise (IDi≠IDI), 𝒞 looks up the list LU for the tuple 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 and returns pskIDi to 𝒜1.(viii)
RevealSecertKey: when 𝒜1 makes this query on IDi, 𝒞 looks up the list LU for the tuple 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 and returns uskIDi to 𝒜1.(ix)
ReplaceKey: when 𝒜1 makes this query on (IDi,upkIDi′), 𝒞 looks up the list LU for the tuple 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉. 𝒞 sets uskIDi←⊥ and replaces upkIDi with upkIDi′.(x)
Sign: when 𝒜1 makes this query on (mi,IDi), 𝒞 does as follows.
(a)
IfIDi=IDI, 𝒞 looks up lists LH1 and LU and for tuples 〈IDi,aIDi,QIDi〉 and 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 separately, where QIDi=aIDiY and upkIDi may have been replaced by 𝒜1. 𝒞 makes H2 query and H3 query with params and gets tuples 〈params,bi,W〉 and 〈params,ci,T〉, where W=biP and T=ciX. 𝒞 generates three random numbers hi,ki,ri∈Zq*, computes Ui=ki-1(ri·P-aIDi·ci-1·Y), Vi=ri·T+hi·bi·upkIDi, and sets H4(mi,IDi,upkIDi,Ui)←hi, H5(mi,IDi,upkIDi,Ui)←ki. At last, 𝒞 adds tuples 〈mi,IDi,upkIDi,Ui,hi〉 and 〈mi,IDi,upkIDi,Ui,ki〉 to LH4 and LH5 separately and returns (Ui,Vi) to 𝒜1. It is easy to say (Ui,Vi) satisfies the equation e(Vi,P)=e(QIDi,Ppub)e(hi·upkIDi,W)e(kiUi,T).(b)
Otherwise (IDi≠IDI), 𝒞 looks up lists LH1 and LU and for tuples 〈IDi,aIDi,QIDi〉 and 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 separately, where QIDi=aIDiP and upkIDi may have been replaced by (𝒜1). 𝒞 makes H2 query and H3 query with params and gets tuples 〈params,bi,W〉 and 〈params,ci,T〉, where W=biP and T=ciX. 𝒞 generates a random number ri∈Zq* and computes Ui=riP, hi=H4(mi,IDi,upkIDi,Ui), ki=H5(mi,IDi,upkIDi,Ui), and Vi=pskIDi+hi·bi·upkIDi+ki·ri·T. At last, 𝒞 returns (Ui,Vi) to 𝒜1. It is easy to say (Ui,Vi) satisfies the equation e(Vi,P)=e(QIDi,Ppub)e(hi·upkIDi,W)e(kiUi,T).
Finally,𝒜1 outputs a tuple (IDi,mi,σi) as its forgery, where σi=(Ui,Vi). If IDi≠IDI, 𝒞 stops the simulation. From the forgery lemma [27], if we have a replay of 𝒞 with the same random tape but different choice of H4 and H5, 𝒜1 will output another three signatures. The following two equations hold since both of the two signatures are valid:
(5)e(Vi,P)=e(QIDi,Ppub)e(hi·upkIDi,W)e(kiUi,T),e(Vi′,P)=e(QIDi,Ppub)e(hi′·upkIDi,W)e(ki′Ui,T).
𝒞 looks up lists LH1 and LU and for tuples 〈IDi,aIDi,QIDi〉 and 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 separately, where QIDi=aIDiP and upkIDi may have been replaced by 𝒜1. 𝒞 makes H2 query and H3 query with params and gets tuples 〈params,bi,W〉 and 〈params,ci,T〉, where W=biP and T=ciX. At last, 𝒞 returns (ki(Vi′-bi·hi′·upkIDi)-ki′(Vi-bi·hi·upkIDi))/aIDi(ki-ki′) as the solution of CDH problem.Analysis. We show that 𝒞 solves the given instance of the CDH problem with the probability η. To do so, we analyze the three events that result in 𝒞’s success.E1: 𝒞 does not abort in all the queries of RevealPartialKey.E2: 𝒜1 can forge a legal signature σi=(Ui,Vi).E3: the outputted tuple (IDi,mi,σi) satisfies IDi=IDI.From the simulation we know thatPr[E1]≥(1-(1/qH1))qRPK, Pr[E2∣E1]≥ε, Pr[E3∣E1∧E2]≥(1/qH1), where qH1 and qRPK denote the numbers of H1 queries and RevealPartialKey queries separately. Then, the probability that 𝒞 solves the CDH problem is
(6)η=Pr⁡[E1∧E2∧E3]=Pr[E1]Pr⁡[E2∣E1]Pr[E3∣E1∧E2]≥1qH1(1-1qH1)qEPPKε.Then𝒞 could solve the CDH problem with a nonnegligible probability since ε is nonnegligible. This contradicts the hardness of the CDH problem. Therefore, our CLS scheme is existentially unforgeable against Type I adversary in random oracle model under the assumption that the CDH problem is hard.Lemma 4.
If there is a Type I adversary𝒜2 wins Game 1 with nonnegligible probability ε. Then we could construct an algorithm 𝒞 to solve the CDH problem in G1 with nonnegligible probability.Proof.
Given an instance(X=xP,Y=yP) of the CDH problem in G1, we will construct an algorithm 𝒞 to compute xyP, where x,y∈Zq* and they are unknown to 𝒞. At first, 𝒞 picks an identity IDI at random as the challenged identity in this game, generates a random number s∈Zq* as the master key, sets the master public key Ppub=sP, selects the system parameters params={G1,G2,e,P,Ppub,H1,H2,H3,H4,H5}, and returns the master key and the parameters to 𝒜2. Then 𝒞 answers 𝒜2’s query as follows.            (i)
H1query: 𝒞 maintains a list LH1 of form 〈IDi,aIDi,QIDi〉. When 𝒜1 makes this query on IDi, 𝒞 does as follows.
(a)
If the listLH1 contains a tuple 〈IDi,aIDi,QIDi〉, 𝒞 returns QIDi to 𝒜2.(b)
Otherwise,𝒞 picks a random aIDi∈Zn*, computes QIDi=aIDiP, adds 〈IDi,aIDi,QIDi〉 to LH1, and returns QIDi to 𝒜2.(ii)
H2query:𝒞 maintains a list LH2 of form 〈mi,bi,Wi〉. When 𝒜2 makes this query on mi, 𝒞 does as follows.
(a)
If the listLH2 contains a tuple 〈mi,bi,Wi〉, 𝒞 returns Wi to 𝒜2.(b)
Otherwise,𝒞 picks a random bi∈Zn*, computes Wi=biX, adds 〈mi,bi,Wi〉 to LH2, and returns Wi to 𝒜2.(iii)
H3query: 𝒞 maintains a list LH3 of form 〈mi,ci,Ti〉. When 𝒜2 makes this query on mi, 𝒞 does as follows.
(a)
If the listLH3 contains a tuple 〈mi,ci,Ti〉, 𝒞 returns Ti to 𝒜2.(b)
Otherwise,𝒞 picks a random ci∈Zn*, computes Ti=ciX, adds 〈mi,ci,Ti〉 to LH3, and returns Ti to 𝒜2.(iv)
H4query: 𝒞 maintains a list LH4 of form 〈mi,IDi,upkIDi,Ui,hi〉. When 𝒜2 makes this query on (mi,IDi,upkIDi,Ui), 𝒞 does as follows.
(a)
If the listLH4 contains a tuple 〈mi,IDi,upkIDi,Ui,hi〉, 𝒞 returns hi to 𝒜2.(b)
Otherwise,𝒞 picks a random hi∈Zn*, returns hi to 𝒜2, and adds 〈mi,IDi,upkIDi,Ui,hi〉 to LH4.(v)
H5query: 𝒞 maintains a list LH5 of form 〈mi,IDi,upkIDi,Ui,ki〉. When 𝒜2 makes this query on (mi,IDi,upkIDi,Ui), 𝒞 does as follows.
(a)
If the listLH5 contains a tuple 〈mi,IDi,upkIDi,Ui,ki〉, 𝒞 returns ki to 𝒜2.(b)
Otherwise,𝒞 picks a random ki∈Zn*, returns ki to 𝒜2, and adds 〈mi,IDi,upkIDi,Ui,hi〉 to LH5.(vi)
CreateUser: 𝒞 maintains a list LU of form 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉. When 𝒜2 makes this query on IDi, 𝒞 does as follows.
(a)
If the listLU contains a tuple 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉, 𝒞 returns upkIDi to 𝒜2.(b)
Otherwise, ifIDi=IDI, 𝒞 gets QIDI=aIDIP by making H1 query with IDI and computes pskIDI=sQIDI. 𝒞 sets uskIDi←⊥ and upkIDi←Y. At last, 𝒞 adds 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 to LU and returns upkIDi to 𝒜2.(c)
Otherwise (IDi≠IDI), 𝒞 gets QIDi=aIDi·P by making H1 query with IDi and computes pskIDI=sQIDI. 𝒞 selects a random number xIDi∈Zq* as his secret key uskIDi and computes his public key as upkIDi=uskIDi·P. At last, 𝒞 adds 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 to LU and returns upkIDi to 𝒜1.(vii)
RevealPartialKey: when 𝒜2 makes this query on IDi, 𝒞 looks up the list LU for the tuple 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 and returns pskIDi to 𝒜2.(viii)
RevealSecertKey: when 𝒜2 makes this query on IDi, 𝒞 does as follows.
(a)
IfIDi=IDI, 𝒞 stops the simulation.(b)
Otherwise (IDi≠IDI), 𝒞 looks up the list LU for the tuple 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 and returns uskIDi to 𝒜2.(ix)
Sign: when 𝒜1 makes this query on (mi,IDi), 𝒞 does as follows.
(a)
IfIDi=IDI, 𝒞 looks up lists LH1 and LU and for tuples 〈IDi,aIDi,QIDi〉 and 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 separately, where QIDi=aIDiP and upkIDi may have been replaced by 𝒜2. 𝒞 makes H2 query and H3 query with params and gets tuples 〈params,bi,W〉 and 〈params,ci,T〉, where W=biX and T=ciX. 𝒞 generates three random numbers hi,ki,ri∈Zq*, computes Ui=ki-1(ri·P-bi·ci-1·hi·Y), Vi=ri·T+aIDi·s·upkIDi, and sets H4(mi,IDi,upkIDi,Ui)←hi, H5(mi,IDi,upkIDi,Ui)←ki. At last, 𝒞 adds tuples 〈mi,IDi,upkIDi,Ui,hi〉 and 〈mi,IDi,upkIDi,Ui,ki〉 to LH4 and LH5 separately and returns (Ui,Vi) to 𝒜2. It is easy to say (Ui,Vi) satisfies the equation e(Vi,P)=e(QIDi,Ppub)e(hi·upkIDi,W)e(kiUi,T).(b)
Otherwise (IDi≠IDI), 𝒞 acts according to the description of the algorithm Sign since he knows both of uskIDi and pskIDi.
Finally,𝒜2 outputs a tuple (IDi,mi,σi) as its forgery, where σi=(Ui,Vi). If IDi≠IDI, 𝒞 stops the simulation. From the forgery lemma [27], if we have a replay of 𝒞 with the same random tape but different choice of H4 and H5, 𝒜2 will output another signatures. The following two equations hold since both of the two signatures are valid:
(7)e(Vi,P)=e(QIDi,Ppub)e(hi·upkIDi,W)e(kiUi,T),e(Vi′,P)=e(QIDi,Ppub)e(hi′·upkIDi,W)e(ki′Ui,T).
𝒞 looks up lists LH1 and LU and for tuples 〈IDi,aIDi,QIDi〉 and 〈IDi,pskIDi,QIDi,uskIDi,upkIDi〉 separately, where QIDi=aIDiP. 𝒞 makes H2 query and H3 query with params and gets tuples 〈params,bi,W〉 and 〈params,ci,T〉, where W=biX and T=ciX. At last, 𝒞 returns (ki(Vi′-s·QIDi)-ki′(Vi-s·QIDi))/bi(hi′ki-hiki′) as the solution of CDH problem.Analysis. We show that 𝒞 solves the given instance of the CDH problem with the probability η. To do so, we analyze the three events that result in 𝒞’s success.E1: 𝒞 does not abort in all the queries of RevealSecertKey.E2: 𝒜1 can forge a legal signature σi=(Ui,Vi).E3: the outputted tuple (IDi,mi,σi) satisfies IDi=IDI.From the simulation we know thatPr[E1]≥(1-(1/qH1))qRSK, Pr[E2∣E1]≥ε, Pr[E3∣E1∧E2]≥(1/qH1), where qH1 and qRSK denote the numbers of H1 queries and RevealSecertKey queries separately. Then, the probability that 𝒞 solves the CDH problem is
(8)η=Pr⁡[E1∧E2∧E3]=Pr[E1]Pr⁡[E2∣E1]Pr[E3∣E1∧E2]≥1qH1(1-1qH1)qRSKε.Then𝒞 could solve the CDH problem with a nonnegligible probability since ε is nonnegligible. This contradicts the hardness of the CDH problem. Therefore, our CLS scheme is existentially unforgeable against a Type II adversary in random oracle model under the assumption that the CDH problem is hard.From the above two lemmas, we could get the following theorem.Theorem 5.
The CLS scheme is secure against adaptively chosen warrant attacks and chosen message and identity attacks in the random oracle model if the CDH problem inG1 is intractable.


## 6.2. Security Analysis of Our CLAS Scheme

For the security of our CLAS scheme, we have the following theorem.Theorem 6.
The CLAS scheme is secure against adaptively chosen warrant attacks and chosen message and identity attacks in the random oracle model if the CDH problem inG1 is intractable.Proof.
Suppose there is an adversary𝒜∈{𝒜1,𝒜2} who could win Game 2 with nonnegligible probability. We could construct another adversary, who could win Game 1 with nonnegligible probability, through the method described in Theorem 2 of Xiong et al.’s work [25]. We have shown that no adversary could win Game 1 with nonnegligible probability in the above theorem. Therefore, our CLAS scheme is secure against adaptively chosen warrant attacks and chosen message and identity attacks in the random oracle model if the CDH problem in G1 is intractable.


## 7. Performance Analysis

In this section, we compare our scheme with two latest CLAS schemes, that is, Zhang et al.’s scheme [22] and Xiong et al.’s scheme [25]. For convenience, some notations are defined as follows:(i)
TP: the time for executing a pairing operation;(ii)
TS: the time for executing a scalar multiplications in G1.The comparisons are listed in Table1. From the table, we know that Xiong et al.’s scheme and our scheme have better performance than Zhang et al.’s scheme. Xiong et al.’s scheme has better performance than our scheme. However, Xiong et al.’s scheme cannot withstand attacks of Type II adversary. It is well known that security is a top priority in network communications. It is acceptable to enhance security at the cost of increasing computational time slightly. Therefore, our scheme is more suitable for practical applications.Table 1
Performance comparisons.
Sign
Verify
Aggregate verify
Zhang et al.’s scheme [22]
5
T
S
5
T
P
+
2
T
S
5
T
P
+
2
n
T
S
Xiong et al.’s scheme [25]
3
T
S
3
T
P
+
2
T
S
3
T
P
+
2
n
T
S
Our scheme
3
T
S
4
T
P
+
2
T
S
4
T
P
+
2
n
T
S


## 8. Conclusion

Recently, Xiong et al. proposed an efficient CLAS scheme. They claimed that both of their schemes are provably secure in the random oracle model. In this paper, we propose a new attack against their scheme. To overcome weakness, we also propose an improved CLAS scheme and show our scheme is provable in the random oracle model.



---

*Source: 343715-2014-03-13.xml*