Leakage-Resilient Revocable Certificateless Encryption with an Outsourced Revocation Authority

Abstract

To resolve both certificate management and key escrow problems, a certificateless public-key system (CLPKS) has been proposed. However, a CLPKS setting must provide a revocation mechanism to revoke compromised users. Thus, a revocable certificateless public-key system (RCLPKS) was presented to address the revocation issue and, in such a system, the key generation centre (KGC) is responsible to run this revocation functionality. Furthermore, a RCLPKS setting with an outsourced revocation authority (ORA), named RCLPKS-ORA setting, was proposed to employ the ORA to alleviate the KGC’s computational burden. Very recently it was noticed that adversaries may adopt side-channel attacks to threaten these existing conventional public-key systems (including CLPKS, RCLPKS and RCLPKS-ORA). Fortunately, leakage-resilient cryptography offers a solution to resist such attacks. In this article, the first leakage-resilient revocable certificateless encryption scheme with an ORA, termed LR-RCLE-ORA scheme, is proposed. The proposed scheme is formally shown to be semantically secure against three types of adversaries in the RCLPKS and RCLPKS-ORA settings while resisting side-channel attacks. In the proposed scheme, adversaries are allowed to continually extract partial ingredients of secret keys participated in various computational algorithms of the proposed scheme while retaining its security.

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 $\mathit{f}\mathrm{(}\mathit{\text{SK}}\mathrm{)}$ , where $\mathit{\text{SK}}$ denotes the involved secret keys and $\mathit{f}\mathrm{(}\mathit{\text{SK}}\mathrm{)}$ 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 ${\mathit{G}}_1$ be an additive group of a prime order p and Q be a generator of ${\mathit{G}}_1$ . Let ${\mathit{G}}_2$ be a multiplicative group of the same order p. A bilinear admissible pairing $\hat{\mathit{e}}:{\mathit{G}}_1\times {\mathit{G}}_1\to {\mathit{G}}_2$ possesses the following properties:

• –

  Bilinear: for $\mathit{r}\mathrm{,}\mathit{s}\in {\mathit{Z}}_{\mathit{p}}^{\ast }$ , $\hat{\mathit{e}}\mathrm{(}\mathit{r}·\mathit{Q}\mathrm{,}\mathit{s}·\mathit{Q}\mathrm{)}=\hat{\mathit{e}}{\mathrm{(}\mathit{Q}\mathrm{,}\mathit{Q}\mathrm{)}}^{\mathit{r}\mathit{s}}$ ;

  –

  Non-degenerate: $\hat{\mathit{e}}\mathrm{(}\mathit{Q}\mathrm{,}\mathit{Q}\mathrm{)}\ne 1$ ;

  –

  Efficiently computable: for $\mathit{R}\mathrm{,}\mathit{S}\in {\mathit{G}}_1\mathrm{,}\hat{\mathit{e}}\mathrm{(}\mathit{R}\mathrm{,}\mathit{S}\mathrm{)}$ is efficiently computed.

  We say that $\{{\mathit{G}}_1\mathrm{,}{\mathit{G}}_2\mathrm{,}\mathit{p}\mathrm{,}\mathit{Q}\mathrm{,}\hat{\mathit{e}}\}$ are the bilinear group parameters. A reader may refer to Boneh and Franklin (2001), Scott (2011) for detailed definitions of bilinear groups.

  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 $\{{\mathit{G}}_1\mathrm{,}{\mathit{G}}_2\mathrm{,}\mathit{p}\mathrm{,}\mathit{Q}\mathrm{,}\hat{\mathit{e}}\}$ be the bilinear group parameters and let each element in two groups ${\mathit{G}}_1$ and ${\mathit{G}}_2$ be represented by distinct bit-strings. In such a case, a random injective mapping ${\mathrm{\Phi }}_1:{\mathit{Z}}_{\mathit{p}}^{\ast }\to \mathit{\xi }{\mathit{G}}_1$ is used to encode all elements of ${\mathit{G}}_1$ , where $\mathit{\xi }{\mathit{G}}_1$ denotes the set of the encoded bit-strings of ${\mathit{G}}_1$ . By the same reason, the other random injective mapping ${\mathrm{\Phi }}_2:{\mathit{Z}}_{\mathit{p}}^{\ast }\to \mathit{\xi }{\mathit{G}}_2$ is employed to encode all elements of ${\mathit{G}}_2$ , where $\mathit{\xi }{\mathit{G}}_2$ denotes the set of the encoded bit-strings of ${\mathit{G}}_2$ . Two sets $\mathit{\xi }{\mathit{G}}_1$ and $\mathit{\xi }{\mathit{G}}_2$ satisfy $|\mathit{\xi }{\mathit{G}}_1|=|\mathit{\xi }{\mathit{G}}_2|=\mathit{p}$ and $\mathit{\xi }{\mathit{G}}_1\cap \mathit{\xi }{\mathit{G}}_2=\mathit{\varphi }$ . In addition, let three operations ${\mathit{O}}_1$ , ${\mathit{O}}_2$ and ${\mathit{O}}_{\mathit{p}}$ , respectively, denote the addition of ${\mathit{G}}_1$ , the multiplication of ${\mathit{G}}_2$ and the bilinear pairing $\hat{\mathit{e}}$ . To perform these group operations, an adversary must request the associated operations (oracles) ${\mathit{O}}_1$ , ${\mathit{O}}_2$ and ${\mathit{O}}_{\mathit{p}}$ which are defined as below:

• ■

  The maximal degrees of polynomials in L ₁ and L ₂ :

In the following, let us first evaluate the advantage that ${\mathit{A}}_{\mathit{I}}$ wins ${\mathit{G}}_{\mathit{\text{LR-RCLE-ORA}}}$ without requesting any leak query. Subsequently, the advantage of ${\mathit{A}}_{\mathit{I}}$ is evaluated when it is allowed to request two kinds of leak queries (Identity secret key leak query and Decrypting leak query).

• ■

The advantage of ${\mathit{A}}_{\mathit{I}}$ without requesting any leak query: If either of the following two cases occurs, ${\mathit{A}}_{\mathit{I}}$ wins the game.

• Case 1:

