INFORMATICA Informatica 1822-88440868-49520868-4952 Vilnius University INFO1143 10.15388/Informatica.2017.127 Research Article Generic Construction of Certificate-Based Signature from Certificateless Signature with Provable Security GaoWeimygaowei@163.com12∗

W. Gao received his PhD and MS degrees in applied mathematics from Hunan University in 2006, Guangzhou University 2003, respectively. He is an associate professor in Ludong University from 2012.

 WangGuilinwang.guilin@huawei.com3

G. Wang received his PhD degree in computer science, from Institute of Software, Chinese Academy of Sciences, PR China, in 2001. He was a senior lecturer in University of Wollongong, Australia. Now he works in Huawei Technologies Co. Ltd., Singapore. His research interests include cryptography and information security.

 ChenKefeikfchen@hznu.edu.cn4

K. Chen is a professor of cryptography and information security school of science, Hangzhou Normal University since 2013. From 1996 to 2013, he was a professor of cryptography and information security in the School of Science, Shanghai Jiaotong University. His interest fields are public key cryptography, cryptographic protocol analysis, applied cryptographic techniques and computer security.

 WangXueliwangxuyuyan@gmail.com5

X. Wang received his PhD degree in mathematics from the Academy of China in 1991, his MS degree in mathematics from Shannxi Normal University in 1987. He is currently a professor of Computer Science at South China Normal University. His current research interests include cryptography, number theory.

 School of Mathematics and Statistics, Ludong University, Yantai 264025, China Nanjing University of Information Science & Technology, Nanjing 210044, China Huawei Technologies Co. Ltd., Singapore Department of Mathematics, Hangzhou Normal University, Hangzhou 311121, China School of Mathematics, South China Normal University, Guangzhou 510631, China Corresponding author. 201711201728221523572015112016 © 2017 Vilnius University2017 Open access article under the CC BY license.

This paper studies the generic construction of certificate-based signature (CBS) from certificateless signature (CLS). This paper proposes a new generic conversion from CLS to CBS which is more intuitive, simpler, and provably secure without random oracles than the current one. To develop the security proof, we put forth one novel CLS security model which features a previously neglected but nontrivial attack and hence captures the CLS security notion more comprehensively. We show that many existing CLS schemes can be proved secure in the current model by slightly modifying its original security proof. Following this conversion, many provably secure CBS schemes can be constructed from the corresponding existing CLS schemes.

 certificateless signature certificate-based signature identity based signature provable security Introduction

Identity-based Cryptography (IBC). In 1984, Shamir (1984) proposed the concept of identity-based PKC (IBC) for reducing the requirements on the public key infrastructure. In IBC, the public key for one entity is its well-known identity information, such as the email address and the full name. The private key for this entity is generated by one trusted party called Private Key Generater (PKG), usually being the signature on the identity information. With this approach, the certification of public keys becomes implicit. However, IBC suffers from the main drawback of being inherently key escrowed, since PKG can generate the private key of any entity.

Certificate-based Cryptography (CBC). Motivated by avoiding the problem of third party queries in PKC, Gentry proposed the new concept of certificate-based encryption (CBE) by combining public key encryption and identity based encryption. Following the idea of CBE, Kang et al. (2004) proposed the concept of certificate based-signature (CBS). This certificate has all of the functionality of a conventional PKI certificate – e.g. it can be used explicitly as proof of current certification – but it can also be used as part of the user decryption/signing key, which is composed of the user-generated private key and the certificate. As a result, CBC achieves two main advantages. On the one hand, unlike IBC, there is no key escrow for CBC, since CA does not know the user-generated private key. On the other hand, the encrypter (or signature verifier) does not need to verify the certificate, because the ciphertext (or signature) can not be decrypted (or generated) unless the certificate exists. This allows CBC to eliminate third party queries on certificate status (Gentry, 2003). By refining basic CBE/CBS through the use of subset covers, an exceptionally efficient PKI can be constructed (Gentry, 2003).

Certificateless cryptography (CLC). Similarly motivated by combining merits of the traditional PKC and IBC, independently from the work of CBC, the concept of certificateless encryption (CLE) and certificateless signature (CLS) were introduced by Al-Riyami and Paterson (2003). In CLC, each entity has two secrets: a secret value SV chosen by the entity and a partial private key PPK generated by a third party called Private Key Generater (PKG). The full private key is the output of a function by taking SV and PPK as the input, and hence can be only known by the user. On the one hand, unlike IBC, CLC does not suffer from key escrow, since PKG does not have access to the user’s secret value SV. CLC does not require the use of certificates to guarantee the authenticity of public key. The two concepts of CBC and CLC are similar. The main difference is the generation of the partial secret key in CLC (it is called certificate in CBC). In CLC the PKG does not require the user’s public key for the generation of the partial secret key, while in CBC the CA does require the user’s public key for the generation of the certificate. Additionally, the trust level of CBC is 3, while the trust level of CLC is 2 (Liu et al., 2007). All the above three kinds of public key cryptographic primitives have the considerable advantages in key managements which make them potentially suitable for many applications such as wireless networks (Guo et al., 2014; Xie and Wang, 2014; Shen et al., 2015) where key management will be additional burden for restricted resources.

Related Works

Although CBC and CLC were developed independently, both of them can be conceptually seen as intermediates between traditional PKC and IBC, seeking to simplify the management of certificates while avoiding the key escrow problem in IBC. So a natural question to establish the connection of two concepts arose in the theoretical cryptography field. In 2005, Al-Riyami and Paterson (2005) presented one generic conversion from CLE to CBE and claimed the provable security of this generic construction of CBE. Shortly later, Kang and Park (2005) pointed out that this generic conversion from CLE to CBE has a critical flaw in the security proof. Recently, Wu et al. (2009) proposed a new generic conversion from CLS to CBS, and a generic conversion from CLE to CBE (Wu et al., 2012). These two generic conversions have to depend on the cryptographic hash function which is taken as a random oracle (Canetti et al., 2004) in the security proof. In addition to the generic results of CBS, there are also some concrete CBS schemes proposed in Kang et al. (2004), Liu et al. (2008, 2011), Wu et al. (2009, 2012), Li et al. (2010, 2012). In current research of cryptography, there are much more results for certificateless cryptography than certificate-based cryptography.

 Motivations

