# Strongly Unforgeable Certificateless Signature Resisting Attacks from Malicious-But-Passive KGC

Authors: Wenjie Yang; Jian Weng; Weiqi Luo; Anjia Yang
Journal: Security and Communication Networks
 (2017)

---

## Abstract

In digital signature, strong unforgeability requires that an attacker cannot forge a new signature on any previously signed/new messages, which is attractive in both theory and practice. Recently, a strongly unforgeable certificateless signature (CLS) scheme without random oracles was presented. In this paper, we firstly show that the scheme fails to achieve strong unforgeability by forging a new signature on a previously signed message under its adversarial model. Then, we point out that the scheme is also vulnerable to the malicious-but-passive key generation center (MKGC) attacks. Finally, we propose an improved strongly unforgeable CLS scheme in the standard model. The improved scheme not only meets the requirement of strong unforgeability but also withstands the MKGC attacks. To the best of our knowledge, we are the first to prove a CLS scheme to be strongly unforgeable against the MKGC attacks without using random oracles.


---

## Body

## 1. Introduction

In 1984, Shamir brought in the notion of identity-based public key cryptography [1] to avert the heavy certificate management problem in traditional certificate-based public key systems. In this scenario, a fully trusted key generation center (KGC) takes care of deriving the secret key from an entity’s public identity information (e.g., personal identity number) which is directly used as the corresponding public key. From then on, lots of efforts have been made in this area [2–4]. However, these identity-based schemes are subject to the key escrow problem; that is, the KGC owns any entity’s secret key and, therefore, can do anything on behalf of the entity whereas not being detected.In order to avoid this problem, Al-Riyami and Paterson introduced a new notion named certificateless public key cryptography (CL-PKC) and formalized its security model [5], in which the KGC is considered as a semitrusted third party and only produces a partial secret key for an entity using its own master secret key, and each entity independently picks an extra secret value for themselves. As a consequence, the entity’s secret key consists of the partial secret key and the secret value, which make an attacker not do anything instead of the entity if the attacker just has one of the two parts. In this scenario [5], the attacks only knowing the entity’s secret value are denoted by public key replacement (PKR) attacks while the others merely obtaining the master secret key are denoted by honest-but-curious key generation center (HKGC) attacks. Before long, Au et al. addressed a malicious-but-passive key generation center (MKGC) attacks [6], in which an attacker can set some trapdoors in the system parameters adaptively rather than only being told the master secret key like in HKGC attacks. So far, CL-PKC has received many attention under those adversarial models.As an important branch in certificateless settings, many studies have focused on certificateless signature (CLS) schemes [7–13]. Nevertheless, most of these early CLS schemes are only provably secure in the random oracle model [14], whose security may not be able to remain when the random oracle is instantiated with a concrete hash function. To fill the gap, Liu et al. proposed the first CLS scheme secure in the standard model [15] and then some modified schemes were put forward in [16–23]. Nevertheless, all of them only were proven to be secure against PKR attacks and HKGC attacks. Although some of them like [19, 22, 23] have been indicated to be secure against MKGC attacks, the authors do not provide a formal security proof under MKGC attacks without random oracles. Therefore, it is still an unresolved problem to construct a concrete CLS scheme provably secure against MKGC attacks in the standard model.Recently, Hung et al. gave a certificateless signature scheme (HT scheme, for short) [21] and discussed its security under PKR attacks and HKGC attacks. They claimed that no attacker can forge a valid signature on a message, even given some previous signatures on the message. In other words, they stated that their scheme is strongly unforgeable under their security model. In this paper, we firstly illustrate that the HT scheme does not meet strong unforgeability as they claimed, by forging a new valid signature on any previously signed message. Further, we show that the HT scheme suffers from MKGC attacks by giving a concrete attack. At last, we propose an improved certificateless signature scheme which not only is strongly unforgeable but also resists MKGC attacks in the standard model.This paper is organized as follows. In Section2, we give some preliminaries. In Section 3, we review the HT scheme and present our attacks. In Section 4, we describe two building blocks based on which we then construct an improved strongly secure certificateless signature scheme in the standard model. Finally, the conclusion is given in Section 5.


## 2. Preliminaries

### 2.1. Bilinear Pairings and Complexity Assumption

In this paper, we adopt the standard term about bilinear pairings described in [21]. Here, (q,G1,G2,e^,g) is a concrete instance, where q denotes a big prime, G1 and G2 denote two q order cyclic groups, e^ denotes an admissible bilinear mapping G1×G1→G2, and g denotes a generator in G1.Discrete Logarithm (DL) Assumption. Given 〈G1,g,h〉, the DL problem is to find the integer a such that h=ga. If the DL problem cannot be solved in polynomial time, the DL assumption holds.Computational Diffie-Hellman (CDH) Assumption. Given 〈G1,g,ga,gb〉, the CDH problem is to compute group element gab. If the CDH problem cannot be solved in polynomial time, the CDH assumption holds.


### 2.2. Collision-Resistant Hash Function (CRHF) Assumption

LetH={Hk} be a keyed hash family of functions Hk:{0,1}∗→{0,1}n indexed by k∈K. We say that algorithm A has advantage ϵ in breaking the collision resistance of H if (1)Pr⁡Ak=m0,m1:m0≠m1,Hkm0=Hkm1>ϵ, where the probability is taken over the random choice of k∈K and the random bits of A. Here, a hash family H is (t,ϵ)-collision-resistant if no t-time adversary has advantage at least ϵ in breaking the collision resistance of H.


### 2.3. Framework and Security Model

The five algorithms below which can be run in polynomial time comprise a certificateless signature scheme:(i)
Setup: when receiving a security parameter ψ, the algorithm outputs the master secret key msk and system parameters sp. sp is available for all the other algorithms.(ii)
PSKExt: when receiving the master secret key msk and an entity e, the algorithm outputs the partial secret key pske and sends it over a secure channel to the entity.(iii)
SetUKey: when receiving an entity e, this algorithm outputs the secret key ske and public key pke. Note that ske is composed of sve and pske, where sve denotes the secret value and is picked by the entity itself independently.(iv)
Sign: when receiving an entity’s secret key ske and a message m, this algorithm outputs a signature σ.(v)
Verify: when receiving a signature σ, a message m, and an entity public key pke, this algorithm outputs either “accept” or “reject” relying on the signature validity.Like [11, 21], two types of adversaries are taken into account in the above CLS definition. The first is a public key replacement (PKR) attacker who knows the targeted entity secret value but cannot request the entity partial secret key. The other is an honest-but-curious KGC (HKGC) attacker that is allowed to obtain the master secret key but cannot know the targeted entity secret value. Here, the strong security of a CLS scheme is captured by means of Games 1 and 2 between a challenger C and an attacker A∈{A1,A2}.Game 1 (for PKR attacker)
(i)
Init: given a security parameter ψ,  C invokesSetup to produce the master secret key msk and system parameters sp. sp is given to A and msk is kept by itself.
(ii)
Queries: in this phase, A runs the following queries adaptively:
O
p
k
(
e
): receiving an entity e,  C invokesSetUkey to obtain the entity public key pke and returns it to A.
O
r
e
p
(
e
,
p
k
e
′
): receiving a new entity public key pke′,  C finds and updates the corresponding item for the entity e.
O
p
s
k
(
e
): receiving an entity e,  C invokesPSKExt to obtain the entity partial secret key pske and returns it to A.
O
s
k
(
e
): receiving an entity e,  C invokesSetUkey to obtain the entity secret key ske and returns it to A. Here, C returns ⊥ if the entity e has already appeared in Orep(e,pke′).
O
s
i
g
n
(
e
,
m
): receiving an entity e and a message m, C invokesSetUkey to obtain ske and then performsSign to generate the signature σ for m under ske. At last, C returns it to A.
(iii)
Forgery: A returns (σ∗,e∗,m∗) and wins if the following conditions hold:
(1)
σ
∗ is a valid signature of m∗ on e∗.
(2)
e
∗ is not requested in Opsk(e) and Osk(e).
(3)
(
σ
∗
,
e
∗
,
m
∗
) is not an output in Osign(e,m).Game 2 (for HKGC attacker)
(i)
Setup: given a security parameter ψ,  C invokesSetup to produce the master secret key msk and system parameters sp. Both msk and sp are given to A.
(ii)
Queries: here, A may request any oracles defined inGame 1, except for Orep(e,pke′) and Opsk(e), in an adaptive manner. Note that it is unreasonable to ask C to respond to the signing queries if pke has been replaced.
(iii)
Forgery: A outputs (σ∗,e∗,m∗) and wins if the following conditions hold:
(1)
σ
∗ is a valid signature of m∗ on e∗.
(2)
e
∗ is not requested in Orep(e,pke′) and Osk(e).
(3)
(
σ
∗
,
e
∗
,
m
∗
) is not an output in Osign(e,m).Au et al. illustrated the definition about malicious-but-passive KGC (MKGC) attacker, which is a stronger and more realistic security requirement. This MKGC may embed extra trapdoors in their system parameters before runningPSKExt. To capture MKGC attacks, the followingSetup algorithm is adopted inGame 2.(i)
Setup: C invokes A to initialize the system public/secret parameters (sp,msk). Here, to mount an attack more easily, A is allowed to set some trapdoors during the initialization phase.Definition 1.
If none of the adversaries can win the above two games with a nonnegligible advantage, in a probabilistic polynomial time (PPT), the signature scheme in certificateless settings is strongly unforgeable against adaptive chosen message attacks.