${\mathit{A}}_{\mathit{I}}$ discovers a collision of two elements in ${\mathit{L}}_1$ or ${\mathit{L}}_2$ . Let us first evaluate the collision probability in ${\mathit{L}}_1$ . Let n be the number of all variates in ${\mathit{L}}_1$ and B selects n random values ${\mathit{v}}_{\mathit{l}}\in {\mathit{Z}}_{\mathit{p}}^{\ast }$ for $\mathit{l}=1\mathrm{,}2\mathrm{,}\dots \mathrm{,}\mathit{n}$ . Let $\mathit{\Xi }{\mathit{G}}_{1\mathrm{,}\mathit{i}}$ and $\mathit{\Xi }{\mathit{G}}_{1\mathrm{,}\mathit{j}}$ be any two distinct polynomials in ${\mathit{L}}_1$ . B then computes $\mathit{\Xi }{\mathit{G}}_{1\mathrm{,}\mathit{C}}\mathrm{(}{\mathit{v}}_1\mathrm{,}{\mathit{v}}_2\mathrm{,}\dots \mathrm{,}{\mathit{v}}_{\mathit{n}}\mathrm{)}=\mathit{\Xi }{\mathit{G}}_{1\mathrm{,}\mathit{i}}-\mathit{\Xi }{\mathit{G}}_{1\mathrm{,}\mathit{j}}$ . If $\mathit{\Xi }{\mathit{G}}_{1\mathrm{,}\mathit{C}}\mathrm{(}{\mathit{v}}_1\mathrm{,}{\mathit{v}}_2\mathrm{,}\dots \mathrm{,}{\mathit{v}}_{\mathit{n}}\mathrm{)}=0$ , it is said that the collision occurs. By Lemma 2, the probability of $\mathit{\Xi }{\mathit{G}}_{1\mathrm{,}\mathit{C}}\mathrm{(}{\mathit{v}}_1\mathrm{,}{\mathit{v}}_2\mathrm{,}\dots \mathrm{,}{\mathit{v}}_{\mathit{n}}\mathrm{)}=0$ is at most $3\mathrm{/}\mathit{p}$ because the maximal polynomial degree in ${\mathit{L}}_1$ is 3 and no information $\mathrm{(}\mathit{\lambda }=0\mathrm{)}$ is leaked. Since there are $\left(\genfrac{}{}{0ex}{}{|{\mathit{L}}_1|}{2}\right)$ distinct pairs $\mathrm{(}\mathit{\Xi }{\mathit{G}}_{1\mathrm{,}\mathit{i}}\mathrm{,}\mathit{\Xi }{\mathit{G}}_{1\mathrm{,}\mathit{j}}\mathrm{)}$ in ${\mathit{L}}_1$ , the collision probability is $\mathrm{(}3\mathrm{/}\mathit{p}\mathrm{)}\left(\genfrac{}{}{0ex}{}{|{\mathit{L}}_1|}{2}\right)$ . Similarly, the collision probability in ${\mathit{L}}_2$ is $\mathrm{(}6\mathrm{/}\mathit{p}\mathrm{)}\left(\genfrac{}{}{0ex}{}{|{\mathit{L}}_2|}{2}\right)$ . As mentioned earlier, we have $|{\mathit{L}}_1|+|{\mathit{L}}_2|\leqq 4\mathit{q}$ . Let the probability of Case 1 be denoted by Pr[Case 1]. Then we have $$\begin{array}{c}Pr[\text{Case}1]\leqq \mathrm{(}3\mathrm{/}\mathit{p}\mathrm{)}\left(\genfrac{}{}{0ex}{}{|{\mathit{L}}_1|}{2}\right)+\mathrm{(}6\mathrm{/}\mathit{p}\mathrm{)}\left(\genfrac{}{}{0ex}{}{|{\mathit{L}}_2|}{2}\right)\leqq \mathrm{(}6\mathrm{/}\mathit{p}\mathrm{)}{\mathrm{(}|{\mathit{L}}_1|+|{\mathit{L}}_2|\mathrm{)}}^2\leqq 96{\mathit{q}}^2\mathrm{/}\mathit{p}.\end{array}$$

Case 2:

If Case 1 does not occur and ${\mathit{A}}_{\mathit{I}}$ gets no leaked information, the success probability of ${\mathit{b}}^{\prime }=\mathit{b}$ is $1\mathrm{/}2$ in the Guess phase. Let Pr[Case 2] denote the success probability that Case 2 occurs. Then we have $Pr[\text{Case}2]\leqq 1\mathrm{/}2$ .

Let ${\text{Pr}}_{\mathit{A}-\mathit{I}-\mathit{W}}$ and ${\mathit{\text{Adv}}}_{\mathit{A}-\mathit{I}-\mathit{W}}$ be the probability and advantage, respectively, that ${\mathit{A}}_{\mathit{I}}$ wins the game without requesting any leak query. By Pr[Case 1] and Pr[Case 2], we have $$\begin{array}{rl}& {\text{Pr}}_{\mathit{A}-\mathit{I}-\mathit{W}}\leqq Pr[\text{Case}1]+Pr[\text{Case}2]\leqq 96{\mathit{q}}^2\mathrm{/}\mathit{p}+\mathrm{(}1\mathrm{/}2\mathrm{)}\mathrm{,}\\ & {\mathit{\text{Adv}}}_{\mathit{A}-\mathit{I}-\mathit{W}}\leqq |96{\mathit{q}}^2\mathrm{/}\mathit{p}+\mathrm{(}1\mathrm{/}2\mathrm{)}-\mathrm{(}1\mathrm{/}2\mathrm{)}|=96{\mathit{q}}^2\mathrm{/}\mathit{p}=\mathit{O}\mathrm{(}{\mathit{q}}^2\mathrm{/}\mathit{p}\mathrm{)}.\end{array}$$ Hence, ${\mathit{\text{Adv}}}_{\mathit{A}-\mathit{I}-\mathit{W}}$ is negligible if $\mathit{q}=\mathit{\text{poly}}\mathrm{(}log\mathit{p}\mathrm{)}$ .

■

The advantage of ${\mathit{A}}_{\mathit{I}}$ with requesting two kinds of leak queries: ${\mathit{A}}_{\mathit{I}}$ can obtain leaked information of related secret keys by the Identity secret key leak query and Decrypting leak query.

• $\mathrm{(}1\mathrm{)}$