From the perspective of theoretical cryptography, it is very interesting to investigate the general relationship between certificate-based signatures and certificateless signatures. As mentioned in Wu et al. (2012), those two cryptographic primitives are quite closely related. In fact, four similarities in certificateless signatures and certificate-based signatures are presented in Wu et al. (2012). However, the state-of-the-art result in Wu et al. (2012) is not satisfactory enough in the viewpoint of theory, since the undesirable primitive “random oracle” (Bellare and Rogaway, 1993) is needed in this framework: “CLS + Random Oracle → CBS” . In the field of provable secure cryptography, researchers usually try to construct cryptographic schemes in the standard model instead of the random oracle model. In contrast, it is a natural and intuitive task in theory to wipe out “Random Oracle”, or to get the most concise framework: “CLS → CBS” .

From the perspective of cryptographic practice, it is also worthwhile to study this most concise framework. In fact, there are much more research works on CLS schemes than those in CBS schemes. Hence, the study on generic construction of CBS from CLS can help us to obtain many concrete CBS schemes from existing CLS schemes with almost no price. Among those constructed in this way, some CBS schemes may have better properties than existing ones.

 Contributions

A new security model for CLS is developed. It captures some new attacks which have never been mentioned in literature. For more details, please refer to Section 2 where two remarks aim to explain its originality. From the viewpoint of basic theory, this further development of security model is an essential refinement for certificateless cryptography theory. From the viewpoint of applications, it is the key technique helping us to prove secure our generic conversion of CBS schemes from CLS schemes.

The most intuitive generic conversion of CLS schemes from CBS schemes is “revived”. Compared with the Wu et al.’s (2009) generic conversion from CLS to CBS, our generic conversion is as intuitive as possible, and as concise as possible. Although it is so intuitive, concise and reasonable, this conversion framework can not be adopted by previous works in cryptography, until the formal security proof is completed in this paper. In terms of cryptographic theory, we provide the formal security proof for the intuitive observation on close relation between CLS signatures and CBS signatures.

Many concrete CBS schemes can be constructed from existing CLS schemes by applying the generic framework. One existing CLS scheme is proved secure in our new security model. With this proof as an example, we also listed other CLS schemes which also can be proved secure in the new security model. Hence, many CBS signature schemes can be constructed.

 Organization

This paper is organized as follows. Section 2 reviews the syntax definition of CLS and proposes the new security model for CLS. Section 3 briefly reviews the definition and security model for CBS in one more concise framework. Section 4 presents our new generic construction of CBS from CLS and its security proof. Section 5 compares our result with the state-of-the-art one proposed in Wu et al. (2012). Section 6 presents a concrete CBS signature scheme as an application example of our generic conversion. Some other CLS schemes which can be similarly proved secure are listed. At last, Section 7 draws the conclusion.

 Certificateless Signature

We use the notation ID and ID to denote the identity information in the certificateless system and certificate-based system respectively. We put the prefix CL . to specify that this is in the certificateless system and CB to specify that this is in the certificate-based system. We use the notation query ↛ O to denote that the query query has never been submitted to the oracle O, and the notation answer ← O to denote that the answer answer has been returned by the oracle O.

A certificateless signature scheme consists of the following six algorithms.

CL.Setup( 1 k ) → ( CL . msk , CL . param ). It takes 1 k as input where k is the security parameter, and returns the master private key CL . msk and the parameter CL . param which is shared in the system.

CL.ExtractPPK ( CL . msk , CL . param , ID ) → D ID . It takes the master private key CL . msk, the system parameter CL . param and the identity ID as input, and returns the partial private key D ID .

CL.SetSV ( CL . param ) → X ID . It takes as input the system parameter CL . param, and outputs a secret value X ID .

CL.SetPK( CL . param , X ID ) → ( CL . PK ID ). It takes as input the system parameter CL . param, and this identity’s secret value X ID , and outputs the public key CL . PK ID .

CL.Sign ( CL . param , D ID , X ID , m ) → CL . σ. It takes as input the system parameter CL . param, the partial private key D ID , the secret value X ID and the message m, and outputs the signature CL . σ.

CL.Verify ( CL . param , ID , CL . PK ID , m , CL . σ ) → b ∈ { 0 , 1 }. It takes as input the system parameter CL . param, an identity ID, this identity’s public key CL . PK ID and a message/signature pair ( m , CL . σ ), and outputs 1 if the signature is correct, or 0 otherwise.

The following definition has some essentially different points from other ones including that in Huang et al. (2011). Two remarks on these basic differences will be presented during the definition. To get more succinct security definition than others, we put four kinds of adversary models together in one unified framework. Additionally, in Section 6, we will show that many existing CLS signature schemes can be proved secure in our new security model and present 6 examples.

A CLS scheme is CL-EUF-CMCI secure against a certain kind of adversary A ∈ { CL.Normal- A I , CL.Super- A I , CL.Normal- A II , CL.Super- A II } , if no polynomially bounded adversary A has a non-negligible success probability in the following CLS game. In the following, CL.Normal- A I , CL.Super- A I , CL.Normal- A II , CL.Super- A II will be called normal Type I adversary, super Type I adversary, normal Type II adversary, and super Type II adversary respectively.

(1) Initial: the challenger runs the algorithm CL.Setup, returns CL . Params and the auxiliary information aux ∈ { nil , CL . msk } to the attacker A ( nil means nothing), where aux = nil , for A ∈ { CL.Normal- A I , CL.Super- A I } , aux = CL . msk , for A ∈ { CL.Normal- A II , CL.Super- A II } .

(2) Queries: in this phase, A can adaptively make requests to a few oracles among the following ones.

O CL . CreateU ( ID ) → CL . PK ID . This oracle receives an input ID and outputs this original public key of the identity ID.

O CL . ReplacePK ( ID , CL . PK ) → ∅. For a public key replacement query ( ID , CL . PK ), it sets CL . PK as the current public key.

O CL . SecretV ( CL . PK ) → X. If CL . PK is the original public key of a ceratin identity ID (i.e. CL . PK has been returned from the oracle O CL . CreateU ), this oracle returns the secret value X corresponding to CL . PK. Otherwise, it refuses this query.

O CL . PartialPK ( ID , CL . PK ) → D ID . For a partial private key query ID, this oracle runs the algorithm CL.ExtractPPK and outputs the result D ID .

O CL . NSign ( ID , m ) → CL . σ. If CL . PK ‾ ID ← O CL . CreateU , which means that the current public key CL . PK ‾ ID has been provided by the oracle O CL . CreateU , it outputs a valid signature CL . σ of m under the current public key CL . PK ‾ ID of the identity ID. Otherwise, it refuses the query.

