Al-Riyami and Paterson (2003) first introduced the notion of certificateless signature (CLS) scheme and gave a concrete construction of CLS scheme. In the CLS scheme, users’ private key was divided into two parts. One part is chosen by users themselves and another part is generated by a third party called KGC, which successfully avoids the key escrow problem. Thanks to maintaining the advantages of eliminating the required certificates in ID-based signature while avoiding key escrow problem, much attention has been paid to the research of CLS. After Al-Riyami and Paterson (2003) proposed the first CLS scheme, dozens of CLS schemes were proposed in terms of different research lines (Jia et al., 2018; Huang et al., 2005; Karati et al., 2018b; He et al., 2012; Xiong et al., 2019). By considering the criticism of random models, Liu et al. (2007) proposed the first concrete CLS scheme which was proved to be secure in the standard model. Unfortunately, Xiong et al. (2008) indicated that Liu et al.’s scheme cannot be able to resist malicious-but-passive KGC attack. In this attack, KGC can maliciously generate system parameters during the system setup stage and forge the signature with the knowledge of the secret value used to calculate the system parameters. For this type of attack, Xiong et al. also put forward an improved scheme in their paper. In the meanwhile, Yuan et al. (2009) presented a CLS scheme in the standard model. Unfortunately, Xia et al. (2010) showed that both Xiong et al.’s improved scheme and Yuan et al.’s scheme are insecure under the key replacement attack. Aiming to resist the key replacement attack proposed by Xia et al., Yu et al. (2012) presented a new CLS scheme in the standard model. Subsequently, Yu et al.’s scheme was proved to be insecure under the attack of Xiong et al. Recently, Shim (2018a) proposed a CLS scheme which makes it possible to prove security in the standard model. In short, most of the existing schemes proposed in the standard are insecure.

The idea of revocation was first proposed by Boneh et al. (2001) and was used in RSA-type cryptosystems. In their scheme, a semi-trusted server called Security Mediator (SEM) is introduced to issue tokens. If a user wants to sign or decrypt a message, he/she must get the token for the message. The scheme revokes the ability of the user to sign or decrypt by stopping issuing tokens to the user. Following the works of Boneh et al. (2001), some well-designed schemes have been constructed in certificateless cryptosystem. Chow et al. (2006) introduced the concept of Security Mediator into the certificateless (SMC) cryptosystem for the first time, and proposed a formal security model. After that, the first pairing-free provable secure SMC scheme as well as a concrete construction was presented by Yap et al. (2007). Unfortunately, SEM is involved in the generation of each signature which causes expensive burden. Furthermore, it is necessary for the Security Mediator to preserve large numbers of secret keys which makes it easier for an attacker to compromise a key. To deal with this problem, Tsai and Tseng (2015) proposed a new RCLS scheme. In their scheme, the user’s partial private key is updated in period time. When the user’s private key is compromised or the user leaves, KGC stops updating the partial private key. At the same time, Shen et al. (2013) showed an efficient certificateless encryption (CLE) with the function of revocation, which was proved to be CCA2-secure under the standard model. Xiong and Qin (2015) presented an RCLS scheme which can resist signing key exposure and applied it into the wireless body area networks. However, Shim (2018b) pointed out that Xiong et al.’s scheme is vulnerable to the type I adversary. Sun et al. (2014) proposed an RCLS schemes from bilinear pairings that was proved to be secure in the random oracle model. To eliminate the random oracle model, Tsai et al. (2014) introduced an RCLS scheme which was proven in the standard model. However, in this paper, Tsai et al.’s scheme is demonstrated to be neither efficient nor resistant to malicious-but-passive KGC attacks. After that, many CLS or CLE schemes with revocation mechanism were presented in the literature (Zhang and Zhao, 2015; Hung et al., 2016; Sun et al., 2018; Zheng et al., 2017). However, most of the existing schemes cannot resist malicious-but-passive KGC attacks.