Identity secret key leak query $\mathrm{(}{\mathit{f}}_{\mathit{\text{ISKE}}\mathrm{,}\mathit{i}}\mathrm{,}{\mathit{h}}_{\mathit{\text{ISKE}}\mathrm{,}\mathit{i}}\mathrm{,}\mathit{i}\mathrm{)}$ : By this query, ${\mathit{A}}_{\mathit{I}}$ may derive leaked information $\mathrm{(}\mathit{\Lambda }{\mathit{f}}_{\mathit{\text{ISKE}}\mathrm{,}\mathit{i}}\mathrm{,}\mathit{\Lambda }{\mathit{h}}_{\mathit{\text{ISKE}}\mathrm{,}\mathit{i}}\mathrm{)}$ such that $|{\mathit{f}}_{\mathit{\text{ISKE}}\mathrm{,}\mathit{i}}|$ , $|{\mathit{h}}_{\mathit{\text{ISKE}}\mathrm{,}\mathit{i}}|\leqq \mathit{\lambda }$ , where $\mathit{\Lambda }{\mathit{f}}_{\mathit{\text{ISKE}}\mathrm{,}\mathit{i}}={\mathit{f}}_{\mathit{\text{ISKE}}\mathrm{,}\mathit{i}}\mathrm{(}{\mathit{\text{KSK}}}_{\mathit{i}\mathrm{,}1}\mathrm{)}$ and $\mathit{\Lambda }{\mathit{h}}_{\mathit{\text{ISKE}}\mathrm{,}\mathit{i}}={\mathit{h}}_{\mathit{\text{ISKE}}\mathrm{,}\mathit{i}}\mathrm{(}{\mathit{\text{KSK}}}_{\mathit{i}\mathrm{,}2}\mathrm{)}$ that are discussed as below:

• •

  $\mathrm{(}{\mathit{\text{KSK}}}_{\mathit{i}\mathrm{,}1}\mathrm{,}{\mathit{\text{KSK}}}_{\mathit{i}\mathrm{,}2}\mathrm{)}$ : Indeed, the KGC’s secret key $\mathit{\text{KSK}}$ has the property in the sense that $\mathit{\text{KSK}}={\mathit{\text{KSK}}}_{0\mathrm{,}1}+{\mathit{\text{KSK}}}_{0\mathrm{,}2}={\mathit{\text{KSK}}}_{1\mathrm{,}1}+{\mathit{\text{KSK}}}_{1\mathrm{,}2}=\cdots ={\mathit{\text{KSK}}}_{\mathit{i}\mathrm{,}1}+{\mathit{\text{KSK}}}_{\mathit{i}\mathrm{,}2}$ . By the refreshing technique, leaked information of ${\mathit{\text{KSK}}}_{\mathit{i}-1\mathrm{,}1}\mathrm{/}{\mathit{\text{KSK}}}_{\mathit{i}-1\mathrm{,}2}$ is independent of that of ${\mathit{\text{KSK}}}_{\mathit{i}\mathrm{,}1}\mathrm{/}{\mathit{\text{KSK}}}_{\mathit{i}\mathrm{,}2}$ . Thus, ${\mathit{A}}_{\mathit{I}}$ may derive at most $2\mathit{\lambda }$ bits of KSK.

(2)

Decrypting leak query $\mathrm{(}\mathit{\text{ID}}\mathrm{,}{\mathit{T}}_{\mathit{s}}\mathrm{,}{\mathit{f}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}\mathrm{,}{\mathit{h}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}\mathrm{,}\mathit{k}\mathrm{)}$ : As mentioned earlier, ${\mathit{A}}_{\mathit{I}}$ is not a legal user of the LR-RCLE-ORA scheme, but it may get the time update key ${\mathit{\text{TUK}}}_{\mathit{\text{ID}}\mathrm{,}\mathit{s}}$ of any user $\mathit{\text{ID}}$ at any period ${\mathit{T}}_{\mathit{s}}$ from public channels. Also, ${\mathit{A}}_{\mathit{I}}$ may get the personal secret key ${\mathit{\text{PSK}}}_{\mathit{\text{ID}}}$ and the identity secret key ${\mathit{\text{ISK}}}_{\mathit{\text{ID}}}$ of any user $\mathit{\text{ID}}$ , but it is disallowed to get the identity secret key ${\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }}$ of the target user ${\mathit{\text{ID}}}^{\ast }$ . Therefore, by this query, ${\mathit{A}}_{\mathit{I}}$ may derive leaked information $\mathrm{(}\mathit{\Lambda }{\mathit{f}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}\mathrm{,}\mathit{\Lambda }{\mathit{h}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}\mathrm{)}$ , where $\mathit{\Lambda }{\mathit{f}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}={\mathit{f}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}\mathrm{(}{\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}\mathrm{,}1}\mathrm{)}$ and $\mathit{\Lambda }{\mathit{h}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}={\mathit{h}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}\mathrm{(}{\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}\mathrm{,}2}\mathrm{)}$ that are discussed as below:

• •

  $\mathrm{(}{\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}\mathrm{,}1}\mathrm{,}{\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}-1\mathrm{,}2}\mathrm{)}$ : Indeed, the identity secret key ${\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }}$ satisfies ${\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }}={\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}0\mathrm{,}1}+{\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}0\mathrm{,}2}={\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}1\mathrm{,}1}+{\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}1\mathrm{,}2}=\cdots ={\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}\mathrm{,}1}+{\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}\mathrm{,}2}$ . Bythe refreshing technique, leaked information of ${\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}-1\mathrm{,}1}\mathrm{/}{\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}-1\mathrm{,}2}$ is independent of that of ${\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}\mathrm{,}1}\mathrm{/}{\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}\mathrm{,}2}$ . Thus, ${\mathit{A}}_{\mathit{I}}$ may derive at most $2\mathit{\lambda }$ bits of ${\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }}$ .

Let ${\text{Pr}}_{\mathit{A}-\mathit{I}}$ and ${\mathit{\text{Adv}}}_{\mathit{A}-\mathit{I}}$ be the probability and advantage, respectively, that ${\mathit{A}}_{\mathit{I}}$ wins ${\mathit{G}}_{\mathit{\text{LR-RCLE-ORA}}}$ with requesting the Identity secret key leak query and Decrypting leak query. If ${\mathit{A}}_{\mathit{I}}$ can obtain the KGC’s secret key $\mathit{\text{KSK}}$ or the target user’s identity key ${\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }}$ , ${\mathit{A}}_{\mathit{I}}$ may decrypt the message. Three events are defined as below:

• (1)

  Let $\mathit{\text{EKSK}}$ denote the event that ${\mathit{A}}_{\mathit{I}}$ gets the $\mathit{\text{KSK}}$ by $\mathit{\Lambda }{\mathit{f}}_{\mathit{\text{ISKE}}\mathrm{,}\mathit{i}}$ and $\mathit{\Lambda }{\mathit{h}}_{\mathit{\text{ISKE}}\mathrm{,}\mathit{i}}$ . Additionally, $\overline{\mathit{\text{EKSK}}}$ is the complement event of $\mathit{\text{EKSK}}$ .

