1 Introduction
To simplify public key management and remove the need of certificates required in the traditional public key cryptography, Shamir (1984) presented the notion of identity (ID)-based public key cryptography (ID-PKC). However, ID-PKC encounters the key escrow problem in the sense that the private key generator (PKG) knows all users’ private keys so that the PKG may decrypt all the ciphertexts or sign the messages on behalf of all the users. In order to solve the key escrow problem in ID-PKC, Al-Riyami and Paterson (2003) proposed the certificateless public key cryptography (CL-PKC), in which there are two players, namely, a key generation centre (KGC) and users. The KGC represents a trusted third party and is responsible to generate each user’s initial key. Each user’s full private key consists of two components, namely, the initial key generated by the KGC and a secret key chosen by the user. Meanwhile, in accordance with the secret key, a user can compute her/his corresponding public key. Obviously, the KGC can’t obtain a user’s full private key due to the lack of the user’s self-chosen secret key. Therefore, CL-PKC overcomes the key escrow problem and retains the advantage of eliminating certificates in ID-PKC. Indeed, the study on CL-PKC has received great attention from researchers and a large number of certificateless cryptographic schemes have been proposed such as certificateless public-key encryption (CL-PKE) (Libert and Quisquater, 2006; Hwang et al., 2008; Tsai et al., 2015; Tsai and Tseng, 2015; Hung et al., 2017) and certificateless signature (CLS) (Huang et al., 2007; Hu et al., 2007; Hung et al., 2015, 2016). The mentioned certificateless encryption/signature schemes above were implemented by employing bilinear pairing groups. However, the operations in bilinear pairing groups are more time-consuming than the exponentiation operator in RSA groups. Recently, several RSA-based certificateless encryption/signature schemes (Zhang and Mao, 2012; Sharma et al., 2016; Lin et al., 2017) were proposed to improve computation performance of pairing-based certificateless encryption/signature schemes.
Nevertheless, the previous adversary models of traditional, ID-based and certificateless public key cryptographies usually have a nature assumption that permanent/temporary secret (private) keys must be kept safely and internal secret states are not leaked to an adversary. However, in practice, it is difficult to keep away from all possible kinds of leakage on these secret data due to a new kind of threat, called “side-channel attacks”, such as timing attacks (Kocher, 1996; Brumley and Boneh, 2005), power analysis (Kocher et al., 1999) and fault attacks (Boneh et al., 1997; Biham et al., 2008). By side-channel attacks, an adversary could obtain partial information of these secret data so that some existing adversary models could be insufficient. More precisely, if a cryptographic scheme was proven secure in an adversary model without addressing side-channel attacks, the cryptographic scheme still could be broken in an environment where an adversary may obtain partial information of secret data. Therefore, the study of leakage-resilient cryptography (LRC) resisting to side-channel attacks has received significant attention recently.
The basic concept of LRC is that a cryptographic scheme remains secure when partial information of the secret data involved in the scheme is visible to the adversary. In order to represent the leakage resilience of cryptographic schemes, an adversary model of LRC must define the adversary’s capabilities of obtaining leakage information. A cryptographic scheme typically includes several calculation rounds. For each calculation round, the adversary has a leakage function f on the secret data τ and may obtain the leakage information $f(\tau )$. Also, the output length of f is limited to λ bits. Namely, the adversary can obtain at most λ bits of leakage information for each calculation round. However, the full secret (private) key would be exposed to the adversary if the total leakage information of a cryptographic scheme is unbounded. In such a case, it will compromise the security of the cryptographic scheme. Hence, several leakage-resilient cryptographic schemes (Akavia et al., 2009; Alwen et al., 2009; Katz and Vaikuntanathan, 2009) make a restriction that the total leakage information must be bounded which is called the bounded leakage model. However, this restriction is impractical. Indeed, the continual leakage model is the most accredited model for leakage-invocated ability of an adversary, which provides the overall unbounded leakage property (Brakerski et al., 2010; Dodis and Haralambiev, 2010; Galindo and Virek, 2013; Wu et al., 2016). The properties of the continual leakage model will be reviewed in Section 3.
1.1 Related Work
Akavia et al. (2009) presented the first security model of leakage-resilient public key encryption (LR-PKE) in the bounded leakage model. In their security model, an adversary can select arbitrary leakage functions of the secret (private) keys and obtains the outputs of these functions. They also proposed a concrete LR-PKE scheme, which is the first leakage-resilient chosen plaintext attack (LR-CPA) secure scheme. Naor and Segev (2009, 2012) extended Akavia et al.’s security model of LR-PKE scheme to present the settings of both the leakage-resilient chosen ciphertext attacks (LR-CCA1) and the adaptive leakage resilient chosen ciphertext attacks (LR-CCA2). Meanwhile, Naor and Segev also presented a generic construction of LR-PKE scheme from the universal hash proof system. Liu et al. (2013) and Li et al. (2013), respectively, proposed efficient LR-PKE schemes which have less computational cost than Naor and Segev’s scheme (2009, 2012). The schemes mentioned above are all secure in bounded leakage model, but not under the continual leakage model. Moreover, Kiltz and Pietrzak (2010) proposed a leakage-resilient public key encryption under the continual leakage model using the generic bilinear group (GBG) model (Boneh et al., 2005). The properties of the GBG model will be presented in Section 2. Based on the GBG model, Galindo et al. (2016) also presented and implemented a new ElGamal-like leakage-resilient key encapsulation (LR-KE) scheme under the continual leakage model. All the LR-PKE schemes mentioned above are based on traditional public key settings.
In ID-based public key settings, Brakerski et al. (2010) proposed the first leakage-resilient ID-based encryption (LR-IBE) scheme under the continual leakage model. Afterwards, Yuen et al. (2012) proposed an improved LR-IBE scheme to achieve better performance. Their scheme allows an adversary to learn partial information of both the system secret key in the key extract phase and the user’s private key in the decryption phase. Recently, Li et al. (2016) presented a new LR-IBE scheme under composite order groups. By the post-challenge continuous auxiliary input, their scheme is secure against adaptive chosen plaintext attacks under three static assumptions in the standard model.
Indeed, there exists little work on leakage-resilient certificateless cryptographic schemes. Xiong et al. (2013) proposed the first leakage-resilient certificateless public key encryption (LR-CL-PKE) scheme, which is secure against Type I (outsider) and Type II (honest-but-curious KGC) adversaries. Xiong et al.’s scheme possesses the security against LR-CPA and LR-CCA1 attacks, but not against LR-CCA2 attacks. Zhou et al. (2016) improved Xiong et al.’s scheme to propose a LR-CCA2 secure leakage-resilient certificateless signcryption scheme based on bilinear pairings. However, both Xiong et al.’s and Zhou et al.’s schemes are secure under the bounded leakage model, but not under the continual leakage model.
1.2 Contributions
Up to date, no existing leakage-resilient certificateless public key encryption (LR-CL-PKE) or leakage-resilient certificateless key encapsulation (LR-CL-KE) schemes are secure under the continual leakage model. In this article, we will propose the first LR-CL-KE scheme under the continual leakage model. We first define the adversary model of LR-CL-KE schemes under the continual leakage model. The adversary model is extended from the adversary model of CL-PKE schemes defined in Hwang et al. (2008), Tsai et al. (2015), Tsai and Tseng (2015). The adversary model also consists of two types of adversaries, namely, Type I adversary (outsider) and Type II adversary (honest-but-curious KGC). By adding the leak queries, the new adversary model of LR-CL-KE schemes allows to leak partial information of the system secret key in the initial key extract phase and leak the partial information of the user’s private key in the decrypt phase. The point is that the adversary model provides the overall unbounded leakage property (Galindo and Virek, 2013; Wu et al., 2016) under the continual leakage model. In the generic bilinear group (GBG) model (Boneh et al., 2005), we formally prove that the proposed LR-CL-KE scheme is semantically secure against chosen ciphertext attacks for both Type I and Type II adversaries. Finally, the performance analysis is given to demonstrate the comparison of the proposed LR-CL-KE scheme and the related schemes.
1.3 Organization
The remainder of the article is organized as follows. Preliminaries are given in Section 2. In Section 3, we present the framework and security notions of LR-CL-KE schemes. Then a concrete LR-CL-KE scheme is proposed in Section 4. We analyse the security of the proposed LR-CL-KE scheme in Section 5. Section 6 demonstrates performance comparisons. Conclusions and future work are given in Section 7.
2 Preliminaries
The notions of bilinear groups (Boneh and Franklin, 2001; Waters, 2005; Scott, 2011), the properties of the generic bilinear group model (Galindo and Virek, 2013; Boneh et al., 2005; Wu et al., 2016) and entropy are briefly introduced here.
2.1 Bilinear Pairings
Let G and ${G_{T}}$ be two cyclic multiplicative groups of large prime order p. Let g be a generator of the group G. An admissible bilinear pairing is a map e: $G\times G\to {G_{T}}$ and satisfies the following conditions:
2.2 Generic Bilinear Group Model
The notions of the generic group model were first introduced by Shoup (1997), which is viewed as an adversary model for cryptographic schemes. In the generic group model, an adversary can issue a group oracle (query) to a challenger for executing the group operation (Maurer and Wolf, 1998). The group operation takes as input two group elements and outputs third group element. For example, in a multiplicative group, the group operation is multiplication which multiplies two group elements together to obtain third group element. Namely, the group oracle allows an adversary to have access to a randomly chosen encoding (element) of a group controlled by the challenger. Meanwhile, if the used group allows the other pairing operation such as bilinear pairing, an additional oracle must be provided. One of the main usages of the generic group model is to analyse computational hardness assumptions such as the discrete logarithm problem. It is said to solve the computational hardness assumption if an adversary can efficiently find a collision element of a group operation.
Boneh et al. (2005) extended the generic group model above to present the generic bilinear group (GBG) model. In the GBG model, there exist two multiplicative cyclic groups G and ${G_{T}}$ with three operations, namely, group operations of G and ${G_{T}}$, respectively, and a bilinear pairing operation from $G\times G$ into ${G_{T}}$. The elements of G and ${G_{T}}$ are respectively encoded by two random injective maps $\varepsilon :{Z_{p}}\to \phi $ and ${\varepsilon _{T}}:{Z_{p}}\to {\phi _{T}}$, where both ϕ and ${\phi _{T}}$ are bit strings such that $|\phi \cap {\phi _{T}}|=0$ and $|\phi |=|{\phi _{T}}|=p$. Meanwhile, in the GBG model, two queries (oracles) ${Q_{G}}$ and ${Q_{T}}$ are provided to perform the associated group multiplication operations in G and ${G_{T}}$ while a query ${Q_{P}}$ is used to perform the evaluation of the bilinear map e. For any x, $y\in {Z_{p}^{\ast }}$, three queries have the following properties respectively.
Note that $\varepsilon (1)=g$ and $e(g,g)={\varepsilon _{T}}(1)={g_{T}}$, where g and ${g_{T}}$ are generators of the groups G and ${G_{T}}$, respectively.
2.3 Entropy
Entropy is a number measure of possible states (or microstates) of a system. In addition, the interpretation of entropy in statistics is viewed as the measure of uncertainty. We assume that X is a finite random variable and Pr is the associated probability distribution. The worst-case predictability of a random variable is measured by using min-entropy. Two kinds of min-entropies are defined as follows:
-
(1) ${H_{\infty }}(X)=-{\log _{2}}({\max _{x}}$Pr$[X=x])$ denotes the min-entropy of a finite random variable X.
-
(2) ${\widetilde{H}_{\infty }}(X|Z)=-lo{g_{2}}({E_{z\gets Z}}[{\max _{x}}$Pr$[X=x|Z=z]])$ denotes the average conditional min-entropy of a random variable X under a correlated random variable Z.
Under some condition on the leakage information, Dodis et al. (2008) presented the min-entropy of a finite random variable X by the following Lemma 1.
Lemma 1.
Assume that $f:X\to {0,1^{\lambda }}$ is a leakage function on a secret random variable X and $f(X)$ denotes the leakage information while the output length of f is limited to λ bits. We have ${\widetilde{H}_{\infty }}(X|f(X))$ ⩾ ${H_{\infty }}(X)-\lambda $.
In addition, Galindo and Virek (2013) proved Lemma 2 below to demonstrate the probability distribution of a polynomial under the leakage information. Their result is an extension of the Schwartz–Zippel lemma (Zippel, 1979; Schwartz, 1980).
Lemma 2.
Assume that $F\in {Z_{p}}[{X_{1}},{X_{2}},\dots ,{X_{n}}]$ denotes a non-zero polynomial of total degree at most d. Let ${P_{i}}$ (for $i=1,2,\dots ,n$) be probability distributions on ${Z_{p}}$ such that ${H_{\infty }}({P_{i}})\geqslant \log (p)-\lambda $ and $0\leqslant \lambda \leqslant \log (p)$. If ${x_{i}}\stackrel{{P_{i}}}{\longleftarrow }{Z_{p}}$ (for $i=1,2,\dots ,n$) are independent, we have the probability Pr$[F({x_{1}},{x_{2}},\dots ,{x_{n}})=0]\leqslant \frac{d}{p}{2^{\lambda }}$.
The following result follows directly from Lemma 2.
3 Framework and Security Notions
In this section, we define the framework (syntax) and security notions (adversary model) of leakage-resilient certificateless key encapsulation (LR-CL-KE) schemes under the continual leakage model. Here, we first introduce the properties of the continual leakage model as follows:
-
– Only computation leakage: This property means that only permanent/temporary secret (private) keys accessed and involved in a current calculation round could be leaked to a side-channel adversary.
-
– Bounded leakage of single observation: The length of leakage information in a single calculation round (observation) is limited to some λ bits. This property indicates that the leakage information of each calculation round is bounded to some fraction of secret information.
-
– Independent leakage: The leakage information of all the calculation rounds is independent with each other.
-
– Overall unbounded leakage: This property means that the total amount of leakage information is unbounded. In such a case, secret (private) keys must be updated (refreshed) before/after each calculation round.
In order to achieve the overall unbounded leakage, a continual leakage model must possess the stateful property (Kiltz and Pietrzak, 2010). Firstly, each secret (private) key must be divided into two parts and stored in different parts of the memory. If secret (private) keys are updated before (or after) executing the calculation round in a cryptographic algorithm while the associated public key remains fixed, we say that the cryptographic scheme under continual leakage model provides stateful property.
3.1 Framework of LR-CL-KE Scheme
Here, we present the framework of LR-CL-KE scheme under the continual leakage model.
Definition 1.
A LR-CL-KE scheme consists of seven algorithms:
-
– Setup: Taking a security parameter as input, the key generation centre (KGC) runs this algorithm to generate the first system secret key $({\mathit{SK}_{0,1}},{\mathit{SK}_{0,2}})$ and the public parameters $\mathit{PP}$. The KGC then publishes $\mathit{PP}$ and keeps $({\mathit{SK}_{0,1}},{\mathit{SK}_{0,2}})$ in secret. The KGC also selects a symmetric cryptosystem with encryption function $E()$ and decryption function $D()$.
-
– Initial key extract: For the i-th user with identity ID, the KGC uses this algorithm to generate the first initial key $({\mathit{DID}_{0}},\mathit{QID})$ of the user. This algorithm consists of two sub-algorithms Extract-1 and Extract-2 defined below, in which the current system secret key $({\mathit{SK}_{i-1,1}},{\mathit{SK}_{i-1,2}})$ is used and is updated to $({\mathit{SK}_{i,1}},{\mathit{SK}_{i,2}})$.The KGC then sends the first initial key $({\mathit{DID}_{0}},\mathit{QID})$ to the user.
-
• Extract-1: Given a random number γ, ${\mathit{SK}_{i-1,1}}$ and the user’s identity ID, this sub-algorithm generates $\mathit{QID}$ and temporary information ${\mathit{TI}_{\mathit{IE}}}$, and updates ${\mathit{SK}_{i-1,1}}$ to ${\mathit{SK}_{i,1}}$.
-
• Extract-2: Given ${\mathit{TI}_{\mathit{IE}}}$, and ${\mathit{SK}_{i-1,2}}$, this sub-algorithm generates ${\mathit{DID}_{0}}$ and updates ${\mathit{SK}_{i-1,2}}$ to ${\mathit{SK}_{i,2}}$.
-
-
– Set secret value: This algorithm is performed by a user with identity ID to generate the user’s secret key ${\mathit{SID}_{0}}$ and the partial public key $\mathit{RID}$.
-
– Set private key: This algorithm is performed by a user with identity ID. This algorithm takes the user’s first initial key $({\mathit{DID}_{0}},\mathit{QID})$ and secret key ${\mathit{SID}_{0}}$ as input to set the user’s private key ($({\mathit{DID}_{0,1}},{\mathit{DID}_{0,2}})$, (${\mathit{SID}_{0,1}},{\mathit{SID}_{0,2}}$)).
-
– Set public key: This algorithm is performed by a user with identity ID. This algorithm takes the initial key $({\mathit{DID}_{0}},\mathit{QID})$ and the partial public key $\mathit{RID}$ as input, and outputs the user’s public key $\mathit{PID}=(\mathit{QID},\mathit{RID})$.
-
– Encrypt: Given a plain-message $msg$ and the public key $\mathit{PID}=(\mathit{QID},\mathit{RID})$ of a receiver with identity ID, this algorithm first generates a random value C and the associated encryption key K, and then generates $CT={E_{K}}(msg)$ by using the encryption function $E()$ of a symmetric cryptosystem. Finally, $(C,CT)$ is sent to the receiver.
-
– Decrypt: This algorithm consists of two sub-algorithms Decrypt-1 and Decrypt-2, run by a receiver. For the j-th Decrypt round, the user with identity ID adopts her/his current private key ($({\mathit{DID}_{j-1,1}},{\mathit{DID}_{j-1,2}})$, $({\mathit{SID}_{j-1,1}},{\mathit{SID}_{j-1,2}})$) to decrypt the ciphertext (C, $CT$) by performing two sub-algorithms. In addition, the current private key ($({\mathit{DID}_{j-1,1}},{\mathit{DID}_{j-1,2}})$, (${\mathit{SID}_{j-1,1}}$, ${\mathit{SID}_{j-1,2}}$)) is also updated to ((${\mathit{DID}_{j,1}}$, ${\mathit{DID}_{j,2}}$), (${\mathit{SID}_{j,1}}$, ${\mathit{SID}_{j,2}}$)).
-
• Decrypt-1: Given ${\mathit{DID}_{j-1,1}}$ and ${\mathit{SID}_{j-1,1}}$, this algorithm outputs ${\mathit{DID}_{j,1}}$, ${\mathit{SID}_{j,1}}$ and the temporary information ${\mathit{TI}_{D}}$.
-
• Decrypt-2: Given C, $CT$, ${\mathit{TI}_{D}}$, ${\mathit{DID}_{j-1,2}}$ and ${\mathit{SID}_{j-1,2}}$, this algorithm generates ${\mathit{DID}_{j,2}}$ and ${\mathit{SID}_{j,2}}$ while obtaining the encryption key K. Finally, the receiver can obtain the plain message $msg$ by ${D_{K}}(CT)$ using the decryption function $D()$ of a symmetric cryptosystem.
-
3.2 Security Notions of LR-CL-KE Scheme
By the framework of LR-CL-KE scheme under the continual leakage model described in Section 3.1, an adversary $\mathcal{A}$ can obtain leakage information in four sub-algorithms: Extract-1, Extract-2, Decrypt-1 and Decrypt-2. To represent the leakage information obtained by the adversary in the i-th Initial key extract round, two leakage functions ${f_{\mathit{IE},i}}$ and ${h_{\mathit{IE},i}}$ are chosen to model the adversary’s abilities in Extract-1 and Extract-2, respectively. Meanwhile, two leakage functions ${f_{D,j}}$ and ${h_{D,j}}$ are, respectively, chosen to model the adversary’s ability in Decrypt-1 and Decrypt-2 of a user’s j-th Decrypt round. It is worth mentioning that four leakage functions ${f_{\mathit{IE},i}}$, ${h_{\mathit{IE},i}}$, ${f_{D,j}}$ and ${h_{D,j}}$ can be efficiently computed while the output length of each leakage function is bounded by λ, where λ is the leakage parameter. That is, $|{f_{\mathit{IE},i}}|$, $|{h_{\mathit{IE},i}}|$, $|{f_{D,j}}|$, $|{h_{D,j}}|\leqslant \lambda $, where $|f|$ denotes the output length of leakage function f. We define the outputs of four leakage functions as follows.
-
– $\Lambda {f_{\mathit{IE},i}}={f_{\mathit{IE},i}}$(${\mathit{SK}_{i-1,1}}$, params).
-
– $\Lambda {h_{\mathit{IE},i}}={h_{\mathit{IE},i}}$(${\mathit{SK}_{i-1,2}}$, ${\mathit{TI}_{\mathit{IE}}}$, params).
-
– $\Lambda {f_{D,j}}={f_{D,j}}$(${\mathit{DID}_{j-1,1}}$, ${\mathit{SID}_{j-1,1}}$, params).
-
– $\Lambda {h_{D,j}}={h_{D,j}}$(${\mathit{DID}_{j-1,2}}$, ${\mathit{SID}_{j-1,2}}$, ${\mathit{TI}_{D}}$, params, skeys).
Here, params denotes the random values involved in the computation of four sub-algorithms Extract-1, Extract-2, Decrypt-1 and Decrypt-2. Moreover, skeys denotes the symmetric encryption key. Note that ${\mathit{TI}_{\mathit{IE}}}$ and ${\mathit{TI}_{D}}$ are the outputs of Extract-1 and Decrypt-1, respectively.
The adversary model of LR-CL-KE schemes consists of two types of adversaries, namely, Type I adversary (outsider) and Type II adversary (honest-but-curious KGC). Two types of adversaries are extended from the adversary model of CL-PKE schemes defined in Hwang et al. (2008), Tsai et al. (2015), Tsai and Tseng (2015) by adding the initial key extract leak query and decrypt leak query. This new model of LR-CL-KE schemes allows adversaries to learn partial information of the system secret key in the initial key extract phase and leak partial information of the user’s private key in the decrypt phase. We describe two types of adversaries as follows.
-
• Type I Adversary (Outsider): This kind of adversary simulates the role of an outsider who can replace the public key of any user with another one chosen by herself/himself. That is, a Type I adversary may decide the secret key of any user with her/his choice. In addition, a Type I adversary may obtain the leakage information of a user’s initial key in the decryption phase while leaking partial information of the KGC’s system secret key in the Initial key extract phase.
-
• Type II Adversary (Honest-but-curious KGC): This kind of adversary simulates the role of the honest-but-curious KGC who owns the system’s secret key and is disallowed to perform the public key replacement. In other words, a Type II adversary holds the initial key of any entity. In addition, a Type II adversary may obtain the leakage information of a user’s secret key in the decryption phase.
In the following, a security game is used to model the security notions of the LR-CL-KE scheme under the continual leakage model. The security game below is played by the challenger $\mathcal{B}$ and an adversary $\mathcal{A}$.
Definition 2 (LR-CL-IND-CCA).
We say that a LR-CL-KE scheme is semantically secure against indistinguishability under chosen ciphertext attack (LR-CL-IND-CCA) if no probabilistic polynomial-time (PPT) adversary $\mathcal{A}$ (including Types I and II adversaries) has a non-negligible advantage in the following LR-CL-IND-CCA game played with a challenger $\mathcal{B}$.
-
– Setup. The challenger $\mathcal{B}$ takes a security parameter l as input, and runs the Setup algorithm to generate the first system secret key $({\mathit{SK}_{0,1}},{\mathit{SK}_{0,1}})$ and the public parameters $\mathit{PP}$. $\mathit{PP}$ is sent to the adversary $\mathcal{A}$. In addition, if $\mathcal{A}$ is of Type II adversary, $\mathcal{B}$ also sends $({\mathit{SK}_{0,1}},{\mathit{SK}_{0,1}})$ to $\mathcal{A}$. If $\mathcal{A}$ is of Type I adversary, the first system secret key $({\mathit{SK}_{0,1}},{\mathit{SK}_{0,1}})$ is kept secret by $\mathcal{B}$.
-
– Phase 1. In this phase, the adversary $\mathcal{A}$ may adaptively issue the following queries:
-
• Initial key extract query (ID). For the i-th Initial key extract query along with a user’s identity ID, the challenger $\mathcal{B}$ uses the current system secret key $({\mathit{SK}_{i-1,1}},{\mathit{SK}_{i-1,2}})$ to generate the user’s first initial key (${\mathit{DID}_{0}}$, $\mathit{QID}$) while updating (${\mathit{SK}_{i-1,1}}$, ${\mathit{SK}_{i-1,2}}$) to (${\mathit{SK}_{i,1}}$, ${\mathit{SK}_{i,2}}$). Finally, $\mathcal{B}$ returns (${\mathit{DID}_{0}}$, $\mathit{QID}$) to $\mathcal{A}$.
-
• Initial key extract leak query (${f_{\mathit{IE},i}},{h_{\mathit{IE},i}},i$): By providing two leakage functions ${f_{\mathit{IE},i}}$ and ${h_{\mathit{IE},i}}$, $\mathcal{A}$ can issue the Initial key extract leak query only once for the i-th Initial key extract query. The challenger $\mathcal{B}$ computes the leakage information ($\Lambda {f_{\mathit{IE},i}},\Lambda {h_{\mathit{IE},i}}$) and returns it to $\mathcal{A}$.
-
• Public key retrieve query (ID). Upon receiving this query along with an identity ID, $\mathcal{B}$ returns the corresponding public key $\mathit{PID}=(\mathit{QID},\mathit{RID})$.
-
• Public key replace query (ID, ${\mathit{PID}^{\prime }}=({\mathit{QID}^{\prime }},{\mathit{RID}^{\prime }})$). Upon receiving this query along with (ID, ${\mathit{PID}^{\prime }}$), $\mathcal{B}$ records the replacement. It means that the adversary $\mathcal{A}$ has replaced the user’s public key with ${\mathit{PID}^{\prime }}=({\mathit{QID}^{\prime }},{\mathit{RID}^{\prime }})$.
-
• Secret key extract query (ID). When the challenger $\mathcal{B}$ receives this query along with an identity ID, $\mathcal{B}$ returns the secret key ${\mathit{SID}_{0}}$. Moreover, the query is forbidden if Public key replace query (ID) has been previously queried in this game.
-
• Decrypt query (ID, C). For the j-th Decrypt round, upon receiving this query along with an identity ID and a ciphertext C, the challenger $\mathcal{B}$ uses the user’s current private key (${\mathit{DID}_{j-1}}=({\mathit{DID}_{j-1,1}},{\mathit{DID}_{j-1,2}}$), ${\mathit{SID}_{j}}=({\mathit{SID}_{j-1,1}},{\mathit{SID}_{j-1,2}}$)) to generate the encryption key K by running two sub-algorithms Decrypt-1 and Decrypt-2. The challenger $\mathcal{B}$ then returns K to $\mathcal{A}$. It is worth mentioning that the current private key $({\mathit{DID}_{j-1}}=({\mathit{DID}_{j-1,1}},{\mathit{DID}_{j-1,2}})$, ${\mathit{SID}_{j}}=({\mathit{SID}_{j-1,1}}$, ${\mathit{SID}_{j-1,2}}$)) is also updated to (${\mathit{DID}_{j}}=({\mathit{DID}_{j,1}},{\mathit{DID}_{j,2}})$, ${\mathit{SID}_{j}}=({\mathit{SID}_{j,1}},{\mathit{SID}_{j,2}}$)).
-
• Decrypt leak query (${f_{D,j}}$, ${h_{D,j}}$, j): By providing two leakage functions ${f_{D,j}}$ and ${h_{D,j}}$, $\mathcal{A}$ can issue the Decrypt leak query only once for the j-th Decrypt query. $\mathcal{B}$ computes the leakage information ($\Lambda {f_{D,j}}$, $\Lambda {h_{D,j}}$) and returns it to $\mathcal{A}$. In addition, if $\mathcal{A}$ is of Type II adversary (honest-but-curious KGC), ($\Lambda {f_{D,j}}$, $\Lambda {h_{D,j}}$) includes only the leakage information of a user’s secret key (${\mathit{SID}_{j-1,1}}$, ${\mathit{SID}_{j-1,2}}$) since $\mathcal{A}$ knows the initial key of any entity. If $\mathcal{A}$ is of Type I adversary (outsider), the adversary may obtain the leakage information of a user’s initial key $({\mathit{DID}_{j-1,1}},{\mathit{DID}_{j-1,2}})$ since an outsider owns the secret key of any entity.
-
-
– Challenge. The adversary $\mathcal{A}$ chooses a target identity ID${^{\ast }}$ and a plaintext pair ($ms{g_{0}^{\ast }}$, $ms{g_{1}^{\ast }}$) to the challenger $\mathcal{B}$. Two restrictions are described as follows.The challenger $\mathcal{B}$ chooses a random $\beta \in \{0,1\}$ and computes ${C^{\ast }}=E(PP$, ID${^{\ast }}$, $ms{g_{\beta }^{\ast }}$, $P{K_{I{D^{\ast }}}}$) by running the Encrypt algorithm. Then $\mathcal{B}$ sends ${C^{\ast }}$ to $\mathcal{A}$. Here $P{K_{I{D^{\ast }}}}$ is the public key of the identity ID${^{\ast }}$.
-
1. If $\mathcal{A}$ is of Type I adversary (outsider), the Initial key extract query (ID${^{\ast }}$) is not queried in Phase 1.
-
2. If $\mathcal{A}$ is of Type II adversary (honest-but-curious KGC), it is disallowed to issue the queries on the Secret value extract query and Public key replace query on ID${^{\ast }}$ in Phase 1.
-
-
– Guess. The adversary $\mathcal{A}$ outputs ${\beta ^{\prime }}\in \{0,1\}$ and wins this game if ${\beta ^{\prime }}=\beta $.
In the LR-CL-IND-CCA game above, we call the adversary $\mathcal{A}$ as a LR-CL-IND-CCA adversary. We define the adversary $\mathcal{A}$’s advantage in attacking the LR-CL-KE scheme as $Ad{v_{A}}(l)=|Pr[\beta ={\beta ^{\prime }}]-\frac{1}{2}|$.
Remark
The LR-CL-IND-CCA game defined above models the security notion of LR-CL-KE scheme against non-adaptive chosen ciphertext attacks (CCA1). For the security notion against adaptive chosen ciphertext attack (CCA2), a new Phase 2 is inserted between the Challenge phase and Guess phase. In the Phase 2, $\mathcal{A}$ may issue further queries as in Phase 1 while a restriction is that $\mathcal{A}$ cannot make a Decrypt query on the challenge ciphertext ${C^{\ast }}=E$(Parms, ID${^{\ast }}$, $ms{g_{\beta }^{\ast }}$, $P{K_{I{D^{\ast }}}}$). It is worth mentioning that our LR-CL-KE scheme is secure against CCA1 under the continual leakage model, but it can’t achieve CCA2 security. The reason will be discussed in Section 5.
4 The Proposed LR-CL-KE Scheme
In the following, we propose the first LR-CL-KE scheme, denoted by Π. As the framework defined in Section 3.1, the LR-CL-KE scheme consists of seven algorithms as follows:
In the following, we show the correctness of recovering the encryption key.
-
– Setup: Given a security parameter l, the KGC first generates two multiplicative groups G and ${G_{T}}$ of prime order p and then randomly picks a generator g of G. Let $e:G\times G\to {G_{T}}$ be an admissible bilinear pairing. The KGC also selects a symmetric cryptosystem with encryption function $E()$ and decryption function $D()$. The KGC runs the following steps to generate the first system secret key $({\mathit{SK}_{0,1}},{\mathit{SK}_{0,1}})$ and the public parameters $\mathit{PP}$:
-
(1) Randomly pick $x\in {Z_{p}^{\ast }}$ and compute $X={g^{x}}$ and ${X_{T}}=e({g^{x}},g)$.
-
(2) Randomly pick $\alpha \in {Z_{p}^{\ast }}$ and set the first system secret key $({\mathit{SK}_{0,1}},{\mathit{SK}_{0,1}})=({g^{\alpha }},X\cdot {g^{\alpha }})$.
-
(3) Randomly pick ${u_{i0}}$, ${u_{i1}}\in {Z_{q}^{\ast }}$ and compute ${U_{0}}$= ${g^{{u_{i0}}}}$ and ${U_{1}}$= ${g^{{u_{i1}}}}$.
-
(4) Publish $\mathit{PP}=(G,{G_{T}},e,p,g,{X_{T}},{U_{0}},{U_{1}},E,D)$.
-
-
– Initial key extract: For the i-th Initial key extract round, upon receiving a user’s identity ID, the KGC generates the first initial key $({\mathit{DID}_{0}},\mathit{QID})$ of the user by running two sub-algorithms Extract-1 and Extract-2 as follows. In addition, the current system secret key $({\mathit{SK}_{i-1,1}},{\mathit{SK}_{i-1,2}})$ is also updated to $({\mathit{SK}_{i,1}},{\mathit{SK}_{i,2}})$. Finally, the KGC sends the first initial key $({\mathit{DID}_{0}},\mathit{QID})=(X\cdot {({U_{0}}\cdot {U_{1}^{ID}})^{\gamma }},{g^{\gamma }})$ to the user via a secure channel. Note that the user may validate the correctness of $({\mathit{DID}_{0}},\mathit{QID})$ by checking the equality $e(g,{\mathit{DID}_{0}})={X_{T}}\cdot e(\mathit{QID},{U_{0}}\cdot {U_{1}^{ID}})$.
-
– Set secret value: A user with identity ID chooses a random number $z\in {Z_{p}^{\ast }}$ and computes the first secret key ${\mathit{SID}_{0}}$ and the partial public key $\mathit{RID}$, where $({\mathit{SID}_{0}},\mathit{RID})=({g^{z}},e({g^{z}},g))$.
-
– Set private key: Given the initial key $({\mathit{DID}_{0}},\mathit{QID})$ and the secret key ${\mathit{SID}_{0}}$, the user sets her/his private key by the steps below:
-
– Set public key: Given the initial key $({\mathit{DID}_{0}},\mathit{QID})$ and the partial public key $\mathit{RID}$, the user with identity ID sets her/his public key $\mathit{PID}=(\mathit{QID},\mathit{RID})=({g^{\gamma }},e({g^{z}},g))$.
-
– Decrypt: For the j-th Decrypt round, given the ciphertext $(C,CT)$, the receiver with identity ID uses the current private key ($({\mathit{DID}_{j-1,1}},{\mathit{DID}_{j-1,2}})$, (${\mathit{SID}_{j-1,1}}$, ${\mathit{SID}_{j-1,2}}$)) to recover the plaintext $msg$ by performing two sub-algorithms as follows. In addition, the current private key ($({\mathit{DID}_{j-1,1}},{\mathit{DID}_{j-1,2}})$, (${\mathit{SID}_{j-1,1}}$, ${\mathit{SID}_{j-1,2}}$)) is also updated to ((${\mathit{DID}_{j,1}}$, ${\mathit{DID}_{j,2}}$), (${\mathit{SID}_{j,1}}$, ${\mathit{SID}_{j,2}}$)).
-
• Decrypt-1: The receiver uses ${\mathit{DID}_{j-1,1}}$ and ${\mathit{SID}_{j-1,1}}$ to compute the temporary information ${\mathit{TI}_{1}}$ and ${\mathit{TI}_{2}}$ by the following steps:
-
• Decrypt-2: Given C, $CT$, ${\mathit{TI}_{1}}$ and ${\mathit{TI}_{2}}$, the receiver uses ${\mathit{DID}_{j-1,2}}$ and ${\mathit{SID}_{j-1,2}}$ to return plaintext $msg$ by the following steps:
-
(1) Compute ${\mathit{DID}_{j,2}}={\mathit{DID}_{j-1,2}}\cdot {g^{-b}}$ and ${\mathit{SID}_{j,2}}={\mathit{SID}_{j-1,2}}\cdot {g^{-c}}$.
-
(2) Compute ${K^{\prime }_{1}}={\mathit{TI}_{1}}\cdot e(C,{\mathit{SID}_{j,2}})$ and ${K^{\prime }_{2}}={\mathit{TI}_{2}}\cdot e(C,{\mathit{DID}_{j,2}})$.
-
(3) The encryption key is computed by ${K^{\prime }}={K^{\prime }_{1}}\oplus {K^{\prime }_{2}}$.
-
(4) Obtain the plaintext $msg={D_{{K^{\prime }}}}(CT)$ by using a symmetric cryptosystem.
-
-
\[\begin{aligned}{}K=& {K_{1}}\oplus {K_{2}}\\ {} =& {(\mathit{RID})^{k}}\oplus \big({X_{T}}\cdot e(\mathit{QID},{U_{0}}\cdot {U_{1}^{ID}})\big)k\\ {} =& e{({g^{z}},g)^{k}}\oplus ({X_{T}}\cdot e{\big({g^{\gamma }},{U_{0}}\cdot {U_{1}^{ID}})\big)^{k}}\\ {} =& e\big({g^{k}},{g^{z}}\big)\oplus \big(e\big({g^{x}},g\big)\cdot e{\big({g^{\gamma }},{U_{0}}\cdot {U_{1}^{ID}}\big)\big)^{k}}\\ {} =& e\big({g^{k}},{\mathit{SID}_{0}}\big)\oplus (e\big(g,{g^{x}}\big)\cdot e{\big(g,{({U_{0}}\cdot {U_{1}^{ID}})^{\gamma }}\big)^{k}}\\ {} =& e\big({g^{k}},{\mathit{SID}_{0}}\big)\oplus (e{\big(g,{g^{x}}\cdot {({U_{0}}\cdot {U_{1}^{ID}})^{\gamma }}\big)^{k}}\\ {} =& e\big({g^{k}},{\mathit{SID}_{0}}\big)\oplus e\big({g^{k}},X\cdot {({U_{0}}\cdot {U_{1}^{ID}})^{\gamma }}\big)\\ {} =& e(C,{\mathit{SID}_{0}})\oplus e(C,{\mathit{DID}_{0}})\\ {} =& e\big(C,{\mathit{SID}_{0}}\cdot {g^{-\omega }}\cdot {g^{\omega }}\big)\oplus e\big(C,{\mathit{DID}_{0}}\cdot {g^{-\beta }}\cdot {g^{\beta }}\big)\\ {} =& e\big(C,{g^{\omega }}\big)\cdot e\big(C,{\mathit{SID}_{0}}\cdot {g^{-\omega }}\big)\oplus e\big(C,{g^{\beta }}\big)\cdot e\big(C,{\mathit{DID}_{0}}\cdot {g^{-\beta }}\big)\\ {} =& e(C,{\mathit{SID}_{0,1}})\cdot e(C,{\mathit{SID}_{0,2}})\oplus e(C,{\mathit{DID}_{0,1}})\cdot e(C,{\mathit{DID}_{0,2}})\\ {} =& {\mathit{TI}_{1}}\cdot e(C,{\mathit{SID}_{0,2}})\oplus {\mathit{TI}_{2}}\cdot e(C,{\mathit{DID}_{0,2}})\\ {} =& {K^{\prime }_{1}}\oplus {K^{\prime }_{2}}\\ {} =& {K^{\prime }}.\end{aligned}\]
5 Security Analysis
As the aforementioned LR-CL-IND-CCA game in Definition 2, there are two types of adversaries, Type I (outsider) and Type II (honest-but-curious KGC). In the section, we present the security analysis of the proposed LR-CL-KE scheme under the continual leakage model for both Type I and Type II adversaries. Indeed, our proposed LR-CL-KE scheme achieves only the CCA1 security (See *Remark in Section 3), but it can’t achieve the CCA2 security. The reason is that an adversary, given the challenge ciphertext ${C^{\ast }}$ with encryption key $K={K_{1}}\oplus {K_{2}}$, can obtain the entire K via the leakage information. That is, the adversary may ask the Decrypt query with input (${C^{\ast }}{)^{2}}\ne {C^{\ast }}$ repeatedly to collect the leakage information about ${K_{1}^{2}}$ and ${K_{2}^{2}}$ by Decrypt leak query. Then the adversary can reconstruct ${K_{1}}$ and ${K_{2}}$ from ${K_{1}^{2}}$ and ${K_{2}^{2}}$, respectively. Finally, an adversary may compute the encryption key $K={K_{1}}\oplus {K_{2}}$. To our best knowledge, no LR-CL-KE scheme under continual leakage model can achieve the CCA2 security.
In the following, we first introduce the non-leakage version of our LR-CL-KE scheme, denoted by ${\Pi _{\mathit{NL}}}$. Then we prove that the non-leakage version ${\Pi _{\mathit{NL}}}$ is CL-IND-CCA secure in the generic bilinear group model. Next, based on the security of the non-leakage version ${\Pi _{\mathit{NL}}}$, we prove that the proposed LR-CL-KE scheme is LR-CL-IND-CCA secure under the continual leakage model.
The non-leakage version ${\Pi _{\mathit{NL}}}$ of our LR-CL-KE scheme consists of seven algorithms as follows:
-
– Setup${_{\mathit{NL}}}$: In this algorithm, the KGC generates the system secret key $X={g^{x}}$, where x is a random number picked from ${Z_{p}^{\ast }}$. Moreover, the public parameters $\mathit{PP}=(G,{G_{T}},e,p,g,{X_{T}},{U_{0}},{U_{1}})$ are identical to those in the proposed LR-CL-KE scheme. Finally, the KGC publishes the public parameters $\mathit{PP}$.
-
– Initial key extract${_{\mathit{NL}}}$: The KGC generates the initial key $(\mathit{DID},\mathit{QID})=(X\cdot {({U_{0}}\cdot {U_{1}^{ID}})^{\gamma }},{g^{\gamma }})$ of a user with identity ID, where γ is picked from ${Z_{p}^{\ast }}$ randomly. The KGC then sends the initial key $(\mathit{DID},\mathit{QID})$ to the user via a secure channel.
-
– Set secret value${_{\mathit{NL}}}$: A user chooses a random number z in ${Z_{p}^{\ast }}$, and computes the user’s secret key $\mathit{SID}={g^{z}}$ and the associated partial public key $\mathit{RID}=e({g^{z}},g)$.
-
– Set private key${_{\mathit{NL}}}$: A user sets her/his private key $(\mathit{DID},\mathit{SID})=(X\cdot {({U_{0}}\cdot {U_{1}^{ID}})^{\gamma }},{g^{z}})$.
-
– Set public key${_{\mathit{NL}}}$: A user sets her/his public key $\mathit{PID}=(\mathit{QID},\mathit{RID})$.
-
– Encrypt${_{\mathit{NL}}}$: Given the public key $\mathit{PID}=(\mathit{QID},\mathit{RID})$ of a user with identity ID, the sender randomly chooses $k\in {Z_{p}^{\ast }}$, and then computes $C={g^{k}}$, ${K_{1}}={(\mathit{RID})^{k}}$ and ${K_{2}}={({X_{T}}\cdot e(\mathit{QID},{U_{0}}\cdot {U_{1}^{ID}}))^{k}}$. The encryption key is $K={K_{1}}\oplus {K_{2}}$. The ciphertext ($C,CT={E_{K}}(msg)$) is sent to the receiver, where $msg$ is the plaintext.
-
– Decrypt${_{\mathit{NL}}}$: Upon receiving a user’s identity ID and the ciphertext $(C,CT)$, the receiver uses the private key $(\mathit{DID},\mathit{SID})$ to get the encryption key $K={K_{1}}\oplus {K_{2}}$ by computing ${K_{1}}=e(C,\mathit{SID})$ and ${K_{2}}=e(C,\mathit{DID})$. Then she/he can decrypt the plaintext $msg={D_{K}}(CT)$.
In Theorems 1 and 2, we prove that the non-leakage version ${\Pi _{\mathit{NL}}}$ of our LR-CL-KE scheme is CL-IND-CCA secure against Types I and II adversaries, respectively. Moreover, in Theorems 3 and 4, we prove that our LR-CL-KE scheme is LR-CL-IND-CCA secure against Types I and II adversaries, respectively.
Theorem 1.
In the generic bilinear group model, the non-leakage version ${\Pi _{\mathit{NL}}}$ of our LR-CL-KE scheme is CL-IND-CCA secure against Type I adversary (outsider).
Proof.
Let ${\mathcal{A}_{\mathit{NL}-I}}$ be Type I adversary (outsider) who can break the non-leakage version ${\Pi _{\mathit{NL}}}$. The adversary ${\mathcal{A}_{\mathit{NL}-I}}$ can adaptively issue all the queries at most q times in total. The advantage that ${\mathcal{A}_{\mathit{NL}-I}}$ breaks ${\Pi _{\mathit{NL}}}$ is bounded by the success probability of ${\mathcal{A}_{\mathit{NL}-I}}$ in the game ${g_{\mathit{NL}-I}}$ which is played by a challenger $\mathcal{B}$ and the adversary ${\mathcal{A}_{\mathit{NL}-I}}$ as follows:
*Game ${g_{\mathit{NL}-I}}$: In the game ${g_{\mathit{NL}-I}}$, there are four phases, namely, Setup, Phase 1, Challenge and Guess, which are described as follows.
-
– Setup: The challenger $\mathcal{B}$ constructs two lists ${L_{G}}$ and ${L_{T}}$ to record the elements in the groups G and ${G_{T}}$, respectively.Moreover, two additional lists ${L_{\mathit{IK}}}$ and ${L_{SK}}$ are constructed to record the user’s initial key and the user’s secret key, respectively. More precisely, the elements in ${L_{\mathit{IK}}}$ are of the form $(\mathit{ID},\mathit{DID},\mathit{QID})$ and the elements in ${L_{\mathit{SK}}}$ are of the form (ID, $\mathit{SID}$, $\mathit{RID}$), where ID is in ${Z_{p}}$, and $\mathit{DID}$, $\mathit{QID}$, $\mathit{SID}$ and $\mathit{RID}$ are multivariate polynomials. At the end of this phase, the challenger $\mathcal{B}$ sends the public parameters $\mathit{PP}$ to ${\mathcal{A}_{\mathit{NL}-I}}$ (using the form of bit strings).
-
• The list ${L_{G}}$ consists of elements of the form (${P_{G,m,n,r}}$, ${\phi _{G,m,n,r}}$). Each ${P_{G,m,n,r}}$ is a multivariate polynomial consists of a finite numbers of variates in G with coefficients in ${Z_{p}}$. For a multivariate polynomial ${P_{G,m,n,r}}$, the challenger $\mathcal{B}$ uses a bit string ${\phi _{G,m,n,r}}$ to communicate with ${\mathcal{A}_{\mathit{NL}-I}}$. The first index “G” in ${P_{G,m,n,r}}$ or ${\phi _{G,m,n,r}}$ indicates that ${P_{G,m,n,r}}$ or ${\phi _{G,m,n,r}}$ is an element in G and is an element in ${G_{T}}$ if the index G is replaced by T. Moreover, the second index “m” indicates the type of query. The third and fourth indices “n” and “r” indicate the r-th element in $G/{G_{T}}$ which appeared in the n-th query. Four tuples $(g,{\phi _{G,I,1,1}})$, $(X,{\phi _{G,I,1,2}})$, $({U_{0}},{\phi _{G,I,1,3}})$ and $({U_{1}},{\phi _{G,I,1,4}})$ are initially added in the list ${L_{G}}$.
-
• The list ${L_{T}}$ is used to record the elements with the form of $({P_{T,m,n,r}},{\phi _{T,m,n,r}})$. The meanings of all indexes of ${P_{T,m,n,r}}$ are the same with the descriptions of ${P_{G,m,n,r}}$ earlier. ${P_{T,m,n,r}}$ is a multivariate polynomial with coefficients in ${Z_{p}}$ and variates in G or ${G_{T}}$. For each multivariate polynomial ${P_{T,m,n,r}}$, the challenger $\mathcal{B}$ uses the bit string ${\phi _{T,m,n,r}}$ to communicate with ${\mathcal{A}_{\mathit{NL}-I}}$. The tuple $({X_{T}},{\phi _{T,I,1,1}})$ is initially added into ${L_{T}}$.
-
-
– Phase 1: In this phase, ${\mathcal{A}_{\mathit{NL}-I}}$ can adaptively issue the following queries at most q times totally.Finally, $\mathcal{B}$ computes the bit string ${\phi _{T,D,i,4}}={\phi _{T,D,i,1}}\oplus {\phi _{T,D,i,2}}$ (which denotes K). At the end of this query, the challenger $\mathcal{B}$ obtains the plaintext $ms{g_{i}}={D_{K}}(C{T_{i}})$ by using the decryption key K. Finally, $\mathcal{B}$ returns $ms{g_{i}}$ to ${\mathcal{A}_{\mathit{NL}-I}}$.
-
• Group G query ${Q_{G}}$ (${\phi _{G,Q,i,1}}$, ${\phi _{G,Q,i,2}}$, operation): For the i-th group query ${Q_{G}}$, ${\mathcal{A}_{\mathit{NL}-I}}$ queries $\mathcal{B}$ along with two bit strings $({\phi _{G,Q,i,1}},{\phi _{G,Q,i,2}})$ and an operation (multiplication or division). The challenger $\mathcal{B}$ performs the following steps.Note that the polynomials ${P_{G,Q,i,1}}$, ${P_{G,Q,i,2}}$ and ${P_{G,Q,i,3}}$ mentioned above are recorded in the list ${L_{G}}$.
-
(i) $\mathcal{B}$ first translates two bit strings ${\phi _{G,Q,i,1}}$ and ${\phi _{G,Q,i,2}}$ into two polynomials ${P_{G,Q,i,1}}$ and ${P_{G,Q,i,2}}$, respectively, in the following way. $\mathcal{B}$ tries to find a pair (${P_{G,m,n,r}}$, ${\phi _{G,m,n,r}}$) in ${L_{G}}$ such that ${\phi _{G,m,n,r}}={\phi _{G,Q,i,1}}$. If so, $\mathcal{B}$ sets ${P_{G,Q,i,1}}={P_{G,m,n,r}}$. Otherwise, $\mathcal{B}$ defines a new variate ${S_{G,Q,i,1}}$ in G, sets ${P_{G,Q,i,1}}={S_{G,Q,i,1}}$, and records $({P_{G,Q,i,1}},{\phi _{G,Q,i,1}})$ in ${L_{G}}$. Similarly, $\mathcal{B}$ also translates the bit string ${\phi _{G,Q,i,2}}$ to ${P_{G,Q,i,2}}$.
-
(ii) $\mathcal{B}$ computes the polynomial ${P_{G,Q,i,3}}={P_{G,Q,i,1}}+{P_{G,Q,i,2}}$ if the operation is multiplication, or ${P_{G,Q,i,3}}={P_{G,Q,i,1}}-{P_{G,Q,i,2}}$ if the operation is division.
-
(iii) $\mathcal{B}$ uses ${P_{G,Q,i,3}}$ to find an element $({P_{G,m,n,r}},{\phi _{G,m,n,r}})$ in ${L_{G}}$ such that ${P_{G,m,n,r}}={P_{G,Q,i,3}}$. If so, $\mathcal{B}$ returns ${\phi _{G,m,n,r}}$ to ${\mathcal{A}_{\mathit{NL}-I}}$. Otherwise, $\mathcal{B}$ randomly chooses a bit string, denoted by ${\phi _{G,Q,i,3}}$, which is distinct from all bit strings recorded in ${L_{G}}$ and ${L_{T}}$. Finally, $\mathcal{B}$ records $({P_{G,Q,i,3}},{\phi _{G,Q,i,3}})$ in ${L_{G}}$ and returns ${\phi _{G,Q,i,3}}$ to ${\mathcal{A}_{\mathit{NL}-I}}$.
-
-
• Group ${G_{T}}$ query ${Q_{T}}$(${\phi _{T,Q,i,1}}$, ${\phi _{T,Q,i,2}}$, operation): For the i-th group query ${Q_{T}}$, ${\mathcal{A}_{\mathit{NL}-I}}$ queries $\mathcal{B}$ along with two bit strings (${\phi _{T,Q,i,1}}$, ${\phi _{T,Q,i,2}}$) and an operation (multiplication or division). The process of this query is similar to that of the Group G query ${Q_{G}}$. $\mathcal{B}$ finally returns ${\phi _{T,Q,i,3}}$ to ${\mathcal{A}_{\mathit{NL}-I}}$. After this query, the polynomials ${P_{T,Q,i,1}}$, ${P_{T,Q,i,2}}$ and ${P_{T,Q,i,3}}$ are recorded in ${L_{T}}$.
-
• Pairing query ${Q_{P}}$$({\phi _{G,P,i,1}},{\phi _{G,P,i,2}})$: For the i-th pairing query ${Q_{P}}$, ${\mathcal{A}_{\mathit{NL}-I}}$ takes as input two bit strings ${\phi _{G,P,i,1}}$ and ${\phi _{G,P,i,2}}$. $\mathcal{B}$ performs the following steps:Note that the polynomials ${P_{G,P,i,1}}$, ${P_{G,P,i,2}}$ and ${P_{T,P,i,1}}$ are recorded in the list ${L_{G}}$ or ${L_{T}}$ after this query.
-
(i) $\mathcal{B}$ first translates two bit strings ${\phi _{G,P,i,1}}$ and ${\phi _{G,P,i,2}}$ to two polynomials ${P_{G,P,i,1}}$ and ${P_{G,P,i,2}}$, respectively. This step is similar to the Step 1 of the Group G query ${Q_{G}}$.
-
(ii) $\mathcal{B}$ computes the polynomial ${P_{T,P,i,1}}={P_{G,P,i,1}}\cdot {P_{G,P,i,2}}$.
-
(iii) $\mathcal{B}$ uses ${P_{T,P,i,1}}$ to find $({P_{T,m,n,r}},{\phi _{T,m,n,r}})$ in ${L_{T}}$ such that ${P_{T,m,n,r}}={P_{T,P,i,1}}$. If so, $\mathcal{B}$ returns ${\phi _{T,m,n,r}}$ to ${\mathcal{A}_{\mathit{NL}-I}}$. Otherwise, $\mathcal{B}$ randomly chooses a bit string, denoted by ${\phi _{T,P,i,1}}$, which is distinct from all bit strings recorded in ${L_{G}}$ and ${L_{T}}$. Then $\mathcal{B}$ records $({P_{T,P,i,1}},{\phi _{T,P,i,1}})$ in ${L_{T}}$ and returns ${\phi _{T,P,i,1}}$ to ${\mathcal{A}_{\mathit{NL}-I}}$.
-
-
• Initial key extract query ${Q_{\mathit{IE}}}$(${\mathit{ID}_{\mathit{IE},i}}$): For the i-th Initial key extract query, ${\mathcal{A}_{\mathit{NL}-I}}$ queries $\mathcal{B}$ along with a user’s identity $I{D_{\mathit{IE},i}}\in {Z_{p}^{\ast }}$. $\mathcal{B}$ tries to find ${\mathit{ID}_{\mathit{IE},i}}$ in ${L_{\mathit{IK}}}$. If so, $\mathcal{B}$ obtains the corresponding multivariate polynomials ${P_{G,IE,i,1}}$ and ${P_{G,IE,i,2}}$ of the user’s initial key $\mathit{DID}$ and $\mathit{QID}$. $\mathcal{B}$ then returns two corresponding bit strings ${\phi _{G,IE,i,1}}$ and ${\phi _{G,IE,i,2}}$ to ${\mathcal{A}_{\mathit{NL}-I}}$. Otherwise, $\mathcal{B}$ performs three steps as follows:The challenger $\mathcal{B}$ also records a tuple (${\mathit{ID}_{\mathit{IE},i}}$, ${P_{G,IE,i,1}}$, ${P_{G,IE,i,2}}$) in the list ${L_{\mathit{IK}}}$.
-
(i) $\mathcal{B}$ selects one variate ${T_{G,IE,i,2}}$ in G (which denotes the $\mathit{QID}$ of ${\mathit{ID}_{\mathit{IE},i}}$) and sets ${P_{G,IE,i,2}}$=${T_{G,IE,i,2}}$. Moreover, $\mathcal{B}$ randomly chooses a bit string, denoted by ${\phi _{G,IE,i,2}}$, which is distinct from all bit strings recorded in ${L_{G}}$ and ${L_{T}}$. Then $\mathcal{B}$ records (${P_{G,IE,i,2}}$, ${\phi _{G,IE,i,2}}$) in ${L_{G}}$.
-
(ii) $\mathcal{B}$ computes the polynomial ${P_{G,IE,i,1}}=X+({U_{0}}+{\mathit{ID}_{\mathit{IE},i}}\cdot {U_{1}})\cdot {T_{G,IE,i,2}}$, which represents the $\mathit{DID}$ of ${\mathit{ID}_{\mathit{IE},i}}$.
-
(iii) Finally, $\mathcal{B}$ chooses a bit string ${\phi _{G,IE,i,1}}$, which is distinct from all bit strings recorded in ${L_{G}}$ and ${L_{T}}$. Then $\mathcal{B}$ records (${P_{G,IE,i,1}}$, ${\phi _{G,IE,i,1}}$) in ${L_{G}}$ and returns (${\phi _{G,IE,i,1}}$, ${\phi _{G,IE,i,2}}$ ) to ${\mathcal{A}_{\mathit{NL}-I}}$.
-
-
• Secret key extract query ${Q_{\mathit{SE}}}$(${\mathit{ID}_{SE,i}}$): For the i-th Secret key extract query, ${\mathcal{A}_{\mathit{NL}-I}}$ queries the challenger $\mathcal{B}$ along with an identity ${\mathit{ID}_{SE,i}}$. $\mathcal{B}$ performs the following steps and finally outputs the bit strings (${\phi _{T,SE,i,1}}$, ${\phi _{T,SE,i,2}}$), which represent the secret key ($\mathit{SID}$, $\mathit{RID}$) to ${\mathcal{A}_{\mathit{NL}-I}}$:The challenger $\mathcal{B}$ also records (${\mathit{ID}_{SE,i}}$, ${P_{G,SE,i,1}}$, ${P_{T,SE,i,2}}$) in the list ${L_{\mathit{SK}}}$.
-
(i) The challenger $\mathcal{B}$ checks whether the secret key of identity ${\mathit{ID}_{SE,i}}$ has been recorded in ${L_{\mathit{SK}}}$. If so, $\mathcal{B}$ returns the bit strings (${\phi _{T,SE,i,1}}$, ${\phi _{T,SE,i,2}}$), which represents the secret key $(\mathit{SID},\mathit{RID})$ to ${\mathcal{A}_{\mathit{NL}-I}}$. Otherwise, $\mathcal{B}$ defines a new variate ${T_{G,SE,i,2}}$ in G and sets ${P_{G,SE,i,1}}={T_{G,SE,i,1}}$, which represents the $\mathit{SID}$ of ${\mathit{ID}_{SE,i}}$. Moreover, $\mathcal{B}$ randomly chooses a new bit string, denoted by ${\phi _{G,SE,i,1}}$, which is distinct from all bit strings recorded in ${L_{G}}$ and ${L_{T}}$. Then $\mathcal{B}$ records (${P_{G,SE,i,1}}$, ${\phi _{G,SE,i,1}}$) in ${L_{G}}$.
-
(ii) $\mathcal{B}$ sets the polynomial ${P_{T,SE,i,2}}={T_{G,SE,i,1}}\cdot g$, which represents the $\mathit{RID}$ for ${\mathit{ID}_{SE,i}}$.
-
(iii) Finally, $\mathcal{B}$ first randomly chooses a new bit string, denoted by ${\phi _{T,SE,i,2}}$, which is distinct from all bit strings recorded in ${L_{G}}$ and ${L_{T}}$. Then $\mathcal{B}$ records (${P_{T,SE,i,2}}$, ${\phi _{T,SE,i,2}}$) in ${L_{T}}$ and returns (${\phi _{G,SE,i,1}}$, ${\phi _{T,SE,i,2}}$) to ${\mathcal{A}_{\mathit{NL}-I}}$.
-
-
• Public key retrieve query ${Q_{\mathit{PK}}}({\mathit{ID}_{PK,i}})$: Upon receiving the i-th Public key retrieve query with an identity ${\mathit{ID}_{PK,i}}\in {Z_{p}^{\ast }}$ as input, the challenger $\mathcal{B}$ performs the following three steps:
-
(i) $\mathcal{B}$ checks whether ${\mathit{ID}_{PK,i}}$ has been recorded in ${L_{\mathit{IK}}}$. If so, $\mathcal{B}$ obtains the corresponding polynomial of $\mathit{QID}$ for ${\mathit{ID}_{PK,i}}$ in ${L_{\mathit{IK}}}$. Otherwise, $\mathcal{B}$ performs the Initial key extract query along with identity ${\mathit{ID}_{PK,i}}$ to generate the polynomial of $\mathit{QID}$.
-
(ii) $\mathcal{B}$ also checks whether ${\mathit{ID}_{PK,i}}$ has been recorded in ${L_{\mathit{SK}}}$. If so, $\mathcal{B}$ obtains the corresponding polynomial of $\mathit{RID}$ for ${\mathit{ID}_{PK,i}}$ in ${L_{\mathit{SK}}}$. Otherwise, $\mathcal{B}$ performs the Secret key extract query with identity ${\mathit{ID}_{PK,i}}$ to generate the polynomial of $\mathit{RID}$ for ${\mathit{ID}_{PK,i}}$.
-
(iii) Finally, C returns two bit strings of polynomials representing $\mathit{QID}$ and $\mathit{RID}$ by searching ${L_{G}}$ and ${L_{T}}$, respectively.
-
-
• Public key replace query ${Q_{\mathit{PR}}}({\mathit{ID}_{\mathit{PR},i}},{\phi _{T,\mathit{PR},i,2}})$: By this query, the adversary ${\mathcal{A}_{\mathit{NL}-I}}$ is allowed to use the bit string ${\phi _{T,\mathit{PR},i,2}}$ to replace the partial public key $\mathit{RID}$ of a user with identity ${\mathit{ID}_{\mathit{PR},i}}$. That is, ${\mathcal{A}_{\mathit{NL}-I}}$ can select a valid secret key $\mathit{SID}$ (i.e. bit string ${\phi _{T,\mathit{PR},i,2}}$) by herself/himself and set the corresponding $\mathit{RID}$. $\mathcal{B}$ then records this replacement. More precisely, upon receiving this query, $\mathcal{B}$ first translates ${\phi _{T,\mathit{PR},i,2}}$ into the corresponding polynomial ${P_{T,\mathit{PR},i,2}}$ by the list ${L_{T}}$. Since ${\mathcal{A}_{\mathit{NL}-I}}$ has the ability to generate the user’s secret key by asking the group oracles, $\mathcal{B}$ can obtain the polynomial ${P_{G,\mathit{PR},i,1}}$ by searching ${P_{T,\mathit{PR},i,2}}={P_{G,\mathit{PR},i,1}}\cdot g$ in the list ${L_{G}}$. The challenger $\mathcal{B}$ then updates the user’s secret key (${\mathit{ID}_{\mathit{PR},i}}$, ${\mathit{SID}_{\mathit{PR},i}}$, ${\mathit{RID}_{\mathit{PR},i}})=({\mathit{ID}_{\mathit{PR},i}}$, ${P_{G,\mathit{PR},i,1}}$, ${P_{T,\mathit{PR},i,2}}$) in ${L_{\mathit{SK}}}$.
-
• Decrypt query ${Q_{D}}$(${\mathit{ID}_{D,i}},{C_{i}},C{T_{i}}$): For the i-th Decrypt round, when ${\mathcal{A}_{\mathit{NL}-I}}$ queries $\mathcal{B}$ along with a user’s identity ${\mathit{ID}_{D,i}}$ and a ciphertext pair (${C_{i}},C{T_{i}}$), $\mathcal{B}$ performs the following two parts to obtain the encryption key K:
-
(1) When $\mathcal{B}$ receives the query, $\mathcal{B}$ first obtains the user’s initial key $\mathit{DID}$ and secret key $\mathit{SID}$ from the lists ${L_{\mathit{IK}}}$ and ${L_{\mathit{SK}}}$, respectively, by the following procedures:
-
(i) $\mathcal{B}$ uses ${\mathit{ID}_{D,i}}$ to find the user’s initial key $\mathit{DID}$ in the list ${L_{\mathit{IK}}}$. If so, $\mathcal{B}$ obtains $\mathit{DID}$ in ${L_{\mathit{IK}}}$. Otherwise, $\mathcal{B}$ issues the query ${Q_{\mathit{IE}}}$(${\mathit{ID}_{D,i}}$) to obtain $\mathit{DID}$.
-
(ii) $\mathcal{B}$ uses ${\mathit{ID}_{D,i}}$ to find the user’s secret key $\mathit{SID}$ in the list ${L_{\mathit{SK}}}$. If so, $\mathcal{B}$ obtains $\mathit{SID}$ in ${L_{\mathit{SK}}}$. Otherwise, $\mathcal{B}$ issues the query ${Q_{\mathit{SE}}}$(${\mathit{ID}_{D,i}}$) to obtain $\mathit{SID}$.
-
(iii) Hence, $\mathcal{B}$ has obtained the polynomials ${P_{G,IE,k,1}}$ and ${P_{G,SE,l,1}}$, which represent $\mathit{DID}$ and $\mathit{SID}$, respectively.
-
-
(2) The challenger $\mathcal{B}$ obtains the encryption key K by performing the following steps:
-
(i) $\mathcal{B}$ checks whether the corresponding polynomial of the ciphertext ${C_{i}}$ has been recorded in the list ${L_{G}}$. If so, $\mathcal{B}$ obtains the polynomial ${P_{G,D,i,3}}$. Otherwise, $\mathcal{B}$ defines a new variate ${T_{G,D,i,3}}$ in G and sets ${P_{G,D,i,3}}={T_{G,D,i,3}}$. Moreover, $\mathcal{B}$ randomly chooses a bit string, denoted by ${\phi _{G,D,i,3}}$, which is distinct from all bit strings in ${L_{G}}$ and ${L_{T}}$.
-
(ii) $\mathcal{B}$ computes the polynomial ${P_{T,D,i,1}}={P_{G,SE,l,1}}\cdot {T_{G,D,i,1}}$ (which denotes ${K_{1}}$) and the polynomial ${P_{T,D,i,2}}={P_{G,IE,l,1}}\cdot {T_{G,D,i,1}}$ (which denotes ${K_{2}}$). $\mathcal{B}$ uses ${P_{T,D,i,1}}$ and ${P_{T,D,i,2}}$ to respectively find $({P_{T,m,j,r}},{\phi _{T,m,j,r}})$ and $({P_{T,m,j,2}},{\phi _{T,m,j,2}})$ in ${L_{T}}$ (i.e. $PT,m,j,r={P_{T,D,i,1}}$ and ${P_{T,m,j,2}}={P_{T,D,i,2}}$). If so, $\mathcal{B}$ then sets the ${\phi _{T,D,i,1}}={\phi _{T,m,j,r}}$ and ${\phi _{T,D,i,2}}={\phi _{T,m,j,2}}$. Otherwise, $\mathcal{B}$ randomly chooses two bit strings, denoted by ${\phi _{T,D,i,1}}$ and ${\phi _{T,D,i,2}}$, which represent the bit strings of ${K_{1}}$ and ${K_{2}}$, respectively. Then $\mathcal{B}$ records (${P_{T,D,i,1}}$, ${\phi _{T,D,i,1}}$) and (${P_{T,D,i,2}}$, ${\phi _{T,D,i,2}}$) in ${L_{T}}$.
-
-
-
-
– Challenge: The adversary ${\mathcal{A}_{\mathit{NL}-I}}$ gives a target identity ID${^{\ast }}$ and a plaintext pair $(ms{g_{0}^{\ast }},ms{g_{1}^{\ast }})$ to $\mathcal{B}$. Because ${\mathcal{A}_{\mathit{NL}-I}}$ is an outsider, ID${^{\ast }}$ is disallowed to be queried in the Initial key extract query of Phase 1. The challenger $\mathcal{B}$ first chooses a random bit $\beta \in \{0,1\}$, then $\mathcal{B}$ defines a new variate ${T_{G,C,1,3}}$ in G and sets ${P_{G,C,1,3}}={T_{G,C,1,3}}$ (which denotes ${C^{\ast }}$). Moreover, $\mathcal{B}$ randomly chooses a bit string, denoted by ${\phi _{G,C,i,3}}$. Afterwards, $\mathcal{B}$ obtains K by the same steps described in the second part of the Decrypt query. At the end of this phase, the challenger $\mathcal{B}$ computes the ciphertext $C{T^{\ast }}={E_{K}}(ms{g_{\beta }^{\ast }})$. Finally, $\mathcal{B}$ returns ${C^{\ast }}$ and $C{T^{\ast }}$ to ${\mathcal{A}_{\mathit{NL}-I}}$.
-
– Guess: The adversary ${\mathcal{A}_{\mathit{NL}-I}}$ outputs ${\beta ^{\prime }}\in \{0,1\}$. If ${\beta ^{\prime }}=\beta $, we say that the adversary ${\mathcal{A}_{\mathit{NL}-I}}$ wins the game ${g_{\mathit{NL}-I}}$.
Here, both the adversary ${\mathcal{A}_{\mathit{NL}-I}}$ and the challenger $\mathcal{B}$ have completed the game ${g_{\mathit{NL}-I}}$. Before evaluating the probability of ${\mathcal{A}_{\mathit{NL}-I}}$ winning the game ${g_{\mathit{NL}-I}}$, we first define several notations and restrictions as follows.
-
(1) In the Phase 1, ${\mathcal{A}_{\mathit{NL}-I}}$ may issue eight kinds of queries ${Q_{G}}$, ${Q_{T}}$, ${Q_{P}}$, ${Q_{\mathit{IE}}}$, ${Q_{\mathit{SE}}}$, ${Q_{\mathit{PK}}}$, ${Q_{\mathit{PR}}}$, ${Q_{D}}$. We define several collections (sets) as follows:
-
• $\{S\}$: The collection of all used variates ${S_{G,Q,i,j}}$ in the query ${Q_{G}}$ and ${S_{G,P,i,j}}$ in the query ${Q_{P}}$.
-
• $\{V\}$: The collection of all used variates ${V_{T,Q,i,j}}$ in the query ${Q_{T}}$.
-
• $\{T\}$: The collection of all used variates ${T_{G,IE,i,2}}$ in the query ${Q_{\mathit{IE}}}$, ${T_{G,D,i,3}}$ in the query ${Q_{D}}$ and ${T_{G,SE,i,1}}$ in the query ${Q_{\mathit{SE}}}$.
-
• $\{\mathit{PG}\}$: The collection of all used polynomials ${P_{G,Q,i,k}}$ , ${P_{G,IE,i,k}}$ and ${P_{G,D,i,k}}$ in the Phase 1.
-
• $\{\mathit{PT}\}$: The collection of all used polynomials ${P_{T,Q,i,k}}$ and ${P_{T,P,i,k}}$ in the Phase 1.
-
-
(2) Let ${q_{O}}$ denote the total number of three queries ${Q_{G}}$, ${Q_{T}}$ and ${Q_{P}}$ while ${q_{\mathit{IE}}}$, ${q_{\mathit{SE}}}$, ${q_{\mathit{PK}}}$, ${q_{\mathit{PR}}}$ and ${q_{D}}$, respectively, represent the numbers of ${Q_{\mathit{IE}}}$, ${Q_{\mathit{SE}}}$, ${Q_{\mathit{PK}}}$, ${Q_{\mathit{PR}}}$ and ${Q_{D}}$. Note that ${\mathcal{A}_{\mathit{NL}-I}}$ can issue all kinds of queries at most q times in total. Hence, we have $q\geqslant {q_{O}}+{q_{\mathit{IE}}}+{q_{\mathit{SE}}}+{q_{\mathit{PK}}}+{q_{\mathit{PR}}}+{q_{D}}$. Let $|{L_{G}}|$ and $|{L_{T}}|$ be the total numbers of elements in ${L_{G}}$ and ${L_{T}}$, respectively. Therefore, $|{L_{G}}|$+ $|{L_{T}}|$ is bounded by $6q$ due to the following reasons:Hence, we have
-
• For each query of ${Q_{G}}$, ${Q_{T}}$ or ${Q_{P}}$, at most 3 elements are recorded in ${L_{G}}$ or ${L_{T}}$.
-
• For each query of ${Q_{\mathit{IE}}}$ or ${Q_{\mathit{SE}}}$, at most 2 new elements are recorded in ${L_{G}}$ or ${L_{T}}$.
-
• For each query of ${Q_{\mathit{PK}}}$, at most 4 new elements are recorded in ${L_{G}}$ or ${L_{T}}$.
-
• For each query of ${Q_{\mathit{PR}}}$, at most 2 new elements are recorded in ${L_{G}}$ or ${L_{T}}$.
-
• For each query of ${Q_{D}}$, at most 6 new elements are recorded in ${L_{G}}$ or ${L_{T}}$.
\[ |{L_{G}}|+|{L_{T}}|\leqslant 5+3{q_{O}}+2{q_{\mathit{IE}}}+2{q_{\mathit{SE}}}+4{q_{\mathit{PK}}}+2{q_{\mathit{PR}}}+6{q_{D}}+1.\]Let $6\leqslant 3{q_{O}}+4{q_{\mathit{IE}}}+4{q_{\mathit{SE}}}+2{q_{\mathit{PK}}}+4{q_{\mathit{PR}}}$, we have -
-
(3) In the following, we discuss the degrees of all multivariate polynomials in $\{{P_{G}}\}$.Therefore, the degrees of all multivariate polynomials in $\{{P_{G}}\}$ are at most 2.
-
• All polynomials in $\{S\}$ and $\{T\}$ are of degree 1.
-
• In ${Q_{\mathit{IE}}}$, each polynomial ${P_{G,\mathit{IE},i,k}}$ has degree at most 2.
-
• In ${Q_{\mathit{SE}}}$, each polynomial ${P_{G,\mathit{SE},i,1}}$ has degree 1.
-
• In ${Q_{D}}$, each polynomial ${P_{G,D,i,k}}$ has degree at most 2.
-
• In ${Q_{G}}$, the polynomial ${P_{G,Q,i,3}}$ is generated by ${P_{G,Q,i,3}}={P_{G,Q,i,1}}+{P_{G,Q,i,2}}$. Hence the degree of ${P_{G,Q,i,3}}$ is less than or equal to the maximal degree of ${P_{G,Q,i,1}}$ and ${P_{G,Q,i,2}}$.
-
-
(4) In the following, we obtain that the degrees of all multivariate polynomials in $\{{P_{T}}\}$ are at most 4:
-
• All polynomials in {V} are of degree 1.
-
• In ${Q_{P}}$, the degree of each polynomial ${P_{T,P,i,k}}$ is at most 4 since each polynomial ${P_{G}}$ has degree at most 2.
-
• In ${Q_{\mathit{SE}}}$, the degree of each polynomial ${P_{T,\mathit{SE},i,2}}$ is 2.
-
• In ${Q_{T}}$, the polynomial ${P_{T,Q,i,3}}$ is generated by ${P_{T,Q,i,3}}={P_{T,Q,i,1}}+{P_{T,Q,i,2}}$. Hence, the degree of ${P_{G,Q,i,3}}$ is less than or equal to the maximal degree of ${P_{T,Q,i,1}}$ and ${P_{T,Q,i,2}}$.
-
In the following, let us discuss the probability that ${\mathcal{A}_{\mathit{NL}-I}}$ wins the game ${g_{\mathit{NL}-I}}$. After completing the game ${g_{\mathit{NL}-I}}$, the challenger $\mathcal{B}$ chooses random values x, ${u_{0}}$, ${u_{1}}$, $\{{s_{1}},{s_{2}},\dots ,\}$, ${t_{1}},{t_{2}},\dots ,$ in ${Z_{q}^{\ast }}$, which represent the values X, ${U_{0}}$, ${U_{1}}$, $\{S\}$, $\{T\}$ in the group G. $\mathcal{B}$ also chooses random values $\{{v_{1}},{v_{2}},\dots ,\}$ in ${Z_{q}^{\ast }}$, which represent the values $\{V\}$ in the group ${G_{T}}$. ${\mathcal{A}_{\mathit{NL}-I}}$ is said to win the game ${g_{\mathit{NL}-I}}$ if one of the following cases happens:
-
• Case 1. There is a collision in G or ${G_{T}}$ which can be described as follows:
-
(i) In the list ${L_{G}}$, there exist two polynomials ${P_{G,i}}$ and ${P_{G,j}}$ such that ${P_{G,i}}$(x , ${u_{0}}$, ${u_{1}}$, $\{s\}$, $\{t\})={P_{G,j}}(x,{u_{0}},{u_{1}},\{s\},\{t\})$.
-
(ii) In the list ${L_{T}}$, there exist two polynomials ${P_{T,i}}$ and ${P_{T,j}}$ such that ${P_{T,i}}(x,{u_{0}},{u_{1}},s,\{t\},\{v\})={P_{T,j}}(x,{u_{0}},{u_{1}},s,\{t\},\{v\})$ .
-
-
• Case 2. The adversary ${\mathcal{A}_{\mathit{NL}-I}}$ outputs ${\beta ^{\prime }}=\beta $ in the Guess phase.
In the real CL-IND-CCA game, the success probability in the simulated game ${g_{\mathit{NL}-I}}$ is an upper bound of the success probability of ${\mathcal{A}_{\mathit{NL}-I}}$. Let us discuss the probabilities of two cases as follows.
-
• Case 1. If ${\mathcal{A}_{\mathit{NL}-I}}$ can find any collisions within G or ${G_{T}}$, one can solve the discrete logarithm problem in G or ${G_{T}}$. Let ${P_{G,i}}$ and ${P_{G,j}}$ denote two distinct polynomials in ${L_{G}}$. Then we obtain the polynomials ${P_{G,C}}={P_{G,i}}-{P_{G,j}}$ is a non-zero polynomial of degree at most 2. By applying Lemma 2 in Section 2 with $\lambda =0$, the probability that ${P_{G,C}}(x,{u_{0}},{u_{1}},\{s\},\{t\})=0$ in ${Z_{q}}$ is at most $\frac{2}{p}$. Since there are $\left(\genfrac{}{}{0pt}{}{|{L_{G}}|}{2}\right)$ different pairs $({P_{G,i}},{P_{G,j}})$, the probability that Case 1 occurs is at most $\frac{2}{p}\left(\genfrac{}{}{0pt}{}{|{L_{G}}|}{2}\right)$. Similarly, the collision probability in ${L_{T}}$ is at most $\frac{4}{p}\left(\genfrac{}{}{0pt}{}{|{L_{T}}|}{2}\right)$ since the polynomials in ${L_{T}}$ have degree at most 4.
-
• Case 2. If ${\mathcal{A}_{\mathit{NL}-I}}$ can’t find any collision in G or ${G_{T}}$, the view of ${\mathcal{A}_{\mathit{NL}-I}}$ in the game ${g_{\mathit{NL}-I}}$ is identical to that in the real CL-IND-CCA game. If the adversary ${\mathcal{A}_{\mathit{NL}-I}}$ doesn’t obtain any useful information in the game ${g_{\mathit{NL}-I}}$, she/he still has the probability $\frac{1}{2}$ on average to output a correct ${\beta ^{\prime }}=\beta $.
Now we evaluate the probability that ${\mathcal{A}_{\mathit{NL}-I}}$ wins the game ${g_{\mathit{NL}-I}}$, denoted by $P{r_{\mathit{NL}-I}}$. Firstly, we define two events of $P{r_{\mathit{NL}-I}}$ as follows.
Meanwhile, let $\overline{\mathit{FAC}}$ and $\overline{\mathit{GBC}}$ denote the complement events of $\mathit{FAC}$ and $\mathit{GBC}$, respectively. The probability that ${\mathcal{A}_{\mathit{NL}-I}}$ wins ${g_{\mathit{NL}-I}}$ can be bounded by
Here, as discussed in Case 1, the probabilities that ${\mathcal{A}_{\mathit{NL}-I}}$ can find a collision in G and ${G_{T}}$ are $\frac{2}{p}$ $\left(\genfrac{}{}{0pt}{}{|{L_{G}}|}{2}\right)$ and $\frac{4}{p}\left(\genfrac{}{}{0pt}{}{|{L_{T}}|}{2}\right)$, respectively. Hence, we have
\[ Pr[\mathit{FAC}]\leqslant \bigg[\frac{2}{p}\left(\genfrac{}{}{0pt}{}{|{L_{G}}|}{2}\right)+\frac{4}{p}\left(\genfrac{}{}{0pt}{}{|{L_{T}}|}{2}\right)\bigg]\leqslant \frac{2}{p}{(|{L_{G}}|+|{L_{T}}|)^{2}}\leqslant \frac{72{q^{2}}}{p}.\]
On the other hand, in case ${\mathcal{A}_{\mathit{NL}-I}}$ can’t find collisions in G or ${G_{T}}$, ${\mathcal{A}_{\mathit{NL}-I}}$ still has probability $\frac{1}{2}$ on average to make a correct guess of ${\beta ^{\prime }}$. Therefore, we have
\[ P{r_{\mathit{NL}-I}}\leqslant Pr[\mathit{FAC}]+Pr[\overline{\mathit{FAC}}\wedge \mathit{GBC}]\leqslant \frac{72{q^{2}}}{p}+\bigg(1-\frac{72{q^{2}}}{p}\bigg)\cdot \frac{1}{2}.\]
The advantage of ${\mathcal{A}_{\mathit{NL}-I}}$ is
\[ Ad{v_{A}}\leqslant \bigg|\frac{72{q^{2}}}{p}+\frac{1}{2}\cdot \bigg(1-\frac{72{q^{2}}}{p}\bigg)-\frac{1}{2}\bigg|=\frac{36{q^{2}}}{p},\]
which is negligible if $q=\mathit{poly}(\log p)$. □Theorem 2.
In the generic bilinear group model, the non-leakage version ${\Pi _{\mathit{NL}}}$ of our LR-CL-KE scheme is CL-IND-CCA secure against Type II adversary (honest-but-curious KGC).
Proof.
Let ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ be a Type II adversary who can break the non-leakage CL-KE scheme ${\Pi _{\mathit{NL}}}$. Meanwhile, the adversary ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ is allowed to issue all queries at most q times. The advantage that ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ breaks ${\Pi _{\mathit{NL}}}$ is bounded by the success probability of ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ in the game ${g_{\mathit{NL}-\mathit{II}}}$ which is played by both the adversary ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ and a challenger $\mathcal{B}$ as follows:
Game ${g_{\mathit{NL}-\mathit{II}}}$: In the game ${g_{\mathit{NL}-\mathit{II}}}$, there are four phases, namely, Setup, Phase 1, Challenge and Guess.
-
– Setup: In this phase, the challenger $\mathcal{B}$ constructs two lists ${L_{G}}$ and ${L_{T}}$ to record the elements in G and ${G_{T}}$, respectively. $\mathcal{B}$ also maintains two lists ${L_{\mathit{IK}}}$ and ${L_{\mathit{SK}}}$ to record the user’s initial key and the user’s secret key, respectively. The forms of ${L_{G}}$, ${L_{T}}$, ${L_{\mathit{IK}}}$ and ${L_{\mathit{SK}}}$ are the same with those described in the game ${g_{\mathit{NL}-I}}$. At the end of this phase, the challenger $\mathcal{B}$ sends the bit strings of the public parameters $\mathit{PP}$ to ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$. Since ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ represents an honest-but-curious KGC, $\mathcal{B}$ also sends the system secret key X (using the form of bit string) to ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$.
-
– Phase 1: Since ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ models the honest-but-curious KGC, ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ can obtain the user’s initial key by issuing the queries ${Q_{G}}$, ${Q_{T}}$ and ${Q_{P}}$. Meanwhile, ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ is not allowed to perform the Public key replacement query. In this phase, ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ can adaptively issue the queries as follows:
-
• Group G query ${Q_{G}}$(${\phi _{G,Q,i,1}}$, ${\phi _{G,Q,i,2}}$, operation): The query is identical to ${Q_{G}}$ presented in the game ${g_{\mathit{NL}-I}}$.
-
• Group ${G_{T}}$ query ${Q_{T}}$(${\phi _{T,Q,i,1}}$, ${\phi _{T,Q,i,2}}$, operation): The query is identical to ${Q_{T}}$ presented in the game ${g_{\mathit{NL}-I}}$.
-
• Pairing query ${Q_{P}}$(${\phi _{G,P,i,1}}$, ${\phi _{G,P,i,2}}$ ): The query is identical to ${Q_{P}}$ presented in the game ${g_{\mathit{NL}-I}}$.
-
• Secret key extract query ${Q_{\mathit{SE}}}$(${\mathit{ID}_{\mathit{SE},i}}$): The query is identical to ${Q_{\mathit{SE}}}$ presented in the game ${g_{\mathit{NL}-I}}$.
-
• Public key retrieve query ${Q_{\mathit{PK}}}$(${\mathit{ID}_{\mathit{PK},i}}$): For the i-th Public key retrieve query with an identity ${\mathit{ID}_{PK,i}}$, $\mathcal{B}$ runs three steps as follows:
-
(i) $\mathcal{B}$ checks whether ${\mathit{ID}_{PK,i}}$ was recorded in ${L_{\mathit{IK}}}$. If so, $\mathcal{B}$ may obtain the corresponding polynomial of $\mathit{QID}$ for ${\mathit{ID}_{PK,i}}$. Otherwise, $\mathcal{B}$ uses the records of the queries ${Q_{G}}$, ${Q_{T}}$ and ${Q_{P}}$ to obtain the corresponding polynomials of $\mathit{DID}$ and $\mathit{QID}$ for ${\mathit{ID}_{\mathit{PK},i}}$ while updating the list ${L_{\mathit{IK}}}$ for ${\mathit{ID}_{\mathit{PK},i}}$.
-
(ii) $\mathcal{B}$ checks whether ${\mathit{ID}_{\mathit{PK},i}}$ was recorded in ${L_{\mathit{SK}}}$. If so, $\mathcal{B}$ may obtain the corresponding polynomial of $\mathit{RID}$ for ${\mathit{ID}_{\mathit{PK},i}}$. Otherwise, $\mathcal{B}$ may issue the Secret key extract query ${Q_{\mathit{SE}}}({\mathit{ID}_{PK,i}})$ to obtain the corresponding polynomial of $\mathit{RID}$ for ${\mathit{ID}_{\mathit{PK},i}}$.
-
(iii) Finally, $\mathcal{B}$ returns $\mathit{QID}$ and $\mathit{RID}$ (with the form of bit strings) by searching the lists ${L_{G}}$ and ${L_{T}}$, respectively.
-
-
• Decrypt query ${Q_{D}}({\mathit{ID}_{D,i}},{C_{i}},C{T_{i}})$: For the i-th Decrypt round, when ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ queries $\mathcal{B}$ along with a user’s identity ${\mathit{ID}_{D,i}}$ and a ciphertext pair $({C_{i}},C{T_{i}})$, $\mathcal{B}$ performs the following two parts to obtain the encryption key K:Finally, $\mathcal{B}$ computes the bit string ${\phi _{T,D,i,4}}={\phi _{T,D,i,1}}\oplus {\phi _{T,D,i,2}}$ (which denotes K). At the end of this query, $\mathcal{B}$ obtains the plaintext $ms{g_{i}}={D_{K}}(C{T_{i}})$ by using the decryption key K. Finally, $\mathcal{B}$ returns $ms{g_{i}}$ to ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$.
-
(1) $\mathcal{B}$ first obtains the user’s initial key $\mathit{DID}$ and secret key $\mathit{SID}$ from the lists ${L_{\mathit{IK}}}$ and ${L_{\mathit{SK}}}$ as follows:
-
(i) $\mathcal{B}$ checks whether the user’s initial key $\mathit{DID}$ of ${\mathit{ID}_{D,i}}$ has been recorded in ${L_{\mathit{IK}}}$. If so, $\mathcal{B}$ obtains the corresponding polynomial of $\mathit{DID}$ for ${\mathit{ID}_{D,i}}$ in ${L_{\mathit{IK}}}$. Otherwise, $\mathcal{B}$ uses the records of the queries ${Q_{G}}$, ${Q_{T}}$ and ${Q_{P}}$ to obtain the corresponding polynomials of $\mathit{DID}$ and $\mathit{QID}$ for ${\mathit{ID}_{D,i}}$ while updating the list ${L_{\mathit{IK}}}$ for ${\mathit{ID}_{D,i}}$.
-
(ii) $\mathcal{B}$ uses ${\mathit{ID}_{D,i}}$ to find the user’s secret key $\mathit{SID}$ in the list ${L_{\mathit{SK}}}$. If so, $\mathcal{B}$ obtains $\mathit{SID}$ in ${L_{\mathit{SK}}}$. Otherwise, $\mathcal{B}$ issues the query ${Q_{\mathit{SE}}}$(${\mathit{ID}_{D,i}}$) to obtain $\mathit{SID}$.
-
(iii) Hence, $\mathcal{B}$ have obtained the corresponding polynomials ${P_{G,IE,k,1}}$ and ${P_{G,SE,l,1}}$, which represent $\mathit{DID}$ and $\mathit{SID}$, respectively.
-
-
(2) $\mathcal{B}$ can obtain the encryption key K by using the same steps in the Decrypt query of the game ${g_{\mathit{NL}-I}}$.
-
-
-
– Challenge: This phase is similar to the Challenge phase described in ${g_{\mathit{NL}-I}}$. The only difference is that ID${^{\ast }}$ is not allowed to be queried in the Secret key extract query of Phase 1 since ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ is the honest-but-curious KGC.
-
– Guess: The adversary ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ outputs ${\beta ^{\prime }}\in \{0,1\}$. If ${\beta ^{\prime }}=\beta $, we say that the adversary ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ wins the game ${g_{\mathit{NL}-\mathit{II}}}$.
As the same arguments in Theorem 1, we can compute the success probability of ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ in the game ${g_{\mathit{NL}-\mathit{II}}}$. We first compute the number of $|{L_{G}}|+|{L_{T}}|$. We have $|{L_{G}}|+|{L_{T}}|\leqslant 5+3{q_{O}}+2{q_{\mathit{SE}}}+4{q_{\mathit{PK}}}+4{q_{D}}+1=3{q_{O}}+2{q_{\mathit{SE}}}+4{q_{\mathit{PK}}}+4{q_{D}}+6\leqslant 4q$ by letting $6\leqslant {q_{O}}+2{q_{\mathit{SE}}}$. And we may obtain $Pr[FAC]\leqslant \frac{32{q^{2}}}{p}$, where the event $\mathit{FAC}$ denotes that ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ can find a collision in G or ${G_{T}}$. So, the success probability of ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ is
\[ P{r_{\mathit{NL}-\mathit{II}}}\leqslant Pr[\mathit{FAC}]+Pr[\overline{\mathit{FAC}}\wedge \mathit{GBC}]\leqslant \frac{32{q^{2}}}{p}+\frac{1}{2}\cdot \bigg(1-\frac{32{q^{2}}}{p}\bigg).\]
Hence, the adversary ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$’s advantage is
\[ Ad{v_{A}}\leqslant \bigg|\frac{32{q^{2}}}{p}+\frac{1}{2}\cdot \bigg(1-\frac{32{q^{2}}}{p}\bigg)-1/2\bigg|=\frac{16{q^{2}}}{p},\]
which is negligible if $q=\mathit{poly}(\log p)$. □Theorem 3.
In the generic bilinear group model, the proposed LR-CL-KE scheme Π is LR-CL-IND-CCA secure against Type I adversary (outsider) under the continual leakage model.
Proof.
In Theorem 1, we have shown that the non-leakage version ${\Pi _{\mathit{NL}}}$ of the proposed LR-CL-KE scheme is CL-IND-CCA secure against Type I adversary. Under the continual leakage model, an adversary is allowed to issue two additional leakage queries, Initial key extract leak query and Decrypt leak query. Let ${\mathcal{A}_{\mathit{LR}-I}}$ be a Type I adversary who may break the proposed LR-CL-KE scheme ${\Pi _{\mathit{LR}}}$. ${\mathcal{A}_{\mathit{LR}-I}}$ can adaptively issue the queries at most q times in total. In the following, we present a game ${g_{\mathit{LR}-I}}$ extended from the game ${g_{\mathit{NL}-I}}$ in Theorem 1 as follows. Game ${g_{\mathit{LR}-I}}$: In the game ${g_{\mathit{LR}-I}}$, there are four phases that include Setup, Phase 1, Challenge and Guess. Four phases are presented as follows:
-
– Setup: The phase is identical to that of the game ${g_{\mathit{NL}-I}}$.
-
– Phase 1: In this phase, the adversary ${\mathcal{A}_{\mathit{LR}-I}}$ can issue two additional leakage queries than the adversary ${\mathcal{A}_{\mathit{NL}-I}}$ in the game ${g_{\mathit{NL}-I}}$, namely, Initial key extract leak query and Decrypt leak query. In order to record the leakage information for two kinds of leak queries, we build four initial-empty lists ${L_{f,IE}}$, ${L_{h,\mathit{IE}}}$, ${L_{f,D}}$ and ${L_{h,D}}$ as follows:\[\begin{array}{l}\displaystyle {L_{f,\mathit{IE}}}=\big\{({f_{\mathit{IE},i}},\Lambda {f_{\mathit{IE},i}}),1\leqslant i\leqslant {q_{\mathit{IE}}}\big\},\\ {} \displaystyle {L_{h,\mathit{IE}}}=\big\{({h_{\mathit{IE},i}},\Lambda {h_{\mathit{IE},i}}),1\leqslant i\leqslant {q_{\mathit{IE}}}\big\},\\ {} \displaystyle {L_{f,D}}=\big\{({f_{D,j}},\Lambda {f_{D,j}}),1\leqslant j\leqslant {q_{D}}\big\},\\ {} \displaystyle {L_{h,D}}=\big\{({h_{D,j}},\Lambda {h_{D,j}}),1\leqslant j\leqslant {q_{D}}\big\}.\end{array}\]Two leakage functions ${f_{\mathit{IE},i}}$ and ${h_{\mathit{IE},i}}$ are, respectively, used to model the adversary’s leak ability for two sub-algorithms Extract-1 and Extract-2 of the i-th Initial key extract round. Also, two leakage functions ${f_{S,j}}$ and ${h_{S,j}}$ are, respectively, used to model the adversary’s leak ability for two sub-algorithms Decrypt-1 and Decrypt-2 of a user’s j-th Decrypt round. Moreover, the leakage information $\Lambda {f_{\mathit{IE},i}}$, $\Lambda {h_{\mathit{IE},i}}$, $\Lambda {f_{D,j}}$ and $\Lambda {h_{D,j}}$ denote the outputs of four leakage functions ${f_{\mathit{IE},i}}$ , ${h_{\mathit{IE},i}}$, ${f_{D,j}}$ and ${h_{D,j}}$, respectively. In the following, we describe two additional leakage queries as follows:
-
• Initial key extract leak query $({f_{\mathit{IE},i}},{h_{\mathit{IE},i}},i)$: For the i-th Initial key extract query, ${\mathcal{A}_{\mathit{LR}-I}}$ can issue the Initial key extract leak query only once by providing two leakage functions ${f_{\mathit{IE},i}}$ and ${h_{\mathit{IE},i}}$ such that $|{f_{\mathit{IE},i}}|\leqslant \lambda $ and $|{h_{\mathit{IE},i}}|\leqslant \lambda $. $\mathcal{B}$ computes and sends the leakage information $(\Lambda {f_{\mathit{IE},i}},\Lambda {h_{\mathit{IE},i}})$ to ${\mathcal{A}_{\mathit{LR}-I}}$, where $\Lambda {f_{\mathit{IE},i}}={f_{\mathit{IE},i}}({\mathit{SK}_{i-1,1}},{\gamma _{i}},{a_{i}})$ and $\Lambda {h_{\mathit{IE},i}}={h_{\mathit{IE},i}}({\mathit{SK}_{i-1,2}},{\mathit{TI}_{\mathit{IE}}},{a_{i}})$. Meanwhile, $\mathcal{B}$ records $({f_{\mathit{IE},i}},\Lambda {f_{\mathit{IE},i}})$ in the list ${L_{f,IE}}$ and $({h_{\mathit{IE},i}},\Lambda {h_{\mathit{IE},i}})$ in the list ${L_{h,\mathit{IE}}}$.
-
• Decrypt leak query $({f_{D,j}},{h_{D,j}},j)$: For the j-th Decrypt query, ${\mathcal{A}_{\mathit{LR}-I}}$ can issue the Decrypt leak query only once by providing two leakage functions ${f_{D,j}}$ and ${h_{D,j}}$ such that $|{f_{D,i}}|\leqslant \lambda $ and $|{h_{D,i}}|\leqslant \lambda $. $\mathcal{B}$ computes and sends the leakage information $(\Lambda {f_{D,j}},\Lambda {h_{D,j}})$ to ${\mathcal{A}_{\mathit{LR}-I}}$, where $\Lambda {f_{D,j}}={f_{D,j}}({\mathit{DID}_{j-1,1}},{b_{j}},{c_{j}})$ and $\Lambda {h_{D,j}}={h_{D,j}}({\mathit{DID}_{j-1,2}},{\mathit{TI}_{1,j}},{\mathit{TI}_{2,j}},{b_{j}},{c_{j}},{K_{1,j}},{K_{2,j}},{K_{j}})$. Meanwhile, $\mathcal{B}$ records $({f_{D,j}},\Lambda {f_{D,j}})$ in the list ${L_{f,D}}$ and (${h_{D,j}}$, $\Lambda {h_{D,j}}$) in the list ${L_{h,D}}$.
-
-
– Challenge: The adversary ${\mathcal{A}_{\mathit{LR}-I}}$ gives a target identity ID${^{\ast }}$ and a plaintext pair ($ms{g_{0}^{\ast }}$, $ms{g_{1}^{\ast }}$) to $\mathcal{B}$. This phase is identical to the Challenge phase in ${g_{\mathit{NL}-I}}$. Finally, $\mathcal{B}$ sends ${C^{\ast }}$ and $C{T^{\ast }}$ to ${\mathcal{A}_{\mathit{LR}-I}}$.
-
– Guess: The adversary ${\mathcal{A}_{\mathit{LR}-I}}$ outputs ${\beta ^{\prime }}\in \{0,1\}$. If ${\beta ^{\prime }}=\beta $, we say that the adversary ${\mathcal{A}_{\mathit{LR}-I}}$ wins the game ${g_{\mathit{LR}-I}}$.
In the game ${g_{\mathit{LR}-I}}$, ${\mathcal{A}_{\mathit{LR}-I}}$ has higher probability to cause collisions by making use of the leakage functions. Two leakage information $\Lambda {f_{\mathit{IE},i}}$ and $\Lambda {h_{\mathit{IE},i}}$, respectively, respresent the ouputs of two leakage functions ${f_{\mathit{IE},i}}$ and ${h_{\mathit{IE},i}}$ in the i-th Initial key extract query. By $\Lambda {f_{\mathit{IE},i}}$ and $\Lambda {h_{\mathit{IE},i}}$, the leaked information about $({\mathit{SK}_{i-1,1}},{\gamma _{i}},{a_{i}})$ and $({\mathit{SK}_{i-1,2}},{\mathit{TI}_{\mathit{IE}}},{a_{i}})$ are discussed below:
-
• ${\gamma _{i}}$: The value ${\gamma _{i}}$ is used to generate the initial key $({\mathit{DID}_{0}},\mathit{QID})$ for ${\mathit{ID}_{\mathit{IE},i}}$ in the Initial key extract query. By Definition 2 in Section 3.2, if ${\mathit{ID}_{\mathit{IE},i}}$ has been queried in the Initial key extract query, it is not allowed to be a target identity in the Challenge phase. Hence, the leakage of ${\gamma _{i}}$ is useless for ${\mathcal{A}_{\mathit{LR}-I}}$.
-
• $({\mathit{SK}_{i-1,1}},{\mathit{SK}_{i-1,2}})$: Since the system secret key $X={\mathit{SK}_{i-1,1}}\cdot {\mathit{SK}_{i-1,2}}$, obtaining some leakage information of ${\mathit{SK}_{i,1}}$ and ${\mathit{SK}_{i,2}}$ is contributive to learn partial information of X for ${\mathcal{A}_{\mathit{LR}-I}}$. Indeed, ${\mathcal{A}_{\mathit{LR}-I}}$ can learn at most 2λ bits of the system secret key X.
-
• ${a_{i}}$: The parameter ${a_{i}}$ is used to generate the next system secret key $({\mathit{SK}_{i,1}},{\mathit{SK}_{i,2}})$ from $({\mathit{SK}_{i-1,1}},{\mathit{SK}_{i-1,2}})$. Hence, ${\mathcal{A}_{\mathit{LR}-I}}$ may obtain at most λ bits of ${\mathit{SK}_{i,1}}$ and ${\mathit{SK}_{i,2}}$, respectively.
-
• ${\mathit{TI}_{\mathit{IE}}}$: The temporary information ${\mathit{TI}_{\mathit{IE}}}$ is only used to generate the initial key ${\mathit{DID}_{0}}$ for ${\mathit{ID}_{\mathit{IE},i}}$. ${\mathit{TI}_{\mathit{IE}}}$ is helpless in this game ${g_{\mathit{LR}-I}}$ since ${\mathit{ID}_{\mathit{IE},i}}$ is not allowed to be a target identity in the Challenge phase.
On the other hand, two leakage information $\Lambda {f_{D,j}}$ and $\Lambda {h_{D,j}}$, respectively, respresent the ouputs of two leakage functions ${f_{D,j}}$ and ${h_{D,j}}$ in the j-th Decrypt leak query. By $\Lambda {f_{D,j}}$ and $\Lambda {h_{D,j}}$, the leaked information about $({\mathit{DID}_{j-1,1}},{b_{j}},{c_{j}})$ and $({\mathit{DID}_{j-1,2}},{\mathit{TI}_{1}},j,{\mathit{TI}_{2}},j,{b_{j}},{c_{j}},{K_{1,j}},{K_{2,j}},{K_{j}})$ are discussed below:
-
• $({\mathit{DID}_{j-1,1}},{\mathit{DID}_{j-1,2}})$: Since the user’s first initial key ${\mathit{DID}_{0}}={\mathit{DID}_{j-1,1}},{\mathit{DID}_{j-1,2}}$, obtaining some leakage information of ${\mathit{DID}_{j-1,1}}$ and ${\mathit{DID}_{j-1,2}}$ is contributive to learn partial information of ${\mathit{DID}_{0}}$ for ${\mathcal{A}_{\mathit{LR}-I}}$. Indeed, ${\mathcal{A}_{\mathit{LR}-I}}$ can learn at most 2λ bits of the user’s initial key ${\mathit{DID}_{0}}$.
-
• $({\mathit{TI}_{1,j}},{\mathit{TI}_{2,j}})$: The temporary information ${\mathit{TI}_{1,j}}$ and ${\mathit{TI}_{2,j}}$ are used to compute ${K_{1,j}}$ and ${K_{2,j}}$, respectively. Since each encryption key ${K_{j}}={K_{1,j}}\oplus {K_{2,j}}$ is independent with each other, obtaining ${\mathit{TI}_{1,j}}$ and ${\mathit{TI}_{2,j}}$ is helpless in the Guess phase.
-
• ${b_{j}}$: The parameter ${b_{j}}$ is used to compute the user’s initial key $({\mathit{DID}_{j,1}},{\mathit{DID}_{j,2}})$ from $({\mathit{DID}_{j-1,1}},{\mathit{DID}_{j-1,2}})$. Therefore, ${\mathcal{A}_{\mathit{LR}-I}}$ can learn at most λ bits of ${\mathit{DID}_{j,1}}$ and ${\mathit{DID}_{j,2}}$, respectively.
-
• ${c_{j}}$: The parameter ${c_{j}}$ is used to compute the user secret key $({\mathit{SID}_{j,1}},{\mathit{SID}_{j,2}})$ from $({\mathit{SID}_{j-1,1}},{\mathit{SID}_{j-1,2}})$. Therefore, ${\mathcal{A}_{\mathit{LR}-I}}$ can learn at most λ bits of ${\mathit{SID}_{j,1}}$ and ${\mathit{SID}_{j,2}}$, respectively.
-
• $({K_{1,j}},{K_{2,j}},{K_{j}})$: For the j-th Decrypt query, ${\mathcal{A}_{\mathit{LR}-I}}$ can use the leakage function ${h_{D,j}}$ to obtain the leakage information about $({K_{1,j}},{K_{2,j}},{K_{j}})$ once for totally at most λ bits. Since ${K_{1,j}}$ and ${K_{2,j}}$ can only be used to generate ${K_{j}}$, adversary ${\mathcal{A}_{\mathit{LR}-I}}$ can learn at most λ bits information about ${K_{j}}$ in the game ${g_{L-IR}}$.
Now, let us discuss the success probability $P{r_{\mathit{LR}-I}}$ that ${\mathcal{A}_{\mathit{LR}-I}}$ wins the game ${g_{\mathit{LR}-I}}$. Since ${\mathcal{A}_{\mathit{LR}-I}}$ can get the secret key of any entity, ${\mathcal{A}_{\mathit{LR}-I}}$ always outputs a correct ${\beta ^{\prime }}$ when she/he gets the target user’s initial key ${\mathit{DID}_{0}}$ or the system secret key X. Firstly, we define three events of $P{r_{\mathit{LR}-I}}$ as follows.
-
(1) The event $\mathit{EI}$ denotes that the adversary ${\mathcal{A}_{\mathit{LR}-I}}$ may obtain ${\mathit{DID}_{0}}$ completely from the leakage information $\Lambda {f_{D,j}}$ and $\Lambda {h_{D,j}}$.
-
(2) The event $\mathit{ES}$ denotes that the adversary ${\mathcal{A}_{\mathit{LR}-I}}$ may obtain the system secret key X completely from the leakage information $\Lambda {f_{\mathit{IE},i}}$ and $\Lambda {h_{\mathit{IE},i}}$.
-
(3) The event $\mathit{EC}$ denotes that the adversary ${\mathcal{A}_{\mathit{LR}-I}}$ may output a correct ${\beta ^{\prime }}$.
In addition, let $\overline{\mathit{ES}}$ and $\overline{\mathit{EI}}$, respectively, denote the complement events of $\mathit{ES}$ and $\mathit{EI}$. The success probability $P{r_{\mathit{LR}-I}}$ that the adversary ${\mathcal{A}_{\mathit{LR}-I}}$ wins the game ${g_{\mathit{LR}-I}}$ is bounded as follows.
\[\begin{aligned}{}P{r_{\mathit{LR}-I}}=& Pr[\mathit{EC}]\\ {} =& Pr[\mathit{EC}\wedge \mathit{ES}]+Pr[\mathit{EC}\wedge \overline{\mathit{ES}}]\\ {} =& Pr[\mathit{EC}\wedge \mathit{ES}]+Pr[\mathit{EC}\wedge \overline{\mathit{ES}}\wedge \mathit{EI}]+Pr[\mathit{EC}\wedge \overline{\mathit{ES}}\wedge \overline{\mathit{EI}}]\\ {} =& Pr[\mathit{EC}\wedge \mathit{ES}]+Pr[\mathit{EC}\wedge \overline{\mathit{ES}}\wedge \mathit{EI}]+Pr[\mathit{EC}|\overline{\mathit{ES}}\wedge \overline{\mathit{EI}}]\cdot (Pr[\overline{\mathit{ES}}\wedge \overline{\mathit{EI}}].\end{aligned}\]
Since $Pr[\mathit{EC}\wedge \mathit{ES}]\leqslant Pr[\mathit{ES}]$ and $Pr[\mathit{EC}\wedge \overline{\mathit{ES}}\wedge \mathit{EI}]\leqslant Pr[\overline{\mathit{ES}}\wedge \mathit{EI}]$, we obtain
\[ P{r_{\mathit{LR}-I}}\leqslant Pr[\mathit{ES}]+Pr[\overline{\mathit{ES}}\wedge \mathit{EI}]+Pr[\mathit{OBC}|\overline{\mathit{ES}}\wedge \overline{\mathit{EI}}]\cdot Pr[\overline{\mathit{ES}}\wedge \overline{\mathit{EI}}].\]
Let us focus on $Pr[\mathit{EC}|\overline{\mathit{ES}}\wedge \overline{\mathit{EI}}]$. Under the condition $\overline{\mathit{ES}}\wedge \overline{\mathit{EI}}$, ${\mathcal{A}_{\mathit{LR}-I}}$ can’t obtain the useful information to output ${\beta ^{\prime }}$ correctly. Hence, $Pr[\mathit{EC}|\overline{\mathit{ES}}\wedge \overline{\mathit{EI}}]$ is $\frac{1}{2}$ on average. Thus, we obtain
\[ Pr[\mathit{EC}|\overline{\mathit{ES}}\wedge \overline{\mathit{EI}}]\cdot Pr[\overline{\mathit{ES}}\wedge \overline{\mathit{EI}}]=(1/2)\big(1-Pr[\mathit{ES}]-Pr[\overline{\mathit{ES}}\wedge \mathit{EI}]\big).\]
Hence, we have
\[ P{r_{\mathit{LR}-I}}\leqslant 1/2+(1/2)\big(Pr[\mathit{ES}]+Pr[\overline{\mathit{ES}}\wedge \mathit{EI}]\big).\]
Lemmas 3 and 4 below offer upper bounds for $Pr[\mathit{ES}]$ and $Pr[\overline{\mathit{ES}}\wedge \mathit{EI}]$, respectively. By assuming these results, the adversary ${\mathcal{A}_{\mathit{LR}-I}}$’s advantage is
\[\begin{aligned}{}Ad{v_{A}}\leqslant & \bigg|P{r_{\mathit{LR}-I}}-\frac{1}{2}\bigg|=\bigg|\frac{1}{2}\big(Pr[ES]+Pr[\overline{\mathit{ES}}\wedge EI]\big)\bigg|\\ {} =& \bigg|\frac{1}{2}\bigg(O\bigg(\frac{{q^{2}}}{p}\cdot {2^{2\lambda }}\bigg)+O\bigg(\frac{{q^{2}}}{p}\cdot {2^{2\lambda }}\bigg)\bigg)\bigg|\leqslant O\bigg(\frac{{q^{2}}}{p}\cdot {2^{2\lambda }}\bigg).\end{aligned}\]
Hence, the advantage of the adversary ${\mathcal{A}_{\mathit{LR}-I}}$ breaking our LR-CL-KE scheme is $O(\frac{{q^{2}}}{p}\cdot {2^{2\lambda }})$. By Corollary 1, if $\lambda \ll \frac{\log (p)}{2}$, we say that the proposed scheme ${\Pi _{\mathit{LR}}}$ is LR-CL-IND-CCA secure against Type I adversary (outsider) under the continual leakage model. □
Proof.
In the Initial key extract algorithm of our LR-CL-KE scheme, the initial key of a user is a signature on her/his identity ID, which is generated by the signature scheme proposed by Galindo and Virek (2013). Hence, the probability $Pr[\mathit{ES}]$ is then bounded by the probability that the adversary can compute the secret key in Galindo and Vivek’s scheme. By applying the Lemma 5 in Galindo and Virek (2013), we have $Pr[\mathit{ES}]\leqslant O(\frac{{q^{2}}}{p}\cdot {2^{2\lambda }})$. □
Proof.
Under the condition $\overline{\mathit{ES}}$, ${\mathcal{A}_{\mathit{LR}-I}}$ can’t obtain the system secret key X. We focus on the probability that ${\mathcal{A}_{\mathit{LR}-I}}$ can obtain ${\mathit{DID}_{0}}$ completely under the condition $\overline{\mathit{ES}}$. As described earlier, no useful information of ${\mathit{DID}_{0}}$ can be obtained from the leakage information $\Lambda {f_{\mathit{IE},i}}$ and $\Lambda {h_{\mathit{IE},i}}$ in the Initial key extract leak query. However, ${\mathcal{A}_{\mathit{LR}-I}}$ may obtain some useful information of ${\mathit{DID}_{0}}$ by the Decrypt leak query. In such a case, $Pr[\overline{\mathit{ES}}\wedge EI]$ denotes that ${\mathcal{A}_{\mathit{LR}-I}}$ can obtain the user’s initial key without using the leakage functions ${f_{\mathit{IE},i}}$ and ${h_{\mathit{IE},i}}$. As described earlier, the useful information to generate the user’s initial key ${\mathit{DID}_{0}}$ from the leakage functions ${f_{D,j}}$ and ${h_{D,j}}$ are $({\mathit{DID}_{j-1,1}},{\mathit{DID}_{j-1,2}})$ and ${b_{j}}$. In our scheme, the user’s initial key is updated in the beginning of two sub-algorithms Decrypt-1 and Decrypt-2. Hence, the adversary can learn at most $2\lambda $ bits about ${\mathit{DID}_{0}}$. Considering the advantage that ${\mathcal{A}_{\mathit{NL}-I}}$ obtains in Theorem 1, the probability that the adversary ${\mathcal{A}_{\mathit{NL}-I}}$ can find a collision is $Pr[\mathit{FAC}]\leqslant \frac{72{q^{2}}}{p}$. By applying Lemma 2, we have $Pr[\overline{\mathit{ES}}\wedge \mathit{EI}]$ is bounded by $\frac{72{q^{2}}}{p}\cdot {2^{2\lambda }}$. Hence, we obtain $Pr[\overline{\mathit{ES}}\wedge \mathit{EI}]\leqslant O(\frac{{q^{2}}}{p}\cdot {2^{2\lambda }})$. □
Theorem 4.
In the generic bilinear group model, the proposed LR-CL-KE scheme Π is LR-CL-IND-CCA secure against Type II adversary (honest-but-curious KGC) under the continual leakage model.
Proof.
In Theorem 2, we have shown that the non-leakage version ${\Pi _{\mathit{NL}}}$ of the proposed LR-CL-KE scheme is CL-IND-CCA secure against Type II adversary. Under the continual leakage model, an adversary is allowed to issue two additional leakage queries, Initial key extract leak query and Decrypt leak query. Let ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ be a Type II adversary who may break the proposed LR-CL-KE scheme ${\Pi _{\mathit{LR}}}$. ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ can adaptively issue the queries at most q times in total. In the following, we present a game ${g_{\mathit{LR}-\mathit{II}}}$ extended from the game ${g_{\mathit{NL}-\mathit{II}}}$ in Theorem 2 as follows. Game ${g_{\mathit{LR}-\mathit{II}}}$. In the game ${g_{\mathit{LR}-\mathit{II}}}$, there are four phases, Setup, Phase 1, Challenge and Guess.
-
– Setup: The phase is identical to that of ${g_{\mathit{NL}-\mathit{II}}}$.
-
– Phase 1: In this phase, ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ can issue an extra leakage query (i.e. Decrypt leak query) than the adversary ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ in the game ${g_{\mathit{NL}-\mathit{II}}}$. In order to record the leakage information for the Decrypt leak query, we build two initial-empty lists ${L_{f,D}}$ and ${L_{h,D}}$, which are identical to those in the game ${g_{\mathit{LR}-I}}$.
-
– Challenge: The adversary ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ gives a target identity ID${^{\ast }}$ and a plaintext pair ($ms{g_{0}^{\ast }}$, $ms{g_{1}^{\ast }}$) to $\mathcal{B}$. This phase is identical to the Challenge phase in ${g_{\mathit{NL}-\mathit{II}}}$. Finally, $\mathcal{B}$ sends ${C^{\ast }}$ and $CT$* to ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$.
-
– Guess: The adversary ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ outputs ${\beta ^{\prime }}\in \{0,1\}$. If ${\beta ^{\prime }}=\beta $, we say that the adversary ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ wins the game ${g_{\mathit{LR}-\mathit{II}}}$.
In ${g_{\mathit{LR}-\mathit{II}}}$, ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ has higher probability to cause collisions by making use of the leakage functions. In the j-th Decrypt leak query, two leakage information $\Lambda {f_{D,j}}$ and $\Lambda {h_{D,j}}$, respectively, respresent the ouputs of two leakage functions ${f_{D,j}}$ and ${h_{D,j}}$. By $\Lambda {f_{D,j}}$ and $\Lambda {h_{D,j}}$, the adversary ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ can obtain the partial information of both $({\mathit{SID}_{j-1,1}},{b_{j}},{c_{j}})$ and $({\mathit{SID}_{j-1,2}},{\mathit{TI}_{1}},i,{\mathit{TI}_{2}},i,{b_{j}},{c_{j}},{K_{1,i}},{K_{2,i}},{K_{i}})$. The discussions on the partial leakage information of (${\mathit{TI}_{1,i}}$, ${\mathit{TI}_{2,i}}$, ${b_{j}}$, ${c_{j}}$, ${K_{1,i}}$, ${K_{2,i}}$, ${K_{i}}$) are the same with those in Theorem 3. In addition, the leaked information about $({\mathit{SID}_{j-1,1}},{\mathit{SID}_{j-1,2}})$ is discussed below:
-
• $({\mathit{SID}_{j-1,1}},{\mathit{SID}_{j-1,2}})$: Since the user’s secret key ${\mathit{SID}_{0}}={\mathit{SID}_{j-1,1}}\cdot {\mathit{SID}_{j-1,2}}$, obtaining some leakage information of ${\mathit{SID}_{j-1,1}}$ and ${\mathit{SID}_{j-1,2}}$ is contributive to learn the partial information of ${\mathit{SID}_{0}}$ for ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$. Indeed, ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ can learn at most 2λ bits of the user’s secret key ${\mathit{SID}_{0}}$.
Now, let us discuss the success probability $P{r_{\mathit{LR}-\mathit{II}}}$ that the adversary ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ wins the game ${g_{\mathit{LR}-\mathit{II}}}$. Since ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ holds the system secret key X, ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ can obtain each user’s initial key ${\mathit{DID}_{0}}$. If ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ can obtain the user’s secret key $\mathit{SID}$, ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ always outputs a correct ${\beta ^{\prime }}$. Here we define two events of $P{r_{\mathit{LR}-\mathit{II}}}$ as follows.
In addition, the event $\overline{EU}$ is the complement event of $\mathit{EU}$. The success probability $P{r_{\mathit{LR}-\mathit{II}}}$ that the adversary ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ wins the game ${g_{\mathit{LR}-\mathit{II}}}$ is bounded as follows.
-
(1) The event $\mathit{EU}$ denotes that the user’s secret key ${\mathit{SID}_{0}}$ can be obtained completely by ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ from the leakage information $\Lambda {f_{D,j}}$ and $\Lambda {h_{D,j}}$.
-
(2) The event $\mathit{EC}$ denotes that ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ can guess ${\beta ^{\prime }}$ correctly.
\[\begin{aligned}{}P{r_{\mathit{LR}-\mathit{II}}}=& Pr[\mathit{EC}]=Pr[\mathit{EC}\wedge \mathit{EU}]+Pr[\mathit{EC}\wedge \overline{\mathit{EU}}]\\ {} =& Pr[\mathit{EC}\wedge \mathit{EU}]+Pr[\mathit{EC}|\overline{\mathit{EU}}]\cdot Pr[\overline{\mathit{EU}}].\end{aligned}\]
Since $Pr[\mathit{EC}\wedge \mathit{EU}]\leqslant Pr[\mathit{EU}]$, we have
Let us focus on $Pr[\mathit{EC}|\overline{\mathit{EU}}]$. Under the condition $\overline{\mathit{EU}}$, ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ can’t obtain useful information to output ${\beta ^{\prime }}$ correctly. Hence, $Pr[\mathit{EC}|\overline{\mathit{EU}}]$ is equal to $\frac{1}{2}$ plus the advantage $O(\frac{{q^{2}}}{p})$ of the adversary ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ in Theorem 2. Thus, we obtain
\[ Pr[\mathit{EC}|\overline{\mathit{EU}}]\cdot Pr[\overline{\mathit{EU}}]=\frac{1}{2}\big(1-Pr[\mathit{EC}\wedge \mathit{EU}]\big).\]
Hence, we have $P{r_{\mathit{LR}-I}}\leqslant \frac{1}{2}+\frac{1}{2}Pr[\mathit{EU}]$. By assuming Lemma 5 below, we obtain an upper bound for ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$’s advantage as
\[ Ad{v_{A}}\leqslant \bigg|P{r_{\mathit{LR}-I}}-\frac{1}{2}\bigg|=\bigg|\frac{1}{2}Pr[\mathit{EU}]\bigg|\leqslant O\bigg(\frac{{q^{2}}}{p}{2^{2\lambda }}\bigg).\]
Thus, the advantage of the adversary ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ breaking our LR-CL-KE scheme is $O(\frac{1}{p}{2^{2\lambda }})$. By Corollary 1, if $\lambda \ll \frac{\log (p)}{2}$, we say that the proposed scheme ${\Pi _{\mathit{LR}}}$ is LR-CL-IND-CCA secure against Type II adversary (honest-but-curious KGC) under the continual leakage model. □Proof.
Considering the advantage that ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ obtains in Theorem 2, the probability that ${\mathcal{A}_{\mathit{NL}-\mathit{II}}}$ can find a collision is $Pr[\mathit{FAC}]\leqslant \frac{32{q^{2}}}{p}$. Since ${\mathcal{A}_{\mathit{LR}-\mathit{II}}}$ can learn at most $2\lambda $ bits information for the user current secret key in the Decrypt leak query, by applying Lemma 2, we have Pr[EU] is bounded by $\frac{32{q^{2}}}{p}{2^{2\lambda }}$. Hence, we obtain $Pr[\mathit{EU}]\leqslant O(\frac{{q^{2}}}{p}){2^{2\lambda }})$. □
6 Performance Analysis
In this section, we compare the proposed LR-CL-KE scheme with the leakage-resilient certificateless public key encryption (LR-CL-PKE) scheme proposed by Xiong et al. (2013). In the following, we define several notations to analyse the computational costs.
When compared to ${T_{e}}$ and ${T_{p}}$, the multiplication operation in the multiplicative group G or ${G_{T}}$ is trivial and negligible (Scott, 2011). Table 1 lists the comparisons between the proposed LR-CL-KE scheme and Xiong et al.’s LR-CL-PKE scheme (Xiong et al., 2013) in terms of the size of encryption cost, decryption cost, security model, security property and leakage model. Note that a user’s private key in Xiong et al.’s LR-CL-PKE scheme is a vector with n elements. For the costs of encryption and decryption, Xiong et al.’s scheme requires $(n+4){T_{e}}$ and $(n+2){T_{p}}$, respectively. In the proposed LR-CL-KE scheme, $4{T_{e}}+{T_{p}}$ and $4{T_{e}}+4{T_{p}}$ are required for encryption and decryption, respectively.
For the security model and security property, Xiong et al. employed the dual system encryption technique (Lewko et al., 2011) to define semi-functional (SF) keys and ciphertexts. In the standard model, they then proved that their scheme possesses the LR-CCA1 security under the bounded leakage model. As mentioned earlier, we formally proved that, in the GBG model, our LR-CL-KE scheme is LR-CCA1 secure against both Type I and Type II adversaries under continual leakage model.
Table 1
Comparisons between our LR-CL-KE scheme and the previously proposed schemes.
| The LR-CL-PKE scheme (Xiong et al., 2013) | The proposed LR-CL-KE scheme | |
| Encryption cost | $(n+4){T_{e}}$ | $4{T_{e}}+4{T_{p}}$ |
| Decryption cost | $(n+2){T_{p}}$ | $4{T_{e}}+4{T_{p}}$ |
| Security model | Standard model (Dual system) | GBG model |
| Security property | LR-CCA1 | LR-CCA1 |
| Leakage model | Bounded leakage | Continue leakage |
7 Conclusions and Future Work
The first LR-CL-KE scheme under the continual leakage model was proposed in the article. We defined a new adversary model for LR-CL-KE schemes under the continual leakage model. The adversary model also consists of two types of adversaries. Type I adversary can obtain partial information of a user’s initial key in the Decrypt phase and KGC’s system secret key in the Initial key extract phase. Type II adversary can obtain partial information of a user’s secret key in the Decrypt phase since she/he already knows the initial key of any user. In the GBG model, we formally proved that our LR-CL-KE scheme is semantically secure against chosen ciphertext attacks for both Type I and Type II adversaries. It is worth mentioning that the proposed LR-CL-KE scheme achieves only the LR-CCA1 security, but not the LR-CCA2 security. Indeed, it is an interesting and open problem to propose a LR-CCA2 secure LR-CL-PKE or LR-CL-KE scheme under the continual leakage model. Furthermore, up to date, there does not exist leakage-resilient RSA-based certificateless encryption/signature schemes under continual leakage model. Indeed, it is also an interesting issue to design efficient leakage-resilient RSA-based certificateless encryption/signature schemes.
