# Strongly Secure Certificateless Signature Scheme Supporting Batch Verification

Authors: Chun-I Fan; Pei-Hsiu Ho; Yi-Feng Tseng
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We propose a strongly secure certificateless signature scheme
supporting batch verification, which makes it possible for a verifier
to verify a set of signatures more efficiently than verifying them
one by one. In an identity-based digital signature scheme, private key generator (PKG) knows each user's signing key, so it can
generate a signature which is indistinguishable from the signature
generated by the user. This is a serious problem because the
property of signature nonrepudiation will not be achieved. In our
proposed scheme, it is impossible for PKG to produce a signature
which is indistinguishable from any signature produced by a user.
Compared with existing signature schemes with batch verification,
although our proposed scheme is not the most efficient one, it
achieves Girault's level-3 security, while the others have Girault's
level-1 or level-2 security only. We also formally prove that the proposed
scheme is unforgeable and satisfies Girault's level-3 security based
on hard problems.


---

## Body

## 1. Introduction

In traditional certificate-based public-key cryptosystems, a user’s public key is produced and is not related to her/his identity. Therefore, the key needs to be certificated by some certification authority (CA) with respect to the user’s identity. Anyone who wants to use the public key must verify the validity of the corresponding certificate for the key first. Considering implementation, the management of public key certificates requires a large amount of computation cost and storage.To reduce the cost of certificate management, Shamir [1] proposed identity based public key cryptography (ID-PKC) in 1984. In ID-PKC, a user’s public key can be an arbitrary bit string which can represent the user’s identity, such as her/his email address or telephone number. And the user’s corresponding private key is computed by a trusted party, called private key generator (PKG) [2].An inherent problem of ID-PKC is the key escrow problem. That is, the private key of a user is known to PKG. PKG can act as any user to decrypt any ciphertext or generate a signature on any message. To solve this problem, Al-Riyami and Paterson [3] proposed certificateless public key cryptography (CL-PKC) in 2003. In CL-PKC, a user’s secret key is a combination of the secret key, computed by PKG using its master secret key, and a user-chosen secret. Thus, PKG cannot know the complete secret key of the user.In 2003, a certificateless public-key signature scheme [3] was proposed, but it suffered from the key replacement attack [4]. After that, several certificateless signature schemes [5–18] were introduced recently. In 2007, Hu et al. [19] proposed a new security model and an improved generic construction for certificateless signatures. It showed that certificateless signatures should satisfy the property of Girault’s level-3 security [20]. If a certificateless signature scheme meets the above property, the framework of CL-PKC will be with the same security level as that of the traditional certificate-based public key cryptosystems.In 1989, batch cryptography was first introduced by Fiat [21]. In a signature scheme with batch verification, the cost for verifying n signatures is less than verifying them one by one. After [21], some results [22–24] about batch verification based on RSA or DLP have been proposed. In 2004, Yoon et al. proposed an ID-based signature scheme with batch verification [25], but their security proof does not meet the definition of batch verification [26]. After that, some ID-based and group signature schemes with batch verification were proposed in [27–34], respectively, but only [29] is a certificateless signature scheme. Besides, the randomization technique [26, 35–39] for the security of signatures with batch verification was introduced. The technique can withstand the attack that an attacker cheats a verifier to accept invalid signatures.In this paper, we will design a certificateless signature scheme with efficient batch verification. The computation cost of our scheme in batch verification is only three pairings and it is independent of the number of individual signatures which will be verified. Furthermore, our scheme satisfies Girault’s level-3 security. Compared to certificateless, ID-based, and group signature schemes with batch verification [7, 11, 14, 16, 27–34], our scheme achieves Girault’s level-3 security, while [27–34] meet Girault’s level-1 security and [7, 11, 14, 16, 29] satisfy Girault’s level-2 security only. Compared to [5, 13], which also achieve Girault’s level-3 security, our scheme is more efficient in verification because of the batch property.The rest of this paper is organized as follows. In Section2, we introduce some preliminaries about mathematical backgrounds and definitions. In Section 3, we present the proposed scheme. In Section 4, we provide formal security proofs for our scheme. We compare the proposed scheme with [5, 7, 11, 13, 14, 16, 27–34] in Section 5. Finally, a concluding remark is given in Section 6.


## 2. Preliminaries

In this section, we review the properties of bilinear groups and some related hard problems.LetG1 and G2 be two cyclic groups of prime order q. Let P be a randomly chosen generator of G1 and let e be a bilinear mapping such that e: G1×G1→G2, which satisfies the following properties.(1)
Bilinearity: for allP,Q,R∈G1, e(P+Q,R)=e(P,R)e(Q,R) and e(P,Q+R)=e(P,Q)e(P,R).(2)
Nondegeneracy: there existsP,Q∈G1 such that e(P,Q)≠1.(3)
Computability: there exists an efficient algorithm to computee(P,Q) for any P,Q∈G1.Definition 1 (batch verification of signatures [35]).
Letl be the security parameter. Suppose that (Gen,Sign,Verify) is a signature scheme, n∈ polynomial(l), and (pk1,sk1),…,(pkn,skn) are generated independently according to Gen(1l) where pki and ski are a user i’s public key and secret key, respectively. Then, we call probabilistic Batch a batch verification algorithm when the following conditions hold.(i)
IfVerify(σi,mi,pki)=1 for all i∈[1,n], then Batch((σ1,m1,pk1),…,(σn,mn,pkn))=1 where mi and σi are a message and a signature, respectively.(ii)
IfVerify(σi,mi,pki)=0 for some i∈[1,n], then Batch((σ1,m1,pk1),…,(σn,mn,pkn))=1 with probability negligible in  k, taken over the randomness of Batch.Definition 2 (a certificateless signature scheme with batch verification).
A certificateless signature scheme with batch verification consists of the following algorithms.(i)
Setup: PKG randomly chooses a secret key and computes the public key Tpub by using the secret key. Then, it publishes Tpub and other system parameters.(ii)
KeyGen: a user IDi first randomly chooses a secret key xi, computes corresponding public key Pi and then sends Pi to PKG. After receiving Pi, PKG outputs a partial private key Di to a legal user with identity IDi.(iii)
Signing(Pi,Di,xi,m): this algorithm gets a user’s public key Pi, the user’s partial private key Di, the user’s secret key xi, and a message m and then it outputs a signature σ on m.(iv)
Verifying(σ,m,IDi,Pi): this algorithm gets a signature σ on a message m, a signer’s identity IDi, and a signer’s public key Pi. It then outputs True or False.(v)
Batch_Verify((σ1,m1,ID1,P1),…,(σn,mn,IDn,Pn)): this algorithm gets n signatures σ1,…,σn on message m1,…,mn, the signers’ identities ID1,…,IDn, and the signers’ public keys  P1,…,Pn, respectively. This algorithm outputs True or False.Definition 3 (Girault’s security [19, 20]).
Girault proposed three security levels to classify the levels of trust to PKG. The three levels are described as follows.(i)
Level 1: PKG knows the secret of any user.(ii)
Level 2: PKG cannot find out all the information of a user’s secret. However, PKG can generate a contradictory public key (or a contradictory certificate) and impersonate the user to generate signatures with respect to the contradictory public key.(iii)
Level 3: PKG cannot find out all the information of a user’s secret nor generate a contradictory public key. PKG can only generate a valid public key (or a valid certificate).Definition 4 (the computational Diffie-Hellman (CDH) problem).
LetG1 be a cyclic group of order q and let P be a generator of G1. Given 〈G1,q,P,aP,bP〉 for some a,b∈Zq*, compute abP.


## 3. Our Proposed Scheme

In this section, we propose an efficient certificateless signature scheme with batch verification based on [15]. G1 is an additive group and G2 is a multiplicative group. Let G1 and G2 be two cyclic groups of prime order q. Let P be a randomly chosen generator of G1 and e a bilinear mapping such that e:G1×G1→G2. The details of our scheme are described as follows.Setup. PKG performs the following operations.(1)
Choose an integerλ∈Zq* and θ∈{0,1}* randomly, and set Tpub=λP.(2)
Choose four cryptographic one-way hash functions,H0:{0,1}*→G1, H1:G1→G1, H2:{0,1}*×G1×G1→Zq*, H3:{0,1}*×G1×G1→Zq*, and H4:{0,1}*→G1.(3)
Publish the system parameters{G1,G2,e,q,P,θ,Tpub,H0,H1,H2,H3,H4} and keep the master key λ secret.Key Generating Phase
(1)
A user with identityIDi randomly chooses xi∈Zq* and computes Pi=xiP, where xi and Pi are called the secret key and the public key, respectively, of user IDi.
(2)
The user sends(IDi,Pi) to PKG.
(3)
PKG getsQi=H0(IDi) and Γi=H1(Pi).
(4)
PKG computesDi0=λQi and Di1=λΓi and sends (Di0,Di1) to the user via a secret channel. The pair (Di0,Di1) is called the partial private key of user IDi. The private key of user IDi consists of xi and (Di0,Di1).Signing Phase. Assume that a signer IDi wants to sign a message m∈{0,1}*. The signer does the following works.(1)
Chooser and α∈Zq* randomly.(2)
ComputeU1=r(Qi+Γi) and U2=αxiP.(3)
Computeh2=H2(m,U1,U2), h3=H3(m,U2,U1), and W=H4(θ).(4)
ComputeV=(r+h2)(Di0+Di1)+(α+h3)xiW.(5)
The signature onm is σ=(V,U1,U2,Pi).Verifying Phase. To verify a signature (V,U1,U2,Pi) on message m, a verifier should do the following works.(1)
ComputeQi=H0(IDi), Γi=H1(Pi), h2=H2(m,U1,U2), h3=H3(m,U2,U1), and W=H4(θ).(2)
Verify if(P,V)=e(Tpub,U1+h2(Qi+Γi))e(W,U2+h3Pi). If it is true, the verifier accepts the signature; otherwise, the verifier rejects it.Batch Verifying Phase. To verify n signatures σ1=(V1,U11,U21,P1),…,σn=(Vn,U1n,U2n,Pn) of the n signers ID1,…,IDn on message m1,…,mn, respectively, a verifier performs the following works.(1)
Choosew1,…,wn∈Zq* randomly.(2)
ComputeQi=H0(IDi), Γi=H1(Pi), h2i=H2(mi,U1i,U2i), h3i=H3(mi,U2i,U1i) for i=1,…,n, and W=H4(θ).(3)
Verify if(P,∑i=1nwiVi)=e(Tpub,∑i=1nwiU1i+wih2i(Qi+Γi))e(W,∑i=1nwiU2i+wih3iPi). If it is true, the verifier accepts the n signatures.Correctness. Consider
(1)e(P,∑i=1n‍wiVi)=e(P,∑i=1n‍wi((ri+h2i)(Di0+Di1)+(αi+h3i)xiW)∑i=1n‍)=e(P,∑i=1n‍wi(ri(Di0+Di1)+h2i(Di0+Di1)))×e(P,∑i=1n‍wi(αixiW+h3ixiW))=e(λP,∑i=1n‍wi(ri(Qi+Γi)+h2i(Qi+Γi)))×e(W,∑i=1n‍wi(αixiP+h3ixiP))=e(Tpub,∑i=1n‍wi(U1i+h2i(Qi+Γi)))×e(W,∑i=1n‍wi(U2i+h3iPi)).