• (2)

  Let $\mathit{\text{EISK}}$ that ${\mathit{A}}_{\mathit{I}}$ gets the ${\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }}$ by $\mathit{\Lambda }{\mathit{f}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}$ and $\mathit{\Lambda }{\mathit{h}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}$ . Additionally, $\overline{\mathit{\text{EISK}}}$ is the complement event of $\mathit{\text{EISK}}$ .

• (3)

  Let $\mathit{\text{ECB}}$ denote the event that ${\mathit{A}}_{\mathit{I}}$ outputs a correct ${\mathit{b}}^{\prime }$ .

Hence, the advantage ${\text{Pr}}_{\mathit{A}-\mathit{I}}$ is Pr[ $\mathit{\text{ECB}}$ ] and the following inequality holds: $$\begin{array}{rl}{\text{Pr}}_{\mathit{A}-\mathit{I}}& =Pr[\mathit{\text{ECB}}]\\ & =Pr[\mathit{\text{ECB}}\wedge \mathrm{(}\mathit{\text{EKSK}}\vee \mathit{\text{EISK}}\mathrm{)}]+Pr[\mathit{\text{ECB}}\wedge \mathrm{(}\overline{\mathit{\text{EKSK}}}\wedge \overline{\mathit{\text{EISK}}}\mathrm{)}]\\ & \leqq Pr[\mathrm{(}\mathit{\text{EKSK}}\vee \mathit{\text{EISK}}\mathrm{)}]+Pr[\mathit{\text{ECB}}\wedge \mathrm{(}\overline{\mathit{\text{EKSK}}}\wedge \overline{\mathit{\text{EISK}}}\mathrm{)}].\end{array}$$ For the event $\mathrm{(}\overline{\mathit{\text{EKSK}}}\wedge \overline{\mathit{\text{EISK}}}\mathrm{)}$ , ${\mathit{A}}_{\mathit{I}}$ can’t obtain the useful information to output a correct bit ${\mathit{b}}^{\prime }$ . ${\mathit{A}}_{\mathit{I}}$ has probability 1/2 to guess the correct bit, so $Pr[\mathit{\text{ECB}}\wedge \mathrm{(}\overline{\mathit{\text{EKSK}}}\wedge \overline{\mathit{\text{EISK}}}\mathrm{)}]$ is still 1/2 on average. Thus, we have: $$\begin{array}{rl}& {\text{Pr}}_{\mathit{A}-\mathit{I}}\leqq Pr[\mathrm{(}\mathit{\text{EKSK}}\vee \mathit{\text{EISK}}\mathrm{)}]+1\mathrm{/}2\mathrm{,}\\ & {\mathit{\text{Adv}}}_{\mathit{A}-\mathit{I}}\leqq |{\text{Pr}}_{\mathit{A}-\mathit{I}}-1\mathrm{/}2|=Pr[\mathrm{(}\mathit{\text{EKSK}}\vee \mathit{\text{EISK}}\mathrm{)}].\end{array}$$