## 2.1. Bilinear Pairings and Complexity Assumption

In this paper, we adopt the standard term about bilinear pairings described in [21]. Here, (q,G1,G2,e^,g) is a concrete instance, where q denotes a big prime, G1 and G2 denote two q order cyclic groups, e^ denotes an admissible bilinear mapping G1×G1→G2, and g denotes a generator in G1.Discrete Logarithm (DL) Assumption. Given 〈G1,g,h〉, the DL problem is to find the integer a such that h=ga. If the DL problem cannot be solved in polynomial time, the DL assumption holds.Computational Diffie-Hellman (CDH) Assumption. Given 〈G1,g,ga,gb〉, the CDH problem is to compute group element gab. If the CDH problem cannot be solved in polynomial time, the CDH assumption holds.


## 2.2. Collision-Resistant Hash Function (CRHF) Assumption

LetH={Hk} be a keyed hash family of functions Hk:{0,1}∗→{0,1}n indexed by k∈K. We say that algorithm A has advantage ϵ in breaking the collision resistance of H if (1)Pr⁡Ak=m0,m1:m0≠m1,Hkm0=Hkm1>ϵ, where the probability is taken over the random choice of k∈K and the random bits of A. Here, a hash family H is (t,ϵ)-collision-resistant if no t-time adversary has advantage at least ϵ in breaking the collision resistance of H.


## 2.3. Framework and Security Model

The five algorithms below which can be run in polynomial time comprise a certificateless signature scheme:(i)
Setup: when receiving a security parameter ψ, the algorithm outputs the master secret key msk and system parameters sp. sp is available for all the other algorithms.(ii)
PSKExt: when receiving the master secret key msk and an entity e, the algorithm outputs the partial secret key pske and sends it over a secure channel to the entity.(iii)
SetUKey: when receiving an entity e, this algorithm outputs the secret key ske and public key pke. Note that ske is composed of sve and pske, where sve denotes the secret value and is picked by the entity itself independently.(iv)
Sign: when receiving an entity’s secret key ske and a message m, this algorithm outputs a signature σ.(v)
Verify: when receiving a signature σ, a message m, and an entity public key pke, this algorithm outputs either “accept” or “reject” relying on the signature validity.Like [11, 21], two types of adversaries are taken into account in the above CLS definition. The first is a public key replacement (PKR) attacker who knows the targeted entity secret value but cannot request the entity partial secret key. The other is an honest-but-curious KGC (HKGC) attacker that is allowed to obtain the master secret key but cannot know the targeted entity secret value. Here, the strong security of a CLS scheme is captured by means of Games 1 and 2 between a challenger C and an attacker A∈{A1,A2}.Game 1 (for PKR attacker)
(i)
Init: given a security parameter ψ,  C invokesSetup to produce the master secret key msk and system parameters sp. sp is given to A and msk is kept by itself.
(ii)
Queries: in this phase, A runs the following queries adaptively:
O
p
k
(
e
): receiving an entity e,  C invokesSetUkey to obtain the entity public key pke and returns it to A.
O
r
e
p
(
e
,
p
k
e
′
): receiving a new entity public key pke′,  C finds and updates the corresponding item for the entity e.
O
p
s
k
(
e
): receiving an entity e,  C invokesPSKExt to obtain the entity partial secret key pske and returns it to A.
O
s
k
(
e
): receiving an entity e,  C invokesSetUkey to obtain the entity secret key ske and returns it to A. Here, C returns ⊥ if the entity e has already appeared in Orep(e,pke′).
O
s
i
g
n
(
e
,
m
): receiving an entity e and a message m, C invokesSetUkey to obtain ske and then performsSign to generate the signature σ for m under ske. At last, C returns it to A.
(iii)
Forgery: A returns (σ∗,e∗,m∗) and wins if the following conditions hold:
(1)
σ
∗ is a valid signature of m∗ on e∗.
(2)
e
∗ is not requested in Opsk(e) and Osk(e).
(3)
(
σ
∗
,
e
∗
,
m
∗
) is not an output in Osign(e,m).Game 2 (for HKGC attacker)
(i)
Setup: given a security parameter ψ,  C invokesSetup to produce the master secret key msk and system parameters sp. Both msk and sp are given to A.
(ii)
Queries: here, A may request any oracles defined inGame 1, except for Orep(e,pke′) and Opsk(e), in an adaptive manner. Note that it is unreasonable to ask C to respond to the signing queries if pke has been replaced.
(iii)
Forgery: A outputs (σ∗,e∗,m∗) and wins if the following conditions hold:
(1)
σ
∗ is a valid signature of m∗ on e∗.
(2)
e
∗ is not requested in Orep(e,pke′) and Osk(e).
(3)
(
σ
∗
,
e
∗
,
m
∗
) is not an output in Osign(e,m).Au et al. illustrated the definition about malicious-but-passive KGC (MKGC) attacker, which is a stronger and more realistic security requirement. This MKGC may embed extra trapdoors in their system parameters before runningPSKExt. To capture MKGC attacks, the followingSetup algorithm is adopted inGame 2.(i)
Setup: C invokes A to initialize the system public/secret parameters (sp,msk). Here, to mount an attack more easily, A is allowed to set some trapdoors during the initialization phase.Definition 1.
If none of the adversaries can win the above two games with a nonnegligible advantage, in a probabilistic polynomial time (PPT), the signature scheme in certificateless settings is strongly unforgeable against adaptive chosen message attacks.


## 3. Analysis of HT Scheme

### 3.1. Review on HT Scheme