## 4. Security Models and Formal Proofs

### 4.1. Security Models

A simulatorB simulates an environment such that an adversary E can query signatures from B. If E can forge a signature, B can use the output from E to solve a hard problem.We classify adversaryE into three types. The adversary of type I cannot access the master secret key and query the partial private key of target ID. The adversary of type II can access the master secret key but cannot query target ID’s secret key nor replace her/his public key. The adversary of type III is to simulate the environment for the proof of that a user cannot produce a signature with a new public-secret key pair, which is different from his own one, without the corresponding partial private key generated from the master secret key.We define the capability ofE which can be captured by the following queries.(i)
H0(IDi): if E inputs a user’s identity IDi to H0, B will output a randomly chosen Qi∈G1 as the user’s public key.(ii)
H1(Pi): when E inputs a public key Pi∈G1 to H1, B outputs a randomly chosen Γi∈G1.(iii)
H2(m,U1,U2): if E inputs a message m∈{0,1}* and U1,U2∈G1, B will output an integer randomly chosen in Zq*.(iv)
H3(m,U2,U1): if E inputs a message   m∈{0,1}*, U2∈G1, and U1∈G1, B will output a random integer in Zq*.(v)
H4(ϱ): if E inputs a string ϱ∈{0,1}*, B will output an element randomly chosen in G1.(vi)
Public_Key(IDi): if E inputs a user’s identity, IDi, then B will output the user’s public key Pi.(vii)
Partial_Private_Key(IDi,Pi): if E inputs a user’s identity IDi and the user’s public key Pi, B will output the partial private key (Di0,Di1).(viii)
Secret_Key(IDi): if E inputs a user’s identity, IDi, B will output the secret key xi of user IDi to E.(ix)
Public_Key_Replacement(IDi,Pi′): when E inputs a user’s identity IDi and the user’s new public key Pi′, B will replace Pi with Pi′. The new partial private key can be obtained by querying Partial_Private_Key(IDi).(x)
Sign(IDi,m): if E inputs a user’s identity IDi and a message m, B will output a user IDi’s signature σ on m to E.Definition 5 (the CDH assumption).
We say that the(t,ε)-CDH assumption holds in G1 if no polynomial-time algorithm within running time t can solve the CDH problem with probability at least ε.Definition 6 (the unforgeability game I).
LetE1 be a polynomial-time attacker of type I. E1 interacts with a challenger B in the following game.(i)
Step 1:B runs the setup algorithm of a certificateless signature scheme with batch verification. B publishes the public parameters.(ii)
Step 2:E1 queries Partial_Private_Key, Public_Key, Public_Key_Replacement, Secret_Key, Sign, H0, H1, H2, H3, and H4 in an arbitrary sequence.(iii)
Step 3:E1 outputs n signatures σ1,…,σn on m1,…,mn corresponding to the signers ID1,…,IDn with the public keys P1,…,Pn, respectively.
E
1 wins the game if (1)
Batch_Verify((σ1,m1,ID1,P1),…,(σn,mn,IDn,Pn)) = True;(2)
there existsσy∈{σ1,…,σn} whose (IDy,my) has not been queried to Sign oracle;(3)
Partial_Private_Key(IDy,Py) has never been queried.
The scheme is (t,ε, I)-unforgeable if no polynomial-time attacker E1, with running time at most t, can win the unforgeability game I with probability at least ε.Definition 7 (the unforgeability game II).
LetE2 be a polynomial-time attacker of type II. E2 interacts with a challenger B in the following game.(i)
Step 1:B runs the setup algorithm of a certificateless signature scheme with batch verification. B publishes the public parameters and sends the master secret key to E2.(ii)
Step 2:E2 queries Partial_Private_Key, Public_Key, Public_Key_Replacement, Secret_Key, Sign, H0, H1, H2, H3, and H4 in an arbitrary sequence.(iii)
Step 3:E2 outputs n signatures σ1,…,σn on m1,…,mn corresponding to the signers ID1,…,IDn with the public keys P1,…,Pn, respectively.
E
2 wins the game if (1)
Batch_Verify((σ1,m1,ID1,P1),…,(σn,mn,IDn,Pn)) = True;(2)
there existsσy∈{σ1,…,σn} whose (IDy,my) has not been queried to Sign oracle;(3)
NeitherSecret_Key(IDy) nor Public_Key_Replacement(IDy,·,·) has been queried.
The scheme is (t,ε, II)-unforgeable if no polynomial-time attacker E2, with running time at most t, can win the unforgeability game II with probability at least ε.Definition 8 (the unforgeability game III [19]).
LetE3 be a polynomial-time attacker of type III. E3 interacts with a challenger B in the following game.(I)
Step 1:B runs the setup algorithm of a certificateless signature scheme with batch verification. B publishes the public parameters.(II)
Step 2:E3 queries Partial_Private_Key, Public_Key, Public_Key_Replacement, Secret_Key, H0, H1, H2, H3, and H4 in an arbitrary sequence.(III)
Step 3:E3 outputs a signature σ*=(V*,U1*,U2*,Py*) on a message m* for the user IDy.
E
3 wins the game if(1)
Verifying(σ*,m*,IDy,Py*)= True;(2)
UserIDy has been created, that is, Public_Key(IDy), Partial_Private_Key(IDy,Py), and Secret_Key(IDy) have been queried;(3)
Py* is different from all of the public keys Py’s returned by Public_Key(IDy) or used to query Public_Key_Replacement.
The scheme is (t,ε, III)-unforgeable if no polynomial-time attacker E3, with running time at most t, can win the unforgeability game III with probability at least ε.


### 4.2.  Formal Proofs

