Receiver selective opening security for identity-based encryption in the multi-challenge setting

Abstract

Receiver selective opening (RSO) security requires that in a situation where there are one sender and multiple receivers, even if an adversary has access to all ciphertexts and adaptively corrupts some fraction of the receivers to obtain their secret keys, the (potentially related) ciphertexts of the uncorrupted receivers remain secure. All of the existing works construct RSO secure identity-based encryption (IBE) in the single-challenge setting, where each identity is used only once for encryption. This restriction makes RSO security for IBE unrealistic in practice. It is preferable to have IBE schemes with RSO security in the multi-challenge setting in practice, where each identity can be used to encrypt multiple messages. In this paper, we initiate the study of RSO security in the multi-challenge setting (which we call $\hbox {RSO}_k$ security) for IBE. Concretely, we show that the conclusion of lower bound, proposed by Yang et al. (in: ASIACRYPT 2020, Springer, 2020), on the secret key size of RSO secure public-key encryption also holds in the IBE setting (i.e., an IBE scheme cannot be $\hbox {RSO}_k$ secure if the length of its secret key is not k times larger than the length of message). For construction, we propose a generic construction of IBE achieving $\hbox {RSO}_k$ security. Through our generic construction, we can obtain $\hbox {RSO}_k$ secure IBE schemes based on decisional linear (DLIN) assumption and learning with error (LWE) assumption. Furthermore, we show that the well-known Fujisaki–Okamoto transformation can be applied to construct a practical IBE scheme achieving $\hbox {RSO}_k$ security.

1 Introduction

Selective opening attacks, firstly formally considered by Bellare et al. [3] for public key encryption (PKE), concern some multi-user scenarios, where an adversary is able to break into a subset of honestly generated ciphertexts and tries to learn information on the messages of some unopened (but maybe potentially related) ciphertexts. Bellare et al. [3] introduce two ways to formalize security notions against selective opening attacks (SO security notions), namely indistinguishability-based (IND-SO) security and simulation-based (SIM-SO) security. Generally, IND-SO security requires that the unopened ciphertexts and the ciphertexts of freshly sampled messages, which are distributed according to the conditional probability distribution (conditioned on the opened ciphertexts), are computationally indistinguishable; SIM-SO security requires that anything, which can be computed from all the ciphertexts and the opened messages together with the corrupted information, can also be computed only from the opened messages. Compared with SIM-SO security, IND-SO security has a limitation that the message distribution should be “efficiently conditionally re-samplable”, while SIM-SO security imposes no limitation on the message distributions; it is already known that under chosen-plaintext attacks (CPA) for PKE, SIM-SO security is strictly stronger than IND-SO security [2, 6, 15]. Thus, for SO security, it is desirable to consider simulation-based definitions.

To date, SO security notions are usually considered in two settings: sender corruption [3, 9, 16, 19] and receiver corruption [2, 13, 15, 22]. In the sender corruption setting, part of the senders may be corrupted (we say that “their ciphertexts are opened”), exposing their messages and random coins employed during the encryption. In the receiver corruption setting, part of them may be corrupted, exposing their messages and secret keys. We denote SO security in the sender corruption setting and in the receiver corruption setting by SSO security and RSO security, respectively.

Standard RSO security is formalized in the single-challenge setting for PKE, where each public key is used only once to encrypt a single challenge message. This restriction makes RSO security unrealistic, since in practice a public key is often used multiple times. More realistic $\hbox {RSO}_k$ security (i.e., RSO security in the multi-challenge setting, where each public key can be used to encrypt $k\ge 1$ challenge messages) is introduced by Yang et al. [42]. They prove that SIM-RSO security is not enough to guarantee SIM-$\hbox {RSO}_k$ security ($k>1$), providing a lower bound on the secret key length for any PKE scheme with $\hbox {RSO}_k$ security in the non-programmable random oracle model, and show SIM-$\hbox {RSO}_k$-CPA/CCA secure PKE constructions with nearly optimal secret key length.

SO security for IBE The study of SO secure identity-based encryption (IBE) is initiated by Bellare et al. [5]. Compared with PKE, IBE allows a sender to generate ciphertexts using a receiver’s identity as a public key, and the subtlety of proving security of IBE comes from the fact that a key generation oracle is provided to an adversary to answer private key queries with respect to different identities, and the adversary is free to choose the challenge identities. Bellare et al. [5] firstly formalize a simulation-based notion of SSO security under CPA attacks for IBE (which we denote as SIM-ID-SSO-CPA security), via adapting the SO framework to IBE in a natural way (i.e., informally, replacing the public keys with the target receivers’ identities, and allowing the adversary to access to the key generation oracle). Furthermore, they construct IBE schemes meeting this security requirement. Later, the first IBE scheme achieving simulation-based SSO security under CCA attacks (which we denote as SIM-ID-SSO-CCA security) is proposed by Lai et al. [30].

As for the receiver corruption setting, the notion of simulation-based RSO security under CPA attacks for IBE (which we denote as SIM-ID-RSO-CPA security) is formalized by Kitagawa and Tanaka [29]. They construct a SIM-ID-RSO-CPA secure IBE scheme from an IBE scheme with basic security (i.e., IND-ID-CPA security). Recently, Hara et al. [14] formalize the notion of simulation-based RSO security under CCA attacks for IBE (which we denote as SIM-ID-RSO-CCA security), and show an IBE construction meeting SIM-ID-RSO-CCA security via the classical double encryption technique [36, 38].

To the best of our knowledge, currently all the known receiver selective opening security notions for IBE [14, 29] are considered in the single-challenge setting (i.e., each identity as used only once to encrypt a single challenge message). However, in practice, usually an identity (i.e., public key) is used multiple times for encryption. More importantly, no RSO security notions in the multi-challenge setting for IBE have ever been considered before.

In this paper, we initiate the study of simulation-based RSO security in the multi-challenge setting for IBE.

Our contributions We firstly formalize the notion of simulation-based RSO security in the multi-challenge setting (which we denote as SIM-ID-$\hbox {RSO}_k$-CPA/CCA security) for IBE. In particular, a SIM-ID-$\hbox {RSO}_k$-CPA/CCA adversary is allowed to access to the key generation oracle, can obtain k challenge ciphertexts for each identity, and can corrupt some of the receivers and know the secret keys; SIM-ID-$\hbox {RSO}_k$-CPA/CCA security requires that anything, which can be computed by the adversary, can also be computed by a simulator only from the opened messages (of the corrupted receivers).

We show that the conclusion (proposed in [42]) of lower bound on the secret key size of $\hbox {RSO}_k$ secure encryption scheme in the PKE setting also holds in the IBE setting. More specifically, we provide a lower bound on the secret key length for any IBE scheme with SIM-ID-$\hbox {RSO}_k$ security in the non-programmable random oracle model. This result implies that for any SIM-ID-$\hbox {RSO}_k$ secure IBE scheme, assuming that the size of its message space (resp., secret key space) is $2^{\ell _{\text {m}}}$ (resp., $2^{\ell _{\text {sk}}}$), we have $\ell _{\text {sk}}\ge \ell _{\text {m}}k$. This result also implies that it is impossible for IBE to achieve SIM-ID-$\hbox {RSO}_k$ security without restricting the number of challenge ciphertexts for each identity (i.e., k).

We stress that this result also suggests that for IBE, RSO security in the single-challenge setting is not enough to guarantee that in the multi-challenge setting. That’s because for any IBE scheme with SIM-ID-RSO-CCA security, assuming that the size of its message space (resp., secret key space) is $2^{\ell _{\text {m}}}$ (resp., $2^{\ell _{\text {sk}}}$), this IBE scheme is not SIM-ID-$\hbox {RSO}_k$-CPA secure for any $k\ge \frac{\ell _{\text {sk}}+1}{\ell _{\text {m}}}$.

We provide a generic construction of IBE achieving SIM-ID-$\hbox {RSO}_k$-CCA security. Our generic IBE scheme is constructed from an IND-ID-CPA secure IBE scheme with message space $\{0,1\}$ and a non-interactive zero-knowledge (NIZK) proof system, via the double encryption technique [36, 38]. More concretely, to encrypt a single-bit message m with identity $\textsf {id}$, the encryption algorithm of our generic IBE scheme proceeds as follows: (i) firstly uniformly sample k bits $\textsf {m} _1,\ldots ,\textsf {m} _{k}$ satisfying $\textsf {m} _1\oplus \cdots \oplus \textsf {m} _{k}=m$; (ii) for each $\eta \in [k]$ and each $\beta \in \{0,1\}$, generate $c_{\eta ,\beta }$ by encrypting $\textsf {m} _{\eta }$ (with identity $(\textsf {id},\eta ,\beta )$) using the encryption algorithm of the underlying IND-ID-CPA secure IBE scheme; (iii) generate a NIZK proof indicating that the 2k ciphertexts $(c_{\eta ,\beta })_{\eta \in [k],\beta \in \{0,1\}}$ are created by encrypting $\textsf {m} _1,\ldots ,\textsf {m} _{k}$ via (ii). With this method, the SIM-ID-$\hbox {RSO}_k$-CCA security of our generic IBE can be implied by the IND-ID-CPA security of the underlying IBE and the security properties of the NIZK proof system.

In particular, when plugging the DLIN-based (resp., the LWE based) instantiations [12, 40] (resp., [1, 37]) into our generic construction, we obtain a concrete DLIN-based (resp., LWE based) SIM-ID-$\hbox {RSO}_k$-CCA secure IBE scheme.

We also provide a practical IBE scheme meeting SIM-ID-$\hbox {RSO}_k$-CCA security in the random oracle model. Specifically, we show that the well-known Fujisaki–Okamoto transformation [11] can be applied to construct SIM-ID-$\hbox {RSO}_k$-CCA secure IBE from a one-way secure (under CPA attacks) IBE scheme with high min-entropy of ciphertexts in the random oracle model. In other words, to encrypt a message m with identity $\textsf {id}$ (and randomness r), the encryption algorithm computes as follows:

$$\begin{aligned} C:=(\textsf {Enc} (pp,\textsf {id},r;H(r,m\oplus G(r))),m\oplus G(r)), \end{aligned}$$

where $\textsf {Enc}$ is the encryption algorithm of the underlying IBE scheme (pp is the public parameter), and both G and H are hash functions.

Related works Since formalized by Bellare et al. in [3], PKE with SO security has been extensively studied. Numerous constructions of SSO (resp., RSO) secure PKE have been proposed based on various assumptions in previous works [8, 9, 16,17,18,19, 24, 25, 32, 33, 35] (resp., [13, 15, 22, 27,28,29, 34, 35, 42]). Recently, PKE achieving both SSO security and RSO security has been proposed in [31]. Relations among SSO/RSO security and standard security for PKE are also extensively studied in previous works [2, 6, 15, 20, 21, 23, 42].

Bellare et al. [5] initiate the study of SO security in the IBE setting, proposing a general paradigm to achieve SIM-ID-SSO-CPA security from IND-ID-CPA secure and “One-Sided Publicly Openable” (1SPO) IBE schemes. The first SIM-ID-SSO-CCA secure IBE scheme is constructed by Lai et al. [30]. In 2020, Jia et al. [26] present the first SIM-ID-SSO-CCA secure IBE scheme with tight security.

Kitagawa et al. [29] formalize the notion of SIM-ID-RSO-CPA security for IBE, and show that a SIM-ID-RSO-CPA secure IBE scheme can be constructed based only on an IND-ID-CPA secure IBE scheme. Hara et al. [14] formalize SIM-ID-RSO-CCA security for IBE, and show a generic construction of SIM-ID-RSO-CCA secure IBE from an IND-ID-CPA secure IBE scheme and a NIZK system satisfying unbounded simulation soundness and unbounded zero-knowledge property.

Roadmap We firstly recall some preliminaries in Sect. 2. Then, we present formal definitions of SIM-ID-$\hbox {RSO}_k$-CPA/CCA security ($k\ge 1$) for IBE in Sect. 3. We provide a lower bound for SIM-ID-$\hbox {RSO}_k$ secure IBE scheme in Sect. 4. Next, we show a generic construction of IBE achieving SIM-ID-$\hbox {RSO}_k$-CCA security in Sect. 5. Finally, we provide a practical SIM-ID-$\hbox {RSO}_k$-CCA secure IBE scheme in Sect. 6.

2 Preliminaries

Notations Let $\lambda \in {\mathbb {N}}$ denote the security parameter. For any $n\in {\mathbb {N}}$, we use [n] to denote the set $\{1, 2, \ldots , n\}$. For a finite set S, we use |S| to denote the size of S, and use $s\leftarrow S$ to denote the process of sampling s uniformly from S. For a distribution $\textsf {Dist}$, we use $x\leftarrow \textsf {Dist}$ to denote the process of sampling x from $\textsf {Dist}$.