Here, we restate HT scheme [21] by the following five algorithms:(i)
Setup: given an instance (q,G1,G2,e^,g), KGC firstly picks α∈Zp∗ at random and computes g1=gα∈G1 and then sets the master secret key msk=g2α, where g2∈G1. Furthermore, KGC randomly chooses e1,e2,…,ene,e′,s1,s2,…,snv,s′,t1,t2,…,tnv,t′,w1, w2,…,wnw,w′∈G1 and sets four vectors e→={ei}i=1ne,  s→={sj}j=1nv,  t→={tj}j=1nv, and w→={wk}j=knw, respectively. Next, KGC selects five classical collision-resistant hash functions H1:{0,1}∗→{0,1}ne,  H2,H3:G1×G1→{0,1}nv, H4:{0,1}∗→{0,1}nw, and H5:{0,1}∗→Zp∗, where ne,  nv, and nw are fixed lengths. Finally, KGC publishes sp=(G1,G2,e^,g,g1,g2,e′,e→,s′,s→,t′,t→,w′,w→,H1,H2, H3,H4,H5).(ii)
PSKExt: let ve→=H1(e)=(ve1,ve2,…,vene) be a bit string from hashing an entity e. Next, KGC randomly picks re from Zp∗ and computes pske=(pske1,pske2)=(g2αEre,gre), where E=e′∏i=1neeivei. Finally, KGC secretly transmits pske to the entity.(iii)
SetUkey: given an entity e, this algorithm firstly chooses two random secret values θ1,θ2∈Zp∗, generates the entity public key pke=(pke1,pke2)=(gθ1,gθ2), and then computes vs→=H2(pke1,pke2)=(vs1,…,vsnv) and vt→=H3(pke1,pke2)=(vt1,…,vtnv), where vs→ and vt→ are two bit strings of length nv. Finally, the entity secret value is set to sve=g2θ1Sθ1Tθ2, where S=s′∏j=1nvsjvsj and T=t′∏j=1nvtjvtj. Here, ske=(sve,pske).(iv)
Sign: given a message m, an entity public key pke, and an entity secret key ske, this algorithm randomly selects rw∈Zp∗, and computes vw→=H4(m)=(vw1,vw2,…,vwnw) and h=H5(m∥grw). Then, the signature σ is set by computing (σ1,σ2,σ3)=(pske1h(sve)hWrw,pske2h,grw), where W=(w′∏k=1nwwkvwk).(v)
Verify: given σ on m under e with pke, this algorithm can verify σ’s validity by the following equation: (2)e^σ1,g=?e^g1,g2he^σ2,Ee^pke1,g2She^pke2,The^σ3,W, where h=H5(m∥σ3),  E=e′∏i=1neeivei,  S=s′∏j=1nvsjvsj,  T=t′∏j=1nvtjvtj, and W=(w′∏k=1nwwkvwk).


### 3.2. Attacks on HT Scheme

#### 3.2.1. Strong Forgery Attack

Here, we indicate that an attackerA generates a new forgery σ′ from an existing signature σ on m by interacting with the challenger C.Stage 1.
C normally invokes theSetup algorithm to produce msk=g2α and sp=(G1,G2,e^,g,g1,g2,e′,e→,s′,s→,t′,t→,w′,w→,H1,H2, H3,H4,H5). Here, C sends sp to A and keeps msk by itself.Stage 2.
Given a target entitye and a message m, C first invokes thePSKExt andSetUkey algorithms to generate the entity secret key (pske1,pske2,sve)=(g2αEre,gre,g2θ1Sθ1Tθ2) and then invokes theSign algorithm to obtain a signature σ of m on e. Obviously, the signature concrete forms are (σ1,σ2,σ3)=(pske1h(sve)hWrw,pske2h,grw), where h=H3(m∥grw).Stage 3.
In order to generateσ′ for m under e,  A randomly picks re′∈Zp∗ and sets σ1′=σ1Ere′h=g2αhE(re+re′)hsvehWrw,  σ2′=σ2gre′h=g(re+re′)h, and σ3′=σ3.It is clear thatσ′ is a new valid signature for m on e with pke since (3)e^σ1′,g=e^g2αhEre+re′hsvehWrw,g=e^g2αh,ge^Ere+re′h,ge^g2Sθ1hTeθ2h,ge^Wrw,g=e^g1,g2he^E,σ2′e^pke1,g2She^pke2,The^W,σ3′.Remark 2.
We notice that there is a flaw in Hung et al.’s security proof. More specifically, when receiving a signing query on(m,e), C first picks rw∈Zp∗ at random and then sets the hash value h=H5(m∥grw) to successfully compute the simulated signature σ=(σ1,σ2,σ3). According to Hung et al.’s simulation process, we know that σ3=grw′, where rw′=rw-θ1hQ(vs→)/K(vw→),  rw-ah+θ1hQ(vs→)/K(vw→), or rw-ah/K(vw→). Obviously, the verification equation e^(σ1,g)=?e^(g1,g2)h′e^(σ2,E)e^(pke1,g2S)h′e^(pke2,T)h′e^(σ3,W) is always not true since h≠h′, where h′=H5(m∥σ3). That is to say, C cannot always give a valid response to a signing query required by an attacker A with nonnegligible probability.


#### 3.2.2. MKGC Attack

Here, we will show that the HT scheme cannot capture MKGC attacks by an interaction betweenC and A as follows.Stage 1.
Here,A is responsible for initializing the system parameters and sends them to C. In particular, A adaptively sets the parameters g2=gβ,s′=gx′,s1=gx1,…,sn=gxnv,t′=gy′,t1=gy1,…,tn=gynv, where β,x′,x1,…,xnv,y′,y1,…,ynv∈Zp∗.Stage 2.
In the queries phase,A can obtain the target entity public key pke=(pke1,pke2)=(gθ1,gθ2). Next, A derives the corresponding secret value sve=g2θ1Sθ1Tθ2 by computing g2θ1=pke1β, Sθ1=pke1x′∑j=1nkxjvsj, and Tθ2=pke2y′∑j=1nkyjvtj, where vs→=H2(pke1,pke2)=(vs1,…,vsnk) and vt→=H3(pke1,pke2)=(vt1,…,vtnk).Stage 3.
Now,A can recover the entity full secret key (pske,sve) and sign any message m instead of the targeted entity.Remark 3.
In MKGC attacks, the KGC can adaptively set some trapdoor in the system parameters during the setup phase which may enhance its attack success probability. Obviously, in the security proof [21], the attacker passively received the master secret key and public parameters generated by the challenger like all the previous schemes [15–23], which did not consider how to capture the MKGC attacks.


## 3.1. Review on HT Scheme

