Strongly secure certificateless key-insulated signature secure in the standard model

Abstract

To protect signing rights against the compromise of secret key, the key-insulated signature (KIS) has attracted a lot of attention from the industry and academia. It would be interesting to investigate the notion of KIS in the certificateless public key cryptography (CL-PKC) environment to solve the problem of certificate management and key escrow simultaneously. To capture the seeming neglected attack mounted by the malicious key generation center (KGC), a stronger security model for the CL-PKC should be considered. In this paper, we first show that the only known CL-KIS scheme is vulnerable against malicious KGC attack, and then propose the first CL-KIS scheme secure against malicious KGC attack, with security proof in the standard model.

1 Introduction

The digital signature [9, 13, 23–25], as a counterpart to hand-written signature in the electronic world, has found wide applications in the fields such as electronic commerce, electronic government, and copyright protection by providing authentication, unforgeability, and non-repudiation. However, some issues should be addressed before the digital signature can be employed in practice. To protect the signing rights against the compromise of secret key, key evolving mechanisms including key-insulated [10, 11], intrusion-resilience [15, 31] and forward secure [8, 14] have been introduced independently. In a key-insulated signature (KIS) scheme [11], the whole lifetime of the signing key is divided into different time periods and this key is refreshed at each time period. On the other hand, the public key associated with this signing key remains unchanged during the whole lifetime. More specifically, the full signing key of the signer is updated by incorporating a temporary signing key held by the signer and a helper key from a physically secure device (which is usually named helper). In this case, the KIS scheme can achieve backward and forward security since the adversary who steals the signing key in present time period cannot break the signature scheme in the former or later time periods. To reduce the overhead caused by the certificate management, the key insulated mechanism has been investigated in identity-based public key cryptography (ID-PKC) [22] setting and several concrete identity-based key-insulated signature (ID-KIS) schemes [28, 29, 32] have already been proposed so far.

In ID-PKC, the public key of a user can be easily derived from its publicly known identity (e.g., email address or cell phone number), whereas the private key of this user is generated according to his/her identity by a fully-trusted private key generator (PKG). Unfortunately, the ID-PKC suffers from the key escrow problem in the sense that PKG has any user’s private key and can forge the signature or decrypt the ciphertext on behalf of any user without being detected. To solve the problems of certificate management in traditional public key cryptosystem (PKC) and key escrow in ID-PKC, respectively, a new paradigm called certificateless public key cryptography (CL-PKC) has been introduced, firstly by Al-Riyami and Paterson [1]. The basic idea of CL-PKC is to construct a full private key for a user by combining a partial private key generated by a semi-trusted key generation center (KGC) with a random secret value chosen by the user himself/herself. CL-PKC is not ID-based since the full public key of each user in the CL-PKC consists not only of the public identity, but also of the user public key calculated by the user himself/herself. Different from traditional PKC, the user public key in the CL-PKC does not need to be certified by any trusted third party (TTP) because the structure of CL-PKC guarantees the validity of the public key without a certificate issued by TTP. On the other hand, the inherent key escrow problem in ID-PKC has also been successfully solved in the CL-PKC environment since the KGC cannot access the full private key of the user. It would be interesting to investigate the notion of KIS in the CL-PKC environment. Recently, Wan et al. [26] present a formal definition of certificateless KIS (CL-KIS) by integrating the notions of CL-PKC and KIS altogether. Furthermore, a concrete CL-KIS scheme along with the formal security proof in the standard model [7] has also been given. In parallel to the work in [26], the certificate-based key insulated signature scheme [12, 16] has also been proposed to enjoy the merits of ID-PKC without suffering from the key escrow problem. Unfortunately, we observe that the seeming neglected attack mounted by the malicious-but-passive KGC has not been captured by Wan et al.’s security model. According to [3], the KGC can forge the signature on behalf of every signer by means of generating the system parameters maliciously.

In this paper, we demonstrate that Wan et al.’s CL-KIS scheme is subjected to the malicious-but-passive KGC attack. It is fair to say devising a CL-KIS scheme secure in the standard model remains an open question. We attempt to close this open issue by devising a provably secure CL-KIS scheme in the standard model. It is proven that our CL-KIS scheme satisfies unforgeability against outside adversary and malicious-but-passive KGC assuming the hardness of computational Diffie-Hellman (CDH) problem. The proofs do not rely on random oracles.

The rest of this paper is organized as follows. In Section 2, we describe the formal model of CL-KIS scheme and the mathematical backgrounds. In Section 3, we review and analyze Wan et al.’s CL-KIS scheme. After that, the improved scheme along with the security analysis in the standard model has been given in Sections 4 and 5, respectively. Finally, the conclusions are given in Section 7.

2 Preliminaries

In this section, we will review the mathematical notions and formal models for CL-KIS scheme.

2.1 Notations

The notations used throughout this paper are listed in Table 1.

Table 1 Notations

2.2 Definitions of CL-KIS Schemes

In order to solve the key escrow problem in the ID-PKC, the signing key of the user in the CL-PKC is split into the user private key calculated by the user himself/herself and the partial private key issued by the KGC. In this way, the key escrow problem is avoided due to the fact that the signing key of the user (especially the user secret key) cannot be accessed by the KGC. In the traditional certificateless signature (CLS) scheme, both of the partial private key and the user private key are kept by the user himself/herself. However, to reduce the damage caused by the key leakage, in the certificateless key insulated signature (CL-KIS) scheme, the combination of the partial private key and the user private key consists of two independent parts, i.e., the helper key stored in the helper and temporary signing key kept by the user. Only the signing key in present time period is compromised, the signing rights are not affected in the former or later time periods. The illustration of the helper key and the temporary signing key is shown in Fig. 1.

Fig. 1

The illustration of the helper key and the temporary signing key

According to [26], a CL-KIS scheme consists of a tuple (Setup, UserKeyGen, ExtractPartialKey, User-key-generation, Gen, CL-Update ^∗, CL-Update, CL-Sign, and CL-Ver) described as follows.

• 1. Setup. Given a security parameter $k\in \mathbb {N}$ as input, this algorithm is executed by KGC to generate the public parameters mpk, a master secret key msk, and the total number of time periods N.

• 2. UserKeyGen. Given the public parameters mpk and user identity ID, this algorithm is executed by the user himself/herself to generate a user public/secret key pair (upk _ID , usk _ID ).

• 3. ExtractPartialKey. Given the master secret key msk along with the user identity ID, this algorithm is executed by KGC to generate a user’s partial private key psk, which will be sent to this user securely.

• 4. Gen. By integrating the user secret key and partial secret key, the helper key hk _ID and the initial signing key x _ID,0 are generated by the user himself/herself. We stress that the initial secret key which will be used in the CL-Sign algorithm cannot be accessed by the KGC, and thus the key escrow problem in ID-PKC can be avoided.

• 5. CL-Update ^∗. Given the public parameters mpk, a time period t, an identity ID and the helper key hk _ID , the helper outputs the update key uk _{ID, t} .

• 6. CL-Update. Given a time period t ₁, a update key $uk_{ID,t_{1}}$, and a signing key $x_{ID,t_{2}}$, user associated with identity ID generates the signing key $x_{ID,t_{1}}$ for the time period t ₁.

• 7. CL-Sign. Given a message m∈{0,1}^∗, time period t, an identity ID, user public key upk _ID , and signing key x _{ID, t} , this algorithm is executed by the user himself/herself to generate a signature (s, t).

• 8. CL-Ver. Given the public parameters mpk, user identity ID, user public key upk _ID , message m, and signature (s, t), this algorithm is executed by the verifier to return 1 for accept or 0 for reject.