For a probabilistic algorithm ${\mathcal {A}}$, let ${\mathcal {R}}_{\mathcal {A}}$ denote the randomness space of ${\mathcal {A}}$. We use $y\leftarrow {\mathcal {A}}(x;r)$ denote the process of running ${\mathcal {A}}$ on input x and inner randomness $r\leftarrow {\mathcal {R}}_{{\mathcal {A}}}$ and outputting y. We write $y\leftarrow {\mathcal {A}}(x)$ for $y\leftarrow {\mathcal {A}}(x;r)$ with uniformly chosen $r\in {\mathcal {R}}_{{\mathcal {A}}}$. We write PPT for probabilistic polynomial-time. For a function $f(\lambda )$, we write that $f(\lambda )\le \textsf {negl}(\lambda )$ if it is negligible.

NIZK proof system Let ${\textsf{R}}$ be an efficiently computable binary relation, and ${\textsf{L}}:=\{x\mid \exists w~\text {s.t.}~(x,w)\in {\textsf{R}}\}$. A NIZK proof NIZK for ${\textsf{L}}$ consists of the following three algorithms:

• $\textsf {CRSGen}(1^{\lambda })$: On input the security parameter $1^{\lambda }$, the common reference string (CRS) generation algorithm outputs a CRS crs.

• $\textsf {Prove}(crs,x,w)$: The proving algorithm, taking a CRS crs, a statement $x\in {\textsf{L}}$ and a witness w for the fact that $x\in {\textsf{L}}$ as input, outputs a proof $\pi$.

• $\textsf {Verify}(crs,x,\pi )$: The verification algorithm, taking a CRS crs, a statement $x\in {\textsf{L}}$ and a proof $\pi$ as input, outputs a bit $b\in \{0,1\}$.

It also satisfies the following conditions:

• Completeness For all $\lambda \in {\mathbb {N}}$, all crs generated by $\textsf {CRSGen}$ and all $(x,w)\in {\textsf{R}}$, we always have $\textsf {Verify}(crs,x,\textsf {prove}(crs,x,w))=1$.

• Unbounded Zero-knowledge There is a PPT simulator ${\mathcal {S}}^{(\text {zk})}=({\mathcal {S}}^{(\text {zk})}_1,{\mathcal {S}}^{(\text {zk})}_2)$ such that for any PPT adversary ${\mathcal {A}}$,

  $$\begin{aligned} {\textbf {Adv}}_{\textsf {NIZK},{\mathcal {A}},{\mathcal {S}}^{(\text {zk})}}^{\text {zk}}(\lambda ):=|\Pr [{{\textbf {G}}}_{\textsf {NIZK},{\mathcal {A}}}^{zk-real }(\lambda )=1]-\Pr [{{\textbf {G}}}_{\textsf {NIZK},{\mathcal {A}},{\mathcal {S}}^{(\text {zk})}}^{zk-sim }(\lambda )=1]| \end{aligned}$$

  is negligible, where ${{\textbf {G}}}_{\textsf {NIZK},{\mathcal {A}}}^{zk-real }(\lambda )$ and ${{\textbf {G}}}_{\textsf {NIZK},{\mathcal {A}},{\mathcal {S}}^{(\text {zk})}}^{zk-sim }(\lambda )$ are shown in Fig. 1.

• Unbounded simulation soundness Let ${\mathcal {S}}^{(\text {zk})}=({\mathcal {S}}^{(\text {zk})}_1,{\mathcal {S}}^{(\text {zk})}_2)$ be a PPT simulator for the unbounded zero-knowledge property of NIZK. For any unbounded adversary ${\mathcal {A}}$, the advantage

  $$\begin{aligned} {\textbf {Adv}}_{\textsf {NIZK},{\mathcal {A}},{\mathcal {S}}^{(\text {zk})}}^{\text {sound}}(\lambda ):=\Pr [{{\textbf {G}}}_{\textsf {NIZK},{\mathcal {A}},{\mathcal {S}}^{(\text {zk})}}^{sound }(\lambda )=1] \end{aligned}$$

  is negligible, where ${{\textbf {G}}}_{\textsf {NIZK},{\mathcal {A}},{\mathcal {S}}^{(\text {zk})}}^{sound }(\lambda )$ is shown in Fig. 1.

Fig. 1

Games for defining zero-knowledge property and simulation-soundness of NIZK

Identity-based encryption An identity-based encryption (IBE) scheme consists of four PPT algorithms $(\textsf {Setup} , \textsf {KGen} , \textsf {Enc} ,\textsf {Dec} )$. The setup algorithm $\textsf {Setup} (1^\lambda )$ outputs a public parameter pp and a master secret key msk. The private key generation algorithm $\textsf {KGen} (pp,msk,\textsf {id})$ takes pp, msk and an identity $\textsf {id}$ as input, and outputs a secret key $sk_{\textsf {id}}$ for $\textsf {id}$. The encryption algorithm $\textsf {Enc} (pp,\textsf {id},m)$ taking pp, $\textsf {id}$ and a message $m\in {\mathcal {M}}_{sp }$ as input, outputs a ciphertext c, where ${\mathcal {M}}_{sp }$ is the message space. The decryption algorithm $\textsf {Dec} (pp,sk_{\textsf {id}},c)$, taking pp, $sk_{\textsf {id}}$ and c as input, outputs a message m or $\bot$, which indicates that c is invalid. For correctness, we require that for any (pp, msk) generated by $\textsf {Setup}$, any valid identity $\textsf {id}$ and any valid message m, $\textsf {Dec} (pp,\textsf {KGen} (pp,msk,\textsf {id}),\textsf {Enc} (pp, \textsf {id}, m))=m$ with overwhelming probability.

Now we recall notions of OW-ID-CPA security and IND-ID-CPA security for IBE [7]. Note that the following recalled definition of IND-ID-CPA security considers multiple challenge identities, like [14]. This security notion is equivalent to the original one proposed in [7] except for a polynomial reduction loss based on the number of challenge identities.

Fig. 2

Games for defining OW-ID-CPA security (in Definition 1) and IND-ID-CPA security (in Definition 2) of IBE

Definition 1

(OW-ID-CPA) We say that an IBE scheme $\textsf {IBE} = (\textsf {Setup} ,\textsf {KGen} , \textsf {Enc} , \textsf {Dec} )$ is $\text {OW-ID-CPA secure}$, if for any PPT adversary ${\mathcal {A}}$,

$$\begin{aligned} \textbf{Adv}_{\textsf {IBE} , {\mathcal {A}}}^{\text {ow-id-cpa} }(\lambda ) :=\Pr [{\textbf {G}} _{\textsf{IBE},{\mathcal {A}}}^{ow-id-cpa }(\lambda )=1] \end{aligned}$$

is negligible, where ${\textbf {G}} _{\textsf{IBE},{\mathcal {A}}}^{ow-id-cpa }(\lambda )$ is defined in Fig. 2.

Definition 2

(IND-ID-CPA) We say that an IBE scheme $\textsf {IBE} = (\textsf {Setup} ,\textsf {KGen} , \textsf {Enc} , \textsf {Dec} )$ is $\text {IND-ID-CPA secure}$, if for any polynomially bounded $n>0$ and any PPT adversary ${\mathcal {A}}$,

$$\begin{aligned} \textbf{Adv}_{\textsf {IBE} , {\mathcal {A}},n}^{\text {ind-id-cpa} }(\lambda ) :=\Pr [{\textbf {G}} _{\textsf{IBE},{\mathcal {A}},n}^{ind-id-cpa }(\lambda )=1] \end{aligned}$$

is negligible, where ${\textbf {G}} _{\textsf{IBE},{\mathcal {A}},n}^{ind-id-cpa }(\lambda )$ is defined in Fig. 2.

3 RSO security in the multi-challenge setting for IBE

In this section, we introduce simulation-based receiver selective opening security in the multi-challenge setting for IBE, which we call SIM-ID-$\text {RSO}_k$-CPA/CCA security ($k\ge 1$).

Definition 3

(SIM-ID-RSO$_{k}$-CPA/CCA security) We say that an IBE scheme $\textsf {IBE} = (\textsf {Setup} ,\textsf {KGen} , \textsf {Enc} , \textsf {Dec} )$ is $\text {SIM-ID-RSO} _{k}\text {-ATK}$ $\text {secure}$ ($\text {ATK} \in \{\text {CPA} ,\text {CCA} \}$), if for any polynomially bounded $n>0$ and any PPT adversary ${\mathcal {A}}$, there exists a PPT simulator ${\mathcal {S}}$, such that for any PPT distinguisher ${\mathcal {D}}$,

$$\begin{aligned} \textbf{Adv}_{\textsf {IBE} , {\mathcal {A}},{\mathcal {S}},{\mathcal {D}},n}^{\text {rso} _{k}\text {-atk} }(\lambda ):= & {} |\Pr [{\mathcal {D}}({\textbf{G}}_{\textsf {IBE} , {\mathcal {A}},n}^{\text {rso} _k\text {-atk-real} }(\lambda ))=1]\\{} & {} -\Pr [{\mathcal {D}}({\textbf{G}}_{\textsf {IBE} , {\mathcal {S}},n}^{\text {rso} _k\text {-atk-ideal} }(\lambda ))=1]| \end{aligned}$$

is negligible, where ${\textbf{G}}_{\textsf {IBE} , {\mathcal {A}},n}^{\text {rso} _k\text {-atk-real} }(\lambda )$ and ${\textbf{G}}_{\textsf {IBE} , {\mathcal {S}},n}^{\text {rso} _k\text {-atk-ideal} }(\lambda )$ are both defined in Fig. 3, and $\text {atk} \in \{\text {cpa} ,\text {cca} \}$.

Fig. 3

Games for defining SIM-ID-$\text {RSO}_{k}$-CPA security and SIM-ID-$\text {RSO}_{k}$-CCA security (in Definition 3) for IBE, where ${\mathcal {I}}\subset [n]$. Boxed code is only executed in the games specified by the game names in the same box style

In game ${\textbf{G}}_{\textsf {IBE} , {\mathcal {A}},n}^{\text {rso} _k\text {-atk-real} }(\lambda )$ ($\text {atk}\in \{\text {cpa},\text {cca}\}$), we use ${\mathcal {L}}_{\text {id}}$ to denote the identities whose secret keys have been generated, and use ${\mathcal {L}}$ to denote these identities and the corresponding secret keys.

4 Lower bound for IBE with $\text {RSO}_{k}$ security

In this section, we show a lower bound for IBE with SIM-ID-$\text {RSO}_{k}$ ($k\ge 1$) security. The idea is inspired by the work of Yang et al. [42]. Generally speaking, we show that the conclusion of lower bound (proposed in [42]) on the secret key size of $\hbox {RSO}_k$ secure encryption scheme in the PKE setting also holds in the IBE setting, i.e., assuming that the secret key space is $\{0,1\}^{\ell _{\text {sk}}}$ and the message space is $\{0,1\}^{\ell _{\text {m}}}$ for some $\ell _{\text {sk}},\ell _{\text {m}}\in {\mathbb {N}}$, an IBE scheme cannot be SIM-ID-$\text {RSO}_{k}$-CPA secure if the length of its secret key is not k times larger than the length of message.

Formally, we have the following theorem.

Theorem 1

Let $\textsf {IBE} = (\textsf {Setup} ,\textsf {KGen} , \textsf {Enc} , \textsf {Dec} )$ be an IBE scheme with secret key space ${{\mathcal {S}}}{{\mathcal {K}}}_{sp }$ and message space ${\mathcal {M}}_{sp }$, where $|{{\mathcal {S}}}{{\mathcal {K}}}_{sp }|=2^{\ell _{sk }}$ and $|{\mathcal {M}}_{sp }|=2^{\ell _{m }}$. If $\ell _{sk }\le \ell _{m }k-1$, then $\textsf {IBE}$ is not SIM-ID-$\text {RSO}_{k}$-CPA secure in the non-programmable random oracle model.

According to Theorem 1, even if $\textsf {IBE}$ is SIM-ID-RSO-CCA secure, when $\ell _{sk }<\ell _{m }k$, it is not SIM-ID-$\hbox {RSO}_k$-CPA secure in the non-programmable random oracle model. In other words, in the IBE setting, RSO security in the single-challenge setting is not enough to guarantee RSO security in the multi-challenge setting.

Next, we turn to the proof of Theorem 1.

Proof

