# Cryptanalysis and Improvement of Three Certificateless Aggregate Signature Schemes

Authors: Xiaodong Yang; Yutong Li; Chunlin Chen; Likun Xiao; Caifen Wang
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

The certificateless aggregate signature (CLAS) scheme is a very important data aggregation technique that compresses a large number of signatures from different users into a short signature. CLAS can reduce the total length of a signature and the computational overhead of signature verification and is therefore highly suitable for resource-constrained network environments. Many CLAS schemes have been proposed in recent years, but the construction of a secure and efficient CLAS scheme remains important. In 2018, Li et al. found that the CLAS scheme proposed by He et al. could not resist malicious-but-passive KGC attacks, and they presented an improved CLAS scheme. Du et al. proposed a CLAS scheme with the constant aggregate signature length and claimed that their scheme was resistant to forgery attacks. Chen et al. designed a CLAS scheme with efficient verification and proved that their CLAS scheme was secure in the random oracle model. In this paper, we demonstrate that Li et al.’s CLAS scheme, Du et al.’s CLAS scheme, and Chen et al.’s CLAS scheme are insecure against coalition attacks and present concrete examples. That is, an attacker can forge a valid aggregate signature using some illegal single signatures. To withstand suck attacks, we propose an improved CLAS scheme based on Chen et al.’s CLAS scheme.


---

## Body

## 1. Introduction

The traditional signature scheme provides security services such as integrity of the message, nonrepudiation of the signer, and user authentication. However, the scheme relies on the public key infrastructure (PKI) and needs to store and verify many certificates [1]. To solve this problem, Shamir [2] proposed the concept of identity-based signature (IBS), where the user’s public key is replaced with an email address or other unique identity information of the user, and a fully trusted key generation center (KGC) produces the user’s private key. Nevertheless, IBS suffers from the key escrow problem since the KGC knows the private keys of all users and can do anything on behalf of the user without being detected. To eliminate the use of certificates and to avoid the key escrow problem, certificateless signature (CLS) was introduced by Al-Riyami and Paterson [3]. In CLS, the user’s public key is self-generated, and the user’s private key consists of two parts: a secret value selected by the user and a partial private key generated by a semitrusted KGC. Consequently, CLS can avoid the security flaws of IBS without requiring certificates. Although some efficient CLS schemes have been presented [4–8], more secure CLS schemes are desired for practical applications.An aggregate signature scheme [9] can aggregate multiple signatures of different messages into a short signature, and the verifier is able to determine the validity of each signature participating in the aggregation by verifying the validity of the aggregate signature. Aggregate signatures reduce storage and bandwidth overhead and are thus highly useful in wireless communication environments. Because of the advantages of CLS and aggregate signatures, some researchers have focused on certificateless aggregate signature (CLAS) schemes [10–12].In 2013, Xiong et al. [13] presented an efficient CLS scheme and used it to design a CLAS scheme with constant pairing computations. However, He et al. [14] found that Xiong et al.’s CLS and CLAS schemes [13] were not secure against malicious KGC attacks, and they proposed an improved CLAS scheme. Very recently, Li et al. [15] showed that He et al.’s CLAS scheme [14] still could not resist malicious-but-passive KGC attacks. Later, Li et al. [15] designed an improved CLAS scheme and claimed that their CLAS scheme was resistant to forgery attacks. Ming et al. [16] gave a CLAS scheme in which the length of aggregate signature is constant. However, Du et al. [17] pointed out that Ming et al.’s CLAS scheme [16] could not resist malicious KGC attacks and proposed a new CLAS scheme. Chen et al. [18] presented a CLAS scheme with efficient verification, but their CLAS scheme was shown to be insecure against Type I and Type II adversaries [19–21].However, most CLAS schemes do not consider coalition attacks [22], which are a type of practical and powerful attack in which an attacker attempts to generate a valid aggregate signature by using illegal individual signatures. Once such an attack is successful, the validity of an aggregate signature cannot guarantee that each individual signature participating in the aggregation is valid. This requires that a secure CLAS scheme should be able to resist coalition attacks. Unfortunately, we note that Li et al.’s CLAS scheme [15], Du et al.’s CLAS scheme [17], and Chen et al.’s CLAS scheme [18] are insecure against coalition attacks since the attacker can forge a valid aggregate signature through illegal single signatures generated by conspiracy from two or more internal signers.


### 1.1. Contributions

In this paper, we provide a cryptanalysis of three CLAS schemes. We first present an attack against Li et al.’s CLAS scheme [15] to show that their CLAS scheme is insecure under practical coalition attacks. Then, we point out that Du et al.’s CLAS scheme [17] cannot resist coalition attacks by giving a concrete attack. Furthermore, we demonstrate the security weakness of Chen et al.’s CLAS scheme [18] by presenting a forgery attack from a coalition of insider signers. Based on Chen et al.’s CLAS scheme, we construct a new CLAS scheme that is secure against coalition attacks.


### 1.2. Paper Organization

The remainder of this paper is organized as follows. Section2 reviews some preliminaries. Section 3 analyses the security of Li et al.’s CLAS scheme. Section 4 gives cryptanalysis of Du et al.’s CLAS scheme. Section 5 analyses the security of Chen et al.’s CLAS scheme. Section 6 presents an improved CLAS scheme. Finally, Section 7 concludes the paper.


## 1.1. Contributions

In this paper, we provide a cryptanalysis of three CLAS schemes. We first present an attack against Li et al.’s CLAS scheme [15] to show that their CLAS scheme is insecure under practical coalition attacks. Then, we point out that Du et al.’s CLAS scheme [17] cannot resist coalition attacks by giving a concrete attack. Furthermore, we demonstrate the security weakness of Chen et al.’s CLAS scheme [18] by presenting a forgery attack from a coalition of insider signers. Based on Chen et al.’s CLAS scheme, we construct a new CLAS scheme that is secure against coalition attacks.


## 1.2. Paper Organization

The remainder of this paper is organized as follows. Section2 reviews some preliminaries. Section 3 analyses the security of Li et al.’s CLAS scheme. Section 4 gives cryptanalysis of Du et al.’s CLAS scheme. Section 5 analyses the security of Chen et al.’s CLAS scheme. Section 6 presents an improved CLAS scheme. Finally, Section 7 concludes the paper.


## 2. Preliminaries

In this section, we briefly review bilinear pairing and the definitions of CLS and CLAS.


### 2.1. Bilinear Pairing

Suppose thatG1 and G2 are two multiplicative cyclic groups of prime order p and that g is a generator of G1. An efficiently computable map e:G1×G1→G2 is said to be a bilinear pairing if it satisfies the following conditions [18]:(i)
Bilinearity: e(ga,gb)=e(g,g)ab=e(gb,ga) for any a,b∈Zp.(ii)
Nondegeneracy: e(g,g)≠1.


### 2.2. Definition of Certificateless Signature