Originally, “normal” is used to mean that one signing query is normal (or reasonable) for the challenger which knows both the current secret value and partial private key for this query. To make one signing oracle query “normal”, all previous definition models require that the current public key be the original one of the current identity. However, this requirement is only sufficient for that the challenger knows the current secret value, but not necessary. In fact, the sufficient and necessary condition for “normal” signing queries should be that the current public key has been generated by the challenger, or formally the oracle O CL . CreateU . For example, the adversary gets Alice’s public key p k A and Bob’s public key p k B from the oracle O CL . CreateU , then requires Alice’s public key to take the value of p k B through the oracle O CL . ReplacePK , and finally queries the signature corresponding to Alice’s identity and the replaced (not original) public key. In this example, although Alice’s public key has been replaced, the challenger still knows the current secret value and hence this signing query should be called “normal”. In fact, our definition for “normal” captures this example, while previous security models leave it out.

O CL . SSign ( ID , m ) → CL . σ. For a super signing query ( ID , m ), it outputs a valid signature CL . σ of m under the current public key CL . PK ‾ ID of the identity ID.

Every attack model A has its own set O A of allowed oracles. In particular, with O ′ = { O CL . CreateUser , O CL . ReplacePK , O CL . SecretV } being commonly allowed, O A = O ′ ∪ { O CL . NSign , O CL . PartialPK } , for A = CL.Normal- A I , O A = O ′ ∪ { O CL . SSign , O CL . PartialPK } , for A = CL.Super- A I , O A = O ′ ∪ { O CL . NSign } , for A = CL.Normal- A II , O A = O ′ ∪ { O CL . SSign } , for A = CL.Super- A II . (3) Output: After all queries, A outputs a forgery ( ID ∗ , m ∗ , CL . σ ∗ ). Let CL . PK ‾ ID ∗ be the current public key of ID ∗ . A is said to win the game if the forgery satisfies the following restrictions to ensure that the successful forgery is nontrivial. It is well-known that the basic security requirement for CLS is that both the secret value and the partial private key are the two indispensable factors for generating a CLS signature. In other words, any forgery generated by the attacker who knows at most one of these two indispensable factors should be accepted as successful.

(i) For A ∈ { CL.Normal- A I , CL.Super- A I , CL.Normal- A II , CL.Super- A II }, it is commonly required that 1 = CL . Verify ( CL . mpk , CL.param , ID ∗ , CL . PK ‾ ID ∗ , m ∗ , CL . σ ∗ ) , and ( ID ∗ , m ∗ ) ↛ O CL . Sign , where O CL . Sign = O CL . NSign , for A ∈ { CL.Normal- A I , CL.Normal- A II } , O CL . Sign = O CL . SSign , for A ∈ { CL.Super- A I , CL.Super- A II } . Here, we use the notation ↛ to denote that the query ( ID ∗ , m ∗ ) has never been provided to the oracle O Sign . This restriction ensures that the signature is valid and not trivially obtained from the signing oracle.

(ii) For A ∈ { CL.Normal- A I , CL.Super- A I }, additionally, it is required that ID ∗ ↛ O CL . PartialPK . This restriction ensures that the target partial private key is not known by A.

(iii) For A ∈ { CL.Normal- A II , CL.Super- A II }, additionally, it is required that CL . PK ‾ ID ∗ ↛ O CL . SecretV , and CL . PK ‾ ID ∗ ← O CL . CreateU , where CL . PK ‾ ID ∗ ← O CL . CreateU means that CL . PK ‾ ID ∗ is provided by the oracle O CL . CreateU .

Fundamentally speaking, the original purpose for this restriction is to ensure that the target secret value is not trivially known by Type II adversary. For this purpose, the type II adversary is prohibited from generating the target public key by himself. In fact, previous security definitions require that the target public key must be the original one for the target identity, while our definition only requires that the current public key must come from the challenger, or formally the oracle O CL . CreateU . For example, the adversary gets Alice’s public key p k A and Bob’s public key p k B from the oracle O CL . CreateU , then requires Alice’s public key to take the value of p k B through the oracle O CL . ReplacePK , and finally forges the signature corresponding to Alice’s identity and her replaced (not original) public key. In this case, although Alice’s public key has been replaced, the adversary still does not know the current secret value and hence this signing forgery should be seen as successful. In fact, our definition formally captures this example, while previous security models leave it out. In fact, this remark for “successful” forgery is somewhat like that for “normal” signing query.

 Certificate-Based Signature

A Certificate-Based Signature Scheme (CBS) consists of five algorithms as follows.

CB . Setup ( 1 k ) → ( CB . msk , CB . param ). It takes as input the security parameter  1 k and returns the certifier’s master secret key CB . msk and the system parameter CB . param that includes the description of a string space Γ, which can be any subset of { 0 , 1 } ∗ .

CB . GenUK ( CB . param ) → ( CB . PK ID , CB . SK ID ). It takes input the system parameter CB . param, and outputs the secet/public key pair ( SK ID , PK ID ) for a certain entity ID.

CB . Cert ( CB . msk , CB . param , ID , CB . PK ID ) → cert ID . It takes as input the master secret key CB . msk, the system parameter CB . param, the identity ID and its public key CB . PK ID , and outputs the certificate cert ID .

CB . Sign ( CB . param , ID , CB . PK ID , cert ID , CB . SK ID , m ) → CB . σ. It takes as input the system parameter CB . param, the identity ID, the public key CB . PK, the certificate cert ID , the secret key CB . SK ID and the message m, and outputs the signature CB . σ.

CB . Verify ( CB . param , ID , CB . PK ID , m , CB . σ ) → b ∈ { 0 , 1 }. It takes as input the system parameter CB . param, an identity ID, this identity’s public key CB . PK ID and a message/signature pair ( m , CB . σ ), and outputs 1 if the signature is correct, or 0 otherwise.

A CBS scheme is CB-EUF-CMCI secure against a certain kind of adversary A ∈ { CB.Normal- A I , CB.Super- A I , CB.Normal- A II , CB.Super- A II } , if no polynomially bounded adversary A has a non-negligible success probability in the following CBS game. In this definition, CB.Normal- A I , CB.Super- A I , CB.Normal- A II , CB.Super- A II will be called normal Type I adversary, super Type I adversary, normal Type II adversary, and super Type II adversary respectively.

