1 Introduction
To eliminate the management of both public keys and their associated certificates in the traditional public-key systems (PKS), an identity (ID)-based public-key system (IDPKS) was proposed (Boneh and Franklin, 2001). In an IDPKS setting, a private key generator (PKG) is responsible to generate all participants’ secret keys. Hence, the IDPKS setting has an inborn disadvantage, namely, the key escrow problem in the sense that the PKG can decrypt any ciphertexts of all participants and sign any messages on behalf of all participants. To resolve both certificate management and key escrow problems, Al-Riyami and Paterson (2003) proposed the certificateless public-key system (CLPKS). In which, there are two kinds of participants, namely, a key generation center (KGC) and users. The KGC is responsible to generate all users’ identity secret keys. In the meantime, each user chooses a personal secret key and sets the associated public key. Therefore, each user has two secret keys, namely, identity secret key and personal secret key. Obviously, the CLPKS setting can solve both the key escrow and certificate management problems.
Under some situations, a user’s ID or public key has to be revoked before expiration. Although the certificate revocation list (CRL) (Housley et al., 2002) is a well-known revocation method, it is unsuitable for IDPKS and CLPKS settings because no certificate is required. Therefore, an IDPKS or CLPKS setting must provide a revocation mechanism to revoke compromised users. Tseng and Tsai (2012) has presented a revocable IDPKS setting. By this revocable concept of Tseng and Tsai, revocable CLPKS (RCLPKS) settings (Shen et al., 2014; Tsai and Tseng, 2015; Hung et al., 2016) were presented to address the revocation issue and the key generation center (KGC) is also responsible to run this revocation functionality. Furthermore, a RCLPKS setting with an outsourced revocation authority (ORA), named RCLPKS-ORA setting (Tsai et al., 2015; Du et al., 2018), was presented to employ the ORA to alleviate the KGC’s computational burden.
Typically, all public-key systems mentioned above have a nature assumption that secret (or private) keys are completely hidden to adversaries. However, a new type of attacks, called “side-channel attacks”, has threatened these existing public-key systems. An adversary may employ side-channel attacks, such as power analysis (Kocher et al., 1999) and timing attack (Kocher, 1996; Brumley and Boneh, 2005) to continually obtain partial ingredients of a participant’s secret (or private) keys so that the associated cryptographic schemes/protocols could be broken. Ways to withstand side-channel attacks on cryptographic schemes/protocols have received significant attention of researchers. Fortunately, leakage-resilient cryptography offers a solution to resist such attacks. Up to date, little research addresses leakage-resilient certificateless public-key systems. In this paper, our aim is to propose the first leakage-resilient revocable certificateless encryption (LR-RCLE) scheme with an outsourced revocation authority (ORA), termed LR-RCLE-ORA scheme.
1.1 Related Work
In leakage-resilient cryptography, a cryptographic scheme/protocol remains secure even though partial ingredients of a participant’s secret (or private) keys in this scheme/protocol is leaked to adversaries. For leakage property, there are two leakage models, namely, bounded and continual. In the bounded leakage model (Katz and Vaikuntanathan, 2009; Alwen et al., 2009), total leaked bit sizes of secret keys for a cryptographic scheme/protocol are limited during its life cycle. Obviously, this limitation is impractical. In contrast, in the continual leakage model, adversaries may continually get leaked information of secret keys for each invocation of cryptographic scheme/protocol. Indeed, the continual leakage model is more accredited (Galindo and Virek, 2013; Wu et al., 2019, 2020; Tseng et al., 2020; Hsieh et al., 2020; Tsai et al., 2021) and it consists of four properties as follows:
-
• Only computation leakage: An adversary can extract partial ingredients of secret keys involved in the current computation round.
-
• Bounded leakage of single computational algorithm: A cryptographic scheme/protocol typically includes several computation rounds. In each computation round, an adversary can extract partial ingredients of secret keys. Namely, an adversary can select a leakage function f for each computation round and obtain the leaked information $f(\textit{SK})$, where $\textit{SK}$ denotes the involved secret keys and $f(\textit{SK})$ is bounded to λ bits.
-
• Independent leakage: Any two leaked partial ingredients of secret keys in various computation rounds are mutually independent. For achieving this property, a secret key must be updated before (or after) running each computation round.
-
• Overall unbounded leakage: The total amount of leaked information is overall unbounded. Indeed, by the independent leakage property, the total leakage amount of secret keys is unlimited.
According to the usage of secret key or public key, there are two kinds of encryption schemes, namely, symmetric encryption and asymmetric encryption based on various public-key systems. For a symmetric encryption scheme, a pre-shared secret key between a sender and a receiver is used to encrypt and decrypt procedures. A symmetric encryption scheme is typically employed to encrypt a large size of message and have high-throughput efficiency. On the contrary, for an asymmetric encryption scheme, a sender uses a designated receiver’s public key to encrypt message while the receiver uses her/his private key to decrypt it. Generally, an asymmetric encryption scheme is employed to encrypt a short size of message (e.g. a session key) or authenticate identity/message so that the throughput of encryption/decryption procedure is not their priority. Also, for considering leakage-resilient property, there are two kinds of leakage-resilient encryption schemes, namely, leakage-resilient symmetric encryption and leakage-resilient asymmetric encryption based on various public-key systems.
Here, let’s introduce the evolution of leakage-resilient symmetric encryption schemes. The first generic construction of leakage-resilient symmetric encryption based on minimal assumptions has been proposed by Hazay et al. (2013). However, the efficiency of Hazay et al.’s scheme is not good so that Abdalla et al. (2013) improved their scheme to propose an efficient leakage-resilient symmetric encryption scheme using the AES block cipher without constructing a leakage resilient block cipher. Recently, for enhancing the efficiency, several leakage-resilient authenticated symmetric encryption schemes based on hardware AES coprocessors (Unterstein et al., 2020; Bronchain et al., 2021) have been proposed.
In the following, several leakage-resilient asymmetric encryption (or key encapsulation) schemes based on traditional PKS, IDPKS and CLPKS settings are reviewed. Based on a traditional PKS setting, the first leakage-resilient encryption (LRE) scheme was presented by Akavia et al. (2009). Subsequently, several LRE schemes (Naor and Segev, 2009, 2012; Liu et al., 2013; Li et al., 2013) were proposed to improve security and performance of Akavia et al.’s scheme. However, all these LRE schemes above are secure only in the bounded leakage model. Moreover, Kiltz and Pietrzak (2010) presented the first LRE scheme under the continual leakage model. Furthermore, Galindo et al. (2016) presented an efficient ElGamal-like LRE scheme under the continual leakage model. Based on an IDPKS setting, Brakerski et al. (2010) proposed the first leakage-resilient ID-based encryption (LR-IBE) scheme under the continual leakage model. Subsequently, several LR-IBE schemes (Yuen et al., 2012; Li et al., 2016) were also proposed to improve security and performance of Brakerski et al.’s scheme.
Up to date, little research addresses leakage-resilient certificateless public-key systems. In 2013, the first leakage-resilient certificateless encryption (LR-CLE) scheme was presented by Xiong et al. (2013). To improve the security and performance of Xiong et al.’s scheme, Zhou et al. (2016) proposed a new leakage-resilient certificateless signcryption scheme. However, both Zhou et al.’s and Xiong et al.’s schemes are secure only under the bounded leakage model. In 2018, Wu et al. (2018) proposed the first LR-CLE scheme under the continual leakage model. In the generic bilinear group (GBG) model (Boneh et al.), Wu et al.’s LR-CLE scheme is semantically secure against chosen ciphertext attacks for two adversaries, namely, outsider and honest-but-curious KGC.
1.2 Contribution and Organization
As mentioned earlier, a RCLPKS setting with an outsourced revocation authority (ORA), named RCLPKS-ORA setting, can revoke compromised users and alleviate the KGC’s revocation computation burden. However, up to date, there are no leakage-resilient revocable certificateless encryption (LR-RCLE) or leakage-resilient revocable certificateless key encapsulation scheme. In this article, the first leakage-resilient revocable certificateless encryption scheme with an ORA, termed LR-RCLE-ORA scheme, is proposed. By extending the adversary models of the revocable certificateless encryption (RCLE) (Tsai and Tseng, 2015) and leakage resilience certificateless encryption (LR-CLE) schemes (Xiong et al., 2013; Wu et al., 2018), a new adversary model of LR-RCLE-ORA schemes is presented. Under this new adversary model, the proposed scheme is formally shown to be semantically secure against three types of adversaries, namely, outsider, revoked user and honest-but-curious KGC. Finally, comparisons with previously proposed schemes (Tsai and Tseng, 2015; Xiong et al., 2013; Wu et al., 2018), the proposed scheme has the following merits. (1) It can resist side-channel attacks and has leakage resilience properties. (2) The revocation functionality is outsourced to an ORA to alleviate the computational load of the KGC. (3) It permits adversaries to continually extract partial ingredient of secret keys and offers the overall unbounded leakage property.
The remaining paper is organized as below. Several preliminaries are presented in Section 2. In Section 3, the syntax (framework) and adversary model (security notions) of LR-RCLE-ORA schemes are defined. The proposed LR-RCLE-ORA scheme is presented in Section 4. In Section 5, the security of the proposed scheme is formally established. The comparisons of the proposed scheme with some RCLE and LR-CLE schemes are given in Section 6. Conclusions are drawn in Section 7.
2 Preliminaries
2.1 Bilinear Groups
Let ${G_{1}}$ be an additive group of a prime order p and Q be a generator of ${G_{1}}$. Let ${G_{2}}$ be a multiplicative group of the same order p. A bilinear admissible pairing $\hat{e}:{G_{1}}\times {G_{1}}\to {G_{2}}$ possesses the following properties:
2.2 Generic Bilinear Group Model
In 2005, Boneh et al. (2005) defined the generic bilinear group (GBG) model, which is a technique of proving the security of some cryptographic schemes. In the GBG model, the discrete logarithm problems on groups of a large order would be solved if collisions of the groups were found by adversaries after finishing the security games of the cryptographic scheme.
In the GBG model, as mentioned in Section 2.1, let $\{{G_{1}},{G_{2}},p,Q,\hat{e}\}$ be the bilinear group parameters and let each element in two groups ${G_{1}}$ and ${G_{2}}$ be represented by distinct bit-strings. In such a case, a random injective mapping ${\Phi _{1}}:{Z_{p}^{\ast }}\to \xi {G_{1}}$ is used to encode all elements of ${G_{1}}$, where $\xi {G_{1}}$ denotes the set of the encoded bit-strings of ${G_{1}}$. By the same reason, the other random injective mapping ${\Phi _{2}}:{Z_{p}^{\ast }}\to \xi {G_{2}}$ is employed to encode all elements of ${G_{2}}$, where $\xi {G_{2}}$ denotes the set of the encoded bit-strings of ${G_{2}}$. Two sets $\xi {G_{1}}$ and $\xi {G_{2}}$ satisfy $|\xi {G_{1}}|=|\xi {G_{2}}|=p$ and $\xi {G_{1}}\cap \xi {G_{2}}=\phi $. In addition, let three operations ${O_{1}}$, ${O_{2}}$ and ${O_{p}}$, respectively, denote the addition of ${G_{1}}$, the multiplication of ${G_{2}}$ and the bilinear pairing $\hat{e}$. To perform these group operations, an adversary must request the associated operations (oracles) ${O_{1}}$, ${O_{2}}$ and ${O_{p}}$ which are defined as below:
Note that $r,s\in {Z_{p}^{\ast }}$, $Q={\Phi _{1}}(1)$ and $\hat{e}(Q,Q)={\Phi _{2}}(1)$.
-
– ${O_{1}}({\Phi _{1}}(r),{\Phi _{1}}(s))\to {\Phi _{1}}(r+s\hspace{2.5pt}\text{mod}\hspace{2.5pt}p)$;
-
– ${O_{2}}({\Phi _{2}}(r),{\Phi _{2}}(s))\to {\Phi _{2}}(r+s\hspace{2.5pt}\text{mod}\hspace{2.5pt}p)$;
-
– ${O_{p}}({\Phi _{1}}(r),{\Phi _{1}}(s))\to {\Phi _{2}}(rs\hspace{2.5pt}\text{mod}\hspace{2.5pt}p)$.
After finishing the security games in the GBG model of a cryptographic scheme, the discrete logarithm problem on ${G_{1}}$ or ${G_{2}}$ would be resolved if adversaries discovered a collision on ${G_{1}}$ or ${G_{2}}$. The discrete logarithm problem and assumption are presented as below:
-
– Discrete logarithm (DL) problem and assumption: Let $\{{G_{1}},{G_{2}},p,Q,\hat{e}\}$ be the bilinear group parameters. Given a group element $r\cdot Q\in {G_{1}}$ or $\hat{e}{(Q,Q)^{r}}\in {G_{2}}$ for unknown $r\in {Z_{p}^{\ast }}$, the DL problem is to find r from $r\cdot Q$ or $\hat{e}{(Q,Q)^{r}}$. The DL assumption is that no polynomial time algorithm A with non-negligible probability can discover r.
2.3 The Security Measure of Leaked Information
To measure the security influence incurred by leaked information of secret keys (finite random variables) involved in a cryptographic scheme, we first introduce the concept of entropy. The entropy of a random variable is employed to denote its uncertainty for guessing this random variable. Let R be a finite random variable and let $\text{Pr}[R=r]$ denote the associated probability of $R=r$. In the following, we present two kinds of min-entropies:
In 2008, Dodis et al. (2008) inferred the following consequence related to the security influence incurred by leaked information of a secret key (finite random variable).
Lemma 1.
Let λ denote the maximal bit-length of leaked information of a secret key (a finite random variable) R. Let $f:R\to {\{0,1\}^{\lambda }}$ denote the associated leakage function of R. Under the condition $f(R)$, the average conditional min-entropy on R is ${\widetilde{H}_{\infty }}(R|f(R))\geqq {H_{\infty }}(R)-\lambda $.
Galindo and Virek (2013) further presented the following consequences related to multiple secret keys (finite random variables).
Lemma 2.
Let ${R_{1}},{R_{2}},\dots ,{R_{n}}$ be n random variables. Let $F\in {Z_{p}}[{R_{1}},{R_{2}},\dots ,{R_{n}}]$ be a polynomial with at most degree d. Let ${P_{k}}$ denote a probability distribution on ${Z_{p}}$ such that ${H_{\infty }}({P_{k}})\geqq \log p-\lambda $ and $0\leqq \lambda \leqq \log p$, for $k=1,2,\dots ,n$. If all ${R_{k}}={r_{k}}\gets {Z_{p}}$ with probability distribution ${P_{k}}$ are mutually independent, we have $\Pr [F({R_{1}}={r_{1}},{R_{2}}={r_{2}},\dots ,{R_{n}}={r_{n}})=0]\leqq (d/p){2^{\lambda }}$.
3 Syntax and Adversary Model
The syntax (framework) and adversary model (security notions) of LR-RCLE-ORA schemes are presented as follows.
3.1 Syntax of LR-RCLE-ORA schemes
Here, let us present the system architecture of an LR-RCLE-ORA scheme as depicted in Fig. 1. An LR-RCLE-ORA scheme consists of three roles, namely, a key generation centre (KGC), an outsourced revocation authority (ORA) and users (senders and receivers). Each user with an identity $\textit{ID}$ randomly selects a personal secret key ${\textit{PSK}_{\textit{ID}}}$ by herself/himself. For each user with $\textit{ID}$, the KGC with a secret key KSK is responsible to generate and securely send an identity secret key ${\textit{ISK}_{\textit{ID}}}$ to the user. For each non-revoked user with $\textit{ID}$ at each period ${T_{s}}$, the ORA with a time secret key $\textit{TSK}$ is responsible to generate and publicly send a time update key ${\textit{TUK}_{\textit{ID},s}}$ to the user. For compromised or revoked users, the ORA will not generate any associated time update keys. At period ${T_{s}}$, when a sender would like to encrypt a plaintext $\mathit{msg}$ to a receiver with $\textit{ID}$, the sender uses the receiver’s $\textit{ID}$ and associated public keys to encrypt $\mathit{msg}$ to generate a ciphertext tuple $(\textit{ID},{T_{s}},\theta )$ while sending $(\textit{ID},{T_{s}},\theta )$ to the receiver. The receiver then uses her/his ${\textit{PSK}_{\textit{ID}}}$, ${\textit{ISK}_{\textit{ID}}}$ and ${\textit{TUK}_{\textit{ID},s}}$ to decrypt $(\textit{ID},{T_{s}},\theta )$ to obtain $\mathit{msg}$.
In the following, we summarize some notations used in the whole paper:
-
• $\textit{KSK}$: the KGC’s secret key;
-
• $\textit{KPK}$: the KGC’s public key;
-
• $\textit{TSK}$: the time secret key;
-
• $\textit{TPK}$: the time public key;
-
• $\textit{ID}$: a user’s identity;
-
• ${\textit{PSK}_{\textit{ID}}}$: a user $\textit{ID}$’s personal secret key;
-
• ${\textit{PPK}_{\textit{ID}}}$: a user $\textit{ID}$’s personal public key;
-
• ${\textit{ISK}_{\textit{ID}}}$: a user $\textit{ID}$’s identity secret key;
-
• ${\textit{IPK}_{\textit{ID}}}$: a user $\textit{ID}$’s identity public key;
-
• ${T_{s}}$: a period ${T_{s}}\in {\{0,1\}^{\ast }}$, for $s=1,\dots ,t$, where t denotes the period length;
-
• ${\textit{TUK}_{\textit{ID},s}}$: a user $\textit{ID}$’s time update key at period ${T_{s}}$;
-
• ${\textit{TUPK}_{\textit{ID},s}}$: a user $\textit{ID}$’s time update public key at period ${T_{s}}$;
-
• $\mathit{msg}$: a message;
-
• θ: a ciphertext.
Based on the syntax (framework) in (Tsai and Tseng, 2015; Xiong et al., 2013; Wu et al., 2018), the syntax of LR-RCLE-ORA schemes is defined as follows. An LR-RCLE-ORA scheme consists of three roles, namely, a key generation centre (KGC), an outsourced revocation authority (ORA) and users (senders and receivers) while including eight algorithms: (1) System setup; (2) Personal secret key setting; (3) Identity secret key extract; (4) Time update key extract; (5) Private key setting; (6) Public key setting; (7) Encrypting; (8) Decrypting. Fig. 2 depicts the algorithm architecture, interactions and their inputs/outputs of the proposed LR-RCLE-ORA scheme. Eight algorithms of the LR-RCLE-ORA scheme are presented in Definition 1 as below:
Definition 1.
An LR-RCLE-ORA scheme consists of three roles, namely, a key generation centre (KGC), an outsourced revocation authority (ORA) and users (senders and receivers). Eight algorithms of the LR-RCLE-ORA scheme are presented as below:
-
– System setup: By taking as input a security parameter κ and a period number t, the KGC generates the KGC’s secret key $\textit{KSK}=({\textit{KSK}_{0,1}},{\textit{KSK}_{0,2}})$ and associated public key KPK, the time secret key $\textit{TSK}=({\textit{TSK}_{0,1}},{\textit{TSK}_{0,2}})$, and time public key TPK. The KGC then securely sends TSK to the ORA. Finally, the KGC publishes t periods ${T_{1}},{T_{2}},\dots ,{T_{t}}$ and public system parameters PSP.
-
– Personal secret key setting: Each user with an identity ID randomly selects a personal secret key ${\textit{PSK}_{\textit{ID}}}=({\textit{PSK}_{\textit{ID},0,1}},{\textit{PSK}_{\textit{ID},0,2}})$ and generates the associated personal public key ${\textit{PPK}_{\textit{ID}}}$.
-
– Identity secret key extract: In this algorithm’s i-th round, by taking as input a user ID and $({\textit{KSK}_{i-1,1}}$, ${\textit{KSK}_{i-1,2}})$, the KGC first carries out two sub-algorithms ISKExtract-1 $(\textit{ID},{\textit{KSK}_{i-1,1}})$ and ISKExtract-2 $({\textit{KSK}_{i-1,2}})$ to set the new KGC’s secret key $({\textit{KSK}_{i,1}},{\textit{KSK}_{i,2}})$, and generate the user’s identity secret key ${\textit{ISK}_{\textit{ID}}}$ and associated identity public key ${\textit{IPK}_{\textit{ID}}}$. Finally, the KGC securely sends ${\textit{IPK}_{\textit{ID}}}$ and ${\textit{ISK}_{\textit{ID}}}$ to the user.
-
– Time update key extract: In this algorithm’s j-th round, by taking as input a user ID, a period ${T_{s}}$ and $({\textit{TSK}_{j-1,1}},{\textit{TSK}_{j-1,2}})$, the ORA carries out two sub-algorithms TUKExtract-1 $(\textit{ID},{T_{s}},{\textit{TSK}_{j-1,1}})$ and TUKExtract-2 $({\textit{TSK}_{j-1,2}})$ to set the new time secret key $({\textit{TSK}_{j,1}},{\textit{TSK}_{j,2}})$, and generate the user’s time update key ${\textit{TUK}_{\textit{ID},s}}$ and associated time update public key ${\textit{TUPK}_{\textit{ID},s}}$ at period ${T_{s}}$. Finally, the ORA sends ${\textit{TUK}_{\textit{ID},s}}$ and ${\textit{TUPK}_{\textit{ID},s}}$ to the user.
-
– Private key setting: At period ${T_{s}}$, a user $\textit{ID}$’s private key tuple includes three parts, namely, ${\textit{PSK}_{\textit{ID}}}$, ${\textit{ISK}_{\textit{ID}}}$, and ${\textit{TUK}_{\textit{ID},s}}$. The user also sets ${\textit{PSK}_{\textit{ID}}}=({\textit{PSK}_{\textit{ID},0,1}},{\textit{PSK}_{\textit{ID},0,2}})$ and ${\textit{ISK}_{\textit{ID}}}=({\textit{ISK}_{\textit{ID},0,1}},{\textit{ISK}_{\textit{ID},0,2}})$.
-
– Public key setting: At period ${T_{s}}$, a user $\textit{ID}$’s public key tuple includes three parts, namely, ${\textit{PPK}_{\textit{ID}}}$, ${\textit{IPK}_{\textit{ID}}}$, and ${\textit{TUPK}_{\textit{ID},s}}$.
-
– Encrypting: At period ${T_{s}}$, by taking as input a plaintext msg and a receiver ID with public key tuple $({\textit{PPK}_{\textit{ID}}},{\textit{IPK}_{\textit{ID}}},{\textit{TUPK}_{\textit{ID},s}}$), the sender generates a ciphertext tuple $(\textit{ID},{T_{s}},\theta =(C,\textit{CT}={E_{\textit{EK}}}(msg)))$, where ${E_{\textit{EK}}}(\cdot )$ is a symmetric encryption function and $\textit{EK}$ is an encryption key encrypted to generate C. Finally, the sender returns the ciphertext tuple $(\textit{ID},{T_{s}},\theta =(C,\textit{CT}))$.
-
– Decrypting: In this algorithm’s k-th round, by taking as input $(\textit{ID},{T_{s}},\theta =(C,\textit{CT}))$, a receiver with ID uses her/his private key tuple $({\textit{PSK}_{\textit{ID}}}=({\textit{PSK}_{\textit{ID},k-1,1}},{\textit{PSK}_{\textit{ID},k-1,2}})$, ${\textit{ISK}_{\textit{ID}}}=({\textit{ISK}_{\textit{ID},k-1,1}},{\textit{ISK}_{\textit{ID},k-1,2}})$, ${\textit{TUK}_{\textit{ID},s}})$ to carry out two sub-algorithms DEC-1$({\textit{PSK}_{\textit{ID},k-1,1}},{\textit{ISK}_{\textit{ID},k-1,1}})$ and DEC-2$({\textit{PSK}_{\textit{ID},k-1,2}},{\textit{ISK}_{\textit{ID},k-1,2}},{\textit{TUK}_{\textit{ID},s}},{T_{s}},\theta =(C,\textit{CT}))$ to set new private key tuple $({\textit{PSK}_{\textit{ID}}}=({\textit{PSK}_{\textit{ID},k,1}},{\textit{PSK}_{\textit{ID},k,2}}),{\textit{ISK}_{\textit{ID}}}=({\textit{ISK}_{\textit{ID},k,1}},{\textit{ISK}_{\textit{ID},k,2}}),{\textit{TUK}_{\textit{ID},s}})$, compute the encryption key EK from C, and decrypt $msg={D_{\textit{EK}}}(\textit{CT})$, where ${D_{\textit{EK}}}(\cdot )$ is the corresponding symmetric decryption function of ${E_{\textit{EK}}}(\cdot )$.
3.2 Adversary Model of LR-RCLE-ORA Schemes
By the entropy concept of secret keys mentioned in Section 2.3, six leakage functions ${f_{\textit{ISKE},i}}$, ${h_{\textit{ISKE},i}}$, ${f_{\textit{TUKE},j}}$, ${h_{\textit{TUKE},j}}$, ${f_{\textit{DEC},k}}$ and ${h_{\textit{DEC},k}}$ are employed to present capabilities of adversaries obtaining leaked information of secrets keys. Both ${f_{\textit{ISKE},i}}$ and ${h_{\textit{ISKE},i}}$ are employed to obtain leaked information of the KGC’s secret key $({\textit{KSK}_{i,1}}$, ${\textit{KSK}_{i,2}})$ used in the Identity secret key extract algorithm’s i-th round. Both ${f_{\textit{TUKE},j}}$ and ${h_{\textit{TUKE},j}}$ are employed to obtain leaked information of the time secret key $({\textit{TSK}_{j,1}}$, ${\textit{TSK}_{j,2}})$ used in the Time update key extract algorithm’s j-th round. Furthermore, both ${f_{\textit{DEC},k}}$ and ${h_{\textit{DEC},k}}$ are employed to obtain leaked information of a receiver’s private key tuple $({\textit{PSK}_{\textit{ID}}}=({\textit{PSK}_{\textit{ID},k,1}},{\textit{PSK}_{\textit{ID},k,2}}),{\textit{ISK}_{\textit{ID}}}=({\textit{ISK}_{\textit{ID},k,1}},{\textit{ISK}_{\textit{ID},k,2}}),{\textit{TUK}_{\textit{ID},s}})$ used in the Decrypting algorithm’s k-th round of a user $\textit{ID}$. An adversary can obtain at most λ bits of secret keys used in each associated algorithm, where λ is related to the security parameter selected in the System setup algorithm. Namely, $|{f_{\textit{ISKE},i}}|$, $|{h_{\textit{ISKE},i}}|$, $|{f_{\textit{TUKE},j}}|$, $|{h_{\textit{TUKE},j}}|$, $|{f_{\textit{DEC},k}}|$, $|{h_{\textit{DEC},k}}|$ ≦ λ, where $|\cdot |$ denotes the output bit-length of a function. The leaked information of a leakage function f is denoted by $\varLambda f$. In the sequel, leaked information of the six leakage functions are denoted as below:
-
– $\varLambda {f_{\textit{ISKE},i}}={f_{\textit{ISKE},i}}({\textit{KSK}_{i,1}})$;
-
– $\varLambda {h_{\textit{ISKE},i}}={h_{\textit{ISKE},i}}({\textit{KSK}_{i,2}})$;
-
– $\varLambda {f_{\textit{TUKE},j}}={f_{\textit{TUKE},j}}({\textit{TSK}_{j,1}})$;
-
– $\varLambda {h_{\textit{TUKE},j}}={h_{\textit{TUKE},j}}({\textit{TSK}_{j,2}})$;
-
– $\varLambda {f_{\textit{DEC},k}}={f_{\textit{DEC},k}}({\textit{PSK}_{\textit{ID},k,1}},{\textit{ISK}_{\textit{ID},k,1}})$;
-
– $\varLambda {h_{\textit{DEC},k}}={h_{\textit{DEC},k}}({\textit{PSK}_{\textit{ID},k,2}},{\textit{ISK}_{\textit{ID},k,2}},{\textit{TUK}_{\textit{ID},k,2}})$.
By extending the adversary model (security notions) in Tsai and Tseng (2015), Xiong et al. (2013), Wu et al. (2018), the adversary model of LR-RCLE-ORA schemes consists of three types of adversaries, namely, outsider (Type I, ${A_{I}}$), revoked user (Type II, ${A_{\textit{II}}}$) and honest-but-curious KGC (Type III, ${A_{\textit{III}}}$).
-
– Outsider (${A_{I}}$): Although ${A_{I}}$ is not a legal user of the LR-RCLE-ORA scheme, it may obtain the time update key ${\textit{TUK}_{\textit{ID},s}}$ of any user $\textit{ID}$ at any period ${T_{s}}$ from public channels. Also, ${A_{I}}$ may get the personal secret key ${\textit{PSK}_{\textit{ID}}}$ and the identity secret key ${\textit{ISK}_{\textit{ID}}}$ of any user $\textit{ID}$, but it is disallowed to get the identity secret key ${\textit{ISK}_{{\textit{ID}^{\ast }}}}$ of the target user ${\textit{ID}^{\ast }}$. For leakage resilient property, ${A_{I}}$ can obtain leaked information of both the target user’s ${\textit{ISK}_{{\textit{ID}^{\ast }}}}=({\textit{ISK}_{{\textit{ID}^{\ast }},k,1}},{\textit{ISK}_{{\textit{ID}^{\ast }},k,2}})$ used in the Decrypting algorithm’s k-th round of the target user and the KGC’s secret key $({\textit{KSK}_{i,1}},{\textit{KSK}_{i,2}})$ used in the Identity secret key extract algorithm’s i-th round.
-
– Revoked user $({A_{\textit{II}}})$: When ${A_{\textit{II}}}$ is a legal user of the LR-RCLE-ORA scheme who has been revoked, it knows the personal secret key ${\textit{PSK}_{\textit{ID}}}$ and the identity secret key ${\textit{ISK}_{\textit{ID}}}$ of any user $\textit{ID}$. Also, ${A_{\textit{II}}}$ may get the time update key ${\textit{TUK}_{\textit{ID},s}}$ of any user $\textit{ID}$ at any period ${T_{s}}$, except ${\textit{TUK}_{{\textit{ID}^{\ast }},{s^{\ast }}}}$ of the target user ${\textit{ID}^{\ast }}$ at target period ${T_{{s^{\ast }}}}$. For leakage resilient property, ${A_{\textit{II}}}$ can obtain leaked information of the time secret key (${\textit{TSK}_{j,1}}$, ${\textit{TSK}_{j,2}}$) used in the Time update key extract algorithm’s j-th round.
-
– Honest-but-curious KGC $({A_{\textit{III}}})$: Since ${A_{\textit{III}}}$ knows the KGC’s secret key $\textit{KSK}$ and time secret key $\textit{TSK}$, it can get the identity secret key ${\textit{ISK}_{\textit{ID}}}$ and time update key ${\textit{TUK}_{\textit{ID},s}}$ of any user $\textit{ID}$ at any period ${T_{s}}$. Also, ${A_{\textit{III}}}$ may get the personal secret key ${\textit{PSK}_{\textit{ID}}}$ of any user $\textit{ID}$, except ${\textit{PSK}_{{\textit{ID}^{\ast }}}}$ of the target user ${\textit{ID}^{\ast }}$. For leakage resilient property, ${A_{\textit{III}}}$ can obtain leaked information of the target user’s ${\textit{PSK}_{{\textit{ID}^{\ast }}}}=({\textit{PSK}_{{\textit{ID}^{\ast }},k,1}},{\textit{PSK}_{{\textit{ID}^{\ast }},k,2}})$ used in the Decrypting algorithm’s k-th round of the target user.
In the continual model of leakage resilient property, the adversary model of LR-RCLE-ORA schemes is defined by the following security game ${G_{\textit{LR-RCLE-ORA}}}$ played by both an adversary (${A_{I}}$, ${A_{\textit{II}}}$ or ${A_{\textit{III}}}$) and a challenger B.
Definition 2.
In the continual leakage model, an LR-RCLE-ORA scheme is semantically secure against chosen cipher-text attacks if no adversary $({A_{I}},{A_{\textit{II}}}\hspace{2.5pt}\text{or}\hspace{2.5pt}{A_{\textit{III}}})$ with non-negligible advantage wins the security game ${G_{\textit{LR-RCLE-ORA}}}$ in polynomial time. This security game ${G_{\textit{LR-RCLE-ORA}}}$ consists of three phases:
-
– Setup phase: By taking as input a security parameter κ and a period number t, a challenger B carries out the System setup algorithm of the LR-RCLE-ORA scheme to generate the KGC’s secret key $\textit{KSK}=({\textit{KSK}_{0,1}},{\textit{KSK}_{0,2}})$, the KGC’s public key KPK, the time secret key $\textit{TSK}=({\textit{TSK}_{0,1}},{\textit{TSK}_{0,2}})$, and the time public key TPK. Also, B sets t periods ${T_{1}},{T_{2}},\dots ,{T_{t}}$ and publishes public system parameters PSP. Additionally, B sends messages to the adversary of various types by the following rules:
-
– Query phase: In the phase, the adversary may request the following queries to B adaptively.
-
• Identity secret key query $(\textit{ID})$: For this query’s i-th round, B sets the new KGC’s secret key $({\textit{KSK}_{i,1}},{\textit{KSK}_{i,2}})$ by using $({\textit{KSK}_{i-1,1}},{\textit{KSK}_{i-1,2}})$. Also, B uses $({\textit{KSK}_{i,1}},{\textit{KSK}_{i,2}})$ to generate and return the associated identity secret key ${\textit{ISK}_{\textit{ID}}}$ and identity public key ${\textit{IPK}_{\textit{ID}}}$.
-
• Identity secret key leak query $({f_{\textit{ISKE},i}},{h_{\textit{ISKE},i}},i)$: In the Identity secret key query’s i-th round, this query is allowed to be requested only once. B returns leaked information $(\varLambda {f_{\textit{ISKE},i}},\varLambda {h_{\textit{ISKE},i}})$.
-
• Time update key query $(\textit{ID},{T_{s}})$: In this query’s j-th round, B sets the new time secret key $({\textit{TSK}_{j,1}}$, ${\textit{TSK}_{j,2}})$ by using $({\textit{TSK}_{j-1,1}},{\textit{TSK}_{j-1,2}})$. Also, B uses $({\textit{TSK}_{j,1}},{\textit{TSK}_{j,2}})$, ID and ${T_{s}}$ to generate and return the associated time update key ${\textit{TUK}_{\textit{ID},s}}$ and the time update public key ${\textit{TUPK}_{\textit{ID},s}}$.
-
• Time update key leak query $({f_{\textit{TUKE},j}},{h_{\textit{TUKE},j}},j)$: In the Time update key query’s j-th round, this query is allowed to be requested only once. B returns leaked information $(\varLambda {f_{\textit{TUKE},j}},\varLambda {h_{\textit{TUKE},j}}$).
-
• Public key retrieve query $(\textit{ID},{T_{s}})$: B returns the associated public key tuple $({\textit{PPK}_{\textit{ID}}},{\textit{IPK}_{\textit{ID}}},{\textit{TUPK}_{\textit{ID},s}})$.
-
• Public key replace query $(\textit{ID},{T_{s}},({\textit{PPK}^{\prime }_{\textit{ID}}},{\textit{IPK}^{\prime }_{\textit{ID}}},{\textit{TUPK}^{\prime }_{\textit{ID},s}}))$: B sets the new public key tuple $({\textit{PPK}^{\prime }_{\textit{ID}}},{\textit{IPK}^{\prime }_{\textit{ID}}},{\textit{TUPK}^{\prime }_{\textit{ID},s}})$ of the user ID at period ${T_{s}}$.
-
• Personal secret key corrupt query $(\textit{ID})$: If the Public key replace query $(\textit{ID})$ has never been requested, B returns the associated personal secret key ${\textit{PSK}_{\textit{ID}}}$.
-
• Decrypting query $(\textit{ID},{T_{s}},\theta =(C,\textit{CT}))$: In this query’s k-th round, B sets the user ID’s new private key tuple $({\textit{PSK}_{\textit{ID}}}=({\textit{PSK}_{\textit{ID},k,1}},{\textit{PSK}_{\textit{ID},k,2}}),{\textit{ISK}_{\textit{ID}}}=({\textit{ISK}_{\textit{ID},k,1}},{\textit{ISK}_{\textit{ID},k,2}}),{\textit{TUK}_{\textit{ID},s}})$ by using $({\textit{PSK}_{\textit{ID}}}=({\textit{PSK}_{\textit{ID},k-1,1}},{\textit{PSK}_{\textit{ID},k-1,2}}),\textit{ISKID}=({\textit{ISK}_{\textit{ID},k-1,1}},{\textit{ISK}_{\textit{ID},k-1,2}})$, ${\textit{TUK}_{\textit{ID},s}})$. Also, B uses the new private key tuple to compute the encryption key $\textit{EK}$ from C, and decrypt $msg={D_{\textit{EK}}}(\textit{CT})$. B returns $\mathit{msg}$.
-
• Decrypting leak query $(\textit{ID},{T_{s}},{f_{\textit{DEC},k}},{h_{\textit{DEC},k}},k)$: In the Decrypting query’s k-th round of the user $\textit{ID}$ at period ${T_{s}}$, this query is allowed to be requested only once. B returns leaked information $(\varLambda {f_{\textit{DEC},k}},\varLambda {h_{\textit{DEC},k}})$.
-
-
– Challenge phase. The adversary sends a target identity ${\textit{ID}^{\ast }}$, a target period ${T_{{s^{\ast }}}}$ and a plaintext pair $(ms{g_{0}^{\ast }},ms{g_{1}^{\ast }})$ to B. B chooses an unbiased random bit $b\in \{0,1\}$ and carries out the Encrypting algorithm with $({\textit{ID}^{\ast }},{T_{{s^{\ast }}}},({\textit{PPK}_{{\textit{ID}^{\ast }}}},{\textit{IPK}_{{\textit{ID}^{\ast }}}},{\textit{TUPK}_{{\textit{ID}^{\ast }},{s^{\ast }}}}),ms{g_{b}^{\ast }})$ to generate ${C^{\ast }}$, ${\textit{EK}^{\ast }}$ and ${\textit{CT}^{\ast }}={E_{{\textit{EK}^{\ast }}}}(ms{g_{b}^{\ast }})$. Finally, B returns the ciphertext tuple $({\textit{ID}^{\ast }}$, ${T_{{s^{\ast }}}}$, $\theta =({C^{\ast }},{\textit{CT}^{\ast }}))$ to the adversary. Additionally, the associated conditions must be satisfied according to various types of adversaries:
-
1. If the adversary is of ${A_{I}}$, the Identity secret key query $({\textit{ID}^{\ast }})$ has never been requested;
-
2. If the adversary is of ${A_{\textit{II}}}$, the Time update key query $({\textit{ID}^{\ast }}$, ${T_{s}^{\ast }})$ has never been requested;
-
3. If the adversary is of ${A_{\textit{III}}}$, both the Personal secret key corrupt query $({\textit{ID}^{\ast }})$ and the Public key replace query $({\textit{ID}^{\ast }},{T_{s}^{\ast }},({\textit{PPK}^{\prime }_{{\textit{ID}^{\ast }}}},{\textit{IPK}^{\prime }_{{\textit{ID}^{\ast }}}},{\textit{TUPK}^{\prime }_{{\textit{ID}^{\ast }},{s^{\ast }}}}))$ has never been requested.
-
-
– Guess phase. In this phase, the adversary must output a bit ${b^{\prime }}\in \{0,1\}$. If ${b^{\prime }}=b$, we say that it wins the game ${G_{\textit{LR-RCLE-ORA}}}$ and its advantage is $|\Pr [{b^{\prime }}=b]-1/2|$.
4 The Proposed LR-RCLE-ORA Scheme
The proposed LR-RCLE-ORA scheme consists of eight algorithms as follows:
-
– System setup: By taking as input a security parameter κ and a period number t, the KGC chooses the bilinear group parameters $\{{G_{1}},{G_{2}},p,Q,\hat{e}\}$, picks a symmetric encryption function $E(\cdot )$ and its associated decryption function $D(\cdot )$, and sets a period set $T=\{{T_{0}},{T_{1}},{T_{2}},\dots ,{T_{t}}\}$. The KGC carries out the following procedures:
-
(1) Randomly select an integer $\alpha \in {Z_{p}^{\ast }}$, and generate the KGC’s secret key $\textit{KSK}=\alpha \cdot Q$ and public key $\textit{KPK}=\hat{e}(Q,\textit{KSK})$. Additionally, the KGC randomly selects an integer ${x_{0}}\in {Z_{p}^{\ast }}$ and generates the KGC’s current secret key $({\textit{KSK}_{0,1}},{\textit{KSK}_{0,2}})=({x_{0}}\cdot Q,\textit{KSK}+(-{x_{0}})\cdot Q)$.
-
(2) Randomly select an integer $\beta \in {Z_{p}^{\ast }}$, and generate the time secret key $\textit{TSK}=\beta \cdot Q$ and time public key $\textit{TPK}=\hat{e}(Q,\textit{TSK})$. Additionally, the KGC securely sends $\textit{TSK}$ to the ORA. The ORA then selects a random integer ${y_{0}}\in {Z_{p}^{\ast }}$ and generates the current time secret key $({\textit{TSK}_{0,1}},{\textit{TSK}_{0,2}})=({y_{0}}\cdot Q,\textit{TSK}+(-{y_{0}})\cdot Q)$.
-
(3) Randomly select four integers $m,n,r,s\in {Z_{p}^{\ast }}$, and compute $M=m\cdot Q$, $N=n\cdot Q$, $R=r\cdot Q$ and $S=s\cdot Q$.
-
(4) Publish public system parameters $\textit{PSP}=\{{G_{1}},{G_{2}},p,Q,\hat{e},\textit{KPK},\textit{TPK},T,D(),E(),M,N,R,S\}$.
-
-
– Personal secret key setting: Each user with an identity $\textit{ID}$ randomly selects an integer $\gamma \in {Z_{p}^{\ast }}$ and generates personal secret key ${\textit{PSK}_{\textit{ID}}}=\gamma \cdot Q$ and the associated personal public key ${\textit{PPK}_{\textit{ID}}}=\hat{e}(Q,{\textit{PSK}_{\textit{ID}}})$.
-
– Identity secret key extract: In this algorithm’s i-th round, by taking as input a user’s $\textit{ID}$ and $({\textit{KSK}_{i-1,1}},{\textit{KSK}_{i-1,2}})$, the KGC carries out two sub-algorithms $\text{ISKExtract-1}(\textit{ID},{\textit{KSK}_{i-1,1}})$ and $\text{ISKExtract-2}({\textit{KSK}_{i-1,2}})$ as below:
-
• $\text{ISKExtract-1}(\textit{ID},{\textit{KSK}_{i-1,1}})$:
-
(1) Randomly select an integer ${x_{i}}\in {Z_{p}^{\ast }}$, and compute ${\textit{KSK}_{i,1}}={\textit{KSK}_{i-1,1}}+{x_{i}}\cdot Q$.
-
(2) Randomly select an integer $u\in {Z_{p}^{\ast }}$, and compute ${\textit{IPK}_{\textit{ID}}}=u\cdot Q$ and temporary value ${\textit{TV}_{\textit{ISKE}}}={\textit{KSK}_{i,1}}+u\cdot (M+\textit{ID}\cdot N)$.
-
-
• $\text{ISKExtract-2}({\textit{KSK}_{i-1,2}})$:
-
(1) Compute ${\textit{KSK}_{i,2}}={\textit{KSK}_{i-1,2}}+(-{x_{i}})\cdot Q$ and ${\textit{ISK}_{\textit{ID}}}={\textit{KSK}_{i,2}}+{\textit{TV}_{\textit{ISKE}}}$.
-
(2) Send the user’s identity secret key ${\textit{ISK}_{\textit{ID}}}$ and associated identity public key ${\textit{IPK}_{\textit{ID}}}$ to the user using a secure channel.
-
-
-
– Time update key extract: In this algorithm’s j-th round, by taking as input a user’s $\textit{ID}$, a period ${T_{s}}$ and $({\textit{TSK}_{j-1,1}},{\textit{TSK}_{j-1,2}})$, the ORA carries out two sub-algorithms $\text{TUKExtract-1}(\textit{ID},{T_{s}},{\textit{TSK}_{j-1,1}})$ and $\text{TUKExtract-2}({\textit{TSK}_{j-1,2}})$ as below:
-
• $\text{TUKExtract-1}(\textit{ID},{T_{s}},{\textit{TSK}_{j-1,1}})$:
-
(1) Randomly select an integer ${y_{j}}\in {Z_{p}^{\ast }}$, and compute ${\textit{TSK}_{j,1}}={\textit{TSK}_{j-1,1}}+{y_{j}}\cdot Q$.
-
(2) Randomly select an integer $v\in {Z_{p}^{\ast }}$, and compute ${\textit{TUPK}_{\textit{ID},s}}=v\cdot Q$ and temporary value ${\textit{TV}_{\textit{TUKE}}}={\textit{TSK}_{j,1}}+v\cdot (R+(\textit{ID}||{T_{s}})\cdot S)$.
-
-
• $\text{TUKExtract-2}({\textit{TSK}_{j-1,2}})$:
-
(1) Compute ${\textit{TSK}_{j,2}}={\textit{TSK}_{j-1,2}}+(-{y_{j}})\cdot Q$ and ${\textit{TUK}_{\textit{ID},s}}={\textit{TSK}_{j,2}}+{\textit{TV}_{\textit{TUKE}}}$.
-
(2) Send the user’s time update key ${\textit{TUK}_{\textit{ID},s}}$ and associated time update public key ${\textit{TUPK}_{\textit{ID},s}}$ to the user.
-
-
-
– Private key setting: At period ${T_{s}}$, a user $\textit{ID}$’s private key tuple includes three parts, namely, ${\textit{PSK}_{\textit{ID}}}$, ${\textit{ISK}_{\textit{ID}}}$, and ${\textit{TUK}_{\textit{ID},s}}$. The user carries out the following procedures:
-
(1) Randomly select an integer ${z_{0}}\in {Z_{p}^{\ast }}$ and compute the current personal secret key $({\textit{PSK}_{\textit{ID},0,1}},{\textit{PSK}_{\textit{ID},0,2}})=({z_{0}}\cdot Q,{\textit{PSK}_{\textit{ID}}}+(-{z_{0}})\cdot Q)$.
-
(2) Randomly select an integer ${w_{0}}\in {Z_{p}^{\ast }}$ and compute the current identity secret key $({\textit{ISK}_{\textit{ID},0,1}},{\textit{ISK}_{\textit{ID},0,2}})=({w_{0}}\cdot Q,{\textit{ISK}_{\textit{ID}}}+(-{w_{0}})\cdot Q)$.
-
(3) Set the user’s private key tuple $({\textit{PSK}_{\textit{ID}}}=({\textit{SK}_{\textit{ID},0,1}},{\textit{SK}_{\textit{ID},0,2}}),{\textit{ISK}_{\textit{ID}}}=({\textit{ISK}_{\textit{ID},0,1}},{\textit{ISK}_{\textit{ID},0,2}}),{\textit{TUK}_{\textit{ID},s}})$.
-
-
– Public key setting: At period ${T_{s}}$, a user $\textit{ID}$ sets her/his public key tuple $({\textit{PPK}_{\textit{ID}}},{\textit{IPK}_{\textit{ID}}},{\textit{TUPK}_{\textit{ID},s}})$.
-
– Encrypting: At period ${T_{s}}$, by taking as input a plaintext $\mathit{msg}$ and a receiver $\textit{ID}$ with public key tuple $({\textit{PPK}_{\textit{ID}}},{\textit{IPK}_{\textit{ID}}},{\textit{TUPK}_{\textit{ID},s}})$, the sender carries out the following procedures:
-
(1) Randomly select an integer $ek\in {Z_{p}^{\ast }}$.
-
(2) Compute $C=ek\cdot Q$, ${K_{1}}={({\textit{PPK}_{\textit{ID}}})^{ek}}$, ${K_{2}}={(\textit{KPK}\cdot \hat{e}({\textit{IPK}_{\textit{ID}}},M+\textit{ID}\cdot N))^{ek}}$ and ${K_{3}}={(\textit{TPK}\cdot \hat{e}({\textit{TUPK}_{\textit{ID},s}},R+(\textit{ID}||{T_{s}})\cdot S))^{ek}}$.
-
(3) Set the encryption key $\textit{EK}={K_{1}}\oplus {K_{2}}\oplus {K_{3}}$.
-
(4) Compute $\textit{CT}={E_{\textit{EK}}}(msg)$ and return the ciphertext tuple $(\textit{ID},{T_{s}},\theta =(C,\textit{CT}))$.
-
-
– Decrypting: In this algorithm’s k-th round, by taking as input $(\textit{ID},{T_{s}},\theta =(C,\textit{CT}))$, a receiver $\textit{ID}$ uses her/his private key tuple $({\textit{PSK}_{\textit{ID}}}=({\textit{PSK}_{\textit{ID},k-1,1}},{\textit{PSK}_{\textit{ID},k-1,2}}),{\textit{ISK}_{\textit{ID}}}=({\textit{ISK}_{\textit{ID},k-1,1}},{\textit{ISK}_{\textit{ID},k-1,2}}),{\textit{TUK}_{\textit{ID},s}})$ to carry out two sub-algorithms $\text{DEC-1}({\textit{PSK}_{\textit{ID},k-1,1}},{\textit{ISK}_{\textit{ID},k-1,1}})$ and $\text{DEC-2}({\textit{PSK}_{\textit{ID},k-1,2}},{\textit{ISK}_{\textit{ID},k-1,2}},{\textit{TUK}_{\textit{ID},s}},{T_{s}},\theta =(C,\textit{CT}))$ as below:
-
• $\text{DEC-1}({\textit{PSK}_{\textit{ID},k-1,1}},{\textit{ISK}_{\textit{ID},k-1,1}})$
-
(1) Randomly select an integer ${z_{k}}\in {Z_{p}^{\ast }}$, and compute ${\textit{PSK}_{\textit{ID},k,1}}={\textit{PSK}_{\textit{ID},k-1,1}}+{z_{k}}\cdot Q$.
-
(2) Randomly select an integer ${w_{k}}\in {Z_{p}^{\ast }}$, and compute ${\textit{ISK}_{\textit{ID},k,1}}={\textit{ISK}_{\textit{ID},k-1,1}}+{w_{k}}\cdot Q$.
-
(3) Compute two temporary values ${\textit{TV}_{1}}=\hat{e}(C,{\textit{PSK}_{\textit{ID},k,1}})$ and ${\textit{TV}_{2}}=\hat{e}(C,{\textit{ISK}_{\textit{ID},k,1}})$.
-
-
• $\text{DEC-2}({\textit{PSK}_{\textit{ID},k-1,2}},{\textit{ISK}_{\textit{ID},k-1,2}},{\textit{TUK}_{\textit{ID},s}},{T_{s}},\theta =(C,\textit{CT}))$In the following, by the key refreshing technique, we have
-
(1) Compute ${\textit{PSK}_{\textit{ID},k,2}}={\textit{PSK}_{\textit{ID},k-1,2}}+(-{z_{k}})\cdot Q$ and ${\textit{ISK}_{\textit{ID},k,2}}={\textit{ISK}_{\textit{ID},k-1,2}}+(-{w_{k}})\cdot Q$.
-
(2) Compute ${K^{\prime }_{1}}={\textit{TV}_{1}}\cdot \hat{e}(C,{\textit{PSK}_{\textit{ID},k,2}})$, ${K^{\prime }_{2}}={\textit{TV}_{2}}\cdot \hat{e}(C,{\textit{ISK}_{\textit{ID},k,2}})$ and ${K^{\prime }_{3}}=\hat{e}(C,{\textit{TUK}_{\textit{ID},s}})$.
-
(3) Compute the encryption key ${\textit{EK}^{\prime }}={K^{\prime }_{1}}\oplus {K^{\prime }_{2}}\oplus {K^{\prime }_{3}}$.
-
(4) Decrypt the plaintext $msg={D_{{\textit{EK}^{\prime }}}}(\textit{CT})$.
\[\begin{aligned}{}& \textit{KSK}={\textit{KSK}_{0,1}}+{\textit{KSK}_{0,2}}={\textit{KSK}_{1,1}}+{\textit{KSK}_{1,2}}=\cdots ={\textit{KSK}_{i,1}}+{\textit{KSK}_{i,2}};\\ {} & \textit{TSK}={\textit{TSK}_{0,1}}+{\textit{TSK}_{0,2}}={\textit{TSK}_{1,1}}+{\textit{TSK}_{1,2}}=\cdots ={\textit{TSK}_{j,1}}+{\textit{TSK}_{j,2}};\\ {} & {\textit{PSK}_{\textit{ID}}}={\textit{PSK}_{\textit{ID},0,1}}+{\textit{PSK}_{\textit{ID},0,2}}={\textit{PSK}_{\textit{ID},1,1}}+{\textit{PSK}_{\textit{ID},1,2}}\\ {} & \phantom{{\textit{PSK}_{\textit{ID}}}}=\cdots ={\textit{PSK}_{\textit{ID},k,1}}+{\textit{PSK}_{\textit{ID},k,2}};\\ {} & {\textit{ISK}_{\textit{ID}}}={\textit{ISK}_{\textit{ID},0,1}}+{\textit{ISK}_{\textit{ID},0,2}}={\textit{ISK}_{\textit{ID},1,1}}+{\textit{ISK}_{\textit{ID},1,2}}\\ {} & \phantom{{\textit{ISK}_{\textit{ID}}}}=\cdots ={\textit{ISK}_{\textit{ID},k,1}}+{\textit{ISK}_{\textit{ID},k,2}}.\end{aligned}\] -
-
In the following, we show the correctness of $\textit{EK}={K_{1}}\oplus {K_{2}}\oplus {K_{3}}={K^{\prime }_{1}}\oplus {K^{\prime }_{2}}\oplus {K^{\prime }_{3}}={\textit{EK}^{\prime }}$.
\[\begin{aligned}{}\textit{EK}& ={K_{1}}\oplus {K_{2}}\oplus {K_{3}}\\ {} & ={({\textit{PPK}_{\textit{ID}}})^{ek}}\oplus {\big(\textit{KPK}\cdot \hat{e}({\textit{IPK}_{\textit{ID}}},M+\textit{ID}\cdot N)\big)^{ek}}\\ {} & \hspace{1em}\oplus {\big(\textit{TPK}\cdot \hat{e}\big({\textit{TUPK}_{\textit{ID},s}},R+(\textit{ID}||{T_{s}})\cdot S\big)\big)^{ek}}\\ {} & =\hat{e}{(Q,{\textit{PSK}_{\textit{ID}}})^{ek}}\oplus {\big(\hat{e}(Q,\textit{KSK})\cdot \hat{e}(u\cdot Q,M+\textit{ID}\cdot N)\big)^{ek}}\\ {} & \hspace{1em}\oplus {\big(\hat{e}(Q,\textit{TSK})\cdot \hat{e}\big(v\cdot Q,R+(\textit{ID}||{T_{s}})\cdot S\big)\big)^{ek}}\\ {} & =\hat{e}{(Q,{\textit{PSK}_{\textit{ID}}})^{ek}}\oplus {\big(\hat{e}(Q,\textit{KSK})\cdot \hat{e}\big(Q,u\cdot (M+\textit{ID}\cdot N)\big)\big)^{ek}}\\ {} & \hspace{1em}\oplus {\big(\hat{e}(Q,\textit{TSK})\cdot \hat{e}\big(Q,v\cdot \big(R+(\textit{ID}||{T_{s}})\cdot S\big)\big)\big)^{ek}}\\ {} & =\hat{e}{(Q,{\textit{PSK}_{\textit{ID}}})^{ek}}\oplus {\big(\hat{e}\big(Q,\textit{KSK}+u\cdot (M+\textit{ID}\cdot N)\big)\big)^{ek}}\\ {} & \hspace{1em}\oplus {\big(\hat{e}\big(Q,\textit{TSK}+v\cdot \big(R+(\textit{ID}||{T_{s}})\cdot S\big)\big)\big)^{ek}}\\ {} & =\hat{e}(ek\cdot Q,{\textit{PSK}_{\textit{ID}}})\oplus \hat{e}\big(ek\cdot Q,\textit{KSK}+u\cdot (M+\textit{ID}\cdot N)\big)\\ {} & \hspace{1em}\oplus \hat{e}\big(ek\cdot Q,\textit{TSK}+v\cdot \big(R+(\textit{ID}||{T_{s}})\cdot S\big)\big)\\ {} & =\hat{e}(C,{\textit{PSK}_{\textit{ID}}})\oplus \hat{e}\big(C,\textit{KSK}+u\cdot (M+\textit{ID}\cdot N)\big)\\ {} & \hspace{1em}\oplus \hat{e}\big(C,\textit{TSK}+v\cdot \big(R+(\textit{ID}||{T_{s}})\cdot S\big)\big)\\ {} & =\hat{e}(C,{\textit{PSK}_{\textit{ID}}})\oplus \hat{e}\big(C,{\textit{KSK}_{i,1}}+{\textit{KSK}_{i,2}}+u\cdot (M+\textit{ID}\cdot N)\big)\\ {} & \hspace{1em}\oplus \hat{e}\big(C,{\textit{TSK}_{j,1}}+{\textit{TSK}_{j,2}}+v\cdot \big(R+(\textit{ID}||{T_{s}})\cdot S\big)\big)\\ {} & =\hat{e}(C,{\textit{PSK}_{\textit{ID}}})\oplus \hat{e}(C,{\textit{KSK}_{i,2}}+{\textit{TV}_{\textit{ISKE}}})\oplus \hat{e}(C,{\textit{TSK}_{j,2}}+{\textit{TV}_{\textit{TUKE}}})\\ {} & =\hat{e}(C,{\textit{PSK}_{\textit{ID}}})\oplus \hat{e}(C,{\textit{ISK}_{\textit{ID}}})\oplus \hat{e}(C,{\textit{TUK}_{\textit{ID},s}})\\ {} & =\hat{e}(C,{\textit{PSK}_{\textit{ID},k,1}}+{\textit{PSK}_{\textit{ID},k,2}})\oplus \hat{e}(C,{\textit{ISK}_{\textit{ID},k,1}}+{\textit{ISK}_{\textit{ID},k,2}})\oplus \hat{e}(C,{\textit{TUK}_{\textit{ID},s}})\\ {} & =\big(\hat{e}(C,{\textit{PSK}_{\textit{ID},k,1}})\cdot \hat{e}(C,{\textit{PSK}_{\textit{ID},k,2}})\big)\\ {} & \hspace{1em}\oplus \big(\hat{e}(C,{\textit{ISK}_{\textit{ID},k,1}})\cdot \hat{e}(C,{\textit{ISK}_{\textit{ID},k,2}})\big)\oplus \hat{e}(C,{\textit{TUK}_{\textit{ID},s}})\\ {} & =\big({\textit{TV}_{1}}\cdot \hat{e}(C,{\textit{PSK}_{\textit{ID},k,2}})\big)\oplus \big({\textit{TV}_{2}}\cdot \hat{e}(C,{\textit{ISK}_{\textit{ID},k,2}})\big)\oplus \hat{e}(C,{\textit{TUK}_{\textit{ID},s}})\\ {} & ={K^{\prime }_{1}}\oplus {K^{\prime }_{2}}\oplus {K^{\prime }_{3}}={\textit{EK}^{\prime }}.\end{aligned}\]
5 Security Analysis
As the security game ${G_{\textit{LR-RCLE-ORA}}}$ presented in Definition 2, the adversary model consists of three types of adversaries, namely, outsider (Type I, ${A_{I}}$), revoked user (Type II, ${A_{\textit{II}}}$) and honest-but-curious KGC (Type III, ${A_{\textit{III}}}$). Under the GBG model presented in Section 2, we employ three theorems to demonstrate that the proposed LR-RCLE-ORA scheme is semantically secure against chosen cipher-text attacks against three types of adversaries, respectively. The relationship and robustness of security analysis are depicted in Fig. 3. In Theorem 1, we first discuss the advantage (denoted by ${\textit{Adv}_{A-I-W}}$) of an outsider (${A_{I}}$) without requesting any leak queries and then evaluate the advantage (denoted by ${\textit{Adv}_{A-I}}$) of an outsider (${A_{I}}$) with requesting Identity secret key leak and Decrypting leak queries. Indeed, by Corollary 1, ${\textit{Adv}_{A-I}}$ is negligible based on the DL assumption. For Theorems 2 and 3, by similar arguments as in Theorem 1, the advantages (denoted by ${\textit{Adv}_{A-\textit{II}}}$ and ${\textit{Adv}_{A-\textit{III}}}$) of a revoked user (${A_{\textit{II}}}$) and an honest-but-curious KGC (${A_{\textit{III}}}$) are also negligible based on the DL assumption.
Theorem 1.
In the GBG model, the proposed LR-RCLE-ORA scheme is semantically secure against chosen cipher-text attacks against an outsider $({A_{I}})$ in the security game ${G_{\textit{LR-RCLE-ORA}}}$.
Proof.
Let ${A_{I}}$ be an outsider of the security game ${G_{\textit{LR-RCLE-ORA}}}$ played with a challenger B. In the GBG model, ${A_{I}}$ may request three queries (oracles) ${O_{1}}$, ${O_{2}}$ and ${O_{p}}$ to perform three corresponding group operations. In the security game ${G_{\textit{LR-RCLE-ORA}}}$, four phases are presented as below:
-
– Setup phase: By taking as input a security parameter κ and a period number t, B carries out the System setup algorithm of the LR-RCLE-ORA scheme to generate the KGC’s secret key $\textit{KSK}=({\textit{KSK}_{0,1}},{\textit{KSK}_{0,2}})$, the KGC’s public key $\textit{KPK}$, the time secret key $\textit{TSK}$, and the time pubic key $\textit{TPK}$. Also, B sets a period set $T=\{{T_{0}},{T_{1}},{T_{2}},\dots ,{T_{t}}\}$ and publishes public system parameters $\textit{PSP}=\{{G_{1}},{G_{2}},p,Q,\hat{e},\textit{KPK},\textit{TPK},T,D(),E(),M,N,R,S\}$. Additionally, B sends $\textit{TSK}$ to ${A_{I}}$ since ${A_{I}}$ is an outsider. To respond the queries requested by ${A_{I}}$, five initially empty lists ${L_{1}}$, ${L_{2}}$, ${L_{\textit{ISK}}}$, ${L_{\textit{TUK}}}$ and ${L_{\textit{PSK}}}$ are constructed as below:Finally, these public system parameters $\varXi Q$, $\varXi M$, $\varXi N$, $\varXi R$, $\varXi S$, $\varXi \textit{KPK}$ and $\varXi \textit{TPK}$ are sent to ${A_{I}}$. Also, B sends the time secret key $\varXi \textit{TSK}$ to ${A_{I}}$.
-
• ${L_{1}}$ and ${L_{2}}$ are used to encode elements of groups ${G_{1}}$ and ${G_{2}}$, respectively.It is worth mentioning the two transforming rules defined below.
-
(1) ${L_{1}}$ includes pairs of $(\varXi {G_{1,t,u,v}}$, $\varTheta {G_{1,t,u,v}})$. An element in ${G_{1}}$ is represented by a multivariate polynomial $\varXi {G_{1,t,u,v}}$ and $\varTheta {G_{1,t,u,v}}$ is the corresponding encoded bit-string, where t, u and v, respectively, denote the query type t, the u-th query and the v-th element in ${G_{1}}$. B initially adds seven pairs $(\varXi Q,\varTheta {G_{1,I,0,1}})$, $(\varXi \textit{KSK},\varTheta {G_{1,I,0,2}})$, $(\varXi \textit{TSK},\varTheta {G_{1,I,0,3}})$, $(\varXi M,\varTheta {G_{1,I,0,4}})$, $(\varXi N,\varTheta {G_{1,I,0,5}})$, $(\varXi R,\varTheta {G_{1,I,0,6}})$ and $(\varXi S,\varTheta {G_{1,I,0,7}})$ in ${L_{1}}$.
-
(2) ${L_{2}}$ includes pairs of $(\varXi {G_{2,t,u,v}},\varTheta {G_{2,t,u,v}})$. An element in ${G_{2}}$ is represented by a multivariate polynomial $\varXi {G_{2,t,u,v}}$ and $\varTheta {G_{2,t,u,v}}$ is the corresponding encoded bit-string, where t, u and v have the same meanings with those indices in ${L_{1}}$. B initially adds two pairs $(\varXi \textit{KPK},\varTheta {G_{2,I,0,1}})$ and $(\varXi \textit{TPK},\varTheta {G_{2,I,0,2}})$ in ${L_{2}}$, where $\varXi \textit{KPK}=\varXi Q\cdot \varXi \textit{KSK}$ and $\varXi \textit{TPK}=\varXi Q\cdot \varXi \textit{TSK}$.
-
(1) By taking as input a polynomial $\varXi {G_{1,t,u,v}}/\varXi {G_{2,t,u,v}}$, B looks for $(\varXi {G_{1,t,u,v}},\varTheta {G_{1,t,u,v}})/(\varXi {G_{2,t,u,v}},\varTheta {G_{2,t,u,v}})$ in ${L_{1}}/{L_{2}}$. If it is found, B returns the encoded bit-string $\varTheta {G_{1,t,u,v}}/\varTheta {G_{2,t,u,v}}$. Otherwise, B randomly chooses and returns a distinct encoded bit-string $\varTheta {G_{1,t,u,v}}/\varTheta {G_{2,t,u,v}}$. In addition, B adds $(\varXi {G_{1,t,u,v}}$, $\varTheta {G_{1,t,u,v}})/(\varXi {G_{2,t,u,v}}$, $\varTheta {G_{2,t,u,v}})$ in ${L_{1}}/{L_{2}}$.
-
(2) By taking as input an encoded bit-string $\varTheta {G_{1,t,u,v}}/\varTheta {G_{2,t,u,v}}$, B looks for $(\varXi {G_{1,t,u,v}},\varTheta {G_{1,t,u,v}})/(\varXi {G_{2,t,u,v}},\varTheta {G_{2,t,u,v}})$ in ${L_{1}}/{L_{2}}$. If it is found, B returns the associated multivariate polynomial $\varXi {G_{1,t,u,v}}/\varXi {G_{2,t,u,v}}$. Otherwise, B terminates the game.
-
-
• ${L_{\textit{ISK}}}$ includes tuples of $(\textit{ID},\varXi {\textit{ISK}_{\textit{ID}}},\varXi {\textit{IPK}_{\textit{ID}}})$, where $\varXi {\textit{ISK}_{\textit{ID}}}$ and $\varXi {\textit{IPK}_{\textit{ID}}}$, respectively, represent the user’s ${\textit{ISK}_{\textit{ID}}}$ and ${\textit{IPK}_{\textit{ID}}}$.
-
• ${L_{\textit{PSK}}}$ includes tuples of $(\textit{ID},\varXi {\textit{PSK}_{\textit{ID}}},\varXi {\textit{PPK}_{\textit{ID}}})$, where $\varXi {\textit{PSK}_{\textit{ID}}}$ and $\varXi {\textit{PPK}_{\textit{ID}}}$, respectively, denote the user’s ${\textit{PSK}_{\textit{ID}}}$ and ${\textit{PPK}_{\textit{ID}}}$.
-
• ${L_{\textit{TUK}}}$ includes tuples of $(\textit{ID},{T_{s}},\varXi {\textit{TUK}_{\textit{ID},s}},\varXi {\textit{TUPK}_{\textit{ID},s}})$, where $\varXi {\textit{TUK}_{\textit{ID},s}}$ and $\varXi {\textit{TUPK}_{\textit{ID},s}}$, respectively, denote the user’s ${\textit{TUK}_{\textit{ID},s}}$ and ${\textit{TUPK}_{\textit{ID},s}}$.
-
-
– Query phase: ${A_{I}}$ can adaptively request various queries to B at most q times. Note that ${A_{I}}$ does not need to request the Time update key leak query and Public key replace query, since ${A_{I}}$ may get the time update key ${\textit{TUK}_{\textit{ID},s}}$ of any user $\textit{ID}$ at any period ${T_{s}}$ from public channels.
-
• ${O_{1}}$ query $(\varTheta {G_{1,Q,l,1}},\varTheta {G_{1,Q,l,2}},\textit{OP})$: In this query’s l-th round, B carries out the following steps:
-
(1) Get a pair of polynomials $(\varXi {G_{1,Q,l,1}},\varXi {G_{1,Q,l,2}})$ by transforming a pair of bit-strings $(\varTheta {G_{1,Q,l,1}},\varTheta {G_{1,Q,l,2}})$ in ${L_{1}}$.
-
(2) Compute the polynomial $\varXi {G_{1,Q,l,3}}=\varXi {G_{1,Q,l,1}}+\varXi {G_{1,Q,l,2}}$ if $\textit{OP}$ = “addition”, and $\varXi {G_{1,Q,l,3}}=\varXi {G_{1,Q,l,1}}-\varXi {G_{1,Q,l,2}}$ if $\textit{OP}$ = “subtraction”.
-
(3) Return the encoded bit-string $\varTheta {G_{1,Q,l,3}}$ by transforming $\varXi {G_{1,Q,l,3}}$ in ${L_{1}}$.
-
-
• ${O_{2}}$ query $(\varTheta {G_{2,Q,l,1}},\varTheta {G_{2,Q,l,2}},\textit{OP})$: In this query’s l-th round, B carries out the following steps:
-
(1) Get a pair of polynomials $(\varXi {G_{2,Q,l,1}},\varXi {G_{2,Q,l,2}})$ by transforming a pair of bit-strings $(\varTheta {G_{2,Q,l,1}},\varTheta {G_{2,Q,l,2}})$ in ${L_{2}}$.
-
(2) Compute the polynomial $\varXi {G_{2,Q,l,3}}=\varXi {G_{2,Q,l,1}}+\varXi {G_{2,Q,l,2}}$ if $\textit{OP}$ = “multiplication”, and $\varXi {G_{2,Q,l,3}}=\varXi {G_{2,Q,l,1}}-\varXi {G_{2,Q,l,2}}$ if $\textit{OP}$ = “division”.
-
(3) Return the encoded bit-string $\varTheta {G_{2,Q,l,3}}$ by transforming $\varXi {G_{2,Q,l,3}}$ in ${L_{2}}$.
-
-
• ${O_{p}}$ query $(\varTheta {G_{1,P,l,1}},\varTheta {G_{1,P,l,2}})$: In this query’s l-th round, B carries out the following steps:
-
(1) Get a pair of polynomials $(\varXi {G_{1,P,l,1}},\varXi {G_{1,P,l,2}})$ by transforming a pair of bit-strings $(\varTheta {G_{1,P,l,1}},\varTheta {G_{1,P,l,2}})$ in ${L_{1}}$.
-
(2) Compute the polynomial $\varXi {G_{2,P,l,1}}=\varXi {G_{1,P,l,1}}\cdot \varXi {G_{1,P,l,2}}$.
-
(3) Return the encoded bit-string $\varTheta {G_{2,P,l,1}}$ by transforming $\varXi {G_{2,P,l,1}}$ in ${L_{2}}$.
-
-
• Identity secret key query $(\textit{ID})$: In this query’s i-th round, B searches ($\textit{ID}$, $\varXi {\textit{ISK}_{\textit{ID}}}$, $\varXi {\textit{IPK}_{\textit{ID}}}$) in ${L_{\textit{ISK}}}$. If it is found, B transforms $(\varXi {\textit{ISK}_{\textit{ID}}}$, $\varXi {\textit{IPK}_{\textit{ID}}})$ to send two encoded bit-strings $(\varTheta {\textit{ISK}_{\textit{ID}}}$, $\varTheta {\textit{IPK}_{\textit{ID}}})$ to ${A_{I}}$. Otherwise, B carries out the following steps:
-
(1) Choose a new variate $\varXi {\textit{TG}_{ISK,i,1}}$ in ${G_{1}}$.
-
(2) Set two polynomials $\varXi {\textit{IPK}_{\textit{ID}}}=\varXi {\textit{TG}_{\textit{ISK},i,1}}$ and $\varXi \textit{TID}=\textit{ID}$.
-
(3) Set the user’s identity secret key $\varXi {\textit{ISK}_{\textit{ID}}}=\varXi \textit{KSK}+\varXi {\textit{TG}_{\textit{ISK},i,1}}\cdot (\varXi M+\varXi N\cdot \varXi \textit{TID})$ while adding $(\textit{ID},\varXi {\textit{ISK}_{\textit{ID}}},\varXi {\textit{IPK}_{\textit{ID}}})$ in ${L_{\textit{ISK}}}$.
-
(4) Transform $(\varXi {\textit{ISK}_{\textit{ID}}},\varXi {\textit{IPK}_{\textit{ID}}})$ to send two encoded bit-strings $(\varTheta {\textit{ISK}_{\textit{ID}}},\varTheta {\textit{IPK}_{\textit{ID}}})$ to ${A_{I}}$.
-
-
• Identity secret key leak query (${f_{\textit{ISKE},i}},{h_{\textit{ISKE},i}},i)$: In the Identity secret key query’s i-th round, this query is allowed to be requested only once. B returns leaked information $(\varLambda {f_{\textit{ISKE},i}},\varLambda {h_{\textit{ISKE},i}})$, where $\varLambda {f_{\textit{ISKE},i}}={f_{\textit{ISKE},i}}({\textit{KSK}_{i,1}})$ and $\varLambda {h_{\textit{ISKE},i}}={h_{\textit{ISKE},i}}({\textit{KSK}_{i,2}})$.
-
• Time update key query $(\textit{ID},{T_{s}})$: In this query’s j-th round, B searches ($\textit{ID}$, ${T_{s}}$, $\varXi {\textit{TUK}_{\textit{ID},s}}$, $\varXi {\textit{TUPK}_{\textit{ID},s}}$) in ${L_{\textit{TUK}}}$. If it is found, B transforms $(\varXi {\textit{TUK}_{\textit{ID},s}},\varXi {\textit{TUPK}_{\textit{ID},s}})$ to return two encoded bit-strings $(\varTheta {\textit{TUK}_{\textit{ID},s}},\varTheta {\textit{TUPK}_{\textit{ID},s}})$. Otherwise, B carries out the following steps:
-
(1) Choose a new variate $\varXi {\textit{TG}_{\textit{TUK},\textit{ID},j,1}}$ in ${G_{1}}$.
-
(2) Set a polynomial $\varXi {\textit{TUPK}_{\textit{ID},s}}=\varXi {\textit{TG}_{\textit{TUK},\textit{ID},j,1}}$ and $\varXi \textit{TTD}=\textit{ID}||{T_{s}}$.
-
(3) Set the user’s time update key $\varXi {\textit{TUK}_{\textit{ID},t}}=\varXi \textit{TSK}+\varXi {\textit{TG}_{\textit{TUK},\textit{ID},j,1}}\cdot (\varXi R+\varXi S\cdot \varXi \textit{TTD})$ while adding $(\textit{ID},{T_{s}},\varXi {\textit{TUK}_{\textit{ID},s}},\varXi {\textit{TUPK}_{\textit{ID},s}})$ in ${L_{\textit{TUK}}}$.
-
(4) Transform $(\varXi {\textit{TUK}_{\textit{ID},s}},\varXi {\textit{TUPK}_{\textit{ID},s}})$ to return two encoded bit-strings $(\varTheta {\textit{TUK}_{\textit{ID},s}},\varTheta {\textit{TUPK}_{\textit{ID},s}})$.
-
-
• Time update key leak query $({f_{\textit{TUKE},j}},{h_{\textit{TUKE},j}},j)$: In the Time update key query’s j-th round, this query is allowed to be requested only once. B returns leaked information $(\varLambda {f_{\textit{TUKE},j}},\varLambda {h_{\textit{TUKE},j}})$, where $\varLambda {f_{\textit{TUKE},j}}={f_{\textit{TUKE},j}}({\textit{TSK}_{j,1}})$ and $\varLambda {h_{\textit{TUKE},j}}={h_{\textit{TUKE},j}}({\textit{TSK}_{j,2}})$.
-
• Public key retrieve query $(\textit{ID},{T_{s}})$: B applies $\textit{ID}$ and ${T_{s}}$ to search ${L_{\textit{ISK}}}$, ${L_{\textit{PSK}}}$ and ${L_{\textit{TUK}}}$ to get the associated public key tuple $(\varXi {\textit{PPK}_{\textit{ID}}},\varXi {\textit{IPK}_{\textit{ID}}},\varXi {\textit{TUPK}_{\textit{ID},s}})$. B returns the corresponding tuple $(\varTheta {\textit{PPK}_{\textit{ID}}},\varTheta {\textit{IPK}_{\textit{ID}}},\varTheta {\textit{TUPK}_{\textit{ID},s}})$.
-
• Public key replace query $(\textit{ID},{T_{s}},(\varTheta {\textit{PPK}^{\prime }_{\textit{ID}}},\varTheta {\textit{IPK}^{\prime }_{\textit{ID}}},\varTheta {\textit{TUPK}^{\prime }_{\textit{ID},s}}))$: B first transforms a tuple of bit-strings $(\varTheta {\textit{PPK}^{\prime }_{\textit{ID}}},\varTheta {\textit{IPK}^{\prime }_{\textit{ID}}},\varTheta {\textit{TUPK}^{\prime }_{\textit{ID},s}})$ to get the corresponding tuple of polynomials $(\varXi {\textit{PPK}^{\prime }_{\textit{ID}}},\varXi {\textit{IPK}^{\prime }_{\textit{ID}}},\varXi {\textit{TUPK}^{\prime }_{\textit{ID},s}})$. B replaces the related tuples with $(\textit{ID},-,\varXi {\textit{PPK}^{\prime }_{\textit{ID}}})$ in ${L_{\textit{PSK}}},(\textit{ID},-,{\textit{IPK}^{\prime }_{\textit{ID}}})$ in ${L_{\textit{ISK}}}$, and $(\textit{ID},{T_{s}},-,\varXi {\textit{TUPK}^{\prime }_{\textit{ID},s}})$ in ${L_{\textit{TUK}}}$.
-
• Personal secret key corrupt query $(\textit{ID})$: If the Public key replace query $(\textit{ID})$ has never been requested, B uses $\textit{ID}$ to search ($\textit{ID}$, $\varXi {\textit{PSK}_{\textit{ID}}}$, $\varXi {\textit{PPK}_{\textit{ID}}}$) in ${L_{\textit{PSK}}}$. If it is found, B transforms ($\varXi {\textit{PSK}_{\textit{ID}}}$, $\varXi {\textit{PPK}_{\textit{ID}}}$) to return two encoded bit-strings ($\varTheta {\textit{PSK}_{\textit{ID}}}$, $\varTheta {\textit{PPK}_{\textit{ID}}}$). Otherwise, B carries out the following steps:
-
(1) Choose a new variate $\varXi T{G_{\textit{PSK},\textit{ID},1}}$ in ${G_{1}}$.
-
(2) Set two polynomials $\varXi {\textit{PSK}_{\textit{ID}}}=\varXi T{G_{\textit{PSK},\textit{ID},1}}$ and $\varXi {\textit{PPK}_{\textit{ID}}}=\varXi Q\cdot \varXi {\textit{PSK}_{\textit{ID}}}$, and add $(\textit{ID},\varXi {\textit{PSK}_{\textit{ID}}},\varXi {\textit{PPK}_{\textit{ID}}})$ in ${L_{\textit{PSK}}}$.
-
(3) Transform $(\varXi {\textit{PSK}_{\textit{ID}}},\varXi {\textit{PPK}_{\textit{ID}}})$ to return two encoded bit-strings $(\varTheta {\textit{PSK}_{\textit{ID}}},\varTheta {\textit{PPK}_{\textit{ID}}})$.
-
-
• Decrypting query $(\textit{ID},{T_{s}},\theta =(C,\textit{CT}))$: In this query’s k-th round, B carries out the following steps:
-
(1) By $\textit{ID}$ and ${T_{s}}$, B finds the associated private key tuple $(\varXi {\textit{PSK}_{\textit{ID}}},\varXi {\textit{ISK}_{\textit{ID}}},\varXi {\textit{TUK}_{\textit{ID},s}})$ in ${L_{\textit{PSK}}}$, ${L_{\textit{ISK}}}$ and ${L_{\textit{TUK}}}$.
-
(2) B transforms the ciphertext C to the polynomial $\varXi C$ in ${L_{1}}$ and sets three polynomials $\varXi {K_{1}}=\varXi {\textit{PSK}_{\textit{ID}}}\cdot \varXi C$, $\varXi {K_{2}}=\varXi {\textit{ISK}_{\textit{ID}}}\cdot \varXi C$ and $\varXi {K_{3}}=\varXi {\textit{TUK}_{\textit{ID},s}}\cdot \varXi C$. Moreover, B transforms $\varXi {K_{1}}$, $\varXi {K_{2}}$ and $\varXi {K_{3}}$ to obtain bit-strings $\varTheta {K_{1}}$, $\varTheta {K_{2}}$ and $\varTheta {K_{3}}$, respectively. Hence, B can gain the encryption key $\varTheta \textit{EK}=\varTheta {K_{1}}\oplus \varTheta {K_{2}}\oplus \varTheta {K_{3}}$. Finally, B returns the encryption key $\varTheta \textit{EK}$ and the plaintext $msg={D_{\varTheta EK}}(\textit{CT})$.
-
-
• Decrypting leak query $(\textit{ID},{T_{s}},{f_{\textit{DEC},k}},{h_{\textit{DEC},k}},k)$: In the Decrypting query’s k-th round of the user $\textit{ID}$ at period ${T_{s}}$, this query is allowed to be requested only once. B returns leaked information ($\varLambda {f_{\textit{DEC},k}}$, $\varLambda {h_{\textit{DEC},k}}$), where $\varLambda {f_{\textit{DEC},k}}={f_{\textit{DEC},k}}({\textit{PSK}_{\textit{ID},k,1}},{\textit{ISK}_{\textit{ID},k,1}})$ and $\varLambda {h_{\textit{DEC},k}}={h_{\textit{DEC},k}}({\textit{PSK}_{\textit{ID},k,2}},{\textit{ISK}_{\textit{ID},k,2}},{\textit{TUK}_{\textit{ID},s}})$.
-
-
– Challenge phase. ${A_{I}}$ sends a target identity ${\textit{ID}^{\ast }}$, a target period ${T_{{s^{\ast }}}}$ and a plaintext pair ($ms{g_{0}^{\ast }}$, $ms{g_{1}^{\ast }}$) to B. Here the Identity secret key query (${\textit{ID}^{\ast }}$) must have never been requested by ${A_{I}}$. B chooses an unbiased random bit $b\in \{0,1\}$ and carries out the $Encrypting$ algorithm with $({\textit{ID}^{\ast }},{T_{{s^{\ast }}}},({\textit{PPK}_{{\textit{ID}^{\ast }}}},{\textit{IPK}_{{\textit{ID}^{\ast }}}},{\textit{TUPK}_{{\textit{ID}^{\ast }},{s^{\ast }}}}),ms{g_{b}^{\ast }})$ to generate ${C^{\ast }}$, ${\textit{EK}^{\ast }}$ and ${\textit{CT}^{\ast }}={E_{{\textit{EK}^{\ast }}}}(ms{g_{b}^{\ast }})$. Finally, B returns the ciphertext tuple $({\textit{ID}^{\ast }},{T_{{s^{\ast }}}},\theta =({C^{\ast }},{\textit{CT}^{\ast }}))$ to the adversary.
-
– Guess phase. In this phase, ${A_{I}}$ must output a bit ${b^{\prime }}\in \{0,1\}$. If ${b^{\prime }}=b$, we say that it wins the game ${G_{\textit{LR-RCLE-ORA}}}$ and its advantage is $|\mathrm{Pr}[{b^{\prime }}=b]-1/2|$.
To evaluate the advantage that ${A_{I}}$ wins the game ${G_{\textit{LR-RCLE-ORA}}}$, we count the total number of elements in both ${L_{1}}$ and ${L_{2}}$. Subsequently, we count the maximal degrees of polynomials in ${L_{1}}$ and ${L_{2}}$, respectively.
-
■ The total number of elements in both L1 and L2:Let ${q_{O}}$ denote the total number of ${O_{1}}$, ${O_{2}}$ and ${O_{p}}$ queries. Let ${q_{I}}$, ${q_{T}}$ and ${q_{D}}$, respectively, be the query numbers of the Identity secret key query, Time update key query and Decrypting query. Since ${A_{I}}$ is allowed to request all queries at most q times, we have
-
• 7 and 2 elements are increased in ${L_{1}}$ and ${L_{2}}$, respectively, in the Setup phase.
-
• For each ${O_{1}}$, ${O_{2}}$ or ${O_{p}}$ query, at most 3 elements are increased in ${L_{1}}$ or ${L_{2}}$.
-
• For each Identity secret key query, at most 3 elements are increased in ${L_{1}}$.
-
• For each Time update key query, at most 3 elements are increased in ${L_{1}}$.
-
• For each Decrypting query, at most 4 elements are increased in ${L_{1}}$.
-
-
■ The maximal degrees of polynomials in L1 and L2:
-
(1) The maximal degree of polynomials in ${L_{1}}$ is 3 due to the following facts:
-
• In the Setup phase, 7 new variates (polynomials) $\varXi Q$, $\varXi \textit{KSK}$, $\varXi \textit{TSK}$, $\varXi M$, $\varXi N$, $\varXi R$ and $\varXi S$ are initially increased in ${L_{1}}$. All these polynomials have degree 1.
-
• For the ${O_{1}}$ query, $\varXi {G_{1,Q,l,3}}$ has the maximal degree of $\varXi {G_{1,Q,l,1}}$ and $\varXi {G_{1,Q,l,2}}$.
-
• For the Identity secret key query, $\varXi {\textit{TG}_{\textit{ISK},i,1}}$, $\varXi \textit{TID}$ and $\varXi {\textit{ISK}_{\textit{ID}}}$ have degrees 1, 1 and 3, respectively.
-
• For the Time update key query, $\varXi {\textit{TG}_{\textit{TUK},\textit{ID},j,1}}$, $\varXi \textit{TTD}$ and $\varXi {\textit{TUK}_{\textit{ID},t}}$ have degrees 1, 1 and 3, respectively.
-
-
(2) The maximal degree of polynomials in ${L_{2}}$ is 6 by the following facts:
-
• In the Setup phase, $\varXi \textit{KPK}$ and $\varXi \textit{TPK}$ have degree 2.
-
• For the ${O_{2}}$ query, $\varXi {G_{2,Q,l,3}}$ has the maximal degree of $\varXi {G_{2,Q,l,1}}$ and $\varXi {G_{2,Q,l,2}}$.
-
• For the ${O_{p}}$ query, $\varXi {G_{2,P,l,1}}$ has degree at most 6 because $\varXi {G_{2,P,l,1}}=\varXi {G_{1,P,l,1}}\cdot \varXi {G_{1,P,l,2}}$, and both $\varXi {G_{1,P,l,1}}$ and $\varXi {G_{1,P,l,2}}$ belong to ${L_{1}}$.
-
• For the Decrypting query, all $\varXi {K_{1}}$, $\varXi {K_{2}}$ and $\varXi {K_{3}}$ have degrees 2.
-
-
In the following, let us first evaluate the advantage that ${A_{I}}$ wins ${G_{\textit{LR-RCLE-ORA}}}$ without requesting any leak query. Subsequently, the advantage of ${A_{I}}$ is evaluated when it is allowed to request two kinds of leak queries (Identity secret key leak query and Decrypting leak query).
Because ${\textit{Adv}_{A-I-W}}\leqq O({q^{2}}/p)$ and ${A_{I}}$ can learn at most $2\lambda $ bits of $\textit{KSK}$ and ${\textit{ISK}_{{\textit{ID}^{\ast }}}}$ by the Identity secret key leak query and Decrypting leak query, we have
-
■ The advantage of ${A_{I}}$ without requesting any leak query: If either of the following two cases occurs, ${A_{I}}$ wins the game.Let ${\text{Pr}_{A-I-W}}$ and ${\textit{Adv}_{A-I-W}}$ be the probability and advantage, respectively, that ${A_{I}}$ wins the game without requesting any leak query. By Pr[Case 1] and Pr[Case 2], we have
-
Case 1: ${A_{I}}$ discovers a collision of two elements in ${L_{1}}$ or ${L_{2}}$. Let us first evaluate the collision probability in ${L_{1}}$. Let n be the number of all variates in ${L_{1}}$ and B selects n random values ${v_{l}}\in {Z_{p}^{\ast }}$ for $l=1,2,\dots ,n$. Let $\varXi {G_{1,i}}$ and $\varXi {G_{1,j}}$ be any two distinct polynomials in ${L_{1}}$. B then computes $\varXi {G_{1,C}}({v_{1}},{v_{2}},\dots ,{v_{n}})=\varXi {G_{1,i}}-\varXi {G_{1,j}}$. If $\varXi {G_{1,C}}({v_{1}},{v_{2}},\dots ,{v_{n}})=0$, it is said that the collision occurs. By Lemma 2, the probability of $\varXi {G_{1,C}}({v_{1}},{v_{2}},\dots ,{v_{n}})=0$ is at most $3/p$ because the maximal polynomial degree in ${L_{1}}$ is 3 and no information $(\lambda =0)$ is leaked. Since there are $\left(\genfrac{}{}{0pt}{}{|{L_{1}}|}{2}\right)$ distinct pairs $(\varXi {G_{1,i}},\varXi {G_{1,j}})$ in ${L_{1}}$, the collision probability is $(3/p)\left(\genfrac{}{}{0pt}{}{|{L_{1}}|}{2}\right)$. Similarly, the collision probability in ${L_{2}}$ is $(6/p)\left(\genfrac{}{}{0pt}{}{|{L_{2}}|}{2}\right)$. As mentioned earlier, we have $|{L_{1}}|+|{L_{2}}|\leqq 4q$. Let the probability of Case 1 be denoted by Pr[Case 1]. Then we have
-
Case 2: If Case 1 does not occur and ${A_{I}}$ gets no leaked information, the success probability of ${b^{\prime }}=b$ is $1/2$ in the Guess phase. Let Pr[Case 2] denote the success probability that Case 2 occurs. Then we have $\Pr [\text{Case}\hspace{2.5pt}2]\leqq 1/2$.
\[\begin{aligned}{}& {\text{Pr}_{A-I-W}}\leqq \Pr [\text{Case}\hspace{2.5pt}1]+\Pr [\text{Case}\hspace{2.5pt}2]\leqq 96{q^{2}}/p+(1/2),\\ {} & {\textit{Adv}_{A-I-W}}\leqq \big|96{q^{2}}/p+(1/2)-(1/2)\big|=96{q^{2}}/p=O\big({q^{2}}/p\big).\end{aligned}\]Hence, ${\textit{Adv}_{A-I-W}}$ is negligible if $q=\textit{poly}(\log p)$. -
-
■ The advantage of ${A_{I}}$ with requesting two kinds of leak queries: ${A_{I}}$ can obtain leaked information of related secret keys by the Identity secret key leak query and Decrypting leak query.Let ${\text{Pr}_{A-I}}$ and ${\textit{Adv}_{A-I}}$ be the probability and advantage, respectively, that ${A_{I}}$ wins ${G_{\textit{LR-RCLE-ORA}}}$ with requesting the Identity secret key leak query and Decrypting leak query. If ${A_{I}}$ can obtain the KGC’s secret key $\textit{KSK}$ or the target user’s identity key ${\textit{ISK}_{{\textit{ID}^{\ast }}}}$, ${A_{I}}$ may decrypt the message. Three events are defined as below:
-
$(1)$ Identity secret key leak query $({f_{\textit{ISKE},i}},{h_{\textit{ISKE},i}},i)$: By this query, ${A_{I}}$ may derive leaked information $(\varLambda {f_{\textit{ISKE},i}},\varLambda {h_{\textit{ISKE},i}})$ such that $|{f_{\textit{ISKE},i}}|$, $|{h_{\textit{ISKE},i}}|\leqq \lambda $, where $\varLambda {f_{\textit{ISKE},i}}={f_{\textit{ISKE},i}}({\textit{KSK}_{i,1}})$ and $\varLambda {h_{\textit{ISKE},i}}={h_{\textit{ISKE},i}}({\textit{KSK}_{i,2}})$ that are discussed as below:
-
• $({\textit{KSK}_{i,1}},{\textit{KSK}_{i,2}})$: Indeed, the KGC’s secret key $\textit{KSK}$ has the property in the sense that $\textit{KSK}={\textit{KSK}_{0,1}}+{\textit{KSK}_{0,2}}={\textit{KSK}_{1,1}}+{\textit{KSK}_{1,2}}=\cdots ={\textit{KSK}_{i,1}}+{\textit{KSK}_{i,2}}$. By the refreshing technique, leaked information of ${\textit{KSK}_{i-1,1}}/{\textit{KSK}_{i-1,2}}$ is independent of that of ${\textit{KSK}_{i,1}}/{\textit{KSK}_{i,2}}$. Thus, ${A_{I}}$ may derive at most $2\lambda $ bits of KSK.
-
-
(2) Decrypting leak query $(\textit{ID},{T_{s}},{f_{\textit{DEC},k}},{h_{\textit{DEC},k}},k)$: As mentioned earlier, ${A_{I}}$ is not a legal user of the LR-RCLE-ORA scheme, but it may get the time update key ${\textit{TUK}_{\textit{ID},s}}$ of any user $\textit{ID}$ at any period ${T_{s}}$ from public channels. Also, ${A_{I}}$ may get the personal secret key ${\textit{PSK}_{\textit{ID}}}$ and the identity secret key ${\textit{ISK}_{\textit{ID}}}$ of any user $\textit{ID}$, but it is disallowed to get the identity secret key ${\textit{ISK}_{{\textit{ID}^{\ast }}}}$ of the target user ${\textit{ID}^{\ast }}$. Therefore, by this query, ${A_{I}}$ may derive leaked information $(\varLambda {f_{\textit{DEC},k}},\varLambda {h_{\textit{DEC},k}})$, where $\varLambda {f_{\textit{DEC},k}}={f_{\textit{DEC},k}}({\textit{ISK}_{{\textit{ID}^{\ast }},k,1}})$ and $\varLambda {h_{\textit{DEC},k}}={h_{\textit{DEC},k}}({\textit{ISK}_{{\textit{ID}^{\ast }},k,2}})$ that are discussed as below:
-
• $({\textit{ISK}_{{\textit{ID}^{\ast }},k,1}},{\textit{ISK}_{{\textit{ID}^{\ast }},k-1,2}})$: Indeed, the identity secret key ${\textit{ISK}_{{\textit{ID}^{\ast }}}}$ satisfies ${\textit{ISK}_{{\textit{ID}^{\ast }}}}={\textit{ISK}_{{\textit{ID}^{\ast }},0,1}}+{\textit{ISK}_{{\textit{ID}^{\ast }},0,2}}={\textit{ISK}_{{\textit{ID}^{\ast }},1,1}}+{\textit{ISK}_{{\textit{ID}^{\ast }},1,2}}=\cdots ={\textit{ISK}_{{\textit{ID}^{\ast }},k,1}}+{\textit{ISK}_{{\textit{ID}^{\ast }},k,2}}$. Bythe refreshing technique, leaked information of ${\textit{ISK}_{{\textit{ID}^{\ast }},k-1,1}}/{\textit{ISK}_{{\textit{ID}^{\ast }},k-1,2}}$ is independent of that of ${\textit{ISK}_{{\textit{ID}^{\ast }},k,1}}/{\textit{ISK}_{{\textit{ID}^{\ast }},k,2}}$. Thus, ${A_{I}}$ may derive at most $2\lambda $ bits of ${\textit{ISK}_{{\textit{ID}^{\ast }}}}$.
-
Hence, the advantage ${\text{Pr}_{A-I}}$ is Pr[$\textit{ECB}$] and the following inequality holds:-
(1) Let $\textit{EKSK}$ denote the event that ${A_{I}}$ gets the $\textit{KSK}$ by $\varLambda {f_{\textit{ISKE},i}}$ and $\varLambda {h_{\textit{ISKE},i}}$. Additionally, $\overline{\textit{EKSK}}$ is the complement event of $\textit{EKSK}$.
-
(2) Let $\textit{EISK}$ that ${A_{I}}$ gets the ${\textit{ISK}_{{\textit{ID}^{\ast }}}}$ by $\varLambda {f_{\textit{DEC},k}}$ and $\varLambda {h_{\textit{DEC},k}}$. Additionally, $\overline{\textit{EISK}}$ is the complement event of $\textit{EISK}$.
-
(3) Let $\textit{ECB}$ denote the event that ${A_{I}}$ outputs a correct ${b^{\prime }}$.
\[\begin{aligned}{}{\text{Pr}_{A-I}}& =\Pr [\textit{ECB}]\\ {} & =\Pr \big[\textit{ECB}\wedge (\textit{EKSK}\vee \textit{EISK})\big]+\Pr \big[\textit{ECB}\wedge (\overline{\textit{EKSK}}\wedge \overline{\textit{EISK}})\big]\\ {} & \leqq \Pr \big[(\textit{EKSK}\vee \textit{EISK})\big]+\Pr \big[\textit{ECB}\wedge (\overline{\textit{EKSK}}\wedge \overline{\textit{EISK}})\big].\end{aligned}\]For the event $(\overline{\textit{EKSK}}\wedge \overline{\textit{EISK}})$, ${A_{I}}$ can’t obtain the useful information to output a correct bit ${b^{\prime }}$. ${A_{I}}$ has probability 1/2 to guess the correct bit, so $\Pr [\textit{ECB}\wedge (\overline{\textit{EKSK}}\wedge \overline{\textit{EISK}})]$ is still 1/2 on average. Thus, we have: -
\[ {\textit{Adv}_{A-I}}\leqq {\textit{Adv}_{A-I-W}}\cdot {2^{2\lambda }}\leqq O\big(\big({q^{2}}/p\big)\cdot {2^{2\lambda }}\big).\]
By Corollary 1, ${\textit{Adv}_{A-I}}$ is negligible if $\lambda <(1-\varepsilon )\log p$. □Theorem 2.
In the GBG model, the proposed LR-RCLE-ORA scheme is semantically secure against chosen cipher-text attacks against a revoked user $({A_{\textit{II}}})$ in the security game ${G_{\textit{LR-RCLE-ORA}}}$.
Proof.
Let ${A_{\textit{II}}}$ be a revoked user of the security game ${G_{\textit{LR-RCLE-ORA}}}$ played with a challenger B. ${A_{\textit{II}}}$ may issue various queries to B at most q times in the game. This game consists of four phases as follows:
-
– Setup phase: The phase is the same as that in the proof in Theorem 1. Additionally, B sends the time secret key $\textit{TSK}$ to ${A_{\textit{II}}}$ since it is a revoked user.
-
– Query phase: In this phase, ${A_{\textit{II}}}$ can adaptively issue various queries to B at most q times. ${A_{ll}}$ queries are identical to those queries in the proof of Theorem 1. Note that ${A_{\textit{II}}}$ knows the personal secret key ${\textit{PSK}_{\textit{ID}}}$ and the identity secret key ${\textit{ISK}_{\textit{ID}}}$ of any user $\textit{ID}$. Also, ${A_{\textit{II}}}$ may get the time update key ${\textit{TUK}_{\textit{ID},s}}$ of any user $\textit{ID}$ at any period ${T_{s}}$, except ${\textit{TUK}_{{\textit{ID}^{\ast }},{s^{\ast }}}}$ of the target user ${\textit{ID}^{\ast }}$ at target period ${T_{{s^{\ast }}}}$.
-
– Challenge phase: ${A_{\textit{II}}}$ sends a target identity ${\textit{ID}^{\ast }}$, a target period ${T_{{s^{\ast }}}}$ and a plaintext pair ($ms{g_{0}^{\ast }},ms{g_{1}^{\ast }}$) to B. Here the Time update key query (${\textit{ID}^{\ast }},{T_{s}^{\ast }}$) must have never been requested by ${A_{\textit{II}}}$. B chooses a unbiased random bit $b\in \{0,1\}$ and carries out the Encrypting algorithm with $({\textit{ID}^{\ast }},{T_{s}^{\ast }},({\textit{PPK}_{{\textit{ID}^{\ast }}}},{\textit{IPK}_{{\textit{ID}^{\ast }}}},{\textit{TUPK}_{{\textit{ID}^{\ast }},{s^{\ast }}}}),ms{g_{b}^{\ast }})$ to generate ${C^{\ast }}$, ${\textit{EK}^{\ast }}$ and ${\textit{CT}^{\ast }}={E_{{\textit{EK}^{\ast }}}}(ms{g_{b}^{\ast }})$. Finally, B returns the ciphertext tuple $({\textit{ID}^{\ast }},{T_{s}^{\ast }},\theta =({C^{\ast }},{\textit{CT}^{\ast }}))$ to ${A_{\textit{II}}}$.
-
– Guess phase: In this phase, ${A_{\textit{II}}}$ must output a bit ${b^{\prime }}\in \{0,1\}$. If ${b^{\prime }}=b$, we say that it wins the game ${G_{\textit{LR-RCLE-ORA}}}$ and its advantage is $|\Pr [{b^{\prime }}=b]-1/2|$.
In the following, let us first evaluate the advantage that ${A_{\textit{II}}}$ wins ${G_{\textit{LR-RCLE-ORA}}}$ without requesting any leak query. Subsequently, the advantage of ${A_{\textit{II}}}$ is evaluated when it is allowed to request the Time update key leak query.
Because ${\textit{Adv}_{A-\textit{II}-W}}\leqq O({q^{2}}/p)$ and ${A_{\textit{II}}}$ can learn at most $2\lambda $ bits of $\textit{TSK}$ by the Time update key leak query, we have
-
■ The advantage of ${A_{\textbf{\textit{II}}}}$ without requesting any leak query: Let ${\textit{Adv}_{A-\textit{II}-W}}$ be the advantage that ${A_{\textit{II}}}$ wins the game without requesting the Time update key leak query. By the similar evaluations as in the proof of Theorem 1, we have ${\textit{Adv}_{A-\textit{II}-W}}=O({q^{2}}/p)$.
-
■ The advantage of ${A_{\textbf{\textit{II}}}}$ with requesting the Time update key leak query: By the Time update key leak query (${f_{\textit{TUKE},j}},{h_{\textit{TUKE},j}}$, j), ${A_{\textit{II}}}$ may derive leaked information ($\varLambda {f_{\textit{TUKE},j}},\varLambda {h_{\textit{TUKE},j}}$) such that $|{f_{\textit{TUKE},j}}|$, $|{h_{\textit{TUKE},j}}|\leqq \lambda $, where $\varLambda {f_{\textit{TUKE},j}}={f_{\textit{TUKE},j}}({\textit{TSK}_{j,1}})$ and $\varLambda {h_{\textit{TUKE},j}}={h_{\textit{TUKE},j}}({\textit{TSK}_{j,2}})$. Indeed, the time secret key $\textit{TSK}$ has the property in the sense that $\textit{TSK}={\textit{TSK}_{0,1}}+{\textit{TSK}_{0,2}}={\textit{TSK}_{1,1}}+{\textit{TSK}_{1,2}}=\cdots ={\textit{TSK}_{i,1}}+{\textit{TSK}_{i,2}}$. By the refreshing technique, leaked information of ${\textit{TSK}_{i-1,1}}/{\textit{TSK}_{i-1,2}}$ is independent of that of ${\textit{TSK}_{i,1}}/{\textit{TSK}_{i,2}}$. Thus, ${A_{\textit{II}}}$ may derive at most $2\lambda $ bits of $\textit{TSK}$.Let ${\text{Pr}_{A-\textit{II}}}$ and ${\textit{Adv}_{A-\textit{II}}}$ be the probability and advantage, respectively, that ${A_{\textit{II}}}$ wins ${G_{\textit{LR-RCLE-ORA}}}$ with requesting the Time update key leak query. Two events are defined as below:Hence, the advantage ${\text{Pr}_{A-\textit{II}}}$ is Pr[$\textit{ECB}$] and the following inequality holds:
-
(1) Let $\textit{ETSK}$ denote the event that ${A_{\textit{II}}}$ gets the time secret key $\textit{TSK}$ by ${f_{\textit{TUKE},j}}$ and ${h_{\textit{TUKE},j}}$. Additionally, $\overline{\textit{ETSK}}$ is the complement event of $\textit{ETSK}$.
-
(2) Let $\textit{ECB}$ denote the event that ${A_{\textit{II}}}$ outputs a correct ${b^{\prime }}$.
\[\begin{aligned}{}{\text{Pr}_{A-\textit{II}}}& =\Pr [\textit{ECB}]\\ {} & =\Pr [\textit{ECB}\wedge \textit{ETSK}]+\Pr [\textit{ECB}\wedge \overline{\textit{ETSK}}]\\ {} & \leqq \Pr [\textit{ETSK}]+\Pr [\textit{ECB}\wedge \overline{\textit{ETSK}}].\end{aligned}\]For the event $\overline{\textit{ETSK}}$, ${A_{\textit{II}}}$ can’t obtain the useful information to output a correct bit ${b^{\prime }}$. ${A_{\textit{II}}}$ has probability $1/2$ to guess the correct bit, so $\Pr [\textit{ECB}\wedge \overline{\textit{ETSK}}]$ is still $1/2$ on average. Thus, we have -
\[ {\textit{Adv}_{A-\textit{II}}}\leqq {\textit{Adv}_{A-\textit{II}-W}}\cdot {2^{2\lambda }}\leqq O\big(\big({q^{2}}/p\big)\cdot {2^{2\lambda }}\big).\]
By Corollary 1, ${\textit{Adv}_{A-\textit{II}}}$ is negligible if $\lambda <(1-\varepsilon )\log p$. □Theorem 3.
In the GBG model, the proposed LR-RCLE-ORA scheme is semantically secure against chosen cipher-text attacks against an honest-but-curious KGC $({A_{\textit{III}}})$ in the security game ${G_{\textit{LR-RCLE-ORA}}}$.
Proof.
Let ${A_{\textit{III}}}$ be an honest-but-curious KGC of the security game ${G_{\textit{LR-RCLE-ORA}}}$ played with a challenger B. ${A_{\textit{III}}}$ may issue various queries to B at most q times in the game. This game consists of four phases as follows:
In the following, let us first evaluate the advantage that ${A_{\textit{III}}}$ wins ${G_{\textit{LR-RCLE-ORA}}}$ without requesting any leak query. Subsequently, the advantage of ${A_{\textit{III}}}$ is evaluated when it is allowed to request the Decrypting leak query $(\textit{ID},{T_{s}},{f_{\textit{DEC},k}},{h_{\textit{DEC},k}},k)$.
Because ${\textit{Adv}_{A-\textit{III}-W}}\leqq O({q^{2}}/p)$ and ${A_{\textit{III}}}$ can learn at most $2\lambda $ bits of $\textit{PSK}$ by the Decrypting leak query, we have
-
– Setup phase: The phase is the same as that in the proof in Theorem 1. Additionally, B sends the KGC’s secret key $\textit{KSK}$ and time secret key $\textit{TSK}$ to ${A_{\textit{III}}}$ since it is an honest-but-curious KGC.
-
– Query phase: In this phase, ${A_{\textit{III}}}$ can adaptively issue various queries to B at most q times. All queries are identical to those queries in the proof of Theorem 1. Note that ${A_{\textit{III}}}$ knows the KGC’s secret key $\textit{KSK}$ and time secret key $\textit{TSK}$ so that it can get the identity secret key ${\textit{ISK}_{\textit{ID}}}$ and time update key ${\textit{TUK}_{\textit{ID},s}}$ of any user $\textit{ID}$ for any period ${T_{s}}$. Also, ${A_{\textit{III}}}$ may get the personal secret key ${\textit{PSK}_{\textit{ID}}}$ of any user $\textit{ID}$, except ${\textit{PSK}_{{\textit{ID}^{\ast }}}}$ of the target user ${\textit{ID}^{\ast }}$.
-
– Challenge phase: ${A_{\textit{III}}}$ sends a target identity ${\textit{ID}^{\ast }}$, a target period ${T_{{s^{\ast }}}}$ and a plaintext pair ($ms{g_{0}^{\ast }},ms{g_{1}^{\ast }}$) to B. Here both the Personal secret key corrupt query (${\textit{ID}^{\ast }}$) and the Public key replace query $({\textit{ID}^{\ast }},{T_{s\ast }},({\textit{PPK}^{\prime }_{{\textit{ID}^{\ast }}}},{\textit{IPK}^{\prime }_{{\textit{ID}^{\ast }}}},{\textit{TUPK}^{\prime }_{{\textit{ID}^{\ast }},{s^{\ast }}}}))$ must have never been requested by ${A_{\textit{III}}}$. B chooses an unbiased random bit $b\in \{0,1\}$ and carries out the Encrypting algorithm with $({\textit{ID}^{\ast }},{T_{s}^{\ast }},({\textit{PPK}_{{\textit{ID}^{\ast }}}},{\textit{IPK}_{{\textit{ID}^{\ast }}}},{\textit{TUPK}_{{\textit{ID}^{\ast }},{s^{\ast }}}}),ms{g_{b}^{\ast }})$ to generate ${C^{\ast }}$, ${\textit{EK}^{\ast }}$ and ${\textit{CT}^{\ast }}={E_{{\textit{EK}^{\ast }}}}(ms{g_{b}^{\ast }})$. Finally, B returns the ciphertext tuple $({\textit{ID}^{\ast }},{T_{s}^{\ast }},\theta =({C^{\ast }},{\textit{CT}^{\ast }}))$ to ${A_{\textit{III}}}$.
-
– Guess phase: In this phase, ${A_{\textit{III}}}$ must output a bit ${b^{\prime }}\in \{0,1\}$. If ${b^{\prime }}=b$, we say that it wins the game ${G_{\textit{LR-RCLE-ORA}}}$ and its advantage is $|\Pr [{b^{\prime }}=b]-1/2|$.
-
■ The advantage of ${A_{\textbf{\textit{III}}}}$ without requesting any leak query: Let ${\textit{Adv}_{A-\textit{III}-W}}$ be the advantage that ${A_{\textit{III}}}$ wins the game without requesting the Decrypting leak query. By the similar evaluations as in the proof of Theorem 1, we have ${\textit{Adv}_{A-\textit{III}-W}}=O({q^{2}}/p)$.
-
■ The advantage of ${A_{\textbf{\textit{III}}}}$ with requesting the Decrypting leak query: By the Decrypting leak query $(\textit{ID},{T_{s}},{f_{\textit{DEC},k}},{h_{\textit{DEC},k}},k)$, ${A_{\textit{III}}}$ may derive leaked information $(\varLambda {f_{\textit{DEC},k}},\varLambda {h_{\textit{DEC},k}})$ such that $|{f_{\textit{DEC},k}}|,|{h_{\textit{DEC},k}}|\leqq \lambda $, where $\varLambda {f_{\textit{DEC},k}}={f_{\textit{DEC},k}}({\textit{PSK}_{\textit{ID},k,1}})$ and $\varLambda {h_{\textit{DEC},k}}={h_{\textit{DEC},k}}({\textit{PSK}_{\textit{ID},k,2}})$. Note that ${A_{\textit{III}}}$ may get the personal secret key ${\textit{PSK}_{\textit{ID}}}$ of any user $\textit{ID}$, except ${\textit{PSK}_{{\textit{ID}^{\ast }}}}$ of the target user ${\textit{ID}^{\ast }}$. For leakage resilient property, ${A_{\textit{III}}}$ can obtain leaked information of the target user’s ${\textit{PSK}_{{\textit{ID}^{\ast }}}}=({\textit{PSK}_{{\textit{ID}^{\ast }},k,1}},{\textit{PSK}_{{\textit{ID}^{\ast }},k,2}})$ used in the Decrypting algorithm’s k-th round of the target user. Indeed, the personal secret key ${\textit{PSK}_{\textit{ID}}}$ has the property in the sense that ${\textit{PSK}_{{\textit{ID}^{\ast }}}}={\textit{PSK}_{{\textit{ID}^{\ast }},0,1}}+{\textit{PSK}_{{\textit{ID}^{\ast }},0,2}}={\textit{PSK}_{{\textit{ID}^{\ast }},1,1}}+{\textit{PSK}_{{\textit{ID}^{\ast }},1,2}}=\cdots ={\textit{PSK}_{{\textit{ID}^{\ast }},k,1}}+{\textit{PSK}_{{\textit{ID}^{\ast }},k,2}}$. By the refreshing technique, leaked information of ${\textit{PSK}_{{\textit{ID}^{\ast }},k-1,1}}/{\textit{PSK}_{{\textit{ID}^{\ast }},k-1,2}}$ is independent of that of ${\textit{PSK}_{{\textit{ID}^{\ast }},k,1}}/{\textit{PSK}_{{\textit{ID}^{\ast }},k,2}}$. Thus, ${A_{\textit{III}}}$ may derive at most $2\lambda $ bits of ${\textit{PSK}_{{\textit{ID}^{\ast }}}}$.Let ${\text{Pr}_{A-\textit{III}}}$ and ${\textit{Adv}_{A-\textit{III}}}$ be the probability and advantage, respectively, that ${A_{\textit{III}}}$ wins ${G_{\textit{LR-RCLE-ORA}}}$ with requesting the Decrypting leak query. Two events are defined as below:Hence, the advantage ${\text{Pr}_{A-\textit{III}}}$ is Pr[$\textit{ECB}$] and the following inequality holds.
-
(1) Let $\textit{EPSK}$ denote the event that ${A_{\textit{III}}}$ gets the personal secret key ${\textit{PSK}_{{\textit{ID}^{\ast }}}}$ by ${f_{\textit{DEC},k}}$ and ${h_{\textit{DEC},k}}$. Additionally, $\overline{\textit{EPSK}}$ is the complement event of $\textit{EPSK}$.
-
(2) Let $\textit{ECB}$ denote the event that ${A_{\textit{III}}}$ outputs a correct ${b^{\prime }}$.
\[\begin{aligned}{}{\text{Pr}_{A-\textit{III}}}& =\Pr [\textit{ECB}]\\ {} & =\Pr [\textit{ECB}\wedge \textit{EPSK}]+\Pr [\textit{ECB}\wedge \overline{\textit{EPSK}}]\\ {} & \leqq \Pr [\textit{EPSK}]+\Pr [\textit{ECB}\wedge \overline{\textit{EPSK}}].\end{aligned}\]For the event $\overline{\textit{EPSK}}$, ${A_{\textit{III}}}$ can’t obtain the useful information to output a correct bit ${b^{\prime }}$. ${A_{\textit{III}}}$ has probability 1/2 to guess the correct bit, so $\Pr [\textit{ECB}\wedge \overline{\textit{EPSK}}]$ is still 1/2 on average. Thus, we have -
\[ {\textit{Adv}_{A-\textit{III}}}\leqq {\textit{Adv}_{A-\textit{III}-W}}\cdot {2^{2\lambda }}\leqq O\big(\big({q^{2}}/p\big)\cdot {2^{2\lambda }}\big).\]
By Corollary 1, ${\textit{Adv}_{A-\textit{III}}}$ is negligible if $\lambda <(1-\varepsilon )\log p$. □6 Comparisons
Here, let’s first present the computation notations of several operations in bilinear groups. By employing the simulation experiences in Li et al. (2021), Table 1 lists two kinds of time-consuming operations and their computational time (in milliseconds). The environment of simulation experiences is a platform with the Intel Core i7-8550U CPU 1.80 GHz processor. The selection of security parameters are ${F_{p}}$, ${G_{1}}$ and ${G_{2}}$. Here, ${F_{p}}$ is a finite field which consists of the set of integers $\{0,1,\dots ,p-1\}$, where p is a 256-bit prime number. And, ${G_{1}}$ and ${G_{2}}$ are groups with 224-bit prime order over the finite field ${F_{p}}$. It is worth mentioning that the computation of a one-way hash function, an addition on an additive group ${G_{1}}$ and a multiplication on a multiplicative group ${G_{2}}$ are omitted because their computational costs are small and negligible.
Table 1
Computational time (in millisecond) of two time-consuming operations.
| Notation | Operation | Computational time |
| ${T_{p}}$ | a bilinear pairing $\hat{e}:{G_{1}}\times {G_{1}}\to {G_{2}}$ | 7.84 ms |
| a scalar multiplication on an additive group ${G_{1}}$ | ||
| ${T_{me}}$ | or | 0.48 ms |
| an exponentiation on a multiplicative group ${G_{2}}$ |
Table 2 lists the comparisons of our LR-RCLE-ORA scheme with several RCLE and LR-CLE schemes (Tsai and Tseng, 2015; Xiong et al., 2013; Wu et al., 2018) in terms of encryption cost (time), decryption cost (time), security proof model, revocation property, outsourced revocation, resisting side-channel attacks and leakage resilience model. Note that a user’s private key in Xiong et al.’s LR-CLE scheme (2013) is a vector with $n\geqq 2$ elements (here, let $n=2$). As compared to the bounded leakage property of Xiong et al.’s LR-CLE scheme (2013), Wu et al.’s scheme and ours possess continual leakage property and are practical for applications. To resist side-channel attacks, our scheme requires some extra computation costs than the RCLE scheme in Tsai and Tseng (2015). As compared with the LR-CLE scheme (Wu et al., 2018), our scheme requires one ${T_{p}}$ for encryption cost and decryption cost, respectively, but our scheme offers outsourced revocation functionality to reduce the computational burden of the KGC for generating all non-revoked users’ time update keys. By Table 2, even though the computational cost of our scheme is worse than the other schemes, our scheme possesses four complete properties, namely, revocation property, outsourced revocation, resisting side-channel attacks and continual leakage property. We emphasize that our scheme is the first LR-RCLE-ORA scheme resisting side-channel attacks while possessing continual leakage property.
Table 2
Comparisons between our scheme and the previously proposed schemes.
| Tsai and Tseng’s RCLE scheme (Tsai and Tseng, 2015) | Xiong et al.’s LR-CLE scheme (Xiong et al., 2013) | Wu et al.’s LR-CLE scheme (Wu et al., 2018) | Our LR-RCLE-ORA scheme | |
| Encryption cost | $3{T_{me}}+{T_{p}}$ | $6{T_{me}}$ | $4{T_{me}}+{T_{p}}$ | $4{T_{me}}+2{T_{p}}$ |
| (9.28 ms) | (2.88 ms) | (9.76 ms) | (17.6 ms) | |
| Decryption cost | $2{T_{me}}+{T_{p}}$ | $4{T_{p}}$ | $4{T_{me}}+4{T_{p}}$ | $4{T_{me}}+5{T_{p}}$ |
| (8.8 ms) | (31.36 ms) | (33.28 ms) | (41.12 ms) | |
| Security proof model | Random oracle model | Standard model (Dual system) | GBG model | GBG model |
| Revocation property | Yes | No | No | Yes |
| Outsourced revocation | No | No | No | Yes |
| Resisting side-channel attacks | No | Yes | Yes | Yes |
| Leakage resilience model | No | Bounded | Continual | Continual |
7 Conclusions
In this paper, the first leakage-resilient revocable certificateless encryption scheme with an outsourced revocation authority (LR-RCLE-ORA) was proposed. As compared to previous RCLE and LR-CLE schemes, our scheme possesses several merits. (1) It can resist side-channel attacks and has leakage resilience properties. (2) The revocation functionality is outsourced to the ORA to alleviate the computational load of the KGC. (3) It permits adversaries to continually extract partial ingredients of secret keys and offers the overall unbounded leakage property. By extending the adversary models of RCLE and LR-CLE schemes, a new adversary model was defined while three kinds of leak queries are added, namely, Identity secret key leak query, Time update key leak query and decrypting leak query. In the GBG model, the security of the proposed scheme is shown to be semantically secure against chosen cipher-text attacks for three kinds of adversaries, namely, outsider, revoked user and honest-but-curious KGC.