A CLS scheme is defined by the following five algorithms:(i)
Setup: Upon input of a security parameter λ∈Z, this algorithm outputs the public parameters pp and the PKG’s master secret key msk.(ii)
PartialKeyGen: Upon input of pp, msk, and a user identity IDi, this algorithm outputs a partial private key pski corresponding to IDi.(iii)
UserKeyGen: Upon input of pp and pski, this algorithm outputs IDi’s secret value uski, public key upki, and private key ski=(pski,uski).(iv)
Sign: Upon input of pp, an identity IDi’s private key ski, and a message mi, this algorithm outputs a signature σi on mi.(v)
Verify: Given an identity IDi, a public key upki, a message mi, and a signature σi, a verifier accepts σi if σi is a valid signature on mi with respect to IDi and upki; otherwise, the verifier rejects σi.In general, two types of attackers exist in a CLS scheme, i.e., Type I and Type II adversaries [3]. A Type I adversary models an outside attacker who is able to determine the user’s secret value or replace the user’s public key at will but who does not have access to the KGC’s master secret key and the user’s partial private key. A Type II adversary models a malicious KGC who knows the KGC’s master secret key and generates the user’s partial private key but who is unable to access the user’s secret value or replace the user’s public key. In the original security model for a CLS scheme [3], a Type II adversary represents an honest-but-curious KGC who always honestly generates the system parameters and the user’s partial private key according to the specifications of the CLS scheme. In the stronger security model proposed by Au et al. [23], a Type II adversary represents a malicious-but-passive KGC who is dishonest from the beginning of the system setup. The malicious-but-passive KGC adversary sets some trapdoors in the system parameters and the master secret key and then uses these trapdoors to launch malicious attacks to compromise the security of the CLS scheme. However, some existing CLS schemes [6–8] have been shown to be insecure against malicious-but-passive KGC attacks.


### 2.3. Definition of Certificateless Aggregate Signature

A CLAS scheme is defined by the following seven algorithms:(i)
TheSetup,PartialKeyGen,UserKeyGen,Sign, andVerify algorithms are the same as those in CLS described in Section 2.(ii)
Aggregate: Upon input of n message-signature pairs {(m1,σ1),…,(mn,σn)} from n users, this algorithm outputs an aggregate signature σ on messages {m1,…,mn}.(iii)
AggregateVerify: Given n identities {ID1,…,IDn}, n public keys {upk1,…,upkn}, and an aggregate signature σ on n messages {m1,…,mn}, a verifier accepts σ if σ is valid; otherwise, the verifier rejects σ.The security model for the CLAS scheme is almost the same as the security model for the CLS scheme, except that an adversary is unable to forge a valid aggregate signature if at least one of the signatures involved in the aggregation is invalid. To save space, we omit the detailed description. Please refer to [1, 3, 23] for the security model of the CLS scheme or the CLAS scheme.


## 2.1. Bilinear Pairing

Suppose thatG1 and G2 are two multiplicative cyclic groups of prime order p and that g is a generator of G1. An efficiently computable map e:G1×G1→G2 is said to be a bilinear pairing if it satisfies the following conditions [18]:(i)
Bilinearity: e(ga,gb)=e(g,g)ab=e(gb,ga) for any a,b∈Zp.(ii)
Nondegeneracy: e(g,g)≠1.


## 2.2. Definition of Certificateless Signature

A CLS scheme is defined by the following five algorithms:(i)
Setup: Upon input of a security parameter λ∈Z, this algorithm outputs the public parameters pp and the PKG’s master secret key msk.(ii)
PartialKeyGen: Upon input of pp, msk, and a user identity IDi, this algorithm outputs a partial private key pski corresponding to IDi.(iii)
UserKeyGen: Upon input of pp and pski, this algorithm outputs IDi’s secret value uski, public key upki, and private key ski=(pski,uski).(iv)
Sign: Upon input of pp, an identity IDi’s private key ski, and a message mi, this algorithm outputs a signature σi on mi.(v)
Verify: Given an identity IDi, a public key upki, a message mi, and a signature σi, a verifier accepts σi if σi is a valid signature on mi with respect to IDi and upki; otherwise, the verifier rejects σi.In general, two types of attackers exist in a CLS scheme, i.e., Type I and Type II adversaries [3]. A Type I adversary models an outside attacker who is able to determine the user’s secret value or replace the user’s public key at will but who does not have access to the KGC’s master secret key and the user’s partial private key. A Type II adversary models a malicious KGC who knows the KGC’s master secret key and generates the user’s partial private key but who is unable to access the user’s secret value or replace the user’s public key. In the original security model for a CLS scheme [3], a Type II adversary represents an honest-but-curious KGC who always honestly generates the system parameters and the user’s partial private key according to the specifications of the CLS scheme. In the stronger security model proposed by Au et al. [23], a Type II adversary represents a malicious-but-passive KGC who is dishonest from the beginning of the system setup. The malicious-but-passive KGC adversary sets some trapdoors in the system parameters and the master secret key and then uses these trapdoors to launch malicious attacks to compromise the security of the CLS scheme. However, some existing CLS schemes [6–8] have been shown to be insecure against malicious-but-passive KGC attacks.


## 2.3. Definition of Certificateless Aggregate Signature

A CLAS scheme is defined by the following seven algorithms:(i)
TheSetup,PartialKeyGen,UserKeyGen,Sign, andVerify algorithms are the same as those in CLS described in Section 2.(ii)
Aggregate: Upon input of n message-signature pairs {(m1,σ1),…,(mn,σn)} from n users, this algorithm outputs an aggregate signature σ on messages {m1,…,mn}.(iii)
AggregateVerify: Given n identities {ID1,…,IDn}, n public keys {upk1,…,upkn}, and an aggregate signature σ on n messages {m1,…,mn}, a verifier accepts σ if σ is valid; otherwise, the verifier rejects σ.The security model for the CLAS scheme is almost the same as the security model for the CLS scheme, except that an adversary is unable to forge a valid aggregate signature if at least one of the signatures involved in the aggregation is invalid. To save space, we omit the detailed description. Please refer to [1, 3, 23] for the security model of the CLS scheme or the CLAS scheme.


## 3. Cryptanalysis of Li et al.’s CLAS Scheme

### 3.1. Review of Li et al.’s Scheme

In 2018, Li et al. [15] presented a CLAS scheme that consists of the following seven algorithms:(i)
Setup: Given a security parameter λ∈Z, the KGC generates the public parameters pp and the master secret key msk by performing the following steps:
(a)
Choose two cyclic groupsG1 and G2 of prime order p, a generator g of G1 and a bilinear pairing e:G1×G1→G2.(b)
Select a random integers∈Zp∗ and compute Ppub=gs.(c)
Pick four cryptographic hash functionsH1,H4:{0,1}∗→G1 and H2,H3:{0,1}∗→Zp∗.(d)
Keep the master secret keymsk=s secret and publish public parameters pp=G1,G2,p,g,,e,Ppub,H1,H2,H3,H4.(ii)
PartialKeyGen: Given a user’s identity IDi, the KGC computes Qi=H1(IDi) and pski=(Qi)s. Then, the KGC sends IDi’s partial private key pski to the user.(iii)
UserKeyGen: The user with identity IDi generates a public/private key pair (upki,ski) according to the following steps:
(a)
Select a random integerxi∈Zp∗ and compute the public key upki=gxi.(b)
Set the secret valueuski=xi and the private key ski=(pski,uski)=((Qi)s,xi).(iv)
Sign: To sign a message mi, a signer with identity IDi performs the following:
(a)
Select a random integerri∈Zp∗ and compute Ri=gri.(b)
Computehi=H2(0,mi,IDi,upki,Ri), ki=H3(1,mi,IDi,upki,Ri), Q=H4(p,g,Ppub) and Yi=(pski)hi·(Ppub)ri·Qkixi·Qri.(c)
Output a signatureσi=(Ri,Yi) on mi.(v)
Verify: Given an identity IDi, a public key upki, a message mi, and a signature σi=(Ri,Yi), a verifier first computes Qi=H1(IDi), hi=H2(0,mi,IDi,upki,Ri), ki=H3(1,mi,IDi,upki,Ri) and Q=H4(p,g,Ppub). Then, the verifier checks the following equation:(1)eYi,g=eRiQihi,PpubeupkikiRi,Q.If the above equation holds, then the verifier acceptsσi; otherwise, the verifier rejects σi.(vi)
Aggregate: Given n message-signature pairs {(m1,σ1=(R1,Y1)),…,(mn,σn=(Rn,Yn))} from n users, the aggregator calculates an aggregate signature σ=(R1,…,Rn,Y) on {m1,…,mn}, where Y=∏i=1nYi.(vii)
AggregateVerify: Given n identities {ID1,…,IDn}, n public keys {upk1,…,upkn}, and an aggregate signature σ=(R1,…,Rn,Y) on n messages {m1,…,mn}, a verifier first computes Qi=H1(IDi), hi=H2(0,mi,IDi,upki,Ri), ki=H3(1,mi,IDi,upki,Ri) and Q=H4(p,g,Ppub) for 1≤i≤n. Then, the verifier checks the following equation:(2)eY,g=e∏i=1nRiQihi,Ppube∏i=1nupkikiRi,Q.If this equation holds, then the verifier acceptsσ; otherwise, the verifier rejects σ.


