# Secure Certificateless Signature with Revocation in the Standard Model

Authors: Tung-Tso Tsai; Sen-Shan Huang; Yuh-Min Tseng
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Certificateless public key cryptography is very attractive in solving the key escrow problem which is inherent in identity- (ID-) based public key cryptography. In the past, a large number of certificateless cryptographic schemes and protocols were presented, but a secure certificateless signature in the standard model (without random oracles) is still not accessible until now. To the best of our knowledge, all the
previously proposed certificateless signature schemes were insecure under a considerably strong security model in the sense that they suffered from outsiders’ key replacement attacks or the attacks from the key generation center (KGC). In this paper, we propose a certificateless signature scheme without random oracles. Moreover, our scheme is secure under the strong security model and provides a public revocation mechanism, called revocable certificateless signature (RCLS). Under the standard computational Diffie-Hellman assumption, we formally demonstrate that our scheme possesses existential unforgeability against adaptive chosen-message attacks.


---

## Body

## 1. Introduction

In 2001, Boneh and Franklin [1], led by Shamir’s idea [2], realized a practical construction of an identity- (ID-) based public key system (ID-PKS) by using bilinear pairings, such as Weil, Tate, and Ate pairings. Subsequently, the study of ID-based cryptographic mechanisms using bilinear pairings has received a great attention from researchers. A large number of literatures, such as [3–7], have been presented. An ID-based public key system consists of two roles, namely, a trusted private key generator (PKG) and users. A user’s identity information, such as social security number, e-mail address, and IP address, is viewed as her/his public key and the corresponding private key is computed and issued secretly by the trusted PKG. Evidently, the PKG owns all the users’ private keys so that it can decrypt ciphertexts or sign messages on behalf of any user as it wishes. Hence, an ID-based public key system always inherits an imperfection—the key escrow problem.To overcome the key escrow problem in ID-based public key systems, Gentry [8] introduced the concept of certificate-based public key system, which contains two roles, namely, a key generation center (KGC) and users. Here, we roughly describe Gentry’s system. A user first generates the public key and then sends it to the KGC. The KGC generates a certificate for the user’s public key and then sends it to the user. The certificate also acts as a decryption or signing key of the user.In 2003, Al-Riyami and Paterson [9] proposed a new paradigm for public key cryptography by combining the traditional public key system (PKS) with ID-PKS, termed certificateless public key system. As a result, certificates are no longer needed, but the two roles, namely, a KGC and users, remain in their certificateless public key system. A user’s private key consists of two components: a partial private key and a secret key. They are generated by the KGC and the user, independently. In this case, the KGC does not have access to the user’s full private key due to the lack of the secret key generated by the user. Hence, this certificateless design resolves the key escrow problem in ID-based public key systems. Subsequently, a numer of certificateless cryptographic schemes and protocols have been studied [10–22].Al-Riyami and Paterson [9] presented a security model for certificateless public key cryptography. It consists of two types of adversaries, namely, outsiders (Type I adversary) and the KGC (Type II adversary). They also presented a concrete certificateless signature (CLS) scheme but did not offer security notion for this kind of scheme. Two years later, Huang et al. [11] first provided formal security notion for CLS schemes and pointed out that Al-Riyami and Paterson’s scheme above suffers from key replacement attacks from outsiders in the sense that, by replacing a user’s public key, an outsider can forge valid signatures without the knowledge of the user’s partial private key. In 2004, Yum and Lee [23] gave a generic construction of CLS schemes by combining an ID-based signature scheme with a signature scheme based on traditional public key systems. In 2006, Hu et al. [12] presented a considerably strong security model for CLS schemes and pointed out a security drawback in Yum and Lee’s construction. Since then, Hu et al.’s security model is considered promising and is generally adopted to formalize the security of CLS schemes.To improve the efficiency of CLS schemes, several constructions of CLS were built and discussed such as [24–27]. In addition, for providing relatively short signature, Huang et al. [14] proposed a certificateless short signature scheme, which was shown to suffer from key replacement attacks by Shim [28]. Recently, Chen et al. [29] wrote a survey article on CLS schemes, in which they also presented a secure certificateless short signature scheme.The security of all the CLS schemes mentioned above was based on the random oracle model [30]. Although these schemes offer better performance, they could be insecure when random oracles are instantiated with some particular hash functions such as SHA-1. In order to compensate this situation, a secure CLS scheme in the standard model (without random oracles) must be constructed. Based on the ID-based signature scheme presented by Paterson and Schuldt [31], Liu et al. [16] proposed the first CLS scheme in the standard model. However, Xiong et al. [17] pointed out that Liu et al.’s scheme is insecure against KGC attacks. To withstand the KGC attacks, two CLS schemes [18, 21] were independently proposed but later shown to be insecure [32, 33]. To our best knowledge, a secure CLS in the standard model (without random oracles) is still not accessible. All the previously proposed CLS schemes in the standard model were insecure under Hu et al.’s strong security model in [12] in the sense that they suffered from key replacement attacks from outsiders (Type I adversary) or attacks from the key generation center (Type II adversary).A public key system should provide an efficient revocation mechanism to revoke misbehaving/compromised users. In traditional public key systems, users are able to know the revoked public keys by querying the certificate revocation list (CRL) [34] which contains all the revoked public keys. Evidently, the CRL approach is no longer suited for the certificateless public key system due to the lack of the usage of certificates. So, revoking misbehaving/compromised users in certificateless public key system has received attention from cryptographic researchers. Recently, Tsai and Tseng [22] and Shen et al. [35], independently, used the revocation technique presented by Tseng and Tsai [36] to propose a revocable certificateless public-key encryption (RCL-PKE) scheme. However, there was little work in constructing a revocable CLS scheme without random oracles.Our Construction. In this paper, we will propose a CLS scheme with revocation in the standard model, calledrevocable certificateless signature (RCLS). This scheme includes two merits.(1)
Under the standard computational Diffie-Hellman assumption, our scheme is secure under Hu et al.’s strong security model. We will formally demonstrate that our scheme possesses existential unforgeability against adaptive chosen-message attacks under the standard computational Diffie-Hellman assumption.(2)
Our CLS scheme provides a public revocation mechanism to revoke misbehaving/compromised users.The rest of the paper is organized as follows. We give some preliminaries in Section2. In Section 3, we review the framework and security notion for RCLS schemes. A concrete RCLS scheme in the standard model is proposed in Section 4. We analyze the security of the proposed scheme in Section 5. In Section 6, we present discussions and comparisons between some existing schemes and ours. Finally, a concluding remark is drawn in Section 7.


## 2. Preliminaries

In this section, we will review some fundamentals required in this sequel, namely, the concept of bilinear pairings and the related assumption.


### 2.1. Bilinear Pairings

In the sequel,G1 and G2 denote two multiplicative cyclic groups of large prime order p. A map e^:G1×G1→G2 is called an admissible bilinear map if it satisfies the following properties.(1)
The mape^ is bilinear: given g,h∈G1 and a,b∈Zp*, we have e^(ga,hb)=e^(g,h)ab.(2)
The mape^ is nondegenerate: there exist g,h∈G1 such that e^(g,h)≠1.(3)
The mape^ is efficiently computable. We refer the reader to previous literature, such as [1, 9], for a more comprehensive description of groups, maps, and other parameters.


### 2.2. Related Mathematical Assumption

Here, we introduce the computational Diffie-Hellman (CDH) problem and define its corresponding security assumption (CDH assumption) on which our scheme is based.Definition 1.
Letg be a generator of G1. Given g,ga,gb with unknown a,b randomly chosen from Zp*, the CDH problem is to compute gab. The associated CDH assumption states that there exists no probabilistic polynomial-time adversary A that can solve the CDH problem with nonnegligible probability. The successful probability (advantage) of the adversary A is presented as
(1)AdvA=Pr⁡[A(g,ga,gb)=gab:g∈G1,a,b∈Zp*],
where the probability is over the random choice consumed by the adversary A.


## 2.1. Bilinear Pairings

In the sequel,G1 and G2 denote two multiplicative cyclic groups of large prime order p. A map e^:G1×G1→G2 is called an admissible bilinear map if it satisfies the following properties.(1)
The mape^ is bilinear: given g,h∈G1 and a,b∈Zp*, we have e^(ga,hb)=e^(g,h)ab.(2)
The mape^ is nondegenerate: there exist g,h∈G1 such that e^(g,h)≠1.(3)
The mape^ is efficiently computable. We refer the reader to previous literature, such as [1, 9], for a more comprehensive description of groups, maps, and other parameters.