In this section, we will prove that our scheme is unforgeable based on the CDH assumption.Lemma 9 (the forking lemma [40]).
Let(s,m,c) be a valid signature-message triple of a signature scheme and h the hashed value of (m,c) where m is a plaintext message, c is a string, and s is called the signature part of the triple. Let A be a probabilistic polynomial-time Turning machine. Given only the public data of the signature scheme as input, if A can find, with nonnegligible probability, a valid signature-message triple (s,m,c) with h, then, with nonnegligible probability, a replay of this machine, with the same random tape and a different value returned by the random oracle, outputs two valid signature-message triples (s,m,c) with h and (s′,m,c) with h′ such that h≠h′.Lemma 10 (the splitting lemma [40]).
LetA⊂X×Y such that Pr[(x,y)∈A]≥ε. For any α<ε, define B={(x,y)∈X×Y∣Pry′∈Y[(x,y′)∈A]≥ε-α} and then the following statements hold: (1)
Pr[B]≥α,(2)
∀(x,y)∈B,Pry′∈Y[(x,y′)∈A]≥ε-α,(3)
Pr[B∣A]≥α/ε.Theorem 11.
Givenn 5-tuples (Vi,U1i,U2i,Pi,mi)’s, if e(P,∑i=1n‍wiVi)=e(Tpub,∑i=1n‍wiU1i+wih2i(Qi+Γi))e(W,∑i=1n‍wiU2i+wih3iPi) where wi is randomly chosen in Zq*, h2i=H2(mi,U1i,U2i), and h3i=H3(mi,U2i,U1i) for each i, the probability of that e(P,Vi)≠e(Tpub,U1i+h2i(Qi+Γi))e(W,U2i+h3iPi) for some i∈{1,…,n} is 1/2∣q∣.Proof.
The proof is based on [35, 37]. If e(P,Vi)≠e(Tpub,U1i+h2i(Qi+Γi))e(W,U2i+h3iPi) for some i, we have that Vi≠(ri+h2i)(λQi+λΓi)+(αi+h3i)xiW for some i. Thus, there exists ci≠0 (mod q) such that Vi=(ri+h2i)(λQi+λΓi)+(αi+h3i)xiW+ciP for some i.
LetVj=(rj+h2j)(λQj+λΓj)+(αj+h3j)xjW+cjP and cj∈{0,1,…,q-1}, ∀j∈{1,…,n}-{i}. As e(P,∑i=1n‍wiVi)=e(Tpub,∑i=1n‍wiU1i+wih2i(Qi+Γi))e(W,∑i=1n‍wiU2i+wih3iPi), w1c1+w2c2+w3c3+⋯+wncn≡0 (mod q) and thus wi=ci-1(w1c1+w2c2+⋯+wi-1ci-1+wi+1ci+1+⋯+wncn) mod q. Since wi is randomly chosen in Zq*, the probability of wi=ci-1(w1c1+w2c2+⋯+wi-1ci-1+wi+1ci+1+⋯+wncn) mod q is 1/2∣q∣, which is negligible.Theorem 12.
The proposed scheme is (t,qsign,qppk,qsk,qpkr,qpk,qh0,qh1,qh2,qh3,qh4,ε,I)-unforgeable assuming that the (t′,ε′)-CDH assumption holds in G1 where ε′≥(ε/(2qh0))(1-1/2|q|)2,  t′≈t+qsign𝒪(tsign)+qppk𝒪(tppk)+qsk𝒪(tsk)+qpkr𝒪(tpkr)+qpk𝒪(tpk)+qh0𝒪(th0)+qh1𝒪(th1)+qh2𝒪(th2)+qh3𝒪(th3)+qh4𝒪(th4)+𝒪(1), qsign, qppk, qsk, qpkr, qpk, qh0, qh1, qh2, qh3, and qh4 being the numbers of queries to Sign, Partial_Private_Key, Secret_Key, Public_Key_Replacement, Public_Key, H0, H1, H2, H3, and H4, respectively, and tsign, tppk, tsk, tpkr, tpk, th0, th1, th2, th3, and th4 being the computing time of the queries to Sign, Partial_Private_Key, Secret_Key, Public_Key_Replacement, Public_Key, H0, H1, H2, H3, and H4, respectively.Proof.
Assume that a polynomial-time attackerE1 wins the game of Definition 6 with probability being at least ε within running time t. A simulator B is given an instance of the CDH problem 〈G1,q,P,aP,bP〉, and B’s goal is to output the value of abP. We will construct B which plays the game in Definition 6 with E1 and outputs the value of abP.
Setup. B sets Tpub=bP and chooses θ∈{0,1}* randomly. Then, B publishes {G1,G2, e, q, P, θ, Tpub, H0, H1,H2,H3, H4}.
B can respond to the queries from E1 as follows.(i)
H0 query: B constructs a list, H0-list, and chooses an identity IDπ randomly. When E1 queries H0(IDi) to B, B checks whether IDi is in H0-list or not. If IDi does not exist in H0-list, then there are the following two cases. Case 1: if IDi=IDπ, B sets Qi=aP=H0(IDi) and stores (IDi,aP) in H0-list. Case 2: if IDi≠IDπ, B sets Qi=kiP=H0(IDi) where ki is randomly chosen in Zq* and stores (IDi,kiP,ki) in H0-list. However, if IDi exists in H0-list, B gets its mapping value, Qi=kiP or aP. Finally, B returns Qi.(ii)
H1 query: B constructs a list, H1-list. If E1 queries H1(Pi) to B where Pi∈G1, B checks whether Pi is in H1-list or not. If it does not exist in H1-list, B randomly chooses ρi∈Zq* and records (Pi,ρiP,ρi) in H1-list; else, B gets its mapping value, ρiP, from H1-list. Then, B returns ρiP to E1.(iii)
H2 query: B constructs H2-list. If E1 queries H2(m,U1,U2) to B, B checks whether (m,U1,U2) is in H2-list or not. If not, B randomly chooses h2∈Zq* and records ((m,U1,U2),h2) in H2-list; else, B gets its mapping value, h2, from H2-list. Then, B returns   h2 to E1.(iv)
H3 query: B constructs H3-list. When E1 queries H3(m,U2,U1) to B, B checks whether (m,U2,U1) is in H3-list or not. If not, B randomly chooses h3∈Zq* and records ((m,U2,U1),h3) in H3-list; otherwise, B gets its mapping value, h3, from H3-list. Then, B responds h3 to E1.(v)
H4 query: B constructs H4-list. If E1 queries H4 with a string ϱ to B, B checks whether ϱ is in H4-list or not. If ϱ does not exist in H4-list, then there are the following two conditions. Condition 1: if ϱ=θ, B sets W=βP=H4(ϱ) where β is randomly chosen in Zq* and stores (ϱ,βP,β) in H4-list. Condition 2: if ϱ≠θ, B sets W=Φ=H4(ϱ) where Φ is randomly chosen in G1 and stores (ϱ,Φ) in H4-list. However, if ϱ exists in H4-list, B gets its mapping value, W=Φ or βP. Finally, B returns W.(vi)
Public_Key query: B constructs a list, pk-list. When E1 queries Public_Key(IDi) to B, B looks up pk-list. If IDi is not found in pk-list, B randomly chooses xi∈Zq*, computes Pi=xiP, and stores (IDi,Pi,xi) in pk-list; otherwise, B gets Pi from pk-list. Finally, B returns Pi.(vii)
Partial_Private_Key query: if E1 queries Partial_Private_Key(IDi,Pi′) to B, B looks up H0-list, pk-list, and H1-list. If IDi=IDπ, B returns “failure.” If IDi is not found in H0-list, B queries H0(IDi) and gets ki from H0-list; else, B retrieves ki from H0-list. If IDi is not in pk-list, B queries Public_Key(IDi) and obtains Pi; otherwise, B catches Pi from pk-list. If Pi≠Pi′, B returns “failure.” Then, if Pi is not found in H1-list, B queries H1(Pi) and gets ρi; else, B retrieves ρi from H1-list. Finally, B returns (Di0=kibP,Di1=ρibP).(viii)
Secret_Key query: if E1 queries Secret_Key(IDi) to B, B looks up pk-list. If IDi is not found in pk-list, B queries Public_Key(IDi) and gets xi; if there is a record (IDi,Pi,xi), then B retrieves xi from pk-list and returns xi.(ix)
Public_Key_Replacement query: when E1 queries Public_Key_Replacement(IDi, Pi′) to B, B looks up pk-list. If IDi is not found in pk-list, B queries Public_Key(IDi). Then, B replaces the record (IDi,Pi,xi) with (IDi,Pi′,⊥) in pk-list.(x)
Sign query: when E1 queries Sign(IDi,m) to B, if IDi=IDπ, B does the following works.
(1)
Choosez, α, and h2∈Zq* randomly;(2)
computeU1=zP-h2aP and U2=αP;(3)
setH2(m,U1,U2)=h2;(4)
computeh3=H3(m,U2,U1) and W=H4(θ);(5)
computeV=zbP+h2ρibP+αβP+h3βPi;(6)
formσ=(V,U1,U2,Pi).Thus, the signature on m is σ=(V,U1,U2,Pi) and it satisfies the verifying formula in Section 3.
IfIDi≠IDπ, B can return a signature on m to E1 because B can compute all secrets of user IDi. Finally, suppose that E1 outputs, with probability at least ε, n signatures σ1,…,σn on m1,…,mn of the signers ID1,…,IDn, respectively, such that (1)
Batch_Verify((σ1,m1,ID1,P1),…,(σn,mn,IDn,Pn)) = True;(2)
there existsσy∈{σ1,…,σn} which is not the output from Sign(IDy,my);(3)
Partial_Private_Key(IDy,Py) has never been queried.
From Lemma9, we fork the sequence of signatures one time and get σ1′,…,σn′ on m1,…,mn by setting h2y′≠h2y. Thus, we randomly choose wi’s and obtain the following two equations:
(2)e(P,∑i=1n‍wiVi)=e(Tpub,∑i=1n‍wiU1i+wih2i(Qi+Γi))×e(W,∑i=1n‍wiU2i+wih3iPi),e(P,∑i=1n‍wiVi′)=e(Tpub,∑i=1n‍wiU1i′+wih2i′(Qi+Γi))×e(W,∑i=1n‍wiU2i′+wih3i′Pi)
with probability being at least ε/2 by Lemma 10, where Vy≠Vy′, U1y=U1y′, h2y≠h2y′, U2y=U2y′, and h3y=h3y′.
We assume thatIDy=IDπ. By Theorem 11, we have that
(3)e(P,Vy)=e(Tpub,U1y+h2y(Qy+Γy))×e(W,U2y+h3yPy),e(P,Vy′)=e(Tpub,U1y+h2y′(Qy+Γy))×e(W,U2y+h3yPy)
with probability being at least (ε/(2qh0))(1-1/2∣q∣)2. Thus, we can compute (h2y-h2y′)-1((Vy-Vy′)-ρyTpub), which is abP, to solve the CDH problem with ε′≥(ε/(2qh0))(1-1/2∣q∣)2 and t′≈t+qsign⁡𝒪(tsign⁡)+qppk𝒪(tppk)+qsk𝒪(tsk)+qpkr𝒪(tpkr)+qpk𝒪(tpk)+qh0𝒪(th0)+qh1𝒪(th1)+qh2𝒪(th2)+qh3𝒪(th3)+qh4𝒪(th4)+𝒪(1).Theorem 13.
The proposed scheme is (t,qsign,qppk,qsk,qpkr,qpk,qh0,qh1,qh2,qh3, qh4, ε, II)-unforgeable assuming that the (t′,ε′)-CDH assumption holds in G1 where ε′≥(ε/(2qpk))(1-1/2|q|)2,t′≈t+qsign𝒪(tsign)+qppk𝒪(tppk)+qsk𝒪(tsk)+qpkr𝒪(tpkr)+qpk𝒪(tpk)+qh0𝒪(th0)+qh1𝒪(th1)+qh2𝒪(th2)+qh3𝒪(th3)+qh4𝒪(th4)+𝒪(1), qsign, qppk, qsk, qpkr, qpk, qh0, qh1, qh2, qh3, and qh4 are the numbers of queries to Sign, Partial_Private_Key, Secret_Key, Public_Key_Replacement, Public_Key, H0, H1, H2, H3, and H4, respectively, and tsign, tppk, tsk, tpkr, tpk, th0, th1, th2, th3, and th4 are the computing time of the queries to Sign, Partial_Private_Key, Secret_Key, Public_Key_Replacement, Public_Key, H0, H1, H2, H3, and H4, respectively.Proof.
Assume that a polynomial-time attackerE2 wins the game of Definition 7 with probability at least ε within running time t. A simulator B is given an instance of the CDH problem 〈G1,q,P,aP,bP〉, and B’s goal is to output the value of abP. We will construct B which plays the game in Definition 7 with E2 and outputs the value of abP.
Setup. B sets Tpub=λP where λ is randomly chosen in Zq* and chooses θ∈{0,1}* randomly. Then, B publishes {G1,G2, e, q, P, θ, Tpub, H0, H1,H2,H3, H4} and sends λ to E2. B can respond to the queries from E2 as follows.(i)
H0 query: B constructs a list, H0-list. When E2 queries H0(IDi) to B, B checks whether IDi is in H0-list or not. If IDi does not exist in H0-list, B sets Qi=kiP=H0(IDi) where ki is a random integer in Zq* and records (IDi, kiP, ki) in H0-list; else, B gets its mapping value, kiP, from H0-list. Then, B returns  Qi=kiP to E2.(ii)
H4 query: B constructs H4-list. If E2 queries H4 with a string ϱ to B, B checks whether ϱ is in H4-list or not. If ϱ does not exist in H4-list, then there are the following two conditions. Condition 1: if ϱ=θ, B sets W=bP=H4(ϱ) and stores (ϱ,bP) in H4-list. Condition 2: if ϱ≠θ, B sets W=Φ=H4(ϱ) where Φ is randomly chosen in G1 and stores (ϱ,Φ) in H4-list. However, if ϱ exists in H4-list, B gets its mapping value, W=Φ or bP. Finally, B returns W.(iii)
The simulations forH1, H2, H3, and Public_Key_Replacement are the same as those in the proof of Theorem 12.(iv)
Public_Key query: B constructs a list, pk-list, and chooses an identity IDπ randomly. When E2 queries Public_Key(IDi) to B, B looks up pk-list. If IDi does not exist in pk-list, then there are the following two conditions. Condition 1: if IDi=IDπ, B sets Pi=aP and stores (IDi,aP) in pk-list. Condition 2: if IDi≠IDπ, B sets Pi=xiP where xi is randomly chosen in Zq* and stores (IDi,xiP,xi) in pk-list. However, if IDi exists in pk-list, B gets its mapping value, Pi=xiP or aP. Finally, B returns Pi.(v)
Partial_Private_Key query: when E2 queries Partial_Private_Key(IDi,Pi′) to B, B looks up H0-list, pk-list, and H1-list. If IDi is not found in H0-list, B queries H0(IDi) and gets ki from H0-list; else, B retrieves ki from H0-list. If IDi is not in pk-list, B queries Public_Key(IDi) and obtains Pi; otherwise, B catches Pi from pk-list. If Pi≠Pi′, B returns “failure.” Then, if Pi is not found in H1-list, B queries H1(Pi) and gets ρi; else, B retrieves ρi from H1-list. Finally, B returns (Di0=λkiP,Di1=λρiP).(vi)
Secret_Key query: when E2 queries Secret_Key(IDi) to B, B looks up pk-list. If IDi=IDπ, B returns “failure.” If IDi is not found in pk-list, B queries Public_Key(IDi) and gets xi from pk-list; else, B retrieves xi from pk-list. Finally, B returns xi.(vii)
Sign query: when E2 queries Sign(IDi,m) to B, if IDi=IDπ, B performs the following works.
(1)
choosez, α, and h3∈Zq* randomly;(2)
computeU1=zP and U2=αP-h3aP;(3)
computeh2=H2(m,U1,U2) and W=H4(θ);(4)
setH3(m,U2,U1)=h3;(5)
computeV=zλP+h2kiλP+h2ρiλP+αW;(6)
formσ=(V,U1,U2,Pi).
Therefore, the signature onm is σ=(V,U1,U2,Pi) and it meets the verifying formula in Section 3.
IfIDi≠IDπ, B can return a signature on m to E2 since B knows all secrets of user IDi. Finally, E2 outputs, with probability being at least ε, n signatures σ1,…,σn on m1,…,mn of the signers ID1,…,IDn, respectively, such that (1)
Batch_Verify((σ1,m1,ID1,P1),…,(σn,mn,IDn,Pn)) = True;(2)
there existsσy∈{σ1,…,σn} which is not the output from Sign(IDy,my);(3)
neitherSecret_Key(IDy) nor Public_Key_Replacement(IDy,·,·) has been queried.
From Lemma9, we fork the sequence of signatures one time and get σ1′,…,σn′ on m1,…,mn by setting h3y′≠h3y. Thus, we randomly choose wi’s and obtain the following two equations:
(4)e(P,∑i=1n‍wiVi)=e(Tpub,∑i=1n‍wiU1i+wih2i(Qi+Γi))×e(W,∑i=1n‍wiU2i+wih3iPi),e(P,∑i=1n‍wiVi′)=e(Tpub,∑i=1n‍wiU1i′+wih2i′(Qi+Γi))×e(W,∑i=1n‍wiU2i′+wih3i′Pi)
with probability being at least ε/2 by Lemma 10, where Vy≠Vy′, U1y=U1y′, h2y=h2y′, U2y=U2y′, and h3y≠h3y′.
We assume thatIDy=IDπ. By Theorem 11, we have that
(5)e(P,Vy)=e(Tpub,U1y+h2y(Qy+Γy))×e(W,U2y+h3yPy),e(P,Vy′)=e(Tpub,U1y+h2y(Qy+Γy))×e(W,U2y+h3y′Py)
with probability being at least (ε/(2qpk))(1-1/2|q|)2. Thus, we can compute (h3y-h3y′)-1(Vy-Vy′), which is abP, to solve the CDH problem with ε′≥(ε/(2qpk))(1-1/2|q|)2 and t′≈t+qsign⁡𝒪(tsign⁡)+qppk𝒪(tppk)+qsk𝒪(tsk)+qpkr𝒪(tpkr)+ qpk𝒪(tpk)+qh0𝒪(th0)+qh1𝒪(th1)+qh2𝒪(th2)+qh3𝒪(th3)+qh4𝒪(th4)+𝒪(1).Theorem 14.
The proposed scheme is (t,qppk,qsk,qpkr,qpk,qh0,qh1,qh2,qh3, qh4, ε, III)-unforgeable assuming that the (t′,ε′)-CDH assumption holds in G1 with ε′≥ε/(2qh1-max⁡),t′≈t+qppk𝒪(tppk)+qsk𝒪(tsk)+qpkr𝒪(tpkr)+qpk𝒪(tpk)+qh0𝒪(th0)+qh1𝒪(th1)+qh2𝒪(th2)+qh3𝒪(th3)+qh4𝒪(th4)+𝒪(1),(2qh1-max⁡) being the possibly maximal number of queries to H1, qppk, qsk, qpkr, qpk, qh0, qh1, qh2, qh3, and qh4 being the numbers of queries to Partial_Private_Key, Secret_Key, Public_Key_Replacement, Public_Key, H0, H1, H2, H3, and H4, respectively, and tsign, tppk, tsk, tpkr, tpk, th0, th1, th2, th3, and th4 being the computing time of the queries to Sign, Partial_Private_Key, Secret_Key, Public_Key_Replacement, Public_Key, H0, H1, H2, H3, and H4, respectively.Proof.
Assume that a polynomial-time attackerE3 wins the game of Definition 8 with probability being at least ε within running time t. A simulator B is given an instance of the CDH problem 〈G1,q,P,aP,bP〉, and B’s goal is to output abP. We will construct B which plays the game in Definition 8 with E3 and outputs abP.
Setup. B sets Tpub=bP and chooses θ∈{0,1}* randomly. Then, B publishes {G1,G2, e, q, P, θ, Tpub, H0, H1,H2,H3, H4}. B can respond to the queries from E3 as follows.
The simulation forH0 is identical to that in the proof of Theorem 13. Consider the following.(i)
H1 query: B constructs a list, H1-list, and then chooses π∈{1,…,qh1-max⁡} at random and sets an index j=0. When E3 queries H1(Pi) to B, B checks whether Pi is in H1-list or not. If Pi does not exist in H1-list, B computes j=j+1 and there are the following two cases. Case 1: if j=π, B sets H1(Pi)=aP and stores (Pi,aP) in H1-list. Case 2: if j≠π, B sets H1(Pi)=ρiP where ρi is randomly chosen in Zq* and stores (Pi,ρiP,ρi) in H1-list. Besides, if Pi exists in H1-list, B gets its mapping value, ρiP or aP. Finally, B returns ρiP or aP.(ii)
H4 query: B constructs H4-list. If E3 queries H4 with a string ϱ to B, B checks whether ϱ is in H4-list or not. If ϱ does not exist in H4-list, then there are the following two conditions. Condition 1: if ϱ=θ, B sets W=βP=H4(ϱ) where β is randomly chosen in Zq* and stores (ϱ,βP,β) in H4-list. Condition 2: if ϱ≠θ, B sets W=Φ=H4(ϱ) where Φ is randomly chosen in G1 and stores (ϱ,Φ) in H4-list. However, if ϱ exists in H4-list, B gets its mapping value, W=Φ or βP. Finally, B returns W.(iii)
Public_Key query: B constructs a list, pk-list. When E3 queries Public_Key(IDi) to B, B looks up pk-list. If IDi is not found in pk-list, B does the following works. B computes Pi=xiP where xi is randomly chosen in Zq*. B queries H1 with Pi. If H1(Pi)=aP, B returns “failure”; otherwise, B stores (IDi,Pi,xi) in pk-list. Besides, if IDi is found in pk-list, B gets Pi from pk-list. Finally, B returns   Pi to E3.(iv)
Partial_Private_Key query: when E3 queries Partial_Private_Key(IDi,Pi′) to B, B looks up H0-list, pk-list, and H1-list. If IDi is not found in H0-list, B queries H0(IDi) and gets ki from H0-list; else, B retrieves ki from H0-list. If IDi is not found in pk-list, B queries Public_Key with IDi and obtains Pi from pk-list; otherwise, B catches Pi from pk-list. If Pi≠Pi′, B returns “failure.” Then, B gets ρi from H1-list. Finally, B returns (Di0=kibP,Di1=ρibP).(v)
H2, H3, Secret_Key, and Public_Key_Replacement queries are the same as those in the proof of Theorem 12. Finally, E3 outputs, with probability at least ε, a signature σ*=(V*,U1*,U2*,Py*) on a message m* for the user IDy such that
(1)
Verifying(σ*,m*,IDy,Py*)= True;(2)
userIDy has been created;(3)
Py* is different from all of the public keys Py*’s returned by Public_Key(IDy) or used to query Public_Key_Replacement.
From Lemma9, we fork the sequence of signatures one time and get σ′=(V′,U1′,U2′,Py*) on m* by setting h2′≠h2*. Thus, we obtain the following two equations:
(6)e(P,V*)=e(Tpub,U1*+h2*(Qy+Γy))e(W,U2*+h3*Py*)e(P,V′)=e(Tpub,U1′+h2′(Qy+Γy))e(W,U2′+h3′Py*)
with a probability at least ε/2 by Lemma 10, where V*≠V′, U1*=U1′, h2*≠h2′, U2*=U2′, and h3*=h3′.
IfH1(Py*)=aP, B can get abP=(h2*-h2′)-1(V*-V′)-kyTpub and solve the CDH problem.
The success probability isε′≥ε/(2qh1-max⁡) with the computing time t′≈t+qsign⁡𝒪(tsign⁡)+qppk𝒪(tppk)+qsk𝒪(tsk)+qpkr𝒪(tpkr)+qpk𝒪(tpk)+qh0𝒪(th0)+qh1𝒪(th1)+qh2𝒪(th2)+qh3𝒪(th3)+qh4𝒪(th4)+𝒪(1).
By Theorem14, a user cannot produce a signature with a new public-secret key pair, which is different from his own one, without the corresponding partial private key being generated from the master secret key. Therefore, if there exist two valid signatures of a user with different public key, the user can prove to anyone that PKG is misbehaving, which means that our scheme achieves Girault’s level-3 security.