Let $H:\{0,1\}^*\rightarrow \{0,1\}^{\ell _{h }}$ be a hash function, which will be modeled as a non-programmable random oracle in this proof. We write ${{\mathcal {P}}}{{\mathcal {P}}}_{sp }$, ${{\mathcal {I}}}{{\mathcal {D}}}_{sp }$ and ${\mathcal {C}}_{sp }$ to denote the public parameter space, the identity space and the ciphertext space of $\textsf {IBE}$ respectively. Let $\ell _{pp }:=\lceil \log |{{\mathcal {P}}}{{\mathcal {P}}}_{sp }|\rceil$, and $\ell _{c }:=\lceil \log |{\mathcal {C}}_{sp }|\rceil$, and $\kappa :=\ell _{pp }+\ell _{c }k+2$. Let $n:=\ell _{h }+1$.

Now, we construct a SIM-ID-$\text {RSO}_{k}$-CPA adversary ${\mathcal {A}}=({\mathcal {A}}_1,{\mathcal {A}}_2,{\mathcal {A}}_3)$ and a distinguisher ${\mathcal {D}}$ as shown in Fig. 4. Note that we require that ${\mathcal {A}}$ should not query oracle ${\mathcal {O}}_{\text {KGen}}$, so we omit oracle ${\mathcal {O}}_{\text {KGen}}$ in Fig. 4.

Fig. 4

Adversary ${\mathcal {A}}$ and distinguisher ${\mathcal {D}}$ in attacking SIM-ID-$\text {RSO}_{k}$-CPA security of $\textsf {IBE}$. We omit oracle ${\mathcal {O}}_{\text {KGen}}$ here, since we require that ${\mathcal {A}}$ should not query ${\mathcal {O}}_{\text {KGen}}$. ${\mathcal {U}}_{\ell _{m }nk}$ denotes a uniform distribution over $\{0,1\}^{\ell _{m }nk}$

Correctness of $\textsf {IBE}$ guarantees that

$$\begin{aligned} \Pr [{\mathcal {D}}({\textbf{G}}_{\textsf {IBE} , {\mathcal {A}},n}^{\text {rso} _k\text {-cpa-real} }(\lambda ))=1]\le \textsf {negl}(\lambda ). \end{aligned}$$

(1)

For any fixed PPT simulator ${\mathcal {S}}=({\mathcal {S}}_1,{\mathcal {S}}_2,{\mathcal {S}}_3)$, without loss of generality, we assume that ${\mathcal {S}}_2$ and ${\mathcal {S}}_3$ are both deterministic, i.e., the random coins are sampled by ${\mathcal {S}}_1$ and then given to ${\mathcal {S}}_2$ and ${\mathcal {S}}_3$ via states $s_1$ and $s_2$ respectively. Let

$$\begin{aligned} \delta _{{\mathcal {S}}}=\Pr [{\mathcal {D}}({\textbf{G}}_{\textsf {IBE} , {\mathcal {S}},n}^{\text {rso} _k\text {-cpa-ideal} }(\lambda ))=1]. \end{aligned}$$

Following the idea of [42], if we can show that $\delta _{{\mathcal {S}}}\ge \frac{1}{2\kappa }$, then we obtain that

$$\begin{aligned}{} & {} \textbf{Adv}_{\textsf {IBE} , {\mathcal {A}},{\mathcal {S}},{\mathcal {D}},n}^{\text {rso} _{k}\text {-cca} }(\lambda )\\{} & {} \quad =|\Pr [{\mathcal {D}}({\textbf{G}}_{\textsf {IBE} , {\mathcal {A}},n}^{\text {rso} _k\text {-cca-real} }(\lambda ))=1]-\Pr [{\mathcal {D}}({\textbf{G}}_{\textsf {IBE} , {\mathcal {S}},n}^{\text {rso} _k\text {-cca-ideal} }(\lambda ))=1]|\\{} & {} \quad \ge \frac{1}{2\kappa }-\textsf {negl}(\lambda ), \end{aligned}$$

which is non-negligible. So what remains is to prove $\delta _{{\mathcal {S}}}\ge \frac{1}{2\kappa }$.

Let $r_{{\mathcal {D}}}$ denote the randomness of ${\mathcal {D}}$ (this randomness is used in the decryption algorithm of $\textsf {IBE}$). Consider an auxiliary game ${{\textbf {G}}}^{\text {aux}}_{\textsf {IBE},{\mathcal {S}},{\mathcal {D}},n,k,\kappa }(\lambda )$ as shown in Fig. 5.

Fig. 5

The auxiliary game ${{\textbf {G}}}^{\text {aux}}_{\textsf {IBE},{\mathcal {S}},{\mathcal {D}},n,k,\kappa }(\lambda )$

We postpone the proofs of the following three lemmas.

Lemma 1

$\Pr [{\textbf {G}} ^{aux }_{\textsf {IBE} ,{\mathcal {S}},{\mathcal {D}},n,k,\kappa }(\lambda )=0]\le \frac{1}{4}$.

Lemma 2

$\Pr [{\textbf {G}} ^{aux }_{\textsf {IBE} ,{\mathcal {S}},{\mathcal {D}},n,k,\kappa }(\lambda )=1]\le \kappa \cdot \delta _{{\mathcal {S}}}$.

Lemma 3

$\Pr [{\textbf {G}} ^{aux }_{\textsf {IBE} ,{\mathcal {S}},{\mathcal {D}},n,k,\kappa }(\lambda )=2]\le \frac{1}{4}$.

Combining the three lemmas, we obtain

$$\begin{aligned} 1\le \frac{1}{4}+\kappa \cdot \delta _{{\mathcal {S}}}+\frac{1}{4}, \end{aligned}$$

which implies

$$\begin{aligned} \delta _{{\mathcal {S}}}\ge \frac{1}{2\kappa }, \end{aligned}$$

finishing the proof of this theorem.

Now, we turn to the proofs of the above three lemmas.

Proof of Lemma 1

Assume that ${\textbf {G}} ^{aux }_{\textsf {IBE} ,{\mathcal {S}},{\mathcal {D}},n,k,\kappa }(\lambda )=0$. Then,

• we have ${\mathcal {M}}={\mathcal {U}}_{\ell _{m }nk}$ (for simplicity, we denote this event as $\textsf {evt}_1$), which means that for each $\theta \in [\kappa ]$, $i\in [n]$ and $j\in [k]$, $m^{(\theta )}_{i,j}$ is uniformly random sampled from $\{0,1\}^{\ell _{m }}$;

• we have $(pp^{(\theta -1)},(c^{(\theta -1)}_{n,j})_{j\in [k]})=(pp^{(\theta )},(c^{(\theta )}_{n,j})_{j\in [k]})$ for all $\theta \in \{2,\ldots ,\kappa \}$ (we denote this event as $\textsf {evt}_2$), so we can write pp as $pp^{(\theta )}$, and $(c_{n,j})_{j\in [k]}$ as $(c^{(\theta )}_{n,j})_{j\in [k]}$;

• we have $m^{(\theta )}_{n,j}=\textsf {Dec} (pp,sk^{(\theta )}_{\textsf {id}_n},c_{n,j})$ for all $\theta \in [\kappa ]$ and all $j\in [k]$ (we denote this event as $\textsf {evt}_3$).

Obviously, we derive

$$\begin{aligned} \Pr [{\textbf {G}} ^{aux }_{\textsf {IBE} ,{\mathcal {S}},{\mathcal {D}},n,k,\kappa }(\lambda )=0]\le \Pr [\textsf {evt}_1\vee \textsf {evt}_2\vee \textsf {evt}_3]. \end{aligned}$$

Note that if fixing any tuple $(pp,(c_{n,1},\ldots ,c_{n,k}),(sk^{(1)}_{\textsf {id}_n},\ldots ,sk^{(\kappa )}_{\textsf {id}_n}))$, which is not necessary the output of ${\mathcal {S}}_3$, then we have

$$\begin{aligned} \Pr [\forall ~\theta \in [\kappa ], ~j\in [k], ~m^{(\theta )}_{n,j}=\textsf {Dec} (pp,sk^{(\theta )}_{\textsf {id}_n},c_{n,j})]=\frac{1}{2^{\ell _{\text {m}}k\kappa }}, \end{aligned}$$

where the probability is taken over the random choice of each $m^{(\theta )}_{n,j}$ ($\theta \in [\kappa ], j\in [k]$).

We also note that total number of possible $(pp,(c_{n,1},\ldots ,c_{n,k}),(sk^{(1)}_{\textsf {id}_n},\ldots ,sk^{(\kappa )}_{\textsf {id}_n}))$ is at most $2^{\ell _{\text {pp}}+\ell _{\text {c}}k+\ell _{\text {sk}}\kappa }=2^{(\ell _{\text {sk}}+1)\kappa -2}$. Hence,

$$\begin{aligned}{} & {} \Pr [\textsf {evt}_1\vee \textsf {evt}_2\vee \textsf {evt}_3]\\{} & {} \quad \le \Pr [\exists ~(pp,(c_{n,1},\ldots ,c_{n,k}),(sk^{(1)}_{\textsf {id}_n},\ldots ,sk^{(\kappa )}_{\textsf {id}_n})):\\{} & {} \qquad \forall ~\theta \in [\kappa ], ~j\in [k], ~m^{(\theta )}_{n,j}=\textsf {Dec} (pp,sk^{(\theta )}_{\textsf {id}_n},c_{n,j})]\\{} & {} \quad \le \frac{2^{(\ell _{\text {sk}}+1)\kappa -2}}{2^{\ell _{\text {m}}k\kappa }}\le \frac{2^{((\ell _{\text {m}}k-1)+1)\kappa -2}}{2^{\ell _{\text {m}}k\kappa }}=\frac{1}{4}. \end{aligned}$$

So we obtain

$$\begin{aligned} \Pr [{\textbf {G}} ^{aux }_{\textsf {IBE} ,{\mathcal {S}},{\mathcal {D}},n,k,\kappa }(\lambda )=0]\le \Pr [\textsf {evt}_1\vee \textsf {evt}_2\vee \textsf {evt}_3]\le \frac{1}{4}. \end{aligned}$$

$\square$

Proof of Lemma 2

Note that the randomness of ${{\textbf {G}}}^{\text {aux}}_{\textsf {IBE},{\mathcal {S}},{\mathcal {D}},n,k,\kappa }(\lambda )$ comes from the randomness of ${\mathcal {S}}$ (i.e., $r_{{\mathcal {S}}}\leftarrow {\mathcal {R}}_{{\mathcal {S}}}$), $r_{{\mathcal {D}}}\leftarrow {\mathcal {R}}_{{\mathcal {D}}}$ and $(m^{(\theta )}_{i,j})_{i\in [n],j\in [k]}\leftarrow {\mathcal {M}}$. Let

$$\begin{aligned} f(r_{{\mathcal {D}}},r_{{\mathcal {S}}}):= & {} \Pr [((\textsf {id}_i)_{i\in [n]},{\mathcal {M}},s_1)={\mathcal {S}}_1(1^{\lambda };r_{{\mathcal {S}}}); ~({\mathcal {I}},s_2)= {\mathcal {S}}_2(s_1);\\{} & {} \quad (m_{i,j})_{i\in [n],j\in [k]}\leftarrow {\mathcal {M}}; ~out={\mathcal {S}}_3((m_{i,j})_{i\in {\mathcal {I}},j\in [k]},s_2):\\{} & {} \quad {\mathcal {D}}((\textsf {id}_i)_{i\in [n]},(m_{i,j})_{i\in [n],j\in [k]},{\mathcal {M}},{\mathcal {I}},out)=1] \end{aligned}$$

where the probability is taken over the random choice of $~(m_{i,j})_{i\in [n],j\in [k]}$. Letting ${\mathbb {E}}_{x\leftarrow X}(x):=\sum _{x}\Pr [X=x]\cdot x$ denote the expectation of the random variable X, we have

$$\begin{aligned} \Pr [{\textbf {G}} ^{aux }_{\textsf {IBE} ,{\mathcal {S}},{\mathcal {D}},n,k,\kappa }(\lambda )=1]= & {} {\mathbb {E}}_{r_{{\mathcal {D}}}\leftarrow {\mathcal {R}}_{{\mathcal {D}}},r_{{\mathcal {S}}}\leftarrow {\mathcal {R}}_{{\mathcal {S}}}}(1-(1-f(r_{{\mathcal {D}}},r_{{\mathcal {S}}}))^{\kappa })\\\le & {} {\mathbb {E}}_{r_{{\mathcal {D}}}\leftarrow {\mathcal {R}}_{{\mathcal {D}}},r_{{\mathcal {S}}}\leftarrow {\mathcal {R}}_{{\mathcal {S}}}}(\kappa \cdot f(r_{{\mathcal {D}}},r_{{\mathcal {S}}}))\\= & {} \kappa \cdot {\mathbb {E}}_{r_{{\mathcal {D}}}\leftarrow {\mathcal {R}}_{{\mathcal {D}}},r_{{\mathcal {S}}}\leftarrow {\mathcal {R}}_{{\mathcal {S}}}}(f(r_{{\mathcal {D}}},r_{{\mathcal {S}}}))\\= & {} \kappa \cdot \delta _{{\mathcal {S}}}. \end{aligned}$$