2.3 Security models

Taking into account of the malicious-but-passive KGC, the security model defined in [26] is reconsidered as follows. Firstly, the malicious outsider who can compromise the user private key or replace the user public key is defined as type I adversary $\mathcal {A}_{1}$. Secondly, the malicious-but-passive KGC who is responsible for the generation of the public system parameter and master public/secret key pair is specified as adversary $\mathcal {A}_{2}$. The restrictions regarding to these security models include that $\mathcal {A}_{1}$ cannot compromise the master secret key nor get access to the user partial key and $\mathcal {A}_{2}$ cannot mount the key replacement attack. The oracles which can be accessed by the adversaries are described as follows.

• 1. Request-Public-Key Oracle: Given a query on identity ID, this oracle returns the matching user public key upk _ID .

• 2. Reveal-Partial-Private-Key Oracle: Given a query on identity ID, this oracle outputs the partial secret key psk _ID associated with this identity.

• 3. Reveal-Secret-Key Oracle: Given a query on identity ID, this oracle outputs a user secret key usk _ID associated with this identity.

• 4. Replace-Public-Key Oracle: Given a identity ID and a new user public key upk _ID , this oracle replaces the associated user’s public key with the new public key $upk_{ID}^{\prime }$.

• 5. Reveal-Signing-Key Oracle: Given a query on identity ID and time period t, this oracle outputs a signing key x _{ID, t} .

• 6. Sign Oracle: Upon receiving an identity ID, the corresponding user public key upk _ID , a time period t, and a message m, challenger $\mathcal {C}$ returns the resulting signature to the adversary.

In order to capture the attacks launched by $\mathcal {A}_{1}$ and $\mathcal {A}_{2}$, two games (Game I and Game II) are defined respectively.

Game I: Let $\mathcal {C}$ be the game simulator/challenger with the input of security parameter $k\in \mathbb {N}$.

• 1. Initial. $\mathcal {C}$ first executes Setup to generate the master public/secret key pair and public parameters, and then publishes the public parameters mpk and keeps the master secret key secret.

• 2. Attack. In this phase, $\mathcal {A}_{1}$ adaptively issues a polynomial bounded number of Request-Public-Key, Reveal-Partial-Private-Key, Reveal-Secret-Key, Replace-Public-Key, Reveal-Signing-Key, and Sign queries.

• 3. Forgery. $\mathcal {A}_{1}$ is to output (ID ^∗, $upk_{ID^{\ast }}$, m ^∗, (s ^∗, t ^∗)). $\mathcal {A}_{1}$ wins if CL-Ver $(mpk, (ID^{\ast }, upk_{ID^{\ast }}, m^{\ast }, (s^{\ast }, t^{\ast })))=1$ for some created ID ^∗, and the Sign has never been queried with $(ID^{\ast }, upk_{ID^{\ast }}, m^{\ast }, t^{\ast })$. One additional restriction is that $\mathcal {A}_{1}$ has never queried Reveal-Partial-Private-Key oracle to get the partial private key of the target user.

Definition 1

A CL-KIS scheme is said to be Type-I secure if there is no probabilistic polynomial-time adversary $\mathcal {A}_{1}$ who wins Game I with non-negligible advantage.

Game II: Let $\mathcal {C}$ be the game challenger with the input of security parameter $k\in \mathbb {N}$.

• 1. Initial. $\mathcal {A}_{2}$ executes Setup to generate the master public/secret key pair and public system parameters, and sends the public system parameters params and the master public/secret key pair to challenger $\mathcal {C}$. We should keep in mind that $\mathcal {A}_{2}$ generates params and msk by itself.

• 2. Attack. In this phase, $\mathcal {A}_{2}$ adaptively issues a polynomial bounded number of Request-Public-Key, Reveal-Secret-Key, Reveal-Signing-Key, and Sign queries.

• 3. Forgery. Finally, $\mathcal {A}_{2}$ is to output (ID ^∗, $upk_{ID^{\ast }}$, m ^∗, (s ^∗, t ^∗)). $\mathcal {A}_{2}$ wins if CL-Ver $(mpk, (ID^{\ast },upk_{ID^{\ast }}, m^{\ast }, (s^{\ast }, t^{\ast })))=1$ for some created ID ^∗ and the Sign has never been queried with $(ID^{\ast }, upk_{ID^{\ast }}, m^{\ast }, t^{\ast })$. One additional restriction is that $\mathcal {A}_{2}$ has never queried Replace-Public-Key to replace the public key of the target user.

Definition 2

A CL-KIS scheme is said to be Type-II secure if there is no probabilistic polynomial-time adversary $\mathcal {A}_{2}$ who wins Game II with non-negligible advantage.

A CL-KIS scheme is said to be existentially unforgeable under adaptive chosen message attacks, if there exists neither polynomial time Type I adversary nor polynomial time Type II adversary who has a non-negligible success probability in Game I and Game II, respectively.

2.4 Bilinear pairing

Let $\mathbb {G}_{1}, \mathbb {G}_{2}$ denote two multiplicative cyclic groups of prime order p. Let $\hat {e}$ be a bilinear map such that $\hat {e}:\mathbb {G}_{1}\times \mathbb {G}_{1}\rightarrow \mathbb {G}_{2}$ with the following properties:

• 1. Bilinearity: For all $g_{1}, g_{2}\in \mathbb {G}_{1}$, and $a,b\in \mathbb {Z}_{p}$, $\hat {e}({g_{1}^{a}}, {g_{2}^{b}})=\hat {e}(g_{1}, g_{2})^{ab}$.

• 2. Non-degeneracy: $\hat {e}(g_{1}, g_{2})\neq 1_{\mathbb {G}_{2}}$.

• 3. Computability: It is efficient to compute $\hat {e}(g_{1}, g_{2})$ for all $g_{1}, g_{2}\in \mathbb {G}_{1}$.

The modified Weil pairing and the Tate pairing are admissible maps of this kind. We refer for more details to [6].

Definition 3

Given the elements g, g ^a, and g ^b, for some random values $a,b\in \mathbb {Z}_{p}$ the Computational Diffie-Hellman (CDH) problem consists of computing the element g ^ab. More details of CDH problem can be found in [5, 9].

3 Analysis of Wan et al.’s scheme

3.1 Overview of Wan et al.’s scheme

Now, we review Wan et al.’s [26] CL-KIS scheme which incorporates the idea of Waters’s signature scheme [27], Paterson and Schuldt [21]’s identity-based signature scheme, and Liu et al.’s certificateless signature scheme [17].

Let H:{0,1}^∗→{0,1}ⁿ be a collision-resistant cryptographic hash function. Select a pairing $\hat {e}:\mathbb {G}_{1}\times \mathbb {G}_{1}\rightarrow \mathbb {G}_{2}$ where $\mathbb {G}_{1}, \mathbb {G}_{2}$ denote two multiplicative cyclic groups of prime order p. Assume N be the total number of time periods.

• 1. Setup.

  • (a) Randomly select $\alpha \leftarrow _{R}\mathbb {Z}_{p}$ and $g_{2}\leftarrow _{R}\mathbb {G}_{1}$. Compute g ₁ = g ^α, where g is a generator of $\mathbb {G}_{1}$. Furthermore, choose a vector $\mathbf {V}=(v_{i})\leftarrow _{R}\mathbb {G}_{1}^{n+1}$.

  • (b) Define a function f by $f(\mathcal {W})=v_{0}{\prod }_{i\in \mathcal {W}}v_{i}$, where $\mathcal {W}\subset \{1,\ldots ,n\}$.

  • (c) The public parameters are $mpk=\{\mathbb {G}_{1},\mathbb {G}_{2},\hat {e},g,g_{1},g_{2},f,\mathbf {V},H,N\}$ and master secret is $msk=g_{2}^{\alpha }$.