Here, we restate HT scheme [21] by the following five algorithms:(i)
Setup: given an instance (q,G1,G2,e^,g), KGC firstly picks α∈Zp∗ at random and computes g1=gα∈G1 and then sets the master secret key msk=g2α, where g2∈G1. Furthermore, KGC randomly chooses e1,e2,…,ene,e′,s1,s2,…,snv,s′,t1,t2,…,tnv,t′,w1, w2,…,wnw,w′∈G1 and sets four vectors e→={ei}i=1ne,  s→={sj}j=1nv,  t→={tj}j=1nv, and w→={wk}j=knw, respectively. Next, KGC selects five classical collision-resistant hash functions H1:{0,1}∗→{0,1}ne,  H2,H3:G1×G1→{0,1}nv, H4:{0,1}∗→{0,1}nw, and H5:{0,1}∗→Zp∗, where ne,  nv, and nw are fixed lengths. Finally, KGC publishes sp=(G1,G2,e^,g,g1,g2,e′,e→,s′,s→,t′,t→,w′,w→,H1,H2, H3,H4,H5).(ii)
PSKExt: let ve→=H1(e)=(ve1,ve2,…,vene) be a bit string from hashing an entity e. Next, KGC randomly picks re from Zp∗ and computes pske=(pske1,pske2)=(g2αEre,gre), where E=e′∏i=1neeivei. Finally, KGC secretly transmits pske to the entity.(iii)
SetUkey: given an entity e, this algorithm firstly chooses two random secret values θ1,θ2∈Zp∗, generates the entity public key pke=(pke1,pke2)=(gθ1,gθ2), and then computes vs→=H2(pke1,pke2)=(vs1,…,vsnv) and vt→=H3(pke1,pke2)=(vt1,…,vtnv), where vs→ and vt→ are two bit strings of length nv. Finally, the entity secret value is set to sve=g2θ1Sθ1Tθ2, where S=s′∏j=1nvsjvsj and T=t′∏j=1nvtjvtj. Here, ske=(sve,pske).(iv)
Sign: given a message m, an entity public key pke, and an entity secret key ske, this algorithm randomly selects rw∈Zp∗, and computes vw→=H4(m)=(vw1,vw2,…,vwnw) and h=H5(m∥grw). Then, the signature σ is set by computing (σ1,σ2,σ3)=(pske1h(sve)hWrw,pske2h,grw), where W=(w′∏k=1nwwkvwk).(v)
Verify: given σ on m under e with pke, this algorithm can verify σ’s validity by the following equation: (2)e^σ1,g=?e^g1,g2he^σ2,Ee^pke1,g2She^pke2,The^σ3,W, where h=H5(m∥σ3),  E=e′∏i=1neeivei,  S=s′∏j=1nvsjvsj,  T=t′∏j=1nvtjvtj, and W=(w′∏k=1nwwkvwk).


## 3.2. Attacks on HT Scheme

### 3.2.1. Strong Forgery Attack

Here, we indicate that an attackerA generates a new forgery σ′ from an existing signature σ on m by interacting with the challenger C.Stage 1.
C normally invokes theSetup algorithm to produce msk=g2α and sp=(G1,G2,e^,g,g1,g2,e′,e→,s′,s→,t′,t→,w′,w→,H1,H2, H3,H4,H5). Here, C sends sp to A and keeps msk by itself.Stage 2.
Given a target entitye and a message m, C first invokes thePSKExt andSetUkey algorithms to generate the entity secret key (pske1,pske2,sve)=(g2αEre,gre,g2θ1Sθ1Tθ2) and then invokes theSign algorithm to obtain a signature σ of m on e. Obviously, the signature concrete forms are (σ1,σ2,σ3)=(pske1h(sve)hWrw,pske2h,grw), where h=H3(m∥grw).Stage 3.
In order to generateσ′ for m under e,  A randomly picks re′∈Zp∗ and sets σ1′=σ1Ere′h=g2αhE(re+re′)hsvehWrw,  σ2′=σ2gre′h=g(re+re′)h, and σ3′=σ3.It is clear thatσ′ is a new valid signature for m on e with pke since (3)e^σ1′,g=e^g2αhEre+re′hsvehWrw,g=e^g2αh,ge^Ere+re′h,ge^g2Sθ1hTeθ2h,ge^Wrw,g=e^g1,g2he^E,σ2′e^pke1,g2She^pke2,The^W,σ3′.Remark 2.
We notice that there is a flaw in Hung et al.’s security proof. More specifically, when receiving a signing query on(m,e), C first picks rw∈Zp∗ at random and then sets the hash value h=H5(m∥grw) to successfully compute the simulated signature σ=(σ1,σ2,σ3). According to Hung et al.’s simulation process, we know that σ3=grw′, where rw′=rw-θ1hQ(vs→)/K(vw→),  rw-ah+θ1hQ(vs→)/K(vw→), or rw-ah/K(vw→). Obviously, the verification equation e^(σ1,g)=?e^(g1,g2)h′e^(σ2,E)e^(pke1,g2S)h′e^(pke2,T)h′e^(σ3,W) is always not true since h≠h′, where h′=H5(m∥σ3). That is to say, C cannot always give a valid response to a signing query required by an attacker A with nonnegligible probability.


### 3.2.2. MKGC Attack

Here, we will show that the HT scheme cannot capture MKGC attacks by an interaction betweenC and A as follows.Stage 1.
Here,A is responsible for initializing the system parameters and sends them to C. In particular, A adaptively sets the parameters g2=gβ,s′=gx′,s1=gx1,…,sn=gxnv,t′=gy′,t1=gy1,…,tn=gynv, where β,x′,x1,…,xnv,y′,y1,…,ynv∈Zp∗.Stage 2.
In the queries phase,A can obtain the target entity public key pke=(pke1,pke2)=(gθ1,gθ2). Next, A derives the corresponding secret value sve=g2θ1Sθ1Tθ2 by computing g2θ1=pke1β, Sθ1=pke1x′∑j=1nkxjvsj, and Tθ2=pke2y′∑j=1nkyjvtj, where vs→=H2(pke1,pke2)=(vs1,…,vsnk) and vt→=H3(pke1,pke2)=(vt1,…,vtnk).Stage 3.
Now,A can recover the entity full secret key (pske,sve) and sign any message m instead of the targeted entity.Remark 3.
In MKGC attacks, the KGC can adaptively set some trapdoor in the system parameters during the setup phase which may enhance its attack success probability. Obviously, in the security proof [21], the attacker passively received the master secret key and public parameters generated by the challenger like all the previous schemes [15–23], which did not consider how to capture the MKGC attacks.


## 3.2.1. Strong Forgery Attack

Here, we indicate that an attackerA generates a new forgery σ′ from an existing signature σ on m by interacting with the challenger C.Stage 1.
C normally invokes theSetup algorithm to produce msk=g2α and sp=(G1,G2,e^,g,g1,g2,e′,e→,s′,s→,t′,t→,w′,w→,H1,H2, H3,H4,H5). Here, C sends sp to A and keeps msk by itself.Stage 2.
Given a target entitye and a message m, C first invokes thePSKExt andSetUkey algorithms to generate the entity secret key (pske1,pske2,sve)=(g2αEre,gre,g2θ1Sθ1Tθ2) and then invokes theSign algorithm to obtain a signature σ of m on e. Obviously, the signature concrete forms are (σ1,σ2,σ3)=(pske1h(sve)hWrw,pske2h,grw), where h=H3(m∥grw).Stage 3.
In order to generateσ′ for m under e,  A randomly picks re′∈Zp∗ and sets σ1′=σ1Ere′h=g2αhE(re+re′)hsvehWrw,  σ2′=σ2gre′h=g(re+re′)h, and σ3′=σ3.It is clear thatσ′ is a new valid signature for m on e with pke since (3)e^σ1′,g=e^g2αhEre+re′hsvehWrw,g=e^g2αh,ge^Ere+re′h,ge^g2Sθ1hTeθ2h,ge^Wrw,g=e^g1,g2he^E,σ2′e^pke1,g2She^pke2,The^W,σ3′.Remark 2.
We notice that there is a flaw in Hung et al.’s security proof. More specifically, when receiving a signing query on(m,e), C first picks rw∈Zp∗ at random and then sets the hash value h=H5(m∥grw) to successfully compute the simulated signature σ=(σ1,σ2,σ3). According to Hung et al.’s simulation process, we know that σ3=grw′, where rw′=rw-θ1hQ(vs→)/K(vw→),  rw-ah+θ1hQ(vs→)/K(vw→), or rw-ah/K(vw→). Obviously, the verification equation e^(σ1,g)=?e^(g1,g2)h′e^(σ2,E)e^(pke1,g2S)h′e^(pke2,T)h′e^(σ3,W) is always not true since h≠h′, where h′=H5(m∥σ3). That is to say, C cannot always give a valid response to a signing query required by an attacker A with nonnegligible probability.


## 3.2.2. MKGC Attack