$\square$

Proof of Lemma 3

Denote the number of queries to H by $q_{H}$. Since H is modeled as a non-programmable random oracle, the probability that there are two distinct queries $x_1,x_2$ satisfying that $H(x_1)=H(x_2)$ is less than $\frac{q_H^2}{2^{\ell _{\text {h}}}}$, which is negligible.

If $\Pr [{\textbf {G}} ^{aux }_{\textsf {IBE} ,{\mathcal {S}},{\mathcal {D}},n,k,\kappa }(\lambda )=2]> \frac{1}{4}$, then via running this game, one can find $\theta \in \{2,\ldots ,\kappa \}$ satisfying that

• (1) $(pp^{(\theta -1)},(c^{(\theta -1)}_{i,j})_{i\in [n],j\in [k]})\ne (pp^{(\theta )},(c^{(\theta )}_{i,j})_{i\in [n],j\in [k]})$;

• (2) $H(pp^{(\theta -1)},(\textsf {id}_i,c^{(\theta -1)}_{i,j})_{i\in [n],j\in [k]})=H(pp^{(\theta )},(\textsf {id}_i,c^{(\theta )}_{i,j})_{i\in [n],j\in [k]})=(t[1],\ldots ,t[h])$, where $t[i]=1$ if and only if $i\in {\mathcal {I}}$,

with probability greater than $\frac{1}{4}$, which is obviously non-negligible, contradicting the collision resistant property of H. $\square$

Remark 1

As pointed out in [4] and restated in [42], impossibility result in the non-programmable random oracle model does not extend to that in the standard model naturally, since the adversary in the non-programmable random oracle model is allowed to query the random oracle and thus is stronger than an adversary in the standard model. So Theorem 1 does not rule out the achievability of SIM-$\hbox {RSO}_k$ secure IBE when $\ell _{sk }\le \ell _{m }k-1$ in the standard model.

Similar to [42], the proof of Theorem 1 can be modified to achieve the same lower bound in the standard model, but only in the auxiliary-input model. More specifically, the modified proof is the same as the proof of Theorem 1, except that (1) H is a collision-resistant (CR) hash function, instead of being modeled as a non-programmable random oracle, and (2) the proof is given in the auxiliary input model, i.e., all participants, including ${\mathcal {A}}$, ${\mathcal {D}}$ and ${\mathcal {S}}$, are all given some common auxiliary input (a random key of the CR hash function) at the beginning.

5 Generic construction of SIM-ID-$\hbox {RSO}_k$-CCA secure IBE

In this section, we show a generic construction of IBE, achieving SIM-ID-$\hbox {RSO}_k$-CCA security, based on an IND-ID-CPA secure IBE scheme and a non-interactive zero-knowledge (NIZK) proof system, via the double encryption technique [36, 38].

Generic construction Let $\textsf {IBE} = (\textsf {Setup} ,\textsf {KGen} , \textsf {Enc} , \textsf {Dec} )$ be an IND-ID-CPA secure IBE scheme with an identity space ${{\mathcal {I}}}{{\mathcal {D}}}\times [k]\times \{0,1\}$ and a message space $\{0,1\}$, for some set ${{\mathcal {I}}}{{\mathcal {D}}}$. Let $\textsf {NIZK}=(\textsf {CRSGen} ,\textsf {Prove} ,\textsf {Verify} )$ be a NIZK proof system for language

We construct an IBE scheme $\textsf {IBE} '= (\textsf {Setup} ',\textsf {KGen} ', \textsf {Enc} ', \textsf {Dec} ')$ with the identity space ${{\mathcal {I}}}{{\mathcal {D}}}$ and the message space $\{0,1\}$ as in Fig. 6.

Fig. 6

IBE scheme $\textsf {IBE} '= (\textsf {Setup} ',\textsf {KGen} ', \textsf {Enc} ', \textsf {Dec} ')$

The correctness of $\textsf {IBE} '$ is straightforward guaranteed by the correctness of $\textsf {IBE}$ and the completeness of $\textsf {NIZK}$. Now we turn to the security analysis. Formally, we have the following theorem.

Theorem 2

If $\textsf {IBE}$ is an IND-ID-CPA secure IBE scheme, and $\textsf {NIZK}$ is a NIZK proof system satisfying unbounded zero-knowledge property and unbounded simulation soundness, then $\textsf {IBE} '$ is SIM-ID-$\hbox {RSO}_k$-CCA secure.

Proof

For any polynomial $n>0$, any PPT adversary ${\mathcal {A}}$ and any PPT distinguisher ${\mathcal {D}}$, we consider the following games ${{\textbf {G}}}_0$–${{\textbf {G}}}_5$.