This paper’s structure is as follows: some preliminaries including bilinear pairings, complexity assumption, system framework and security notions are introduced in Section 2. Section 3 briefly analyses Tsai et al.’ scheme and then displays a forgery attack about their scheme. A concrete RCLS scheme and associated security proof are demonstrated in Section 4. Section 5 provides the performance evaluation. Section 6 summarizes this paper.

Chosen two multiplicative cyclic groups G,GT of prime order p, given two random generators u,v of G , the bilinear map eˆ:G×G→GT needs to satisfy the following features: 1.

Bilinearity: For any a,b∈Zp∗ , eˆ(ua,vb)=eˆ(u,v)ab .

•

Computational Diffie–Hellman (CDH) Problem: Given a tuple (g,ga,gb) to calculate gab where a,b∈Zp∗ , g∈G .

An RCLS scheme consists of eight algorithms whose details are depicted below. •

Setup: A KGC produces a system master secret key SSK and system public parameters SPP on input the security parameter k.

According to the scheme (Al-Riyami and Paterson, 2003), there are two kinds of attackers in the certificateless signature setting, which are usually called the Type-I adversary AI and Type-II adversary AII . AI models a malicious user who has the right to replace a legitimate user’s public key without knowing the system master secret key. AII models a malicious-but-passive KGC who has knowledge of the system master secret key while is not allowed to replace any public key. For a RCLS scheme’s security, there is one more adversary called a revoked user Aru who cannot obtain the time key but still has the right to replace the public key (Sun et al., 2014). To better explain the attacking ability of these adversaries, we first define six oracles that adversary A∈{AI,AII,Aru} can access. •

Public-Key-Extract Query: After receiving an identity ID , this oracle produces the user’s public key PKID .

Define five collision-resistant hash functions H0:{0,1}∗→{0,1}nu , H1:{0,1}∗→{0,1}nt , H2:G×G→{0,1}nk , H3:G×G→{0,1}ns , H4:{0,1}∗→{0,1}nm , where nu , nt , nm , ns , nk , are fixed lengths from Z . •

Setup: Taken k as the security parameter, KGC generates a bilinear map eˆ:G×G→GT , where G , GT are cyclic groups of order p. Furthermore, KGC picks x,y∈Zp∗ , g,g1,g2∈G and calculates g1=gx+y , SSK=g2x , where g,SSK denote a generator of G and the system secret key respectively. In addition, let g2y denotes the time secret key. After that, KGC randomly selects u′,t′,k′,s′,m′∈G , and five vectors U=[ui]∈Gnu , T=[ti]∈Gnt , K=[ki]∈Gnk , S=[si]∈Gns , M=[mi]∈Gnm . Finally, KGC issues the system public parameters SPP=⟨G,GT,eˆ,g,g1,g2,U,T,K,S,M,H0,H1,H2,H3,H4,u′,t′,k′,s′,m′⟩ .

Tsai et al. alleged that their scheme (Tsai et al., 2014) was secure against Type-I and Type-II adversaries under the standard model. After a careful investigation, however, we found that their scheme was insecure against a Type-II adversary. Then we show a concrete attack instance to demonstrate that the scheme in Tsai et al. (2014) is so vulnerable that any malicious-but-passive KGC, AII , can forge a valid signature of message M∗ for identity ID∗ . The attack is as follows:

Anyone can verify the signature σ∗ through performing the algorithm RCL-Verify, which is to check whether the equation eˆ(g,σ1∗)=?eˆ(g1,g2∗)·eˆ(σ2∗,u′∏i=1nuuiνi)·eˆ(σ3∗,t′∏i=1nttiνti)·eˆ(PK(1),g2∗(k′∗∏i=1nkkiνui))·eˆ(PK(2),s′∗∏i=1nssiνsi)·eˆ(σ4∗,m′∏i=1nmmiνmi) holds. This verification will hold due to the following fact: eˆ(g,σ1∗)=eˆ(g,g1γ·(u′ ∏i=1nuuiνi)a·(t′ ∏i=1nttiνti)b·(PK(1))(γ+α+Σi=1nkαiνui)·(PK(2))(β+Σi=1nsβiνsi)·(m′ ∏i=1nmmiνmi)c)=eˆ(g1,gγ)·eˆ(ga,u′ ∏i=1nuuiνi)·eˆ(gb,t′ ∏i=1nttiνti)·eˆ(PK(1),g(γ+α+Σi=1nkαiνui))·eˆ(PK(2),g(β+Σi=1nsβiνsi))·eˆ(gc,m′ ∏i=1nmmiνmi)=eˆ(g1,g2∗)·eˆ(σ2∗,u′ ∏i=1nuuiνi)·eˆ(σ3∗,t′ ∏i=1nttiνti)·eˆ(PK(1),g2∗(k′∗ ∏i=1nkkiνui))·eˆ(PK(2),s′∗ ∏i=1nssiνsi)·eˆ(σ4∗,m′ ∏i=1nmmiνmi).