(1) Initial: the challenger runs the algorithm CB.Setup, returns CB . Params and the auxiliary information aux ∈ { nil , CB . msk } to the attack A ( nil means nothing), where aux = nil , for A ∈ { CB.Normal- A I , CB.Super- A I } , aux = CB . msk , for A ∈ { CB.Normal- A II , CB.Super- A II } .

(2) Queries: in this phase, A can adaptively make requests to a few oracles among the following ones.

O CB . CreateU ( ID ) → CB . PK ID . This oracle receives an input ID and outputs this original public key of the identity ID.

O CB . ReplacePK ( ID , CB . PK ) → ∅. For a public key replacement query ( ID , CB . PK ), it sets CB . PK as the current public key of ID.

O CB . Corrupt ( ID ) → CB . SK ID . If ID has been submitted to the oracle O CB . CreateU , this oracle returns the secret key CB . SK ID corresponding to ID’s original public key. Otherwise, it first makes the oracle query O CB . CreateU ( ID ) and then the oracle query O CB . Corrupt ( ID ).

O CB . Cert ( ID , CB . PK ) → cert ID . For this certification query, this oracle gets the result cert ID by running the algorithm CB.Cert and outputs it.

O CB . NSign ( ID , m ) → CB . σ. If ID has been submitted to O CB . CreateU , it outputs a valid signature CB . σ of m under the original public key CB . PK ID of the identity  ID. Otherwise, it refuses the query.

O CB . SSign ( ID , m ) → CB . σ. For a super signing query ( ID , m ), it outputs a valid signature CB . σ of m under the current public key CB . PK ‾ ID of the identity ID.

Every attack model A has its own set O A of allowed oracles. In particular, with O ′ = { O CB . CreateUser , O CB . ReplacePK , O CB . Corrupt } being commonly allowed, O A = O ′ ∪ { O CB . NSign , O CB . Cert } , for A = CB.Normal- A I , O A = O ′ ∪ { O CB . SSign , O CB . Cert } , for A = CB.Super- A I , O A = O ′ ∪ { O CB . NSign } , for A = CB.Normal- A II , O A = O ′ ∪ { O CB . SSign } , for A = CB.Super- A II .

(3) Output: after all queries, A outputs a forgery ( ID ∗ , m ∗ , CB . σ ∗ ). Let CB . PK ‾ ID ∗ be the current public key of ID ∗ . A is said to win the game if this forgery satisfies the following requirements.

For A ∈ { CB.Normal- A I , CB.Super- A I , CB.Normal- A II , CB.Super- A II }, it is commonly required that 1 = CB . Verify ( CB . mpk , CB . param , ID ∗ , CB . PK ‾ ID ∗ , m ∗ , CB . σ ∗ ) , and ( ID ∗ , m ∗ ) ↛ O Sign , where O C B.Sign = O CB . NSign , for A ∈ { CB.Normal- A I , CB.Normal- A II } , O C B.Sign = O CB . SSign , for A ∈ { CB.Super- A I , CB.Super- A II } .

For A ∈ { CB.Normal- A I , CB.Super- A I }, additionally, it is required that ID ∗ ↛ O CB . Cert .

For A ∈ { CB.Normal- A II , CB.Super- A II }, additionally, it is required that ID ∗ ↛ O CB . Corrupt , and CB . PK ‾ ID ∗ = O CB . CreateU ( ID ∗ ) .

Generic Construction CLS-2-CBS and Security Proof

Let Π CL be a CLS scheme Π CL = ( CL . Setup , CL . SetSV , CL . SetPK , CL . ExtractPPK , CL . Sign , CL . Verify ) , with algorithms as specified in Definition 1. Then a CBS scheme Π CL = ( CB . Setup , CB . GenUK , CB . Cert , CB . Sign , CB . Verify ) is defined as follows. Let Γ be the identity information space for Π CB , PKCB be the public key space for Π CB and IDCL denotes the space of identities for Π CL . Without loss of generality, we assume that IDCL = Γ × PKCB.

(1) CB.Setup. On input a security parameter 1 k , first run ( CL . msk , CL . param ) ← CL . Setup ( 1 k ) . Then set CB . msk = CL . msk. Define CB . param by extending CL . param to include some other relative information. The output is ( CB . msk , CB . param ).

(2) CB.GenUK. On input CB . param, first extract CL . param from CB . param. Run X ← CL . SetSV ( CL . param ) , CL . PK ← CL . Set PK ( CL . param , X ) . The output is ( CB . PK , CB . SK ) = ( CL . PK , X ).

(3) CB.Cert. On input CB . msk , CB . param , ID , CB . PK ID , first extract CL . param from CB . param. Set the ID = ID | | CB . PK ID and CL . msk = CB . msk. The output is cert ID ← CL . ExtractPPK ( CL . param , CL . msk , ID ) .

(4) CB.Sign. On input CB . param, cert ID , CB . SK ID , m, first extract CL . param from CB . param. Then set ID = ID | | CB . PK ID , CL . PK ID = CB . PK ID , D ID = cert ID , X ID = CB . SK ID . The output is CB . σ ← CL . Sign ( C L . p a r a m , ID , CL . PK ID , D ID , X ID , m ) .

(5) CB.Verify. On input CB . param , ID , CB . PK ID , m , CB . σ, extract CL . param from CB . param. Set ID = ID | | CB . PK ID , CL . PK ID = CB . PK ID and CL . σ = CB . σ. The output is b ← CL . Verify ( CL . param , ID , CL . PK ID , m , CL . σ ) .

The following four theorems deal with the four kinds of adversaries respectively. As will be seen, all these security reductions are perfectly tight and depend on no random oracles. These two reduction features show that both concepts of CBS and CLS are very closely related to each other.

Suppose that A I is a super Type I adversary against Π CB with success probability ϵ and running time t. Then there is a super Type I adversary B I against Π CL with success probability ϵ and running time O ( t ).

Let C denote the Π CL challenger against B I . B I mounts a Type I attack on Π CL by simulating the challenger for A I and using help from A I as follows.

Initial phase for CBS game. B I obtains from C the system parameter of Π CL and extends it into the system parameter CB . param of Π CB as done in CB . Setup of Π CB . B I supplies CB . param to A I .

Queries Phase for CBS game. When A I enters the Queries phase for the CBS game, B I accordingly enters the Queries phase of the CLS game. For the oracle queries from A I , B I handles these queries as follows.