Here, we will show that the HT scheme cannot capture MKGC attacks by an interaction betweenC and A as follows.Stage 1.
Here,A is responsible for initializing the system parameters and sends them to C. In particular, A adaptively sets the parameters g2=gβ,s′=gx′,s1=gx1,…,sn=gxnv,t′=gy′,t1=gy1,…,tn=gynv, where β,x′,x1,…,xnv,y′,y1,…,ynv∈Zp∗.Stage 2.
In the queries phase,A can obtain the target entity public key pke=(pke1,pke2)=(gθ1,gθ2). Next, A derives the corresponding secret value sve=g2θ1Sθ1Tθ2 by computing g2θ1=pke1β, Sθ1=pke1x′∑j=1nkxjvsj, and Tθ2=pke2y′∑j=1nkyjvtj, where vs→=H2(pke1,pke2)=(vs1,…,vsnk) and vt→=H3(pke1,pke2)=(vt1,…,vtnk).Stage 3.
Now,A can recover the entity full secret key (pske,sve) and sign any message m instead of the targeted entity.Remark 3.
In MKGC attacks, the KGC can adaptively set some trapdoor in the system parameters during the setup phase which may enhance its attack success probability. Obviously, in the security proof [21], the attacker passively received the master secret key and public parameters generated by the challenger like all the previous schemes [15–23], which did not consider how to capture the MKGC attacks.


## 4. Our CLS Scheme

In this section, we construct an improved strongly unforgeable certificateless signature scheme and demonstrate its security on the condition that both [3, 24] are secure, and DL and CRHF assumptions hold.


### 4.1. Building Blocks

Paterson and Schuldt’s Identity-Based Signature Scheme (PIBS) [3]
(i)
Setup: let (q,G1,G2,e^,g) be an instance described in Section 2. First, pick a random element α from Zp∗ and compute g1=gα. Then, choose random elements g2,e′,w′ from G1 and two vectors e→={ek}k=1ne, w→={wl}l=1nw of lengths ne and nw, respectively, whose entries are random elements from G1. Finally, the master secret key is msk=g2α and the system parameter is sp=(G1,G2,e^,g,g1,g2,e′,e→,w′,w→).
(ii)
Extract: let E=He(e), where e is an entity. Set E={k∣E[k]=1,k=1,2,…,ne}. To construct e’s secret key ske, pick a random number re from Zp∗ and compute (4)ske=ske1,ske2=g2α1e′∏k∈Eekre,gre.
(iii)
Sign: let W⊂{1,2,…,nm} be the set of indices l such that W[l]=1, where W[l] is the lth bit of message m. σ is constructed by picking a random element rw from Zp∗ and computing (5)σ=g2αe′∏k∈Eekrew′∏l∈Wwlrm,gre,grw.
(iv)
Verify: given a signature σ=(σ1,σ2,σ3) of m under e, a verifier accepts σ if the following equality holds: (6)e^σ1,g=?e^g1,g2e^e′∏k∈Eek,σ2e^w′∏l∈Wwl,σ3.
Output 1 if it is valid. Otherwise, output 0.Boneh et al.’s Signature Scheme (BSW) [24]
(i)
SetUKey: let (q,G1,G2,e^,g) be an instance described in Section 2. First, pick a random number β from Zp∗ and set ge1=gβ. Then, choose three random values ge2,he,ve′ from G1 where logg⁡he is known and a random nw-length vector v→e={vei}i=1nw whose elements are also chosen from G1. In addition, choose two random collision-resistant hash functions H:{0,1}∗→Zp∗ and Hw:G1→{0,1}ne. Finally, output the secret key ske=ge2β and the public key pke=(G1,G2,e^,g,ge1,ge2,he,ve′,v→e).
(ii)
Sign: given a message m, first, pick two random numbers rw,  s from Zp∗ and compute W=Hw(gthes), where t=H(m∥grw). Then, set W={i∣W[i]=1,i=1,2,…,nw}. At last, σ is constructed by computing (7)σ=σ1,σ2,σ3=ge2βve′∏i∈Wveirw,grw,s.
(iii)
Verify: given σ of m under pke, first, compute W=Hm(gtheσ3), where t=H(m∥σ2). Then, set W={i∣N[i]=1,i=1,2,…,nm}. Finally, verify the following equation: (8)e^σ1,g=?e^ge1,ge2e^ve′∏i∈Wvei,σ2.


### 4.2. Our Concrete Scheme

Let (q,G1,G2,e^,g) be an instance described in Section 2. In our scheme, three classic hash functions, H:{0,1}∗×sp×pke×e×G12→Zp∗,  Hw:G1→{0,1}nw, and He:{0,1}∗→{0,1}ne, are adopted from H to handle arbitrary messages and identities. Note that the cyclic groups and hash functions are publicly confirmed by all interested parties.(i)
Setup: first, choose random elements α1,α2,φ,x′,x1,x2,…,xne,y′,y1,y2,…,ynw from Zp∗. Then, compute g1=gα1,g2=gα2,h=gφ,e′=gx′,e→={ek}k=1ne={gxk}k=1ne,w′=gy′,w→={wl}l=1nw={gyl}l=1nw. Finally, the master secret key is msk=(α1,α2,φ,x′,x1,x2,…,xne,y′,y1,y2,…,ynw) and system parameter is sp=(G1,G2,g,g1,g2,h,e′,e→,w′,w→).(ii)
PSKExt: let E=He(e) where e is an entity. Set E={k∣E[k]=1,k=1,2,…,ne}. To construct e’s partial secret key pske, pick a random number re from Zp∗ and compute (9)pske=pske1,pske2=g2α1e′∏k∈Eekre,gre.(iii)
SetUKey: first, choose random elements βe1,βe2,ϕe,ze′,ze1,ze2,…,zenw from Zp∗. Then, compute ge1=gβe1,ge2=gβe2,he=gϕe,ve′=gze′,v→e={vei}i=1nw={gzei}i=1nw. At last, let the public key be pke=(ge1,ge2,he,ve′,v→e) and the secret values be sve=(βe1,βe2,ϕe,ze′,ze1,ze2,…,zenw). Note that ske=(sve,pske).(iv)
Sign: given m, pke, and ske, the signer selects two random numbers rw,s∈Zp∗, computes t=H(m∥sp∥pke∥e∥pske2∥grw), and sets E={k∣E[k]=1,k=1,2,…,ne}, where E=He(e), W={l∣W[l]=1,l=1,2,…,nw}, where W=Hw(gths), and W′={i∣W′[i]=1,i=1,2,…,nw}, where W′=Hw(gthes), respectively. At last, σ is constructed by computing (10)σ=ge2βe1ve′∏i∈W′veirw,g2α1e′∏k∈Eekrew′∏l∈Wwlrw,gre,grw,s.(v)
Verify: given σ of m under e, any verifier first computes E=He(e),  W=Hw(gthσ5) and W′=Hw(gtheσ5), where t=H(m∥sp∥pke∥e∥σ3∥σ4). Then, the verifier sets E={k∣E[k]=1,k=1,2,…,ne}, W={l∣W[l]=1,l=1,2,…,nw}, and W′={i∣W′[i]=1,i=1,2,…,nw}, respectively. Finally, the equalities are checked as follows: (11)e^σ1,g=?e^ge1,ge2e^ve′∏i∈W′vei,σ4,e^σ2,g=?e^g1,g2e^e′∏k∈Eek,σ3e^w′∏l∈Wwl,σ4.Output 1 if the equations hold. Otherwise, output 0.For simplicity, we may setmsk=α1 and sve=βe1 because the others called implicit master secret keys/secret values are not used during its execution. Here, they are explicitly listed to easily prove its security as follows.


### 4.3. Security Analysis