### 3.2. Attack on Li et al.’s Scheme

Li et al. [15] proved that their CLAS scheme is existentially unforgeable in the random oracle model. In this subsection, we show that Li et al.’s CLAS scheme [15] is insecure against coalition attacks from internal signers. That is, two or more internal signers who generate multiple illegal single signatures can collude to generate a valid aggregate signature. Without loss of generality, suppose that U1 and U2 are two internal signers. Let ID1 and upk1 be the identity and public key of U1, respectively. ID2 and upk2 are the identity and public key of U2, respectively. U1 generates an invalid signature σ1∗ of message m1, and U2 generates an invalid signature σ2∗ of message m2. Then, U1 colludes with U2 to generate a valid aggregate signature σ∗ for {m1,m2}. The detailed attack process is described as follows.(1)
U1 randomly selects r1∈Zp∗ and calculates R1∗=gr1, h1=H2(0,m1,ID1,upk1,R1∗), k1=H3(1,m1,ID1,upk1,R1∗), Q=H4(p,g,Ppub) and K1=(Ppub)r1Qr1. Then, U1 sends K1 to U2.(2)
U2 randomly selects r2∈Zp∗ and calculates R2∗=gr2, h2=H2(0,m2,ID2,upk2,R2∗), k2=H3(1,m2,ID2,upk2,R2∗), Q=H4(p,g,Ppub) and K2=(Ppub)r2Qr2. Then, U2 sends K2 to U1.(3)
U1 calculates Y1∗=(psk1)h1·K2·Qk1x1 and outputs an individual signature σ1∗=(R1∗,Y1∗) on m1, where x1 is the secret value of U1.(4)
U2 uses its secret value x2 to calculate Y2∗=(psk2)h2·K1·Qk2x2 and outputs an individual signature σ2∗=(R2∗,Y2∗) on m2.(5)
U1 cooperates with U2 to forge an aggregate signature σ∗=(R1∗,R2∗,Y∗) on {m1,m2}, where Y∗=Y1∗·Y2∗.σ i ∗ can easily be verified to be an invalid single signature for mi under IDi and upki since σi∗ does not satisfy the individual signature verification equation, i=1,2. However, the forged aggregate signature σ∗ on {m1,m2} under {ID1,ID2} and {upk1,upk2} is valid since(3)eY∗,g=eY1∗Y2∗,g=epsk1h1K2Qk1x1·psk2h2K1Qk2x2,g=epsk1h1K1Qk1x1·psk2h2K2Qk2x2,g=epsk1h1Ppubr1Qr1Qk1x1·psk2h2Ppubr2Qr2Qk2x2,g=eR1∗Q1h1,Ppubeupk1k1R1∗,Q·eR2∗Q2h2,Ppubeupk2k2R2∗,Q=e∏i=12Ri∗Qihi,Ppube∏i=12upkikiRi∗,Q.The above analysis shows that the forged aggregate signatureσ∗ satisfies the aggregate signature verification equation. Therefore, U1 can collude with U2 to produce a valid aggregate signature with some illegal single signatures. Therefore, Li et al.’s CLAS scheme [15] is vulnerable to coalition attacks.


## 3.1. Review of Li et al.’s Scheme

In 2018, Li et al. [15] presented a CLAS scheme that consists of the following seven algorithms:(i)
Setup: Given a security parameter λ∈Z, the KGC generates the public parameters pp and the master secret key msk by performing the following steps:
(a)
Choose two cyclic groupsG1 and G2 of prime order p, a generator g of G1 and a bilinear pairing e:G1×G1→G2.(b)
Select a random integers∈Zp∗ and compute Ppub=gs.(c)
Pick four cryptographic hash functionsH1,H4:{0,1}∗→G1 and H2,H3:{0,1}∗→Zp∗.(d)
Keep the master secret keymsk=s secret and publish public parameters pp=G1,G2,p,g,,e,Ppub,H1,H2,H3,H4.(ii)
PartialKeyGen: Given a user’s identity IDi, the KGC computes Qi=H1(IDi) and pski=(Qi)s. Then, the KGC sends IDi’s partial private key pski to the user.(iii)
UserKeyGen: The user with identity IDi generates a public/private key pair (upki,ski) according to the following steps:
(a)
Select a random integerxi∈Zp∗ and compute the public key upki=gxi.(b)
Set the secret valueuski=xi and the private key ski=(pski,uski)=((Qi)s,xi).(iv)
Sign: To sign a message mi, a signer with identity IDi performs the following:
(a)
Select a random integerri∈Zp∗ and compute Ri=gri.(b)
Computehi=H2(0,mi,IDi,upki,Ri), ki=H3(1,mi,IDi,upki,Ri), Q=H4(p,g,Ppub) and Yi=(pski)hi·(Ppub)ri·Qkixi·Qri.(c)
Output a signatureσi=(Ri,Yi) on mi.(v)
Verify: Given an identity IDi, a public key upki, a message mi, and a signature σi=(Ri,Yi), a verifier first computes Qi=H1(IDi), hi=H2(0,mi,IDi,upki,Ri), ki=H3(1,mi,IDi,upki,Ri) and Q=H4(p,g,Ppub). Then, the verifier checks the following equation:(1)eYi,g=eRiQihi,PpubeupkikiRi,Q.If the above equation holds, then the verifier acceptsσi; otherwise, the verifier rejects σi.(vi)
Aggregate: Given n message-signature pairs {(m1,σ1=(R1,Y1)),…,(mn,σn=(Rn,Yn))} from n users, the aggregator calculates an aggregate signature σ=(R1,…,Rn,Y) on {m1,…,mn}, where Y=∏i=1nYi.(vii)
AggregateVerify: Given n identities {ID1,…,IDn}, n public keys {upk1,…,upkn}, and an aggregate signature σ=(R1,…,Rn,Y) on n messages {m1,…,mn}, a verifier first computes Qi=H1(IDi), hi=H2(0,mi,IDi,upki,Ri), ki=H3(1,mi,IDi,upki,Ri) and Q=H4(p,g,Ppub) for 1≤i≤n. Then, the verifier checks the following equation:(2)eY,g=e∏i=1nRiQihi,Ppube∏i=1nupkikiRi,Q.If this equation holds, then the verifier acceptsσ; otherwise, the verifier rejects σ.