(1) O CB . CreateU ( ID ) → CB . PK ID . If the query ID has been submitted to the oracle O CB . CreateU , it will directly return the previous answer which is recorded in the list L. Otherwise, it does as follows. B I chooses a random identity ID ′ and obtains its original public key CL . PK ˜ ID ′ through the oracle O CL . CreateU . It sets ID = ID | | CB . PK ID ′ and requires the oracle O CL . ReplacePK to change the public key of ID into CL . PK ˜ ID ′ . In this case, the CBS original public key of ID is the CLS original public key of ID ′ . In other words, every original public key for Π CB is related with a certain original public key for Π CL .

Additionally, to record the above operations for future use, B I sets the original public key CB . PK ˜ ID = CL . PK ˜ ID ′ and the current public key CB . PK ‾ ID = CL . PK ˜ ID ′ , and adds the tuple ( ID , ID ′ , CB . PK ˜ ID , CB . PK ‾ ID ) to the initially empty list L.

(2) O CB . ReplacePK ( ID , CB . PK ) → ∅. If ID has not been submitted to the oracle O CB . CreateU , B I first makes the query O CB . CreateU ( ID ) by himself before the following operations. Otherwise, it directly does the following. B I sets ID = ID | | CB . PK, and sequentially makes two oracle queries O CL . CreateU ( ID ) and O CL . ReplacePK ( ID , CB . PK ) to change the public key value of ID into CB . PK.

Additionally, to record the above operation, B I searches the relative tuple ( ID , ID ′ , CB . PK ˜ ID , CB . PK ‾ ID ) , and then changes the value of CB . PK ‾ ID into CB . PK.

(3) O CB . Corrupt ( ID ) → CB . SK ID . Without loss of generality, we assume that ID has been submitted to the oracle O CB . CreateU . B I searches the corresponding tuple ( ID , ID ′ , CB . PK ˜ ID , CB . PK ‾ ID ) in the list L. Then it makes the oracle query O CL . SecretV ( CB . PK ˜ ID ) and relays this answer to the attacker A I . Here note CB . PK ˜ ID = CL . PK ˜ ID ′ .

(4) O CB . Cert ( ID , CB . PK ) → cert ID . Without loss of generality, we assume that the current public key CB . PK ‾ ID = CB . PK in the corresponding tuple ( ID , ID ′ , CB . PK ˜ ID , CB . PK ‾ ID ) of the list L. B I sets ID = ID | | CB . PK, makes the oracle query O CL . PartialPK ( ID ), and then relays the returned partial private key D ID as the certificate for A I .

(5) O CB . SSign ( ID , m ) → CB . σ. For a query ( ID , m ), this oracle browses the list L for the corresponding tuple ( ID , ID ′ , CB . PK ˜ ID , CB . PK ‾ ID ) . Then it sets ID = ID | | CB . PK ‾ ID , makes the signing oracle query O CL . SSign ( ID , m ) and relays this answer to A I .

Output for CBS game. Now the attacker A I returns its forgery ( ID ∗ , m ∗ , CB . σ ∗ ). Without loss of generality, we assume that A I has made the oracle query O CB . CreateU or the replacing public key oracle query for ID ∗ . B I browses the list L for the the corresponding tuple ( ID ∗ , ID ′ ∗ , CB . PK ˜ ID ∗ , CB . PK ‾ ID ∗ ) , and returns ( ID ∗ , m ∗ , CL . σ ∗ ) to its challenger C, where ID ∗ = ID ∗ | | CB . PK ‾ ID ∗ , CL . σ ∗ = CB . σ ∗ .

Analysis. First, from the relations of Π CB and Π CL , it can be easily or trivially seen that  B I perfectly simulates the game settings for A I in the two phases of Initial and Queries. Second, if the forgery ( ID ∗ , m ∗ , CB . σ ∗ ) is successful, i.e. this forgery satisfies the three additions: CB . Verify ( CB . param , ID ∗ , CB . PK ‾ ID ∗ , m ∗ , CB . σ ∗ ) = 1 , ( ID ∗ , m ∗ ) ↛ O CB . SSign , ( ID ∗ , CB . PK ‾ ID ∗ ) ↛ O CB . Cert , then, by checking these two groups of three restrictions one by one (the above and the below), it easily follows that ( ID ∗ , m ∗ , CL . σ ∗ ) is also successful, i.e. this forgery satisfies that CL . Verify ( CL . param , ID ∗ , CL . PK ‾ ID ∗ , m ∗ , CL . σ ∗ ) = 1 , ( ID ∗ , m ∗ ) ↛ O CL . SSign , ID ∗ ↛ O CL . PartialPK . Hence, the success probability of B I is same to that of A I . Additionally, since what B I mainly does in reduction is just issuing some relative queries to C, it is obvious that the time of B I is almost equal to the time t of A I . Hence we say that the running time of B I is O ( t ).  □

Suppose that A II is a super Type II adversary against Π CB with success probability ϵ and running time t. Then there is a super Type II adversary B II against Π CL with success probability ϵ and O ( t ).

Let C denote a Π CL challenger against Type II adversary B II . B II mounts a Type II attack on Π CL using help from A II as follows.

Initial for CBS game. How B II communicates with A II is the same to how B I communicates with A I in the above proof for Theorem 1, except that B II additionally gets the master private key CL . msk and relays it to A II as the master key CB . msk for Π CB .

Queries for CBS game. How B II answers these queries from A II is the same to how  B I simulates the oracles for A I in the above proof for Theorem 1, except that A II does not query the oracle O CB . Cert .

Output for CBS game. How B II generates the forged signature is the same to how B I generates the forged signature in the above proof for Theorem 1. Of course, the forged signatures from B I and B II satisfy different conditions.