In this subsection, we introduce two lemmas to demonstrate that our scheme is strongly unforgeable against PKR attacks and MKGC attacks based on the CDH, DL and CRHF assumptions defined in Section2.Lemma 4.
Our scheme is strongly secure against PKR attacks launched by the attackerA1 assumingPIBS is weakly secure [3], the discrete log problem is intractable in G1, and finding concrete collisions is difficult in H.Analysis. Given any PPT adversary A1 trying to break our CLS scheme in an adaptive chosen-message attack, we can forge a PPT adversary B1 producing a weak forgery on thePIBS scheme/solving discrete log in G1/finding concrete collision of H. Moreover, to consistently answer A1’s queries, B1 keeps a table T which is initially empty in our security proofs.Init. First, if B1 attempt to break thePIBS scheme, B1 randomly picks a number φ from Zp∗ and sets h=gφ, else B1 directly picks a random value h from G1. Then, B1 chooses three hash functions H,  He, and Hw from a classic hash family H. Finally, B1 returns (PIBS.params,h,H,He,Hw) to A1 as the system parameters sp. Here, in order to make the initialization appropriate, we flip a coin to predict the forgery type launched by A1.Queries. In the query phase, B1 responds to A1’s all queries defined in their security model as follows:O
p
s
k
(
e
): B1 runsPIBS.Extract on He(e) to obtain the partial secret key pske and returns it to A1.O
s
k
(
e
): B1 searches T to find the entity e and get the entity secret value sve=(βe1,βe2,ϕe,ze′,ze1,ze2,…,zenw). If it does not exist, B1 first picks nw+4 random values (βe1,βe2,ϕe,ze′,ze1,ze2,…,zenw) from Zp∗ and stores them in T. Finally, B1 returns (sve,pske) to A1 as the secret key for e.O
p
k
(
e
): B1 searches T to discover the entity e and returns (ge1,ge2,ve′,ve1,…,venw) to A1. Otherwise, B1 first picks nw+4 random values (βe1,βe2,ϕe,ze′,ze1,ze2,…,zenw) from Zp∗ and then stores those values in L. At last, (gβe1,gβe2,ϕe,gze′,gze1,…,gzenw) is returned to A1 as the entity public key.O
r
e
p
(
e
,
p
k
e
′
): B1 searches T to find the entity e and update its public key using a new public key pke′. If it does not exist, A1 directly sets the entity public key to be pke′.O
s
i
g
n
(
e
,
m
): for a signature of a message m on the entity public key pke,(i)
ifB1 attempts to breakPIBS by means of A1’s ability, B1 picks a random value λ from Zp and runsPIBS.Sign(He(e),Hm(gλ)) to produce (σ1′,σ2′,σ3′). Moreover, B1 computes t=H(m∥sp∥pke∥e∥σ2′∥σ3′) to recover s=(λ-t)/φ.(ii)
Otherwise,B1 invokesPPKExt(He(e)) to generate e’s partial secret key (pske1,pske2). Then, B1 picks two random values rw,s from Zp∗ and simulatesPIBS.Sign(He(e),Hw(gths)) to produce (σ1′,σ2′,σ3′) where t=H(m∥sp∥pke∥e∥σ2′∥σ3′).Next,B1 computes W′=Hw(gthes) and sets σ1=gβe1βe2(σ3′)∑i∈W′zei where W′={i∣W′[i]=1,i=1,2,…,nw}. At last, B1 sets σ=(σ1,σ2,σ3,σ4,σ5)=(σ1,σ1′,σ2′,σ3′,s) and returns it to A1.Forgery. If A1 outputs σ∗ on m∗ for e∗ with pke∗ such that(i)
Hw(gt∗hs∗)≠Hw(gths), B1 can succeed in breaking thePIBS scheme by forging a valid signature (σ2∗,σ3∗,σ4∗) on the message Hw(gt∗hs∗);(ii)
Hw(gt∗hs∗)=Hw(gths) but gt∗hs∗≠gths,  B1 can succeed in finding a concrete collision to hash function Hw;(iii)
gt∗hs∗=gths but t∗≠t, B1 can succeed in solving the discrete logarithm problem by computing d=(t-t∗)/(s∗-s);(iv)
gt∗hs∗=gths,  t∗=t but m∗∥sp∥pke∗∥e∗∥σ3∗∥σ4∗≠m∥sp∥pke∥e∥σ3∥σ4,  B1 can succeed in finding a concrete collision to hash function H.Here,s,  t, and m∥sp∥pke∥e∥σ3∥σ4 denote those elements queried/involved during the query phase.Lemma 5.
Our scheme is strongly secure against MKGC attacks launched byA2 assumingBSW is strongly existential unforgeable.Analysis. Given a PPT adversary A2 breaking our CLS scheme in an adaptive chosen-message attack, we simulate a PPT adversary B2 producing a strong forgery on theBSW scheme. Moreover, to consistently answer A2’s queries, B2 keeps a table T which is initially empty in our security proofs.Init. B2 invokes A2 to initialize the master secret key msk=(α1,α2,φ,x′,x1,x2,…,xne,y′,y1,y2,…,ynw) and the system parameters sp=(G1,G2,g,h,g1,g2,e′,e→,w′,w→). Here, in order to launch MKGC attacks more easily, A2 is allowed to set some trapdoors during the initialization phase.Queries. In the query phase, B2 responds to A2’s all queries involved in their security model as follows:O
s
k
(
e
): B2 searches T to find the entity e and get the entity secret value sve=(βe1,βe2,ϕe,ze′,ze1,ze2,…,zenw). If it does not exist, B2 first picks nw+4 random values (βe1,βe2,ϕe,ze′,ze1,ze2,…,zenw) from Zp∗ and stores them in T. Finally, B2 returns (sve,pske) to A2 as the secret key for e.O
p
k
(
e
): Analogously, B2 looks up T to find the entity e and returns (ge1,ge2,ve′,ve1,…,venw) to A2. If e is not found, B2 first picks nw+4 random elements (βe1,βe2,ϕe,ze′,ze1,ze2,…,zenw) from Zp∗ and then stores those values in T. At last, B2 sets ge1=gβe1,ge2=gβe2,he=ϕe,ve′=gze′,ve1=gze1,…,venw=gzenw and returns these elements to A2.O
r
e
p
(
e
,
p
k
e
′
): B2 searches T to find the entity e and updates the entity public key using a new public key pke′. If it does not exist, B2 directly sets the entity public key to be pke′ provided by A2.O
s
i
g
n
(
e
,
m
): for a signature query on a message m under an entity e with the public key pke, B2 first invokesPPKExt(He(e)) to get the entity partial secret key pske and then runsBSW.Sign(pke,m∥sp∥pke∥e∥pske2) to generate (σ1′,σ2′,σ3′). Next, B2 computes t=H(m∥sp∥pke∥e∥pske2∥σ2′) and sets σ2=pske1(σ2′)∑l∈Wyl, where W={l∣W[l]=1,l=1,2,…,nw} and W=Hw(gthσ3′). At last, B2 sets σ=(σ1,σ2,σ3,σ4,σ5)=(σ1′,σ2,D2,σ2′,σ3′) and returns it to A2.Forgery. If A2 eventually returns σ∗=(σ1∗,σ2∗,σ3∗,σ4∗,σ5∗) for m∗ under e∗ with pke∗, B1 can succeed in breaking theBSW scheme by forging a valid signature (σ1∗,σ4∗,σ5∗) on the message He(gt∗hes∗) where t∗=H(m∗∥sp∥pke∗∥e∗∥σ3∗∥σ4∗). Note that H and He are two types of classic hash in theBSW scheme.In general, we demonstrate that our CLS scheme is strongly unforgeable against PKR attacks and MKGC attacks in the standard model by combining Lemmas4 and 5.