## 2.2. Related Mathematical Assumption

Here, we introduce the computational Diffie-Hellman (CDH) problem and define its corresponding security assumption (CDH assumption) on which our scheme is based.Definition 1.
Letg be a generator of G1. Given g,ga,gb with unknown a,b randomly chosen from Zp*, the CDH problem is to compute gab. The associated CDH assumption states that there exists no probabilistic polynomial-time adversary A that can solve the CDH problem with nonnegligible probability. The successful probability (advantage) of the adversary A is presented as
(1)AdvA=Pr⁡[A(g,ga,gb)=gab:g∈G1,a,b∈Zp*],
where the probability is over the random choice consumed by the adversary A.


## 3. Framework and Security Notion of Revocable Certificateless Signature

In this section, we will define the framework and security notion for our RCLS scheme. In 2003, Al-Riyami and Paterson [9] presented a concrete certificateless signature (CLS) scheme, but did not give formal security notion for such schemes. Later, Yum and Lee [23] and Huang et al. [11] defined formal security notion for CLS schemes. Furthermore, Hu et al. [12] enhanced the definitions in [11, 23] to permit stronger queries. Since then, Hu et al.’s security model is generally adopted to formalize the security of CLS schemes. By modifying Hu et al.’s framework and security notion for CLS schemes [12], we present a framework of our RCLS scheme by addingtime key update algorithm. Under this new framework, a user’s partial private key consists of two components, namely, an initial secret key (fixed since being issued) and a time update key (altered every period of time). As a result, the issue on time update key queries must be addressed in the security notion for CLS schemes.Definition 2.
A revocable certificateless signature (RCLS) is specified by six algorithms, namely, the system setup, the initial key extract, the time key update, the user key generation, the signing, and the verification.(i)
System setup: this algorithm takes security parameter l and the total number z of periods as input and returns a system secret key, a time secret key, and the public parameters Params. We assume that Params are publicly and authentically available in all the following algorithms.(ii)
Initial key extract: this algorithm takes the system secret key and a user’s identity ID as input and returns the user’s initial secret key DID to the user via a secure channel.(iii)
Time key update: this algorithm takes the time secret key, a user’s identity ID, and a period t as input and returns the user’s time update key TID,t to the user via a public channel.(iv)
User key generation: this algorithm takes the public parameters Params and ID as input and outputs the secret key SKID and public key PKID.(v)
Signing: this algorithm takes a user’s initial secret key DID, the user’s time update key TID,t, the user’s secret key SKID, and a message M as input and returns a signature σ.(vi)
Verification: taking a signature σ, a message M, a user identity ID, a period t, and the user’s public key PKID as input; the algorithm outputs either “accept” or “reject.”Remark 3.
Thesystem setup, theinitial key extract, and thetime key update algorithms are run by the KGC, while theuser key generation algorithm is run by the user.
There are three types of adversaries in our security notion for RCLS schemes. In the following, we will employ a security game to model security notion for RCLS schemes. The security game describes the interaction between a challenger and an adversary. Before introducing the security game, we first describe capabilities of Type I, Type II, and Type III adversaries, respectively.(i)
Type I adversary (outsider): an adversary of this type does not have access to the system secret key and time secret key, but she/he can replace the public key of any entity with another of her/his own choice.(ii)
Type II adversary (KGC): an adversary of this type is the KGC who knows the system secret key and time secret key. The KGC can produce the initial secret key and time update key of arbitrary identity, but it is forbidden to replace the public key of any identity at any time.(iii)
Type III adversary (revoked user): an adversary of this type used to be a member of the system before being revoked by the system. A revoked user still owns the initial secret key although the system stops issuing the current time update key for her/him.Definition 4.
A RCLS scheme is existential unforgeable against chosen message attack if there is no probabilistic polynomial-time (PPT) adversaryA which has non-negligible advantage in the following security game. (i)
Setup. A challenger B takes a security parameter l and runs thesystem setup algorithm. The challenger B gives the public parameters Params to the adversary A. Meanwhile, if A is of Type II adversary, B gives the system secret key and time secret key to A. Otherwise, the challenger B keeps them for itself.(ii)
Phase 1. The adversaryA may issue thepublic key retrieve,public key replace,initial key extract,time key update,secret key extract, andsigning queries as follows.
(a)
Public key retrieve query (ID). When A issues this query with an identity ID, the challenger B returns the corresponding public key PKID to A.(b)
Public key replace query (ID,PKID′). In such a query, the adversary replaces the public key of the identity ID with PKID′. The challenger records the replacement.(c)
Initial key extract query (ID). When A issues this query with an identity ID, the challenger B runs theinitial key extract algorithm to return the initial secret key DID.(d)
Time key update query (ID,t). When A issues this query with an identity ID in a period t, the challenger B runs thetime key update algorithm to return the time update key TID,t.(e)
Secret key extract query (ID). When A issues this query with an identity ID, the challenger B returns the secret key SKID. Here, the query is forbidden if the identity ID has already appeared in thepublic key replace query.(f)
Signing query (ID,t,M). When A issues this query with (ID,t,M), the challenger B uses the initial secret key DID, the time update key TID,t, and the secret key SKID to run thesigning algorithm to obtain a signature σ on the message M. The challenger B then returns σ to A no matter whether the identity ID appears in thepublic key replace query or not.Note that a Type I adversary can issue all types of queries except theinitial key extract query on ID*; a Type II adversary can issue all types of queries except the queries on public key replace and thesecret key extract query on ID*; a Type III adversary (revoked user) is allowed to issue all types of queries except thetime update key query on (ID*,t*).(iii)
Forgery. The adversary A outputs (ID*,t*,M*,σ*). We say that the adversary A wins this game if the following conditions are satisfied.
(1)
The response of theverification algorithm on (ID*,t*,M*,σ*) is “accept.”(2)
(ID*,t*,M*) has never been submitted during thesigning query process.Remark 5.
Since a Type II adversary owns the system secret key and the time secret key, it is able to generate any initial secret key and time update key. Hence, a Type II adversary does not need to issue the queries on initial secret key and time update key.


## 4. Concrete Revocable Certificateless Signature Scheme