## 3.2. Attack on Li et al.’s Scheme

Li et al. [15] proved that their CLAS scheme is existentially unforgeable in the random oracle model. In this subsection, we show that Li et al.’s CLAS scheme [15] is insecure against coalition attacks from internal signers. That is, two or more internal signers who generate multiple illegal single signatures can collude to generate a valid aggregate signature. Without loss of generality, suppose that U1 and U2 are two internal signers. Let ID1 and upk1 be the identity and public key of U1, respectively. ID2 and upk2 are the identity and public key of U2, respectively. U1 generates an invalid signature σ1∗ of message m1, and U2 generates an invalid signature σ2∗ of message m2. Then, U1 colludes with U2 to generate a valid aggregate signature σ∗ for {m1,m2}. The detailed attack process is described as follows.(1)
U1 randomly selects r1∈Zp∗ and calculates R1∗=gr1, h1=H2(0,m1,ID1,upk1,R1∗), k1=H3(1,m1,ID1,upk1,R1∗), Q=H4(p,g,Ppub) and K1=(Ppub)r1Qr1. Then, U1 sends K1 to U2.(2)
U2 randomly selects r2∈Zp∗ and calculates R2∗=gr2, h2=H2(0,m2,ID2,upk2,R2∗), k2=H3(1,m2,ID2,upk2,R2∗), Q=H4(p,g,Ppub) and K2=(Ppub)r2Qr2. Then, U2 sends K2 to U1.(3)
U1 calculates Y1∗=(psk1)h1·K2·Qk1x1 and outputs an individual signature σ1∗=(R1∗,Y1∗) on m1, where x1 is the secret value of U1.(4)
U2 uses its secret value x2 to calculate Y2∗=(psk2)h2·K1·Qk2x2 and outputs an individual signature σ2∗=(R2∗,Y2∗) on m2.(5)
U1 cooperates with U2 to forge an aggregate signature σ∗=(R1∗,R2∗,Y∗) on {m1,m2}, where Y∗=Y1∗·Y2∗.σ i ∗ can easily be verified to be an invalid single signature for mi under IDi and upki since σi∗ does not satisfy the individual signature verification equation, i=1,2. However, the forged aggregate signature σ∗ on {m1,m2} under {ID1,ID2} and {upk1,upk2} is valid since(3)eY∗,g=eY1∗Y2∗,g=epsk1h1K2Qk1x1·psk2h2K1Qk2x2,g=epsk1h1K1Qk1x1·psk2h2K2Qk2x2,g=epsk1h1Ppubr1Qr1Qk1x1·psk2h2Ppubr2Qr2Qk2x2,g=eR1∗Q1h1,Ppubeupk1k1R1∗,Q·eR2∗Q2h2,Ppubeupk2k2R2∗,Q=e∏i=12Ri∗Qihi,Ppube∏i=12upkikiRi∗,Q.The above analysis shows that the forged aggregate signatureσ∗ satisfies the aggregate signature verification equation. Therefore, U1 can collude with U2 to produce a valid aggregate signature with some illegal single signatures. Therefore, Li et al.’s CLAS scheme [15] is vulnerable to coalition attacks.


## 4. Cryptanalysis of Du et al.’s CLAS Scheme

### 4.1. Review of Du et al.’s Scheme

In 2017, Du et al. [17] designed a CLAS scheme which is composed of the following seven algorithms:(i)
Setup: Given a security parameter λ∈Z, the KGC selects two cyclic groups G1 and G2 of prime order p, a generator g of G1 and a bilinear pairing e:G1×G1→G2. Then, the KGC randomly selects s∈Zp∗ and compute Ppub=gs. Next, the KGC picks four hash functions H1,H2,,H3:{0,1}∗→G1 and H4:{0,1}∗→Zp∗. Finally, the KGC stores the master secret key msk=s secret and publish public parameters pp={G1,G2,p,g,,e,Ppub,H1,H2,H3,H4}.(ii)
PartialKeyGen: Given a user’s identity IDi, the KGC calculates Qi=H1(IDi) and pski=(Qi)s. Then, the KGC sends IDi’s partial private key pski to the user.(iii)
UserKeyGen: The user with identity IDi randomly selects xi∈Zp∗ and calculates the public key upki=gxi. Then, the user sets the secret value uski=xi and the private key ski=(pski,uski)=((Qi)s,xi).(iv)
Sign: Given a message mi, a signer with identity IDi executes the following steps:
(a)
Randomly selectri∈Zp∗ and compute Ri=gri.(b)
ComputeWi=H2(mi,IDi,upki), T=H3(Ppub) and hi=H4(mi,IDi,upki).(c)
ComputeYi=(pski)hi(Wi)xiTri.(d)
Output a signatureσi=(Ri,Yi) on mi.(v)
Verify: Given a signature σi= (Ri,Yi) on a message mi under an identity IDi and public key upki, a verifier first calculates Qi=H1(IDi), Wi=H2(mi,IDi,upki), T=H3(Ppub) and hi=H4(mi,IDi,upki). Then, the verifier verifies whether the following equation holds or not.(4)eYi,g=eQihi,PpubeWi,upkieT,Ri.If it holds, then the verifier acceptsσi; otherwise, the verifier rejects σi.(vi)
Aggregate: Given n message-signature pairs {(m1,σ1=(R1,Y1)),…,(mn,σn=(Rn,Yn))} from n users, the aggregator calculates an aggregate signature σ=(R,Y) on {m1,…,mn}, where R=∏i=1nRi and Y=∏i=1nYi.(vii)
AggregateVerify: Given an aggregate signature σ=(R,Y) on {m1,…,mn} under n identities {ID1,…,IDn} and n public keys {upk1,…,upkn}, a verifier first calculates Qi=H1(IDi), Wi=H2(mi,IDi,upki), T=H3(Ppub) and hi=H4(mi,IDi,upki) for 1≤i≤n. Then, the verifier verifies whether the following equation holds or not.(5)eY,g=e∏i=1nQihi,Ppub∏i=1neWi,upkieT,R.If it holds, then the verifier acceptsσ; otherwise, the verifier rejects σ.


### 4.2. Attack on Du et al.’s Scheme