• 2. UserKeyGen. User selects a secret value $x\leftarrow _{R}\mathbb {Z}_{p}$ as his secret key usk _ID and computes his public key as $upk_{ID}=(upk_{ID}^{(1)}$, $upk_{ID}^{(2)})=(g^{x}, {g_{1}^{x}})$.

• 3. ExtractPartialKey. Compute V _ID = H(ID) and define $\mathcal {V}_{ID}\subset \{1,\ldots ,n\}$ to be the set of indices i such that V _ID [i]=1. To construct the partial secret key of identity ID, the KGC randomly picks $d_{u}\leftarrow _{R}\mathbb {Z}_{p}$ and computes:

  $$psk_{ID}=(psk_{ID}^{(1)},psk_{ID}^{(2)})=(g_{2}^{\alpha}(f(\mathcal{V}_{ID}))^{d_{u}},g^{d_{u}}). $$

• 4. Gen. The user performs the following steps:

  • (a) Pick $d_{v}\leftarrow _{R}\mathbb {Z}_{p}$ and compute $a_{ID}=(psk_{ID}^{(2)})^{x}g^{d_{v}}$ and $hk_{ID}=(psk_{ID}^{(1)})^{x}f(\mathcal {V}_{ID})^{d_{v}}$.

  • (b) Pick $b_{ID,0}, c_{ID,0}\leftarrow _{R}\mathbb {G}_{1}$ and define the initial signing key as x _ID,0 = (a _ID , b _ID,0, c _ID,0).

  • (c) Output the helper key hk _ID and the initial signing key x _ID,0.

• 5. CL-Update ^∗. Given a time period t and an identity ID, the helper performs the following steps:

  • (a) Pick $d_{t}\leftarrow _{R}\mathbb {Z}_{p}$ and assign $\hat {c}_{ID,t}=g^{d_{t}}$.

  • (b) Compute V _{ID, t} = H(ID, t).

  • (c) Define $\mathcal {V}_{ID,t}\subset \{1,\ldots ,n\}$ to be the set of indices i such that V _{ID, t} [i]=1.

  • (d) Compute $\hat {b}_{ID,t}=hk_{ID}\cdot f(\mathcal {V}_{ID,t})^{d_{t}}$.

  • (e) Output the update key $uk_{ID,t}=(\hat {b}_{ID,t},~\hat {c}_{ID,t})$.

• 6. CL-Update. Given a time period t ₁, a update key $uk_{ID,t_{1}}$, and a signing key $x_{ID,t_{2}}$, user associated with identity ID generates the signing key in the time period t ₁ as follows:

  • (a) Parse $x_{ID,t_{2}}=(a_{ID}, b_{ID,t_{2}}, c_{ID,t_{2}})$ and $uk_{ID,t_{1}}=(\hat {b}_{ID,t_{1}}, \hat {c}_{ID,t_{1}})$.

  • (b) Set $b_{ID,t_{1}},=\hat {b}_{ID,t_{1}}, c_{ID,t_{1}}=\hat {c}_{ID,t_{1}}$.

  • (c) Output the signing key $x_{ID,t_{1}}=(a_{ID}, b_{ID,t_{1}}, c_{ID,t_{1}})$

• 7. CL-Sign. To sign a message m∈{0,1}^∗ in time period t, the signer with identity ID and signing key x _{ID, t} generates the signature as follows:

  • (a) Parse x _{ID, t} = (a _ID , b _{ID, t} , c _{ID, t} ).

  • (b) Compute M = H(m). Let M[i] be the i-th bit of M and let $\mathcal {M}\subset \{1,\ldots ,n\}$ be the set of indices i such that M[i]=1.

  • (c) Pick $d_{m}\leftarrow _{R}\mathbb {Z}_{p}$ and compute $D=g^{d_{m}}$ and $B=b_{ID, t}\cdot f(\mathcal {M})^{d_{m}}$.

  • (d) Output the signature (s, t)=((D, B, a _ID , c _{ID, t} ), t) on the message m in time period t.

• 8. CL-Ver. Given a signature (s, t) for an identity ID and public key $(upk_{ID}^{(1)}, upk_{ID}^{(2)})$ on a message m, a verifier executes the following steps to check the validity of the signature.

  • (a) Parse (D, B, a _ID , c _{ID, t} ).

  • (b) Compute M = H(m). Let M[i] be the i-th bit of M and let $\mathcal {M}\subset \{1,\ldots ,n\}$ be the set of indices i such that M[i]=1.

  • (c) Let $\mathcal {V}_{ID}, \mathcal {V}_{ID,t}$ be the sets described in the ExtractPartialKey and CL-Update algorithms respectively.

  • (d) Check whether $\hat {e}(upk_{ID}^{(1)},g_{1})=\hat {e}(upk_{ID}^{(2)},g)$ and

    $$\hat{e}(B,g)\,=\,\hat{e}(g_{2}, upk_{ID}^{(2)})\hat{e}(f(\mathcal{V}_{ID}), a_{ID})\hat{e}(f(\mathcal{V}_{ID,t}), c_{ID,t})\hat{e}(f(\mathcal{M}), D) $$

  Output valid if both equalities hold. Otherwise output invalid. The signature is valid if all the steps pass. Otherwise it is invalid.

3.2 Analysis

According to [26], their scheme is semantically secure against Type I and Type II adversary in the standard model. However, the attack mounted by the malicious KGC has been neglected in [26]. In fact, we demonstrate that their scheme is not unforgeable against the malicious-but-passive KGC (Type II adversary $\mathcal {A}_{2}$) attack in this subsection. Intuitively, the insecurity of Wan et al.’s scheme lies in the fact that, given a signature, a malicious-but-passive KGC (Type II adversary $\mathcal {A}_{2}$) can derive the user’s signing key, and hence can certainly forge signature on behalf of this user. The attack is described in detail as follows.

• 1. In the initial phase, adversary $\mathcal {A}_{2}$ generates the master public key mpk and master secret key for challenger $\mathcal {C}$. In particular, adversary $\mathcal {A}_{2}$ computes $v_{0}\leftarrow _{R}\mathbb {G}_{1}$ and $v_{i}\leftarrow _{R}\mathbb {G}_{1}$ for i = 1,…, n as follows:

  • Choose random values β ₀, β ₁,⋯ , β _n in $\mathbb {Z}_{p}$.

  • Compute $v_{0}=g^{\beta _{0}}$ and $v_{i}=g^{\beta _{i}}$ for i = 1,…, n.