Analysis. This analysis can immediately follow from the analysis in the above proof of Theorem 1. Here, we only deal with the somewhat difficult part of the analysis. In particular, we will show how to get CL . PK ‾ ID ∗ ↛ O CL . SecretV , and CL . PK ‾ ID ∗ ← O CL . CreateU , from ID ∗ ↛ O CB . Corrupt , and CB . PK ‾ ID ∗ = O CB . CreateU ( ID ∗ ) , where ID ∗ = ID ∗ | | CB . PK ‾ ID ∗ , CL . σ ∗ = CB . σ ∗ . By checking the simulation of the oracle O CB . CreateU by B II for A II (same to those in the proof of Theorem 1), the equation CB . PK ‾ ID ∗ = O CB . CreateU ( ID ∗ ) means that the original public key CB . PK ˜ ID ∗ is equal to the current public key CB . PK ‾ ID ∗ , i.e. that CB . PK ˜ ID ∗ = CB . PK ‾ ID ∗ . By checking the simulation of oracles O CB . CreateU and O CB . ReplacePK , it can be seen that the CLS current public key CL . PK ‾ ID of ID = ID | | CB . PK ‾ ID is always equal to the CBS current public key CB . PK ‾ ID of ID. In particular, for ID ∗ = ID ∗ | | CB . PK ‾ ID ∗ , we have CB . PK ‾ ID ∗ = CL . PK ‾ ID ∗ . Let the tuple ( ID ∗ , ID ′ ∗ , CB . PK ˜ ID ∗ , CB . PK ‾ ID ∗ ) be the corresponding record in L. Then by checking the simulation of the oracle O CB . CreateU again, it can be seen that the CBS original public key CB . PK ˜ ID ∗ is equal to the CLS original public key CL . PK ˜ ID ′ ∗ of ID ′ ∗ , i.e. that CB . PK ˜ ID ∗ = CL . PK ˜ ID ′ ∗ . By the above three equations, we can get CL . PK ‾ ID ∗ = CL . PK ˜ ID ′ ∗ . Hence, from CB . PK ‾ ID ∗ = O CB . CreateU ( ID ∗ ) , we can get that CL . PK ‾ ID ∗ ← O CL . CreateU . By checking the oracle simulation process provided by B II to A II (same to those in the proof of Theorem 1), it can be seen that O CL . SecretV ( CL . PK ˜ ID ′ ∗ ) is queried by B II only when O CB . Corrupt ( ID ∗ ) is queried by A II . Then by the just proved equation CL . PK ‾ ID ∗ = CL . PK ˜ ID ′ ∗ , we prove that O CL . SecretV ( CL . PK ‾ ID ∗ ) is queried by B II only when O CB . Corrupt ( ID ∗ ) is queried by A II . In other words, from ID ∗ ↛ O CB . Corrupt we can get CL . PK ‾ ID ∗ ↛ O CL . SecretV .  □

Suppose that A I is a normal Type I adversary against Π CB with success probability ϵ and running time t. Then there is a normal Type I adversary B I against Π CL with success probability ϵ and running time O ( t ).

The proof for Theorem 3 is the same to that for Theorem 1, except the difference that the CBS normal signing oracle is simulated depending on the CLS normal signing oracle in this proof for Theorem 3, while the CBS super signing oracle is simulated depending on the CLS super signing oracle in this proof for Theorem 1. Now show how to simulate the CBS normal signing oracle using the CLS normal signing oracle.

For a normal signing query O CB . NSign ( ID , m ), browse the list L for the corresponding tuple ( ID , ID ′ , CB . PK ˜ ID , CB . PK ‾ ID ) . Set ID = ID | | CB . PK ‾ ID and make the signing oracle query O CL . NSign ( ID , m ) and relay this answer to A I . By checking the simulation of the oracle O CB . CreateU , it can be seen that the original CBS public key CB . PK ˜ ID of ID is the original CLS public key CL . PK ˜ ID ′ of ID ′ , and the original CLS public key CL . PK ˜ ID ′ of ID ′ is the current CLS public key CL . PK ‾ ID of ID. Hence, the query ( ID , m ) will not be rejected by the oracle O CL . NSign . Hence, this proof can immediately follow Theorem 1.  □

Suppose that A I is a normal Type II adversary against Π CB with success probability ϵ and running time t. Then there is a normal Type II adversary B I against Π CL with success probability ϵ and running time O ( t ).

The proof for Theorem 4 is the same to that for Theorem 2, except for the difference that the CBS normal signing oracle is simulated depending on the CLS normal signing oracle in this proof for Theorem 4, while the CBS super signing oracle is simulated depending on the CLS super signing oracle in this proof for Theorem 2. Additionally, in the proof of Theorem 3, we have showed how to simulate the CBS normal signing oracle by using the CLS normal signing oracle. Hence, this proof can immediately follow Theorem 2 and Theorem 3.  □

 Comparison Between CLS-2-CBS with Wu <italic>et al</italic>.’s Result

Our generic construction is very similar to that of Wu et al. (2009). In particular, if we replace ID = ID | | CB . PK ID with ID = H ( ID | | CB . PK ID ) , where H is a hash function , then our construction will become identical with Wu et al.’s (2009) construction.

Our security proof is in the standard model. Contrastingly, the security proof in Wu et al. (2009) relies the assumption that the hash function in ID = H ( ID | | CB . PK ID ) is a random oracle. As a result, our method can convert a CLS scheme secure in the standard model into a CBS scheme secure in the standard model. However, through Wu et al.’s method, the resulting CBS scheme is only secure in the random oracle model. Of course, the standard model is preferable over the random oracle model in security proof Canetti et al. (2004).

We emphasize the theoretical significance of our generic construction. Roughly speaking, by our result, the cryptographic primitive of CBS can be obtained from the single primitive of CLS. However, by Wu et al.’s result, the primitive of CBS can not be obtained from the single primitive of CLS, since the random oracle is additionally needed.

To support our generic conversion, the new CLS security model is developed by introducing one nontrivial attack never mentioned before. This new definition succeeds in more elaborately capturing the security notion of CLS. Notably, this new security is inherently preserved in many existing CLS schemes. In other words, our contribution in this respect is that we point out, formalize, and apply this subtle property to refine the close relation between CLS and CBS.

Application Example – One Concrete CBS scheme

Let G 1 and G 2 be two groups of prime order q and let P be a generator of G 1 , where G 1 is additively represented and G 2 is multiplicatively represented. A map e : G 1 × G 1 → G 2 is said to be a bilinear pairing, if the following three conditions hold: (1) e is bilinear, i.e. e ( a P , b P ) = e ( P , P ) a b for all a , b ∈ Z q ∗ ; (2) e is non-degenerate, i.e. e ( P , P ) ≠ 1, where 1 is the identity of G 2 ; (3) e is efficiently computable.

The CDH problem: given P, a P, b P with uniformly random choices of a , b ∈ Z q , output a b P. An algorithm A has success probability ϵ in solving the CDH problem, if Pr [ A ( P , a P , b P ) = a b P ] = ϵ ] . The CDH problem is said to be ( t , ϵ )-intractable if there is no algorithm to solve this problem with time less than t and success probability greater than ϵ.

The following scheme is constructed from the second CLS scheme in Huang et al. (2011) through the generic conversion CLS-2- CBS.