Du et al. [17] claimed that their CLAS scheme is existentially unforgeable against the Type I and Type II adversaries in the random oracle model. However, we show that Du et al.’s CLAS scheme [17] is vulnerable to coalition attacks. Similarly, assuming U1 and U2 are two internal signers, they perform the following steps to generate two illegal single signatures, but the corresponding aggregate signature is legal.(1)
The signerU1 with identity ID1 and public key upk1 first selects a random value r1∈Zp∗ and calculates R1∗=gr1. Then, U1 randomly picks a message m1, and calculates W1=H2(m1,ID1,upk1), T=H3(Ppub) and h1=H4(m1,ID1,upk1). Finally, U1 sends Tr1 to U2.(2)
The signerU2 with identity ID2 and public key upk2 first selects a random value r2∈Zp∗ and calculates R2∗=gr2. Then, U2 randomly picks a message m2, and calculates W2=H2(m2,ID2,upk2), T=H3(Ppub) and h2=H4(m2,ID2,upk2). Finally, U2 sends Tr2 to U1.(3)
U1 calculates Y1∗=(psk1)h1(W1)x1Tr2 using the secret value x1 and partial private key psk1 and outputs an individual signature σ1∗=(R1∗,Y1∗) on m1.(4)
U2 calculates Y2∗=(psk2)h2(W2)x2Tr1 using the secret value x2 and partial private key psk2 and outputs an individual signature σ2∗=(R2∗,Y2∗) on m2.(5)
U1 cooperates with U2 to forge an aggregate signature σ∗=(R∗,Y∗) on {m1,m2}, where R∗=R1∗·R2∗ and Y∗=Y1∗·Y2∗.Obviously,σi∗ is not a legal signature on message mi under identity IDi and public key upki, i=1,2. However, the forged aggregate signature σ∗ on {m1,m2} under {ID1,ID2} and {upk1,upk2} is valid since σ∗ satisfies the following aggregate signature verification equation:(6)eY∗,g=eY1∗Y2∗,g=epsk1h1W1x1Tr2·psk2h2W2x2Tr1,g=epsk1h1W1x1Tr1·psk2h2W2x2Tr2,g=eQ1h1,PpubeW1,upk1eT,R1∗·eQ2h2,PpubeW2,upk2eT,R2∗=e∏i=12Qihi,Ppub∏i=12eWi,upkieT,R∗.From the above analysis, we can see thatU1 produces an illegal signature σ1∗ on message m1, and U2 produces an illegal signature σ2∗ on message m2, but the resulting aggregate signature σ∗ on {m1,m2} is valid. Hence, Du et al.’s CLAS scheme [17] is unable to withstand coalition attacks.


## 4.1. Review of Du et al.’s Scheme

In 2017, Du et al. [17] designed a CLAS scheme which is composed of the following seven algorithms:(i)
Setup: Given a security parameter λ∈Z, the KGC selects two cyclic groups G1 and G2 of prime order p, a generator g of G1 and a bilinear pairing e:G1×G1→G2. Then, the KGC randomly selects s∈Zp∗ and compute Ppub=gs. Next, the KGC picks four hash functions H1,H2,,H3:{0,1}∗→G1 and H4:{0,1}∗→Zp∗. Finally, the KGC stores the master secret key msk=s secret and publish public parameters pp={G1,G2,p,g,,e,Ppub,H1,H2,H3,H4}.(ii)
PartialKeyGen: Given a user’s identity IDi, the KGC calculates Qi=H1(IDi) and pski=(Qi)s. Then, the KGC sends IDi’s partial private key pski to the user.(iii)
UserKeyGen: The user with identity IDi randomly selects xi∈Zp∗ and calculates the public key upki=gxi. Then, the user sets the secret value uski=xi and the private key ski=(pski,uski)=((Qi)s,xi).(iv)
Sign: Given a message mi, a signer with identity IDi executes the following steps:
(a)
Randomly selectri∈Zp∗ and compute Ri=gri.(b)
ComputeWi=H2(mi,IDi,upki), T=H3(Ppub) and hi=H4(mi,IDi,upki).(c)
ComputeYi=(pski)hi(Wi)xiTri.(d)
Output a signatureσi=(Ri,Yi) on mi.(v)
Verify: Given a signature σi= (Ri,Yi) on a message mi under an identity IDi and public key upki, a verifier first calculates Qi=H1(IDi), Wi=H2(mi,IDi,upki), T=H3(Ppub) and hi=H4(mi,IDi,upki). Then, the verifier verifies whether the following equation holds or not.(4)eYi,g=eQihi,PpubeWi,upkieT,Ri.If it holds, then the verifier acceptsσi; otherwise, the verifier rejects σi.(vi)
Aggregate: Given n message-signature pairs {(m1,σ1=(R1,Y1)),…,(mn,σn=(Rn,Yn))} from n users, the aggregator calculates an aggregate signature σ=(R,Y) on {m1,…,mn}, where R=∏i=1nRi and Y=∏i=1nYi.(vii)
AggregateVerify: Given an aggregate signature σ=(R,Y) on {m1,…,mn} under n identities {ID1,…,IDn} and n public keys {upk1,…,upkn}, a verifier first calculates Qi=H1(IDi), Wi=H2(mi,IDi,upki), T=H3(Ppub) and hi=H4(mi,IDi,upki) for 1≤i≤n. Then, the verifier verifies whether the following equation holds or not.(5)eY,g=e∏i=1nQihi,Ppub∏i=1neWi,upkieT,R.If it holds, then the verifier acceptsσ; otherwise, the verifier rejects σ.


## 4.2. Attack on Du et al.’s Scheme

Du et al. [17] claimed that their CLAS scheme is existentially unforgeable against the Type I and Type II adversaries in the random oracle model. However, we show that Du et al.’s CLAS scheme [17] is vulnerable to coalition attacks. Similarly, assuming U1 and U2 are two internal signers, they perform the following steps to generate two illegal single signatures, but the corresponding aggregate signature is legal.(1)
The signerU1 with identity ID1 and public key upk1 first selects a random value r1∈Zp∗ and calculates R1∗=gr1. Then, U1 randomly picks a message m1, and calculates W1=H2(m1,ID1,upk1), T=H3(Ppub) and h1=H4(m1,ID1,upk1). Finally, U1 sends Tr1 to U2.(2)
The signerU2 with identity ID2 and public key upk2 first selects a random value r2∈Zp∗ and calculates R2∗=gr2. Then, U2 randomly picks a message m2, and calculates W2=H2(m2,ID2,upk2), T=H3(Ppub) and h2=H4(m2,ID2,upk2). Finally, U2 sends Tr2 to U1.(3)
U1 calculates Y1∗=(psk1)h1(W1)x1Tr2 using the secret value x1 and partial private key psk1 and outputs an individual signature σ1∗=(R1∗,Y1∗) on m1.(4)
U2 calculates Y2∗=(psk2)h2(W2)x2Tr1 using the secret value x2 and partial private key psk2 and outputs an individual signature σ2∗=(R2∗,Y2∗) on m2.(5)
U1 cooperates with U2 to forge an aggregate signature σ∗=(R∗,Y∗) on {m1,m2}, where R∗=R1∗·R2∗ and Y∗=Y1∗·Y2∗.Obviously,σi∗ is not a legal signature on message mi under identity IDi and public key upki, i=1,2. However, the forged aggregate signature σ∗ on {m1,m2} under {ID1,ID2} and {upk1,upk2} is valid since σ∗ satisfies the following aggregate signature verification equation:(6)eY∗,g=eY1∗Y2∗,g=epsk1h1W1x1Tr2·psk2h2W2x2Tr1,g=epsk1h1W1x1Tr1·psk2h2W2x2Tr2,g=eQ1h1,PpubeW1,upk1eT,R1∗·eQ2h2,PpubeW2,upk2eT,R2∗=e∏i=12Qihi,Ppub∏i=12eWi,upkieT,R∗.From the above analysis, we can see thatU1 produces an illegal signature σ1∗ on message m1, and U2 produces an illegal signature σ2∗ on message m2, but the resulting aggregate signature σ∗ on {m1,m2} is valid. Hence, Du et al.’s CLAS scheme [17] is unable to withstand coalition attacks.