## 4.1. Security Models

A simulatorB simulates an environment such that an adversary E can query signatures from B. If E can forge a signature, B can use the output from E to solve a hard problem.We classify adversaryE into three types. The adversary of type I cannot access the master secret key and query the partial private key of target ID. The adversary of type II can access the master secret key but cannot query target ID’s secret key nor replace her/his public key. The adversary of type III is to simulate the environment for the proof of that a user cannot produce a signature with a new public-secret key pair, which is different from his own one, without the corresponding partial private key generated from the master secret key.We define the capability ofE which can be captured by the following queries.(i)
H0(IDi): if E inputs a user’s identity IDi to H0, B will output a randomly chosen Qi∈G1 as the user’s public key.(ii)
H1(Pi): when E inputs a public key Pi∈G1 to H1, B outputs a randomly chosen Γi∈G1.(iii)
H2(m,U1,U2): if E inputs a message m∈{0,1}* and U1,U2∈G1, B will output an integer randomly chosen in Zq*.(iv)
H3(m,U2,U1): if E inputs a message   m∈{0,1}*, U2∈G1, and U1∈G1, B will output a random integer in Zq*.(v)
H4(ϱ): if E inputs a string ϱ∈{0,1}*, B will output an element randomly chosen in G1.(vi)
Public_Key(IDi): if E inputs a user’s identity, IDi, then B will output the user’s public key Pi.(vii)
Partial_Private_Key(IDi,Pi): if E inputs a user’s identity IDi and the user’s public key Pi, B will output the partial private key (Di0,Di1).(viii)
Secret_Key(IDi): if E inputs a user’s identity, IDi, B will output the secret key xi of user IDi to E.(ix)
Public_Key_Replacement(IDi,Pi′): when E inputs a user’s identity IDi and the user’s new public key Pi′, B will replace Pi with Pi′. The new partial private key can be obtained by querying Partial_Private_Key(IDi).(x)
Sign(IDi,m): if E inputs a user’s identity IDi and a message m, B will output a user IDi’s signature σ on m to E.Definition 5 (the CDH assumption).
We say that the(t,ε)-CDH assumption holds in G1 if no polynomial-time algorithm within running time t can solve the CDH problem with probability at least ε.Definition 6 (the unforgeability game I).
LetE1 be a polynomial-time attacker of type I. E1 interacts with a challenger B in the following game.(i)
Step 1:B runs the setup algorithm of a certificateless signature scheme with batch verification. B publishes the public parameters.(ii)
Step 2:E1 queries Partial_Private_Key, Public_Key, Public_Key_Replacement, Secret_Key, Sign, H0, H1, H2, H3, and H4 in an arbitrary sequence.(iii)
Step 3:E1 outputs n signatures σ1,…,σn on m1,…,mn corresponding to the signers ID1,…,IDn with the public keys P1,…,Pn, respectively.
E
1 wins the game if (1)
Batch_Verify((σ1,m1,ID1,P1),…,(σn,mn,IDn,Pn)) = True;(2)
there existsσy∈{σ1,…,σn} whose (IDy,my) has not been queried to Sign oracle;(3)
Partial_Private_Key(IDy,Py) has never been queried.
The scheme is (t,ε, I)-unforgeable if no polynomial-time attacker E1, with running time at most t, can win the unforgeability game I with probability at least ε.Definition 7 (the unforgeability game II).
LetE2 be a polynomial-time attacker of type II. E2 interacts with a challenger B in the following game.(i)
Step 1:B runs the setup algorithm of a certificateless signature scheme with batch verification. B publishes the public parameters and sends the master secret key to E2.(ii)
Step 2:E2 queries Partial_Private_Key, Public_Key, Public_Key_Replacement, Secret_Key, Sign, H0, H1, H2, H3, and H4 in an arbitrary sequence.(iii)
Step 3:E2 outputs n signatures σ1,…,σn on m1,…,mn corresponding to the signers ID1,…,IDn with the public keys P1,…,Pn, respectively.
E
2 wins the game if (1)
Batch_Verify((σ1,m1,ID1,P1),…,(σn,mn,IDn,Pn)) = True;(2)
there existsσy∈{σ1,…,σn} whose (IDy,my) has not been queried to Sign oracle;(3)
NeitherSecret_Key(IDy) nor Public_Key_Replacement(IDy,·,·) has been queried.
The scheme is (t,ε, II)-unforgeable if no polynomial-time attacker E2, with running time at most t, can win the unforgeability game II with probability at least ε.Definition 8 (the unforgeability game III [19]).
LetE3 be a polynomial-time attacker of type III. E3 interacts with a challenger B in the following game.(I)
Step 1:B runs the setup algorithm of a certificateless signature scheme with batch verification. B publishes the public parameters.(II)
Step 2:E3 queries Partial_Private_Key, Public_Key, Public_Key_Replacement, Secret_Key, H0, H1, H2, H3, and H4 in an arbitrary sequence.(III)
Step 3:E3 outputs a signature σ*=(V*,U1*,U2*,Py*) on a message m* for the user IDy.
E
3 wins the game if(1)
Verifying(σ*,m*,IDy,Py*)= True;(2)
UserIDy has been created, that is, Public_Key(IDy), Partial_Private_Key(IDy,Py), and Secret_Key(IDy) have been queried;(3)
Py* is different from all of the public keys Py’s returned by Public_Key(IDy) or used to query Public_Key_Replacement.
The scheme is (t,ε, III)-unforgeable if no polynomial-time attacker E3, with running time at most t, can win the unforgeability game III with probability at least ε.