Setup ( 1 k ) → ( msk , params ). This algorithm is run by the authority CA. Let G 1 and G 2 be two groups of prime order q, P be a generator of G 1 , and e : G 1 × G 1 → G 2 be a bilinear pairing. It specifies two hash functions H 0 , H 1 : { 0 , 1 } ∗ → G 1 ∗ . Let Γ be the set of identity information. It chooses the master key msk = s uniformly at random from Z q and computes the public key mpk = s P. The system parameter is params = ( q , e , G 1 , G 2 , P , mpk , H 0 , H 1 , Γ ) .

GenUK ( params ) → ( PK ID , SK ID ). It selects a random SK ID ∈ Z q , computes PK ID = SK ID P and outputs SK ID , PK ID as ID’s secret/public key pair.

Cert ( CB . msk , params , ID , PK ID ) → cert. It sets cert ID = s H 0 ( ID | | PK ID ).

Sign ( params , ID , cert ID , PK ID , SK ID , m ) → σ. For a message m, the user ID computes the signature σ = ( u , v , W ), where

u = H 1 ( m | | ID | | PK ID | | r 1 P | | e ( P , P ) r 2 ) for random r 1 , r 2 ∈ Z q , which are chosen by ID;

v = r 1 − u · SK ID mod q, W = r 2 P − u · cert ID .

Verify ( params , ID , PK ID , m , σ ) → b. Given a message/signature pair ( m , σ = ( u , v , W ) ), user ID’s public key PK ID , anyone can check whether u = H 1 ( m | | ID | | PK ID | | v P + u · PK ID | | e ( W , P ) e ( H 0 ( ID | | PK ID ) , s P ) u ) . If the equality holds, output 1; otherwise, output 0.

The second certificateless scheme in Huang et al. (2011) is CL-EUF-CMCI secure against a super Type I adversary.

The proof directly follows the observation that (1) the security definition against a super Type I adversary in Huang et al. (2011) is essentially the same as that of ours, except some notation differences.  □

The second certificateless scheme in Huang et al. (2011) is CL-EUF-CMCI secure against a super Type II adversary.

First, compare the security definition against a super Type II adversary in Huang et al. (2011) and that of ours.

Observe the difference: Huang’s definition in Huang et al. (2011) requires that the attacked identity’s public key be the original one, while our definition allows that the attacked identity’s public key can be the replaced one under the constraint condition that this public key must be the other identity’s original public key. In other words, for our definition, the attacker can replace Alice’s public key with Bob’s original public key, and then attack Alice with this replaced public key.

Observe the common purpose of these restrictions: in both definitions, the super type II adversary does not know the attacked identity’s current secret value. All in all, facing the same purpose of keeping the target secret value secret from the adversary, our definition tries to make less restrictions while the restriction in Huang’s definition goes too far.

 Next revisit the security proof (for Theorem 4.4) in Huang et al. (2011):

Observe the key point of probability analysis (for Theorem 4.4 in Huang et al. (2011)): only if the target public key comes from the challenger and the corresponding secret value is never queried, this security proof always conducts well. In other words, for the proof of Huang et al. (2011), what matters is not that the target public key is “original”, but that the corresponding secret key is not known by this adversary.

At last, following the above observations, we can easily obtain the security proof for Lemma 2, by slightly adapting the security proof for Theorem 4.4 in Huang et al. (2011): in addition to some trivial modifications, change (1) the condition equation “ ID ∗ = ID π ” into “ ID ∗ ’s current public key = ID π ’s original public key” and (2) “ A I I is not allowed to replace this user’s public key” into “ A I I is not allowed to query the secret value corresponding to this user’s current public key”. Hence, we can omit the detailed proof.  □

The above CBS scheme is secure (in the random oracle model) against CB.Super- A I and CB.Super- A II , assuming that CDH problem is hard in G 1 .

We can obtain the proof immediately from Theorems 1, 2 for the security of the generic construction and Lemmas 1, 2 for the security of the underlying CLS scheme.  □

Just as the proof of Lemmas 1 and 2, we can similarly prove that many existing certificateless signature schemes are secure in our new security model, by slightly modifying their original proof. In fact, by revisiting the two remarks during Definition 2 in Section 2 and the three observations in Lemma 2, we can conclude that how to get these proofs is almost trivial. In other words, for a normal signing query, the common basic reason why both the original proof and the modified proof conduct well is not that the public key has been replaced, but that the current secret value is not known by the challenger; for a signature forgery, the common basic reason why both the original proof and the modified proof conducts is not that the public key has been replaced, but that the current secret value is not known by the adversary. Hence, these almost trivial modifications and the proof in our new security model for existing CLS schemes can be omitted here. Some examples among them are as follows.

The first certificateless scheme in Huang et al. (2011) is CL-EUF-CMCI secure against a normal Type I adversary and a super Type II adversary;

The certificateless scheme in Huang et al. (2005) is CL-EUF-CMCI secure against a normal Type I adversary and a normal Type II adversary;

The certificateless scheme in Choi et al. (2011) is CL-EUF-CMCI secure against a super Type I adversary and a super Type II adversary;

The certificateless scheme in Zhang et al. (2007) is CL-EUF-CMCI secure against a normal Type I adversary and a normal Type II adversary.

The certificateless scheme based on RSA in Zhang and Mao (2012) is CL-EUF-CMCI secure against a normal Type I adversary and a normal Type II adversary.

The certificateless scheme in Pang et al. (2015) is CL-EUF-CMCI secure against a normal Type I adversary and a normal Type II adversary.

All the above certificateless signature schemes can be used to construct certificate-based signature schemes through the generic framework. For example, based on the state-of-the-art CLS signature scheme secure in the standard model (Pang et al., 2015), we can construct one CBS scheme in the standard model which is almost the same to the the state-of-the-art CBS scheme recently proposed by Lu and Li (2015). Hence, we omit the trivial scheme description. In particular, both of them can be seen as the extension of the famous Waters signature scheme (Waters, 2005).

Now we simply present the efficiency comparisons between the Lu-Li CBS scheme and our CBS scheme generically constructed from Pang et al.’s CLS scheme. First, because both of them are constructed based on the Waters signature scheme, there is almost no difference in the first three algorithms for setup, user key generation and the certification generation of both CBS schemes, except some notational differences. Second, for the signing algorithms, both CBS schemes have the same signature size, i.e. 3 group elements. To generate a signature, our CBS scheme needs 7 exponentiations in the bilinear group, while the Lu-Li CBS scheme needs 6 exponentiations. Third, to verify a signature, both CBS schemes need 3 pairing computations. Here note that group exponentiations and parings are the main computation for generating and verifying a signature respectively. Hence, we can see that the CBS scheme constructed using our generic framework in the standard model is almost as efficient as the Lu-Li CBS scheme in terms of signature size and computation complexity.

 Conclusion