• 2. In the attack phase, $\mathcal {A}_{2}$ issues a signature query by submitting an identity ID ^∗, a time period t ^∗, public key $(upk_{ID^{\ast }}^{(1)}, upk_{ID^{\ast }}^{(2)})$, and a message m ^∗. Then adversary $\mathcal {A}_{2}$ is given a signature $(s^{\ast }, t^{\ast })=((D^{\ast }, B^{\ast }, a_{ID^{\ast }}, c_{ID^{\ast },t^{\ast }}),t^{\ast })$ under the identity ID ^∗ and public key $d(upk_{ID^{\ast }}^{(1)}, upk_{ID^{\ast }}^{(2)})$ on the message m ^∗ in time period t ^∗ such that

  $$\begin{array}{@{}rcl@{}} \hat{e}\left(upk_{ID^{\ast}}^{(1)},g_{1}\right)\!\!&=&\!\!\hat{e}\left(upk_{ID^{\ast}}^{(2)},g\right)\\ \hat{e}(B^{\ast},g)\!\!&=&\!\!\hat{e}\left(g_{2}, upk_{ID^{\ast}}^{(2)}\right)\hat{e}(f(\mathcal{V}_{ID^{\ast}}), a_{ID^{\ast}})\\ \!\!&&\!\!\times\hat{e}(f(\mathcal{V}_{ID^{\ast},t^{\ast}}),\! c_{ID^{\ast},t^{\ast}})\hat{e}\!\left(f(n{\ast}), D^{\ast}\!\right) \end{array} $$

  where $V_{ID^{\ast }}=H(ID^{\ast })$ and $\mathcal {V}_{ID^{\ast }}\subset \{1,\ldots ,n\}$ denote the set of indices i such that $V_{ID^{\ast }}[i]=1$, $V_{ID^{\ast },t^{\ast }}=H(ID^{\ast },t^{\ast })$ and $\mathcal {V}_{ID^{\ast },t^{\ast }}\subset \{1,\ldots ,n\}$ denote the set of indices i such that $V_{ID^{\ast },t^{\ast }}[i]=1$, M ^∗=H(m ^∗) and $\mathcal {M}^{\ast }\subset \{1,\ldots ,n\}$ denote the set of indices i such that M ^∗[i]=1.

  From $D^{\ast }=g^{d_{m}^{\ast }}$ and $B^{\ast }=b_{ID^{\ast }, t^{\ast }}\cdot f\left (\left .\mathcal {M}^{\ast }\right )\right )^{d_{m}^{\ast }}$, adversary $\mathcal {A}_{2}$ can derive the user’s signing key $b_{ID^{\ast },t^{\ast }}$ by computing $\frac {B^{\ast }}{(D^{\ast })^{\beta ^{\prime }+{\sum }_{j\in \mathcal {M}}\beta _{j}}}$, since

  $$\begin{array}{@{}rcl@{}} \frac{B^{\ast}}{(D^{\ast})^{\beta_{0}+{\sum}_{j\in \mathcal{M}^{\ast}}\beta_{j}}}&=&\frac{b_{ID^{\ast}, t^{\ast}}\cdot f(\mathcal{M}^{\ast})^{d_{m}^{\ast}}}{(g^{d_{m}^{\ast}})^{\beta^{\prime}+{\sum}_{j\in \mathcal{M}^{\ast}}\beta_{j}}}\\ &=&\frac{b_{ID^{\ast}, t^{\ast}}\cdot f(\mathcal{M}^{\ast})^{d_{m}^{\ast}}}{(g^{\beta^{\prime}+{\sum}_{j\in \mathcal{M}^{\ast}}\beta_{j}})^{d_{m}^{\ast}}}\\ &=&\frac{b_{ID^{\ast}, t^{\ast}}\cdot f(\mathcal{M}^{\ast})^{d_{m}^{\ast}}}{(g^{\beta^{\prime}}{\prod}_{j\in \mathcal{M}^{\ast}}g^{\beta_{j}})^{d_{m}^{\ast}}}\\ &=&\frac{b_{ID^{\ast}, t^{\ast}}\cdot f(\mathcal{M}^{\ast})^{d_{m}^{\ast}}}{f(\mathcal{M}^{\ast})^{d_{m}^{\ast}}}\\ &=&b_{ID^{\ast}, t^{\ast}} \end{array} $$

  Recall that $(a_{ID^{\ast }}, c_{ID^{\ast },t^{\ast }})$ can be extracted from the signature (s ^∗, t ^∗) directly. Thus, adversary $\mathcal {A}_{2}$ can obtain the user’s signing key $x_{ID^{\ast },t^{\ast }}=(a_{ID^{\ast }}, b_{ID^{\ast },t^{\ast }}, c_{ID^{\ast },t^{\ast }})$. Equipped with this signing key, $\mathcal {A}_{2}$ can definitely forge valid signature on behalf of this user within the time period t ^∗.

Our result shows that Wan et al.’s scheme cannot provide existential unforgeability against the malicious-but-passive KGC.

4 An improved scheme

In this section, we provide an improvement of the CL-KIS scheme proposed in [26] which can resist the attacks mounted by the outsider adversary (type I adversary) and malicious-but-passive KGC (type II adversaries) simultaneously. In fact, the user public key has not been incorporated in the part of signature associated with the message to be signed. In this section, we show how to fix this problem.

Without losing of generality, we only describe the CL-Sign and CL-Ver algorithms since the other algorithms are identical to the one defined in [26].

• 1. CL-Sign. To sign a message m∈{0,1}^∗ in time period t, the signer with identity ID and signing key x _{ID, t} generates the signature as follows:

  • (a) Parse x _{ID, t} = (a _ID , b _{ID, t} , c _{ID, t} ).

  • (b) Compute M = H(m). Let M[i] be the i-th bit of M and let $\mathcal {M}\subset \{1,\ldots ,n\}$ be the set of indices i such that M[i]=1.

  • (c) Pick $d_{m}\leftarrow _{R}\mathbb {Z}_{p}$ and compute $D=g^{d_{m}}$ and $B=b_{ID, t}\cdot f(\mathcal {M})^{d_{m}}\cdot (upk_{ID}^{(1)})^{H_{1}(m)d_{m}}$, where $H_{1}:\{0,1\}^{\ast }\rightarrow \mathbb {Z}_{p}$ is a collision-resistant cryptographic hash function defined in the public parameters mpk.

  • (d) Output the signature (s, t) = ((D, B, a _ID , c _{ID, t} ), t ) on the message m in time period t.

• 2. CL-Ver. Given a signature (s, t) for an identity ID and public key $(upk_{ID}^{(1)}, upk_{ID}^{(2)})$ on a message m, a verifier executes the following steps to check the validity of the signature.

  • (a) Parse (D, B, a _ID , c _{ID, t} ).

  • (b) Compute M = H(m). Let M[i] be the i-th bit of M and let $\mathcal {M}\subset \{1,\ldots ,n\}$ be the set of indices i such that M[i]=1.

  • (c) Let $\mathcal {V}_{ID}, \mathcal {V}_{ID,t}$ be the sets described in the ExtractPartialKey and CL-Update algorithms respectively.

  • (d) Check whether $\hat {e}(upk_{ID}^{(1)},g_{1})=\hat {e}(upk_{ID}^{(2)},g)$ and

    $$\begin{array}{@{}rcl@{}} \hat{e}(B,g)\!&=&\!\hat{e}\left(\!g_{2}, upk_{ID}^{(2)}\right)\hat{e}(f(\mathcal{V}_{ID}), a_{ID})\\ &&\times\hat{e}(f(\mathcal{V}_{ID,t}), c_{ID,t})\hat{e}\left(\!f(\mathcal{M})(upk_{ID}^{(1)}\right)^{H_{1}(m)},\! D) \end{array} $$

  Output valid if both equalities hold. Otherwise output invalid. The signature is valid if all the steps pass. Otherwise it is invalid.

Remark 1

To resist the above malicious-but-passive KGC attack, the signature part $B=b_{ID, t}\cdot f(\mathcal {M})^{d_{m}}$ in the original Wan et al.’s scheme has been replaced with $B=b_{ID, t}\cdot f(\mathcal {M})^{d_{m}}\cdot (upk_{ID}^{(1)})^{H_{1}(m)d_{m}}$. In this way, the user public key $upk_{ID}^{(1)}$ has been embedded into the signature such that the malicious Type-II adversary $\mathcal {A}_{2}$ cannot extract b _{ID, t} from B and D without the knowledge of the corresponding user secret key usk _ID .