In this section, we describe a concrete revocable certificateless signature scheme that consists of six algorithms.(i)
System setup: the KGC takes a security parameter l as input and returns G1,G2,e^, where e^:G1×G1→G2 is an admissible bilinear map and G1 and G2 are two cyclic groups of sufficiently large prime order p. Then, the KGC sets five collision-resistant hash functions Hu:{0,1}*→{0,1}nu, Ht:{0,1}*→{0,1}nt, Hζ:G1×G1→{0,1}nζ, Hη:G1×G1→{0,1}nη, and Hw:{0,1}*→{0,1}nw, where nu, nt, nζ, nη, and nw are fixed. Furthermore, the KGC randomly chooses five values u′, t′, ζ′, η′, w′∈G1 and five vectors U⃑=(ui), T⃑=(tj), ζ⃑=(ζr), η⃑=(ηs), W⃑=(wk), where ui, tj, ζr, ηs, wk∈G1 for i=1,2,…,nu, j=1,2,…,nt, r=1,2,…,nζ, s=1,2,…,nη, and k=1,2,…,nw. A generator g of G1 and two values α,β∈Zp* are picked. The KGC computes g1∈gα+β∈G1 and randomly chooses g2∈G1 to set the system secret key as g2α and the time secret key as g2β. Then, the public parameters are presented as Params={G1,G2,e^,Hu,Ht,Hζ,Hη,Hw,g,g1,g2,u′,U⃑,t′,T⃑, ζ′,ζ⃑,η′,η⃑,w′,W⃑}.(ii)
Initial key extract: given a user’s identity ID∈{0,1}*, the KGC computes a bit string v=Hu(ID)=(v1,v2,…,vnu). The KGC then chooses a random value rv∈Zp* and uses the system secret key to compute the user’s initial secret key DID=(D1,D2)=(g2α(u′∏i=1nu‍uivi)rv,grv). The KGC transmits DID to the user via a secure channel.(iii)
Time update key: given a user’s identity ID∈{0,1}* and a period t, the KGC computes a bit string vt=Ht(ID,t)=(vt1,vt2,…,vtnt). The KGC then chooses a random value rt∈Zp* and uses the time secret key to compute the user’s time update key TID,t=(T1,T2)=(g2β(t′∏j=1nt‍tjvtj)rt,grt). The KGC transmits TID,t to the user via a public channel.(iv)
User key generation: given a user’s identity ID, this algorithm selects two secret values λ1,λ2∈Zp* and computes the user’s public key PKID=(PK1,PK2)=(gλ1,gλ2). Then, the algorithm first computes two bit strings vu=Hζ=(PK1,PK2)=(vu1,vu2,…,vunζ) and vs=Hη(PK1,PK2)=(vs1,vs2,…,vsnη). Finally, the algorithm uses the selected two secret values to compute the user’s secret key SKID=g2λ1(ζ′∏r=1nζ‍ζrvur)λ1(η′∏s=1nη‍ηsvss)λ2.(v)
Signing: given a message M∈{0,1}*, a signer computes a bit string vm=Hw(M)=(vm1,vm2,…,vmnw). The signer chooses a random value rm∈Zp* and computes grm. The signer uses her/his initial secret key DID=(D1,D2), time update key TID,t=(T1,T2), and secret key SKID to compute a signature on the message M as follows:
(2)σ=(σ1,σ2,σ3,σ4)=D1·T1·SKIDw′∏k=1nw‍wkvmkrm,D2,T2,grm=g2αu′∏i=1nu‍uivirvg2βt′∏j=1nt‍tjvtjrtg2λ1ζ′∏r=1nζ‍ζrvurλ1·η′∏s=1nη‍ηsvssλ2w′∏k=1nw‍wkvmkrm,grv,grt,grm.(vi)
Verification: given a period t, a signature σ=(σ1,σ2,σ3,σ4) on a message M for a signer with an identity ID and the signer’s public key PKID=(PK1,PK2), a verifier first computes five bit strings v=Hu(ID), vt=Ht(ID,t), vu=Hζ(PK1,PK2), vs=Hη(PK1,PK2), and vm=Hw(M). Finally, the verifier checks the following equation:
(3)e^g,σ1=e^g1,g2e^σ2,u′∏i=1nu‍uivie^σ3,t′∏j=1nt‍tjvtj·e^PK1,g2ζ′∏r=1nu‍ζrvure^PK2,η′∏s=1nη‍ηsvss·e^σ3,w′∏k=1nw‍wkvmk.


## 5. Security Analysis