${{{\textbf {Game}}}\ {{\textbf {G}}}_0:}$ This game is exactly the same as ${\textbf{G}}_{\textsf {IBE} ', {\mathcal {A}},n}^{\text {rso} _k\text {-cca-real} }(\lambda )$. Specifically, the challenger interacts with ${\mathcal {A}}$ as follows.

• (1) The challenger firstly computes $(pp,msk)\leftarrow \textsf {Setup} (1^\lambda )$ and $crs\leftarrow \textsf {CRSGen} (1^{\lambda })$, and sets $PP:=(pp,crs)$ and $MSK:=msk$. Then, it prepares five sets ${\mathcal {L}}_{\text {id}}:=\emptyset$, ${\mathcal {L}}:=\emptyset$, ${\mathcal {L}}':=\emptyset$, ${\mathcal {L}}_{\text {chal}}:=\emptyset$ and ${\mathcal {C}}:=\emptyset$, and sends PP to ${\mathcal {A}}_1$. The challenger answers ${\mathcal {A}}_1$’s oracle queries as follows:

  • ${{\mathcal {O}}_{\text {KGen}}(\textsf {id}):}$ Since ${\mathcal {C}}=\emptyset$, the challenger directly checks whether $\textsf {id}$ belongs to ${\mathcal {L}}_\text {id}$ or not.

    • If $\textsf {id}\notin {\mathcal {L}}_{\text {id}}$, then for each $\eta \in [k]$, it samples $\alpha _{\eta }\leftarrow \{0,1\}$, and generates $sk_{\textsf {id},\eta ,\alpha _{\eta }}\leftarrow \textsf{KGen}(pp,msk,(\textsf {id},\eta ,\alpha _{\eta }))$. Then it sets that $SK_{\textsf {id}}:=((\alpha _{\eta },sk_{\textsf {id},\eta ,\alpha _{\eta }})_{\eta \in [k]},\textsf {id})$, appends $\textsf {id}$ (resp., $(\textsf {id},SK_{\textsf {id}})$) to ${\mathcal {L}}_{\text {id}}$ (resp., ${\mathcal {L}}$), and returns $SK_{\textsf {id}}$ to ${\mathcal {A}}_1$.

    • If $\textsf {id}\in {\mathcal {L}}_{\text {id}}$, which means that there is some $(\textsf {id},SK_{\textsf {id}})\in {\mathcal {L}}$, then it returns $SK_{\textsf {id}}$ to ${\mathcal {A}}_1$.

  • ${{\mathcal {O}}_{\text {Dec}}(\textsf {id},C):}$ The challenger checks whether $\textsf {id}$ belongs to ${\mathcal {L}}_{\text {id}}$.

    • If $\textsf {id}\notin {\mathcal {L}}_{\text {id}}$, then for each $\eta \in [k]$, it samples $\alpha _{\eta }\leftarrow \{0,1\}$, and generates $sk_{\textsf {id},\eta ,\alpha _{\eta }}\leftarrow \textsf{KGen}(pp,msk,(\textsf {id},\eta ,\alpha _{\eta }))$. Then it sets that $SK_{\textsf {id}}:=((\alpha _{\eta },sk_{\textsf {id},\eta ,\alpha _{\eta }})_{\eta \in [k]},\textsf {id})$.

    • If $\textsf {id}\in {\mathcal {L}}_{\text {id}}$, which means that there is some $(\textsf {id},SK_{\textsf {id}})\in {\mathcal {L}}$, then it retrieves $SK_{\textsf {id}}$ from ${\mathcal {L}}$.

    The challenger parse $SK_{\textsf {id}}=((\alpha _{\eta },sk_{\textsf {id},\eta ,\alpha _{\eta }})_{\eta \in [k]},\textsf {id})$ and $C=((c_{\eta ,\beta })_{\eta \in [k],\beta \in \{0,1\}},\pi )$, and sets that $x:=(pp,\textsf {id},(c_{\eta ,\beta })_{\eta \in [k],\beta \in \{0,1\}})$. If $\textsf {Verify} (crs,x,\pi )=0$, it returns $\bot$ to ${\mathcal {A}}_1$; otherwise, it computes $\textsf {m} _\eta :=\textsf {Dec} (pp,sk_{\textsf {id},\eta ,\alpha _\eta },c_{\eta ,\alpha _\eta })$ for each $\eta \in [k]$, and then returns $m:=\textsf {m} _1\oplus \cdots \oplus \textsf {m} _{k}$ to ${\mathcal {A}}_1$.

• (2) Receiving $((\textsf {id}_i)_{i\in [n]},{\mathcal {M}})$ from ${\mathcal {A}}_1$, the challenger proceeds as follows. For each $i\in [n]$, it firstly generates $SK_{\textsf {id}_i}$. In particular, for each $i\in [n]$ and each $\eta \in [k]$, it samples $\alpha _{i,\eta }\leftarrow \{0,1\}$, and computes $sk_{\textsf {id}_i,\eta ,\alpha _{i,\eta }}\leftarrow \textsf{KGen}(pp,msk,(\textsf {id}_i,\eta ,\alpha _{i,\eta }))$. Then, for each $i\in [n]$, the challenger sets that $SK_{\textsf {id}_i}:=((\alpha _{i,\eta },sk_{\textsf {id}_i,\eta ,\alpha _{i,\eta }})_{\eta \in [k]},\textsf {id}_i)$, and appends $\textsf {id}_i$ (resp., $(\textsf {id}_i,SK_{\textsf {id}_i})$) to ${\mathcal {L}}_{\text {id}}$ (resp., ${\mathcal {L}}$). After that, it samples $(m^*_{i,j})_{i\in [n],j\in [k]} \leftarrow {\mathcal {M}}$. For each $i\in [n]$ and $j\in [k]$, the challenger generates a challenge ciphertext $C^*_{i,j}$ for $m^*_{i,j}$ as follows.

  • (a) It firstly samples $\textsf {m} _{i,j,\eta }\leftarrow \{0,1\}$ for each $\eta \in [k]$ and $\eta \ne j$, and sets $\textsf {m} _{i,j,j}:=(\oplus _{\eta \in [k]\wedge \eta \ne j}\textsf {m} _{i,j,\eta })\oplus m^*_{i,j}$.

  • (b) For each $\eta \in [k]$ and each $\beta \in \{0,1\}$, the challenger samples $r_{i,j,\eta ,\beta }\leftarrow {\mathcal {R}}_{\textsf {Enc} }$, and computes $c_{i,j,\eta ,\beta }=\textsf {Enc} (pp,(\textsf {id}_i,\eta ,\beta ),\textsf {m} _{i,j,\eta };r_{i,j,\eta ,\beta })$.

  • (c) The challenger computes $\pi _{i,j}\leftarrow \textsf {Prove} (crs,(pp,\textsf {id}_i,(c_{i,j,\eta ,\beta })_{\eta \in [k],\beta \in \{0,1\}}),((\textsf {m} _{i,j,\eta },r_{i,j,\eta ,\beta })_{\eta \in [k],\beta \in \{0,1\}}))$.

  • (d) It sets $C^*_{i,j}:=((c_{i,j,\eta ,\beta })_{\eta \in [k],\beta \in \{0,1\}},\pi _{i,j})$.

• (3) The challenger appends $(\textsf {id}_i,C^*_{i,j})$ to ${\mathcal {C}}$ for each $i\in [n]$ and each $j\in [k]$, and returns $(C^*_{i,j})_{i\in [n],j\in [k]}$ to ${\mathcal {A}}_2$. Then, it answers ${\mathcal {A}}_2$’s oracle queries as follows:

  • ${{\mathcal {O}}_{\text {KGen}}(\textsf {id}):}$ If $\textsf {id}\in \{\textsf {id}_i\mid i\in [n]\}$, the challenger returns $\bot$ to ${\mathcal {A}}_2$ directly. Otherwise, it answers this query as that in Step (1).

  • ${{\mathcal {O}}_{\text {Dec}}(\textsf {id},C):}$ The challenger firstly checks whether $(\textsf {id},C)\in {\mathcal {C}}$. If so, it returns $\bot$ to ${\mathcal {A}}_2$ directly. Otherwise, it checks whether $\textsf {id}$ belongs to ${\mathcal {L}}_{\text {id}}$ or not.

    • If $\textsf {id}\notin {\mathcal {L}}_{\text {id}}$, then for each $\eta \in [k]$, it samples $\alpha _{\eta }\leftarrow \{0,1\}$, and generates $sk_{\textsf {id},\eta ,\alpha _{\eta }}\leftarrow \textsf{KGen}(pp,msk,(\textsf {id},\eta ,\alpha _{\eta }))$. Then it sets that $SK_{\textsf {id}}:=((\alpha _{\eta },sk_{\textsf {id},\eta ,\alpha _{\eta }})_{\eta \in [k]},\textsf {id})$.

    • If $\textsf {id}\in {\mathcal {L}}_{\text {id}}$, which means that there is some $(\textsf {id},SK_{\textsf {id}})\in {\mathcal {L}}$, then it retrieves $SK_{\textsf {id}}$ from ${\mathcal {L}}$.

    The challenger parse $SK_{\textsf {id}}=((\alpha _{\eta },sk_{\textsf {id},\eta ,\alpha _{\eta }})_{\eta \in [k]},\textsf {id})$ and $C=((c_{\eta ,\beta })_{\eta \in [k],\beta \in \{0,1\}},\pi )$, and sets that $x:=(pp,\textsf {id},(c_{\eta ,\beta })_{\eta \in [k],\beta \in \{0,1\}})$. If $\textsf {Verify} (crs,x,\pi )=0$, it returns $\bot$ to ${\mathcal {A}}_2$; otherwise, it computes $\textsf {m} _\eta :=\textsf {Dec} (pp,sk_{\textsf {id},\eta ,\alpha _\eta },c_{\eta ,\alpha _\eta })$ for each $\eta \in [k]$, and then returns $m:=\textsf {m} _1\oplus \cdots \oplus \textsf {m} _{k}$ to ${\mathcal {A}}_2$.

• (4) Receiving ${\mathcal {I}}\subset [n]$ from $A_2$, the challenger returns $(SK_{\textsf {id}_i},m^*_{i,j})_{i\in [n],j\in [k]}$ to ${\mathcal {A}}_3$, and answers ${\mathcal {A}}_3$’s oracle queries exactly as in Step (3).

• (5) Finally, upon receiving ${\mathcal {A}}_3$’s final output out, the challenger outputs $((\textsf {id}_i)_{i\in [n]},(m^*_{i,j})_{i\in [n],j\in [k]}, {\mathcal {M}}, {\mathcal {I}}, out)$.

${{\textbf {Game}}\ {{\textbf {G}}}_{1}:}$ This game is the same as ${{\textbf {G}}}_0$, except that when generating the CRS and the proofs, the challenger employs the simulator ${\mathcal {S}}^{(\text {zk})}=({\mathcal {S}}^{(\text {zk})}_1,{\mathcal {S}}^{(\text {zk})}_2)$ for the unbounded zero-knowledge property of NIZK, instead of generating them honestly. More specifically, in Step (1), the challenger computes $(crs,td)\leftarrow {\mathcal {S}}^{(\text {zk})}_1(1^{\lambda })$; for each $i\in [n]$ and $j\in [k]$, in (c) of Step (2), the challenger computes $\pi _{i,j}\leftarrow {\mathcal {S}}^{(\text {zk})}_2(crs,td,(pp,\textsf {id}_i,(c_{i,j,\eta ,\beta })_{\eta \in [k],\beta \in \{0,1\}}))$.

The unbounded zero-knowledge property of NIZK guarantees that

$$\begin{aligned} |\Pr [{\mathcal {D}}({\textbf{G}}_1)=1]-\Pr [{\mathcal {D}}({\textbf{G}}_0)=1]|\le {\textbf {Adv}}_{\textsf {NIZK},{\mathcal {A}}_{\text {zk}},{\mathcal {S}}^{(\text {zk})}}^{\text {zk}}(\lambda ) \end{aligned}$$

(2)

for some adversary ${\mathcal {A}}_{\text {zk}}$.

${{\textbf {Game}}\ {{\textbf {G}}}_{2}:}$ This game is the same as ${{\textbf {G}}}_1$, except for the generation of the challenge ciphertexts. More specifically, for each $i\in [n]$ and $j\in [k]$, the challenger computes $c_{i,j,j,1\oplus \alpha _{i,j}}\leftarrow \textsf {Enc} (pp,(\textsf {id}_i,j,1\oplus \alpha _{i,j}),1\oplus \textsf {m} _{i,j,j})$ instead of $c_{i,j,j,1\oplus \alpha _{i,j}}\leftarrow \textsf {Enc} (pp,(\textsf {id}_i,j,1\oplus \alpha _{i,j}),\textsf {m} _{i,j,j})$ in (b) of Step (2). Note that this change can be seen as letting $\textsf {m} '_{i,j,j}:=\textsf {m} _{i,j,j}\oplus \alpha _{i,j}=((\oplus _{\eta \in [k]\wedge \eta \ne j}\textsf {m} _{i,j,\eta })\oplus m^*_{i,j})\oplus \alpha _{i,j}$, the challenger computes

$$\begin{aligned} c_{i,j,j,0}\leftarrow & {} \textsf {Enc} (pp,(\textsf {id}_i,j,0),\textsf {m} '_{i,j,j}) \\ c_{i,j,j,1}\leftarrow & {} \textsf {Enc} (pp,(\textsf {id}_i,j,1),1\oplus \textsf {m} '_{i,j,j}) \end{aligned}$$

for each $i\in [n]$ and $j\in [k]$ in (b) of Step (2).

Now we show that ${{\textbf {G}}}_2$ and ${{\textbf {G}}}_1$ are computationally indistinguishable. Note that in these two games, for each $i\in [n]$, (i) the challenger only uses $SK_{\textsf {id}_i}=((\alpha _{i,\eta },sk_{\textsf {id}_i,\eta ,\alpha _{i,\eta }})_{\eta \in [k]},\textsf {id}_i)$ to answer ${\mathcal {A}}$’s decryption queries and selective opening queries, and (ii) if ${\mathcal {A}}_2$ or ${\mathcal {A}}_3$ submits $\textsf {id}_i$ to ${\mathcal {O}}_{\text {KGen}}$, the challenger will return $\bot$ as a response.¹ In other words, $sk_{\textsf {id}_i,\eta ,1\oplus \alpha _{i,\eta }}$ for any $i\in [n]$ and any $\eta \in [k]$ will never be used. So for all $i\in [n]$ and $\eta \in [k]$, $sk_{\textsf {id}_i,\eta ,1\oplus \alpha _{i,\eta }}$ is hidden from the view of ${\mathcal {A}}$. Thus, IND-ID-CPA security of $\textsf {IBE}$ guarantees that

$$\begin{aligned} |\Pr [{\mathcal {D}}({\textbf{G}}_2)=1]-\Pr [{\mathcal {D}}({\textbf{G}}_1)=1]|\le \textbf{Adv}_{\textsf {IBE} , {\mathcal {A}}_{\text {ibe}},nk}^{\text {ind-id-cpa} }(\lambda ) \end{aligned}$$

(3)

for some adversary ${\mathcal {A}}_{\text {ibe}}$.

${{\textbf {Game}}\ {{\textbf {G}}}_3:}$ This game is the same as ${{\textbf {G}}}_2$, except for the generation of secret keys for the challenge identities $(\textsf {id}_i)_{i\in [n]}$ in Step (2). More specifically, in this game, when generating a secret key for $\textsf {id}_{i}$ ($i\in [n]$) in Step (2), besides generating $SK_{\textsf {id}_i}=((\alpha _{i,\eta },sk_{\textsf {id}_i,\eta ,\alpha _{i,\eta }})_{\eta \in [k]},\textsf {id}_i)$, the challenger additionally proceeds as follows:

• (i) Compute $sk_{\textsf {id}_i,\eta ,1\oplus \alpha _{i,\eta }}\leftarrow \textsf {KGen} (pp,msk,(\textsf {id}_i,\eta ,1\oplus \alpha _{i,\eta }))$ for each $\eta \in [k]$, set that $SK'_{\textsf {id}_i}:=((1\oplus \alpha _{i,\eta },sk_{\textsf {id}_i,\eta ,1\oplus \alpha _{i,\eta }})_{\eta \in [k]},\textsf {id}_i)$, and append $(\textsf {id}_i, SK'_{\textsf {id}_i})$ into ${\mathcal {L}}'$.

• (ii) Append $(\textsf {id}_i, (sk_{\textsf {id}_i,\eta ,0},sk_{\textsf {id}_i,\eta ,1})_{\eta \in [k]})$ into ${\mathcal {L}}_{\text {chal}}$.

Note that this change does not affect the view of ${\mathcal {A}}$. Hence,

$$\begin{aligned} \Pr [{\mathcal {D}}({\textbf{G}}_3)=1]=\Pr [{\mathcal {D}}({\textbf{G}}_2)=1]. \end{aligned}$$

(4)

${{\textbf {Game}}\ {{\textbf {G}}}_{4}:}$ This game is the same as ${{\textbf {G}}}_3$, except for the way to answer ${\mathcal {A}}$’s key generation queries. More specifically, upon receiving a key generation query $\textsf {id}$ to ${\mathcal {O}}_{\text {KGen}}$, besides generating $SK_{\textsf {id}}=((\alpha _{\eta },sk_{\textsf {id},\eta ,\alpha _{\eta }})_{\eta \in [k]},\textsf {id})$, the challenger additionally generates $SK'_{\textsf {id}}=((1\oplus \alpha _{\eta },sk_{\textsf {id},\eta ,1\oplus \alpha _{\eta }})_{\eta \in [k]},\textsf {id})$ and appends $(\textsf {id}, SK'_{\textsf {id}})$ into ${\mathcal {L}}'$. Note that this is a conceptual change, so it does not affect the view of ${\mathcal {A}}$. Thus,

$$\begin{aligned} \Pr [{\mathcal {D}}({\textbf{G}}_4)=1]=\Pr [{\mathcal {D}}({\textbf{G}}_3)=1]. \end{aligned}$$

(5)

We also note that in this and subsequent games, for any $\textsf {id}$ and any $\eta \in [k]$, if $sk_{\textsf {id},\eta ,\alpha _{\eta }}$ has been stored in ${\mathcal {L}}$, and both $sk_{\textsf {id},\eta ,0}$ and $sk_{\textsf {id},\eta ,1}$ have been generated and can be retrieved.

${{\textbf {Game}}\ {{\textbf {G}}}_{5}:}$ This game is the same as ${{\textbf {G}}}_4$, except for the way to answer ${\mathcal {A}}$’s decryption queries. More precisely, for any decryption query $(\textsf {id},C)$, the challenger will use $sk_{\textsf {id},\eta ,0}$ instead of $sk_{\textsf {id},\eta ,\alpha _{\eta }}$ to answer this query.

The unbounded simulation soundness of $\textsf {NIZK}$ guarantees that