## 5. Cryptanalysis of Chen et al.’s CLAS Scheme

### 5.1. Review of Chen et al.’s Scheme

Chen et al.’s CLAS scheme [18] is described as follows:(i)
Setup: Given a security parameter λ∈Z, the KGC performs the following steps to generate the public parameters pp and the master secret key msk:
(a)
Choose two cyclic groupsG1 and G2 of prime order p, a generator g of G1 and a bilinear pairing e:G1×G1→G2.(b)
Select a random integers∈Zp∗ and compute Ppub=gs.(c)
Pick six cryptographic hash functionsH1,H1′,H2, H3:{0,1}∗→G1 and H4,H5: {0,1}∗→Zp∗.(d)
Keep the master secret keymsk=s secret and publish public parameters pp={G1,G2,p,g,e,Ppub,H1,H1′,H2,H3,H4,H5}.(ii)
PartialKeyGen: Given a user’s identity IDi, the KGC computes Qi,1=H1(IDi) and Qi,2=H1′(IDi). Then, the KGC computes pski=(pski,1,pski,2)=((Qi,1)s,(Qi,2)s) and sends IDi’s partial private key pski to the user through a secure channel.(iii)
UserKeyGen: The user with identity IDi generates a public/private key pair (upki,ski) according to the following steps:
(a)
Select two random integersxi,1,xi,2∈Zp∗ and compute the public key upki=(upki,1,upki,2)=(gxi,1,gxi,2).(b)
Set the secret valueuski=(xi,1,xi,2) and the corresponding private key ski=(pski,uski).(iv)
Sign: Given a message mi and state information st∈{0,1}∗, a signer with identity IDi performs the following:
(a)
Select a random integerri∈Zp∗ and compute Ri=gri.(b)
ComputeW=H2(st), V=H3(st), hi=H4(mi,IDi,upki,pp), hi′=H5(mi, IDi,upki,pp) and(7)Yi=pski,1hi·pski,2·Whi′xi,1+xi,2·Vri.(c)
Output a signatureσi=(Ri,Yi) on mi.(v)
Verify: Given an identity IDi, a public key upki=(upki,1,upki,2), state information st, a message mi, and a signature σi= (Ri,Yi), a verifier first computes Qi,1=H1(IDi), Qi,2=H1′(IDi), W=H2(st), V=H3(st), hi=H4(mi,IDi,upki,pp) and hi′=H5(mi, IDi,upki,pp). Then, the verifier checks the following equation:(8)eYi,g=eQi,1hiQi,2,Ppub·eupki,1hi′upki,2,W·eRi,V.If this equation holds, then the verifier acceptsσi; otherwise, the verifier rejects σi.(vi)
Aggregate: Given n message-signature pairs {(m1,σ1=(R1,Y1)),…,(mn,σn=(Rn,Yn))} from n users, the aggregator outputs an aggregate signature σ=(R,Y) on messages {m1,…,mn}, where R=∏i=1nRi and Y=∏i=1nYi.(vii)
AggregateVerify: Given n identities {ID1,…,IDn}, n public keys {upk1=(upk1,1,upk1,2),…,upkn=(upkn,1,upkn,2)}, state information st, and an aggregate signature σ=(R,Y) on n messages {m1,…,mn}, a verifier first computes Qi,1=H1(IDi), Qi,2=H1′(IDi), W=H2(st), V=H3(st), hi=H4(mi,IDi, upki,pp), and hi′=H5(mi, IDi,upki,pp) for 1≤i≤n. Then, the verifier checks the following equation:(9)eY,g=e∏i=1nQi,1hiQi,2,Ppub·e∏i=1nupki,1hi′upki,2,W·eR,V.If the equation holds, then the verifier acceptsσ; otherwise, the verifier rejects σ.


### 5.2. Attack on Chen et al.’s CLAS Scheme

Chen et al. [18] demonstrated that their CLAS scheme was provably secure in the random oracle model. In this section, we present an attack on Chen et al.’s CLAS scheme [18] to demonstrate that their scheme cannot withstand an attack from a coalition of insider signers. Without loss of generality, we assume that {U1,U2} are two signers with identities {ID1,ID2} and corresponding public keys {upk1=(upk1,1,upk1,2),upk2=(upk2,1,upk2,2)}, respectively. A message m1 is signed by U1 with the private key sk1=(psk1,usk1)=((psk1,1,psk1,2),(x1,1,x1,2)), and another message m2 is signed by U2 with the private key sk2=(psk2,usk2)=((psk2,1,psk2,2),(x2,1,x2,2)). In the following attack, U1 cooperates with U2 to generate invalid signatures {σ1∗,σ2∗} on {m1,m2}, while the corresponding aggregate signature σ∗ on {m1,m2} satisfies the aggregate signature verification equation. Let st be the state information, W=H2(st) and V=H3(st).(1)
U1 chooses a random integer r1∈Zp∗ and computes R1∗=gr1, h1=H4(m1,ID1, upk1,pp) and h1′=H5(m1, ID1,upk1,pp). Then, U1 sends Vr1 to U2.(2)
U2 chooses a random integer r2∈Zp∗ and computes R2∗=gr2, h2=H4(m2,ID2, upk2,pp) and h2′=H5(m2, ID2,upk2,pp). Then, U2 sends Vr2 to U1.(3)
U1 computes Y1∗=(psk1,1)h1·psk1,2·Wh1′x1,1+x1,2·Vr2 and sets σ1∗=(R1∗,Y1∗) as a signature on m1.(4)
U2 computes Y2∗=(psk2,1)h2·psk2,2·Wh2′x2,1+x2,2·Vr1 and sets σ2∗=(R2∗,Y2∗) as a signature on m2.(5)
U1 cooperates with U2 to generate a forged aggregate signature σ∗=(R∗,Y∗) on {m1,m2}, where R∗=R1∗R2∗ and Y∗=Y1∗Y2∗.Clearly,σ1∗=(R1∗,Y1∗) is an invalid single signature on m1 since it does not satisfy the verification equation as follows:(10)eY1∗,g=epsk1,1h1psk1,2Wh1′x1,1+x1,2Vr2,g=epsk1,1h1psk1,2,geWh1′x1,1+x1,2,gegr2,V=eH1ID1h1H1′ID1,Ppub·eupk1,1h1′upk1,2,W·eR2∗,V≠eQ1,1h1Q1,2,Ppub·eupk1,1h1′upk1,2,W·eR1∗,VSimilarly, the single signature σ2∗=(R2∗,Y2∗) on m2 is also invalid. However, σ∗=(R∗,Y∗) is a valid aggregate signature on {m1,m2}. The correctness of σ∗ can be verified as follows:(11)eY∗,g=eY1∗Y2∗,g=epsk1,1h1psk1,2Wh1′x1,1+x1,2Vr2·psk2,1h2psk2,2Wh2′x2,1+x2,2Vr1,g=epsk1,1h1psk1,2Wh1′x1,1+x1,2Vr1·psk2,1h2psk2,2Wh2′x2,1+x2,2Vr2,g=e∏i=12Qi,1hiQi,2,Ppub·e∏i=12upki,1hi′upki,2,W·eR∗,V.Hence, in Chen et al.’s CLAS scheme [18], dishonest insider signers can cooperate to forge valid aggregate signatures of arbitrary messages by combining invalid individual signatures. This result also shows that the validity of an aggregate signature does not guarantee the validity of every signature involved in the aggregation. Therefore, our attack is successful; that is, Chen et al.’s CLAS scheme [18] is insecure against coalition attacks.