## 4.2.  Formal Proofs

In this section, we will prove that our scheme is unforgeable based on the CDH assumption.Lemma 9 (the forking lemma [40]).
Let(s,m,c) be a valid signature-message triple of a signature scheme and h the hashed value of (m,c) where m is a plaintext message, c is a string, and s is called the signature part of the triple. Let A be a probabilistic polynomial-time Turning machine. Given only the public data of the signature scheme as input, if A can find, with nonnegligible probability, a valid signature-message triple (s,m,c) with h, then, with nonnegligible probability, a replay of this machine, with the same random tape and a different value returned by the random oracle, outputs two valid signature-message triples (s,m,c) with h and (s′,m,c) with h′ such that h≠h′.Lemma 10 (the splitting lemma [40]).
LetA⊂X×Y such that Pr[(x,y)∈A]≥ε. For any α<ε, define B={(x,y)∈X×Y∣Pry′∈Y[(x,y′)∈A]≥ε-α} and then the following statements hold: (1)
Pr[B]≥α,(2)
∀(x,y)∈B,Pry′∈Y[(x,y′)∈A]≥ε-α,(3)
Pr[B∣A]≥α/ε.Theorem 11.
Givenn 5-tuples (Vi,U1i,U2i,Pi,mi)’s, if e(P,∑i=1n‍wiVi)=e(Tpub,∑i=1n‍wiU1i+wih2i(Qi+Γi))e(W,∑i=1n‍wiU2i+wih3iPi) where wi is randomly chosen in Zq*, h2i=H2(mi,U1i,U2i), and h3i=H3(mi,U2i,U1i) for each i, the probability of that e(P,Vi)≠e(Tpub,U1i+h2i(Qi+Γi))e(W,U2i+h3iPi) for some i∈{1,…,n} is 1/2∣q∣.Proof.
The proof is based on [35, 37]. If e(P,Vi)≠e(Tpub,U1i+h2i(Qi+Γi))e(W,U2i+h3iPi) for some i, we have that Vi≠(ri+h2i)(λQi+λΓi)+(αi+h3i)xiW for some i. Thus, there exists ci≠0 (mod q) such that Vi=(ri+h2i)(λQi+λΓi)+(αi+h3i)xiW+ciP for some i.
LetVj=(rj+h2j)(λQj+λΓj)+(αj+h3j)xjW+cjP and cj∈{0,1,…,q-1}, ∀j∈{1,…,n}-{i}. As e(P,∑i=1n‍wiVi)=e(Tpub,∑i=1n‍wiU1i+wih2i(Qi+Γi))e(W,∑i=1n‍wiU2i+wih3iPi), w1c1+w2c2+w3c3+⋯+wncn≡0 (mod q) and thus wi=ci-1(w1c1+w2c2+⋯+wi-1ci-1+wi+1ci+1+⋯+wncn) mod q. Since wi is randomly chosen in Zq*, the probability of wi=ci-1(w1c1+w2c2+⋯+wi-1ci-1+wi+1ci+1+⋯+wncn) mod q is 1/2∣q∣, which is negligible.Theorem 12.
The proposed scheme is (t,qsign,qppk,qsk,qpkr,qpk,qh0,qh1,qh2,qh3,qh4,ε,I)-unforgeable assuming that the (t′,ε′)-CDH assumption holds in G1 where ε′≥(ε/(2qh0))(1-1/2|q|)2,  t′≈t+qsign𝒪(tsign)+qppk𝒪(tppk)+qsk𝒪(tsk)+qpkr𝒪(tpkr)+qpk𝒪(tpk)+qh0𝒪(th0)+qh1𝒪(th1)+qh2𝒪(th2)+qh3𝒪(th3)+qh4𝒪(th4)+𝒪(1), qsign, qppk, qsk, qpkr, qpk, qh0, qh1, qh2, qh3, and qh4 being the numbers of queries to Sign, Partial_Private_Key, Secret_Key, Public_Key_Replacement, Public_Key, H0, H1, H2, H3, and H4, respectively, and tsign, tppk, tsk, tpkr, tpk, th0, th1, th2, th3, and th4 being the computing time of the queries to Sign, Partial_Private_Key, Secret_Key, Public_Key_Replacement, Public_Key, H0, H1, H2, H3, and H4, respectively.Proof.
Assume that a polynomial-time attackerE1 wins the game of Definition 6 with probability being at least ε within running time t. A simulator B is given an instance of the CDH problem 〈G1,q,P,aP,bP〉, and B’s goal is to output the value of abP. We will construct B which plays the game in Definition 6 with E1 and outputs the value of abP.
Setup. B sets Tpub=bP and chooses θ∈{0,1}* randomly. Then, B publishes {G1,G2, e, q, P, θ, Tpub, H0, H1,H2,H3, H4}.
B can respond to the queries from E1 as follows.(i)
H0 query: B constructs a list, H0-list, and chooses an identity IDπ randomly. When E1 queries H0(IDi) to B, B checks whether IDi is in H0-list or not. If IDi does not exist in H0-list, then there are the following two cases. Case 1: if IDi=IDπ, B sets Qi=aP=H0(IDi) and stores (IDi,aP) in H0-list. Case 2: if IDi≠IDπ, B sets Qi=kiP=H0(IDi) where ki is randomly chosen in Zq* and stores (IDi,kiP,ki) in H0-list. However, if IDi exists in H0-list, B gets its mapping value, Qi=kiP or aP. Finally, B returns Qi.(ii)
H1 query: B constructs a list, H1-list. If E1 queries H1(Pi) to B where Pi∈G1, B checks whether Pi is in H1-list or not. If it does not exist in H1-list, B randomly chooses ρi∈Zq* and records (Pi,ρiP,ρi) in H1-list; else, B gets its mapping value, ρiP, from H1-list. Then, B returns ρiP to E1.(iii)
H2 query: B constructs H2-list. If E1 queries H2(m,U1,U2) to B, B checks whether (m,U1,U2) is in H2-list or not. If not, B randomly chooses h2∈Zq* and records ((m,U1,U2),h2) in H2-list; else, B gets its mapping value, h2, from H2-list. Then, B returns   h2 to E1.(iv)
H3 query: B constructs H3-list. When E1 queries H3(m,U2,U1) to B, B checks whether (m,U2,U1) is in H3-list or not. If not, B randomly chooses h3∈Zq* and records ((m,U2,U1),h3) in H3-list; otherwise, B gets its mapping value, h3, from H3-list. Then, B responds h3 to E1.(v)
H4 query: B constructs H4-list. If E1 queries H4 with a string ϱ to B, B checks whether ϱ is in H4-list or not. If ϱ does not exist in H4-list, then there are the following two conditions. Condition 1: if ϱ=θ, B sets W=βP=H4(ϱ) where β is randomly chosen in Zq* and stores (ϱ,βP,β) in H4-list. Condition 2: if ϱ≠θ, B sets W=Φ=H4(ϱ) where Φ is randomly chosen in G1 and stores (ϱ,Φ) in H4-list. However, if ϱ exists in H4-list, B gets its mapping value, W=Φ or βP. Finally, B returns W.(vi)
Public_Key query: B constructs a list, pk-list. When E1 queries Public_Key(IDi) to B, B looks up pk-list. If IDi is not found in pk-list, B randomly chooses xi∈Zq*, computes Pi=xiP, and stores (IDi,Pi,xi) in pk-list; otherwise, B gets Pi from pk-list. Finally, B returns Pi.(vii)
Partial_Private_Key query: if E1 queries Partial_Private_Key(IDi,Pi′) to B, B looks up H0-list, pk-list, and H1-list. If IDi=IDπ, B returns “failure.” If IDi is not found in H0-list, B queries H0(IDi) and gets ki from H0-list; else, B retrieves ki from H0-list. If IDi is not in pk-list, B queries Public_Key(IDi) and obtains Pi; otherwise, B catches Pi from pk-list. If Pi≠Pi′, B returns “failure.” Then, if Pi is not found in H1-list, B queries H1(Pi) and gets ρi; else, B retrieves ρi from H1-list. Finally, B returns (Di0=kibP,Di1=ρibP).(viii)
Secret_Key query: if E1 queries Secret_Key(IDi) to B, B looks up pk-list. If IDi is not found in pk-list, B queries Public_Key(IDi) and gets xi; if there is a record (IDi,Pi,xi), then B retrieves xi from pk-list and returns xi.(ix)
Public_Key_Replacement query: when E1 queries Public_Key_Replacement(IDi, Pi′) to B, B looks up pk-list. If IDi is not found in pk-list, B queries Public_Key(IDi). Then, B replaces the record (IDi,Pi,xi) with (IDi,Pi′,⊥) in pk-list.(x)
Sign query: when E1 queries Sign(IDi,m) to B, if IDi=IDπ, B does the following works.
(1)
Choosez, α, and h2∈Zq* randomly;(2)
computeU1=zP-h2aP and U2=αP;(3)
setH2(m,U1,U2)=h2;(4)
computeh3=H3(m,U2,U1) and W=H4(θ);(5)
computeV=zbP+h2ρibP+αβP+h3βPi;(6)
formσ=(V,U1,U2,Pi).Thus, the signature on m is σ=(V,U1,U2,Pi) and it satisfies the verifying formula in Section 3.
IfIDi≠IDπ, B can return a signature on m to E1 because B can compute all secrets of user IDi. Finally, suppose that E1 outputs, with probability at least ε, n signatures σ1,…,σn on m1,…,mn of the signers ID1,…,IDn, respectively, such that (1)
Batch_Verify((σ1,m1,ID1,P1),…,(σn,mn,IDn,Pn)) = True;(2)
there existsσy∈{σ1,…,σn} which is not the output from Sign(IDy,my);(3)
Partial_Private_Key(IDy,Py) has never been queried.
From Lemma9, we fork the sequence of signatures one time and get σ1′,…,σn′ on m1,…,mn by setting h2y′≠h2y. Thus, we randomly choose wi’s and obtain the following two equations:
(2)e(P,∑i=1n‍wiVi)=e(Tpub,∑i=1n‍wiU1i+wih2i(Qi+Γi))×e(W,∑i=1n‍wiU2i+wih3iPi),e(P,∑i=1n‍wiVi′)=e(Tpub,∑i=1n‍wiU1i′+wih2i′(Qi+Γi))×e(W,∑i=1n‍wiU2i′+wih3i′Pi)
with probability being at least ε/2 by Lemma 10, where Vy≠Vy′, U1y=U1y′, h2y≠h2y′, U2y=U2y′, and h3y=h3y′.
We assume thatIDy=IDπ. By Theorem 11, we have that
(3)e(P,Vy)=e(Tpub,U1y+h2y(Qy+Γy))×e(W,U2y+h3yPy),e(P,Vy′)=e(Tpub,U1y+h2y′(Qy+Γy))×e(W,U2y+h3yPy)
with probability being at least (ε/(2qh0))(1-1/2∣q∣)2. Thus, we can compute (h2y-h2y′)-1((Vy-Vy′)-ρyTpub), which is abP, to solve the CDH problem with ε′≥(ε/(2qh0))(1-1/2∣q∣)2 and t′≈t+qsign⁡𝒪(tsign⁡)+qppk𝒪(tppk)+qsk𝒪(tsk)+qpkr𝒪(tpkr)+qpk𝒪(tpk)+qh0𝒪(th0)+qh1𝒪(th1)+qh2𝒪(th2)+qh3𝒪(th3)+qh4𝒪(th4)+𝒪(1).Theorem 13.
The proposed scheme is (t,qsign,qppk,qsk,qpkr,qpk,qh0,qh1,qh2,qh3, qh4, ε, II)-unforgeable assuming that the (t′,ε′)-CDH assumption holds in G1 where ε′≥(ε/(2qpk))(1-1/2|q|)2,t′≈t+qsign𝒪(tsign)+qppk𝒪(tppk)+qsk𝒪(tsk)+qpkr𝒪(tpkr)+qpk𝒪(tpk)+qh0𝒪(th0)+qh1𝒪(th1)+qh2𝒪(th2)+qh3𝒪(th3)+qh4𝒪(th4)+𝒪(1), qsign, qppk, qsk, qpkr, qpk, qh0, qh1, qh2, qh3, and qh4 are the numbers of queries to Sign, Partial_Private_Key, Secret_Key, Public_Key_Replacement, Public_Key, H0, H1, H2, H3, and H4, respectively, and tsign, tppk, tsk, tpkr, tpk, th0, th1, th2, th3, and th4 are the computing time of the queries to Sign, Partial_Private_Key, Secret_Key, Public_Key_Replacement, Public_Key, H0, H1, H2, H3, and H4, respectively.Proof.
Assume that a polynomial-time attackerE2 wins the game of Definition 7 with probability at least ε within running time t. A simulator B is given an instance of the CDH problem 〈G1,q,P,aP,bP〉, and B’s goal is to output the value of abP. We will construct B which plays the game in Definition 7 with E2 and outputs the value of abP.
Setup. B sets Tpub=λP where λ is randomly chosen in Zq* and chooses θ∈{0,1}* randomly. Then, B publishes {G1,G2, e, q, P, θ, Tpub, H0, H1,H2,H3, H4} and sends λ to E2. B can respond to the queries from E2 as follows.(i)
H0 query: B constructs a list, H0-list. When E2 queries H0(IDi) to B, B checks whether IDi is in H0-list or not. If IDi does not exist in H0-list, B sets Qi=kiP=H0(IDi) where ki is a random integer in Zq* and records (IDi, kiP, ki) in H0-list; else, B gets its mapping value, kiP, from H0-list. Then, B returns  Qi=kiP to E2.(ii)
H4 query: B constructs H4-list. If E2 queries H4 with a string ϱ to B, B checks whether ϱ is in H4-list or not. If ϱ does not exist in H4-list, then there are the following two conditions. Condition 1: if ϱ=θ, B sets W=bP=H4(ϱ) and stores (ϱ,bP) in H4-list. Condition 2: if ϱ≠θ, B sets W=Φ=H4(ϱ) where Φ is randomly chosen in G1 and stores (ϱ,Φ) in H4-list. However, if ϱ exists in H4-list, B gets its mapping value, W=Φ or bP. Finally, B returns W.(iii)
The simulations forH1, H2, H3, and Public_Key_Replacement are the same as those in the proof of Theorem 12.(iv)
Public_Key query: B constructs a list, pk-list, and chooses an identity IDπ randomly. When E2 queries Public_Key(IDi) to B, B looks up pk-list. If IDi does not exist in pk-list, then there are the following two conditions. Condition 1: if IDi=IDπ, B sets Pi=aP and stores (IDi,aP) in pk-list. Condition 2: if IDi≠IDπ, B sets Pi=xiP where xi is randomly chosen in Zq* and stores (IDi,xiP,xi) in pk-list. However, if IDi exists in pk-list, B gets its mapping value, Pi=xiP or aP. Finally, B returns Pi.(v)
Partial_Private_Key query: when E2 queries Partial_Private_Key(IDi,Pi′) to B, B looks up H0-list, pk-list, and H1-list. If IDi is not found in H0-list, B queries H0(IDi) and gets ki from H0-list; else, B retrieves ki from H0-list. If IDi is not in pk-list, B queries Public_Key(IDi) and obtains Pi; otherwise, B catches Pi from pk-list. If Pi≠Pi′, B returns “failure.” Then, if Pi is not found in H1-list, B queries H1(Pi) and gets ρi; else, B retrieves ρi from H1-list. Finally, B returns (Di0=λkiP,Di1=λρiP).(vi)
Secret_Key query: when E2 queries Secret_Key(IDi) to B, B looks up pk-list. If IDi=IDπ, B returns “failure.” If IDi is not found in pk-list, B queries Public_Key(IDi) and gets xi from pk-list; else, B retrieves xi from pk-list. Finally, B returns xi.(vii)
Sign query: when E2 queries Sign(IDi,m) to B, if IDi=IDπ, B performs the following works.
(1)
choosez, α, and h3∈Zq* randomly;(2)
computeU1=zP and U2=αP-h3aP;(3)
computeh2=H2(m,U1,U2) and W=H4(θ);(4)
setH3(m,U2,U1)=h3;(5)
computeV=zλP+h2kiλP+h2ρiλP+αW;(6)
formσ=(V,U1,U2,Pi).
Therefore, the signature onm is σ=(V,U1,U2,Pi) and it meets the verifying formula in Section 3.
IfIDi≠IDπ, B can return a signature on m to E2 since B knows all secrets of user IDi. Finally, E2 outputs, with probability being at least ε, n signatures σ1,…,σn on m1,…,mn of the signers ID1,…,IDn, respectively, such that (1)
Batch_Verify((σ1,m1,ID1,P1),…,(σn,mn,IDn,Pn)) = True;(2)
there existsσy∈{σ1,…,σn} which is not the output from Sign(IDy,my);(3)
neitherSecret_Key(IDy) nor Public_Key_Replacement(IDy,·,·) has been queried.
From Lemma9, we fork the sequence of signatures one time and get σ1′,…,σn′ on m1,…,mn by setting h3y′≠h3y. Thus, we randomly choose wi’s and obtain the following two equations:
(4)e(P,∑i=1n‍wiVi)=e(Tpub,∑i=1n‍wiU1i+wih2i(Qi+Γi))×e(W,∑i=1n‍wiU2i+wih3iPi),e(P,∑i=1n‍wiVi′)=e(Tpub,∑i=1n‍wiU1i′+wih2i′(Qi+Γi))×e(W,∑i=1n‍wiU2i′+wih3i′Pi)
with probability being at least ε/2 by Lemma 10, where Vy≠Vy′, U1y=U1y′, h2y=h2y′, U2y=U2y′, and h3y≠h3y′.
We assume thatIDy=IDπ. By Theorem 11, we have that
(5)e(P,Vy)=e(Tpub,U1y+h2y(Qy+Γy))×e(W,U2y+h3yPy),e(P,Vy′)=e(Tpub,U1y+h2y(Qy+Γy))×e(W,U2y+h3y′Py)
with probability being at least (ε/(2qpk))(1-1/2|q|)2. Thus, we can compute (h3y-h3y′)-1(Vy-Vy′), which is abP, to solve the CDH problem with ε′≥(ε/(2qpk))(1-1/2|q|)2 and t′≈t+qsign⁡𝒪(tsign⁡)+qppk𝒪(tppk)+qsk𝒪(tsk)+qpkr𝒪(tpkr)+ qpk𝒪(tpk)+qh0𝒪(th0)+qh1𝒪(th1)+qh2𝒪(th2)+qh3𝒪(th3)+qh4𝒪(th4)+𝒪(1).Theorem 14.
The proposed scheme is (t,qppk,qsk,qpkr,qpk,qh0,qh1,qh2,qh3, qh4, ε, III)-unforgeable assuming that the (t′,ε′)-CDH assumption holds in G1 with ε′≥ε/(2qh1-max⁡),t′≈t+qppk𝒪(tppk)+qsk𝒪(tsk)+qpkr𝒪(tpkr)+qpk𝒪(tpk)+qh0𝒪(th0)+qh1𝒪(th1)+qh2𝒪(th2)+qh3𝒪(th3)+qh4𝒪(th4)+𝒪(1),(2qh1-max⁡) being the possibly maximal number of queries to H1, qppk, qsk, qpkr, qpk, qh0, qh1, qh2, qh3, and qh4 being the numbers of queries to Partial_Private_Key, Secret_Key, Public_Key_Replacement, Public_Key, H0, H1, H2, H3, and H4, respectively, and tsign, tppk, tsk, tpkr, tpk, th0, th1, th2, th3, and th4 being the computing time of the queries to Sign, Partial_Private_Key, Secret_Key, Public_Key_Replacement, Public_Key, H0, H1, H2, H3, and H4, respectively.Proof.
Assume that a polynomial-time attackerE3 wins the game of Definition 8 with probability being at least ε within running time t. A simulator B is given an instance of the CDH problem 〈G1,q,P,aP,bP〉, and B’s goal is to output abP. We will construct B which plays the game in Definition 8 with E3 and outputs abP.
Setup. B sets Tpub=bP and chooses θ∈{0,1}* randomly. Then, B publishes {G1,G2, e, q, P, θ, Tpub, H0, H1,H2,H3, H4}. B can respond to the queries from E3 as follows.
The simulation forH0 is identical to that in the proof of Theorem 13. Consider the following.(i)
H1 query: B constructs a list, H1-list, and then chooses π∈{1,…,qh1-max⁡} at random and sets an index j=0. When E3 queries H1(Pi) to B, B checks whether Pi is in H1-list or not. If Pi does not exist in H1-list, B computes j=j+1 and there are the following two cases. Case 1: if j=π, B sets H1(Pi)=aP and stores (Pi,aP) in H1-list. Case 2: if j≠π, B sets H1(Pi)=ρiP where ρi is randomly chosen in Zq* and stores (Pi,ρiP,ρi) in H1-list. Besides, if Pi exists in H1-list, B gets its mapping value, ρiP or aP. Finally, B returns ρiP or aP.(ii)
H4 query: B constructs H4-list. If E3 queries H4 with a string ϱ to B, B checks whether ϱ is in H4-list or not. If ϱ does not exist in H4-list, then there are the following two conditions. Condition 1: if ϱ=θ, B sets W=βP=H4(ϱ) where β is randomly chosen in Zq* and stores (ϱ,βP,β) in H4-list. Condition 2: if ϱ≠θ, B sets W=Φ=H4(ϱ) where Φ is randomly chosen in G1 and stores (ϱ,Φ) in H4-list. However, if ϱ exists in H4-list, B gets its mapping value, W=Φ or βP. Finally, B returns W.(iii)
Public_Key query: B constructs a list, pk-list. When E3 queries Public_Key(IDi) to B, B looks up pk-list. If IDi is not found in pk-list, B does the following works. B computes Pi=xiP where xi is randomly chosen in Zq*. B queries H1 with Pi. If H1(Pi)=aP, B returns “failure”; otherwise, B stores (IDi,Pi,xi) in pk-list. Besides, if IDi is found in pk-list, B gets Pi from pk-list. Finally, B returns   Pi to E3.(iv)
Partial_Private_Key query: when E3 queries Partial_Private_Key(IDi,Pi′) to B, B looks up H0-list, pk-list, and H1-list. If IDi is not found in H0-list, B queries H0(IDi) and gets ki from H0-list; else, B retrieves ki from H0-list. If IDi is not found in pk-list, B queries Public_Key with IDi and obtains Pi from pk-list; otherwise, B catches Pi from pk-list. If Pi≠Pi′, B returns “failure.” Then, B gets ρi from H1-list. Finally, B returns (Di0=kibP,Di1=ρibP).(v)
H2, H3, Secret_Key, and Public_Key_Replacement queries are the same as those in the proof of Theorem 12. Finally, E3 outputs, with probability at least ε, a signature σ*=(V*,U1*,U2*,Py*) on a message m* for the user IDy such that
(1)
Verifying(σ*,m*,IDy,Py*)= True;(2)
userIDy has been created;(3)
Py* is different from all of the public keys Py*’s returned by Public_Key(IDy) or used to query Public_Key_Replacement.
From Lemma9, we fork the sequence of signatures one time and get σ′=(V′,U1′,U2′,Py*) on m* by setting h2′≠h2*. Thus, we obtain the following two equations:
(6)e(P,V*)=e(Tpub,U1*+h2*(Qy+Γy))e(W,U2*+h3*Py*)e(P,V′)=e(Tpub,U1′+h2′(Qy+Γy))e(W,U2′+h3′Py*)
with a probability at least ε/2 by Lemma 10, where V*≠V′, U1*=U1′, h2*≠h2′, U2*=U2′, and h3*=h3′.
IfH1(Py*)=aP, B can get abP=(h2*-h2′)-1(V*-V′)-kyTpub and solve the CDH problem.
The success probability isε′≥ε/(2qh1-max⁡) with the computing time t′≈t+qsign⁡𝒪(tsign⁡)+qppk𝒪(tppk)+qsk𝒪(tsk)+qpkr𝒪(tpkr)+qpk𝒪(tpk)+qh0𝒪(th0)+qh1𝒪(th1)+qh2𝒪(th2)+qh3𝒪(th3)+qh4𝒪(th4)+𝒪(1).
By Theorem14, a user cannot produce a signature with a new public-secret key pair, which is different from his own one, without the corresponding partial private key being generated from the master secret key. Therefore, if there exist two valid signatures of a user with different public key, the user can prove to anyone that PKG is misbehaving, which means that our scheme achieves Girault’s level-3 security.