$$\begin{aligned} |\Pr [{\mathcal {D}}({\textbf{G}}_5)=1]-\Pr [{\mathcal {D}}({\textbf{G}}_4)=1]|\le {\textbf {Adv}}_{\textsf {NIZK},{\mathcal {A}}'_{\text {zk}},{\mathcal {S}}^{(\text {zk})}}^{\text {sound}}(\lambda ) \end{aligned}$$

(6)

for some adversary ${\mathcal {A}}'_{\text {zk}}$.

${{\textbf {Game}}\ {{\textbf {G}}}_{6}:}$ This game is the same as ${{\textbf {G}}}_5$, except for the way to generate the challenge ciphertexts and answer the selective opening query. More specifically,

• When generating the challenge ciphertexts, the challenger samples $\textsf {m} '_{i,j,j}\leftarrow \{0,1\}$ instead of setting $\textsf {m} '_{i,j,j}:=((\oplus _{\eta \in [k]\wedge \eta \ne j}\textsf {m} _{i,j,\eta })\oplus m^*_{i,j})\oplus \alpha _{i,j}$ for each $i\in [n]$ and $j\in [k]$ in (a) of Step (2).

• The challenger does not sample $\alpha _{i,j}$ for any $i\in [n]$ in Step (2) (note that both $sk_{\textsf {id}_i,j,0}$ and $sk_{\textsf {id}_i,j,1}$ for all $i\in [n]$ and all $j\in [k]$ have been generated and stroed in ${\mathcal {L}}_{\text {chal}}$ since the change introduced in game ${{\textbf {G}}}_3$). Instead, when answering the selective opening query ${\mathcal {I}}\subset [n]$ in Step (4), the challenger sets that $\alpha _{i,j}:=((\oplus _{\eta \in [k]\wedge \eta \ne j}\textsf {m} _{i,j,\eta })\oplus m^*_{i,j})\oplus \textsf {m} '_{i,j,j}$ for all $i\in {\mathcal {I}}$ and $j\in [k]$.

The only difference between ${{\textbf {G}}}_6:$ and ${{\textbf {G}}}_5$ is the order of generations of $\textsf {m} '_{i,j,j}$ and $\alpha _{i,j}$ for some i and some j, and it is easy to see that this difference does not affect ${\mathcal {A}}$’s view in these two games. Hence,

$$\begin{aligned} \Pr [{\mathcal {D}}({\textbf{G}}_6)=1]=\Pr [{\mathcal {D}}({\textbf{G}}_5)=1]. \end{aligned}$$

(7)

Now, we construct a simulator ${\mathcal {S}}=({\mathcal {S}}_1,{\mathcal {S}}_2,{\mathcal {S}}_3)$, which simulates ${\textbf{G}}_6$ perfectly for ${\mathcal {A}}$, as shown in Fig. 7. Obviously,

$$\begin{aligned} {\textbf{G}}_{\textsf {IBE} , {\mathcal {S}},n}^{\text {rso} _k\text {-cca-ideal} }(\lambda )={{\textbf {G}}}_6. \end{aligned}$$

(8)

Fig. 7

Simulator ${\mathcal {S}}=({\mathcal {S}}_1,{\mathcal {S}}_2,{\mathcal {S}}_3)$ in the proof of Theorem 2

Note that ${\textbf{G}}_{\textsf {IBE} ', {\mathcal {A}},n}^{\text {rso} _k\text {-cca-real} }(\lambda )={{\textbf {G}}}_0$, so combining Eqs. (2)–(8), we obtain that

$$\begin{aligned}{} & {} \textbf{Adv}_{\textsf {IBE} ', {\mathcal {A}},{\mathcal {S}},{\mathcal {D}},n}^{\text {rso} _{k}\text {-cca} }(\lambda )\\{} & {} \quad =|\Pr [{\mathcal {D}}({\textbf{G}}_{\textsf {IBE} ', {\mathcal {A}},n}^{\text {rso} _k\text {-cca-real} }(\lambda ))=1]-\Pr [{\mathcal {D}}({\textbf{G}}_{\textsf {IBE} ', {\mathcal {S}},n}^{\text {rso} _k\text {-cca-ideal} }(\lambda ))=1]|\\{} & {} \quad =|\Pr [{\mathcal {D}}({{\textbf {G}}}_0)=1]-\Pr [{\mathcal {D}}({{\textbf {G}}}_6)=1]|\\{} & {} \quad \le {\textbf {Adv}}_{\textsf {NIZK},{\mathcal {A}}_{\text {zk}},{\mathcal {S}}^{(\text {zk})}}^{\text {zk}}(\lambda )+\textbf{Adv}_{\textsf {IBE} , {\mathcal {A}}_{\text {ibe}},n}^{\text {ind-id-cpa} }(\lambda ) +{\textbf {Adv}}_{\textsf {NIZK},{\mathcal {A}}'_{\text {zk}},{\mathcal {S}}^{(\text {zk})}}^{\text {sound}}(\lambda ), \end{aligned}$$

for some adversaries ${\mathcal {A}}_{\text {zk}}$, ${\mathcal {A}}_{\text {ibe}}$ and ${\mathcal {A}}'_{\text {zk}}$. $\square$

Instantiations Note that the NIZK proof system satisfying unbounded zero-knowledge property and unbounded simulation soundness can be constructed based on an ordinary NIZK proof system (i.e., a NIZK proof system satisfying standard zero-knowledge property and standard soundness) via the transformation of [39] without any additional assumption. Hence, when plugging a DLIN-based (resp., LWE-based) IND-ID-CPA secure IBE scheme [40] (resp., [1]) and a DLIN-based (resp., LWE-based) ordinary NIZK proof system [12] (resp., [37]) into our generic construction, we can obtain a concrete DLIN-based (resp., LWE-based) SIM-ID-$\hbox {RSO}_k$-CCA secure IBE scheme.

6 Practical SIM-ID-$\hbox {RSO}_k$-CCA secure IBE scheme

Although we have proposed a generic IBE construction achieving SIM-ID-$\hbox {RSO}_k$-CCA security in Sect. 5, it is inefficient in practical applications. In this section, we show a practical IBE construction achieving SIM-ID-$\hbox {RSO}_k$-CCA security in the random oracle model. More specifically, as shown in [41], the Fujisaki–Okamoto transformation [10] can be applied to the IBE case, generally converting an IBE scheme with OW-ID-CPA security (and high min-entropy of ciphertexts) into an IBE scheme with IND-ID-CCA security in the random oracle model. Now we show that via the Fujisaki–Okamoto transformation [11], the obtained IBE scheme actually achieves SIM-ID-$\hbox {RSO}_k$-CCA security.

Firstly, we introduce a property of IBE in the following definition, which is extended directly from $\gamma$-spread PKE [10, 11].

Definition 4

($\gamma$-spread) Let $\textsf {IBE} = (\textsf {Setup} ,\textsf {KGen} , \textsf {Enc} , \textsf {Dec} )$ be an IBE scheme with identity space ${{\mathcal {I}}}{{\mathcal {D}}}$, message space ${\mathcal {M}}_{\text {sp}}$, ciphertext space ${{\mathcal {C}}}{{\mathcal {T}}}_{\text {sp}}$ and randomness space ${\mathcal {R}}_{\textsf {Enc} }$. For any pp generated by $\textsf {Setup}$, any $\textsf {id} \in {{\mathcal {I}}}{{\mathcal {D}}}$, any $m\in {\mathcal {M}}_{\text {sp}}$ and any $c\in {{\mathcal {C}}}{{\mathcal {T}}}_{\text {sp}}$,

$$\begin{aligned} \Pr [r\leftarrow {\mathcal {R}}_{\textsf {Enc} }: c=\textsf {Enc} (pp,\textsf {id} ,m;r)]\le 2^{-\gamma }. \end{aligned}$$

Let $\textsf {IBE} = (\textsf {Setup} ,\textsf {KGen} , \textsf {Enc} , \textsf {Dec} )$ be an IBE scheme with an identity space ${{\mathcal {I}}}{{\mathcal {D}}}$, a message space ${\mathcal {M}}_{\text {sp}}$ and a randomness space ${\mathcal {R}}_{\textsf {Enc} }$. Consider the IBE scheme $\textsf {FOIBE}=(\textsf {FOSetup} ,\textsf {FOKGen} ,\textsf {FOEnc} ,\textsf {FODec} )$ as shown in Fig. 8, with a message space ${\mathcal {M}}_{\textsf {FO}}:=\{0,1\}^{\ell }$, for some $\ell \in {\mathbb {N}}$, and a randomness space ${\mathcal {R}}_{\textsf {FOEnc} }:={\mathcal {M}}_{\text {sp}}$. Note that the underlying $G:{\mathcal {R}}_{\textsf {FOEnc} }\rightarrow \{0,1\}^{\ell }$ and $H:{\mathcal {R}}_{\textsf {FOEnc} }\times \{0,1\}^{\ell }\rightarrow {\mathcal {R}}_{\textsf {Enc} }$ in Fig.  8. are both hash functions, which will be modeled as random oracles in the security proof.

Fig. 8

IBE scheme $\textsf {FOIBE}=(\textsf {FOSetup} ,\textsf {FOKGen} ,\textsf {FOEnc} ,\textsf {FODec} )$

The correctness of $\textsf {FOIBE}$ is obviously guaranteed by the correctness of $\textsf {IBE}$. For security, we have the following theorem.

Theorem 3

If $\textsf {IBE}$ is an OW-ID-CPA secure, $\gamma$-spread IBE scheme, and both G and H are modeled as random oracles, then $\textsf {FOIBE}$ is SIM-ID-$\hbox {RSO}_k$-CCA secure in the random oracle model.

Before going into the formal proof, we firstly show an intuition of why $\textsf {FOIBE}$ achieves SIM-ID-$\hbox {RSO}_k$-CCA security. For a normally generated ciphertext $C=(e,c)$, we have $c=m\oplus G(r)$ and $e=\textsf {Enc} (pp,\textsf {id},r;H(r,c))$, where $r\leftarrow {\mathcal {R}}_{\textsf {FOEnc} }$. So in the ciphertext C, only c contains the information about the message m, and m is concealed by G(r). Note that as long as r has never been queried to the random oracle ${\mathcal {O}}_{\text {G}}$, the adversary ${\mathcal {A}}$ has no information about m (since ${\mathcal {O}}_{\text {G}}(r)$ is uniformly distributed from ${\mathcal {A}}$’s point of view). Furthermore, note that r is the input “plaintext” of the underlying encryption algorithm $\textsf {Enc}$, so the one-wayness of $\textsf {IBE}$ guarantees that ${\mathcal {A}}$ cannot find out the value of r, which implies that c is uniformly distributed from ${\mathcal {A}}$’s point of view. Hence, if r has never been queried to the random oracles, then both c and $h=H(r,c)$ are uniformly distributed, and $e=\textsf {Enc} (pp,\textsf {id},r;h)$ is independent of m. In this case, in the proof, the challenge ciphertexts can be generated firstly without knowing the challenge messages, and then when answering the selective opening query, the challenge ciphertexts and the corresponding challenge messages are correlated via programming the random oracles. That’s how we deal with the selective opening query in the proof. For the decryption query, via the technique of the Fujisaki–Okamoto transformation [11], the properties of the random oracles implies that the decryption oracle can be simulated without the secret keys (i.e., the modification introduced in the following game ${{\textbf {G}}}_1$).

The formal proof is as follows.

Proof

For any polynomial $n>0$, any PPT adversary ${\mathcal {A}}$ and any PPT distinguisher ${\mathcal {D}}$, let $q_d$ (resp. $q_r$) denote the total number of decryption queries (resp. random-oracle queries) made by ${\mathcal {A}}$. Without loss of generality, we require that the challenger samples the random coins $(r_{i,j}\leftarrow {\mathcal {R}}_{\textsf {FOEnc} })_{i\in [n],j\in [k]}$ before sending the public parameter PP to ${\mathcal {A}}$. We also assume that ${\mathcal {A}}$ will not repeat identical queries to the same oracles.

Since both G and H are modeled as random oracles, we assume that the challenger maintains lists $L_G$ and $L_H$, which are both empty sets at the beginning, and employs them to keep track of the issued calls (either by the game or ${\mathcal {A}}$) of ${\mathcal {O}}_G(t)$ and ${\mathcal {O}}_H(u_1,u_2)$, respectively. Specifically, for a query t submitted to ${\mathcal {O}}_G$, ${\mathcal {O}}_G$ returns $g_t$ if there is an entry $(t,g_t)\in L_G$, otherwise it samples $g_t\leftarrow \{0,1\}^{\ell }$, adds $(t,g_t)$ to $L_G$, and returns $g_t$; similarly, for a query $(u_1,u_2)$ submitted to ${\mathcal {O}}_H$, ${\mathcal {O}}_H$ returns $h_u$ if there is an entry $((u_1,u_2),h_u)\in L_H$, otherwise it samples $h_u\leftarrow {\mathcal {R}}_{\textsf {Enc} }$, adds $((u_1,u_2),h_u)$ to $L_H$, and returns $h_u$.

We proceed in a series of games.

Fig. 9

Games ${{\textbf {G}}}_0$–${{\textbf {G}}}_3$ in the proof of Theorem 3. Boxed code is only executed in the games specified by the game names in the same box style

${{{\textbf {Game}}}\ {{\textbf {G}}}_0:}$ ${{\textbf {G}}}_{0}$ (as shown in Fig. 9) is the real game ${\textbf{G}}_{\textsf {FOIBE} , {\mathcal {A}},n}^{\text {rso} _k\text {-cca-real} }(\lambda )$, i.e.,

$$\begin{aligned} {{\textbf {G}}}_{0}={\textbf{G}}_{\textsf {FOIBE} , {\mathcal {A}},n}^{\text {rso} _k\text {-cca-real} }(\lambda ). \end{aligned}$$

(9)

${{{\textbf {Game}}}\ {{\textbf {G}}}_{1}:}$ Game ${{\textbf {G}}}_{1}$ is the same as ${{\textbf {G}}}_{0}$, except that we change the procedure of the decryption oracle such that the decryption queries can be answered without the secret keys. Specifically, as shown in Fig. 9, for a decryption query $(\textsf {id},(e,c))$ in ${{\textbf {G}}}_{1}$, instead of decrypting e with $sk_{\textsf {id}}$ to obtain ${\hat{r}}$ and querying $({\hat{r}},c)$ to ${\mathcal {O}}_H$, the decryption oracle returns $\bot$ directly if ${\mathcal {A}}$ did not subimt some tuple $({\hat{r}},c)$ to ${\mathcal {O}}_H$ such that $e=\textsf {Enc} (pp,\textsf {id},{\hat{r}};{\mathcal {O}}_H({\hat{r}},c))$.

We note that for any decryption query $(\textsf {id},(e,c))\notin {\mathcal {C}}$, if there exists $(({\hat{r}},c),{\hat{h}})\in L_H$ such that $e=\textsf {Enc} (pp,\textsf {id},{\hat{r}};{\hat{h}})$, then obviously the decryption oracle in game $\text {G}_1$ and that in $\text {G}_0$ will return the same message as a response. Let $\textsf {evt}_0$ denote the event that in game $\text {G}_0$, ${\mathcal {A}}$ submits a decryption query $(\textsf {id},(e,c))\notin {\mathcal {C}}$ such that (i) “$\not \exists ~(({\hat{r}},c),{\hat{h}})\in L_H$ s.t. $e=\textsf {Enc} (pp,\textsf {id},{\hat{r}};{\hat{h}})$”, and (ii) the decryption oracle does not return $\bot$. Note that ${{\textbf {G}}}_{1}$ is the same as ${{\textbf {G}}}_{0}$, except that $\textsf {evt}_0$ occurs. Thus, we have $|\Pr [{\mathcal {D}}({\textbf {G}} _{1})=1]-\Pr [{\mathcal {D}}({\textbf {G}} _{0})=1]|\le \Pr [\textsf {evt}_0].$ The fact that $\textsf {evt}_0$ occurs in ${{\textbf {G}}}_0$ implies that for $r':=\textsf {Dec} (pp,sk_{\textsf {id}},e)$, ${\mathcal {O}}_{\text {H}}(r',c)$ is uniformly and independently sampled from ${\mathcal {R}}_{\textsf {Enc} }$. Since $\textsf {IBE}$ is $\gamma$-spread, $\Pr [e=\textsf {Enc} (pp,\textsf {id},r';{\mathcal {O}}_{\text {H}}(r',c))]\le 2^{-\gamma }$. Hence, we obtain that