5 Analysis of the improved scheme

We prove that our CL-KIS scheme is existentially unforgeable against Type I and II adversary, in the standard model, given that the CDH problem is hard.

Theorem 1

(Type I Existential Unforgeability). Our CL-KIS scheme is 𝜖-existential unforgeable against Type I adversary with advantage at most 𝜖, assuming that the 𝜖 ^′ -CDH assumption holds in $\mathbb {G}_{1}$ , where $\epsilon ^{\prime }\geq ~\frac {\epsilon }{64(q_{e}+q_{se}+q_{s})(q_{se}+q_{s})q_{s}(n+1)^{3}}$ where q _e is the number of queries made to the oracle Reveal-Partial-Private-Key, q _se is the number of queries made to the Reveal-Signing-Key oracle, q _s is the number of queries made to the Sign oracle, q _k is the number of queries made to the oracles Reveal-Secret-Key and Request-Public-Key altogether.

Proof

We assume that an 𝜖-Type I adversary $\mathcal {A}_{1}$ for our scheme exists. Resorting to this forger, an algorithm $\mathcal {C}$ can be constructed to solve CDH problem with probability at least 𝜖 ^′.

The aim of algorithm $\mathcal {C}$ is to output g ^ab by given a group $\mathbb {G}_{1}$ of prime order p with generator g and elements $g^{a},g^{b}\in \mathbb {G}_{1}$ where a, b are selected uniformly at random from $\mathbb {Z}_{p}^{\ast }$. $\mathcal {C}$ makes use of $\mathcal {A}_{1}$ by simulating a challenger for $\mathcal {A}_{1}$. Such a simulation can be depicted as follows:

• Initial. $\mathcal {C}$ sets l = 2(q _e +q _s +q _se ) and randomly chooses a integer k with 0≤k≤n. We assume that l(n+1)<p for the given values of q _e , q _s , q _k , and n. The simulator then chooses an integer $x_{0}\leftarrow _{R}\mathbb {Z}_{l}$ and a vector (x _i ) of length n, with $x_{i}\leftarrow _{R}\mathbb {Z}_{l}$ for all i. Lastly, $\mathcal {C}$ chooses a integer $y_{0}\leftarrow _{R}\mathbb {Z}_{p}$ and a vector (y _i ) of length n with $y_{i}\leftarrow _{R}\mathbb {Z}_{p}$ for all i. A pair of functions are defined as follows:

  $$F(\mathcal{W})=x_{0}+\sum\limits_{i\in \mathcal{W}}x_{i}-l\cdot k ~~J(\mathcal{W})=y_{0}+\sum\limits_{i\in \mathcal{W}}y_{i} $$

  $\mathcal {C}$ assigns g ₁ = g ^a, g ₂ = g ^b, $u_{0}=g_{2}^{-l\cdot k+x_{0}}g^{y_{0}}$, $u_{i}=g_{2}^{x_{i}}g^{y_{i}}~(1\leq i\leq n)$, and the public parameters mpk = (g ₁, g ₂, u ₀,(u _i )) are sent to $\mathcal {A}_{1}$. Moreover, this assignment of parameter means that the master secret is $g_{2}^{\alpha }={g_{2}^{a}}=g^{ab}$ and we have the following equations:

  $$f(\mathcal{W})=u_{0}\prod\limits_{i\in\mathcal{W}}u_{i}=g_{2}^{F(\mathcal{W})}g^{J(\mathcal{W})} $$

• Attack. $\mathcal {C}$ maintains a list $\mathcal {L}$ which is initially empty and consists of entry (ID, psk _ID , upk _ID , usk _ID ). $\mathcal {C}$ simulates all oracles as follows:

• Request-Public-Key Oracle: Given an identity ID, $\mathcal {C}$ looks up its list $\mathcal {L}$ to find out the corresponding entry. If it does not exist, $\mathcal {C}$ runs UserKeyGen and ExtractPartialKey algorithms to generate the secret/public key pair and partial private key respectively. It then stores (ID, psk _ID , upk _ID , usk _ID ) into the list $\mathcal {L}$. In both cases, upk _ID is returned.

  Reveal-Partial-Private-Key Oracle: Consider a query for the partial private key of an identity ID ($\mathcal {C}$ computes V _ID = H(ID) and sets $\mathcal {V}_{ID}\subset \{1,\ldots , n\}$ to be the set of indices i such that V _ID [i]=1). $\mathcal {C}$ does not know the master secret, but assuming $F(\mathcal {V}_{ID})\neq 0 \bmod p$, it can construct a partial private key by choosing $r_{u}\leftarrow _{R}\mathbb {Z}_{p}$ and computing $\left (psk^{(1)}_{ID}, psk^{(2)}_{ID}\right )=\left (g_{1}^{-\frac {J(\mathcal {V}_{ID})}{F(\mathcal {V}_{ID})}}\left (u_{0}{\prod }_{i\in \mathcal {V}_{ID}}u_{i}\right )^{r_{u}},g_{1}^{-\frac {1}{F(\mathcal {V}_{ID})}}g^{r_{u}}\right )$. It can be verified that defining $(psk^{(1)}_{ID}, psk^{(2)}_{ID})$ in this manner yields a valid user partial key of ID assuming $\tilde {r}_{u}=r_{u}-a/F(\mathcal {V}_{ID})$, since that

  $$\begin{array}{@{}rcl@{}} psk^{(1)}_{ID} &=& g_{1}^{-\frac{J(\mathcal{V}_{ID})}{F(\mathcal{V}_{ID})}}\left(u_{0}\prod\limits_{i\in \mathcal{V}_{ID}}u_{i}\right)^{r_{u}}\\ &=&\!{g_{2}^{a}}\left(g_{2}^{F(\mathcal{V}_{ID})}g^{J(\mathcal{V}_{ID})}\right)^{-a/F(\mathcal{V}_{ID})}\!\left(\!g_{2}^{F(\mathcal{V}_{ID})}g^{J(\mathcal{V}_{ID})}\!\right)^{r_{u}}\\ &=&{g_{2}^{a}}(g_{2}^{F(\mathcal{V}_{ID})}g^{J(\mathcal{V}_{ID})})^{r_{u}-a/F(\mathcal{V}_{ID})}\\ &=& {g_{2}^{a}}\left(u_{0}\prod\limits_{i\in \mathcal{V}_{ID}}u_{i}\right)^{\tilde{r}_{u}} \end{array} $$

  and $psk^{(2)}_{ID}=g_{1}^{-\frac {1}{F(\mathcal {V}_{ID})}}g^{r_{u}}=g^{r_{u}-a/F(\mathcal {V}_{ID})}=g^{\tilde {r}_{u}}$. In this way, all the partial private keys computed by $\mathcal {C}$ are indistinguishable from the real one. However, the above simulation aborts if $F(\mathcal {V}_{ID})=0\bmod p$. Given the assumption l(n+1)<p which implies 0≤l⋅k<p and $0\leq x_{0}+{\sum }_{i\in \mathcal {V}_{ID}}x_{i}<p$, it is easy to find that $F(\mathcal {V}_{ID})=0\bmod p$ implies that $F(\mathcal {V}_{ID})=0\bmod l$. Therefore, $F(\mathcal {V}_{ID})\neq 0\bmod l$ implies $F(\mathcal {V}_{ID})\neq 0\bmod p$.

  Reveal-Secret-Key Oracle: Upon receiving a query for a public key of an identity ID, $\mathcal {C}$ looks up $\mathcal {L}$ to find out the corresponding entry. If it does not exist, $\mathcal {C}$ runs UserKeyGen to generate a secret and public key pair. It stores the key pair in $\mathcal {L}$ and returns the secret key usk _ID .

  Replace-Public-Key Oracle: Upon receiving a query for a public key replace oracle request of an identity ID, $\mathcal {C}$ looks up $\mathcal {L}$ to replace the corresponding entry. If it does not exist, $\mathcal {C}$ creates a new entry for this identity.

  Reveal-Signing-Key Oracle: Consider a query for a signing key of identity ID and period t, $\mathcal {C}$ first computes V _ID = H(ID) and V _{ID, t} = H(ID, t), and then sets $\mathcal {V}_{ID}\subset \{1,\ldots ,n\}$ to be the set of indices i such that V _ID [i]=1 and $\mathcal {V}_{ID,t}\subset \{1,\ldots ,n\}$ to be the set of indices i such that V _{ID, t} [i]=1 respectively. $\mathcal {C}$ looks up $\mathcal {L}$ to check whether the user public key of ID has been replaced or not. If this user public key has already been replaced with the new user public key $upk_{ID}=(upk_{ID}^{(1)}, upk_{ID}^{(2)})$, $\mathcal {C}$ computes the signing key in case $F(\mathcal {V}_{ID,t})\neq 0\bmod q$ and $F(\mathcal {V}_{ID,t})\neq 0\bmod l$ as follows:

  $\mathcal {C}$ picks d _u , $d_{t}\!\leftarrow _{R}\!\mathbb {Z}_{p}$ and computes $a_{ID}\,=\,g^{d_{u}}$, $b_{ID,t}=(upk_{ID}^{(2)})^{-J(\mathcal {V}_{ID,t})/F(\mathcal {V}_{ID,t})} f(\mathcal {V}_{ID})^{d_{u}}f(\mathcal {V}_{ID,t})^{d_{t}}$, $c_{ID,t}=\left (upk_{ID}^{(2)}\right )^{-1/F(\mathcal {V}_{ID,t})} g^{d_{t}}$. After that, $\mathcal {C}$ returns (a _ID , b _{ID, t} , c _{ID, t} ) as the signing key.

  The correctness can be shown as below:

  $$\begin{array}{@{}rcl@{}} b_{ID,t} &=&\left(upk_{ID}^{(2)}\right)^{-J(\mathcal{V}_{ID,t})/F(\mathcal{V}_{ID,t})}f(\mathcal{V}_{ID})^{d_{u}}f(\mathcal{V}_{ID,t})^{d_{t}} \\ &=&g_{1}^{-\frac{J(\mathcal{V}_{ID,t})}{F(\mathcal{V}_{ID,t})}x}\left(g_{2}^{F(\mathcal{V}_{ID,t})}g^{J(\mathcal{V}_{ID,t})}\right)^{d_{t}}f(\mathcal{V}_{ID})^{d_{u}}\\ &=&g^{-\frac{axJ(\mathcal{V}_{ID,t})}{F(\mathcal{V}_{ID,t})}}\left(g_{2}^{F(\mathcal{V}_{ID,t})}g^{J(\mathcal{V}_{ID,t})}\right)^{\frac{ax}{F(\mathcal{V}_{ID,t})}}\left(g_{2}^{F(\mathcal{V}_{ID,t})}g^{J(\mathcal{V}_{ID,t})}\right)^{-\frac{ax}{F(\mathcal{V}_{ID,t})}}\left(g_{2}^{F(\mathcal{V}_{ID,t})}g^{J(\mathcal{V}_{ID,t})}\right)^{d_{t}}f(\mathcal{V}_{ID})^{d_{u}} \\ &=&g^{-\frac{axJ(\mathcal{V}_{ID,t})}{F(\mathcal{V}_{ID,t})}}g^{abx}g^{\frac{axJ(\mathcal{V}_{ID,t})}{F(\mathcal{V}_{ID,t})}}\left(g_{2}^{F(\mathcal{V}_{ID,t})}g^{J(\mathcal{V}_{ID,t})}\right)^{\tilde{d}_{t}}f(\mathcal{V}_{ID})^{d_{u}}\\ &=&g_{2}^{ax}f(\mathcal{V}_{ID,t})^{\tilde{d}_{t}}f(\mathcal{V}_{ID})^{d_{u}}\\ c_{ID,t} &=& \left(upk_{ID}^{(2)}\right)^{-1/F(\mathcal{V}_{ID,t})}g^{d_{t}}\\ &=& g^{\tilde{d}_{t}} \end{array} $$

  Here, $\tilde {d}_{t}=d_{t}-\frac {a}{F(\mathcal {V}_{ID,t})}x$.

  If the user public key has not been replaced yet and assuming $F(\mathcal {V}_{ID})\,=\, 0\bmod l$ and $F(\mathcal {V}_{ID,t})\neq 0\bmod l$, $\mathcal {C}$ picks $d_{u}, d_{t}\leftarrow _{R}\mathbb {Z}_{p}$ and extracts the user secret key usk _ID from the list $\mathcal {L}$. After that, $\mathcal {C}$ computes $a_{ID}=g^{d_{u}}$, $b_{ID,t}=g^{-usk_{ID} J(\mathcal {V}_{ID,t})/F(\mathcal {V}_{ID,t})}f(\mathcal {V}_{ID})^{d_{u}}f(\mathcal {V}_{ID,t})^{d_{t}\cdot usk_{ID}}$, $c_{ID,t}=g^{-usk_{ID}/F(\mathcal {V}_{ID,t})}g^{usk_{ID}\cdot d_{t}}$. After that, $\mathcal {C}$ returns (a _ID , b _{ID, t} , c _{ID, t} ) as the signing key.

  Otherwise, if the user public key has not been replaced yet and assuming $F(\mathcal {V}_{ID})\neq 0\bmod l$, $\mathcal {C}$ generates the signing key by performing CL-Update algorithm.

• Sign Oracle: Consider a query for a signature of ID on m in time period t, $\mathcal {C}$ executes Oracle to get the signing key and generates the signature by performing CL-Sign algorithm.

Forgery. If $\mathcal {C}$ does not abort as a consequence of one of the queries above, $\mathcal {A}_{1}$, with probability at least 𝜖, returns an identity ID ^∗, a user public key $upk_{ID^{\ast }}$, a message m ^∗, and valid forgery $(s^{\ast }, t^{\ast })= \left (\left (D^{\ast }, B^{\ast }, a_{ID^{\ast }}, c_{ID^{\ast },t^{\ast }}\right ),t^{\ast }\right )$ on m ^∗. $\mathcal {C}$ computes $V_{ID^{\ast }}=H(ID^{\ast })$, $V_{ID^{\ast }, t^{\ast }}=H(ID^{\ast }, t^{\ast })$ and M ^∗=H(m ^∗), and then sets $\mathcal {V}_{ID^{\ast }}\subset \{1,\ldots ,n\}$ to be the set of indices i such that $V_{ID^{\ast }}[i]=1$, $\mathcal {V}_{ID^{\ast },t^{\ast }}\subset \{1,\ldots ,n\}$ to be the set of indices i such that $V_{ID^{\ast },t^{\ast }}[i]=1$ and M ^∗[i] be the i-th bit of M ^∗ and lets $\mathcal {M}^{\ast }\subset \{1,\ldots ,n\}$ be the set of indices i such that M ^∗[i]=1, respectively. If $F(\mathcal {V}_{ID^{\ast }})=0\bmod p$ or $F(\mathcal {V}_{ID^{\ast },t^{\ast }})=0\bmod p$ or $F(\mathcal {M}^{\ast })=0\bmod p$, then $\mathcal {C}$ aborts. Otherwise, $\mathcal {C}$ extracts the user secret key $usk_{ID^{\ast }}$ of the target user ID ^∗ and computes