Notice that AII neither knows svID=(x1,x2) nor replaces (PK(1),PK(2)) . Thus, the RCLS scheme of Tsai et al. cannot withstand the forgery attack mounted by a malicious-but-passive KGC. The underlying reason is that the user secret value svID is embedded in the signature inappropriately such that the user public key gx1,gx2 can be utilized by the malicious-but-passive KGC to forge the signature with the support of the random numbers associated with the system parameters. Specially, SKID=g2x1(k′∏i=1nkkiνui)x1(s′∏i=1nssiνsi)x2 has been regarded as one factor in the generation of signature σ1 , and this factor can be easily generated by raising the gx1,gx2 with the exponentiations α,β,γ,αi,βi . Therefore, it is easy to forge the signature σ to make the equation hold in the algorithm RCL-Verify.

Inspired by a certificateless signature scheme in the standard model that can resist the malicious-but-passive attacks (Shim, 2018a), we construct a certificateless signature scheme with revocation in the standard model. In the proposed scheme, it is possible to construct a RCLS scheme secure against the Type-I and II attackers as well as the malicious-but-passive attacks by using the term (g3x2)x1−1 . To be specific, although a malicious KGC calculates g3 as gω of its own choice ω to implement the malicious-but-passive attack, the malicious KGC cannot calculate (g3x2)x1−1 without the knowledge of  x1 . In other words, if one uses g3x2 instead of (g3x2)x1−1 , the malicious KGC can calculate g3x2 by calculating (gx2)ω from the known user’s public key gx2 . In fact, there does not exist a probabilistic polynomial-time algorithm that can calculate g3x2 with non-negligible advantage on inputting g,gω,gx2 . Besides, there does not exist a probabilistic polynomial-time algorithm that can calculate (g3x2)x1−1 with non-negligible advantage on inputting g3,g3x1,g3x2 , which is equivalent to the CDH problem according to Bao et al. (2003). The detail description of the proposed RCLS scheme is presented as follows:

Define three collision-resistant hash functions H0:{0,1}∗→{0,1}nu , H1:{0,1}∗→{0,1}nt , H2:{0,1}∗→{0,1}nm , where nu,nt,nm are fixed lengths from Z . •

Setup: Taken k as the security parameter, KGC generates a bilinear map eˆ:G×G→GT , where G,GT are cyclic groups of order p. Furthermore, KGC picks x,y∈Zp∗,g2,g3∈G and calculates g1=gx+y , A=eˆ(g1,g2) , SSK=(g2x,g2y) , where g,SSK denote a generator of G and the system secret key respectively. After that, KGC randomly selects α,β,γ∈G , and three vectors U=[ui]∈Gnu , T=[ti]∈Gnt , M=[mi]∈Gnm . Define three functions f1,f2,f3 via f1(U)=α∏i∈Uui , f2(T)=β∏i∈Tti , f3(M)=γ∏i∈Mmi , where U⊆{1,2,…,nu} , T⊆{1,2,…,nt} , M⊆{1,2,…,nm} . Finally, KGC issues the system public parameters SPP=⟨G,GT,eˆ,g,g1,g2,g3,A,f1,f2,f3,U,T,M,H0,H1,H2⟩ .