## 5. Discussions

The comparisons between our scheme and [5, 7, 11, 13, 14, 16, 27–34] are shown in Table 1. Although our proposed scheme is not the most efficient, it satisfies the property of Girault’s level-3 security with formal proofs.Table 1
The comparisons between [5, 7, 11, 13, 14, 16, 27–34] and our scheme.
Signing phase
Verification phase
Security level
Formally proved
Security model
[5]
n
T
s
2
n
T
e
+
2
n
T
a
Girault’s level-3
Yes
ROM
≈
2400
n
t
m
[7]
2
n
T
s
+
2
n
T
h
+
n
T
a
(
2
n
+
1
)
T
p
+
n
T
a
Girault’s level-2
Yes
ROM
+
n
T
s
+
2
n
T
h
≈
(
2475
n
+
1200
)
t
m
[27]
2
n
T
s
2
T
p
+
3
n
T
s
+
T
a
Girault’s level-1
Yes
ROM
≈
(
87
n
+
480
)
t
m
[28] Cha-based
2
n
T
s
2
T
p
+
2
n
T
s
+
n
T
a
Girault’s level-1
No
ROM
+
n
t
m
≈
(
59
n
+
480
)
t
m
[28] Waters-based
(
z
+
2
)
T
s
+
(
z
+
1
)
T
a
3
T
p
+
2
n
(
z
+
1
)
T
s
Girault’s level-1
No
STD
+
n
(
2
z
+
3
)
T
a
≈
(
58
n
(
z
+
1
)
+
720
)
t
m
[28] Hess-based
n
T
p
+
3
n
T
s
+
n
T
a
2
T
p
+
3
n
T
s
Girault’s level-1
No
ROM
+
n
t
m
≈
(
88
n
+
480
)
t
m
[29] Geng-based
3
n
T
s
+
n
T
a
+
n
t
m
3
T
p
+
4
n
T
s
Girault’s level-2
No
ROM
+
(
n
-
1
)
T
a
+
2
n
t
m
≈
(
118
n
+
720
)
t
m
[32]
2
n
T
p
+
11
n
T
s
+
4
n
(
T
a
+
t
m
)
2
T
p
+
13
n
T
s
Girault’s level-1
No
ROM
+
8
T
a
≈
(
377
n
+
480
)
t
m
[11]
2
n
T
s
(
n
+
1
)
T
p
Girault’s level-2
No
—
≈
(
1200
n
+
1200
)
t
m
[13]
n
t
e
(
n
+
1
)
T
e
+
n
t
e
Girault’s level-3
Yes
ROM
≈
(
1200
n
+
1440
)
t
m
[30]
(
k
+
4
)
n
T
s
+
(
k
+
2
)
n
T
a
5
T
p
+
4
n
T
s
Girault’s level-1
No
—
+
4
(
n
-
1
)
T
a
≈
(
116
n
+
1200
)
t
m
[14]
5
n
T
s
+
n
T
a
(
n
+
1
)
T
p
+
3
n
T
a
+
2
n
T
s
Girault’s level-2
Yes
ROM
≈
(
1258
n
+
1200
)
t
m
[33]
2
n
T
p
+
13
n
T
s
+
4
n
T
a
+
8
n
t
m
2
T
p
+
14
n
T
s
Girault’s level-1
No
ROM
+
7
n
T
a
+
2
n
t
m
≈
(
408
n
+
480
)
t
m
[34]
2
n
T
p
+
10
n
T
s
+
6
n
T
a
+
7
n
t
m
2
T
p
+
13
n
T
s
Girault’s level-1
No
—
+
n
(
T
a
+
t
m
)
≈
(
378
n
+
480
)
t
m
[16]
3
n
t
m
+
5
n
t
e
(
3
n
+
1
)
T
p
+
n
t
e
Girault’s level-2
Yes
STD
≈
(
3601
n
+
1200
)
t
m
[31]
n
(
T
s
+
T
a
)
3
T
p
+
n
T
s
Girault’s level-1
No
—
+
n
T
h
+
3
n
T
a
≈
(
52
n
+
720
)
t
m
Ours
4
n
T
s
+
n
T
h
+
3
n
T
a
3
T
p
+
3
n
T
s
Girault’s level-3
Yes
ROM
+
2
n
T
h
+
n
T
a
≈
(
133
n
+
720
)
t
m
According to [41–43], Tp≈5te,Ts≈29tm,  Th≈23tm,Ta≈0.12tm, and te≈240tm.
z: the number of ℓ-bit chunks in Waters scheme; k: the number of registered users in Qin scheme; n: the number of individual signatures; Tp: the time cost of a pairing operation; Ts: the time cost of a scalar multiplication in G1; Th: the time cost of a map-to-point hash operation; Ta: the time cost of a point addition operation; tm: the time cost of a modular multiplication in Zp; th: the time cost of a hash operation; ROM: random oracle model; STD: standard model.


## 6. Conclusions

In this paper, we have proposed a certificateless signature scheme with fast batch verification and it satisfies Girault’s level-3 security, where almost all existing signatures for batch verification reach Girault’s level-1 security and only one reaches Girault's level-2 security. Finally, we have formally demonstrated that the proposed scheme is unforgeable and achieves Girault’s level-3 security based on the CDH problem.



---

*Source: 854135-2014-04-16.xml*