### 4.4. Discussion

Although our scheme has more parameters compared with the existing schemes, it not only overcomes the weakness of those previous schemes but also is proven to be secure under our stronger security model. In Lemma5, the KGC can set some trapdoors in the system parameters adaptively rather than passively receiving the master secret key and the corresponding public parameters from the challenger like in the previous schemes, which is consistent with the actual situation in a concrete scheme. To the best of our knowledge, we are the first to prove a CLS scheme to be strongly secure against the MKGC attacks without random oracles.


## 4.1. Building Blocks

Paterson and Schuldt’s Identity-Based Signature Scheme (PIBS) [3]
(i)
Setup: let (q,G1,G2,e^,g) be an instance described in Section 2. First, pick a random element α from Zp∗ and compute g1=gα. Then, choose random elements g2,e′,w′ from G1 and two vectors e→={ek}k=1ne, w→={wl}l=1nw of lengths ne and nw, respectively, whose entries are random elements from G1. Finally, the master secret key is msk=g2α and the system parameter is sp=(G1,G2,e^,g,g1,g2,e′,e→,w′,w→).
(ii)
Extract: let E=He(e), where e is an entity. Set E={k∣E[k]=1,k=1,2,…,ne}. To construct e’s secret key ske, pick a random number re from Zp∗ and compute (4)ske=ske1,ske2=g2α1e′∏k∈Eekre,gre.
(iii)
Sign: let W⊂{1,2,…,nm} be the set of indices l such that W[l]=1, where W[l] is the lth bit of message m. σ is constructed by picking a random element rw from Zp∗ and computing (5)σ=g2αe′∏k∈Eekrew′∏l∈Wwlrm,gre,grw.
(iv)
Verify: given a signature σ=(σ1,σ2,σ3) of m under e, a verifier accepts σ if the following equality holds: (6)e^σ1,g=?e^g1,g2e^e′∏k∈Eek,σ2e^w′∏l∈Wwl,σ3.
Output 1 if it is valid. Otherwise, output 0.Boneh et al.’s Signature Scheme (BSW) [24]
(i)
SetUKey: let (q,G1,G2,e^,g) be an instance described in Section 2. First, pick a random number β from Zp∗ and set ge1=gβ. Then, choose three random values ge2,he,ve′ from G1 where logg⁡he is known and a random nw-length vector v→e={vei}i=1nw whose elements are also chosen from G1. In addition, choose two random collision-resistant hash functions H:{0,1}∗→Zp∗ and Hw:G1→{0,1}ne. Finally, output the secret key ske=ge2β and the public key pke=(G1,G2,e^,g,ge1,ge2,he,ve′,v→e).
(ii)
Sign: given a message m, first, pick two random numbers rw,  s from Zp∗ and compute W=Hw(gthes), where t=H(m∥grw). Then, set W={i∣W[i]=1,i=1,2,…,nw}. At last, σ is constructed by computing (7)σ=σ1,σ2,σ3=ge2βve′∏i∈Wveirw,grw,s.
(iii)
Verify: given σ of m under pke, first, compute W=Hm(gtheσ3), where t=H(m∥σ2). Then, set W={i∣N[i]=1,i=1,2,…,nm}. Finally, verify the following equation: (8)e^σ1,g=?e^ge1,ge2e^ve′∏i∈Wvei,σ2.


## 4.2. Our Concrete Scheme

Let (q,G1,G2,e^,g) be an instance described in Section 2. In our scheme, three classic hash functions, H:{0,1}∗×sp×pke×e×G12→Zp∗,  Hw:G1→{0,1}nw, and He:{0,1}∗→{0,1}ne, are adopted from H to handle arbitrary messages and identities. Note that the cyclic groups and hash functions are publicly confirmed by all interested parties.(i)
Setup: first, choose random elements α1,α2,φ,x′,x1,x2,…,xne,y′,y1,y2,…,ynw from Zp∗. Then, compute g1=gα1,g2=gα2,h=gφ,e′=gx′,e→={ek}k=1ne={gxk}k=1ne,w′=gy′,w→={wl}l=1nw={gyl}l=1nw. Finally, the master secret key is msk=(α1,α2,φ,x′,x1,x2,…,xne,y′,y1,y2,…,ynw) and system parameter is sp=(G1,G2,g,g1,g2,h,e′,e→,w′,w→).(ii)
PSKExt: let E=He(e) where e is an entity. Set E={k∣E[k]=1,k=1,2,…,ne}. To construct e’s partial secret key pske, pick a random number re from Zp∗ and compute (9)pske=pske1,pske2=g2α1e′∏k∈Eekre,gre.(iii)
SetUKey: first, choose random elements βe1,βe2,ϕe,ze′,ze1,ze2,…,zenw from Zp∗. Then, compute ge1=gβe1,ge2=gβe2,he=gϕe,ve′=gze′,v→e={vei}i=1nw={gzei}i=1nw. At last, let the public key be pke=(ge1,ge2,he,ve′,v→e) and the secret values be sve=(βe1,βe2,ϕe,ze′,ze1,ze2,…,zenw). Note that ske=(sve,pske).(iv)
Sign: given m, pke, and ske, the signer selects two random numbers rw,s∈Zp∗, computes t=H(m∥sp∥pke∥e∥pske2∥grw), and sets E={k∣E[k]=1,k=1,2,…,ne}, where E=He(e), W={l∣W[l]=1,l=1,2,…,nw}, where W=Hw(gths), and W′={i∣W′[i]=1,i=1,2,…,nw}, where W′=Hw(gthes), respectively. At last, σ is constructed by computing (10)σ=ge2βe1ve′∏i∈W′veirw,g2α1e′∏k∈Eekrew′∏l∈Wwlrw,gre,grw,s.(v)
Verify: given σ of m under e, any verifier first computes E=He(e),  W=Hw(gthσ5) and W′=Hw(gtheσ5), where t=H(m∥sp∥pke∥e∥σ3∥σ4). Then, the verifier sets E={k∣E[k]=1,k=1,2,…,ne}, W={l∣W[l]=1,l=1,2,…,nw}, and W′={i∣W′[i]=1,i=1,2,…,nw}, respectively. Finally, the equalities are checked as follows: (11)e^σ1,g=?e^ge1,ge2e^ve′∏i∈W′vei,σ4,e^σ2,g=?e^g1,g2e^e′∏k∈Eek,σ3e^w′∏l∈Wwl,σ4.Output 1 if the equations hold. Otherwise, output 0.For simplicity, we may setmsk=α1 and sve=βe1 because the others called implicit master secret keys/secret values are not used during its execution. Here, they are explicitly listed to easily prove its security as follows.


## 4.3. Security Analysis