$$\begin{aligned} |\Pr [{\mathcal {D}}({\textbf {G}} _{1})=1]-\Pr [{\mathcal {D}}({\textbf {G}} _{0})=1]|\le \Pr [\textsf {evt}_0]\le q_d\cdot 2^{-\gamma }. \end{aligned}$$

(10)

${{\textbf {Game}}\ {{\textbf {G}}}_{2}:}$ Game ${{\textbf {G}}}_{2}$ is the same as ${{\textbf {G}}}_{1}$, except that the challenger aborts this game (with output $\bot$) as long as $\textsf {AbortEARLY}$ occurs. Concretely, as long as ${\mathcal {A}}_1$ submits a random-oracle query t to ${\mathcal {O}}_{\text {G}}$ such that $t\in \{r_{i,j}\mid i\in [n],j\in [k]\}$, or a a random-oracle query $(u_1,u_2)$ to ${\mathcal {O}}_{\text {H}}$ such that $u_1\in \{r_{i,j}\mid i\in [n],j\in [k]\}$, then $\textsf {AbortEARLY}$ is set true, which means that this game is aborted with output $\bot$. The details are shown in Fig. 9.

Note that $r_{i,j}$ for all $i\in [n]$ and $j\in [k]$ is uniformly random distributed from ${\mathcal {A}}_1$’s point of view when obtaining PP. We also note that when ${\mathcal {A}}_1$ queries the random oracles, $\textsf {EvtChal}$ is not set true. Hence,

$$\begin{aligned}{} & {} |\Pr [{\mathcal {D}}({\textbf {G}} _{2})=1]-\Pr [{\mathcal {D}}({\textbf {G}} _{1})=1]|\nonumber \\{} & {} \quad \le \Pr [\textsf {AbortEARLY}] \le \sum _{\theta =1}^{q_r}\frac{nk}{|{\mathcal {R}}_{\textsf {FOEnc} }|-(\theta -1)}\le \frac{nkq_r}{|{\mathcal {R}}_{\textsf {FOEnc} }|-q_r}. \end{aligned}$$

(11)

${{\textbf {Game}}\ {{\textbf {G}}}_{3}:}$ Game ${{\textbf {G}}}_{3}$ is the same as ${{\textbf {G}}}_{2}$, except that (i) during the generation of the challenge ciphertexts, for all $i\in [n]$ and $j\in [k]$, the procedures “$c_{i,j}=m^*_{i,j}\oplus {\mathcal {O}}_{\text {G}}(r_{i,j})$, $h_{i,j}= {\mathcal {O}}_{\text {H}}(r_{i,j},c_{i,j})$” are replaced with “$c_{i,j}\leftarrow \{0,1\}^{\ell }$, $h_{i,j}\leftarrow {\mathcal {R}}_{\textsf {Enc} }$”, instead of querying ${\mathcal {O}}_{\text {G}}$ and ${\mathcal {O}}_{\text {H}}$, and (ii) ${\mathcal {O}}_{\text {G}}(r_{i,j})=c_{i,j}\oplus m^*_{i,j}$ and ${\mathcal {O}}_{\text {H}}(r_{i,j},c_{i,j})=h_{i,j}$ are programmed only when $i\in {\mathcal {I}}$ or $r_{i,j}$ (resp., $(r_{i,j},c_{i,j})$) is submitted to ${\mathcal {O}}_{\text {G}}$ (resp., ${\mathcal {O}}_{\text {H}}$). The details are shown in Fig. 9.

Note that during the generation of the challenge ciphertexts, both $c_{i,j}$ and $h_{i,j}$ are uniformly distributed for all $i\in [n]$ and $j\in [k]$, since the modification introduced in game ${{\textbf {G}}}_2$. So “$c_{i,j}=m^*_{i,j}\oplus {\mathcal {O}}_{\text {G}}(r_{i,j})$, $h_{i,j}= {\mathcal {O}}_{\text {H}}(r_{i,j},c_{i,j})$” can be replaced with “$c_{i,j}\leftarrow \{0,1\}^{\ell }$, $h_{i,j}\leftarrow {\mathcal {R}}_{\textsf {Enc} }$”. The additional procedures for answering ${\mathcal {A}}$’s random-oracle queries and opening queries are introduced to ensure that for all $i\in [n]$ and $j\in [k]$, ${\mathcal {O}}_{\text {G}}(r_{i,j})$ and ${\mathcal {O}}_{\text {H}}(r_{i,j},c_{i,j})$ are programmed consistently. Hence, from ${\mathcal {A}}$’s point of view, these two games are identical, i.e.,

$$\begin{aligned} \Pr [{\mathcal {D}}({\textbf {G}} _{3})=1]-\Pr [{\mathcal {D}}({\textbf {G}} _{2})=1]=0. \end{aligned}$$

(12)

For convenience, we rewrite game ${{\textbf {G}}}_{3}$ in Fig. 10, removing the replaced procedures.

Fig. 10

Games ${{\textbf {G}}}_3$–${{\textbf {G}}}_5$ in the proof of Theorem 3. Boxed code is only executed in the games specified by the game names in the same box style

${{\textbf {Game}}\ {{\textbf {G}}}_{4}:}$ Game ${{\textbf {G}}}_{4}$ is the same as ${{\textbf {G}}}_{3}$, except that the challenger does not generate the secret keys corresponding to the challenge identities (i.e., $(\textsf {id}_i)_{i\in [n]}$), until the identities are submitted to ${\mathcal {O}}_{\text {KGen}}$ or submitted for the selective opening query. The details are shown in Fig. 10.

Note that (i) ${\mathcal {O}}_{\text {Dec}}$ can answer the decryption queries without any secret key because of the modification introduced in ${{\textbf {G}}}_1$, and (ii) in ${{\textbf {G}}}_3$, for any $\textsf {id}\in {{\mathcal {I}}}{{\mathcal {D}}}$, $sk_{\textsf {id}}$ has never been used or given to ${\mathcal {A}}$ until the identity $\textsf {id}$ is submitted to ${\mathcal {O}}_{\text {KGen}}$ or included in ${\mathcal {I}}$ as the selective opening query. Therefore, from ${\mathcal {A}}$’s point of view, ${{\textbf {G}}}_{4}$ and ${{\textbf {G}}}_{3}$ are identical, i.e.,

$$\begin{aligned} \Pr [{\mathcal {D}}({\textbf {G}} _{4})=1]-\Pr [{\mathcal {D}}({\textbf {G}} _{3})=1]=0. \end{aligned}$$

(13)

${{\textbf {Game}}\ {{\textbf {G}}}_{5}:}$ In this game, a new abort condition is added (as shown in Fig. 10). Specifically, if ${\mathcal {A}}_2$ or ${\mathcal {A}}_3$ submits a random-oracle query $r_{i,j}$ (resp., $(r_{i,j},c_{i,j})$) to ${\mathcal {O}}_{\text {G}}$ (resp., ${\mathcal {O}}_{\text {H}}$) satisfying that $(r_{i,j},\cdot )\notin L_G \wedge i\notin {\mathcal {I}}$ (resp., $((r_{i,j},c_{i,j}),\cdot )\notin L_H \wedge i\notin {\mathcal {I}}$), then AbortHASH is set true, which means that this game is aborted with output $\bot$. We present the following lemma with a postponed proof. $\square$

Lemma 4

$|\Pr [{\mathcal {D}}({\textbf {G}} _{5})=1]-\Pr [{\mathcal {D}}({\textbf {G}} _{4})=1]|\le nkq_r\cdot \textbf{Adv}_{\textsf {IBE} , {\widetilde{{\mathcal {A}}}}}^{\text {ow-id-cpa} }(\lambda )$ for some PPT adversary ${\widetilde{{\mathcal {A}}}}$.

Now, we construct a simulator ${\mathcal {S}}=({\mathcal {S}}_1,{\mathcal {S}}_2,{\mathcal {S}}_3)$, which simulates ${\textbf{G}}_5$ perfectly for ${\mathcal {A}}$, as shown in Fig. 11. Obviously,

$$\begin{aligned} {\textbf{G}}_{\textsf {FOIBE} , {\mathcal {S}},n}^{\text {rso} _k\text {-cca-ideal} }(\lambda )={{\textbf {G}}}_5. \end{aligned}$$

(14)

Fig. 11

Simulator ${\mathcal {S}}=({\mathcal {S}}_1,{\mathcal {S}}_2,{\mathcal {S}}_3)$ in the proof of Theorem 3

Hence, combining Eqs. (9)–(14) and Lemma 4, we obtain that

$$\begin{aligned}{} & {} \textbf{Adv}_{\textsf {FOIBE} , {\mathcal {A}},{\mathcal {S}},{\mathcal {D}},n}^{\text {rso} _{k}\text {-cca} }(\lambda )\\{} & {} \quad =|\Pr [{\mathcal {D}}({\textbf{G}}_{\textsf {FOIBE} , {\mathcal {A}},n}^{\text {rso} _k\text {-cca-real} }(\lambda ))=1]-\Pr [{\mathcal {D}}({\textbf{G}}_{\textsf {FOIBE} , {\mathcal {S}},n}^{\text {rso} _k\text {-cca-ideal} }(\lambda ))=1]|\\{} & {} \quad =|\Pr [{\mathcal {D}}({{\textbf {G}}}_0)=1]-\Pr [{\mathcal {D}}({{\textbf {G}}}_5)=1]|\\{} & {} \quad \le q_d\cdot 2^{-\gamma }+\frac{nkq_r}{|{\mathcal {R}}_{\textsf {FOEnc} }|-q_r} +nkq_r\cdot \textbf{Adv}_{\textsf {IBE} , {\widetilde{{\mathcal {A}}}}}^{\text {ow-id-cpa} }(\lambda ), \end{aligned}$$

for some adversary ${\widetilde{{\mathcal {A}}}}$.

We catch up with the proof of Lemma 4.

Proof of Lemma 4

We note that ${{\textbf {G}}}_{5}$ and ${{\textbf {G}}}_{4}$ proceed identically until event AbortHASH is set true. Thus, we have $|\Pr [{\mathcal {D}}({\textbf {G}} _{5})=1]-\Pr [{\mathcal {D}}({\textbf {G}} _{4})=1]|\le \Pr [\textsf {AbortHASH}]$.