In this paper, we proposed a new provably secure generic conversion from CLS to CBS. To analyse its security, we redefined the security model for CLS by formalizing some important but previously ignored properties. This new security definition is the main reason why our new conversion can be provably secure in the standard model. As an example, we constructed a new provably secure certificate-based signature scheme by applying this new generic method. These results formally showed that the two conceptions of CBS and CLS (CBC and CLC) are very closely related to each other.

 Acknowledgements

This work is partially supported by National Natural Science Foundation of China (61202475, 61472114 and 61133014), Shandong Province Statistics Key Project (KT16022), the Priority Academic Program Development of Jiangsu Higher Education Institutions (PAPD, Nanjing University of Information Science & Technology) and Jiangsu Collaborative Innovation Center on Atmospheric Environment and Equipment Technology (CICAEET, Nanjing University of Information Science & Technology).

 References Al-Riyami, S.S., Paterson, K.G. (2003). Certificateless public key cryptography. In: Proceedings of ASIACRYPT 2003, Lecture Notes in Computer Science, Vol. 2894. Springer, Berlin, pp. 452–473. Al-Riyami, S.S., Paterson, K.G. (2005). CBE from CLE: a generic construction and effiient schemes. In: Proceedings of PKC 2005, Lecture Notes in Computer Science, Vol. 3386. Springer, Berlin, pp. 398–415. Bellare, M., Rogaway, P. (1993). Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of 1st ACM Conference on Computer and Communications Security. ACM Press, pp. 62–73. Canetti, R., Goldreich, O., Halevi, S. (2004). The random oracle methodology, revisited. Journal of ACM, 51(4), 557–594. Choi, K.Y., Park, J.H., Lee, D.H. (2011). A new provably secure certificateless short signature scheme. Computers & Mathematics with Applications, 61(7), 1760–1768. Gentry, C. (2003). Certificate-based signature and the certificate revocation problem. In: Proeedings of EUROCRYPT 2003, Lecture Notes in Computer Science, Vol. 2656. Springer, Berlin, pp. 272–293. Guo, P., Wang, J., Li, B., Lee, S. (2014). A variable threshold-value authentication architecture for wireless mesh networks. Journal of Internet Technology, 15(16), 929–936. Huang, X., Susilo, W., Mu, Y., Zhang, F. (2005). On the security of certificateless signature schemes from asiacrypt 2003. In: Proceedings of Cryptology and Network Security 2005, Lecture Notes in Computer Science, Vol. 3810. Springer, Berlin, pp. 13–25. Huang, X., Mu, Y., Susilo, W., Wong, D., Wu, W. (2011). Certificateless signatures: new schemes and security models. The Computer Journal, 55(4), 457–474. Kang, B.G., Park, J.H. (2005). Is it possible to have CBE from CLE? Iacr cryptology print archive. available at eprint.iacr.org/2005/431.ps. Kang, B.G., Park, J.H., Hahn, S.G. (2004). A certificate-based signature scheme. In: Proceedings of CT-RSA 2004, Lecture Notes in Computer Science, Vol. 2964. Springer, Berlin, pp. 99–111. Li, J., Huang, X., Mu, Y., Susilo, W., Wu, Q. (2010). Constructions of certificate-based signature secure against key replacement attacks. Journal of Computer Security, 18(3), 421–449. Li, J., Huang, X., Zhang, Y., Xu, L. (2012). An efficient short certificate-based signature scheme. Journal of Systems and Software, 85(2), 314–322. Liu, J.K., Au, M.H., Susilo, W. (2007). Self-generated certificate public key cryptography and certificateless signature/encryption scheme in the standard model. In: Proceedings of the 2nd ACM Symposium on Information, Computer and Communications Security. ACM Press, pp. 273–283. Liu, J.K., Baek, J., Susilo, W., Zhou, J. (2008). Certificate-based signature schemes without pairings or random oracles. In: Proceedings of Information Security Conference 2008, Lecture Notes in Computer Science, Vol. 5222. Springer, Berlin, pp. 285–297. Liu, J.K., Bao, F., Zhou, J. (2011). Short and efficient certificate-based signature. In: Proceedings of Networking Workshops 2011, Lecture Notes in Computer Science, Vol. 2867. Springer, Berlin, pp. 167–178. Lu, Y., Li, J. (2015). Improved certificate-based signature scheme without random oracles. IET Information Security, 10(2), 80–86. Pang, L., Hu, Y., Liu, Y., Xu, K., Li, H. (2015). Efficient and secure certificateless signature scheme in the standard model. International Journal of Communication Systems. https://doi.org/10.1002/dac.3041. Published online in Wiley Online Library (wileyonlinelibrary.com). Shamir, A. (1984). Identity-based cryptosystems and signature schemes. In: Proceedings of Crypto 1984, Lecture Notes in Computer Science, Vol. 196. Springer, Berlin, pp. 47–53. Shen, J., Tan, H., Wang, J., Wang, J.W., Lee, S. (2015). A novel routing protocol providing good transmission reliability in underwater sensor networks. Journal of Internet Technology, 16(1), 171–178. Waters, B. (2005). Efficient identity-based encryption without random oracles. In: Proceedings of EUROCRYPT 2005, Lecture Notes in Computer Science, Vol. 3494. Springer, Berlin, pp. 114–127. Wu, W., Mu, Y., Susilo, W., Huang, X. (2009). Certificate-based signatures revisited. Journal of Universal Computer Science, 15(8), 1659–1684. Wu, W., Mu, Y., Susilo, W., Huang, X. (2012). Provably secure construction of certificate-based encryption from certificateless encryption. The Computer Journal, 55(10), 1157–1168. Xie, S., Wang, Y. (2014). Construction of tree network with limited delivery latency in homogeneous wireless wensor networks. Wireless Personal Communications, 78(1), 231–246. Zhang, J., Mao, J. (2012). An efficient RSA-based certificateless signature scheme. The Journal of Systems and Software, 85(3), 638–642. Zhang, L., Zhang, F., Zhang, F. (2007). New efficient certificateless signature scheme. In: Proceedings of EUC 2007, Lecture Notes in Computer Science, Vol. 4809. Springer, Berlin, pp. 692–703.