$$\begin{array}{@{}rcl@{}} && \frac{B^{\ast}}{a_{ID^{\ast}}^{J(\mathcal{V}_{ID^{\ast}})}c_{ID^{\ast},t^{\ast}}^{J(\mathcal{V}_{ID^{\ast},t^{\ast}})}(D^{\ast})^{J(\mathcal{M}^{\ast})+usk_{ID^{\ast}}\cdot H_{1}(m^{\ast})}} \\ &=& \frac{(g_{2}^{\alpha}f(\mathcal{V}_{ID^{\ast}})^{d_{u}})^{usk_{ID^{\ast}}}\cdot f(\mathcal{V}_{ID^{\ast}})^{d_{v}}\cdot f(\mathcal{V}_{ID^{\ast},t^{\ast}})^{d_{t}}\cdot f(\mathcal{M}^{\ast})^{d_{m}}\cdot (upk_{ID^{\ast}}^{(1)})^{H_{1}(m^{\ast})d_{m}}}{(g^{d_{u}\cdot usk_{ID^{\ast}}}g^{d_{v}})^{J(\mathcal{V}_{ID^{\ast}})}(g^{d_{t}})^{J(\mathcal{V}_{ID^{\ast},t^{\ast}})}(g^{d_{m}})^{J(\mathcal{M}^{\ast})+usk_{ID^{\ast}}\cdot H_{1}(m^{\ast})}} \\ &=& g^{ab\cdot usk_{ID^{\ast}}} \end{array} $$

$\mathcal {C}$ outputs $g^{ab}=g^{ab\cdot usk_{ID^{\ast }}}/g^{usk_{ID^{\ast }}}$ as the solution to the CDH problem instance. □

Probability analysis

For the simulation to complete without aborting, we require the following conditions fulfilled:

• 1. All Reveal-Partial-Private-Key queries on an identity ID have $F(\mathcal {V}_{ID})\neq 0\bmod l$.

• 2. All Reveal-Signing-Key queries ID in period t have either $F(\mathcal {V}_{ID})\neq 0\bmod l$ or $F(\mathcal {V}_{ID,t})\neq 0\bmod l$.

• 3. All Sign queries (ID, m) in period t have either $F(\mathcal {V}_{ID})\neq 0\bmod l$ or $F(\mathcal {V}_{ID,t})\neq 0\bmod l$ or $F(\mathcal {M})\neq 0\bmod l$.

• 4. $F(\mathcal {V}_{ID^{\ast }})= 0\bmod l$ or $F(\mathcal {V}_{ID^{\ast }, t^{\ast }})= 0\bmod l$ or $F(\mathcal {M}^{\ast })= 0\bmod l$.

Define the events A _i , A ^∗, B _j , B ^∗, C _k , C ^∗ as

• $A_{i}:F(\mathcal {V}_{ID_{i}})\neq 0\bmod l$ where $i=1, \ldots , q_{e}+q_{se}+q_{s} A^{\ast }:F(\mathcal {V}_{ID^{\ast }})=0\bmod p$

• $B_{j}:F(\mathcal {V}_{ID_{j},t_{j}})\neq 0\bmod l$ where $j=1,\ldots , q_{se}+q_{s} B^{\ast }:F(\mathcal {V}_{ID^{\ast }, t^{\ast }})=0\bmod p$

• $C_{k}:F(\mathcal {M}_{k})\neq 0\bmod l$ where $k=1,\ldots , q_{s} C^{\ast }:F(\mathcal {M}^{\ast })=0\bmod p$

The probability of $\mathcal {C}$ not aborting is : Pr[not abort]$\geq Pr[(\bigwedge \limits _{i=1}^{q_{e}+q_{se}+q_{s}}A_{i}\wedge A^{\ast })\wedge (\bigwedge \limits _{j=1}^{q_{se}+q_{s}}B_{j}\wedge B^{\ast })\wedge (\bigwedge \limits _{k=1}^{q_{s}}C_{k}\wedge C^{\ast })]$. It is easy to see that the events $(\bigwedge \limits _{i=1}^{q_{e}+q_{se}+q_{s}}A_{i}\wedge A^{\ast })$, $(\bigwedge \limits _{j=1}^{q_{se}+q_{s}}B_{j}\wedge B^{\ast })$ and $(\bigwedge \limits _{k=1}^{q_{s}}C_{k}\wedge C^{\ast })$ are independent.

The assumption l⋅(n+1)<p implies if $F(\mathcal {V}_{ID_{i}})=0\bmod p$ then $F(\mathcal {V}_{ID_{i}})=0\bmod l$. In addition, it also implies that if $F(\mathcal {V}_{ID_{i}})=0\bmod l$, there is a unique choice of k with 0≤k≤n such that $F(\mathcal {V}_{ID_{i}})=0\bmod p$. Since k, x ₀ and vector (x _i ) of length n are randomly chosen, we have

$$\begin{array}{@{}rcl@{}} Pr[A^{\ast}] \!\!&=& \!\!Pr[F(\mathcal{V}_{ID^{\ast}})=0\bmod p \wedge F(\mathcal{V}_{ID^{\ast}})=0\bmod l] \\ \!&=&\! Pr[F(\mathcal{V}_{ID^{\ast}})=0\bmod l]\\ \!&&\!\times Pr[F(\mathcal{V}_{ID^{\ast}})=0\bmod p|F(\mathcal{V}_{ID^{\ast}})=0\bmod l]\\ &=&\frac{1}{l}\frac{1}{n+1} \end{array} $$

On the other hand, we have $Pr[\bigwedge _{i=1}^{q_{e}+q_{se}+q_{s}}A_{i}| A^{\ast }]=1-Pr[\bigvee _{i=1}^{q_{e}+q_{se}+q_{s}}\overline {A}_{i}| A^{\ast }]\geq 1-{\sum }_{i=1}^{q_{e}+q_{se}+q_{s}}Pr[\overline {A}_{i}| A^{\ast }]$ where $\overline {A}_{i}$ denotes the event $F(\mathcal {V}_{ID_{i}})=0\bmod l$.

Hence , we have

$$\begin{array}{@{}rcl@{}} Pr[\bigwedge\limits_{i=1}^{q_{e}+q_{se}+q_{s}}A_{i}\wedge A^{\ast}] &=& Pr[A^{\ast}]Pr[\bigwedge\limits_{i=1}^{q_{e}+q_{se}+q_{s}}A_{i}|A^{\ast}]\\ &\geq& \frac{1}{l\cdot(n+1)}(1-\frac{q_{e}+q_{se}+q_{s}}{l}) \end{array} $$

and setting l = 2(q _e +q _se +q _s ) as in the simulation gives $Pr[\bigwedge \limits _{i=1}^{q_{e}+q_{se}+q_{s}}A_{i}\wedge A^{\ast }]\geq \frac {1}{4(q_{e}+q_{se}+q_{s})(n+1)}$