So what remains is to compute $\Pr [\textsf {AbortHASH}]$.

Without loss of generality, we assume that for any tuple (r, c), before querying oracle ${\mathcal {O}}_{\text {H}}$ on (r, c), ${\mathcal {A}}$ will query ${\mathcal {O}}_{\text {G}}$ on r firstly. With this assumption, to answer ${\mathcal {A}}$’s decryption queries, the challenger does not need to “access to” ${\mathcal {O}}_{\text {G}}$, as shown in Fig. 12.

Now, we construct an OW-ID-CPA adversary ${\widetilde{{\mathcal {A}}}}$, attacking $\textsf {IBE}$, from ${\mathcal {A}}$ in Fig. 12. We introduce a special event Abort-Return (in Fig. 12), and require that when Abort-Return is set true, ${\widetilde{{\mathcal {A}}}}$ immediately terminate the simulation and returns the current ${\widetilde{m}}$ as its final output.

Fig. 12

Adversary ${\widetilde{{\mathcal {A}}}}=({\widetilde{{\mathcal {A}}}}_1,{\widetilde{{\mathcal {A}}}}_2)$ attacking $\textsf {IBE}$ in the proof of Lemma 4. Note that without loss of generality, we assume that for any tuple $(\textsf {id},r,c)$, before querying oracle ${\mathcal {O}}_{\text {H}}$ on (r, c), ${\mathcal {A}}$ will query ${\mathcal {O}}_{\text {G}}$ on r firstly

For any $i'\in [n]$, let $\textsf {AbortHASH}_{i'}$ denote the event that AbortHASH occurs for the first time for $i=i'$. Thus,

$$\begin{aligned} \Pr [\textsf {AbortHASH}]\le \sum _{i=1}^n\Pr [\textsf {AbortHASH}_i]. \end{aligned}$$

(15)

For any $j'\in [k]$, let $\textsf {AbortHASH}_{i,j'}$ denote the event that $\textsf {AbortHASH}_i$ occurs for the first time at ${\mathcal {A}}$’s random-oracle query $r_{i,j'}$ to ${\mathcal {O}}_{\text {G}}$ or random-oracle query $(r_{i,j'},c_{i,j'})$ to ${\mathcal {O}}_{\text {H}}$. Thus,

$$\begin{aligned} \Pr [\textsf {AbortHASH}_i]\le \sum _{j=1}^{k}\Pr [\textsf {AbortHASH}_{i,j}]. \end{aligned}$$

(16)

Furthermore, for any $\theta '\in [q_r]$, let $\textsf {AbortHASH}_{i,j}^{(\theta ')}$ denote the event that $\textsf {AbortHASH}_{i,j}$ occurs for the first time at ${\mathcal {A}}$’s ${\widetilde{\theta }}$-th random oracle query. Thus,

$$\begin{aligned} \Pr [\textsf {AbortHASH}_{i,j}]\le \sum _{\theta =1}^{q_r}\Pr [\textsf {AbortHASH}_{i,j}^{(\theta )}]. \end{aligned}$$

(17)

For ${\widetilde{i}}\leftarrow [n]$, ${\widetilde{j}}\leftarrow [k]$ and ${\widetilde{\theta }}\leftarrow [q_r]$, we claim that the probability that $\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}$ occurs in the game simulated by ${\widetilde{{\mathcal {A}}}}$ is equal to $\Pr [\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}]$ (i.e., the probability that $\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}$ occurs in ${{\textbf {G}}}_4$). The reason is as follows.

• (1) When ignoring the oracles ${\mathcal {O}}_{\text {G}}$, ${\mathcal {O}}_{\text {H}}$, ,${\mathcal {O}}_{\text {KGen}}$ and ${\mathcal {O}}_{\text {Dec}}$, the game simulated by ${\widetilde{{\mathcal {A}}}}$ is the same as ${{\textbf {G}}}_4$, except for the case that $\textsf {Abort-Return-I}$ occurs. Note that in the game simulated by ${\widetilde{{\mathcal {A}}}}$, ${\widetilde{{\mathcal {A}}}}$ will terminate the simulation with output ${\widetilde{m}}$ as long as $\textsf {Abort-Return-I}$ occurs. On the other hand, $\textsf {Abort-Return-I}$ occurs if and only if ${\widetilde{i}}\in {\mathcal {I}}$, which suggests that $\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}$ will not occur. So ${\widetilde{{\mathcal {A}}}}$ can terminate the simulation when $\textsf {Abort-Return-I}$ occurs without influencing the probability that $\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}$ occurs.

• (2) Both oracles ${\mathcal {O}}_{\text {KGen}}$ and ${\mathcal {O}}_{\text {Dec}}$ in the game simulated by ${\widetilde{{\mathcal {A}}}}$ are identical with that in ${{\textbf {G}}}_4$.

• (3) The only differences between the oracle ${\mathcal {O}}_{\text {G}}$ simulated by ${\widetilde{{\mathcal {A}}}}$ (denoted as ${\mathcal {O}}^{{\widetilde{{\mathcal {A}}}}}_{\text {G}}$) and the real ${\mathcal {O}}_{\text {G}}$ in ${{\textbf {G}}}_4$ are: (i) ${\widetilde{{\mathcal {A}}}}$ introduces $\textsf {Abort-Return-II}$ and aborts when $\textsf {Count}={\widetilde{\theta }}$, and (ii) for a query t satisfying $(t,\cdot )\notin L_G$, ${\widetilde{{\mathcal {A}}}}$ checks whether $t\in \{r_{i,j}\mid (i,j)\in ([n]\times [k])\setminus \{({\widetilde{i}},{\widetilde{j}})\}\}$ instead of checking whether $t\in \{r_{i,j}\mid i\in [n],j\in [k]\}$ in ${{\textbf {G}}}_4$.

  • (a) For (i), $\textsf {Abort-Return-II}$ is set true when $\textsf {Count}={\widetilde{\theta }}$, suggesting that ${\widetilde{{\mathcal {A}}}}$ terminates the simulation with output ${\widetilde{m}}$ immediately. Note that $\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}$ focuses on ${\mathcal {A}}$’s ${\widetilde{\theta }}$-th random oracle query. Whatever happens when $\textsf {Count}>{\widetilde{\theta }}$ will not affect $\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}$. So introducing $\textsf {Abort-Return-II}$ will not influence the probability that $\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}$ occurs.

  • (b) Now we analyze the case of (ii). For the $\theta$-th query t satisfying $(t,\cdot )\notin L_G$ and $\theta <{\widetilde{\theta }}$,² if $t\notin \{r_{i,j}\mid i\in [n],j\in [k]\}$ or $t\in \{r_{i,j}\mid (i,j)\in ([n]\times [k])\setminus \{({\widetilde{i}},{\widetilde{j}})\}\}$, obviously ${\mathcal {O}}^{{\widetilde{{\mathcal {A}}}}}_{\text {G}}$ and ${\mathcal {O}}_{\text {G}}$ both generate the response in the same way. On the other hand, if $t=r_{{\widetilde{i}},{\widetilde{j}}}$, then $\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}$ will not occur, because the $\theta$-th query $t=r_{{\widetilde{i}},{\widetilde{j}}}$ leads to AbortHASH, where $\theta <{\widetilde{\theta }}$, and ${\mathcal {A}}$ are assumed to not repeat identical queries to the same oracles. So no matter what ${\widetilde{{\mathcal {A}}}}$ returns as the response of ${\mathcal {O}}^{{\widetilde{{\mathcal {A}}}}}_{\text {G}}$, the response will not affect $\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}$.

  Hence, the differences between ${\mathcal {O}}^{{\widetilde{{\mathcal {A}}}}}_{\text {G}}$ (in the game simulated by ${\widetilde{{\mathcal {A}}}}$) and ${\mathcal {O}}_{\text {G}}$ (in ${{\textbf {G}}}_4$) does not influence the probability that $\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}$ occurs.

• (4) The only differences between the oracle ${\mathcal {O}}_{\text {H}}$ simulated by ${\widetilde{{\mathcal {A}}}}$ (denoted as ${\mathcal {O}}^{{\widetilde{{\mathcal {A}}}}}_{\text {H}}$) and the real ${\mathcal {O}}_{\text {H}}$ in ${{\textbf {G}}}_4$ are: (i) ${\widetilde{{\mathcal {A}}}}$ introduces $\textsf {Abort-Return-II}$ and aborts when $\textsf {Count}={\widetilde{\theta }}$, and (ii) for a query $(u_1,u_2)$ satisfying $((u_1,u_2),\cdot )\notin L_H$, ${\widetilde{{\mathcal {A}}}}$ checks whether $u_1\in \{r_{i,j}\mid (i,j)\in ([n]\times [k])\setminus \{({\widetilde{i}},{\widetilde{j}})\}\}$ instead of checking whether $u_1\in \{r_{i,j}\mid i\in [n],j\in [k]\}$ in ${{\textbf {G}}}_4$.

  • 1. For (i), $\textsf {Abort-Return-II}$ is set true when $\textsf {Count}={\widetilde{\theta }}$, suggesting that ${\widetilde{{\mathcal {A}}}}$ terminates the simulation with output ${\widetilde{m}}$ immediately. Note that $\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}$ focuses on ${\mathcal {A}}$’s ${\widetilde{\theta }}$-th random oracle query. Whatever happens when $\textsf {Count}>{\widetilde{\theta }}$ will not affect $\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}$. So introducing $\textsf {Abort-Return-II}$ will not influence the probability that $\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}$ occurs.

  • 2. Now we analyze the case of (ii). For the $\theta$-th query $(u_1,u_2)$ satisfying $((u_1,u_2),\cdot )\notin L_G$ and $\theta <{\widetilde{\theta }}$, if $u_1\notin \{r_{i,j}\mid i \in [n],j\in [k]\}$ or $u_1\in \{r_{i,j}\mid (i,j)\in ([n]\times [k])\setminus \{({\widetilde{i}},{\widetilde{j}})\}\}$, obviously ${\mathcal {O}}^{{\widetilde{{\mathcal {A}}}}}_{\text {H}}$ and ${\mathcal {O}}_{\text {H}}$ both generate the response in the same way. On the other hand, if $u_1=r_{{\widetilde{i}},{\widetilde{j}}}$, then there are two cases:

    • Case 1: $u_2\ne c_{{\widetilde{i}},{\widetilde{j}}}$. In this case, both ${\mathcal {O}}^{{\widetilde{{\mathcal {A}}}}}_{\text {H}}$ and ${\mathcal {O}}_{\text {H}}$ will generate the response in the same way: sampling $h_u\leftarrow {\mathcal {R}}_{\textsf {Enc} }$ and adding $((u_1,u_2),h_u)$ to $L_H$.

    • Case 2: $u_2= c_{{\widetilde{i}},{\widetilde{j}}}$. In this case, $\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}$ will not occur since the $\theta$-th query $(u_1,u_2)=(r_{{\widetilde{i}},{\widetilde{j}}},c_{{\widetilde{i}},{\widetilde{j}}})$ leads to AbortHASH, where $\theta <{\widetilde{\theta }}$, and ${\mathcal {A}}$ are assumed to not repeat identical queries to the same oracles. So no matter what ${\widetilde{{\mathcal {A}}}}$ returns as the response of ${\mathcal {O}}^{{\widetilde{{\mathcal {A}}}}}_{\text {H}}$, the response will not affect $\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}$.

    Hence, the differences between ${\mathcal {O}}^{{\widetilde{{\mathcal {A}}}}}_{\text {H}}$ (in the game simulated by ${\widetilde{{\mathcal {A}}}}$) and ${\mathcal {O}}_{\text {H}}$ (in ${{\textbf {G}}}_4$) does not influence the probability that $\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}$ occurs.

Note that ${\widetilde{{\mathcal {A}}}}$ succeeds if and only if $\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}$ occurs. Hence,

$$\begin{aligned} \textbf{Adv}_{\textsf {IBE} , {\widetilde{{\mathcal {A}}}}}^{\text {ow-id-cpa} }(\lambda )= & {} \Pr [\textsf {AbortHASH}_{{\widetilde{i}},{\widetilde{j}}}^{({\widetilde{\theta }})}]\\= & {} \frac{1}{n k q_r}\sum _{i=1}^n\sum _{j=1}^k\sum _{\theta =1}^{q_r}\Pr [\textsf {AbortHASH}_{i,j}^{(\theta )}]\\\ge & {} \frac{1}{n k q_r}\Pr [\textsf {AbortHASH}]. \end{aligned}$$

$\square$