## 5.1. Review of Chen et al.’s Scheme

Chen et al.’s CLAS scheme [18] is described as follows:(i)
Setup: Given a security parameter λ∈Z, the KGC performs the following steps to generate the public parameters pp and the master secret key msk:
(a)
Choose two cyclic groupsG1 and G2 of prime order p, a generator g of G1 and a bilinear pairing e:G1×G1→G2.(b)
Select a random integers∈Zp∗ and compute Ppub=gs.(c)
Pick six cryptographic hash functionsH1,H1′,H2, H3:{0,1}∗→G1 and H4,H5: {0,1}∗→Zp∗.(d)
Keep the master secret keymsk=s secret and publish public parameters pp={G1,G2,p,g,e,Ppub,H1,H1′,H2,H3,H4,H5}.(ii)
PartialKeyGen: Given a user’s identity IDi, the KGC computes Qi,1=H1(IDi) and Qi,2=H1′(IDi). Then, the KGC computes pski=(pski,1,pski,2)=((Qi,1)s,(Qi,2)s) and sends IDi’s partial private key pski to the user through a secure channel.(iii)
UserKeyGen: The user with identity IDi generates a public/private key pair (upki,ski) according to the following steps:
(a)
Select two random integersxi,1,xi,2∈Zp∗ and compute the public key upki=(upki,1,upki,2)=(gxi,1,gxi,2).(b)
Set the secret valueuski=(xi,1,xi,2) and the corresponding private key ski=(pski,uski).(iv)
Sign: Given a message mi and state information st∈{0,1}∗, a signer with identity IDi performs the following:
(a)
Select a random integerri∈Zp∗ and compute Ri=gri.(b)
ComputeW=H2(st), V=H3(st), hi=H4(mi,IDi,upki,pp), hi′=H5(mi, IDi,upki,pp) and(7)Yi=pski,1hi·pski,2·Whi′xi,1+xi,2·Vri.(c)
Output a signatureσi=(Ri,Yi) on mi.(v)
Verify: Given an identity IDi, a public key upki=(upki,1,upki,2), state information st, a message mi, and a signature σi= (Ri,Yi), a verifier first computes Qi,1=H1(IDi), Qi,2=H1′(IDi), W=H2(st), V=H3(st), hi=H4(mi,IDi,upki,pp) and hi′=H5(mi, IDi,upki,pp). Then, the verifier checks the following equation:(8)eYi,g=eQi,1hiQi,2,Ppub·eupki,1hi′upki,2,W·eRi,V.If this equation holds, then the verifier acceptsσi; otherwise, the verifier rejects σi.(vi)
Aggregate: Given n message-signature pairs {(m1,σ1=(R1,Y1)),…,(mn,σn=(Rn,Yn))} from n users, the aggregator outputs an aggregate signature σ=(R,Y) on messages {m1,…,mn}, where R=∏i=1nRi and Y=∏i=1nYi.(vii)
AggregateVerify: Given n identities {ID1,…,IDn}, n public keys {upk1=(upk1,1,upk1,2),…,upkn=(upkn,1,upkn,2)}, state information st, and an aggregate signature σ=(R,Y) on n messages {m1,…,mn}, a verifier first computes Qi,1=H1(IDi), Qi,2=H1′(IDi), W=H2(st), V=H3(st), hi=H4(mi,IDi, upki,pp), and hi′=H5(mi, IDi,upki,pp) for 1≤i≤n. Then, the verifier checks the following equation:(9)eY,g=e∏i=1nQi,1hiQi,2,Ppub·e∏i=1nupki,1hi′upki,2,W·eR,V.If the equation holds, then the verifier acceptsσ; otherwise, the verifier rejects σ.


## 5.2. Attack on Chen et al.’s CLAS Scheme

Chen et al. [18] demonstrated that their CLAS scheme was provably secure in the random oracle model. In this section, we present an attack on Chen et al.’s CLAS scheme [18] to demonstrate that their scheme cannot withstand an attack from a coalition of insider signers. Without loss of generality, we assume that {U1,U2} are two signers with identities {ID1,ID2} and corresponding public keys {upk1=(upk1,1,upk1,2),upk2=(upk2,1,upk2,2)}, respectively. A message m1 is signed by U1 with the private key sk1=(psk1,usk1)=((psk1,1,psk1,2),(x1,1,x1,2)), and another message m2 is signed by U2 with the private key sk2=(psk2,usk2)=((psk2,1,psk2,2),(x2,1,x2,2)). In the following attack, U1 cooperates with U2 to generate invalid signatures {σ1∗,σ2∗} on {m1,m2}, while the corresponding aggregate signature σ∗ on {m1,m2} satisfies the aggregate signature verification equation. Let st be the state information, W=H2(st) and V=H3(st).(1)
U1 chooses a random integer r1∈Zp∗ and computes R1∗=gr1, h1=H4(m1,ID1, upk1,pp) and h1′=H5(m1, ID1,upk1,pp). Then, U1 sends Vr1 to U2.(2)
U2 chooses a random integer r2∈Zp∗ and computes R2∗=gr2, h2=H4(m2,ID2, upk2,pp) and h2′=H5(m2, ID2,upk2,pp). Then, U2 sends Vr2 to U1.(3)
U1 computes Y1∗=(psk1,1)h1·psk1,2·Wh1′x1,1+x1,2·Vr2 and sets σ1∗=(R1∗,Y1∗) as a signature on m1.(4)
U2 computes Y2∗=(psk2,1)h2·psk2,2·Wh2′x2,1+x2,2·Vr1 and sets σ2∗=(R2∗,Y2∗) as a signature on m2.(5)
U1 cooperates with U2 to generate a forged aggregate signature σ∗=(R∗,Y∗) on {m1,m2}, where R∗=R1∗R2∗ and Y∗=Y1∗Y2∗.Clearly,σ1∗=(R1∗,Y1∗) is an invalid single signature on m1 since it does not satisfy the verification equation as follows:(10)eY1∗,g=epsk1,1h1psk1,2Wh1′x1,1+x1,2Vr2,g=epsk1,1h1psk1,2,geWh1′x1,1+x1,2,gegr2,V=eH1ID1h1H1′ID1,Ppub·eupk1,1h1′upk1,2,W·eR2∗,V≠eQ1,1h1Q1,2,Ppub·eupk1,1h1′upk1,2,W·eR1∗,VSimilarly, the single signature σ2∗=(R2∗,Y2∗) on m2 is also invalid. However, σ∗=(R∗,Y∗) is a valid aggregate signature on {m1,m2}. The correctness of σ∗ can be verified as follows:(11)eY∗,g=eY1∗Y2∗,g=epsk1,1h1psk1,2Wh1′x1,1+x1,2Vr2·psk2,1h2psk2,2Wh2′x2,1+x2,2Vr1,g=epsk1,1h1psk1,2Wh1′x1,1+x1,2Vr1·psk2,1h2psk2,2Wh2′x2,1+x2,2Vr2,g=e∏i=12Qi,1hiQi,2,Ppub·e∏i=12upki,1hi′upki,2,W·eR∗,V.Hence, in Chen et al.’s CLAS scheme [18], dishonest insider signers can cooperate to forge valid aggregate signatures of arbitrary messages by combining invalid individual signatures. This result also shows that the validity of an aggregate signature does not guarantee the validity of every signature involved in the aggregation. Therefore, our attack is successful; that is, Chen et al.’s CLAS scheme [18] is insecure against coalition attacks.