A similar analysis for the sign queries gives the result $Pr[\overline {B}_{j}|B^{\ast }] \geq \frac {1}{4(q_{se}+q_{s})(n+1)}$ and $Pr[\overline {C}_{k}|C^{\ast }] \geq \frac {1}{4(q_{s}(n+1)}$, and finally we get that Pr[not abort]$\geq Pr[\overline {A}_{i}|A^{\ast }]Pr[\overline {B}_{j}|B^{\ast }]\geq \frac {1}{64(q_{e}+q_{se}+q_{s})(q_{se}+q_{s})q_{s}(n+1)^{3}}$

If the simulation does not abort, $\mathcal {A}_{1}$ will produce a forged signature with probability at least 𝜖. Thus, $\mathcal {C}$ can solve the CDH problem instance with probability $\epsilon ^{\prime }\geq \frac {\epsilon }{64(q_{e}+q_{se}+q_{s})(q_{se}+q_{s})q_{s}(n+1)^{3}}$

Theorem 2

(Type II Existential Unforgeability). Our CL-KIS scheme is 𝜖-existential unforgeable against Type II adversary with advantage at most 𝜖, assuming that the 𝜖 ^′ -CDH assumption holds in $\mathbb {G}_{1}$ , where $\epsilon ^{\prime }\geq \frac {\epsilon }{64(q_{se}+q_{s})(q_{se}+q_{s})q_{s}(n+1)^{3}}$ where q _se is the number of queries made to the Reveal-Signing-Key oracle, q _s is the number of queries made to the Sign oracle, q _k is the number of queries made to the oracle Reveal-Secret-Key and Request-Public-Key altogether.

Proof

We assume that an 𝜖-Type II adversary $\mathcal {A}_{2}$ for our scheme exists. From this forger, we construct an algorithm $\mathcal {C}$ that solves CDH with probability at least 𝜖 ^′.

The algorithm $\mathcal {C}$ is given a group $\mathbb {G}_{1}$ of prime order p with generator g and elements $g^{a},g^{b}\in \mathbb {G}_{1}$ where a, b are selected uniformly at random from $\mathbb {Z}_{p}^{\ast }$. To be able to use $\mathcal {A}_{2}$ to output g ^ab, $\mathcal {C}$ must be able to simulate a challenger for $\mathcal {A}_{2}$. Such a simulation can be created in the following way:

• Initial. $\mathcal {C}$ executes Setup like Theorem 1. Specifically, $\mathcal {C}$ selects $\alpha \in _{R}\mathbb {Z}_{p}^{*}$ and assigns g ₁ = g ^α, g ₂ = g ^b.

• Attack. $\mathcal {C}$ maintains a list $\mathcal {L}$ which is initially empty and consists of entry (ID, psk _ID , upk _ID , usk _ID ). $\mathcal {C}$ simulates all oracles as follows:

• Request-Public-Key Oracle: Given an identity ID, if ID = ID ^∗, $\mathcal {C}$ selects a secret value $x\leftarrow _{R}\mathbb {Z}_{p}$ and computes the corresponding public key as upk _ID = ((g ^a)^x, (g ^a)^α⋅x). Otherwise, $\mathcal {C}$ looks up its list $\mathcal {L}$ to find out the corresponding entry. If it does not exist, $\mathcal {C}$ runs UserKeyGen and ExtractPartialKey algorithms to generate the secret/public key pair and partial private key respectively. It then stores (ID, psk _ID , upk _ID , usk _ID ) into the list $\mathcal {L}$. In both cases, upk _ID is returned.

• Reveal-Secret-Key Oracle: Upon receiving a query for a public key of an identity ID, if ID = ID ^∗, $\mathcal {C}$ aborts the simulation. Otherwise, $\mathcal {C}$ looks up $\mathcal {L}$ to find out the corresponding entry. If it does not exist, $\mathcal {C}$ runs UserKeyGen to generate a secret and public key pair. It stores the key pair in $\mathcal {L}$ and returns the secret key usk _ID .

  Sign Oracle: For a given query for a signature of ID on $m, ~\mathcal {C}$ checks if the identity is equal to ID ^∗. If yes, it just aborts. Otherwise, $\mathcal {C}$ forges the signature as the same with Theorem 1.

• Forgery. $\mathcal {C}$ executes Forgery like Theorem 1 and outputs the solution to the CDH problem instance.

The probability analysis is similar to the proof of Type I Adversary except the removal of the partial secret key extract query in Type II Adversary. □

6 Potential applications

The potential applications of our CL-KIS scheme are listed as follows:

Secret handshakes [2, 4, 30]: As a fundamental cryptographic primitive, secret handshake scheme enables the members of a certain group to authenticate each other in a private way. Prior to participation, users become group members by registering with group authorities (GAs) and obtaining membership credentials. After that, one member can prove to the communicating peer that it has a valid organizational credential, yet this proof hides the identity of the issuing organization unless the communicating party also has a valid credential from the same organization. The applications of secret handshake range from online dating in the online social networks to the high-bandwidth digital content protection (HDCP). In case the private key of a member has been leaked, it is natural to assume that the adversary can impersonate this member to authenticate with other members in the same group without being observed, which means that the security of the secret handshakes is broken totally. Taking the disastrous consequences of key exposure into account, the secret handshake scheme with key-exposure resilience has been introduced by integrating the idea of key insulated and secret handshakes [29]. However, the key escrow problem was not considered in [29] in the sense that the malicious PKG can impersonate any user since it can generate the private key for any user in the system. Thus, the proposed CL-KIS scheme can be used to construct secret handshakes scheme featured with key escrow resilience and key exposure resilience. Concretely, the KGC in the proposed CL-KIS scheme is acted by the GA in the secret handshake scheme, who is responsible for the registration of new members and for any subsequent membership revocation. After verifying a user’s real identity, GA allocates and sends a list of pseudo-identities along with the corresponding partial private keys to this member secretly. Suppose Alice and Bob are two entities who want to authenticate each other anonymously, they need to send a random message to each other, signed with a certificateless key-insulated signature under the one-time pseudo-identity and the user public key. Alice and Bob can verify the certificateless key-insulated signature on the message, and learn that it definitely came from a legitimate member from the same group. Finally, only GA can open the real identity of a malicious member in a secret handshake instance by looking up the lists of the pseudo-identities corresponding to the real identity.

Multi-receiver authentication[18]:In a large-scale one-to-many (multicast) system such as for TV shopping, a broadcaster (root node) needs to communicate with a huge number of subscribing users (leaf nodes). To impede the pirate users from accessing the TV content free of charge, the broadcaster sends a personal information request along with its signature to the users. After receiving this request, users must transmit personal information to the broadcaster if this request is authenticated. Only when the requested personal information has been received, the broadcaster distributes TV content to this user accordingly. In such a system, the broadcaster has to distribute his new verification key to all subscribing users in an authentic manner to renew his verification key in case the private key of the broadcaster has been compromised. To deal with the key exposure problem without renewing a verification key frequently, the idea of key insulated signature has been employed to design secure provider authentication against key leakage [19, 20]. To enjoy the merits of traditional public key cryptography and ID-PKC altogether, the proposed CL-KIS scheme seems to be a promising approach to address this issue. Specifically, the KGC in the proposed CL-KIS scheme can be instantiated by a semi-trusted commercial organization or government department, who publishes the system parameters and issues the partial private key to the broadcaster.

7 Conclusion

In this paper, we have shown that Wan et al.’s CL-KIS scheme [26] is subjected to malicious-but-passive KGC attack by giving concrete attack. To fix the vulnerabilities in [26], we proposed an improved CL-KIS scheme provably secure in the standard model. As far as we know, this is the first provably secure CL-KIS without random oracles in the literature. Furthermore, we suggest several potential applications that can make use of our CL-KIS scheme, including secret handshakes and one-to-many authentication. We believe our scheme is very useful in many practical applications, such as secret handshakes and one-to-many authentication.