Reattack of a Certificateless Aggregate Signature Scheme with Constant Pairing Computations

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.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Hang Tu 1 and Debiao He 2 and Baojun Huang 2

Academic Editor:T. M. Deserno and Academic Editor:W. Zuo

1, School of Computer, Wuhan University, Wuhan 430072, China
2, School of Mathematics and Statistics, Wuhan University, Wuhan 430072, China

Received 20 September 2013; Accepted 9 January 2014; 13 March 2014

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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. Section 2 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

Let _G1 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 [arrow right]_G2 which satisfies the following properties.

(1) Bilinearity [figure omitted; refer to PDF]

where Q,R∈_G1 , a,b∈^Zq* .

(2) Nondegeneracy [figure omitted; refer to PDF]

(3) Computability: there is an efficient algorithm to compute e(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 ...9C;1 and the Type II adversary ...9C;2 . The adversary ...9C;1 is not able to access the master key but he could replace public keys at his will. The adversary ...9C;2 represents a malicious KGC who generates partial private key of users. ...9C;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 us_kIDi , and the public key up_kIDi . It then stores the tuple (_IDi ,ps_kIDi ,up_kIDi ,us_kIDi ) into a list L . In both cases, ps_kIDi 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, [perpendicular] 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, [perpendicular] is returned; otherwise, the corresponding us_kIDi is returned.

(iv) ReplaceKey : On input of an identity _IDi and a user public/secret key pair (^{upk_IDi [variant prime]} ,^{usk_IDi [variant prime]} ), the oracle searches L for the entry of _IDi . If it is not found, nothing will be carried out. Otherwise, the oracle updates (_IDi ,ps_kIDi ,up_kIDi ,us_kIDi ) to (_IDi ,ps_kIDi ,^{upk_IDi [variant prime]} ,^{usk_IDi [variant prime]} ).

(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 (us_kIDi ,up_kIDi ) has not been replaced.

(b) If _IDi has not been created, a symbol [perpendicular] is returned.

(c) If the user public/secret key pair of _IDi has been replaced with say (^{upk_IDi [variant prime]} ,^{usk_IDi [variant prime]} ), then the oracle returns the result of Sign(^{usk_IDi [variant prime]} ,^{psk_IDi [variant prime]} ,_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 ...9E; and an adversary ...9C;∈{...9C;1,...9C;2} for a CLS scheme as follows.

(i) ...9E; executes MasterKeyGen to get master private/public key pair (mpk,msk ).

(ii) ...9C; can adaptively issue the CreateUser , RevealPartialKey , RevealSecertKey , ReplaceKey , and Sign queries to ...9E; .

(iii): ...9C; is to output a message ^mi* and a signature ^σi* corresponding to a target identity ^IDi* and a public key up_k^IDi* .

We say that ...9C; 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 up_k^IDi* .

(2) If ...9C; is ...9C;1 , the identity ^IDi* has not submitted to RevealPartialKey queries to get the partial private key ps_k^IDi* . If ...9C; is ...9C;2 , ^IDi* has not submitted to RevealSecertKey queries or ReplaceKey queries to get the secret key us_k^IDi* .

(3) The oracle Sign 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 ...9C;∈{...9C;1,...9C;2} , which wins Game 1 with nonnegligible advantage.

Game 2.

The second game is performed between a challenger ...9E; and an adversary ...9C;∈{...9C;1,...9C;2} for a CLAS scheme as follows.

(i) ...9E; executes MasterKeyGen to get master private/public key pair (mpk,msk ).

(ii) ...9C; can adaptively issue the CreateUser , RevealPartialKey , RevealSecertKey , ReplaceKey , and Sign queries to ...9E; .

(iii): ...9C; outputs a set of n users whose identities are from the set ^LID* ={^ID1* ,...,^IDn* } and corresponding public keys from the set ^Lupk* ={up^k1* ,...,up^kn* } , n messages ^Lm* ={^m1* ,...,^mn* } , and an aggregate signature ^σ* .

We say that ...9C; 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 {up^k1* ,...,up^kn* } .

(2) If ...9C; is ...9C;1 , at least one of the identities ^IDi* has not submitted to RevealPartialKey queries to get the partial private key ps_k^IDi* . If ...9C; is ...9C;2 , at least one of ^IDi* has not been submitted to RevealSecertKey queries or ReplaceKey queries to get the secret key us_k^IDi* .

(3) The oracle Sign 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 ...9C;∈{...9C;1,...9C;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 , and Verify . 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 group _G1 and a cyclic multiplicative group _G2 with prime order q .

(2) Generate two generators P , Q of _G1 and an admissible pairing e:_G1 ×_G1 [arrow right]_G2 .

(3) Generate a random number s∈^Zq* and compute _Ppub =sP .

(4) Choose cryptographic hash functions _H1 :{0,1^}* [arrow right]_G1 and _H2 :{0,1^}* [arrow right]^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 ps_kIDi =s_QIDi 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 us_kIDi and computes his public key as up_kIDi =us_kIDi ·P .

Sign . Given a message _mi , the partial private key ps_kIDi , the secret key us_kIDi , the user with identity _IDi , and the corresponding public key up_kIDi , perform the following steps to generate a signature.

(1) Generate a random number _ri ∈^Zq* and compute _Ui =_ri P .

(2) Compute _hi =_H2 (_mi ,_IDi ,up_kIDi ,_Ui ) , _Vi =ps_kIDi +_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 up_kIDi :

(1) Compute _QIDi =_H1 (_IDi ) and _hi =_H2 (_mi ,_IDi ,up_kIDi ,_Ui ) .

(2) Verify e(_Vi ,P)=e(_hi ·_Ui +_QIDi ,_Ppub )e(_hi ·up_kIDi ,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 , and AggregateVerify . 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 {_U1 ,...,_Un } with identities {_ID1 ,...,_IDn } , corresponding public keys {up_k1 ,...,up_kn } , and message-signature pairs {(_m1 ,_σ1 =(_U1 ,_V1 )),...,(_mn ,_σn =(_Un ,_Vn ))} from {_U1 ,...,_Un } , respectively, the aggregate signature generator computes V=^∑i=1n_Vi and outputs σ=(_U1 ,...,_U2 ,V) as an aggregate signature.

AggregateVerify . To verify an aggregate signature σ=(_U1 ,...,_U2 ,V) signed by n users {_U1 ,...,_Un } with identities {_ID1 ,...,_IDn } and the corresponding public keys {up_k1 ,...,up_kn } on messages {_m1 ,...,_mn } , the verifier performs the following steps.

(1) Compute _QIDi =_H1 (_IDi ) and _hi =_H2 (_mi ,_IDi ,up_kIDi ,_Ui ) for i=1,...,n .

(2) Verify e(V,P)=e(^∑i=1n (_hi ·_Ui +_QIDi ),_Ppub )e(^∑i=1n_hi ·up_kIDi ,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 ...9C;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 ...9C;2 be a malicious KGC. Then ...9C;2 could choose a random t and compute Q=tP , when he generates the system parameters. After that, ...9C;2 could forge a legal signature of any message.

(1) The Type II adversary ...9C;2 has the master key s . Then, he could compute a user _Ui 's partial private key ps_kIDi =s_QIDi , where _QIDi =_H1 (_IDi ) .

(2) For any message _mi , ...9C;2 generates a random number _ri ∈^Zq* and computes _Ui =_ri P , _hi =_H2 (_mi ,_IDi ,up_kIDi ,_Ui ) and _Vi =ps_kIDi +_hi ·_ri ·_Ppub +_hi ·t·up_kIDi .

(3) ...9C;2 outputs (_Ui ,_Vi ) as the signature on _mi .

Since Q=tP , _Ui =_ri P , and _Vi =ps_kIDi +_hi ·_ri ·_Ppub +_hi ·t·up_kIDi , we could have [figure omitted; refer to PDF]

Then, we know that (_Ui ,_Vi ) is a legal signature on _mi . Besides, _IDi has not been submitted to RevealSecertKey queries or ReplaceKey queries to get the secret key us_k^IDi* and the oracle Sign has never been queried with (_IDi ,_mi ). So the Type II adversary ...9C;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 ...9C;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 ...9C;2 be a malicious KGC. Then ...9C;2 could choose a random t and compute Q=tP , when he generates the system parameters. After that, ...9C;2 could forge an aggregate signature.

Let {_U1 ,...,_Un } be an aggregating set of n users with identities {_ID1 ,...,_IDn } and the corresponding public keys {up_k1 ,...,up_kn } .

(1) For i=1,2,...,n , ...9C;2 does the following five substeps to generate a legal signature (_Ui ,_Vi ) on a message _mi .

(i) The Type II adversary ...9C;2 has the master key s . Then, he could compute a user _Ui 's partial private key ps_kIDi =s_QIDi , where _QIDi =_H1 (_IDi ) .

(ii) For any message _mi , ...9C;2 generates a random number _ri ∈^Zq* and computes _Ui =_ri P , _hi =_H2 (_mi ,_IDi ,up_kIDi ,_Ui ) , and _Vi =ps_kIDi +_hi ·_ri ·_Ppub +_hi ·t·up_kIDi .

(iii): ...9C;2 outputs (_Ui ,_Vi ) as the signature on _mi .

(2) ...9C;2 computes V=^∑i=1n_Vi .

(3) ...9C;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 ,s_Ppub )e(_hi ·up_kIDi ,Q) , where Q=tP and _Vi =ps_kIDi +_hi ·_ri ·_Ppub +_hi ·t·up_kIDi . Then we could have that [figure omitted; refer to PDF]

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 to RevealSecertKey queries or ReplaceKey queries to get the secret key us_k^IDi* and the oracle Sign has never been queried with (_IDi ,_mi ). So the Type II adversary ...9C;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 , and Verify . 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 group _G1 and a cyclic multiplicative group _G2 with prime order q .

(2) Generate a generator P of _G1 and an admissible pairing e:_G1 ×_G1 [arrow right]_G2 .

(3) Generate a random number s∈^Zq* and compute _Ppub =sP .

(4) Choose cryptographic hash functions _H1 ,_H2 ,_H3 :{0,1^}* [arrow right]_G1 and _H4 ,_H5 :{0,1^}* [arrow right]^Zq* .

(5) KGC publishes the system parameters params={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 ps_kIDi =s_QIDi 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 us_kIDi and computes his public key as up_kIDi =us_kIDi ·P .

Sign . Given a message _mi , the partial private key ps_kIDi , the secret key us_kIDi , the user with identity _IDi , and the corresponding public key up_kIDi , perform the following steps to generate a signature.

(1) Generate a random number _ri ∈^Zq* and compute _Ui =_ri P .

(2) Compute W=_H2 (params) , T=_H3 (params) , _hi =_H4 (_mi ,_IDi ,up_kIDi ,_Ui ) , and _ki =_H5 (_mi ,_IDi ,up_kIDi ,_Ui ) .

(3) Compute, _Vi =ps_kIDi +_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 up_kIDi , consider the following.

(1) Compute _QIDi =_H1 (_IDi ) , W=_H2 (params) , T=_H3 (params) , _hi =_H4 (_mi ,_IDi ,up_kIDi ,_Ui ) , and _ki =_H5 (_mi ,_IDi ,up_kIDi ,_Ui ) .

(2) Verify e(_Vi ,P)=e(_QIDi ,_Ppub )e(_hi ·up_kIDi ,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 , and AggregateVerify . 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 {_U1 ,...,_Un } with identities {_ID1 ,...,_IDn } , corresponding public keys {up_k1 ,...,up_kn } , and message-signature pairs {(_m1 ,_σ1 =(_U1 ,_V1 )),...,(_mn ,_σn =(_Un ,_Vn ))} from {_U1 ,...,_Un } , respectively, the aggregate signature generator computes V=^∑i=1n_Vi and outputs σ=(_U1 ,...,_Un ,V) as an aggregate signature.

AggregateVerify . To verify an aggregate signature σ=(_U1 ,...,_Un ,V) signed by n users {_U1 ,...,_Un } with identities {_ID1 ,...,_IDn } and the corresponding public keys {up_k1 ,...,up_kn } on messages {_m1 ,...,_mn } , the verifier performs the following steps.

(1) Compute _QIDi =_H1 (_IDi ) , W=_H2 (params) , T=_H3 (params) , _hi =_H4 (_mi ,_IDi ,up_kIDi ,_Ui ) , and _ki =_H5 (_mi ,_IDi ,up_kIDi ,_Ui ) for i=1,...,n .

(2) Verify e(V,P)=e(^∑i=1n_QIDi ,_Ppub )e(^∑i=1n_hi ·up_kIDi ,Q)e(^∑i=1n_ki ·_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 ...9C;1 wins Game 1 with nonnegligible probability [straight epsilon] , 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 ...9E; to compute xyP , where x,y∈^Zq* and they are unknown to ...9E; . At first, ...9E; 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 ...9C;1 . Then ...9E; answers ...9C;1 's query as follows.

(i) _H1 query : ...9E; maintains a list _LH1 of form Y9;_IDi ,_aIDi ,_QIDi YA; . When ...9C;1 makes this query on _IDi , ...9E; does as follows.

(a) If the list _LH1 contains a tuple Y9;_IDi ,_aIDi ,_QIDi YA; , ...9E; returns _QIDi to ...9C;1 .

(b) Otherwise, if _IDi =_IDI , ...9E; picks a random _aIDi ∈^Zn* , computes _QIDi =_aIDi Y , adds Y9;_IDi ,_aIDi ,_QIDi YA; to _LH1 , and returns _QIDi to ...9C;1 .

(c) Otherwise (_IDi ...0;_IDI ), ...9E; picks a random _aIDi ∈^Zn* , computes _QIDi =_aIDi P , adds Y9;_IDi ,_aIDi ,_QIDi YA; to _LH1 , and returns _QIDi to ...9C;1 .

(ii) _H2 query : ...9E; maintains a list _LH2 of form Y9;_mi ,_bi ,_Wi YA; . When ...9C;1 makes this query on _mi , ...9E; does as follows.

(a) If the list _LH2 contains a tuple Y9;_mi ,_bi ,_Wi YA; , ...9E; returns _Wi to ...9C;1 .

(b) Otherwise, ...9E; picks a random _bi ∈^Zn* , computes _Wi =_bi P , adds Y9;_mi ,_bi ,_Wi YA; to _LH2 , and returns _Wi to ...9C;1 .

(iii): _H3 query : ...9E; maintains a list _LH3 of form Y9;_mi ,_ci ,_Ti YA; . When ...9C;1 makes this query on _mi , ...9E; does as follows.

(a) If the list _LH3 contains a tuple Y9;_mi ,_ci ,_Ti YA; , ...9E; returns _Ti to ...9C;1 .

(b) Otherwise, ...9E; picks a random _ci ∈^Zn* , computes _Ti =_ci X , adds Y9;_mi ,_ci ,_Ti YA; to _LH3 , and returns _Ti to ...9C;1 .

(iv) _H4 query : ...9E; maintains a list _LH4 of form Y9;_mi ,_IDi ,up_kIDi ,_Ui ,_hi YA; . When ...9C;1 makes this query on (_mi ,_IDi ,up_kIDi ,_Ui ) , ...9E; does as follows.

(a) If the list _LH4 contains a tuple Y9;_mi ,_IDi ,up_kIDi ,_Ui ,_hi YA; , ...9E; returns _hi to ...9C;1 .

(b) Otherwise, ...9E; picks a random _hi ∈^Zn* , returns _hi to ...9C;1 , and adds Y9;_mi ,_IDi ,up_kIDi ,_Ui ,_hi YA; to _LH4 .

(v) _H5 query : ...9E; maintains a list _LH5 of form Y9;_mi ,_IDi ,up_kIDi ,_Ui ,_ki YA; . When ...9C;1 makes this query on (_mi ,_IDi ,up_kIDi ,_Ui ) , ...9E; does as follows.

(a) If the list _LH5 contains a tuple Y9;_mi ,_IDi ,up_kIDi ,_Ui ,_ki YA; , ...9E; returns _ki to ...9C;1 .

(b) Otherwise, ...9E; picks a random _ki ∈^Zn* , returns _ki to ...9C;1 , and adds Y9;_mi ,_IDi ,up_kIDi ,_Ui ,_hi YA; to _LH5 .

(vi) CreateUser : ...9E; maintains a list _LU of form Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; . When ...9C;1 makes this query on _IDi , ...9E; does as follows.

(a) If the list _LU contains a tuple Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; , ...9E; returns up_kIDi to ...9C;1 .

(b) Otherwise, if _IDi =_IDI , ...9E; gets _QIDI =_aIDI Y by making _H1 query with _IDI and sets ps_kIDI [arrow left][perpendicular] . ...9E; selects a random number _xIDi ∈^Zq* as his secret key us_kIDi and computes his public key as up_kIDi =us_kIDi ·P . At last, ...9E; adds Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; to _LU and returns up_kIDi to ...9C;1 .

(c) Otherwise (_IDi ...0;_IDI ), ...9E; gets _QIDi =_aIDi ·P by making _H1 query with _IDi and sets ps_kIDi =_aIDi ·_Ppub . ...9E; selects a random number _xIDi ∈^Zq* as his secret key us_kIDi and computes his public key as up_kIDi =us_kIDi ·P . At last, ...9E; adds Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; to _LU and returns up_kIDi to ...9C;1 .

(vii): RevealPartialKey : when ...9C;1 makes this query on _IDi , ...9E; does as follows.

(a) If _IDi =_IDI , ...9E; stops the simulation.

(b) Otherwise (_IDi ...0;_IDI ), ...9E; looks up the list _LU for the tuple Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; and returns ps_kIDi to ...9C;1 .

(viii): RevealSecertKey : when ...9C;1 makes this query on _IDi , ...9E; looks up the list _LU for the tuple Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; and returns us_kIDi to ...9C;1 .

(ix) ReplaceKey : when ...9C;1 makes this query on (_IDi ,^{upk_IDi [variant prime]} ) , ...9E; looks up the list _LU for the tuple Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; . ...9E; sets us_kIDi [arrow left][perpendicular] and replaces up_kIDi with ^{upk_IDi [variant prime]} .

(x) Sign : when ...9C;1 makes this query on (_mi ,_IDi ) , ...9E; does as follows.

(a) If _IDi =_IDI , ...9E; looks up lists _LH1 and _LU and for tuples Y9;_IDi ,_aIDi ,_QIDi YA; and Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; separately, where _QIDi =_aIDi Y and up_kIDi may have been replaced by ...9C;1 . ...9E; makes _H2 query and _H3 query with params and gets tuples Y9;params,_bi ,WYA; and Y9;params,_ci ,TYA; , where W=_bi P and T=_ci X . ...9E; generates three random numbers _hi ,_ki ,_ri ∈^Zq* , computes _Ui =^ki-1 (_ri ·P-_aIDi ·^ci-1 ·Y) , _Vi =_ri ·T+_hi ·_bi ·up_kIDi , and sets _H4 (_mi ,_IDi ,up_kIDi ,_Ui )[arrow left]_hi , _H5 (_mi ,_IDi ,up_kIDi ,_Ui )[arrow left]_ki . At last, ...9E; adds tuples Y9;_mi ,_IDi ,up_kIDi ,_Ui ,_hi YA; and Y9;_mi ,_IDi ,up_kIDi ,_Ui ,_ki YA; to _LH4 and _LH5 separately and returns (_Ui ,_Vi ) to ...9C;1 . It is easy to say (_Ui ,_Vi ) satisfies the equation e(_Vi ,P)=e(_QIDi ,_Ppub )e(_hi ·up_kIDi ,W)e(_kiUi ,T) .

(b) Otherwise (_IDi ...0;_IDI ), ...9E; looks up lists _LH1 and _LU and for tuples Y9;_IDi ,_aIDi ,_QIDi YA; and Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; separately, where _QIDi =_aIDi P and up_kIDi may have been replaced by (...9C;1) . ...9E; makes _H2 query and _H3 query with params and gets tuples Y9;params,_bi ,WYA; and Y9;params,_ci ,TYA; , where W=_bi P and T=_ci X . ...9E; generates a random number _ri ∈^Zq* and computes _Ui =_ri P , _hi =_H4 (_mi ,_IDi ,up_kIDi ,_Ui ) , _ki =_H5 (_mi ,_IDi ,up_kIDi ,_Ui ) , and _Vi =ps_kIDi +_hi ·_bi ·up_kIDi +_ki ·_ri ·T . At last, ...9E; returns (_Ui ,_Vi ) to ...9C;1 . It is easy to say (_Ui ,_Vi ) satisfies the equation e(_Vi ,P)=e(_QIDi ,_Ppub )e(_hi ·up_kIDi ,W)e(_kiUi ,T) .

Finally, ...9C;1 outputs a tuple (_IDi ,_mi ,_σi ) as its forgery, where _σi =(_Ui ,_Vi ) . If _IDi ...0;_IDI , ...9E; stops the simulation. From the forgery lemma [27], if we have a replay of ...9E; with the same random tape but different choice of _H4 and _H5 , ...9C;1 will output another three signatures. The following two equations hold since both of the two signatures are valid: [figure omitted; refer to PDF]

...9E; looks up lists _LH1 and _LU and for tuples Y9;_IDi ,_aIDi ,_QIDi YA; and Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; separately, where _QIDi =_aIDi P and up_kIDi may have been replaced by ...9C;1 . ...9E; makes _H2 query and _H3 query with params and gets tuples Y9;params,_bi ,WYA; and Y9;params,_ci ,TYA; , where W=_bi P and T=_ci X . At last, ...9E; returns (_ki (^{Vi[variant prime]} -_bi ·^{hi[variant prime]} ·up_kIDi )-^{ki[variant prime]} (_Vi -_bi ·_hi ·up_kIDi ))/_aIDi (_ki -^{ki[variant prime]} ) as the solution of CDH problem.

Analysis . We show that ...9E; solves the given instance of the CDH problem with the probability η . To do so, we analyze the three events that result in ...9E; 's success.

: _E1 : ...9E; does not abort in all the queries of RevealPartialKey .

: _E2 : ...9C;1 can forge a legal signature _σi =(_Ui ,_Vi ) .

: _E3 : the outputted tuple (_IDi ,_mi ,_σi ) satisfies _IDi =_IDI .

From the simulation we know that ^{Pr[_E1 ]...5;(1-(1/_qH1 ))_qRPK} , Pr[_E2 |"_E1 ]...5;[straight epsilon] , Pr[_E3 |"_E1 ⋀_E2 ]...5;(1/_qH1 ) , where _qH1 and _qRPK denote the numbers of _H1 queries and RevealPartialKey queries separately. Then, the probability that ...9E; solves the CDH problem is [figure omitted; refer to PDF]

Then ...9E; could solve the CDH problem with a nonnegligible probability since [straight epsilon] 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 ...9C;2 wins Game 1 with nonnegligible probability [straight epsilon] . Then we could construct an algorithm ...9E; 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 ...9E; to compute xyP , where x,y∈^Zq* and they are unknown to ...9E; . At first, ...9E; 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 ...9C;2 . Then ...9E; answers ...9C;2 's query as follows.

(i) _H1 query : ...9E; maintains a list _LH1 of form Y9;_IDi ,_aIDi ,_QIDi YA; . When ...9C;1 makes this query on _IDi , ...9E; does as follows.

(a) If the list _LH1 contains a tuple Y9;_IDi ,_aIDi ,_QIDi YA; , ...9E; returns _QIDi to ...9C;2 .

(b) Otherwise, ...9E; picks a random _aIDi ∈^Zn* , computes _QIDi =_aIDi P , adds Y9;_IDi ,_aIDi ,_QIDi YA; to _LH1 , and returns _QIDi to ...9C;2 .

(ii) _H2 query: ...9E; maintains a list _LH2 of form Y9;_mi ,_bi ,_Wi YA; . When ...9C;2 makes this query on _mi , ...9E; does as follows.

(a) If the list _LH2 contains a tuple Y9;_mi ,_bi ,_Wi YA; , ...9E; returns _Wi to ...9C;2 .

(b) Otherwise, ...9E; picks a random _bi ∈^Zn* , computes _Wi =_bi X , adds Y9;_mi ,_bi ,_Wi YA; to _LH2 , and returns _Wi to ...9C;2 .

(iii): _H3 query : ...9E; maintains a list _LH3 of form Y9;_mi ,_ci ,_Ti YA; . When ...9C;2 makes this query on _mi , ...9E; does as follows.

(a) If the list _LH3 contains a tuple Y9;_mi ,_ci ,_Ti YA; , ...9E; returns _Ti to ...9C;2 .

(b) Otherwise, ...9E; picks a random _ci ∈^Zn* , computes _Ti =_ci X , adds Y9;_mi ,_ci ,_Ti YA; to _LH3 , and returns _Ti to ...9C;2 .

(iv) _H4 query : ...9E; maintains a list _LH4 of form Y9;_mi ,_IDi ,up_kIDi ,_Ui ,_hi YA; . When ...9C;2 makes this query on (_mi ,_IDi ,up_kIDi ,_Ui ) , ...9E; does as follows.

(a) If the list _LH4 contains a tuple Y9;_mi ,_IDi ,up_kIDi ,_Ui ,_hi YA; , ...9E; returns _hi to ...9C;2 .

(b) Otherwise, ...9E; picks a random _hi ∈^Zn* , returns _hi to ...9C;2 , and adds Y9;_mi ,_IDi ,up_kIDi ,_Ui ,_hi YA; to _LH4 .

(v) _H5 query : ...9E; maintains a list _LH5 of form Y9;_mi ,_IDi ,up_kIDi ,_Ui ,_ki YA; . When ...9C;2 makes this query on (_mi ,_IDi ,up_kIDi ,_Ui ) , ...9E; does as follows.

(a) If the list _LH5 contains a tuple Y9;_mi ,_IDi ,up_kIDi ,_Ui ,_ki YA; , ...9E; returns _ki to ...9C;2 .

(b) Otherwise, ...9E; picks a random _ki ∈^Zn* , returns _ki to ...9C;2 , and adds Y9;_mi ,_IDi ,up_kIDi ,_Ui ,_hi YA; to _LH5 .

(vi) CreateUser : ...9E; maintains a list _LU of form Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; . When ...9C;2 makes this query on _IDi , ...9E; does as follows.

(a) If the list _LU contains a tuple Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; , ...9E; returns up_kIDi to ...9C;2 .

(b) Otherwise, if _IDi =_IDI , ...9E; gets _QIDI =_aIDI P by making _H1 query with _IDI and computes ps_kIDI =s_QIDI . ...9E; sets us_kIDi [arrow left][perpendicular] and up_kIDi [arrow left]Y . At last, ...9E; adds Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; to _LU and returns up_kIDi to ...9C;2 .

(c) Otherwise (_IDi ...0;_IDI ), ...9E; gets _QIDi =_aIDi ·P by making _H1 query with _IDi and computes ps_kIDI =s_QIDI . ...9E; selects a random number _xIDi ∈^Zq* as his secret key us_kIDi and computes his public key as up_kIDi =us_kIDi ·P . At last, ...9E; adds Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; to _LU and returns up_kIDi to ...9C;1 .

(vii): RevealPartialKey : when ...9C;2 makes this query on _IDi , ...9E; looks up the list _LU for the tuple Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; and returns ps_kIDi to ...9C;2 .

(viii): RevealSecertKey: when ...9C;2 makes this query on _IDi , ...9E; does as follows.

(a) If _IDi =_IDI , ...9E; stops the simulation.

(b) Otherwise (_IDi ...0;_IDI ), ...9E; looks up the list _LU for the tuple Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; and returns us_kIDi to ...9C;2 .

(ix) Sign : when ...9C;1 makes this query on (_mi ,_IDi ) , ...9E; does as follows.

(a) If _IDi =_IDI , ...9E; looks up lists _LH1 and _LU and for tuples Y9;_IDi ,_aIDi ,_QIDi YA; and Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; separately, where _QIDi =_aIDi P and up_kIDi may have been replaced by ...9C;2 . ...9E; makes _H2 query and _H3 query with params and gets tuples Y9;params,_bi ,WYA; and Y9;params,_ci ,TYA; , where W=_bi X and T=_ci X . ...9E; generates three random numbers _hi ,_ki ,_ri ∈^Zq* , computes _Ui =^ki-1 (_ri ·P-_bi ·^ci-1 ·_hi ·Y) , _Vi =_ri ·T+_aIDi ·s·up_kIDi , and sets _H4 (_mi ,_IDi ,up_kIDi ,_Ui )[arrow left]_hi , _H5 (_mi ,_IDi ,up_kIDi ,_Ui )[arrow left]_ki . At last, ...9E; adds tuples Y9;_mi ,_IDi ,up_kIDi ,_Ui ,_hi YA; and Y9;_mi ,_IDi ,up_kIDi ,_Ui ,_ki YA; to _LH4 and _LH5 separately and returns (_Ui ,_Vi ) to ...9C;2 . It is easy to say (_Ui ,_Vi ) satisfies the equation e(_Vi ,P)=e(_QIDi ,_Ppub )e(_hi ·up_kIDi ,W)e(_kiUi ,T) .

(b) Otherwise (_IDi ...0;_IDI ), ...9E; acts according to the description of the algorithm Sign since he knows both of us_kIDi and ps_kIDi .

Finally, ...9C;2 outputs a tuple (_IDi ,_mi ,_σi ) as its forgery, where _σi =(_Ui ,_Vi ) . If _IDi ...0;_IDI , ...9E; stops the simulation. From the forgery lemma [27], if we have a replay of ...9E; with the same random tape but different choice of _H4 and _H5 , ...9C;2 will output another signatures. The following two equations hold since both of the two signatures are valid: [figure omitted; refer to PDF]

...9E; looks up lists _LH1 and _LU and for tuples Y9;_IDi ,_aIDi ,_QIDi YA; and Y9;_IDi ,ps_kIDi ,_QIDi ,us_kIDi ,up_kIDi YA; separately, where _QIDi =_aIDi P . ...9E; makes _H2 query and _H3 query with params and gets tuples Y9;params,_bi ,WYA; and Y9;params,_ci ,TYA; , where W=_bi X and T=_ci X . At last, ...9E; returns (_ki (^{Vi[variant prime]} -s·_QIDi )-^{ki[variant prime]} (_Vi -s·_QIDi ))/_bi (^{hi[variant prime]}_ki -_hi^{ki[variant prime]} ) as the solution of CDH problem.

Analysis . We show that ...9E; solves the given instance of the CDH problem with the probability η . To do so, we analyze the three events that result in ...9E; 's success.

: _E1 : ...9E; does not abort in all the queries of RevealSecertKey .

: _E2 : ...9C;1 can forge a legal signature _σi =(_Ui ,_Vi ) .

: _E3 : the outputted tuple (_IDi ,_mi ,_σi ) satisfies _IDi =_IDI .

From the simulation we know that Pr[_E1 ]...5;(1-(1/_qH1 )^)_qRSK , Pr[_E2 |"_E1 ]...5;[straight epsilon] , Pr[_E3 |"_E1 ⋀_E2 ]...5;(1/_qH1 ) , where _qH1 and _qRSK denote the numbers of _H1 queries and RevealSecertKey queries separately. Then, the probability that ...9E; solves the CDH problem is [figure omitted; refer to PDF]

Then ...9E; could solve the CDH problem with a nonnegligible probability since [straight epsilon] 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 in _G1 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 in _G1 is intractable.

Proof.

Suppose there is an adversary ...9C;∈{...9C;1,...9C;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 Table 1. 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.

Conflict of Interests

The authors declare that they have no conflict of interests.

References

[1] D. Boneh, C. Gentry, B. Lynn, H. Shacham, "Aggregate and verifiably encrypted signatures from bilinear maps," in Proceedings of the Eurocrypt '03, vol. 3027, of Lecture Notes in Computer Science, pp. 416-432, 2003.

[2] S. Kent, C. Lynn, K. Seo, "Secure Border Gateway Protocol (S-BGP)," IEEE Journal on Selected Areas in Communications , vol. 18, no. 4, pp. 582-592, 2000.

[3] US Department of Transportation, "National Highway Traffic Safety Administration, vehicle safety communications project," Final Report , US Department of Transportation, Washington DC, USA, 2006.

[4] A. Shamir, "Identity-based cryptosystems and signature schemes," in Proceedings of the CRYPTO '84, vol. 196, of Lecture Notes in Computer Science, pp. 47-53, Springer, Berlin, Germany, 1985.

[5] S. Al-Riyami, K. Paterson, "Certificateless public key cryptography," in Proceedings of the 9th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT '03), vol. 2894, of Lecture Notes in Computer Science, pp. 452-473, Springer, Berlin, Germany, 2003.

[6] J. Baek, R. Safavi-Naini, W. Susilo, "Certificateless public key encryption without pairing," in Proceedings of the Industrial Simulation Conference (ISC '05), vol. 3650, of Lecture Notes in Computer Science, pp. 134-148, Springer, Berlin, Germany, 2005.

[7] Y. Sun, F. Zhang, J. Baek, "Strongly secure certificateless public key encryption without pairing," in Proceedings of the Cryptology and Network Security (CANS '07), vol. 4856, of Lecture Notes in Computer Science, pp. 194-208, Springer, Berlin, Germany, 2007.

[8] J. Lai, W. Kou, K. Chen, "Self-generated-certificate public key encryption without pairing and its application," Information Sciences , vol. 181, no. 11, pp. 2422-2435, 2011.

[9] D. He, Y. Chen, J. Chen, R. Zhang, W. Han, "A new two-round certificateless authenticated key agreement protocol without bilinear pairings," Mathematical and Computer Modelling , vol. 54, no. 11-12, pp. 3143-3152, 2011.

[10] D. He, J. Chen, J. Hu, "A pairing-free certificateless authenticated key agreement protocol," International Journal of Communication Systems , vol. 25, no. 2, pp. 221-230, 2012.

[11] D. He, S. Padhye, J. Chen, "An efficient certificateless two-party authenticated key agreement protocol," Computers and Mathematics with Applications , vol. 64, no. 6, pp. 1914-1926, 2012.

[12] C. Zhou, W. Zhou, X. Dong, "Provable certificateless generalized signcryption scheme," Designs, Codes and Cryptography , 2012.

[13] W. Liu, C. Xu, "Certificateless signcryption scheme without bilinear pairing," Ruan Jian Xue Bao/Journal of Software , vol. 22, no. 8, pp. 1918-1926, 2011.

[14] D. He, J. Chen, J. Hu, "A pairing-free certificateless authenticated key agreement protocol," International Journal of Communication Systems , vol. 25, no. 2, pp. 221-230, 2012.

[15] D. He, Y. Chen, J. Chen, "An efficient secure certificateless proxy signature scheme without pairings," Mathematical and Computer Modelling , vol. 57, no. 9-10, pp. 2510-2518, 2013.

[16] D. He, B. Huang, J. Chen, "New certificateless short signature scheme," IET Information Security , vol. 7, no. 2, pp. 113-117, 2013.

[17] R. Castro, R. Dahab, "Efficient Certificateless Signatures Suitable for Aggregation," Cryptology ePrint Archive, http://eprint.iacr.org/2007/454

[18] G. Zheng, L. Yu, H. Xuan, C. Kefei, "Two certificateless aggregate signatures from bilinear maps," in Proceedings of the 8th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (SNPD '07), vol. 3, pp. 188-193, August 2007.

[19] Z. Gong, Y. Long, X. Hong, K. Chen, "Practical certificateless aggregate signatures from bilinear maps," Journal of Information Science and Engineering , vol. 26, no. 6, pp. 2093-2106, 2010.

[20] L. Zhang, F. Zhang, "A new certificateless aggregate signature scheme," Computer Communications , vol. 32, no. 6, pp. 1079-1085, 2009.

[21] X. Hu, Q. Wu, Z. Chen, "Strong security enabled certificateless aggregate signatures applicable to mobile computation," in Proceedings of the 3rd IEEE International Conference on Intelligent Networking and CollaborativeSystems (INCoS '11), pp. 92-99, IEEE Computer Society, Washington, DC, USA, December 2011.

[22] L. Zhang, B. Qin, Q. Wu, F. Zhang, "Efficient many-to-one authentication with certificateless aggregate signatures," Computer Networks , vol. 54, no. 14, pp. 2482-2491, 2010.

[23] N. Yanai, R. Tso, M. Mambo, E. Okamoto, "A certificateless ordered sequential aggregate signature scheme secure against super adversaries," Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications , vol. 3, no. 1-2, pp. 30-54, 2012.

[24] K. Shim, "On the security of a certificateless aggregate signature scheme," IEEE Communications Letters , vol. 15, no. 10, pp. 1136-1138, 2011.

[25] H. Xiong, Z. Guan, Z. Chen, F. Li, "An Efficient certificateless aggregate signature with constant pairing computations," Information Science , vol. 219, no. 10, pp. 225-235, 2013.

[26] D. He, M. Tian, J. Chen, "Insecurity of an efficient certificateless aggregate signature with constant pairing computations," Information Sciences , 2013.

[27] P. David, S. Jacque, "Security arguments for digital signatures and blind signatures," Journal of Cryptology , vol. 13, no. 3, pp. 361-396, 2000.