## 6. Improved Certificateless Aggregate Signature Scheme

In Chen et al.’s CLAS scheme [18], Du et al.’s CLAS scheme [17], and Li et al.’s CLAS scheme [15], the main reason that the abovementioned coalition attacks can occur is that insider signers can exchange some information involved in the individual signature generation, such as hri and (Ppub)riQri. To overcome these security weaknesses, we propose an improved CLAS scheme based on Chen et al.’s CLAS scheme [18]. Our CLAS scheme is described as follows:(i)
TheSetup,PartialKeyGen, andUserKeyGen algorithms are the same as those of Chen et al.’s CLAS scheme described in Section 4. The only difference is that theSetup algorithm adds a collision-resistant hash function H6:{0,1}∗→{0,1}l, where l is the length of the output message of H6.(ii)
Sign: Given a message mi and state information st∈{0,1}∗, a signer with identity IDi executes the following steps:
(a)
Randomly selectri∈Zp∗ and compute Ri=gri.(b)
ComputeW=H2(st), V=H3(st), hi=H4(mi,IDi,upki,Ri,W,V,pp), hi′=H5(mi,IDi, upki,Ri,W,V,pp) and(12)Yi=pski,1hi·pski,2·Whi′xi,1+xi,2+hiri·Vri.(c)
Outputσi=(Ri,Yi) as a signature on mi.(iii)
Verify: This algorithm is the same as theVerify algorithm in Chen et al.’s CLAS scheme, except that the signature verification equation is modified as follows:(13)eYi,g=eQi,1hiQi,2,Ppub·eupki.1hi′upki,2Rihi,W·eRi,V,wherehi=H4(mi,IDi,upki,Ri,W,V,pp) and hi′=H5(mi, IDi,upki,Ri,W,V,pp).(iv)
Aggregate: Given n message-signature pairs {(m1,σ1=(R1,Y1)),…,(mn,σn=(Rn,Yn))} from n signers, the aggregator first computes(14)Y=H6eY1,g,…,eYn,gand then outputs an aggregate signatureσ=(R1,…,Rn,Y) on messages {m1,…,mn}.(v)
AggregateVerify: Given n identities {ID1,…,IDn}, n public keys {upk1=(upk1,1,upk1,2),…,upkn=(upkn,1,upkn,2)}, state information st and an aggregate signature σ=(R1,…,Rn,Y) on n messages {m1,…,mn}, a verifier first computes Qi,1=H1(IDi), Qi,2=H1′(IDi), W=H2(st), V=H3(st), hi=H4(mi,IDi,upki,Ri,W,V,pp) and hi′=H5(mi, IDi,upki,Ri,W,V,pp) for 1≤i≤n. Then, the verifier checks whether(15)Y=H6eQ1,1h1Q1,2,Ppub·eupk1,1h1′upk1,2R1h1,W·eR1,V,…,eQn,1hnQn,2,Ppub·eupkn,1hn′upkn,2Rnhn,W·eRn,Vholds. If it holds, then the verifier acceptsσ; otherwise, the verifier rejects σ.IfHi is a collision-resistant hash function, then it is difficult to find z1 and z2 such that Hi(z1)=Hi(z2) [24]. In our improved CLAS scheme, if the KGC selects t1,t2∈Zp∗ and computes W=gt1 and V=gt2, then the KGC is unable to find a unique st to satisfy H2(st)=W and H3(st)=V due to the collision resistance of H2 and H3. However, if the KGC computes W=H2(st)=gt1 and V=H3(st)=gt2, then the difficulty of the KGC calculating t1,t2∈Zp∗ from W and V is equivalent to solving the discrete logarithm problem. Therefore, the improved CLAS scheme can resist malicious-but-passive KGC attacks unless the adversary can break the collision resistance of H2 and H3.The partRi in every individual signature is embedded in hash values hi=H4(mi,IDi,upki,Ri,W,V,pp) and hi′=H5(mi, IDi,upki,Ri,W,V,pp), which makes it impossible for an attacker to modify Ri at will. Hence, our improved CLAS scheme is resistant to the universal forgery attacks in [19–21].The unforgeability of the proposed CLAS scheme is almost the same as that of Chen et al.’s CLAS scheme. Since Chen et al. [18] demonstrated that their CLAS scheme is existentially unforgeable in the random oracle model, our improved CLAS scheme can be similarly proven to be existentially unforgeable in the random oracle model. The security proofs of the two schemes are basically the same, so we omit the detailed description. Here, we prove only that the proposed CLAS scheme can resist the coalition attack described in Section 4.Theorem 1.
If the hash functionH6 is collision-resistant, then the proposed CLAS scheme can withstand attacks from the coalition of insider signers.Proof.
If each signatureσi= (Ri,Yi) involved in the aggregation is valid, we have that(16)eYi,g=eQi,1hiQi,2,Ppub·eupki,1hi′upki,2Rihi,W·eRi,Vfori=1,…,n.Thus, we can obtain(17)Y=H6eY1,g,…,eYn,g=H6eQ1,1h1Q1,2,Ppub·eupk1,1h1′upk1,2R1h1,W·eR1,V,…,eQn,1hnQn,2,Ppub·eupkn,1hn′upkn,2Rnhn,W·eRn,V.Therefore, the corresponding aggregate signature σ=(R1,…,Rn,Y) is also valid.
Meanwhile, if an aggregate signatureσ=(R1,…,Rn,Y) is valid, we have(18)Y=H6eQ1,1h1Q1,2,Ppub·eupk1,1h1′upk1,2R1h1,W·eR1,V,…,eQn,1hnQn,2,Ppub·eupkn,1hn′upkn,2Rnhn,W·eRn,V=H6eY1,g,…,eYn,g. Since the hash function H6 is collision-resistant, H6(Vri,Vrj) is not equal to H6(Vrj,Vri) for any two values Vri and Vrj. From the above aggregate signature verification equation, we derive the following equations:(19)eYi,g=eQi,1hiQi,2,Ppub·eupki,1hi′upki,2Rihi,W·eRi,Vfori=1,…,n.This derivation implies that an aggregate signature σ=(R1,…,Rn,Y) is valid if and only if each signature σi= (Ri,Yi) involved in the aggregation is valid. Therefore, the proposed CLAS scheme can withstand forgery attacks from a coalition of insider signers.


## 7. Conclusion

In this paper, we present a cryptanalysis of three CLAS schemes. The analysis shows that Li et al.’s CLAS scheme [15], Du et al.’s CLAS scheme [17], and Chen et al.’s CLAS scheme [18] are insecure against attacks from a coalition of insider signers. To overcome these attacks, we propose an improved CLAS scheme. Compared with Chen et al.’s CLAS scheme [18], our improved scheme has large computational overhead in generating and verifying aggregate signatures. How to construct a secure CLAS scheme without bilinear pairing is a challenging issue, which we leave as an open problem.



---

*Source: 1908632-2018-08-23.xml*