In this subsection, we introduce two lemmas to demonstrate that our scheme is strongly unforgeable against PKR attacks and MKGC attacks based on the CDH, DL and CRHF assumptions defined in Section2.Lemma 4.
Our scheme is strongly secure against PKR attacks launched by the attackerA1 assumingPIBS is weakly secure [3], the discrete log problem is intractable in G1, and finding concrete collisions is difficult in H.Analysis. Given any PPT adversary A1 trying to break our CLS scheme in an adaptive chosen-message attack, we can forge a PPT adversary B1 producing a weak forgery on thePIBS scheme/solving discrete log in G1/finding concrete collision of H. Moreover, to consistently answer A1’s queries, B1 keeps a table T which is initially empty in our security proofs.Init. First, if B1 attempt to break thePIBS scheme, B1 randomly picks a number φ from Zp∗ and sets h=gφ, else B1 directly picks a random value h from G1. Then, B1 chooses three hash functions H,  He, and Hw from a classic hash family H. Finally, B1 returns (PIBS.params,h,H,He,Hw) to A1 as the system parameters sp. Here, in order to make the initialization appropriate, we flip a coin to predict the forgery type launched by A1.Queries. In the query phase, B1 responds to A1’s all queries defined in their security model as follows:O
p
s
k
(
e
): B1 runsPIBS.Extract on He(e) to obtain the partial secret key pske and returns it to A1.O
s
k
(
e
): B1 searches T to find the entity e and get the entity secret value sve=(βe1,βe2,ϕe,ze′,ze1,ze2,…,zenw). If it does not exist, B1 first picks nw+4 random values (βe1,βe2,ϕe,ze′,ze1,ze2,…,zenw) from Zp∗ and stores them in T. Finally, B1 returns (sve,pske) to A1 as the secret key for e.O
p
k
(
e
): B1 searches T to discover the entity e and returns (ge1,ge2,ve′,ve1,…,venw) to A1. Otherwise, B1 first picks nw+4 random values (βe1,βe2,ϕe,ze′,ze1,ze2,…,zenw) from Zp∗ and then stores those values in L. At last, (gβe1,gβe2,ϕe,gze′,gze1,…,gzenw) is returned to A1 as the entity public key.O
r
e
p
(
e
,
p
k
e
′
): B1 searches T to find the entity e and update its public key using a new public key pke′. If it does not exist, A1 directly sets the entity public key to be pke′.O
s
i
g
n
(
e
,
m
): for a signature of a message m on the entity public key pke,(i)
ifB1 attempts to breakPIBS by means of A1’s ability, B1 picks a random value λ from Zp and runsPIBS.Sign(He(e),Hm(gλ)) to produce (σ1′,σ2′,σ3′). Moreover, B1 computes t=H(m∥sp∥pke∥e∥σ2′∥σ3′) to recover s=(λ-t)/φ.(ii)
Otherwise,B1 invokesPPKExt(He(e)) to generate e’s partial secret key (pske1,pske2). Then, B1 picks two random values rw,s from Zp∗ and simulatesPIBS.Sign(He(e),Hw(gths)) to produce (σ1′,σ2′,σ3′) where t=H(m∥sp∥pke∥e∥σ2′∥σ3′).Next,B1 computes W′=Hw(gthes) and sets σ1=gβe1βe2(σ3′)∑i∈W′zei where W′={i∣W′[i]=1,i=1,2,…,nw}. At last, B1 sets σ=(σ1,σ2,σ3,σ4,σ5)=(σ1,σ1′,σ2′,σ3′,s) and returns it to A1.Forgery. If A1 outputs σ∗ on m∗ for e∗ with pke∗ such that(i)
Hw(gt∗hs∗)≠Hw(gths), B1 can succeed in breaking thePIBS scheme by forging a valid signature (σ2∗,σ3∗,σ4∗) on the message Hw(gt∗hs∗);(ii)
Hw(gt∗hs∗)=Hw(gths) but gt∗hs∗≠gths,  B1 can succeed in finding a concrete collision to hash function Hw;(iii)
gt∗hs∗=gths but t∗≠t, B1 can succeed in solving the discrete logarithm problem by computing d=(t-t∗)/(s∗-s);(iv)
gt∗hs∗=gths,  t∗=t but m∗∥sp∥pke∗∥e∗∥σ3∗∥σ4∗≠m∥sp∥pke∥e∥σ3∥σ4,  B1 can succeed in finding a concrete collision to hash function H.Here,s,  t, and m∥sp∥pke∥e∥σ3∥σ4 denote those elements queried/involved during the query phase.Lemma 5.
Our scheme is strongly secure against MKGC attacks launched byA2 assumingBSW is strongly existential unforgeable.Analysis. Given a PPT adversary A2 breaking our CLS scheme in an adaptive chosen-message attack, we simulate a PPT adversary B2 producing a strong forgery on theBSW scheme. Moreover, to consistently answer A2’s queries, B2 keeps a table T which is initially empty in our security proofs.Init. B2 invokes A2 to initialize the master secret key msk=(α1,α2,φ,x′,x1,x2,…,xne,y′,y1,y2,…,ynw) and the system parameters sp=(G1,G2,g,h,g1,g2,e′,e→,w′,w→). Here, in order to launch MKGC attacks more easily, A2 is allowed to set some trapdoors during the initialization phase.Queries. In the query phase, B2 responds to A2’s all queries involved in their security model as follows:O
s
k
(
e
): B2 searches T to find the entity e and get the entity secret value sve=(βe1,βe2,ϕe,ze′,ze1,ze2,…,zenw). If it does not exist, B2 first picks nw+4 random values (βe1,βe2,ϕe,ze′,ze1,ze2,…,zenw) from Zp∗ and stores them in T. Finally, B2 returns (sve,pske) to A2 as the secret key for e.O
p
k
(
e
): Analogously, B2 looks up T to find the entity e and returns (ge1,ge2,ve′,ve1,…,venw) to A2. If e is not found, B2 first picks nw+4 random elements (βe1,βe2,ϕe,ze′,ze1,ze2,…,zenw) from Zp∗ and then stores those values in T. At last, B2 sets ge1=gβe1,ge2=gβe2,he=ϕe,ve′=gze′,ve1=gze1,…,venw=gzenw and returns these elements to A2.O
r
e
p
(
e
,
p
k
e
′
): B2 searches T to find the entity e and updates the entity public key using a new public key pke′. If it does not exist, B2 directly sets the entity public key to be pke′ provided by A2.O
s
i
g
n
(
e
,
m
): for a signature query on a message m under an entity e with the public key pke, B2 first invokesPPKExt(He(e)) to get the entity partial secret key pske and then runsBSW.Sign(pke,m∥sp∥pke∥e∥pske2) to generate (σ1′,σ2′,σ3′). Next, B2 computes t=H(m∥sp∥pke∥e∥pske2∥σ2′) and sets σ2=pske1(σ2′)∑l∈Wyl, where W={l∣W[l]=1,l=1,2,…,nw} and W=Hw(gthσ3′). At last, B2 sets σ=(σ1,σ2,σ3,σ4,σ5)=(σ1′,σ2,D2,σ2′,σ3′) and returns it to A2.Forgery. If A2 eventually returns σ∗=(σ1∗,σ2∗,σ3∗,σ4∗,σ5∗) for m∗ under e∗ with pke∗, B1 can succeed in breaking theBSW scheme by forging a valid signature (σ1∗,σ4∗,σ5∗) on the message He(gt∗hes∗) where t∗=H(m∗∥sp∥pke∗∥e∗∥σ3∗∥σ4∗). Note that H and He are two types of classic hash in theBSW scheme.In general, we demonstrate that our CLS scheme is strongly unforgeable against PKR attacks and MKGC attacks in the standard model by combining Lemmas4 and 5.


## 4.4. Discussion

Although our scheme has more parameters compared with the existing schemes, it not only overcomes the weakness of those previous schemes but also is proven to be secure under our stronger security model. In Lemma5, the KGC can set some trapdoors in the system parameters adaptively rather than passively receiving the master secret key and the corresponding public parameters from the challenger like in the previous schemes, which is consistent with the actual situation in a concrete scheme. To the best of our knowledge, we are the first to prove a CLS scheme to be strongly secure against the MKGC attacks without random oracles.


## 5. Conclusion

In this paper, we firstly showed that Hung et al.’s scheme cannot meet the requirements of strong unforgeability as they claimed. Then, we pointed out that their construction does not withstand the MKGC attacks and gave a concrete forgery to break it. Finally, we constructed an improved strongly unforgeable certificateless signature scheme and proved its security under the MKGC attacks in the standard model.



---

*Source: 5704865-2017-11-20.xml*