In this section, we establish three theorems to demonstrate that, under the CDH assumption, the proposed RCLS scheme offers existential unforgeability against adaptive chosen-message attacks for Type I, Type II, and Type III adversaries, respectively.Theorem 6.
Under the CDH assumption, the proposed RCLS scheme is secure against Type I adversary (outsider). Concretely, if there is a Type I adversary that has an advantageϵ against the proposed scheme within a running time τ, then we can construct an algorithm to solve the CDH problem with an advantage
(4)ϵ′≥ϵ16qKqS(qE+qS)(nu+1)(nζ+1)(nw+1)
within a running time τ′=τ+O((nu·qE+nt·qU+(nζ+nη)·qK + (nu+nt+nζ+nη+nw)·qS)τ1+(qE+qU+qS+qK)τ2), in which qE,qU, and qS are the numbers of queries on initial key extract, time key update, and signing, respectively, qK is the sum of the numbers of queries on public key replace and secret key extract, and τ1 and τ2 denote the executing time of a multiplication and an exponentiation in G1, respectively.Proof.
Assume that a Type I adversaryA can forge a valid signature for the proposed RCLS scheme. We will construct an algorithm B that solves the CDH problem as follows. Without loss of generality, we assume that there exists a tuple G1,G2,e^, as mentioned in Section 2, and the algorithm B is given g,ga,gb∈G1, where a and b are unknown to B. In order to compute gab, the algorithm B simulates a challenger in the following game. (i)
Setup. A challenger (algorithm) B first sets five collision-resistant hash functions Hu:{0,1}*→{0,1}nu, Ht:{0,1}*→{0,1}nt, Hζ:G1×G1→{0,1}nζ, Hη:G1×G1→{0,1}nη, and Hw:{0,1}*→{0,1}nw, where nu, nt, nζ, nη, and nw are fixed. Note that the employed collision-resistant hash functions are not viewed as random oracles in our security proofs. The challenger B then sets lv=2(qE+qS), lu=qK, and lm=2qS and chooses three integers kv, ku, and km at random, where 0≤kv≤nu, 0≤ku≤nζ, and 0≤km≤nw. We assume that lv(nu+1)<p, lu(nζ+1)<p, and lm(nw+1)<p for the given values of qE, qK, qS, nu, nζ and nw. The challenger B randomly selects the integers x′,x1,…,xnu∈Zlv, y′,y1,…,ynu∈Zp, z′,z1,…,znt∈Zp, a′,a1,…,anζ∈Zlu, b′,b1,…,bnη∈Zp, c′,c1,…,cnw∈Zlm, and d′,d1,…,dnw∈Zp.Now, the challengerB constructs a set of public parameters as follows. The challenger B chooses a value β∈Zp as the time secret key. The challenger B sets g1=gagβ and g2=gb. Furthermore, B computes u′=g2-lvkv+x′gy′and a vector U⃑=(ui), where ui=g2xigyi for 1≤i≤nu; t′=gz′ and a vector T⃑=(tj), where tj=gzj for 1≤j≤nt; ζ′=g2-1-luku+a′ and a vector ζ⃑=(ζr), where ζr=g2ar for 1≤r≤nζ; η′=gb′ and a vector η⃑=(ηs), where ηs=gbs for 1≤s≤nη; w′=g2-lmkm+c′gd′ and a vector W⃑=(wk), where wk=g2ckgdk for 1≤k≤nw. Now, the challenger B has constructed a set of public parameters as Params={G1,G2,e^,Hu,Ht,Hζ,Hη,Hw,g,g1,g2,u′,U⃑,t′,T⃑, ζ′,ζ⃑,η′,η⃑,w′,W⃑}.Before performingQueries and Forgery between the adversary A and the challenger B, we define seven functions J, E, Q, L, F, R, and K by
(5)J(v)=y′+∑i=1nu‍viyi;E(vt)=z′+∑j=1nt‍vtjzj;Q(vs)=b′+∑s=1nη‍vsrbs;L(vm)=d′+∑k=1nw‍vmkdk;F(v)=-lvkv+x′+∑i=1nu‍vixi;R(vu)=-luku+a′+∑r=1nζ‍vurar;K(vm)=-lmkm+c′+∑k=1nw‍vmkck.Here, as before,v=Hu(ID)=(v1,v2,…,vnu) for an identity ID, vt=Ht(ID,t)=(vt1,vt2,…,vnt) for an identity ID in a period t, vu=Hζ(PK1,PK2)=(vu1,vu2,…,vunζ) and vs=Hη(PK1,PK2)=(vs1,vs2,…,vsnη) for a public key PKID=(PK1,PK2), and vm=Hw(M)=(vm1,vm2,…,vmnw) for a message M.Finally, for the cumbersome notations defined above, we conclude with five relations to which will be referred frequently in the sequel; namely,(6)u′∏i=1nu‍uivi=g2F(v)gJ(v);t′∏j=1nt‍tjvtj=gE(vt);ζ′∏r=1nζ‍ζrvur=g2R(vu)-1;η′∏s=1nη‍ηsvss=gQ(vs);w′∏k=1nw‍wkvmk=g2K(vm)gL(vm).(ii)
Queries. The challenger B maintains a list L of tuples of the form ID,λ1,λ2,PKID,SKID. Initially the list is empty. The adversary A may make a number of queries in an adaptive manner as follows.
(a)
Public key retrieve query (ID): upon receiving a query for the public key of an identity ID, the challenger B responds to the query as follows.
(1)
IfID appears in the list L, the challenger B responds with the corresponding PKID.(2)
IfID does not appear in the list L, the challenger B selects two secret values λ1,λ2∈Zp*, sets the public key PKID=(PK1,PK2)=(gλ1,gλ2), and then computes vu=Hζ(PK1,PK2)=(vu1,vu2,…,vunζ), vs=Hη(PK1,PK2)=(vs1,vs2,…,vsnη), and the secret key SKID=g2λ1(ζ′∏r=1nζ‍ζrvur)λ1(η′∏s=1nη‍ηsvss)λ2. The challenger B adds the tuple ID,λ1,λ2,PKID,SKID in the list L and returns PKID as the query output.(b)
Public key replace query (ID,PKID′): upon receiving a query to replace the public key of an identity ID, the challenger B accesses the tuple ID,λ1,λ2,PKID,SKID in the list L. If ID appears in the list L, the challenger B replaces PKID with PKID′. If ID does not appear in the list L, the challenger adds the tuple ID,⊥,⊥,PKID′,⊥ in the list L.(c)
Initial key extract query (ID): upon receiving a query for the initial secret key of an identity ID, the challenger B first sets v=Hu(ID), and then computes F(v) and J(v). If F(v)=0, the challenger B aborts. Otherwise, the challenger B chooses a random value rv∈Zp and responds with the initial secret key DID generated by
(7)DID=(D1,D2)=ga-Jv/Fvg2FvgJvrv,ga-1/Fvgrv.Here,DID=(D1,D2) is indeed a valid initial secret key since, by the first equality in (6),
(8)D1=ga-J(v)/F(v)g2FvgJva/F(v)·g2FvgJvrv-a/F(v)=ga-J(v)/F(v)g2FvgJva/F(v)·u′∏i=1nu‍uivirv-a/Fv=g2au′∏i=1nu‍uivirv′;D2=ga-1/F(v)grv=grv-a/F(v)=grv′,whererv′=rv-a/F(v).(d)
Time key update query (ID,t): upon receiving a query for the time update key of an identity ID in a period t, the challenger B first sets vt=Ht(ID,t) and then computes E(vt). The challenger B chooses a random rt∈Zp and uses the time secret key β to compute the time update key as follows:
(9)TID,t=(T1,T2)=(g2βgEvtrt,grt)=g2βt′∏j=1nt‍tjvtjrt,grt.(e)
Secret key extract query (ID): upon receiving a query for the secret key of an identity ID, the challenger B accesses the tuple ID,λ1,λ2,PKID,SKID in the list L. If ID appears in the list L, the challenger B responds with SKID. If ID does not appear in the list L, the challenger B runsuser key generation algorithm to add the tuple ID,λ1,λ2,PKID,SKID in the list L and responds with SKID.(f)
Signing query (ID,t,M,PKID): consider a query for a message M, an identity ID, a period t, and a public key PKID=(PK1,PK2). The challenger B first sets v=Hu(ID), vt=Ht(ID,t), vu=Hζ(PK1,PK2), vs=Hη(PK1,PK2), and vm=Hw(M). B then computes F(v), J(v), E(vt), R(vu), Q(vs), K(vm), and L(vm). If K(vm)=0, the challenger B reports failure and terminates. Otherwise, the challenger B considers the following two cases.Case  1: assume that the identity ID has previously appeared in thepublic key replace query. If F(v)≠0, the challenger B can compute the initial secret key DID=(D1,D2) as in theinitial key extract query. In addition, the challenger B computes the time update key TID,t=(T1,T2) as in thetime key update query. The challenger B then chooses a random value rm∈Zp* and responds whit the signature
(10)σ=(σ1,σ2,σ3,σ4)=g2KvmgLvmrmD1T1PK1-L(vm)/K(vm)R(vu)·PK2Qvs×g2KvmgLvmrm,D2,T2,PK1-Rvu/Kvmgrm.Note thatσ is indeed a valid signature since K(vm)≠0 and, by the equalities in (6),
(11)σ1=D1T1gλ1-L(vm)/K(vm)R(vu)·gλ2Q(vs)g2KvmgLvmrm=D1T1g2λ1g2Rvu-1λ1gQvsλ2·g2KvmgLvmrm-λ1Rvu/Kvm=D1T1g2λ1ζ′∏r=1nζ‍ζrvurλ1η′∏s=1nη‍ηsvssλ2·w′∏k=1nw‍wkvmkrm′;σ2=D2;σ3=T2;σ4=g-λ1R(vu)/K(vm)grm=grm′,whererm′=rm-λ1R(vu)/K(vm).On the other hand, ifF(v)=0, the challenger B first computes the time update key TID,t=(T1,T2) as in thetime key update query. Then, the challenge B chooses two random values rv,rm∈Zp* and responds with the signature
(12)σ=(σ1,σ2,σ3,σ4)=ga-Lvm/Kvmg2FvgJvrv×T1PK1-L(vm)/K(vm)R(vu)·PK2Q(vs)g2KvmgLvmrm,grv,T2,g1-1/K(vm)PK1-R(vu)/K(vm)grmg2FvgJvrv.Note thatσ is also a valid signature since, by (6),
(13)σ1=ga-Lvm/Kvmg2FvgJvrv×T1gλ1-L(vm)/K(vm)R(vu)·gλ2Q(vs)g2KvmgLvmrm=g2ag2FvgJvrvT1g2λ1g2Rvu-1λ1gQvsλ2·g2KvmgLvmrm-a+λ1Rvu/Kvm=g2au′∏i=1nu‍uivirvT1g2λ1ζ′∏r=1nζ‍ζrvurλ1·η′∏s=1nη‍ηsvssλ2w′∏k=1nw‍wkvmkrm′;σ2=grv;σ3=T2;σ4=ga-1/K(vm)gλ1-R(vu)/K(vm)grm=grm-a+λ1R(vu)/K(vm)=grm′,whererm′=rm-a+λ1R(vu)/K(vm).Case  2: assume that the identity ID has not previously appeared in thepublic key replace query. The challenger B computes the time update key TID,t=(T1,T2) as in thetime key update query. If F(v)≠0, the challenger B can compute the initial secret key (D1,D2) as in theinitial key extract query and accesses the list L to obtain the corresponding secret key SKID. The challenger B chooses a random value rm∈Zp* and then responds with the signature
(14)σ=D1T1SKIDw′∏k=1nw‍wkvmkrm,D2,T2,grm.IfF(v)=0, then B chooses two random values rv,rm∈Zp* and responds with the signature
(15)σ=ga-Lvm/Kvmu′∏i=1nu‍uivirvT1SKID·w′∏k=1nw‍wkvmkrm,grv,T2,g1-1/K(vm)grm.(iii)
Forgery. Assume that the adversary A generates a valid signature σ*=(σ1,σ2,σ3,σ4) for ID* on M* in t*, where ID*, t*, and M* are the target identity, period, and message, respectively. The challenger B first accesses to the list L to obtain PKID*=(PK1,PK2). The challenger B then computes v*=Hu(ID*), vt*=Ht(ID*,t*), vu*=Hζ(PK1,PK2), vs*=Hη(PK1,PK2), vm*=Hw(M*), F(v*), J(v*), E(vt*), R(vu*), Q(vs*), L(vm*), and K(vm*). If F(v*)≠0, R(vu*)≠0, or K(vm*)≠0, the challenger B aborts. Otherwise, that is, when F(v*)=R(vu*)=K(vm*)=0, the challenger B, by using (6), computes gab as follows:
(16)σ1σ2Jv*σ3Evt*PK2Qvs*σ4Lvm*g2β=g2au′∏i=1nu‍uivirvg2βt′∏j=1nt‍tjvtjrtg2λ1ζ′∏r=1nζ‍ζrvurλ1grvJ(v*)grtE(vt*)gλ2Q(vs*)grmL(vm*)g2β·η′∏s=1nη‍ηsvssλ2w′∏k=1nw‍wkvmkrm=g2ag2Fv*gJv*rvgEvt*rtg2λ1g2Rvu*-1λ1grvJ(v*)grtE(vt*)gλ2Q(vs*)grmL(vm*)·gQvs*λ2g2Kvm*gLvm*rm=g2asinceFv*=Qvs*=Kvm*=0=gab.Thus, the challengerB resolves the computational Diffie-Hellman (CDH) problem.
Next, we proceed to the probability analysis for the simulation above. Note that if the simulation aborts, then the CDH problem will be unable to be computed by the challenger. InForge phase, the adversary can generate a signature if the challenger can correctly response the adversary’s queries in Phase 1 and do not abort in the security game. If the signature is valid, the challenger can use it to solve the CDH problem. Thus, the probability of the challenger not aborting in the security game is equal to the probability of solving the CDH problem. Hence, we list the events that the challenger B does not abort during the simulation process. (1)
In the phase ofinitial key extract query: if F(v)≠0, the challenger B can correctly answer queries without aborting.(2)
In the phase ofsigning query: if K(vm)≠0, the challenger B can correctly respond queries without aborting.(3)
In the phase offorgery: if F(v*)=R(vu*)=K(vm*)=0, the challenger B can perform the simulation without aborting.
LetqI be the number of identities appearing in eitherinitial key extract queries orsigning queries not involving the challenge identity. In addition, let qT be the number of identities with the period appearing in thetime key update queries and let qM be the number of messages in thesigning queries involving the challenge identity. Clearly, we will have qI<qE+qS, qT<qU and qM<qS. To simplify the analysis, we define the events Ai:F(v)≠0 mod lv for the ith query (1≤i≤qI), A*:F(v*)=0 mod p, Bk:K(vm)≠0 mod lm for the kth query (1≤k≤qM), B*:K(vm*)=0 mod p, and C*:R(vu*)=0 mod p. From the above analysis, the probability of the challenger B not aborting is
(17)Pr⁡¬abort≥Pr⁡⋀i=1qIAi∧A*∧⋀k=1qMBk∧B*∧C*=Pr⁡A*Pr⁡⋀i=1qIAi∣A*Pr⁡B*×Pr⁡⋀k=1qMBk∣B*Pr⁡[C*].
Note that, ifF(v)=0 mod lv, there will be a unique choice of kv with 0≤kv≤nu such that F(v)=0. Since kv,x′,x1,…,xnu are chosen randomly, we obtain that
(18)Pr⁡A*=Pr⁡[F(v*)=0]≥Pr⁡[F(v*)=0∧F(v*)=0mod⁡lv]=Pr⁡[F(v*)=0mod⁡lv]·Pr⁡⁡Fv*=0∣Fv*=0mod⁡lv=1lv1nu+1.
By similar arguments, we have
(19)Pr⁡B*=Pr⁡Kvm*=0≥1lm1nw+1,Pr⁡[C*]=Pr⁡[R(vu*)=0]≥1lu1nζ+1.
We also have that
(20)Pr⁡⋀i=1qIAi∣A*=1-Pr⁡⋁i=1qI¬Ai∣A*≥1-∑i=1qI‍Pr⁡[¬Ai∣A*]=1-qIlv≥1-qE+qSlv
and, similarly,
(21)Pr⁡⋀k=1qMBk∣B*=1-qMlm≥1-qSlm.
Hence, we can obtain that
(22)Pr⁡⋀i=1qIAi∧A*=Pr⁡[A*]·Pr⁡⋀i=1qIAi∣A*≥1lv1nu+11-qE+qSlv,Pr⁡[⋀k=1qMBk∧B*]≥1lm1nw+11-qSlm.
We have set lv=2(qE+qS), lu=qK, and lm=2qS in the setup at the beginning of the proof, and so the resulting probability of the challenger B not aborting is
(23)Pr⁡¬abort≥Pr⁡⋀i=1qIAi∧A*∧⋀k=1qMBk∧B*∧C*=Pr⁡A*Pr⋀i=1qIAi∣A*Pr⁡⁡[B*]×Pr⁡⋀k=1qMBk∣B*Pr⁡C*≥14(qE+qS)(nu+1)4qS(nw+1)qK(nζ+1)=116qKqS(qE+qS)(nu+1)(nζ+1)(nw+1).
Since the adversaryA that has an advantage ϵ against the proposed certificateless signature scheme, the challenger B has an advantage
(24)ϵ′≥ϵ16qKqS(qE+qS)(nu+1)(nζ+1)(nw+1)
to solve the CDH problem.
For the queries, we observe that there areO(nu) multiplications and O(1) exponentiations in theinitial key extract queries. There are O(nt) multiplications and O(1) exponentiations in thetime update key queries. There are O(nζ) multiplications and O(1) exponentiations in both thepublic key retrieve and thesecret key extract queries. Moreover, there are O(nu+nt+nζ+nη+nw) multiplications and O(1) exponentiations in thesigning queries. So we have τ′=τ+O((nu·qE+nt·qU+(nζ+nη)·qK+(nu+nt+nζ+nη+nw)·qS)·τ1 + (qE+qU+qK+qS)·τ2), where τ1 and τ2 denote the executing time of a multiplication in G1 and an exponentiation in G1, respectively.Theorem 7.
Under the CDH assumption, the proposed RCLS scheme is secure against Type II adversary. Concretely, if there is a Type II adversary (KGC) that has an advantageϵ against the proposed scheme within a running time τ, then we can construct an algorithm to solve the CDH problem with an advantage
(25)ϵ′≥ϵ4qKqS(nw+1)
within a running time τ′=τ+O(((nζ+nη)·qK+(nu+nt+nζ+nη+nw)·qS)·τ1 + (qK+qS)·τ2), in which qK and qS are the numbers of queries onsecret key extract andsigning, respectively, and τ1 and τ2 denote the executing time of a multiplication and an exponentiation in G1, respectively.Proof.
We assume that a Type II adversaryA can forge a valid signature for the proposed RCLS scheme. We will construct an algorithm B that solves the CDH problem as follows. Without loss of generality, we assume that there exists a tuple G1,G2,e^, as mentioned in Section 2, and the algorithm B is given g,ga,gb∈G1, where a and b are unknown to B. In order to compute gab, the algorithm B simulates a challenger in the following game. (i)
Setup. A challenger (algorithm) B first sets five collision-resistant hash functions Hu:{0,1}*→{0,1}nu, Ht:{0,1}*→{0,1}nt, Hζ:G1×G1→{0,1}nζ, Hη:G1×G1→{0,1}nη, and Hw:{0,1}*→{0,1}nw, where nu, nt, nζ, nη, and nw are fixed. Note that the employed collision-resistant hash functions are not viewed as random oracles in our security proofs. The challenger B then sets lm=2qS and chooses an integer km at random, where 0≤km≤nw. We assume that lm(nw+1)<p for the given values of qS and nw. The challenger B randomly selects the integers: z′,z1,…,znu∈Zp, x′,x1,…,xnt∈Zp, a′,a1,…,anζ∈Zp, b′,b1,…,bnη∈Zp, c′,c1,…,cnw∈Zlm, and d′,d1,…,dnw∈Zp.Now, the challengerB constructs a set of public parameters as follows. The challenger B chooses two values α,β∈Zp. The challenger B sets g1=gα+β and g2=gb. Furthermore, B computes and sends the system secret key g2α and time secret key g2β to the adversary A. Also, B computes u′=gz′and a vector U⃑=(ui), where ui=gzi for 1≤i≤nu; t′=gx′ and a vector T⃑=(tj), where tj=gxj for 1≤j≤nt; ζ′=g2a′ and a vector ζ⃑=(ζr), where ζr=g2ar for 1≤r≤nζ; η′=gb′ and a vector η⃑=(ηs), where ηs=gbs for 1≤s≤nη; w′=g2-lmkm+c′gd′ and a vector W⃑=(wk), where wk=g2ckgdk for 1≤k≤nw. Now, the challenger B has constructed a set of public parameters as Params={G1,G2,e^,Hu,Ht,Hζ, Hη,Hw,g,g1,g2,u′,U⃑,t′,T⃑,ζ′,ζ⃑,η′,η⃑,w′,W⃑}.Before performingQueries and Forgery between the adversary A and the challenger B, we define six functions E, F, R, Q, K, and L by
(26)E(v)=z′+∑i=1nu‍vizi;F(vt)=x′+∑j=1nt‍vtjxj;R(vu)=a′+∑r=1nζ‍vurar;Q(vs)=b′+∑s=1nη‍vsrbs;K(vm)=-lmkm+c′+∑k=1nw‍vmkck;L(vm)=d′+∑k=1nw‍vmkdk.Here, as before,v=Hu(ID)=(v1,v2,…,vnu) for an identity ID, vt=Ht(ID,t)=(vt1,vt2,…,vnt) for an identity ID in a period t, vu=Hζ(PK1,PK2)=(vu1,vu2,…,vunζ) and vs=Hη(PK1,PK2)=(vs1,vs2,…,vsnη) for a public key PKID=(PK1,PK2), and vm=Hw(M)=(vm1,vm2,…,vmnw) for a message M.Finally, for the cumbersome notations defined above, we conclude with four relations to which will be referred frequently in the sequel; namely,(27)u′∏i=1nu‍uivi=gE(v);t′∏j=1nt‍tjvtj=gF(vt);ζ′∏r=1nζ‍ζrvur=g2Rvu;η′∏s=1nη‍ηsvss=gQ(vs);w′∏k=1nw‍wkvmk=g2K(vm)gL(vm).(ii)
Queries. The challenger B maintains a list L of tuples of the form ID,λ1,λ2,PKID,SKID. Initially the list is empty. First, without loss of generality, the challenger B picks a target identity ID′, selects a secret value λ2∈Zp*, and sets the public key PKID′=(PK1,PK2)=(ga,gλ2). Then, the challenger B adds the tuple ID′,⊥,λ2,PKID′,⊥ in the list L. The adversary A may make a number of queries in an adaptive manner as follows.
(a)
Public key retrieve query (ID): upon receiving a query for the public key of an identity ID, the challenger B responds to the query as follows.
(1)
IfID appears in the list L, the challenger B responds with the corresponding PKID.(2)
IfID does not appear in the list L, the challenger B selects two secret values λ1,λ2∈Zp*, sets the public key PKID=(PK1,PK2)=(gλ1,gλ2), and then computes vu=Hζ(PK1,PK2)=(vu1,vu2,…,vunζ), vs=Hη(PK1,PK2)=(vs1,vs2,…,vsnη) and the secret key SKID=g2λ1(ζ′∏r=1nζ‍ζrvur)λ1(η′∏s=1nη‍ηsvss)λ2. The challenger B adds the tuple ID,λ1,λ2,PKID,SKID in the list L and returns PKID as the query output.(b)
Secret key extract query (ID): consider such a query along with an identity ID. If ID=ID′, the challenger B aborts. If ID≠ID′ and ID appears in the list L, the challenger B accesses the tuple ID,λ1,λ2,PKID,SKID in the list L and responds with SKID. If ID≠ID′ and ID does not appear in the list L, the challenger B runs theuser key generation algorithm to add the tuple ID,λ1,λ2,PKID,SKID in the list L and then responds with SKID so obtained.(c)
Signing query (ID,t,M,PKID): consider a query for a message M, an identity ID, a period t, and a public key PKID=(PK1,PK2). The challenger B first sets v=Hu(ID), vt=Ht(ID,t), vu=Hζ(PK1,PK2), vs=Hη(PK1,PK2), and vm=Hw(M). B then computes E(v), F(vt), R(vu), Q(vs), K(vm), and L(vm). If K(vm)=0, the challenger B reports failure and terminates. Otherwise, the challenger B considers the following two cases.Case  1: if ID=ID′, the challenger B runs theinitial key extract andtime key update algorithms to obtain the initial secret key DID=(D1,D2) and the time update key TID,t=(T1,T2). The challenger B chooses a random value rm∈Zp* and then responds with the signature
(28)σ=(σ1,σ2,σ3,σ4)=D1T1PK1-L(vm)/K(vm)(1+R(vu))·PK2Q(vs)g2KvmgLvmrm,D2,T2,PK1-(1+R(vu))/K(vm)grm.Note thatσ is indeed a valid signature since K(vm)≠0 and, by the equalities in (27),
(29)σ1=D1T1ga-L(vm)/K(vm)(1+R(vu))gλ2Q(vs)·g2KvmgLvmrm=D1T1g2ag2RvuagQvsλ2·g2KvmgLvmrm-a(1+R(vu))/K(vm)=D1T1g2aζ′∏r=1nζ‍ζrvuraη′∏s=1nη‍ηsvssλ2·w′∏k=1nw‍wkvmkrm′;σ2=D2;σ3=T2;σ4=ga-(1+R(vu))/K(vm)grm=grm′,whererm′=rm-a(1+R(vu))/K(vm).Case  2: if ID≠ID′, the challenger B runs theinitial key extract andtime key update algorithms to obtain the initial secret key DID=(D1,D2) and the time update key TID,t=(T1,T2). Then, B accesses to the list L to obtain the secret key SKID. The challenger B chooses a random value rm∈Zp* and then responds with the signature
(30)σ=(σ1,σ2,σ3,σ4)=(D1T1SKIDw′∏k=1nw‍wkvmkrm,D2,T2,grm).(iii)
Forgery. Assume that the adversary A generates a valid signature σ*=(σ1,σ2,σ3,σ4) for ID* on M* in t*, where ID*, t*, and M* are the target identity, period, and message, respectively. If ID≠ID′, the challenger B reports failure and terminates. If ID=ID′, the challenger B first accesses to the list L to obtain PKID*=(PK1,PK2). The challenger B then computes v*=Hu(ID*), vt*=Ht(ID*,t*), vu*=Hζ(PK1,PK2), vs*=Hη(PK1,PK2), vm*=Hw(M*), E(v*), F(vt*), R(vu*), Q(vs*), L(vm*), and K(vm*). If K(vm*)≠0, the challenger B aborts. Otherwise, that is, when K(vm*)=0, the challenger B, by using (27), computes (gab)1+R(vu*) as follows:
(31)V=σ1g2α+βσ2Ev*σ3Fvt*PK2Rvu*σ4Lvm*=g2α+βu′∏i=1nu‍uivirvt′∏j=1nt‍tjvtjrtg2aζ′∏r=1nζ‍ζrvurag2α+βgrvE(v*)grtF(vt*)gλ2Q(vs*)grmL(vm*)·η′∏s=1nη‍ηsvssλ2w′∏k=1nw‍wkvmkrm=gEv*rvgFvt*rtg2ag2Rvu*agrvE(v*)grtF(vt*)gλ2Q(vs*)grmL(vm*)·gQvs*λ2g2Kvm*gLvm*rm=g2a1+Rvu*(sinceK(vm*)=0)=gab1+R(vu*), where α and β have been chosen in the setup at the beginning of the proof. Finally, by computing V(1+R(vu*))-1, we obtain the value gab. Thus, the challenger B resolves the computational Diffie-Hellman (CDH) problem.
Next, we proceed to the probability analysis for the simulation above. For convenience, we list the events that the challengerB does not abort during the simulation process. (1)
In the phase ofsigning query: if K(vm)≠0, the challenger B can correctly respond to queries without aborting.(2)
In the phase offorgery: if ID*=ID′ and K(vm*)=0, the challenger B can perform the simulation without aborting. Let qM be the number of messages in thesigning queries involving the challenge identity. Clearly, we will have qM<qS. To simplify the analysis, we define the events Bk:K(vm)≠0 for the kth query (1≤k≤qM), B*:K(vm*)=0, C*:ID*=ID′. From the analysis above, the probability of the challenger B not aborting is
(32)Pr⁡¬abort≥Pr⁡⋀k=1qMBk∧B*∧C*=Pr⁡[B*]·Pr⁡⋀k=1qMBk∣B*·Pr⁡[C*].
The analysis of probability above is similar to Theorem6. Here, we can obtain that
(33)Pr⁡⋀k=1qMBk∧B*=Pr⁡[B*]·Pr⁡⋀k=1qMBk∣B*≥1lm1nw+11-qSlm.
Since we have setlm=2qS, the resulting probability of the challenger B not aborting is
(34)Pr⁡¬abort≥Pr⁡[B*]·Pr⁡⋀k=1qMBk∣B*·Pr⁡[C*]≥14qKqS(nw+1),
by noting that Pr⁡[C*]=1/qK.
Since the adversaryA has an advantage ϵ against the proposed certificateless signature scheme, the challenger B has an advantage
(35)ϵ′≥ϵ4qKqS(nw+1)
to solve the CDH problem.
For the queries, we observe that there areO(nζ+nη) multiplications and O(1) exponentiations insecret key extract queries. Moreover, there are O(nu+nt+nζ+nη+nw) multiplications and O(1) exponentiations in thesigning queries. So we have τ′=τ + O(((nζ+nη)·qK+(nu+nt+nζ+nη+nw)·qS)τ1+(qK+qS)τ2), where τ1 and τ2 denote the executing time of a multiplication and an exponentiation in G1, respectively.Theorem 8.
Under the CDH assumption, the proposed RCLS scheme is secure against Type III adversary (revoked user). Concretely, if there is a revoked user that has an advantageϵ against the proposed scheme within a running time τ, then we can construct an algorithm to solve the CDH problem with an advantage
(36)ϵ′≥ϵ16qKqS(qU+qS)(nt+1)(nζ+1)(nw+1)
within a running time τ′=τ+O((nu·qE+nt·qU+(nζ+nη)·qK + (nu+nt+nζ+nη+nw)·qS)τ1+(qE+qU+qS+qK)τ2), in which qE, qU, and qS are the numbers of queries on initial key extract, time key update, and signing, respectively, qK is the sum of the numbers of queries on public key replace and secret key extract, and τ1 and τ2 denote the executing time of a multiplication and an exponentiation in G1, respectively.Proof.
Assume that a revoked userA can forge a valid signature for the proposed RCLS scheme. We will construct an algorithm B that solves the CDH problem as follows. Without loss of generality, we assume that there exists a tuple G1,G2,e^, as mentioned in Section 2, and the algorithm B is given g,ga,gb∈G1, where a and b are unknown to B. In order to compute gab, the algorithm B simulates a challenger in the following game. (i)
Setup. A challenger (algorithm) B first sets five collision-resistant hash functions Hu:{0,1}*→{0,1}nu, Ht:{0,1}*→{0,1}nt, Hζ:G1×G1→{0,1}nζ, Hη:G1×G1→{0,1}nη, and Hw:{0,1}*→{0,1}nw, where nu, nt, nζ, nη, and nw are fixed. Note that the employed collision-resistant hash functions are not viewed as random oracles in our security proofs. The challenger B then sets lt=2(qU+qS), lu=qK and lm=2qS, and chooses three integers kt, ku, and km at random, where 0≤kt≤nt, 0≤ku≤nζ, and 0≤km≤nw. We assume that lt(nt+1)<p, lu(nζ+1)<p, and lm(nw+1)<p for the given values of qU, qK, qS, nt, nζ, and nw. The challenger B randomly selects the integers: z′,z1,…,znu∈Zp, x′,x1,…,xnt∈Zlt, y′,y1,…,ynt∈Zp, a′,a1,…,anζ∈Zlu, b′,b1,…,bnη∈Zp, c′,c1,…,cnw∈Zlm, and d′,d1,…,dnw∈Zp.Now, the challengerB constructs a set of public parameters as follows. The challenger B chooses a value α∈Zp as the system secret key. The challenger B sets g1=gαga and g2=gb. Furthermore, B computes u′=gz′ and a vector U⃑=(ui), where ui=gzj for 1≤i≤nu; t′=g2-ltkt+x′gy′ and a vector T⃑=(tj), where tj=g2xigyi for 1≤j≤nt; ζ′=g2-1-luku+a′ and a vector ζ⃑=(ζr), where ζr=g2ar for 1≤r≤nζ; η′=gb′ and a vector η⃑=(ηs), where ηs=gbs for 1≤s≤nη; w′=g2-lmkm+c′gd′ and a vector W⃑=(wk), where wk=g2ckgdk for 1≤k≤nw. Now, the challenger B has constructed a set of public parameters as Params={G1,G2,e^,Hu,Ht,Hζ,Hη,Hw,g,g1,g2,u′,U⃑,t′,T⃑, ζ′,ζ⃑,η′,η⃑,w′,W⃑}.Before performingQueries and Forgery between the adversary A and the challenger B, we define seven functions E, J, Q, L, F, R, and K by
(37)Ev=z′+∑i=1nu‍vizi;Jvt=y′+∑j=1nt‍vtjyj.Q(vs)=b′+∑s=1nη‍vsrbs;L(vm)=d′+∑k=1nw‍vmkdk;F(vt)=-ltkt+x′+∑j=1nt‍vtjxj;R(vu)=-luku+a′+∑r=1nζ‍vurar;Kvm=-lmkm+c′+∑k=1nw‍vmkck.Here, as before,v=Hu(ID)=(v1,v2,…,vnu) for an identity ID, vt=Ht(ID,t)=(vt1,vt2,…,vnt) for an identity ID in a period t, vu=Hζ(PK1,PK2)=(vu1,vu2,…,vunζ) and vs=Hη(PK1,PK2)=(vs1,vs2,…,vsnη) for a public key PKID=(PK1,PK2), and vm=Hw(M)=(vm1,vm2,…,vmnw) for a message M.Finally, for the cumbersome notations defined above, we conclude with four relations to which will be referred frequently in the sequel; namely,(38)u′∏i=1nu‍uivi=gEv;t′∏j=1nt‍tjvtj=g2F(vt)gJ(vt);ζ′∏r=1nζ‍ζrvur=g2Rvu-1;η′∏s=1nη‍ηsvss=gQ(vs);w′∏k=1nw‍wkvmk=g2K(vm)gL(vm).(ii)
Queries. The challenger B maintains a list L of tuples of the form ID,λ1,λ2,PKID,SKID. Initially the list is empty. The adversary A may make a number of queries in an adaptive manner as follows.
(a)
Public key retrieve query (ID): to respond to the queries, the challenger B responds to the queries as in Theorem 6.(b)
Public key replace query (ID,PKID′): to respond to the queries, the challenger B responds to the queries as in Theorem 6.(c)
Initial key extract query (ID): upon receiving a query for the initial secret key of an identity ID, the challenger B first sets v=Hu(ID) and then computes E(v). The challenger B chooses a random rv∈Zp and uses the system secret key α to compute the initial secet key as follows:
(39)DID=(D1,D2)=(g2αgEvrv,grv)=(g2αu′∏i=1nu‍uivirv,grv).(d)
Time key update query (ID,t): upon receiving a query for the time update key of an identity ID in a period t, the challenger B first sets vt=Ht(ID,t), and then computes F(vt) and J(vt). If F(vt)=0, the challenger B aborts. Otherwise, the challenger B chooses a random value rt∈Zp and responds with the time update key TID,t generated by
(40)TID,t=(T1,T2)=ga-Jvt/Fvtg2FvtgJvtrt,ga-1/Fvtgrt.Here,TID,t=(T1,T2) is indeed a valid time update key since, by the first equality in (38),
(41)T1=ga-Jvt/Fvtg2FvtgJvta/Fvt·g2FvtgJvtrt-a/Fvt=ga-Jvt/Fvtg2FvtgJvta/Fvt·t′∏j=1nt‍tjvtjrt-a/Fvt=g2at′∏j=1nt‍tjvtjrt′;D2=ga-1/F(vt)grt=grt-a/F(vt)=grt′,wherert′=rt-a/F(vt).(e)
Secret key extract query (ID): to respond to the queries, the challenger B responds to the queries as in Theorem 6.(f)
Signing query (ID,t,M,PKID): consider a query for a message M, an identity ID, a period t, and a public key PKID=(PK1,PK2). The challenger B first sets v=Hu(ID), vt=Ht(ID,t), vu=Hζ(PK1,PK2), vs=Hη(PK1,PK2), and vm=Hw(M). B then computes E(v), F(vt), J(vt), R(vu), Q(vs), K(vm), and L(vm). If K(vm)=0, the challenger B reports failure and terminates. Otherwise, the challenger B considers the following two cases.Case  1: assume that the identity ID has previously appeared in thepublic key replace query. If F(vt)≠0, the challenger B can compute the time update key TID,t=(T1,T2) as in thetime key update query. In addition, the challenger B computes the initial secret key DID=(D1,D2) as in theinitial key extract query. The challenger B then chooses a random value rm∈Zp* and responds with the signature
(42)σ=σ1,σ2,σ3,σ4=D1T1PK1-Lvm/KvmRvu·PK2Qvsg2KvmgLvmrm,D2,T2,PK1-R(vu)/K(vm)grm.Note thatσ is indeed a valid signature since K(vm)≠0 and, by the equalities in (38),
(43)σ1=D1T1gλ1-Lvm/KvmRvu·gλ2Qvsg2KvmgLvmrm=D1T1g2λ1g2Rvu-1λ1gQvsλ2·g2KvmgLvmrm-λ1Rvu/Kvm=D1T1g2λ1ζ′∏r=1nζ‍ζrvurλ1η′∏s=1nη‍ηsvssλ2·w′∏k=1nw‍wkvmkrm′;σ2=D2;σ3=T2;σ4=g-λ1R(vu)/K(vm)grm=grm′,whererm′=rm-λ1R(vu)/K(vm).On the other hand, ifF(vt)=0, the challenger B first computes the initial secret key DID=(D1,D2) as in theinitial key extract query. Then, the challenge B chooses two random values rt,rm∈Zp* and responds with the signature
(44)σ=σ1,σ2,σ3,σ4=D1ga-Lvm/Kvmg2FvtgJvtrt×PK1-Lvm/KvmRvu·PK2Qvsg2KvmgLvmrm,D2,grt,g1-1/K(vm)PK1-R(vu)/K(vm)grmg2FvtgJvtrt.Note thatσ is also a valid signature since, by (38),
(45)σ1=D1ga-Lvm/Kvmg2FvtgJvtrt×gλ1-Lvm/KvmRvu·gλ2Qvsg2KvmgLvmrm=D1g2ag2FvtgJvtrtg2λ1g2Rvu-1λ1gQvsλ2·g2KvmgLvmrm-a+λ1Rvu/Kvm=D1g2at′∏j=1nt‍tjvtjrtg2λ1ζ′∏r=1nζ‍ζrvurλ1·η′∏s=1nη‍ηsvssλ2w′∏k=1nw‍wkvmkrm′;σ2=D2;σ3=grt;σ4=ga-1/Kvmgλ1-Rvu/Kvmgrm=grm-a+λ1R(vu)/K(vm)=grm′,whererm′=rm-a+λ1R(vu)/K(vm).Case  2: assume that the identity ID has not previously appeared in thepublic key replace query. The challenger B computes the initial secret key DID=(D1,D2) as in theinitial key extract query. If F(vt)≠0, the challenger B can compute the time update key TID,t=(T1,T2) as in theinitial key extract query and accesses the list L to obtain the corresponding secret key SKID. The challenger B chooses a random value rm∈Zp* and then responds with the signature
(46)σ=(D1T1SKIDw′∏k=1nw‍wkvmkrm,D2,T2,grm).IfF(vt)=0, then B chooses two random values rt,rm∈Zp* and responds with the signature
(47)σ=D1ga-Lvm/Kvmt′∏j=1nt‍tjvtjrtSKID·w′∏k=1nw‍wkvmkrm,D2,grt,g1-1/K(vm)grm.(iii)
Forgery. Assume that the adversary A generates a valid signature σ*=(σ1,σ2,σ3,σ4) for ID* on M* in t*, where ID*, t*, and M* are the target identity, period, and message, respectively. The challenger B first accesses the list L to obtain PKID*=(PK1,PK2). The challenger B then computes v*=Hu(ID*), vt*=Ht(ID*,t*), vu*=Hζ(PK1,PK2), vs*=Hη(PK1,PK2), vm*=Hw(M*), E(v*), F(vt*), J(vt*), R(vu*), Q(vs*), L(vm*), and K(vm*). If F(vt*)≠0, R(vu*)≠0, or K(vm*)≠0, the challenger B aborts. Otherwise, that is, when F(vt*)=R(vu*)=K(vm*)=0, the challenger B, by using (38), computes gab as follows:
(48)σ1σ2Ev*σ3Jvt*PK2Qvs*σ4Lvm*g2α=g2αu′∏i=1nu‍uivirvg2at′∏j=1nt‍tjvtjrtg2λ1ζ′∏r=1nζ‍ζrvurλ1grvEv*grtJvt*gλ2Qvs*grmLvm*g2α·η′∏s=1nη‍ηsvssλ2w′∏k=1nw‍wkvmkrm=g2Ev*rvg2agFvt*gJvt*rtg2λ1g2Rvu*-1λ1grvEv*grtJvt*gλ2Qvs*grmLvm*·gQvs*λ2g2Kvm*gLvm*rm=g2asinceFvt*=Qvs*=Kvm*=0=gab.Thus, the challengerB resolves the computational Diffie-Hellman (CDH) problem.
The analysis is similar to Theorem6. The probability of the challenger B not aborting is
Pr
⁡
[
¬
abort
]
≥
1
/
16
q
K
q
S
(
q
E
+
q
S
)
(
n
u
+
1
)
(
n
ζ
+
1
)
(
n
w
+
1
). Then, the successful probability (advantage) of the challenger B who can solve the CDH problem is at least ɛ/16qKqS(qE+qS)(nu+1)(nζ+1)(nw+1). The executing time is τ+O((nu·qE+nt·qU+(nζ+nη)·qK + (nu+nt+nζ+nη+nw)·qS)·τ1 + (qE+qU+qK+qS)·τ2), where τ1 and τ2 denote the executing time of a multiplication in G1 and an exponentiation in G1, respectively.