Because ${\mathit{\text{Adv}}}_{\mathit{A}-\mathit{I}-\mathit{W}}\leqq \mathit{O}\mathrm{(}{\mathit{q}}^2\mathrm{/}\mathit{p}\mathrm{)}$ and ${\mathit{A}}_{\mathit{I}}$ can learn at most $2\mathit{\lambda }$ bits of $\mathit{\text{KSK}}$ and ${\mathit{\text{ISK}}}_{{\mathit{\text{ID}}}^{\ast }}$ by the Identity secret key leak query and Decrypting leak query, we have $$\begin{array}{c}{\mathit{\text{Adv}}}_{\mathit{A}-\mathit{I}}\leqq {\mathit{\text{Adv}}}_{\mathit{A}-\mathit{I}-\mathit{W}}·2^{2\mathit{\lambda }}\leqq \mathit{O}\mathrm{\left(}\mathrm{\right(}{\mathit{q}}^2\mathrm{/}\mathit{p}\mathrm{)}·2^{2\mathit{\lambda }}\mathrm{)}.\end{array}$$ By Corollary 1, ${\mathit{\text{Adv}}}_{\mathit{A}-\mathit{I}}$ is negligible if $\mathit{\lambda }\mathrm{<}\mathrm{(}1-\mathit{\epsilon }\mathrm{)}log\mathit{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 $\mathrm{(}{\mathit{A}}_{\mathit{\text{II}}}\mathrm{)}$ in the security game ${\mathit{G}}_{\mathit{\text{LR-RCLE-ORA}}}$ .

Proof.

Let ${\mathit{A}}_{\mathit{\text{II}}}$ be a revoked user of the security game ${\mathit{G}}_{\mathit{\text{LR-RCLE-ORA}}}$ played with a challenger B. ${\mathit{A}}_{\mathit{\text{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 $\mathit{\text{TSK}}$ to ${\mathit{A}}_{\mathit{\text{II}}}$ since it is a revoked user.

–

Query phase: In this phase, ${\mathit{A}}_{\mathit{\text{II}}}$ can adaptively issue various queries to B at most q times. ${\mathit{A}}_{\mathit{l}\mathit{l}}$ queries are identical to those queries in the proof of Theorem 1. Note that ${\mathit{A}}_{\mathit{\text{II}}}$ knows the personal secret key ${\mathit{\text{PSK}}}_{\mathit{\text{ID}}}$ and the identity secret key ${\mathit{\text{ISK}}}_{\mathit{\text{ID}}}$ of any user $\mathit{\text{ID}}$ . Also, ${\mathit{A}}_{\mathit{\text{II}}}$ may get the time update key ${\mathit{\text{TUK}}}_{\mathit{\text{ID}}\mathrm{,}\mathit{s}}$ of any user $\mathit{\text{ID}}$ at any period ${\mathit{T}}_{\mathit{s}}$ , except ${\mathit{\text{TUK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}{\mathit{s}}^{\ast }}$ of the target user ${\mathit{\text{ID}}}^{\ast }$ at target period ${\mathit{T}}_{{\mathit{s}}^{\ast }}$ .

–

Challenge phase: ${\mathit{A}}_{\mathit{\text{II}}}$ sends a target identity ${\mathit{\text{ID}}}^{\ast }$ , a target period ${\mathit{T}}_{{\mathit{s}}^{\ast }}$ and a plaintext pair ( $\mathit{m}\mathit{s}{\mathit{g}}_0^{\ast }\mathrm{,}\mathit{m}\mathit{s}{\mathit{g}}_1^{\ast }$ ) to B. Here the Time update key query ( ${\mathit{\text{ID}}}^{\ast }\mathrm{,}{\mathit{T}}_{\mathit{s}}^{\ast }$ ) must have never been requested by ${\mathit{A}}_{\mathit{\text{II}}}$ . B chooses a unbiased random bit $\mathit{b}\in \{0\mathrm{,}1\}$ and carries out the Encrypting algorithm with $\mathrm{(}{\mathit{\text{ID}}}^{\ast }\mathrm{,}{\mathit{T}}_{\mathit{s}}^{\ast }\mathrm{,}\mathrm{(}{\mathit{\text{PPK}}}_{{\mathit{\text{ID}}}^{\ast }}\mathrm{,}{\mathit{\text{IPK}}}_{{\mathit{\text{ID}}}^{\ast }}\mathrm{,}{\mathit{\text{TUPK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}{\mathit{s}}^{\ast }}\mathrm{)}\mathrm{,}\mathit{m}\mathit{s}{\mathit{g}}_{\mathit{b}}^{\ast }\mathrm{)}$ to generate ${\mathit{C}}^{\ast }$ , ${\mathit{\text{EK}}}^{\ast }$ and ${\mathit{\text{CT}}}^{\ast }={\mathit{E}}_{{\mathit{\text{EK}}}^{\ast }}\mathrm{(}\mathit{m}\mathit{s}{\mathit{g}}_{\mathit{b}}^{\ast }\mathrm{)}$ . Finally, B returns the ciphertext tuple $\mathrm{(}{\mathit{\text{ID}}}^{\ast }\mathrm{,}{\mathit{T}}_{\mathit{s}}^{\ast }\mathrm{,}\mathit{\theta }=\mathrm{(}{\mathit{C}}^{\ast }\mathrm{,}{\mathit{\text{CT}}}^{\ast }\mathrm{)}\mathrm{)}$ to ${\mathit{A}}_{\mathit{\text{II}}}$ .

–

Guess phase: In this phase, ${\mathit{A}}_{\mathit{\text{II}}}$ must output a bit ${\mathit{b}}^{\prime }\in \{0\mathrm{,}1\}$ . If ${\mathit{b}}^{\prime }=\mathit{b}$ , we say that it wins the game ${\mathit{G}}_{\mathit{\text{LR-RCLE-ORA}}}$ and its advantage is $|Pr[{\mathit{b}}^{\prime }=\mathit{b}]-1\mathrm{/}2|$ .

In the following, let us first evaluate the advantage that ${\mathit{A}}_{\mathit{\text{II}}}$ wins ${\mathit{G}}_{\mathit{\text{LR-RCLE-ORA}}}$ without requesting any leak query. Subsequently, the advantage of ${\mathit{A}}_{\mathit{\text{II}}}$ is evaluated when it is allowed to request the Time update key leak query.

• ■

The advantage of ${\mathit{A}}_{\mathit{\text{II}}}$ without requesting any leak query: Let ${\mathit{\text{Adv}}}_{\mathit{A}-\mathit{\text{II}}-\mathit{W}}$ be the advantage that ${\mathit{A}}_{\mathit{\text{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 ${\mathit{\text{Adv}}}_{\mathit{A}-\mathit{\text{II}}-\mathit{W}}=\mathit{O}\mathrm{(}{\mathit{q}}^2\mathrm{/}\mathit{p}\mathrm{)}$ .

■

The advantage of ${\mathit{A}}_{\mathit{\text{II}}}$ with requesting the Time update key leak query: By the Time update key leak query ( ${\mathit{f}}_{\mathit{\text{TUKE}}\mathrm{,}\mathit{j}}\mathrm{,}{\mathit{h}}_{\mathit{\text{TUKE}}\mathrm{,}\mathit{j}}$ , j), ${\mathit{A}}_{\mathit{\text{II}}}$ may derive leaked information ( $\mathit{\Lambda }{\mathit{f}}_{\mathit{\text{TUKE}}\mathrm{,}\mathit{j}}\mathrm{,}\mathit{\Lambda }{\mathit{h}}_{\mathit{\text{TUKE}}\mathrm{,}\mathit{j}}$ ) such that $|{\mathit{f}}_{\mathit{\text{TUKE}}\mathrm{,}\mathit{j}}|$ , $|{\mathit{h}}_{\mathit{\text{TUKE}}\mathrm{,}\mathit{j}}|\leqq \mathit{\lambda }$ , where $\mathit{\Lambda }{\mathit{f}}_{\mathit{\text{TUKE}}\mathrm{,}\mathit{j}}={\mathit{f}}_{\mathit{\text{TUKE}}\mathrm{,}\mathit{j}}\mathrm{(}{\mathit{\text{TSK}}}_{\mathit{j}\mathrm{,}1}\mathrm{)}$ and $\mathit{\Lambda }{\mathit{h}}_{\mathit{\text{TUKE}}\mathrm{,}\mathit{j}}={\mathit{h}}_{\mathit{\text{TUKE}}\mathrm{,}\mathit{j}}\mathrm{(}{\mathit{\text{TSK}}}_{\mathit{j}\mathrm{,}2}\mathrm{)}$ . Indeed, the time secret key $\mathit{\text{TSK}}$ has the property in the sense that $\mathit{\text{TSK}}={\mathit{\text{TSK}}}_{0\mathrm{,}1}+{\mathit{\text{TSK}}}_{0\mathrm{,}2}={\mathit{\text{TSK}}}_{1\mathrm{,}1}+{\mathit{\text{TSK}}}_{1\mathrm{,}2}=\cdots ={\mathit{\text{TSK}}}_{\mathit{i}\mathrm{,}1}+{\mathit{\text{TSK}}}_{\mathit{i}\mathrm{,}2}$ . By the refreshing technique, leaked information of ${\mathit{\text{TSK}}}_{\mathit{i}-1\mathrm{,}1}\mathrm{/}{\mathit{\text{TSK}}}_{\mathit{i}-1\mathrm{,}2}$ is independent of that of ${\mathit{\text{TSK}}}_{\mathit{i}\mathrm{,}1}\mathrm{/}{\mathit{\text{TSK}}}_{\mathit{i}\mathrm{,}2}$ . Thus, ${\mathit{A}}_{\mathit{\text{II}}}$ may derive at most $2\mathit{\lambda }$ bits of $\mathit{\text{TSK}}$ .

Let ${\text{Pr}}_{\mathit{A}-\mathit{\text{II}}}$ and ${\mathit{\text{Adv}}}_{\mathit{A}-\mathit{\text{II}}}$ be the probability and advantage, respectively, that ${\mathit{A}}_{\mathit{\text{II}}}$ wins ${\mathit{G}}_{\mathit{\text{LR-RCLE-ORA}}}$ with requesting the Time update key leak query. Two events are defined as below:

• (1)

Let $\mathit{\text{ETSK}}$ denote the event that ${\mathit{A}}_{\mathit{\text{II}}}$ gets the time secret key $\mathit{\text{TSK}}$ by ${\mathit{f}}_{\mathit{\text{TUKE}}\mathrm{,}\mathit{j}}$ and ${\mathit{h}}_{\mathit{\text{TUKE}}\mathrm{,}\mathit{j}}$ . Additionally, $\overline{\mathit{\text{ETSK}}}$ is the complement event of $\mathit{\text{ETSK}}$ .

(2)

Let $\mathit{\text{ECB}}$ denote the event that ${\mathit{A}}_{\mathit{\text{II}}}$ outputs a correct ${\mathit{b}}^{\prime }$ .

Hence, the advantage ${\text{Pr}}_{\mathit{A}-\mathit{\text{II}}}$ is Pr[ $\mathit{\text{ECB}}$ ] and the following inequality holds: $$\begin{array}{rl}{\text{Pr}}_{\mathit{A}-\mathit{\text{II}}}& =Pr[\mathit{\text{ECB}}]\\ & =Pr[\mathit{\text{ECB}}\wedge \mathit{\text{ETSK}}]+Pr[\mathit{\text{ECB}}\wedge \overline{\mathit{\text{ETSK}}}]\\ & \leqq Pr[\mathit{\text{ETSK}}]+Pr[\mathit{\text{ECB}}\wedge \overline{\mathit{\text{ETSK}}}].\end{array}$$ For the event $\overline{\mathit{\text{ETSK}}}$ , ${\mathit{A}}_{\mathit{\text{II}}}$ can’t obtain the useful information to output a correct bit ${\mathit{b}}^{\prime }$ . ${\mathit{A}}_{\mathit{\text{II}}}$ has probability $1\mathrm{/}2$ to guess the correct bit, so $Pr[\mathit{\text{ECB}}\wedge \overline{\mathit{\text{ETSK}}}]$ is still $1\mathrm{/}2$ on average. Thus, we have $$\begin{array}{rl}& {\text{Pr}}_{\mathit{A}-\mathit{\text{II}}}\leqq Pr[\mathit{\text{ETSK}}]+1\mathrm{/}2\mathrm{,}\\ & {\mathit{\text{Adv}}}_{\mathit{A}-\mathit{\text{II}}}\leqq |{\text{Pr}}_{\mathit{A}-\mathit{\text{II}}}-1\mathrm{/}2|=Pr[\mathit{\text{ETSK}}].\end{array}$$

Because ${\mathit{\text{Adv}}}_{\mathit{A}-\mathit{\text{II}}-\mathit{W}}\leqq \mathit{O}\mathrm{(}{\mathit{q}}^2\mathrm{/}\mathit{p}\mathrm{)}$ and ${\mathit{A}}_{\mathit{\text{II}}}$ can learn at most $2\mathit{\lambda }$ bits of $\mathit{\text{TSK}}$ by the Time update key leak query, we have $$\begin{array}{c}{\mathit{\text{Adv}}}_{\mathit{A}-\mathit{\text{II}}}\leqq {\mathit{\text{Adv}}}_{\mathit{A}-\mathit{\text{II}}-\mathit{W}}·2^{2\mathit{\lambda }}\leqq \mathit{O}\mathrm{\left(}\mathrm{\right(}{\mathit{q}}^2\mathrm{/}\mathit{p}\mathrm{)}·2^{2\mathit{\lambda }}\mathrm{)}.\end{array}$$ By Corollary 1, ${\mathit{\text{Adv}}}_{\mathit{A}-\mathit{\text{II}}}$ is negligible if $\mathit{\lambda }\mathrm{<}\mathrm{(}1-\mathit{\epsilon }\mathrm{)}log\mathit{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 $\mathrm{(}{\mathit{A}}_{\mathit{\text{III}}}\mathrm{)}$ in the security game ${\mathit{G}}_{\mathit{\text{LR-RCLE-ORA}}}$ .

Proof.

Let ${\mathit{A}}_{\mathit{\text{III}}}$ be an honest-but-curious KGC of the security game ${\mathit{G}}_{\mathit{\text{LR-RCLE-ORA}}}$ played with a challenger B. ${\mathit{A}}_{\mathit{\text{III}}}$ 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 KGC’s secret key $\mathit{\text{KSK}}$ and time secret key $\mathit{\text{TSK}}$ to ${\mathit{A}}_{\mathit{\text{III}}}$ since it is an honest-but-curious KGC.

–

Query phase: In this phase, ${\mathit{A}}_{\mathit{\text{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 ${\mathit{A}}_{\mathit{\text{III}}}$ knows the KGC’s secret key $\mathit{\text{KSK}}$ and time secret key $\mathit{\text{TSK}}$ so that it can get the identity secret key ${\mathit{\text{ISK}}}_{\mathit{\text{ID}}}$ and time update key ${\mathit{\text{TUK}}}_{\mathit{\text{ID}}\mathrm{,}\mathit{s}}$ of any user $\mathit{\text{ID}}$ for any period ${\mathit{T}}_{\mathit{s}}$ . Also, ${\mathit{A}}_{\mathit{\text{III}}}$ may get the personal secret key ${\mathit{\text{PSK}}}_{\mathit{\text{ID}}}$ of any user $\mathit{\text{ID}}$ , except ${\mathit{\text{PSK}}}_{{\mathit{\text{ID}}}^{\ast }}$ of the target user ${\mathit{\text{ID}}}^{\ast }$ .

–

Challenge phase: ${\mathit{A}}_{\mathit{\text{III}}}$ sends a target identity ${\mathit{\text{ID}}}^{\ast }$ , a target period ${\mathit{T}}_{{\mathit{s}}^{\ast }}$ and a plaintext pair ( $\mathit{m}\mathit{s}{\mathit{g}}_0^{\ast }\mathrm{,}\mathit{m}\mathit{s}{\mathit{g}}_1^{\ast }$ ) to B. Here both the Personal secret key corrupt query ( ${\mathit{\text{ID}}}^{\ast }$ ) and the Public key replace query $\mathrm{(}{\mathit{\text{ID}}}^{\ast }\mathrm{,}{\mathit{T}}_{\mathit{s}\ast }\mathrm{,}\mathrm{(}{\mathit{\text{PPK}}}_{{\mathit{\text{ID}}}^{\ast }}^{\prime }\mathrm{,}{\mathit{\text{IPK}}}_{{\mathit{\text{ID}}}^{\ast }}^{\prime }\mathrm{,}{\mathit{\text{TUPK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}{\mathit{s}}^{\ast }}^{\prime }\mathrm{)}\mathrm{)}$ must have never been requested by ${\mathit{A}}_{\mathit{\text{III}}}$ . B chooses an unbiased random bit $\mathit{b}\in \{0\mathrm{,}1\}$ and carries out the Encrypting algorithm with $\mathrm{(}{\mathit{\text{ID}}}^{\ast }\mathrm{,}{\mathit{T}}_{\mathit{s}}^{\ast }\mathrm{,}\mathrm{(}{\mathit{\text{PPK}}}_{{\mathit{\text{ID}}}^{\ast }}\mathrm{,}{\mathit{\text{IPK}}}_{{\mathit{\text{ID}}}^{\ast }}\mathrm{,}{\mathit{\text{TUPK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}{\mathit{s}}^{\ast }}\mathrm{)}\mathrm{,}\mathit{m}\mathit{s}{\mathit{g}}_{\mathit{b}}^{\ast }\mathrm{)}$ to generate ${\mathit{C}}^{\ast }$ , ${\mathit{\text{EK}}}^{\ast }$ and ${\mathit{\text{CT}}}^{\ast }={\mathit{E}}_{{\mathit{\text{EK}}}^{\ast }}\mathrm{(}\mathit{m}\mathit{s}{\mathit{g}}_{\mathit{b}}^{\ast }\mathrm{)}$ . Finally, B returns the ciphertext tuple $\mathrm{(}{\mathit{\text{ID}}}^{\ast }\mathrm{,}{\mathit{T}}_{\mathit{s}}^{\ast }\mathrm{,}\mathit{\theta }=\mathrm{(}{\mathit{C}}^{\ast }\mathrm{,}{\mathit{\text{CT}}}^{\ast }\mathrm{)}\mathrm{)}$ to ${\mathit{A}}_{\mathit{\text{III}}}$ .

–

Guess phase: In this phase, ${\mathit{A}}_{\mathit{\text{III}}}$ must output a bit ${\mathit{b}}^{\prime }\in \{0\mathrm{,}1\}$ . If ${\mathit{b}}^{\prime }=\mathit{b}$ , we say that it wins the game ${\mathit{G}}_{\mathit{\text{LR-RCLE-ORA}}}$ and its advantage is $|Pr[{\mathit{b}}^{\prime }=\mathit{b}]-1\mathrm{/}2|$ .

In the following, let us first evaluate the advantage that ${\mathit{A}}_{\mathit{\text{III}}}$ wins ${\mathit{G}}_{\mathit{\text{LR-RCLE-ORA}}}$ without requesting any leak query. Subsequently, the advantage of ${\mathit{A}}_{\mathit{\text{III}}}$ is evaluated when it is allowed to request the Decrypting leak query $\mathrm{(}\mathit{\text{ID}}\mathrm{,}{\mathit{T}}_{\mathit{s}}\mathrm{,}{\mathit{f}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}\mathrm{,}{\mathit{h}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}\mathrm{,}\mathit{k}\mathrm{)}$ .

• ■

  The advantage of ${\mathit{A}}_{\mathit{\text{III}}}$ without requesting any leak query: Let ${\mathit{\text{Adv}}}_{\mathit{A}-\mathit{\text{III}}-\mathit{W}}$ be the advantage that ${\mathit{A}}_{\mathit{\text{III}}}$ wins the game without requesting the Decrypting leak query. By the similar evaluations as in the proof of Theorem 1, we have ${\mathit{\text{Adv}}}_{\mathit{A}-\mathit{\text{III}}-\mathit{W}}=\mathit{O}\mathrm{(}{\mathit{q}}^2\mathrm{/}\mathit{p}\mathrm{)}$ .

• ■

  The advantage of ${\mathit{A}}_{\mathit{\text{III}}}$ with requesting the Decrypting leak query: By the Decrypting leak query $\mathrm{(}\mathit{\text{ID}}\mathrm{,}{\mathit{T}}_{\mathit{s}}\mathrm{,}{\mathit{f}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}\mathrm{,}{\mathit{h}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}\mathrm{,}\mathit{k}\mathrm{)}$ , ${\mathit{A}}_{\mathit{\text{III}}}$ may derive leaked information $\mathrm{(}\mathit{\Lambda }{\mathit{f}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}\mathrm{,}\mathit{\Lambda }{\mathit{h}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}\mathrm{)}$ such that $|{\mathit{f}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}|\mathrm{,}|{\mathit{h}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}|\leqq \mathit{\lambda }$ , where $\mathit{\Lambda }{\mathit{f}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}={\mathit{f}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}\mathrm{(}{\mathit{\text{PSK}}}_{\mathit{\text{ID}}\mathrm{,}\mathit{k}\mathrm{,}1}\mathrm{)}$ and $\mathit{\Lambda }{\mathit{h}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}={\mathit{h}}_{\mathit{\text{DEC}}\mathrm{,}\mathit{k}}\mathrm{(}{\mathit{\text{PSK}}}_{\mathit{\text{ID}}\mathrm{,}\mathit{k}\mathrm{,}2}\mathrm{)}$ . Note that ${\mathit{A}}_{\mathit{\text{III}}}$ may get the personal secret key ${\mathit{\text{PSK}}}_{\mathit{\text{ID}}}$ of any user $\mathit{\text{ID}}$ , except ${\mathit{\text{PSK}}}_{{\mathit{\text{ID}}}^{\ast }}$ of the target user ${\mathit{\text{ID}}}^{\ast }$ . For leakage resilient property, ${\mathit{A}}_{\mathit{\text{III}}}$ can obtain leaked information of the target user’s ${\mathit{\text{PSK}}}_{{\mathit{\text{ID}}}^{\ast }}=\mathrm{(}{\mathit{\text{PSK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}\mathrm{,}1}\mathrm{,}{\mathit{\text{PSK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}\mathrm{,}2}\mathrm{)}$ used in the Decrypting algorithm’s k-th round of the target user. Indeed, the personal secret key ${\mathit{\text{PSK}}}_{\mathit{\text{ID}}}$ has the property in the sense that ${\mathit{\text{PSK}}}_{{\mathit{\text{ID}}}^{\ast }}={\mathit{\text{PSK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}0\mathrm{,}1}+{\mathit{\text{PSK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}0\mathrm{,}2}={\mathit{\text{PSK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}1\mathrm{,}1}+{\mathit{\text{PSK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}1\mathrm{,}2}=\cdots ={\mathit{\text{PSK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}\mathrm{,}1}+{\mathit{\text{PSK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}\mathrm{,}2}$ . By the refreshing technique, leaked information of ${\mathit{\text{PSK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}-1\mathrm{,}1}\mathrm{/}{\mathit{\text{PSK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}-1\mathrm{,}2}$ is independent of that of ${\mathit{\text{PSK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}\mathrm{,}1}\mathrm{/}{\mathit{\text{PSK}}}_{{\mathit{\text{ID}}}^{\ast }\mathrm{,}\mathit{k}\mathrm{,}2}$ . Thus, ${\mathit{A}}_{\mathit{\text{III}}}$ may derive at most $2\mathit{\lambda }$ bits of ${\mathit{\text{PSK}}}_{{\mathit{\text{ID}}}^{\ast }}$ .

  Let ${\text{Pr}}_{\mathit{A}-\mathit{\text{III}}}$ and ${\mathit{\text{Adv}}}_{\mathit{A}-\mathit{\text{III}}}$ be the probability and advantage, respectively, that ${\mathit{A}}_{\mathit{\text{III}}}$ wins ${\mathit{G}}_{\mathit{\text{LR-RCLE-ORA}}}$ with requesting the Decrypting leak query. Two events are defined as below:

• (2)

  Let $\mathit{\text{ECB}}$ denote the event that ${\mathit{A}}_{\mathit{\text{III}}}$ outputs a correct ${\mathit{b}}^{\prime }$ .

Hence, the advantage ${\text{Pr}}_{\mathit{A}-\mathit{\text{III}}}$ is Pr[ $\mathit{\text{ECB}}$ ] and the following inequality holds. $$\begin{array}{rl}{\text{Pr}}_{\mathit{A}-\mathit{\text{III}}}& =Pr[\mathit{\text{ECB}}]\\ & =Pr[\mathit{\text{ECB}}\wedge \mathit{\text{EPSK}}]+Pr[\mathit{\text{ECB}}\wedge \overline{\mathit{\text{EPSK}}}]\\ & \leqq Pr[\mathit{\text{EPSK}}]+Pr[\mathit{\text{ECB}}\wedge \overline{\mathit{\text{EPSK}}}].\end{array}$$ For the event $\overline{\mathit{\text{EPSK}}}$ , ${\mathit{A}}_{\mathit{\text{III}}}$ can’t obtain the useful information to output a correct bit ${\mathit{b}}^{\prime }$ . ${\mathit{A}}_{\mathit{\text{III}}}$ has probability 1/2 to guess the correct bit, so $Pr[\mathit{\text{ECB}}\wedge \overline{\mathit{\text{EPSK}}}]$ is still 1/2 on average. Thus, we have $$\begin{array}{rl}& {\text{Pr}}_{\mathit{A}-\mathit{\text{III}}}\leqq Pr[\mathit{\text{EPSK}}]+1\mathrm{/}2\mathrm{,}\\ & {\mathit{\text{Adv}}}_{\mathit{A}-\mathit{\text{III}}}\leqq |{\text{Pr}}_{\mathit{A}-\mathit{\text{III}}}-1\mathrm{/}2|=Pr[\mathit{\text{EPSK}}].\end{array}$$

Because ${\mathit{\text{Adv}}}_{\mathit{A}-\mathit{\text{III}}-\mathit{W}}\leqq \mathit{O}\mathrm{(}{\mathit{q}}^2\mathrm{/}\mathit{p}\mathrm{)}$ and ${\mathit{A}}_{\mathit{\text{III}}}$ can learn at most $2\mathit{\lambda }$ bits of $\mathit{\text{PSK}}$ by the Decrypting leak query, we have $$\begin{array}{c}{\mathit{\text{Adv}}}_{\mathit{A}-\mathit{\text{III}}}\leqq {\mathit{\text{Adv}}}_{\mathit{A}-\mathit{\text{III}}-\mathit{W}}·2^{2\mathit{\lambda }}\leqq \mathit{O}\mathrm{\left(}\mathrm{\right(}{\mathit{q}}^2\mathrm{/}\mathit{p}\mathrm{)}·2^{2\mathit{\lambda }}\mathrm{)}.\end{array}$$ By Corollary 1, ${\mathit{\text{Adv}}}_{\mathit{A}-\mathit{\text{III}}}$ is negligible if $\mathit{\lambda }\mathrm{<}\mathrm{(}1-\mathit{\epsilon }\mathrm{)}log\mathit{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 ${\mathit{F}}_{\mathit{p}}$ , ${\mathit{G}}_1$ and ${\mathit{G}}_2$ . Here, ${\mathit{F}}_{\mathit{p}}$ is a finite field which consists of the set of integers $\{0\mathrm{,}1\mathrm{,}\dots \mathrm{,}\mathit{p}-1\}$ , where p is a 256-bit prime number. And, ${\mathit{G}}_1$ and ${\mathit{G}}_2$ are groups with 224-bit prime order over the finite field ${\mathit{F}}_{\mathit{p}}$ . It is worth mentioning that the computation of a one-way hash function, an addition on an additive group ${\mathit{G}}_1$ and a multiplication on a multiplicative group ${\mathit{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
${\mathit{T}}_{\mathit{p}}$	a bilinear pairing $\hat{\mathit{e}}:{\mathit{G}}_1\times {\mathit{G}}_1\to {\mathit{G}}_2$	7.84 ms
	a scalar multiplication on an additive group ${\mathit{G}}_1$
${\mathit{T}}_{\mathit{m}\mathit{e}}$	or	0.48 ms
	an exponentiation on a multiplicative group ${\mathit{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 $\mathit{n}\geqq 2$ elements (here, let $\mathit{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 ${\mathit{T}}_{\mathit{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{\mathit{T}}_{\mathit{m}\mathit{e}}+{\mathit{T}}_{\mathit{p}}$	$6{\mathit{T}}_{\mathit{m}\mathit{e}}$	$4{\mathit{T}}_{\mathit{m}\mathit{e}}+{\mathit{T}}_{\mathit{p}}$	$4{\mathit{T}}_{\mathit{m}\mathit{e}}+2{\mathit{T}}_{\mathit{p}}$
	(9.28 ms)	(2.88 ms)	(9.76 ms)	(17.6 ms)
Decryption cost	$2{\mathit{T}}_{\mathit{m}\mathit{e}}+{\mathit{T}}_{\mathit{p}}$	$4{\mathit{T}}_{\mathit{p}}$	$4{\mathit{T}}_{\mathit{m}\mathit{e}}+4{\mathit{T}}_{\mathit{p}}$	$4{\mathit{T}}_{\mathit{m}\mathit{e}}+5{\mathit{T}}_{\mathit{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.