1 Introduction
In the traditional public key infrastructure (PKI) based signature system (ElGamal, 1985), the user’s identity is bound to the corresponding public key through a certificate which is issued by a trusted certificate authority. Obviously, the complex and expensive certificate management has become an obstacle to the development of PKI-based system. Therefore, the notion of identity-based (shorten as ID-based) signature scheme (Shamir, 1984) has been proposed to alleviate this problem. In ID-based signature, users’ public keys are their unique identity information that is publicly known, while the user’s private key is created by a private key generator (PKG) with a master secret key. In this way, the certificate is eliminated in ID-based signature because the public key is derived from the identity of the user. Since the private key of all users is created by PKG, the signature of any entity can easily be forged by PKG, which results in the notorious key escrow problem. Thankfully, the certificateless signature (CLS) system (Al-Riyami and Paterson, 2003) preserves the advantages of eliminating the required certificates in ID-based signature while avoiding key escrow problem. In a CLS-based system, the private key includes the secret value chosen by the entity itself and the partial private key generated by the Key Generation Center (KGC). It is easy to observe that the key escrow problem was solved successfully. Since then, many efficient CLS schemes were proposed in the literature (Huang et al., 2007; Yap et al., 2006; Zhang et al., 2006; Karati et al., 2018a).
For any public key system, it is indispensable to have the function of revocation. Imagine a situation in which the employee in charge of confidential documents in the company is leaving. In order to ensure that confidential files are not disclosed, the private key held by the employee must be revoked. Similarly, with the frequent use of signature operations in the signature system, private keys are inevitably leaked. In this case, the user with the compromised key is no longer reliable. In the traditional public key system, the revoked public key can be known by the user through the certificate revocation list (CRL) (Housley et al., 2002). Apparently, this method does not apply to the certificateless cryptosystem due to the lack of certificates. So far, there are two revocation mechanisms in the process of certificateless public key cryptosystem development. One mechanism is to split the partial private key of the user generated by KGC into two parts, one is delivered to the user and the other is sent to the Security Mediator (an online mediator) (Ju et al., 2005; Yap et al., 2007). In this approach, the Security Mediator is required to create each signature which causes expensive burden. Moreover, it is necessary for the Security Mediator to maintain large quantities of secret keys which makes it easier for an attacker to compromise a key. Different from the Security Mediator based revocation approach, another certificateless system with revocation has been introduced where the user’s partial private key is updated in period time (Tsai and Tseng, 2015). When the user’s private key is compromised or the user leaves, KGC stops updating the partial private key. Nevertheless, most existing schemes in this mechanism prove their security under the random oracle model. This paradigm is to model the hash function as random oracles in the security proof. Unfortunately, when random oracles are instantiated by a concrete hash function, these schemes are vulnerable to be broken (Canetti et al., 2004). Tsai et al. (2014) introduced a CLS scheme with revocation mechanism, whose security was theoretically proven by using the idea of standard model. However, we observed that the proposed scheme is neither efficient nor can resist malicious-but-passive KGC attacks.
For the above reasons, we propose a new certificateless signature scheme with revocation (RCLS) and prove its security under the standard model. In our scheme, the partial private key issued by the KGC is spilt into two independent parts, where the former is associated with the identity of the user and the latter is related to the time period. In the meanwhile, our scheme can resist malicious-but-passive KGC attacks. Specific contributions are as follows:
-
1. This paper first reveals the insecurity of the scheme in Tsai et al. (2014), and displays the forgery attack as well as the reason why their scheme is easily broken.
-
2. Next, this paper proposes a new certificateless signature scheme with revocation, whose security proof is provided in the standard model based on the Computational Diffie–Hellman assumption. And the attack mounted by the malicious-but-passive KGC is able to be resisted in our scheme.
-
3. Finally, by comparing the performance and properties with related works, the RCLS scheme in this paper outperforms the existing works.
1.1 Related Work
Al-Riyami and Paterson (2003) first introduced the notion of certificateless signature (CLS) scheme and gave a concrete construction of CLS scheme. In the CLS scheme, users’ private key was divided into two parts. One part is chosen by users themselves and another part is generated by a third party called KGC, which successfully avoids the key escrow problem. Thanks to maintaining the advantages of eliminating the required certificates in ID-based signature while avoiding key escrow problem, much attention has been paid to the research of CLS. After Al-Riyami and Paterson (2003) proposed the first CLS scheme, dozens of CLS schemes were proposed in terms of different research lines (Jia et al., 2018; Huang et al., 2005; Karati et al., 2018b; He et al., 2012; Xiong et al., 2019). By considering the criticism of random models, Liu et al. (2007) proposed the first concrete CLS scheme which was proved to be secure in the standard model. Unfortunately, Xiong et al. (2008) indicated that Liu et al.’s scheme cannot be able to resist malicious-but-passive KGC attack. In this attack, KGC can maliciously generate system parameters during the system setup stage and forge the signature with the knowledge of the secret value used to calculate the system parameters. For this type of attack, Xiong et al. also put forward an improved scheme in their paper. In the meanwhile, Yuan et al. (2009) presented a CLS scheme in the standard model. Unfortunately, Xia et al. (2010) showed that both Xiong et al.’s improved scheme and Yuan et al.’s scheme are insecure under the key replacement attack. Aiming to resist the key replacement attack proposed by Xia et al., Yu et al. (2012) presented a new CLS scheme in the standard model. Subsequently, Yu et al.’s scheme was proved to be insecure under the attack of Xiong et al. Recently, Shim (2018a) proposed a CLS scheme which makes it possible to prove security in the standard model. In short, most of the existing schemes proposed in the standard are insecure.
The idea of revocation was first proposed by Boneh et al. (2001) and was used in RSA-type cryptosystems. In their scheme, a semi-trusted server called Security Mediator (SEM) is introduced to issue tokens. If a user wants to sign or decrypt a message, he/she must get the token for the message. The scheme revokes the ability of the user to sign or decrypt by stopping issuing tokens to the user. Following the works of Boneh et al. (2001), some well-designed schemes have been constructed in certificateless cryptosystem. Chow et al. (2006) introduced the concept of Security Mediator into the certificateless (SMC) cryptosystem for the first time, and proposed a formal security model. After that, the first pairing-free provable secure SMC scheme as well as a concrete construction was presented by Yap et al. (2007). Unfortunately, SEM is involved in the generation of each signature which causes expensive burden. Furthermore, it is necessary for the Security Mediator to preserve large numbers of secret keys which makes it easier for an attacker to compromise a key. To deal with this problem, Tsai and Tseng (2015) proposed a new RCLS scheme. In their scheme, the user’s partial private key is updated in period time. When the user’s private key is compromised or the user leaves, KGC stops updating the partial private key. At the same time, Shen et al. (2013) showed an efficient certificateless encryption (CLE) with the function of revocation, which was proved to be CCA2-secure under the standard model. Xiong and Qin (2015) presented an RCLS scheme which can resist signing key exposure and applied it into the wireless body area networks. However, Shim (2018b) pointed out that Xiong et al.’s scheme is vulnerable to the type I adversary. Sun et al. (2014) proposed an RCLS schemes from bilinear pairings that was proved to be secure in the random oracle model. To eliminate the random oracle model, Tsai et al. (2014) introduced an RCLS scheme which was proven in the standard model. However, in this paper, Tsai et al.’s scheme is demonstrated to be neither efficient nor resistant to malicious-but-passive KGC attacks. After that, many CLS or CLE schemes with revocation mechanism were presented in the literature (Zhang and Zhao, 2015; Hung et al., 2016; Sun et al., 2018; Zheng et al., 2017). However, most of the existing schemes cannot resist malicious-but-passive KGC attacks.
1.2 Organization
This paper’s structure is as follows: some preliminaries including bilinear pairings, complexity assumption, system framework and security notions are introduced in Section 2. Section 3 briefly analyses Tsai et al.’ scheme and then displays a forgery attack about their scheme. A concrete RCLS scheme and associated security proof are demonstrated in Section 4. Section 5 provides the performance evaluation. Section 6 summarizes this paper.
2 Preliminaries
This section describes some mathematical knowledge, formal definition and security model, which are utilized in the proposed revocable certificateless signature scheme.
2.1 Bilinear Pairing
Chosen two multiplicative cyclic groups $\mathcal{G},{\mathcal{G}_{T}}$ of prime order p, given two random generators $u,v$ of $\mathcal{G}$, the bilinear map $\hat{e}:\mathcal{G}\times \mathcal{G}\to {\mathcal{G}_{T}}$ needs to satisfy the following features:
2.2 Mathematical Concept and Assumption
-
• Computational Diffie–Hellman (CDH) Problem: Given a tuple $(g,{g^{a}},{g^{b}})$ to calculate ${g^{ab}}$ where $a,b\in {\mathcal{Z}_{p}^{\ast }}$, $g\in \mathcal{G}$.
-
• Computational Diffie–Hellman (CDH) Assumption: The CDH assumption in $\mathfrak{G}$ holds if there does not exist polynomial-time algorithm $\mathfrak{B}$ to solve the CDH problem with non-negligible advantage formulated as
2.3 Outline of RCLS
An RCLS scheme consists of eight algorithms whose details are depicted below.
-
• Setup: A KGC produces a system master secret key $\mathsf{SSK}$ and system public parameters $\mathsf{SPP}$ on input the security parameter k.
-
• Partial-Private-Key-Extraction: A KGC produces a partial private key ${\mathsf{PPK}_{\mathit{ID}}}$ on input $\mathsf{SPP}$, $\mathsf{SSK}$ and an identity $\mathit{ID}$.
-
• Time-Key-Update: A KGC produces the time key ${\mathsf{TK}_{T}}$ on input $\mathsf{SSK}$, $\mathit{ID}$ and a time period T.
-
• Secret-Value-Generation: A user with identity $\mathit{ID}$ calculates the secret value $s{v_{\mathit{ID}}}$ on input $\mathsf{SPP}$.
-
• Public-Key-Generation: A user calculates the public key ${\mathsf{PK}_{\mathit{ID}}}$ on input $\mathsf{SPP}$, $\mathit{ID}$ and the secret value $s{v_{\mathit{ID}}}$ of this identity $\mathit{ID}$.
-
• Secret-Key-Generation: A non-revocation user calculates the full secret key ${\mathsf{SK}_{\mathit{ID}}}$ on input $\mathsf{SPP}$, $\mathit{ID}$, $s{v_{\mathit{ID}}}$ and the corresponding ${\mathsf{PPK}_{\mathit{ID}}}$ and ${\mathsf{TK}_{T}}$.
-
• RCL-Sign: A signer produces a signature σ on input $\mathsf{SPP}$, $\mathit{ID}$, $s{v_{\mathit{ID}}}$, ${\mathsf{SK}_{\mathit{ID}}}$ and a message M.
-
• RCL-Verify: A verifier outputs VALID or INVALID to demonstrate signature σ’s validity on input $\mathsf{SPP}$, $\mathit{ID}$, σ, M, T, ${\mathsf{PK}_{\mathit{ID}}}$.
2.4 Security Model of RCLS
According to the scheme (Al-Riyami and Paterson, 2003), there are two kinds of attackers in the certificateless signature setting, which are usually called the Type-I adversary ${\mathfrak{A}_{I}}$ and Type-II adversary ${\mathfrak{A}_{\mathit{II}}}$. ${\mathfrak{A}_{I}}$ models a malicious user who has the right to replace a legitimate user’s public key without knowing the system master secret key. ${\mathfrak{A}_{\mathit{II}}}$ models a malicious-but-passive KGC who has knowledge of the system master secret key while is not allowed to replace any public key. For a RCLS scheme’s security, there is one more adversary called a revoked user ${\mathfrak{A}_{\mathit{ru}}}$ who cannot obtain the time key but still has the right to replace the public key (Sun et al., 2014). To better explain the attacking ability of these adversaries, we first define six oracles that adversary $\mathfrak{A}\in \{{\mathfrak{A}_{I}},{\mathfrak{A}_{\mathit{II}}},{\mathfrak{A}_{\mathit{ru}}}\}$ can access.
-
• Public-Key-Extract Query: After receiving an identity $\mathit{ID}$, this oracle produces the user’s public key ${\mathsf{PK}_{\mathit{ID}}}$.
-
• Partial-Private-Key-Extract Query: After receiving $\mathit{ID}$, this oracle produces the user $\mathit{ID}$’s partial private key ${\mathsf{PPK}_{\mathit{ID}}}$.
-
• Time-Key-Update Query: After receiving $(\mathit{ID},T)$, this oracle produces the time key ${\mathsf{TK}_{T}}$.
-
• Secret-Value-Extract Query: After receiving $\mathit{ID}$, this oracle produces the user $\mathit{ID}$’s secret value $s{v_{\mathit{ID}}}$.
-
• Public-Key-Replace Query: After receiving $(\mathit{ID},{\mathsf{PK}^{\prime }_{\mathit{ID}}})$, a user $\mathit{ID}$’s public key is replaced with ${\mathsf{PK}^{\prime }_{\mathit{ID}}}$ through this oracle.
-
• RCL-Sign Query: After receiving $\mathit{ID}$, T, ${\mathsf{PK}_{\mathit{ID}}}$ and a message M, this oracle produces a valid signature σ.
Definition 1.
An RCLS scheme is existentially unforgeable (EUF) against a $(t,{q_{\mathit{PK}}},{q_{\mathit{PPK}}},{q_{\mathit{TK}}},{q_{\mathit{SV}}},{q_{\mathit{PKR}}},{q_{S}})$ Type-I adaptively chosen message (CMA) adversary ${\mathfrak{A}_{I}}$ if ${\mathfrak{A}_{I}}$ runs in polynomial time t, makes at most ${q_{\mathit{PK}}}$ queries to the oracle Public-Key-Extract Query, ${q_{\mathit{PPK}}}$ queries to the oracle Partial-Private-Key-Extract Query, ${q_{\mathit{TK}}}$ queries to the oracle Time-Key-Update Query, ${q_{\mathit{SV}}}$ queries to the oracle Secret-Value-Extract Query, ${q_{\mathit{PKR}}}$ queries to the oracle Public-Key-Replace Query, ${q_{S}}$ queries to the oracle RCL-Sign Query and wins in Game I with a negligible advantage.
Game I.
Setup: A challenger $\mathfrak{B}$ generates the system master secret key $\mathsf{SSK}$ and system public parameters $\mathsf{SPP}$ by performing the algorithm Setup. After that, $\mathfrak{B}$ returns $\mathsf{SPP}$ to ${\mathfrak{A}_{I}}$.
Query: ${\mathfrak{A}_{I}}$ queries onto all oracles defined above adaptively.
Forgery: After finishing all queries, ${\mathfrak{A}_{I}}$ outputs a forged signature ${\sigma ^{\ast }}$ on the message ${M^{\ast }}$.
Definition 2.
A RCLS scheme is $(t,{q_{\mathit{PK}}},{q_{\mathit{PPK}}},{q_{\mathit{TK}}},{q_{\mathit{SV}}},{q_{\mathit{PKR}}},{q_{S}})$-EUF-CMA-secure for Type-II adversary ${\mathfrak{A}_{\mathit{II}}}$ if ${\mathfrak{A}_{\mathit{II}}}$ wins in Game II with a negligible advantage.
Game II.
Setup: A challenger $\mathfrak{B}$ generates the system secret key $\mathsf{SSK}$ and system public parameters $\mathsf{SPP}$ by performing the algorithm Setup. After that, $\mathfrak{B}$ returns $\mathsf{SPP}$ and $\mathsf{SSK}$ to ${\mathfrak{A}_{\mathit{II}}}$.
Query: ${\mathfrak{A}_{\mathit{II}}}$ queries onto those oracles defined above adaptively except for the oracle Partial-Private-Key-Extract Query and the oracle Time-Key-Update Query.
Forgery: After finishing all queries, ${\mathfrak{A}_{\mathit{II}}}$ outputs a forged signature ${\sigma ^{\ast }}$ on the message ${M^{\ast }}$.
Definition 3.
A RCLS scheme is $(t,{q_{\mathit{PK}}},{q_{\mathit{PPK}}},{q_{\mathit{TK}}},{q_{\mathit{SV}}},{q_{\mathit{PKR}}},{q_{S}})$-EUF-CMA-secure for a revoked user ${\mathfrak{A}_{\mathit{ru}}}$ if ${\mathfrak{A}_{\mathit{ru}}}$ wins in Game III with a negligible advantage.
Game III.
Setup: A challenger $\mathfrak{B}$ generates the system secret key $\mathsf{SSK}$ and system public parameters $\mathsf{SPP}$ by performing the algorithm Setup. After that, $\mathfrak{B}$ returns $\mathsf{SPP}$ to ${\mathfrak{A}_{\mathit{ru}}}$.
Query: ${\mathfrak{A}_{\mathit{ru}}}$ queries onto all oracles defined above adaptively.
Forgery: After finishing all queries, ${\mathfrak{A}_{\mathit{ru}}}$ outputs a forged signature ${\sigma ^{\ast }}$ on the message ${M^{\ast }}$.
Note that, when the forgery satisfies the following requirements, adversary $\mathfrak{A}\in \{{\mathfrak{A}_{I}},{\mathfrak{A}_{\mathit{II}}},{\mathfrak{A}_{\mathit{ru}}}\}$ will win the above Game I, Game II and Game III:
-
1. If $\mathfrak{A}\in {\mathfrak{A}_{I}}$, $\mathfrak{A}$ has never queried the oracle Partial-Private-Key-Extract Query with ${\mathit{ID}^{\ast }}$.
-
2. If $\mathfrak{A}\in {\mathfrak{A}_{\mathit{II}}}$, $\mathfrak{A}$ has never queried the oracle Secret-Value-Extract Query with ${\mathit{ID}^{\ast }}$ nor queried the oracle Public-Key-Replace Query with ${\mathsf{PK}_{{\mathit{ID}^{\ast }}}}$.
-
3. If $\mathfrak{A}\in {\mathfrak{A}_{\mathit{ru}}}$, $\mathfrak{A}$ has never queried the oracle Time-Key-Update Query with $({\mathit{ID}^{\ast }},{T^{\ast }})$.
-
4. $\mathfrak{A}$ has never queried the oracle RCL-Sign Query with $({\mathit{ID}^{\ast }},{M^{\ast }},{T^{\ast }})$.
-
5. $\mathit{VALID}\gets \text{RCL-Verify}(\mathsf{SPP},{\mathit{ID}^{\ast }},{\sigma ^{\ast }},{M^{\ast }},{T^{\ast }},{\mathsf{PK}_{{\mathit{ID}^{\ast }}}})$.
3 A Brief Analysis of Tsai et al.’s Scheme
This section first sketches out the certificateless signature with revocation scheme of Tsai et al. (2014), and then demonstrates that Tsai et al.’s RCLS scheme cannot resist the malicious-but-passive KGC attacks.
3.1 Overview of Tsai et al.’s RCLS Scheme
Define five collision-resistant hash functions ${\mathcal{H}_{0}}:{\{0,1\}^{\ast }}\to {\{0,1\}^{{n_{u}}}}$, ${\mathcal{H}_{1}}:{\{0,1\}^{\ast }}\to {\{0,1\}^{{n_{t}}}}$, ${\mathcal{H}_{2}}:\mathcal{G}\times \mathcal{G}\to {\{0,1\}^{{n_{k}}}}$, ${\mathcal{H}_{3}}:\mathcal{G}\times \mathcal{G}\to {\{0,1\}^{{n_{s}}}}$, ${\mathcal{H}_{4}}:{\{0,1\}^{\ast }}\to {\{0,1\}^{{n_{m}}}}$, where ${n_{u}}$, ${n_{t}}$, ${n_{m}}$, ${n_{s}}$, ${n_{k}}$, are fixed lengths from $\mathcal{Z}$.
-
• Setup: Taken k as the security parameter, KGC generates a bilinear map $\hat{e}:\mathcal{G}\times \mathcal{G}\to {\mathcal{G}_{T}}$, where $\mathcal{G}$, ${\mathcal{G}_{T}}$ are cyclic groups of order p. Furthermore, KGC picks $x,y\in {\mathcal{Z}_{p}^{\ast }}$, $g,{g_{1}},{g_{2}}\in \mathcal{G}$ and calculates ${g_{1}}={g^{x+y}}$, $\mathsf{SSK}={g_{2}^{x}}$, where $g,\mathsf{SSK}$ denote a generator of $\mathcal{G}$ and the system secret key respectively. In addition, let ${g_{2}^{y}}$ denotes the time secret key. After that, KGC randomly selects ${u^{\prime }},{t^{\prime }},{k^{\prime }},{s^{\prime }},{m^{\prime }}\in \mathcal{G}$, and five vectors $\mathbf{U}=[{u_{i}}]\in {\mathcal{G}^{{n_{u}}}}$, $\mathbf{T}=[{t_{i}}]\in {\mathcal{G}^{{n_{t}}}}$, $\mathbf{K}=[{k_{i}}]\in {\mathcal{G}^{{n_{k}}}}$, $\mathbf{S}=[{s_{i}}]\in {\mathcal{G}^{{n_{s}}}}$, $\mathbf{M}=[{m_{i}}]\in {\mathcal{G}^{{n_{m}}}}$. Finally, KGC issues the system public parameters $\mathsf{SPP}=\langle \mathcal{G},{\mathcal{G}_{T}},\hat{e},g,{g_{1}},{g_{2}},\mathbf{U},\mathbf{T},\mathbf{K},\mathbf{S},\mathbf{M},{\mathcal{H}_{0}},{\mathcal{H}_{1}},{\mathcal{H}_{2}},{\mathcal{H}_{3}},{\mathcal{H}_{4}},{u^{\prime }},{t^{\prime }},{k^{\prime }},{s^{\prime }},{m^{\prime }}\rangle $.
-
• Partial-Private-Key-Extraction: After receiving $\mathsf{SSK},\mathsf{SPP}$, and a user’s identity $\mathit{ID}$, KGC will first calculate a set as $\nu ={\mathcal{H}_{0}}(\mathit{ID})=\{{\nu _{1}},{\nu _{2}},\dots ,{\nu _{{n_{u}}}}\}$. Then KGC calculates the user’s partial private key ${\mathsf{PPK}_{\mathit{ID}}}=({\mathsf{PPK}^{(1)}},{\mathsf{PPK}^{(2)}})=({g_{2}^{x}}{({u^{\prime }}{\textstyle\prod _{i=1}^{{n_{u}}}}{u_{i}^{{\nu _{i}}}})^{{r_{\nu }}}},{g^{{r_{\nu }}}})$ where ${r_{\nu }}$ is randomly selected by KGC from ${\mathcal{Z}_{p}^{\ast }}$.
-
• Time-Key-Update: Upon receiving $\mathsf{SSK},\mathit{ID}$ and a time period T, KGC calculates a set as $\nu t={\mathcal{H}_{1}}(\mathit{ID},t)=(\nu {t_{1}},\nu {t_{2}},\dots ,\nu {t_{{n_{t}}}})$, and sets the time key ${\mathsf{TK}_{T}}=({\mathsf{TK}^{(1)}},{\mathsf{TK}^{(2)}})=({g_{2}^{y}}{({t^{\prime }}{\textstyle\prod _{i=1}^{{n_{t}}}}{t_{i}^{\nu {t_{i}}}})^{{r_{t}}}},{g^{{r_{t}}}})$ where ${r_{t}}$ is randomly selected by KGC from ${\mathcal{Z}_{p}^{\ast }}$.
-
• Secret-Value-Generation: A user with identity $\mathit{ID}$ randomly picks ${x_{1}},{x_{2}}\in {\mathcal{Z}_{p}^{\ast }}$ and sets the secret value $s{v_{\mathit{ID}}}=({x_{1}},{x_{2}})$.
-
• Public-Key-Generation: The user with identity $\mathit{ID}$ calculates ${\mathsf{PK}_{\mathit{ID}}}=({\mathsf{PK}^{(1)}},{\mathsf{PK}^{(2)}})=({g^{{x_{1}}}},{g^{{x_{2}}}})$ as the public key.
-
• Secret-Key-Generation: The user $\mathit{ID}$ computes a set as $\nu u={\mathcal{H}_{2}}({\mathsf{PK}^{(1)}},{\mathsf{PK}^{(2)}})=\{\nu {u_{1}},\nu {u_{2}},\dots ,\nu {u_{{n_{k}}}}\}$ and $\nu s={\mathcal{H}_{3}}({\mathsf{PK}^{(1)}},{\mathsf{PK}^{(2)}})=\{\nu {s_{1}},\nu {s_{2}},\dots ,\nu {s_{{n_{s}}}}\}$. Then, the algorithm calculates the secret key ${\mathsf{SK}_{\mathit{ID}}}={g_{2}^{{x_{1}}}}{({k^{\prime }}{\textstyle\prod _{i=1}^{{n_{k}}}}{k_{i}^{\nu {u_{i}}}})^{{x_{1}}}}{({s^{\prime }}{\textstyle\prod _{i=1}^{{n_{s}}}}{s_{i}^{\nu {s_{i}}}})^{{x_{2}}}}$.
-
• RCL-Sign: Upon receiving ${\mathsf{PPK}_{\mathit{ID}}}=({\mathsf{PPK}^{(1)}},{\mathsf{PPK}^{(2)}})$ and ${\mathsf{TK}_{T}}=({\mathsf{TK}^{(1)}},{\mathsf{TK}^{(2)}})$, a signer $\mathit{ID}$ can sign a message $M\in {\{0,1\}^{\ast }}$ with a secret key ${\mathsf{SK}_{\mathit{ID}}}$ by performing the following steps:
-
(1) Define a set as $\nu m={\mathcal{H}_{4}}(M)=\{\nu {m_{1}},\nu {m_{2}},\dots ,\nu {m_{{n_{m}}}}\}$.
-
(2) Randomly select ${r_{m}}\in {\mathcal{Z}_{p}^{\ast }}$ and calculate ${\sigma _{1}}={\mathsf{PPK}^{(1)}}\cdot {\mathsf{TK}^{(1)}}\cdot {\mathsf{SK}_{\mathit{ID}}}{({m^{\prime }}{\textstyle\prod _{i=1}^{{n_{m}}}}{m_{i}^{\nu {m_{i}}}})^{{r_{m}}}}$, ${\sigma _{2}}={\mathsf{PPK}^{(2)}}$, ${\sigma _{3}}={\mathsf{TK}^{(2)}}$, ${\sigma _{4}}={g^{{r_{m}}}}$.
-
(3) Output a revocable certificateless signature $\sigma =({\sigma _{1}},{\sigma _{2}},{\sigma _{3}},{\sigma _{4}})$ of the message M and return to a verifier.
-
-
• RCL-Verify: Given $\mathsf{SPP}$, $\mathit{ID}$, σ, M, t, ${\mathsf{PK}_{\mathit{ID}}}$, the verifier calculates five sets $\nu ={\mathcal{H}_{0}}(\mathit{ID})$, $\nu t={\mathcal{H}_{1}}(\mathit{ID},t)$, $\nu u={\mathcal{H}_{2}}({\mathsf{PK}^{(1)}},{\mathsf{PK}^{(2)}})$, $\nu s={\mathcal{H}_{3}}({\mathsf{PK}^{(1)}},{\mathsf{PK}^{(2)}})$, $\nu m={\mathcal{H}_{4}}(M)$. After that, the verifier can check the equation : $\hat{e}(g,{\sigma _{1}})\stackrel{?}{=}\hat{e}({g_{1}},{g_{2}})\cdot \hat{e}({\sigma _{2}},{u^{\prime }}{\textstyle\prod _{i=1}^{{n_{u}}}}{u_{i}^{{\nu _{i}}}})\cdot \hat{e}({\sigma _{3}},{t^{\prime }}{\textstyle\prod _{i=1}^{{n_{t}}}}{t_{i}^{\nu {t_{i}}}})\cdot \hat{e}({\mathsf{PK}^{(1)}},{g_{2}}({k^{\prime }}{\textstyle\prod _{i=1}^{{n_{k}}}}{k_{i}^{\nu {u_{i}}}}))\cdot \hat{e}({\mathsf{PK}^{(2)}},{s^{\prime }}{\textstyle\prod _{i=1}^{{n_{s}}}}{s_{i}^{\nu {s_{i}}}})\cdot \hat{e}({\sigma _{4}},{m^{\prime }}{\textstyle\prod _{i=1}^{{n_{m}}}}{m_{i}^{\nu {m_{i}}}})$. If the equation holds, output VALID, otherwise, output INVALID.
3.2 Forgery Attack of Tsai et al.’s Scheme
Tsai et al. alleged that their scheme (Tsai et al., 2014) was secure against Type-I and Type-II adversaries under the standard model. After a careful investigation, however, we found that their scheme was insecure against a Type-II adversary. Then we show a concrete attack instance to demonstrate that the scheme in Tsai et al. (2014) is so vulnerable that any malicious-but-passive KGC, ${\mathfrak{A}_{\mathit{II}}}$, can forge a valid signature of message ${M^{\ast }}$ for identity ${\mathit{ID}^{\ast }}$. The attack is as follows:
-
(1) ${\mathfrak{A}_{\mathit{II}}}$ randomly selects $\alpha ,\beta ,\gamma \in {\mathcal{Z}_{p}^{\ast }}$ and calculates ${g_{2}^{\ast }}={g^{\gamma }},{k^{{^{\prime }}\ast }}={g^{\alpha }},{s^{{^{\prime }}\ast }}={g^{\beta }}$. Besides, ${\mathfrak{A}_{\mathit{II}}}$ sets ${K^{\ast }}=[{k_{i}}]=[{g^{{\alpha _{i}}}}]\in {\mathcal{G}^{{n_{k}}}}$, ${S^{\ast }}=[{s_{i}}]=[{g^{{\beta _{i}}}}]\in {\mathcal{G}^{{n_{s}}}}$, where ${\alpha _{i}},{\beta _{i}}\in {\mathbb{Z}_{p}^{\ast }}$. Other parameters in the system master secret key and system public parameters are generated normally by the KGC. Finally, ${\mathfrak{A}_{\mathit{II}}}$ publishes these public parameters.
-
(2) By making a hash query on $({\mathsf{PK}^{(1)}},{\mathsf{PK}^{(2)}}),{\mathfrak{A}_{\mathit{II}}}$ can obtain the hash value $vu,vs$. Then ${\mathfrak{A}_{\mathit{II}}}$ can calculate ${k^{{^{\prime }}\ast }}{\textstyle\prod _{i=1}^{{n_{k}}}}{k_{i}^{\nu {u_{i}}}}={g^{(\alpha +{\Sigma _{i=1}^{{n_{k}}}}{\alpha _{i}}\nu {u_{i}})}}$, ${s^{{^{\prime }}\ast }}{\textstyle\prod _{i=1}^{{n_{s}}}}{s_{i}^{\nu {s_{i}}}}={g^{(\beta +{\Sigma _{i=1}^{{n_{s}}}}{\beta _{i}}\nu {s_{i}})}}$.
-
(3) ${\mathfrak{A}_{\mathit{II}}}$ randomly picks $a,b,c\in {\mathcal{Z}_{p}^{\ast }}$ and calculates ${\sigma _{2}^{\ast }}={g^{a}},{\sigma _{3}^{\ast }}={g^{b}},{\sigma _{4}^{\ast }}={g^{c}}$.
-
(4) ${\mathfrak{A}_{\mathit{II}}}$ calculates ${\sigma _{1}^{\ast }}={g_{1}^{\gamma }}\cdot {({u^{\prime }}{\textstyle\prod _{i=1}^{{n_{u}}}}{u_{i}^{{\nu _{i}}}})^{a}}\cdot {({t^{\prime }}{\textstyle\prod _{i=1}^{{n_{t}}}}{t_{i}^{\nu {t_{i}}}})^{b}}\cdot {({\mathsf{PK}^{(1)}})^{(\gamma +\alpha +{\Sigma _{i=1}^{{n_{k}}}}{\alpha _{i}}\nu {u_{i}})}}\cdot {({\mathsf{PK}^{(2)}})^{(\beta +{\Sigma _{i=1}^{{n_{s}}}}{\beta _{i}}\nu {s_{i}})}}\cdot {({m^{\prime }}{\textstyle\prod _{i=1}^{{n_{m}}}}{m_{i}^{\nu {m_{i}}}})^{c}}$.
-
(5) The signature on the message ${M^{\ast }}$ is ${\sigma ^{\ast }}=({\sigma _{1}^{\ast }},{\sigma _{2}^{\ast }},{\sigma _{3}^{\ast }},{\sigma _{4}^{\ast }})$.
Anyone can verify the signature ${\sigma ^{\ast }}$ through performing the algorithm RCL-Verify, which is to check whether the equation $\hat{e}(g,{\sigma _{1}^{\ast }})\stackrel{?}{=}\hat{e}({g_{1}},{g_{2}^{\ast }})\cdot \hat{e}({\sigma _{2}^{\ast }},{u^{\prime }}{\textstyle\prod _{i=1}^{{n_{u}}}}{u_{i}^{{\nu _{i}}}})\cdot \hat{e}({\sigma _{3}^{\ast }},{t^{\prime }}{\textstyle\prod _{i=1}^{{n_{t}}}}{t_{i}^{\nu {t_{i}}}})\cdot \hat{e}({\mathsf{PK}^{(1)}},{g_{2}^{\ast }}({k^{{^{\prime }}\ast }}{\textstyle\prod _{i=1}^{{n_{k}}}}{k_{i}^{\nu {u_{i}}}}))\cdot \hat{e}({\mathsf{PK}^{(2)}},{s^{{^{\prime }}\ast }}{\textstyle\prod _{i=1}^{{n_{s}}}}{s_{i}^{\nu {s_{i}}}})\cdot \hat{e}({\sigma _{4}^{\ast }},{m^{\prime }}{\textstyle\prod _{i=1}^{{n_{m}}}}{m_{i}^{\nu {m_{i}}}})$ holds. This verification will hold due to the following fact:
\[\begin{aligned}{}\hat{e}(g,{\sigma _{1}^{\ast }})=& \hat{e}\Bigg(g,{g_{1}^{\gamma }}\cdot {\Bigg({u^{\prime }}{\prod \limits_{i=1}^{{n_{u}}}}{u_{i}^{{\nu _{i}}}}\Bigg)^{a}}\cdot {\bigg({t^{\prime }}{\prod \limits_{i=1}^{{n_{t}}}}{t_{i}^{\nu {t_{i}}}}\bigg)^{b}}\cdot {\big({\mathsf{PK}^{(1)}}\big)^{(\gamma +\alpha +{\Sigma _{i=1}^{{n_{k}}}}{\alpha _{i}}\nu {u_{i}})}}\\ {} & \cdot {\big({\mathsf{PK}^{(2)}}\big)^{(\beta +{\Sigma _{i=1}^{{n_{s}}}}{\beta _{i}}\nu {s_{i}})}}\cdot {\Bigg({m^{\prime }}{\prod \limits_{i=1}^{{n_{m}}}}{m_{i}^{\nu {m_{i}}}}\Bigg)^{c}}\Bigg)\\ {} =& \hat{e}\big({g_{1}},{g^{\gamma }}\big)\cdot \hat{e}\Bigg({g^{a}},{u^{\prime }}{\prod \limits_{i=1}^{{n_{u}}}}{u_{i}^{{\nu _{i}}}}\Bigg)\cdot \hat{e}\Bigg({g^{b}},{t^{\prime }}{\prod \limits_{i=1}^{{n_{t}}}}{t_{i}^{\nu {t_{i}}}}\Bigg)\\ {} & \cdot \hat{e}\big({\mathsf{PK}^{(1)}},{g^{(\gamma +\alpha +{\Sigma _{i=1}^{{n_{k}}}}{\alpha _{i}}\nu {u_{i}})}}\big)\\ {} & \cdot \hat{e}\big({\mathsf{PK}^{(2)}},{g^{(\beta +{\Sigma _{i=1}^{{n_{s}}}}{\beta _{i}}\nu {s_{i}})}}\big)\cdot \hat{e}\Bigg({g^{c}},{m^{\prime }}{\prod \limits_{i=1}^{{n_{m}}}}{m_{i}^{\nu {m_{i}}}}\Bigg)\\ {} =& \hat{e}\big({g_{1}},{g_{2}^{\ast }}\big)\cdot \hat{e}\Bigg({\sigma _{2}^{\ast }},{u^{\prime }}{\prod \limits_{i=1}^{{n_{u}}}}{u_{i}^{{\nu _{i}}}}\Bigg)\cdot \hat{e}\Bigg({\sigma _{3}^{\ast }},{t^{\prime }}{\prod \limits_{i=1}^{{n_{t}}}}{t_{i}^{\nu {t_{i}}}}\Bigg)\\ {} & \cdot \hat{e}\Bigg({\mathsf{PK}^{(1)}},{g_{2}^{\ast }}\Bigg({k^{{^{\prime }}\ast }}{\prod \limits_{i=1}^{{n_{k}}}}{k_{i}^{\nu {u_{i}}}}\Bigg)\Bigg)\\ {} & \cdot \hat{e}\Bigg({\mathsf{PK}^{(2)}},{s^{{^{\prime }}\ast }}{\prod \limits_{i=1}^{{n_{s}}}}{s_{i}^{\nu {s_{i}}}}\Bigg)\cdot \hat{e}\Bigg({\sigma _{4}^{\ast }},{m^{\prime }}{\prod \limits_{i=1}^{{n_{m}}}}{m_{i}^{\nu {m_{i}}}}\Bigg).\end{aligned}\]
Notice that ${\mathfrak{A}_{\mathit{II}}}$ neither knows $s{v_{\mathit{ID}}}=({x_{1}},{x_{2}})$ nor replaces $({\mathsf{PK}^{(1)}},{\mathsf{PK}^{(2)}})$. Thus, the RCLS scheme of Tsai et al. cannot withstand the forgery attack mounted by a malicious-but-passive KGC. The underlying reason is that the user secret value $s{v_{\mathit{ID}}}$ is embedded in the signature inappropriately such that the user public key ${g^{{x_{1}}}},{g^{{x_{2}}}}$ can be utilized by the malicious-but-passive KGC to forge the signature with the support of the random numbers associated with the system parameters. Specially, ${\mathsf{SK}_{\mathit{ID}}}={g_{2}^{{x_{1}}}}{({k^{\prime }}{\textstyle\prod _{i=1}^{{n_{k}}}}{k_{i}^{\nu {u_{i}}}})^{{x_{1}}}}{({s^{\prime }}{\textstyle\prod _{i=1}^{{n_{s}}}}{s_{i}^{\nu {s_{i}}}})^{{x_{2}}}}$ has been regarded as one factor in the generation of signature ${\sigma _{1}}$, and this factor can be easily generated by raising the ${g^{{x_{1}}}},{g^{{x_{2}}}}$ with the exponentiations $\alpha ,\beta ,\gamma ,{\alpha _{i}},{\beta _{i}}$. Therefore, it is easy to forge the signature σ to make the equation hold in the algorithm RCL-Verify.
4 Our Proposed RCLS Scheme
This section describes a revocable certificateless signature scheme without random oracles and presents the concrete construction. Afterwards, this section represents the security analysis, which demonstrates that our proposed RCLS scheme is EUF-CMA-secure in the standard model.
4.1 Construction
Inspired by a certificateless signature scheme in the standard model that can resist the malicious-but-passive attacks (Shim, 2018a), we construct a certificateless signature scheme with revocation in the standard model. In the proposed scheme, it is possible to construct a RCLS scheme secure against the Type-I and II attackers as well as the malicious-but-passive attacks by using the term ${({g_{3}^{{x_{2}}}})^{{x_{1}^{-1}}}}$. To be specific, although a malicious KGC calculates ${g_{3}}$ as ${g^{\omega }}$ of its own choice ω to implement the malicious-but-passive attack, the malicious KGC cannot calculate ${({g_{3}^{{x_{2}}}})^{{x_{1}^{-1}}}}$ without the knowledge of ${x_{1}}$. In other words, if one uses ${g_{3}^{{x_{2}}}}$ instead of ${({g_{3}^{{x_{2}}}})^{{x_{1}^{-1}}}}$, the malicious KGC can calculate ${g_{3}^{{x_{2}}}}$ by calculating ${({g^{{x_{2}}}})^{\omega }}$ from the known user’s public key ${g^{{x_{2}}}}$. In fact, there does not exist a probabilistic polynomial-time algorithm that can calculate ${g_{3}^{{x_{2}}}}$ with non-negligible advantage on inputting $g,{g^{\omega }},{g^{{x_{2}}}}$. Besides, there does not exist a probabilistic polynomial-time algorithm that can calculate ${({g_{3}^{{x_{2}}}})^{{x_{1}^{-1}}}}$ with non-negligible advantage on inputting ${g_{3}},{g_{3}^{{x_{1}}}},{g_{3}^{{x_{2}}}}$, which is equivalent to the CDH problem according to Bao et al. (2003). The detail description of the proposed RCLS scheme is presented as follows:
Define three collision-resistant hash functions ${\mathcal{H}_{0}}:{\{0,1\}^{\ast }}\to {\{0,1\}^{{n_{u}}}}$, ${\mathcal{H}_{1}}:{\{0,1\}^{\ast }}\to {\{0,1\}^{{n_{t}}}}$, ${\mathcal{H}_{2}}:{\{0,1\}^{\ast }}\to {\{0,1\}^{{n_{m}}}}$, where ${n_{u}},{n_{t}},{n_{m}}$ are fixed lengths from $\mathcal{Z}$.
-
• Setup: Taken k as the security parameter, KGC generates a bilinear map $\hat{e}:\mathcal{G}\times \mathcal{G}\to {\mathcal{G}_{T}}$, where $\mathcal{G},{\mathcal{G}_{T}}$ are cyclic groups of order p. Furthermore, KGC picks $x,y\in {\mathcal{Z}_{p}^{\ast }},{g_{2}},{g_{3}}\in \mathcal{G}$ and calculates ${g_{1}}={g^{x+y}}$, $A=\hat{e}({g_{1}},{g_{2}})$, $\mathsf{SSK}=({g_{2}^{x}},{g_{2}^{y}})$, where $g,\mathsf{SSK}$ denote a generator of $\mathcal{G}$ and the system secret key respectively. After that, KGC randomly selects $\alpha ,\beta ,\gamma \in \mathcal{G}$, and three vectors $\mathbf{U}=[{u_{i}}]\in {\mathcal{G}^{{n_{u}}}}$, $\mathbf{T}=[{t_{i}}]\in {\mathcal{G}^{{n_{t}}}}$, $\mathbf{M}=[{m_{i}}]\in {\mathcal{G}^{{n_{m}}}}$. Define three functions ${f_{1}},{f_{2}},{f_{3}}$ via ${f_{1}}(\mathcal{U})=\alpha {\textstyle\prod _{i\in \mathcal{U}}}{u_{i}}$, ${f_{2}}(\mathcal{T})=\beta {\textstyle\prod _{i\in \mathcal{T}}}{t_{i}}$, ${f_{3}}(\mathcal{M})=\gamma {\textstyle\prod _{i\in \mathcal{M}}}{m_{i}}$, where $\mathcal{U}\subseteq \{1,2,\dots ,{n_{u}}\}$, $\mathcal{T}\subseteq \{1,2,\dots ,{n_{t}}\}$, $\mathcal{M}\subseteq \{1,2,\dots ,{n_{m}}\}$. Finally, KGC issues the system public parameters $\mathsf{SPP}=\langle \mathcal{G},{\mathcal{G}_{T}},\hat{e},g,{g_{1}},{g_{2}},{g_{3}},A,{f_{1}},{f_{2}},{f_{3}},\mathbf{U},\mathbf{T},\mathbf{M},{\mathcal{H}_{0}},{\mathcal{H}_{1}},{\mathcal{H}_{2}}\rangle $.
-
• Partial-Private-Key-Extraction: After receiving $\mathsf{SSK},\mathsf{SPP}$, and a user’s identity $\mathit{ID}$, KGC will first calculate a set as ${\mathcal{F}_{\mathit{ID}}}=\{i|u[i]=1,u={\mathcal{H}_{0}}(\mathit{ID})\}\subseteq \{1,2,\dots ,{n_{u}}\}$. Then KGC calculates the user’s partial private key ${\mathsf{PPK}_{\mathit{ID}}}=({\mathsf{PPK}^{(1)}},{\mathsf{PPK}^{(2)}})=({g_{2}^{x}}{f_{1}}{({\mathcal{F}_{\mathit{ID}}})^{{r_{u}}}},{g^{{r_{u}}}})$ where ${r_{u}}$ is randomly selected by KGC from ${\mathcal{Z}_{p}^{\ast }}$.
-
• Time-Key-Update: Upon receiving $\mathsf{SSK},\mathit{ID}$ and a time period T, KGC calculates a set as ${\mathcal{F}_{\mathit{ID},t}}=\{i|{t^{\prime }}[i]=1,{t^{\prime }}={\mathcal{H}_{1}}(\mathit{ID},t)\}\subseteq \{1,2,\dots ,{n_{t}}\}$, and sets the time key ${\mathsf{TK}_{T}}=({\mathsf{TK}^{(1)}},{\mathsf{TK}^{(2)}})=({g_{2}^{y}}{f_{2}}{({\mathcal{F}_{\mathit{ID},t}})^{{r_{t}}}},{g^{{r_{t}}}})$ where ${r_{t}}$ is randomly selected by KGC from ${\mathcal{Z}_{p}^{\ast }}$.
-
• Secret-Value-Generation: A user with identity $\mathit{ID}$ randomly picks ${x_{1}},{x_{2}}\in {\mathcal{Z}_{p}^{\ast }}$ and sets the secret value $s{v_{\mathit{ID}}}=({x_{1}},{x_{2}})$.
-
• Public-Key-Generation: The user $\mathit{ID}$ calculates ${\mathsf{PK}_{\mathit{ID}}}=({\mathsf{PK}^{(1)}},{\mathsf{PK}^{(2)}})=({g^{{x_{1}}}},{g^{{x_{2}}}})$ as the public key.
-
• Secret-Key-Generation: The user $\mathit{ID}$ randomly selects $\lambda ,\mu \in {\mathcal{Z}_{p}^{\ast }}$ and calculates the secret key ${\mathsf{SK}_{\mathit{ID}}}=({\mathsf{SK}^{(1)}},{\mathsf{SK}^{(2)}},{\mathsf{SK}^{(3)}})=({({\mathsf{PPK}^{(1)}}\cdot {\mathsf{TK}^{(1)}}\cdot {f_{1}}{({\mathcal{F}_{\mathit{ID}}})^{\lambda }}\cdot {f_{2}}{({\mathcal{F}_{\mathit{ID},t}})^{\mu }}\cdot {g_{3}^{{x_{2}}}})^{{x_{1}^{-1}}}},{\mathsf{PPK}^{(2)}}\cdot {g^{\lambda }},{\mathsf{TK}^{(2)}}\cdot {g^{\mu }})$.
-
• RCL-Sign: Upon receiving $\mathsf{SPP}$ and ${\mathsf{PK}_{\mathit{ID}}}$, a signer $\mathit{ID}$ can sign a message $M\in {\{0,1\}^{\ast }}$ with a secret key ${\mathsf{SK}_{\mathit{ID}}}$ and signer’s secret value $s{v_{\mathit{ID}}}$ by performing the following steps:
-
(1) Define a set as ${\mathcal{F}_{M}}=\{i|m[i]=1,m={\mathcal{H}_{2}}(M,\mathit{ID},{\mathsf{PK}_{\mathit{ID}}})\}\subseteq \{1,2,\dots ,{n_{m}}\}$.
-
(2) Randomly select $\nu \in {\mathcal{Z}_{p}^{\ast }}$ and calculate ${\sigma _{1}}={\mathsf{SK}^{(1)}}\cdot {({f_{3}}{({\mathcal{F}_{M}})^{\nu }})^{{x_{1}^{-1}}}}$, ${\sigma _{2}}={\mathsf{SK}^{(2)}}$, ${\sigma _{3}}={\mathsf{SK}^{(3)}}$, ${\sigma _{4}}={g^{\nu }}$.
-
(3) Output a revocable certificateless signature $\sigma =({\sigma _{1}},{\sigma _{2}},{\sigma _{3}},{\sigma _{4}})$ of the message M and return to a verifier.
-
-
• RCL-Verify: Given $\mathsf{SPP},\mathit{ID},\sigma ,M,t,{\mathsf{PK}_{\mathit{ID}}}$, any verifier can check the equation $\hat{e}({\sigma _{1}},{\mathsf{PK}^{(1)}})\stackrel{?}{=}A\cdot \hat{e}({f_{1}}({\mathcal{F}_{\mathit{ID}}}),{\sigma _{2}})\cdot \hat{e}({f_{2}}({\mathcal{F}_{\mathit{ID},t}}),{\sigma _{3}})\cdot \hat{e}({f_{3}}({\mathcal{F}_{M}}),{\sigma _{4}})\cdot \hat{e}({g_{3}},{\mathsf{PK}^{(2)}})$. If theequation holds, output VALID, otherwise, output INVALID.
4.2 Security Analysis
Theorem 1.
The proposed scheme is $(t,{q_{\mathit{PPK}}},{q_{\mathit{TK}}},{q_{S}},\epsilon )$-EUF-CMA-secure in Game I defined in Section 2 if the $({t^{\prime }},{\epsilon ^{\prime }})$-CDH assumption holds in $\mathcal{G}$, where
Proof.
Assume that ${\mathfrak{A}_{I}}$ is a Type-I attacker against the proposed scheme. There is a ${t^{\prime }}$-time algorithm $\mathfrak{B}$ that can solve the CDH problem with advantage at least ${\epsilon ^{\prime }}$ by interacting with ${\mathfrak{A}_{I}}$.
Let g be a generator of $\mathcal{G}$, ${g^{a}},{g^{b}}$ be two elements of $\mathcal{G}$ where $a,b\in {\mathcal{Z}_{p}^{\ast }}$. The algorithm $\mathfrak{B}$ can compute ${g^{ab}}$ as the solution of CDH problem by simulating a challenger for ${\mathfrak{A}_{I}}$.
Setup: $\mathfrak{B}$ sets ${l_{u}}=2({q_{\mathit{PPK}}}+{q_{S}}),{l_{m}}=2{q_{S}}$. Suppose that ${l_{u}}({n_{u}}+1)\leqslant p$, ${l_{m}}({n_{m}}+1)\leqslant p$. Next $\mathfrak{B}$ randomly selects two integers ${k_{u}},{k_{m}}$ with $0\leqslant {k_{u}}\leqslant {n_{u}}$, $0\leqslant {k_{m}}\leqslant {n_{m}}$. Afterwards, the following integers are selected by $\mathfrak{B}$:
\[\begin{aligned}{}& {x^{\prime }}\in {\mathcal{Z}_{{l_{u}}}},\hspace{2em}{z^{\prime }}\in {\mathcal{Z}_{{l_{m}}}},\hspace{2em}{y^{\prime }},{v^{\prime }},{w^{\prime }}\in {\mathcal{Z}_{p}^{\ast }},\\ {} & \mathbf{X}=[{x_{i}}]\in {\mathcal{Z}_{{l_{u}}}^{{n_{u}}}},\hspace{2em}\mathbf{Y}=[{y_{i}}]\in {\mathcal{Z}_{p}^{{n_{u}}}},\\ {} & \mathbf{V}=[{v_{i}}]\in {\mathcal{Z}_{p}^{{n_{t}}}},\hspace{2em}\mathbf{Z}=[{z_{i}}]\in {\mathcal{Z}_{{l_{m}}}^{{n_{m}}}},\hspace{2em}\mathbf{W}=[{w_{i}}]\in {\mathcal{Z}_{p}^{{n_{m}}}}.\end{aligned}\]
Besides, $\mathfrak{B}$ defines five functions for $u={\mathcal{H}_{0}}(\mathit{ID})$, $ut={\mathcal{H}_{1}}(\mathit{ID},t)$, $m={\mathcal{H}_{2}}(M,\mathit{ID},{\mathsf{PK}_{\mathit{ID}}})$ as follows:
\[\begin{aligned}{}& {F_{1}}(u)={x^{\prime }}+\sum \limits_{i\in \mathcal{U}}{x_{i}}-{l_{u}}{k_{u}},\hspace{2em}{J_{1}}(u)={y^{\prime }}+\sum \limits_{i\in \mathcal{U}}{y_{i}},\hspace{1em}\text{where}\hspace{2.5pt}\mathcal{U}\subseteq \{1,2,\dots ,{n_{u}}\},\\ {} & {J_{2}}(ut)={v^{\prime }}+\sum \limits_{i\in \mathcal{T}}{v_{i}},\hspace{1em}\text{where}\hspace{2.5pt}\hspace{2.5pt}\mathcal{T}\subseteq \{1,2,\dots ,{n_{t}}\},\\ {} & {F_{2}}(m)={z^{\prime }}+\sum \limits_{i\in \mathcal{M}}{z_{i}}-{l_{m}}{k_{m}},\hspace{2.5pt}{J_{3}}(m)={w^{\prime }}+\sum \limits_{i\in \mathcal{M}}{w_{i}},\hspace{1em}\text{where}\hspace{2.5pt}\mathcal{M}\subseteq \{1,2,\dots ,{n_{m}}\}.\end{aligned}\]
After that, $\mathfrak{B}$ randomly selects $\alpha \in {\mathcal{Z}_{p}^{\ast }}$, then sets the following parameters
\[\begin{aligned}{}& {g_{1}}={g^{a}}{g^{\alpha }},\hspace{2em}{g_{2}}={g^{b}},\\ {} & {u^{\prime }}={g_{2}^{-{l_{u}}{k_{u}}+{x^{\prime }}}}{g^{{y^{\prime }}}},\hspace{2em}{u_{i}}={g_{2}^{{x_{i}}}}{g^{{y_{i}}}}\hspace{1em}(1\leqslant i\leqslant {n_{u}}),\\ {} & {t^{\prime }}={g^{{v^{\prime }}}},\hspace{2em}{t_{i}}={g^{{v_{i}}}}\hspace{1em}(1\leqslant i\leqslant {n_{t}}),\\ {} & {m^{\prime }}={g_{2}^{-{l_{m}}{k_{m}}+{z^{\prime }}}}{g^{{w^{\prime }}}},\hspace{2em}{m_{i}}={g_{2}^{{z_{i}}}}{g^{{w_{i}}}}\hspace{1em}(1\leqslant i\leqslant {n_{m}})\end{aligned}\]
and constructs the following equations:
\[\begin{aligned}{}& {f_{1}}(\mathcal{U})={u^{\prime }}\prod \limits_{i\in \mathcal{U}}{u_{i}}={g_{2}^{{F_{1}}(u)}}{g^{{J_{1}}(u)}},\hspace{2em}{f_{2}}(\mathcal{T})={t^{\prime }}\prod \limits_{i\in \mathcal{T}}{t_{i}}={g^{{J_{2}}(ut)}},\\ {} & {f_{3}}(\mathcal{M})={m^{\prime }}\prod \limits_{i\in \mathcal{M}}{m_{i}}={g_{2}^{{F_{2}}(m)}}{g^{{J_{3}}(m)}}.\end{aligned}\]
Query: Attacker ${\mathfrak{A}_{I}}$ performs queries adaptively as following:
-
• Public-Key-Extract Query: At first, $\mathfrak{B}$ maintains a list ${L_{\mathit{PK}}}=\{(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})\}$ in order to respond to these queries. When an identity $\mathit{ID}$ is supplied to this oracle, $\mathfrak{B}$ inspects the list ${L_{\mathit{PK}}}$:
-
(1) If the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ exists in ${L_{\mathit{PK}}}$, $\mathfrak{B}$ answers to ${\mathfrak{A}_{I}}$ with ${\mathsf{PK}_{\mathit{ID}}}$.
-
(2) If the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ doesn’t exist in ${L_{\mathit{PK}}}$, $\mathfrak{B}$ randomly picks ${x_{1}},{x_{2}}\in {\mathcal{Z}_{p}^{\ast }}$, calculates ${g^{{x_{1}}}},{g^{{x_{2}}}}$, and sets $s{v_{\mathit{ID}}}=({x_{1}},{x_{2}})$, ${\mathsf{PK}_{\mathit{ID}}}=({g^{{x_{1}}}},{g^{{x_{2}}}})$. After that, $\mathfrak{B}$ answers to ${\mathfrak{A}_{I}}$ with ${\mathsf{PK}_{\mathit{ID}}}$ and inserts the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ into ${L_{\mathit{PK}}}$.
-
-
• Partial-Private-Key-Extract Query: At first, $\mathfrak{B}$ maintains a list ${L_{\mathit{PPK}}}=\{(\mathit{ID},{\mathsf{PPK}_{\mathit{ID}}})\}$ in order to respond to these queries. When an identity $\mathit{ID}$ is supplied to this oracle, $\mathfrak{B}$ inspects the list ${L_{\mathit{PPK}}}$:
-
(1) If the tuple $(\mathit{ID},{\mathsf{PPK}_{\mathit{ID}}})$ exists in ${L_{\mathit{PPK}}}$, $\mathfrak{B}$ answers to ${\mathfrak{A}_{I}}$ with ${\mathsf{PPK}_{\mathit{ID}}}$.
-
(2) If the tuple $(\mathit{ID},{\mathsf{PPK}_{\mathit{ID}}})$ doesn’t exist in ${L_{\mathit{PPK}}}$, and ${F_{1}}(u)\ne 0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}p$, $\mathfrak{B}$ randomly picks ${r_{u}}\in {\mathcal{Z}_{p}^{\ast }}$ and calculates\[ {\mathsf{PPK}_{\mathit{ID}}}=\big({\mathsf{PPK}^{(1)}},{\mathsf{PPK}^{(2)}}\big)=\bigg({\bigg(\frac{{g_{1}}}{{g^{\alpha }}}\bigg)^{-\frac{{J_{1}}(u)}{{F_{1}}(u)}}}{f_{1}^{{r_{u}}}}(\mathcal{U}),{\bigg(\frac{{g_{1}}}{{g^{\alpha }}}\bigg)^{-\frac{1}{{F_{1}}(u)}}}{g^{{r_{u}}}}\bigg).\]After that, $\mathfrak{B}$ answer to ${\mathfrak{A}_{I}}$ with ${\mathsf{PPK}_{\mathit{ID}}}$ and inserts the tuple $(\mathit{ID},{\mathsf{PPK}_{\mathit{ID}}})$ into ${L_{\mathit{PPK}}}$.
-
(3) Otherwise, $\mathfrak{B}$ outputs “failure” and discontinues.
-
-
• Time-Key-Update Query: When a tuple $(\mathit{ID},T)$ is supplied to this oracle, $\mathfrak{B}$ randomly selects ${r_{t}}\in {\mathcal{Z}_{p}^{\ast }}$ and calculates the time key ${\mathsf{TK}_{T}}=({\mathsf{TK}^{(1)}},{\mathsf{TK}^{(2)}})=({g_{2}^{\alpha }}{f_{2}^{{r_{t}}}}(\mathcal{T}),{g^{{r_{t}}}})$.
-
• Secret-Value-Extract Query: When an identity $\mathit{ID}$ is supplied to this oracle, $\mathfrak{B}$ inspects the list ${L_{\mathit{PK}}}$:
-
(1) If the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ exists in ${L_{\mathit{PK}}}$, $\mathfrak{B}$ answers to ${\mathfrak{A}_{I}}$ with $s{v_{\mathit{ID}}}$.
-
(2) If the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ doesn’t exist in ${L_{\mathit{PK}}}$, $\mathfrak{B}$ makes a Public-Key-Extract Query with $\mathit{ID}$ to obtain $({\mathsf{PK}_{\mathit{ID}}},s{v_{\mathit{ID}}})$. After that, $\mathfrak{B}$ updates $({\mathsf{PK}_{\mathit{ID}}},s{v_{\mathit{ID}}})$ into ${L_{\mathit{PK}}}$ and answers to ${\mathfrak{A}_{I}}$ with $s{v_{\mathit{ID}}}$.
-
-
• Public-Key-Replace Query: When an identity $(\mathit{ID},{\mathsf{PK}^{\prime }_{\mathit{ID}}})$ is supplied to this oracle, $\mathfrak{B}$ inspects the list ${L_{\mathit{PK}}}$:
-
(1) If the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ exists in ${L_{\mathit{PK}}}$, $\mathfrak{B}$ sets ${\mathsf{PK}_{\mathit{ID}}}={\mathsf{PK}^{\prime }_{\mathit{ID}}},s{v_{\mathit{ID}}}=s{v^{\prime }_{\mathit{ID}}}$ and then updates $({\mathsf{PK}_{\mathit{ID}}},s{v_{\mathit{ID}}})$ into ${L_{\mathit{PK}}}$.
-
(2) If the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ doesn’t exist in ${L_{\mathit{PK}}}$, $\mathfrak{B}$ first makes a Public-Key-Extract Query with $\mathit{ID}$ to obtain $({\mathsf{PK}_{\mathit{ID}}},s{v_{\mathit{ID}}})$. And then $\mathfrak{B}$ sets ${\mathsf{PK}_{\mathit{ID}}}={\mathsf{PK}^{\prime }_{\mathit{ID}}},s{v_{\mathit{ID}}}=s{v^{\prime }_{\mathit{ID}}}$. After that, $\mathfrak{B}$ updates $({\mathsf{PK}_{\mathit{ID}}},s{v_{\mathit{ID}}})$ into ${L_{\mathit{PK}}}$.
-
-
• RCL-Sign Query: When the tuple $(M,\mathit{ID},T)$ is supplied to this oracle, $\mathfrak{B}$ inspects the list ${L_{\mathit{PK}}}$:
-
(1) If the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ exists in ${L_{\mathit{PK}}}$, $\mathfrak{B}$ retrieves the list ${L_{\mathit{PPK}}}$:
-
(i) If the tuple $(\mathit{ID},{\mathsf{PPK}_{\mathit{ID}}})$ exists in ${L_{\mathit{PPK}}}$, $\mathfrak{B}$ produces a signature $\sigma \gets \text{RCL-Sign}(s{v_{\mathit{ID}}},{\mathsf{PPK}_{\mathit{ID}}},M)$ by running the algorithm RCL-Sign.
-
(ii) If the tuple $(\mathit{ID},{\mathsf{PPK}_{\mathit{ID}}})$ doesn’t exist in ${L_{\mathit{PPK}}}$, and ${F_{1}}(u)\ne 0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{u}}$, $\mathfrak{B}$ makes a Partial-Private-Key-Extract Query to get $(\mathit{ID},{\mathsf{PPK}_{\mathit{ID}}})$, and then produces a signature by running the algorithm RCL-Sign.
-
(iii) If the tuple $(\mathit{ID},{\mathsf{PPK}_{\mathit{ID}}})$ doesn’t exist in ${L_{\mathit{PPK}}}$, and ${F_{1}}(u)=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{u}}$, $\mathfrak{B}$ calculates ${F_{2}}(m)\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{m}}$:
-
① If ${F_{2}}(m)\ne 0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{m}}$, $\mathfrak{B}$ selects $\lambda ,\mu ,\nu \in {\mathcal{Z}_{p}^{\ast }}$ and calculates\[\begin{aligned}{}\sigma =& ({\sigma _{1}},{\sigma _{2}},{\sigma _{3}},{\sigma _{4}})\\ {} =& \bigg({\bigg[{g_{2}^{\alpha }}{f_{1}^{\lambda }}(\mathcal{U}){f_{2}^{\mu }}(\mathcal{T}){\bigg(\frac{{g_{1}}}{{g^{\alpha }}}\bigg)^{-\frac{{J_{3}}(m)}{{F_{2}}(m)}}}{f_{3}^{\nu }}(\mathcal{M}){g_{3}^{{x_{2}}}}\bigg]^{{x_{1}^{-1}}}},\\ {} & {g^{\lambda }},{g^{\mu }},{g_{1}^{-\frac{1}{{F_{2}}(m)}}}{g^{\nu }}\bigg)\\ {} =& \big({\big[{g_{2}^{a+\alpha }}{f_{1}^{\lambda }}(\mathcal{U}){f_{2}^{\mu }}(\mathcal{T}){f_{3}^{{\nu ^{\prime }}}}(\mathcal{M}){g_{3}^{{x_{2}}}}\big]^{{x_{1}^{-1}}}},{g^{\lambda }},{g^{\mu }},{g^{{\nu ^{\prime }}}}\big),\end{aligned}\]where ${\nu ^{\prime }}=\nu -\frac{a}{{F_{2}}(m)}$.
-
② If ${F_{2}}(m)=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{m}}$, $\mathfrak{B}$ outputs “failure” and discontinues.
-
-
(iv) Otherwise, $\mathfrak{B}$ outputs “failure” and discontinues.
-
-
(2) If the tuple $(\mathit{ID},s{v_{\mathit{ID}}},{\mathsf{PK}_{\mathit{ID}}})$ doesn’t exist in ${L_{\mathit{PK}}}$, $\mathfrak{B}$ makes a Public-Key-Extract Query with $\mathit{ID}$ and then repeats step (1).
Forgery: After finishing all queries and $\mathfrak{B}$ doesn’t discontinue, ${\mathfrak{A}_{I}}$ outputs ${u^{\ast }}={\mathcal{H}_{0}}({\mathit{ID}^{\ast }})$, $u{t^{\ast }}={\mathcal{H}_{1}}({\mathit{ID}^{\ast }},{t^{\ast }})$, ${m^{\ast }}={\mathcal{H}_{2}}({M^{\ast }},{\mathit{ID}^{\ast }},{\mathsf{PK}_{{\mathit{ID}^{\ast }}}})$, and generates a forgery ${\sigma ^{\ast }}=({\sigma _{1}^{\ast }},{\sigma _{2}^{\ast }},{\sigma _{3}^{\ast }},{\sigma _{4}^{\ast }})$. Iff ${F_{1}}({u^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}p$ and ${F_{2}}({m^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}p$, $\mathfrak{B}$ calculates
\[\begin{aligned}{}& \frac{{({\sigma _{1}^{\ast }})^{{x_{1}^{\ast }}}}}{{({\sigma _{2}^{\ast }})^{{J_{1}}({u^{\ast }})}}{({\sigma _{3}^{\ast }})^{{J_{2}}(u{t^{\ast }})}}{({\sigma _{4}^{\ast }})^{{J_{3}}({m^{\ast }})}}{g_{2}^{\alpha }}{g_{3}^{{x_{2}^{\ast }}}}}=\frac{{({[{g_{2}^{a+\alpha }}{f_{1}^{\lambda }}(\mathcal{U}){f_{2}^{\mu }}(\mathcal{T}){f_{3}^{{\nu ^{\prime }}}}(\mathcal{M}){g_{3}^{{x_{2}^{\ast }}}}]^{{x_{1}^{\ast -1}}}})^{{x_{1}^{\ast }}}}}{{g^{{J_{1}}({u^{\ast }})\lambda }}{g^{{J_{2}}(u{t^{\ast }})\mu }}{g^{{J_{3}}({m^{\ast }}){\nu ^{\prime }}}}{g_{2}^{\alpha }}{g_{3}^{{x_{2}^{\ast }}}}}\\ {} & \hspace{1em}=\frac{{g_{2}^{a+\alpha }}{({g_{2}^{{F_{1}}({u^{\ast }})}}{g^{{J_{1}}({u^{\ast }})}})^{\lambda }}{({g^{{J_{2}}(u{t^{\ast }})}})^{\mu }}{({g_{2}^{{F_{2}}({m^{\ast }})}}{g^{{J_{3}}({m^{\ast }})}})^{{\nu ^{\prime }}}}{g_{3}^{{x_{2}^{\ast }}}}}{{g^{{J_{1}}({u^{\ast }})\lambda }}{g^{{J_{2}}(u{t^{\ast }})\mu }}{g^{{J_{3}}({m^{\ast }}){\nu ^{\prime }}}}{g_{2}^{\alpha }}{g_{3}^{{x_{2}^{\ast }}}}}\\ {} & \hspace{1em}={g_{2}^{a}}={g^{ab}},\end{aligned}\]
${g^{ab}}$ is the solution of the CDH problem.Now we analyse the probability that $\mathfrak{B}$ can solve the given CDH problem instance. At first, let ${u_{1}},\dots ,{u_{{q_{U}}}}$ be the ${\mathcal{H}_{0}}$’s result that appears in either Partial-Private-Key-Extract Query or in RCL-Sign Query but not including the algorithm’s identity ${\mathit{ID}^{\ast }}$. Let $u{t_{1}},\dots ,u{t_{{q_{T}}}}$ be the ${\mathcal{H}_{1}}$’s result that appears in Time-Key-Update Query. Let ${m_{1}},\dots ,{m_{{q_{M}}}}$ be the ${\mathcal{H}_{2}}$’s result that appears in RCL-Sign Query including all identity $\mathit{ID}$. Obviously, there are ${q_{U}}\leqslant {q_{\mathit{PPK}}}+{q_{S}}$, ${q_{T}}\leqslant {q_{\mathit{TK}}}$ and ${q_{M}}\leqslant {q_{S}}$. Next, we define the following events for simplifying the probability analysis.
-
(1) ${E_{i}}$ ($i=1,\dots ,{q_{U}}$): ${F_{1}}({u_{i}})\ne 0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{u}}$, in other words, $\mathfrak{B}$ does not discontinue in the ${\mathfrak{A}_{I}}$’s Partial-Private-Key-Extract Query.
-
(2) ${E^{\ast }}$: ${F_{1}}({u^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}p$.
-
(3) ${E^{\prime }_{i}}$ ($i=1,\dots ,{q_{M}}$): ${F_{2}}({m_{i}})\ne 0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{m}}$, in other words, $\mathfrak{B}$ does not discontinue in the ${\mathfrak{A}_{I}}$’s RCL-Sign Query.
-
(4) ${E^{\prime \hspace{0.1667em}\ast }}$: ${F_{2}}({m^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}p$.
-
(5) ${E_{S}^{\ast }}$: ${F_{1}}({u^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}p,{F_{2}}({m^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}p$, in other words, ${\mathfrak{A}_{I}}$ produces a valid signature.
The probability that $\mathfrak{B}$ does not discontinue is
\[\begin{aligned}{}\text{Pr[success]}& \geqslant \text{Pr}\Bigg[\Bigg(\hspace{0.1667em}{\underset{i=1}{\overset{{q_{U}}}{\bigwedge }}}{E_{i}}\wedge {E^{\ast }}\Bigg)\wedge \Bigg(\hspace{0.1667em}{\underset{i=1}{\overset{{q_{M}}}{\bigwedge }}}{E^{\prime }_{i}}\wedge {E^{\prime \ast }}\Bigg)\wedge {E_{S}^{\ast }}\Bigg]\\ {} & =\text{Pr}[{E^{\ast }}]\cdot \text{Pr}\Bigg[\hspace{0.1667em}{\underset{i=1}{\overset{{q_{U}}}{\bigwedge }}}{E_{i}}|{E^{\ast }}\Bigg]\cdot \text{Pr}[{E^{\prime \hspace{0.1667em}\ast }}]\cdot \text{Pr}\Bigg[\hspace{0.1667em}{\underset{i=1}{\overset{{q_{M}}}{\bigwedge }}}{E^{\prime }_{i}}|{E^{\prime \ast }}\Bigg]\cdot \text{Pr}[{E_{S}^{\ast }}],\end{aligned}\]
\[\begin{aligned}{}& \because {l_{u}}=2({q_{\mathit{PPK}}}+{q_{S}}),\hspace{2.5pt}{l_{m}}=2{q_{S}},\hspace{2.5pt}{l_{u}}({n_{u}}+1)\leqslant p,\hspace{2.5pt}{l_{m}}({n_{m}}+1)\leqslant p\\ {} & \begin{aligned}{}\therefore \text{Pr}[{E^{\ast }}]& =\text{Pr}[{F_{1}}({u^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}p\wedge {F_{1}}({u^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{u}}]\\ {} & =\text{Pr}[{F_{1}}({u^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{u}}]\cdot \text{Pr}[{F_{1}}({u^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}p|{F_{1}}({u^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{u}}]\\ {} & =\frac{1}{{l_{u}}}\cdot \frac{1}{{n_{u}}+1}\\ {} \text{Pr}[{E^{\prime \ast }}]& =\text{Pr}[{F_{2}}({m^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}p\wedge {F_{2}}({m^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{m}}]\\ {} & =\text{Pr}[{F_{2}}({m^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{m}}]\cdot \text{Pr}[{F_{2}}({m^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}p|{F_{2}}({m^{\ast }})=0\hspace{0.2em}\mathrm{mod} \hspace{0.2em}{l_{m}}]\\ {} & =\frac{1}{{l_{m}}}\cdot \frac{1}{{n_{m}}+1},\end{aligned}\end{aligned}\]
\[\begin{aligned}{}\text{Pr}\Bigg[\hspace{0.1667em}{\underset{i=1}{\overset{{q_{U}}}{\bigwedge }}}{E_{i}}|{E^{\ast }}\Bigg]=& 1-\text{Pr}\Bigg[\hspace{0.1667em}{\underset{i=1}{\overset{{q_{U}}}{\bigvee }}}\lnot {E_{i}}|{E^{\ast }}\Bigg]\geqslant 1-{\sum \limits_{i=1}^{{q_{U}}}}\text{Pr}\big[\lnot {E_{i}}|{E^{\ast }}\big]\\ {} =& 1-\frac{{q_{U}}}{{l_{u}}}\geqslant 1-\frac{{q_{\mathit{PPK}}}+{q_{S}}}{{l_{u}}},\\ {} \text{Pr}\Bigg[\hspace{0.1667em}{\underset{i=1}{\overset{{q_{M}}}{\bigwedge }}}{E^{\prime }_{i}}|{E^{\prime \hspace{0.1667em}\ast }}\Bigg]=& 1-\text{Pr}\Bigg[\hspace{0.1667em}{\underset{i=1}{\overset{{q_{M}}}{\bigvee }}}\lnot {E^{\prime }_{i}}|{E^{\prime \hspace{0.1667em}\ast }}\Bigg]\geqslant 1-{\sum \limits_{i=1}^{{q_{M}}}}\text{Pr}\big[\lnot {E^{\prime }_{i}}|{E^{\prime \hspace{0.1667em}\ast }}\big]\\ {} =& 1-\frac{{q_{M}}}{{l_{m}}}\geqslant 1-\frac{{q_{S}}}{{l_{m}}}\\ {} \Longrightarrow & \text{Pr[success]}\geqslant \frac{\epsilon }{16({q_{\mathit{PPK}}}+{q_{S}})({n_{u}}+1)({n_{m}}+1){q_{S}}}.\end{aligned}\]
Theorem 2.
The proposed scheme is $(t,{q_{\mathit{PPK}}},{q_{\mathit{TK}}},{q_{S}},\epsilon )$-EUF-CMA-secure in Game II defined in Section 2 if the $({t^{\prime }},{\epsilon ^{\prime }})$-CDH assumption holds in $\mathcal{G}$, where
Theorem 3.
The proposed scheme is $(t,{q_{\mathit{PPK}}},{q_{\mathit{TK}}},{q_{S}},\epsilon )$-EUF-CMA-secure in Game III defined in Section 2 if the $({t^{\prime }},{\epsilon ^{\prime }})$-CDH assumption holds in $\mathcal{G}$, where
5 Performance Evaluation
This section investigates the property of the proposed scheme and its performance in terms of computational and communication overhead.
Table 1 demonstrates the properties of different schemes in respect of the security level, revocation mechanism, security model and security assumption for the existing RCLS schemes (Tsai et al., 2014; Xiong and Qin, 2015; Hung et al., 2016; Zheng et al., 2017) and our proposed scheme. Here, the symbol “✓” represents that the scheme satisfies the property and “×” represents that the scheme does not satisfy the property. “ROM” and “SM” denote that the security model is the random oracle model and the standard model, respectively. Obviously, our proposed scheme holds all properties. Especially, our proposed RCLS scheme is provably secure in the standard model and resists the attack mounted by the malicious-but-passive KGC.
Table 1
Property comparisons of different RCLS schemes.
| Scheme | Tsai et al. | Xiong and Qin | Huang et al. | Zheng et al. | Our scheme |
| Security against ${\mathfrak{A}_{I}}$ | ✓ | × | ✓ | ✓ | ✓ |
| Security against ${\mathfrak{A}_{\mathit{II}}}$ | × | ✓ | ✓ | ✓ | ✓ |
| Security against ${\mathfrak{A}_{\mathit{ru}}}$ | ✓ | × | ✓ | × | ✓ |
| Revocable | ✓ | ✓ | ✓ | ✓ | ✓ |
| Security model | SM | ROM | ROM | ROM | SM |
| Security assumption | CDH | CDH | CDH | CDH | CDH |
Table 2
Computation overhead comparisons of different RCLS schemes.
| Scheme | Signature size | Signing cost | Verification cost |
| Tsai et al. | $4|\mathcal{G}|$ | $1SM+(\frac{{n_{m}}}{2}+1)M$ | $7P+(\frac{{n_{u}}+{n_{t}}+{n_{k}}+{n_{s}}+{n_{m}}}{5}+5)M$ |
| Xiong and Qin | $3|\mathcal{G}|$ | $5SM$ | $5P+3H$ |
| Hung et al. | $1|\mathcal{G}|$ | $2SM+2M$ | $4P+3H$ |
| Zheng et al. | $6|\mathcal{G}|$ | $4SM+2M$ | $9P+6H+2SM+3E$ |
| Our scheme | $4|\mathcal{G}|$ | $3SM+(\frac{{n_{m}}}{2}+1)M$ | $5P+(\frac{{n_{u}}+{n_{t}}+{n_{m}}}{3}+3)M$ |
Table 2 shows theoretical evaluation of the signature size, signing and verification cost. In the computational overhead comparison, there are five operations that are considered: pairing, scalar multiplication, multiplication in $\mathcal{G}$, exponentiation in ${\mathcal{G}_{T}}$ and hash operations, which are denoted by $P,\mathit{SM},M,E$ and H respectively. Especially, it is known that the pairing operation and the scalar multiplication on a curve make up the major part of the computational complexity. In the communication overhead comparison, signature size is measured with respect to the number of group elements. From Table 2, it is readily to observe that Hung et al.’ scheme (Hung et al., 2016) has better performance than the schemes in Tsai et al. (2014), Xiong and Qin (2015), Zheng et al. (2017) and our presented scheme in terms of computation and communication overhead. However, the scheme of Hung et al. (2016) was constructed in the random oracle model. Although the scheme of Tsai et al. (2014) was constructed without random oracles same as our scheme, their scheme needs more verification cost and cannot resist the malicious-but-passive attacks. Therefore, our proposed scheme is more secure and efficient in actual life.
6 Conclusion
This paper first analyses a certificateless signature scheme with revocation of Tsai et al. (2014), which was proved to be secure without random oracles. However, this paper demonstrates that their scheme is insecure against the malicious-but-passive attacks. Considering that there does not exist a secure RCLS scheme under the standard model at present, this paper constructs a new and provably secure RCLS scheme without random oracles.
To explain readily the proposed revocable certificateless signature scheme, this paper formalizes the RCLS scheme’s definition and security model. Furthermore, a concrete RCLS construction scheme is given, whose security analysis is proved in the standard model with CDH assumption. Compared to the existing solutions, the RCLS proposed in this paper is more efficient and secure.