## 6. Discussions and Comparisons

Here, we compare our RCLS scheme with the previously proposed CLS schemes in the standard model [16–18, 21]. Table 1 presents the comparisons between those schemes and ours in terms of computational cost and security property.Table 1
Comparisons between our scheme and the previously proposed schemes.
Liu et al.’s  scheme [16]
Xiong  et al.’s  scheme [17]
Yuan  et al.’s scheme [18]
Yu  et al.’s scheme [21]
Our scheme
Computational cost for signature
6Texp⁡
6Texp⁡
9Texp⁡
7Texp⁡
2Texp⁡
Computational cost for verification
6TGe
3TGe
6TGe
5TGe
7TGe
Against Type I adversary
Yes
No
No
No
Yes
Against Type II adversary
No
Yes
Yes
No
Yes
Revocation mechanism
No
No
No
No
Yes
Against Type III adversary
—
—
—
—
Yes
Security assumption
NGBDH Many-DH
NGBDH Many-DH
AC-DH 2-Many-DH
NGBDH Many-DH
CDHIn the signature procedure, our scheme requires only2Texp⁡ operations and the other schemes require at least 6Texp⁡ operations, where Texp⁡ is the time for executing an exponentiation operation in G1. In the verification procedure, our scheme requires 7TGe operations, where TGe denotes the time for executing a pairing operation e^. Our scheme requires more pairing operations than the others but it provides the security against both Type I and Type II adversaries. As for the security analysis, as mentioned in Section 1, all the existing CLS schemes in the standard model suffer from outsiders’ key replacement attacks (Type I adversary) or KGC attacks (Type II adversary). We emphasize that our scheme provides a full security against both Type I and Type II adversaries.In addition, our scheme provides a public revocation mechanism, while the existing CLS schemes did not. As for security assumptions, our scheme is based on the standard CDH assumption, while the others are based on nonstandard assumptions, such as the non-pairing-based generalized bilinear Diffie-Hellman (NGBDH), many Diffie-Hellman (Many-DH), augmented computational Diffie-Hellman (AC-DH), and 2-many Difffie-Hellman (2-Many-DH) assumptions.Furthermore, to reduce the KGC’s computational cost, one may adopt the technique in [37] by employing a delegated revocation authority (DRA) to generate users’ time update keys. In Figure 1, we illustrate how the DRA assists the KGC in revoking misbehaving/compromised users. First, the KGC generates the public parametersparams, the system secret key g2α and the time secret key g2β. Secondly, the KGC transmits the time secret key g2β to the DRA by using a secure channel, and then the DRA can use it to generate users’ time update keys and send them to users via a public channel. Finally, in order to revoke some misbehaving/compromised users, it only stops issuing the current time update keys to those users.Figure 1
The generation of a user’s full signing key.


## 7. Conclusions

In this article, we proposed the first secure revocable certificateless signature scheme in the standard model under an extended model of Hu et al.’s. We formally demonstrated that our scheme possesses existential unforgeability against adaptive chosen-message attacks from Type I, Type II, and Type III adversaries under the standard computational Diffie-Hellman assumption. Moreover, Table1 indicates that our scheme owns better security than the others under consideration. Finally, an interesting and nontrivial issue, namely, constructing a strongly unforgeable certificateless signature scheme, is worth studying. We leave it as future work.



---

*Source: 728591-2014-11-19.xml*