Outsider-Anonymous Broadcast Encryption with Keyword Search: Generic Construction, CCA Security, and with Sublinear Ciphertexts

Keita EMURA, Kaisei KAJITA, Go OHTAKE

Summary :

As a multi-receiver variant of public key encryption with keyword search (PEKS), broadcast encryption with keyword search (BEKS) has been proposed (Attrapadung et al. at ASIACRYPT 2006/Chatterjee-Mukherjee at INDOCRYPT 2018). Unlike broadcast encryption, no receiver anonymity is considered because the test algorithm takes a set of receivers as input and thus a set of receivers needs to be contained in a ciphertext. In this paper, we propose a generic construction of BEKS from anonymous and weakly robust 3-level hierarchical identity-based encryption (HIBE). The proposed generic construction provides outsider anonymity, where an adversary is allowed to obtain secret keys of outsiders who do not belong to the challenge sets, and provides sublinear-size ciphertext in terms of the number of receivers. Moreover, the proposed construction considers security against chosen-ciphertext attack (CCA) where an adversary is allowed to access a test oracle in the searchable encryption context. The proposed generic construction can be seen as an extension to the Fazio-Perera generic construction of anonymous broadcast encryption (PKC 2012) from anonymous and weakly robust identity-based encryption (IBE) and the Boneh et al. generic construction of PEKS (EUROCRYPT 2004) from anonymous IBE. We run the Fazio-Perera construction employs on the first-level identity and run the Boneh et al. generic construction on the second-level identity, i.e., a keyword is regarded as a second-level identity. The third-level identity is used for providing CCA security by employing one-time signatures. We also introduce weak robustness in the HIBE setting, and demonstrate that the Abdalla et al. generic transformation (TCC 2010/JoC 2018) for providing weak robustness to IBE works for HIBE with an appropriate parameter setting. We also explicitly introduce attractive concrete instantiations of the proposed generic construction from pairings and lattices, respectively.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E107-A No.9 pp.1465-1477
• Publication Date: 2024/09/01
• Publicized: 2024/02/26
• Online ISSN: 1745-1337
• DOI: 10.1587/transfun.2023DMP0003
• Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
• Category: Cryptography and Information Security

1.  Introduction

Public key encryption with keyword search (PEKS) [1] is a searchable encryption in a public key setting. Let assume that a content and related keywords are encrypted and the ciphertexts are preserved on a cloud server. A receiver specifies a keyword \(kw\) to be searched, generates a trapdoor, and sends it to the cloud server. The cloud server runs the test algorithm and returns a ciphertext of a content containing \(kw\) to the receiver. As a multi-receiver variant of PEKS, Attrapadung et al. [2] introduced broadcast encryption with keyword search (BEKS) whose security is defined as a selective manner. Chatterjee and Mukherjee [3] proposed a BEKS scheme which is secure under the SXDH (Symmetric eXternal Diffie-Hellman) assumption and provides adaptive security. They also mentioned that the generic construction of Ambrona et al. [4] on [5] or on [6] also provide pairing-based BEKS constructions. Note that, in the BEKS syntax, the test algorithm takes a set of receivers in addition to a ciphertext and a trapdoor. Thus, a set of receivers needs to be contained in a ciphertext, and their BEKS constructions do not provide receiver anonymity, i.e., information about receivers is leaked¹. Other multi-receiver variants of PEKS have also been proposed [7]-[13] to reduce the communication cost compared to the case that a PEKS scheme is separately run for each receiver. Though they considered keyword privacy where no information about keyword is revealed from ciphertexts, they did not consider receiver anonymity. Receiver anonymity is recognized as an important security requirement for preserving privacy in the broadcast encryption context, and several attempts have been considered [14]-[19].

Liu et al. introduced broadcast authenticated encryption with keyword search (BAEKS) [20] as a multi-receiver variant of public key authenticated encryption with keyword search (PAEKS) [21]-[26] ² with receiver anonymity, and proposed a pairing-based BAEKS scheme (in the random oracle model) with linear-size ciphertext in terms of the number of receivers. The anonymity is defined as a restricted manner where the challenge sets \(S^\ast_0\) and \(S^\ast_1\) are fixed during the setup phase and an adversary is not allowed to obtain the secret key of a receiver, i.e., no corruption is allowed. Mukherjee [27] proposed a BAEKS scheme providing statistical consistency where the advantage is negligible for all computationally unbounded adversaries. The security model for anonymity is restricted as in the Liu et al. model where no corruption is allowed. Emura [28] proposed a generic construction of BAEKS that provides linear-size ciphertext in terms of the number of receivers, and provides full anonymity where an adversary is allowed to obtain the secret keys of the receivers belonging to \(S^\ast_0\cap S^\ast_1\). The building block is PAEKS providing ciphertext anonymity and consistency in a multi-receiver setting. The generic construction extends the Libert et al. generic construction of anonymous broadcast encryption [14]. The building block of the Libert et al. generic construction is (key-private and weakly robust) public key encryption (PKE) that allows us to employ PAEKS instead of the PKE. The linear-size ciphertext seems mandatory when full anonymity is required due to the analyses by Kiayias-Samari [18] and Kobayashi-Watanabe-Minematsu-Shikata [17]³.

The Fazio-Perera generic construction of anonymous broadcast encryption [15] provides outsider anonymity, where no information about a receiver is leaked from ciphertexts against outsiders, i.e., an adversary is allowed to obtain secret keys of outsiders who belong to neither \(S^\ast_0\) nor \(S^\ast_1\). At the expense of a weak anonymity level, the Fazio-Perera generic construction provides sublinear-size ciphertext using the subset cover framework [29]. In this paper, we mainly focus on the complete subtree (CS) method. Fazio and Perera mentioned that outsider anonymity seems a natural relaxation, since often the contents of the communication already reveal something about the recipient set. Since a main usage of PEKS is that the cloud server returns a ciphertext of a content containing a keyword to the receiver, outsider anonymous BAEKS with sublinear-size ciphertext is effective to reduce the communication cost. However, employing the Fazio-Perera generic construction to BAEKS is left as an open problem in [28] due to the following reason: the building block of the Fazio-Perera generic construction is (anonymous and weakly robust) identity-based encryption (IBE) that prevents to directly employ PAEKS because PAEKS is not ID-based and does not provide a secret key derivation algorithm. Since BEKS [2], [3] or multi-receiver variants of PEKS [7]-[13] did not consider receiver anonymity, proposing an outsider anonymous BEKS (or multi-receiver variants of PEKS) with sublinear-size ciphertext is an important and interesting topic.

1.1  Our Contribution

In this paper, we propose a generic construction of outsider anonymous BEKS from anonymous and weakly robust 3-level hierarchical identity-based encryption (HIBE) and one-time signatures. Informally, outsider anonymity in the BEKS context means that no information about receivers is revealed from ciphertexts when an adversary is allowed to obtain secret keys of outsiders who belong to neither \(S^\ast_0\) nor \(S^\ast_1\), and is allowed to obtain trapdoors of all receivers with the restriction that if the receivers belong to \(S^\ast_0\cup S^\ast_1\), then \(kw\not\in\{kw^\ast_0,kw^\ast_1\}\) where \(kw^\ast_0\) and \(kw^\ast_1\) are challenge keywords. Moreover, the proposed construction considers security against chosen-ciphertext attack (CCA) where an adversary is allowed to access a test oracle. The proposed generic construction provides sublinear-size ciphertext in terms of the number of receivers. Technically, our generic construction can be seen as an extension to the Fazio-Perera generic construction of anonymous broadcast encryption from anonymous and weakly robust IBE [15] and the Boneh et al. generic construction of PEKS from anonymous IBE [1], where we run the Fazio-Perera construction employs on the first-level identity and run the Boneh et al. generic construction on the second-level identity, i.e., a keyword is regarded as a second-level identity. The third level is used for the Canetti-Halevi-Katz (CHK) transformation [30] for providing CCA security. We also introduce weak robustness in the HIBE setting, and demonstrate that the Abdalla et al. generic transformation for providing weak robustness to IBE [31], [32] works for HIBE with an appropriate parameter setting.

Instantiations. We can employ any anonymous HIBE schemes, e.g., HIBE from parings [33]-[35], [41], [42] or from lattices [36], [43]-[45] with a suitable one-time signature scheme. We convert HIBEs to provide weak robustness via the generic construction [31], [32] which is explained in Sect. 3. We explicitly give attractive concrete instantiations of the proposed generic construction from pairings and lattices, respectively, and give comparisons in Table 1.

Table 1  Comparison among multi-receiver variants of PEKS. Auth. stands for Authenticity where a sender secret key is required for encryption as in PAEKS. Let \(U\) be the set of all receivers and \(S\subseteq U\) be a set of receivers specified in the encryption algorithm. We denote \(N=|U|\), \(|S|=N^\prime\leq N\), and \(R=|U|-|S|\). CT, ROM, and STD stand for ciphertext, random oracle model, and standard model, respectively. BDHSE, DLIN, BDHE, DDHI, MSE-DDH, DBDH, BDH, CODH, SXDH, LWE, and NCRHF stand for Bilinear Diffie-Hellman Summation Exponent, Decision LINear, Bilinear Diffie-Hellman Exponentiation, Decisional Diffie-Hellman Inverse, Multi-Sequence of Exponents Diffie-Hellman, Decisional Bilinear Diffie-Hellman, Bilinear Diffie-Hellman, Computational Oracle Diffie-Hellman, Symmetric eXternal Diffie-Hellman, Learning With Errors, and Near-Collision Resistant Hash Functions, respectively. CCA stands for chosen-ciphertext attack in the searchable encryption context where an adversary is allowed to access a test oracle. We omit complexity assumptions for one-time signatures.

• For pairing-based instantiations, we select the Ramanna-Sarkar (RS) HIBE scheme [33], the Langrehr-Pan (LP) HIBE scheme [34], and the Blazy-Kiltz-Pan (BKP) HIBE scheme [35] which are secure under the SXDH (Symmetric eXternal Diffie-Hellman) assumption⁴.

• For lattice-based instantiations, we select the Agrawal-Boneh-Boyen (ABB) HIBE scheme [36] though it provides selective security. By using the transformation given by Boneh and Boyen (BB) [37], it can be converted to provide adaptive security in the random oracle model (ROM) (See Theorem 7.2 in the ePrint version [46]) by the process of hashing the identity \({\sf ID}\) with ROM before using \({\sf ID}\). The BB transformation is briefly explained (in the case of IBE) as follows. In the initial phase, the simulator \({\mathcal B}\) picks \({\sf ID}^\ast_{\sf sel}\) as the challenge identity of the underlying selective secure IBE scheme. For the challenge identity \({\sf ID}^\ast_{\sf ada}\), \({\mathcal B}\) programs \({\sf ID}^\ast_{\sf sel}=H({\sf ID}^\ast_{\sf ada})\) where \(H\) is modeled as a random oracle. \({\mathcal B}\) guesses \({\sf ID}^\ast_{\sf ada}\) with the probability at least \(1/q_H\) where \(q_H\) is the number of random oracle queries. Because there are schemes that are secure in the ROM but insecure in the quantum random oracle model (QROM) [47], it would be better to show that the BB transformation works in the QROM setting. Unfortunately, this all-but-one programming does not work well in the QROM setting because a superposition of all the identities can be sent by a single query, and \({\mathcal B}\)’s guessing fails with overwhelming probability. Thus, though we do not deny the possibility to prove that the BB transformation works in the QROM setting, we state the underlying HIBE scheme as ABB+BB and require ROM in Table 1. We remark that Zhandry [48] proved that the ABB HIBE scheme is secure in the QROM but still it is selectively secure. For giving lattice-based instantiations in the standard model, we pay attention to the fact that the size of keyword space can be regarded as a polynomial of a security parameter or keywords have low entropy⁵, and selective security is sufficient for employing the CHK transformation. Thus, we can employ a 3-level HIBE scheme that satisfies adaptive security only for the first level and selective security for the other levels. Asano-Emura-Takayasu (AET) [39] introduced such 3-level HIBE schemes where the first level is either the Yamada IBE scheme [38] or the Jager-Kurek-Niehues (JKN) IBE scheme [40] which is adaptively secure, and other levels are selectively secure by appending a part of the selectively secure ABB IBE scheme. We can employ the Asano et al. HIBE schemes⁶. By employing state-of-the-art IBE schemes for the first level, we can construct BEKS schemes whose master public keys consist of only poly-log matrices in terms of the security parameter, as in [38], [40]. We state the underlying HIBE scheme as Y+AET or JKN+AET in Table 1. Though Cash et al. [44] proposed a lattice-based adaptively secure HIBE scheme in the standard model, the master public key size is proportional to the square of the security parameter. Moreover, though Singh et al. [49] proposed a lattice-based adaptively secure HIBE scheme in the standard model, the scheme achieves only bounded security in the sense that the size of a modulus \(q\) depends on the number of adversary’s key extraction queries. Thus, we do not employ the Cash et al. HIBE scheme and the Singh et al. HIBE scheme as candidates of instantiations.

For comparison, we instantiated the generic construction of BAEKS [28] from the Qin-Cui-Zheng-Zheng (QCZZ) PAEKS scheme [21] and the Mukherjee PAEKS scheme (i.e., the Mukherjee BAEKS scheme [27] with the single receiver setting) as specified in [28], as pairing-based BAEKS instantiations. We remark that no lattice-based instantiation was given because the Cheng-Meng lattice-based PAEKS scheme [22] was not proven to provide ciphertext anonymity⁷, and thus it was not stated as the building block. Though Yao et al. [26] proposed a lattice-based PAEKS scheme, they did not define consistency which is mandatory to instantiate the generic construction of BAEKS. Thus, we do not consider the Yao et al. scheme as a building block.

CPA Security. Though we focus on CCA security in this paper, BEKS providing outsider CPA anonymity, where no test oracle is defined, can be constructed generically from 2-level anonymous and weakly robust HIBE. Then, we can still employ the Asano et al. HIBE schemes by eliminating the third-level for lattice-based instantiations.

2.  Preliminaries

2.1  One-Time Signatures

An one-time signature scheme \({\sf OTS}\) consists of \(({\sf OTS.KeyGen},{\sf OTS.Sign},{\sf OTS.Verify})\). The key generation algorithm \({\sf OTS.KeyGen}\) takes a security parameter \(\lambda\) as input, and outputs a verification key and a signing key \(({\sf vk},{\sf sigk})\). The signing algorithm \({\sf OTS.Sign}\) takes \({\sf sigk}\) and a message \(M\in {\sf SigMspace}\) as input, where \({\sf SigMspace}\) is a signed message space, and outputs a signature \(\sigma\). The verification algorithm \({\sf OTS.Verify}\) takes \({\sf vk}\), \(\sigma\), and \(M\) as input, and outputs 0 or 1. We require the correctness holds where for any \(\lambda\), \(({\sf vk},{\sf sigk})\leftarrow{\sf OTS.KeyGen}(1^\lambda)\), and \(M\in{\sf SigMspace}\), \({\sf OTS.Verify}({\sf vk},{\sf OTS.Sign}({\sf sigk},M),M)=1\) holds. Moreover, we require the strong existential unforgeability against adaptive chosen message attack (sEUF-CMA) holds: Let \({\mathcal A}\) be probabilistic polynomial-time (PPT) adversaries. Here, \(({\sf vk},{\sf sigk})\leftarrow{\sf OTS.KeyGen}(1^\lambda)\), \((\sigma^\ast,M^\ast)\leftarrow{\mathcal A}^{{\sf OTS.Sign}(\cdot)}({\sf vk})\), and \({\mathcal A}\) is allowed to send a message \(M\) to the signing oracle \({\sf OTS.Sign}\) just once that returns \(\sigma\leftarrow{\sf OTS.Sign}({\sf sigk},M)\). We say that \({\sf OTS}\) is sEUF-CMA secure if the advantage \({\sf Adv}_{{\sf OTS},{\mathcal A}}^{\sf sEUF\text{-}CMA}(\lambda) :=\Pr[{\sf OTS.Verify}({\sf vk},\sigma^\ast,M^\ast)=1\wedge (\sigma^\ast,M^\ast)\neq (\sigma,M)]\) is negligible in the security parameter.

2.2  Anonymous 3-Level Hierarchical Identity-Based Encryption

Definition 1. [Syntax of 3-level HIBE]  An HIBE scheme \({\sf HIBE}\) consists of the following five algorithms \(({\sf HIBE.Setup}, {\sf HIBE.KeyGen}, {\sf HIBE.KeyDer}, {\sf HIBE.Enc}, {\sf HIBE.Dec})\) defined as follows. Here, \({\sf Mspace}\) is a message space and \({\sf IDspace}\) is an identity space. A hierarchical identity is denoted as \(({\sf ID},{\sf ID}^\prime,{\sf ID}^{\prime\prime})\in{\sf IDspace}\times{\sf IDspace}\times{\sf IDspace}\), and we consider the three-dimension identity only. In our purpose, it is sufficient that the \({\sf HIBE.KeyGen}\) algorithm generates a secret key for a first-level identity \({\sf ID}\) and the \({\sf IBE.Enc}\) algorithm takes a hierarchical identity \(({\sf ID},{\sf ID}^\prime,{\sf ID}^{\prime\prime})\) as input.

• \({\sf HIBE.Setup}\): The setup algorithm takes a security parameter \(\lambda\) as input, and outputs a master public key \({\sf MPK}\) and a master secret key \({\sf MSK}\).

• \({\sf HIBE.KeyGen}\): The key generation algorithm takes \({\sf MPK}\), \({\sf MSK}\), and \({\sf ID}\in{\sf IDspace}\) as input, and outputs a secret key \({\sf sk}_{\sf ID}\).

• \({\sf HIBE.KeyDer}\): For the second level key derivation, the key derivation algorithm takes \({\sf MPK}\), \({\sf sk}_{\sf ID}\), and \({\sf ID}^\prime\in{\sf IDspace}\) as input, and outputs a secret key \({\sf sk}_{{\sf ID},{\sf ID}^\prime}\). For the third level key derivation, the key derivation algorithm takes \({\sf MPK}\), \({\sf sk}_{{\sf ID},{\sf ID}^\prime}\), and \({\sf ID}^{\prime\prime}\in{\sf IDspace}\) as input, and outputs a secret key \({\sf sk}_{{\sf ID},{\sf ID}^\prime,{\sf ID}^{\prime\prime}}\).

• \({\sf HIBE.Enc}\): The encryption algorithm takes \({\sf MPK}\), \(({\sf ID},{\sf ID}^\prime,{\sf ID}^{\prime\prime})\in{\sf IDspace}\times{\sf IDspace}\times{\sf IDspace}\), and a plaintext \(M\in{\sf Mspace}\) as input, and outputs a ciphertext \({\sf ct_{HIBE}}\).

• \({\sf HIBE.Dec}\): The decryption algorithm takes \({\sf MPK}\), \({\sf ct_{HIBE}}\), and \({\sf sk}_{{\sf ID},{\sf ID}^\prime,{\sf ID}^{\prime\prime}}\) as input, and outputs \(M\) or \(\bot\).

Correctness. For any security parameter \(\lambda\), \(({\sf MPK},{\sf MSK})\leftarrow{\sf HIBE.Setup}(1^\lambda)\), \({\sf ID},{\sf ID}^\prime,{\sf ID}^{\prime\prime}\in{\sf IDspace}\), and \(M\in{\sf Mspace}\), \({\sf HIBE.Dec}({\sf MPK},{\sf ct_{HIBE}},{\sf sk}_{{\sf ID},{\sf ID}^\prime,{\sf ID}^{\prime\prime}})=M\) holds where \({\sf ct_{HIBE}}\leftarrow{\sf HIBE.Enc}({\sf MPK},({\sf ID},{\sf ID}^\prime,{\sf ID}^{\prime\prime}), M)\), \({\sf sk}_{\sf ID}\leftarrow{\sf HIBE.KeyGen}({\sf MPK},{\sf MSK},{\sf ID})\), \({\sf sk}_{{\sf ID},{\sf ID}^\prime}\) \(\leftarrow\) \({\sf HIBE.KeyDer}({\sf MPK}, {\sf MSK}, {\sf sk}_{\sf ID}, {\sf ID}^\prime)\), and \({\sf sk}_{{\sf ID},{\sf ID}^\prime,{\sf ID}^{\prime\prime}}\leftarrow{\sf HIBE.KeyDer}({\sf MPK},{\sf MSK}, {\sf sk}_{{\sf ID},{\sf ID}^\prime},{\sf ID}^{\prime\prime})\).

Anonymity. Briefly, anonymity means that no information about \(({\sf ID},{\sf ID}^\prime,{\sf ID}^{\prime\prime})\) is revealed from a ciphertext \({\sf ct_{HIBE}}\leftarrow{\sf HIBE.Enc}({\sf MPK},({\sf ID},{\sf ID}^\prime,{\sf ID}^{\prime\prime}),M)\). The formal definition is as follows. We employ a CPA notion here.

Definition 2 (Anonymity).  We define the following experiment.

\[\begin{gathered} \begin{split} {\sf Exp}&_{{\sf HIBE},{\mathcal A}}^{{\sf Anon\text{-}CPA}\text{-}b}(\lambda):\\ &({\sf MPK},{\sf MSK})\leftarrow {\sf HIBE.Setup}(1^\lambda)\\ &V_1:=\emptyset;~V_2:=\emptyset;~V_3:=\emptyset\\ &(({\sf ID}_0,{\sf ID}^\prime_0,{\sf ID}^{\prime\prime}_0),({\sf ID}_1,{\sf ID}^\prime_1,{\sf ID}^{\prime\prime}_1),M_0^\ast,M^\ast_1,{\sf st})\\ &~~~\leftarrow{\mathcal A}^{{\sf HIBE.KeyGen}({\sf MPK},{\sf MSK},\cdot)}({\sf MPK})\\ &~~~~\textit{s.t.}~{\sf ID}_0,{\sf ID}_1\not\in V_1\wedge ({\sf ID}_0,{\sf ID}^\prime_0), ({\sf ID}_1,{\sf ID}^\prime_1)\not\in V_2 \\ &~~~~\wedge ({\sf ID}_0,{\sf ID}^\prime_0,{\sf ID}^{\prime\prime}_0),({\sf ID}_1,{\sf ID}^\prime_1,{\sf ID}^{\prime\prime}_1)\not\in V_3\\ &~~~~\wedge M_0^\ast,M_1^\ast\in{\sf Mspace}\wedge |M_0^\ast|=|M_1^\ast|\\ &{\sf ct^\ast_{HIBE}}\leftarrow{\sf HIBE.Enc}({\sf MPK},({\sf ID}_b,{\sf ID}^\prime_b,{\sf ID}^{\prime\prime}_b),M^\ast_b)\\ &b^\prime\leftarrow{\mathcal A}^{{\sf HIBE.KeyGen}({\sf MPK},{\sf MSK},\cdot)}({\sf ct^\ast_{HIBE}},{\sf st})\\ &\textit{If}~b=b^\prime,~\textit{then output}~1,~\textit{and}~0~\textit{otherwise.} \end{split} \end{gathered}\]

The key extraction oracle \({\sf HIBE.KeyGen}\) for the first-level identity takes \({\sf ID}\in{\sf IDspace}\) as input, returns \({\sf sk}_{{\sf ID}}\leftarrow{\sf HIBE.KeyGen}({\sf MSK},{\sf ID})\), and updates \(V_1\leftarrow V_1\cup\{{\sf ID}\}\). The key extraction oracle \({\sf HIBE.KeyGen}\) for the two-dimensional hierarchical identities takes \(({\sf ID},{\sf ID}^\prime)\in{\sf IDspace}\times{\sf IDspace}\) as input, computes \({\sf sk}_{{\sf ID}}\leftarrow{\sf HIBE.KeyGen}({\sf MSK},{\sf ID})\), returns \({\sf sk}_{{\sf ID},{\sf ID}^\prime}\leftarrow{\sf HIBE.KeyDer}({\sf MSK},{\sf sk}_{\sf ID},{\sf ID}^\prime)\), and updates \(V_2\leftarrow V_2\cup\{({\sf ID},{\sf ID}^\prime)\}\). The key extraction oracle \({\sf HIBE.KeyGen}\) for the three-dimensional hierarchical identities takes \(({\sf ID},{\sf ID}^\prime,{\sf ID}^{\prime\prime})\in{\sf IDspace}\times{\sf IDspace}\times{\sf IDspace}\) as input, computes \({\sf sk}_{{\sf ID}}\leftarrow{\sf HIBE.KeyGen}({\sf MSK},{\sf ID})\), \({\sf sk}_{{\sf ID},{\sf ID}^\prime}\leftarrow{\sf HIBE.KeyDer}({\sf MSK},{\sf sk}_{\sf ID},{\sf ID}^\prime)\), returns \({\sf sk}_{{\sf ID},{\sf ID}^\prime,{\sf ID}^{\prime\prime}}\leftarrow{\sf HIBE.KeyDer}({\sf MSK},{\sf sk}_{{\sf ID},{\sf ID}^\prime},{\sf ID}^{\prime\prime})\), and updates \(V_3\leftarrow V_3\cup\{({\sf ID},{\sf ID}^\prime,{\sf ID}^{\prime\prime})\}\). In the post-challenge phase, the oracle returns \(\bot\) if any prefix of \(({\sf ID}_0,{\sf ID}^\prime_0,{\sf ID}^{\prime\prime}_0)\) or \(({\sf ID}_1,{\sf ID}^\prime_1,{\sf ID}^{\prime\prime}_1)\) is queried. We say that a HIBE scheme \({\sf HIBE}\) is Anon-CPA secure if the advantage \({\sf Adv}_{{\sf HIBE},{\mathcal A}}^{\sf Anon\text{-}CPA}(\lambda) :=|\Pr[{\sf Exp}_{{\sf HIBE},{\mathcal A}}^{{\sf Anon\text{-}CPA}\text{-}0}(\lambda)=1]-\Pr[{\sf Exp}_{{\sf HIBE},{\mathcal A}}^{{\sf Anon\text{-}CPA}\text{-}1}(\lambda)=1]|\) is negligible for all PPT adversaries \({\mathcal A}\) in the security parameter \(\lambda\).

2.3  Complete Subtree Method

We introduce the complete subtree (CS) method [29]. Let \({\sf BT}\) be a binary tree with \(N\) leaves. For a leaf node \(i\), let \({\sf Path}(i)\) be the set of nodes from the leaf to the root. Let \({\sf RSet}\) be the set of revoked leaves and \(R=|{\sf RSet}|\). For non leaf node \(x\), let \(x_{\sf left}\) be the left child of \(x\) and \(x_{\sf right}\) be the right child of \(x\).

1. Initialize \(X,{\sf cover}\leftarrow\emptyset\).

2. For all \(i\in {\sf RSet}\), add \({\sf Path}(i)\) to \(X\).

3. For all \(x\in X\), if \(x_{\sf left}\not\in X\) then add \(x_{\sf left}\) to \({\sf cover}\). If \(x_{\sf right}\not\in X\) then add \(x_{\sf right}\) to \({\sf cover}\).

4. If \(|{\sf Rset}|=0\) then add the root node \({\sf root}\) to \({\sf cover}\).

5. Output \({\sf cover}\).

We denote \({\sf cover}\leftarrow {\sf CompSubTree}({\sf BT},{\sf RSet})\). \(|{\sf cover}|\) is estimated as \(O(R\log(N/R))\)⁸.

2.4  Previous Generic Constructions

We briefly revisit previous generic constructions as follows.

The Abdalla et al. Generic Construction [52]. Abdalla et al. demonstrated that anonymous IBE implies PEKS. Briefly, a receiver runs \(({\sf MPK},{\sf MSK})\leftarrow {\sf IBE.Setup}(1^\lambda)\) and sets \({\sf MPK}\) as a public key and \({\sf MSK}\) as a secret key. To encrypt a keyword \(kw\), a random plaintext \(R\) is encrypted using a keyword \(kw\) as the identity such that \({\sf ct_{IBE}}\leftarrow{\sf IBE.Enc}({\sf MPK},kw,R)\) and \(({\sf ct_{IBE}},R)\) is a PEKS ciphertext. A trapdoor is a secret key \({\sf td}_{kw}\leftarrow{\sf IBE.KeyGen}({\sf MSK},kw)\). The test algorithm, that takes \(({\sf ct_{IBE}},R)\) and \({\sf td}_{kw}\) as input, outputs 1 if \(R={\sf IBE.Dec}({\sf MPK},{\sf ct_{IBE}},{\sf td}_{kw})\) and 0 otherwise. No information about \(kw\) is revealed from \(({\sf ct_{IBE}},R)\) if the underlying IBE scheme is anonymous. Moreover, if there exists \(kw^\prime\) where \(kw\neq kw^\prime\) and the test algorithm outputs 1 for \({\sf td}_{kw^\prime}\leftarrow{\sf IBE.KeyGen}({\sf MSK},kw^\prime)\) and \(({\sf ct_{IBE}},R)\) where \({\sf ct_{IBE}}\leftarrow{\sf IBE.Enc}({\sf MPK}, kw,R)\) (i.e., no consistency holds), then an algorithm can be constructed that breaks the IND-CPA security of the underlying IBE scheme. That is, the generic construction provides computational consistency.

The Boneh et al. Generic Construction [1]. The Boneh et al. generic construction is almost the same as the Abdalla et al. generic construction, except that \(R\) is fixed as \(0^\lambda\) where \(\lambda\in\mathbb{N}\) is a security parameter. \({\sf ct_{IBE}}\) can be directly regarded as a PEKS ciphertext that reduces the ciphertext size compared to that of the Abdalla et al. generic construction. Abdalla et al. [52] showed that there is an IBE scheme that is anonymous and provides IND-CPA security, but the PEKS scheme obtained via the Boneh et al. generic construction does not provide consistency. Abdalla et al. also demonstrated that the Boneh et al. generic construction provides consistency if the underlying anonymous IBE is weakly robust [31], [32]. Briefly, robustness means that the decryption algorithm outputs \(\bot\) if the corresponding decryption key is not used (See Sect. 3 for details). Abdalla et al. also mentioned that if the underlying IBE scheme is CCA secure in addition to provide weak robustness, then the PEKS scheme converted via the Boneh et al. generic construction is also CCA secure where an adversary is allowed to issue a test query.

The Fazio-Perera Generic Construction [15]. Fazio and Perera proposed a generic construction of anonymous broadcast encryption from anonymous IBE. Because the decryption algorithm does not take the set of receivers \(S\) as input, the underlying anonymous IBE scheme is required to be weakly robust. Let \(U\) be the set of all receivers and \(S\subseteq U\) be a set of receivers specified in the encryption algorithm. We denote \(N=|U|\), \(R=|U|-|S|\), and \(L=\lfloor R\log(N/R) \rfloor\). Moreover, let \(\ell=|{\sf cover}|\) where \({\sf cover}=\{x_1,\ldots,x_\ell\}\) is the set of nodes determined by the CS method. A ciphertext is a set of IBE ciphertexts: \({{\sf ct}_{{\sf IBE},j}}\leftarrow{\sf IBE.Enc}({\sf MPK},x_j,M)\) for \(j=1,2,\ldots,\ell\), and \({{\sf ct}_{{\sf IBE},j}}\leftarrow{\sf IBE.Enc}({\sf MPK},{\sf dummy},\tilde{M})\) for \(j=\ell+1,\ldots,L\) where \(\tilde{M}\xleftarrow{＄}\{0,1\}^{|M|}\) and \({\sf dummy}\) is a dummy identity. The order of ciphertexts is randomized via a random permutation. A receiver decrypts the ciphertext to find an IBE ciphertext whose decryption result is non-\(\bot\). Due to the robustness of the underlying IBE scheme, a receiver can find such a ciphertext if the receiver belongs to the set \(S\) specified in the encryption algorithm. Due to the anonymity of the underlying IBE scheme, no information about identity is revealed from ciphertext in the sense of outsider anonymity. For providing CCA security, CCA secure anonymous IBE and one-time signatures are employed. A verification key \({\sf vk}\) is contained such that \({{\sf ct}_{{\sf IBE},j}}\leftarrow{\sf IBE.Enc}({\sf MPK},x_j,M||{\sf vk})\) for \(j=1,2,\ldots,\ell\), and \({{\sf ct}_{{\sf IBE},j}}\leftarrow{\sf IBE.Enc}({\sf MPK},{\sf dummy},\tilde{M})\) for \(j=\ell+1,\ldots,L\) where \(\tilde{M}\xleftarrow{＄}\{0,1\}^{|M|+|{\sf vk}|}\). A signature \(\sigma\) is generated on \({\sf vk}||\{{{\sf ct}_{{\sf IBE},j}}\}_{j\in[1,L]}\) and \((\sigma,{\sf vk},\{{{\sf ct}_{{\sf IBE},j}}\}_{j\in[1,L]})\) is a ciphertext.

3.  On Weak Robustness in the HIBE Setting

Briefly, robustness (in the HIBE setting) means that the \({\sf HIBE.Dec}\) algorithm that takes \({\sf ct_{HIBE}}\) and \({\sf sk}_{{\sf ID}_1,{\sf ID}^\prime_1,{\sf ID}^{\prime\prime}_1}\) outputs an error symbol \(\bot\) where \({\sf ct_{HIBE}}\leftarrow{\sf HIBE.Enc}({\sf MPK},({\sf ID}_0,{\sf ID}^\prime_0, {\sf ID}^{\prime\prime}_0),M)\), \({\sf sk}_{{\sf ID}_1}\leftarrow{\sf HIBE.KeyGen}({\sf MPK},{\sf MSK},{\sf ID}_1)\), \({\sf sk}_{{\sf ID}_1,{\sf ID}^\prime_1}\leftarrow{\sf HIBE.KeyDer}({\sf MPK},{\sf sk}_{{\sf ID}_1},{\sf ID}^\prime_1)\), \({\sf sk}_{{\sf ID}_1,{\sf ID}^\prime_1,{\sf ID}^{\prime\prime}_1}\leftarrow{\sf HIBE.KeyDer}({\sf MPK},{\sf sk}_{{\sf ID}_1,{\sf ID}^\prime_1},{\sf ID}^{\prime\prime}_1)\), and \(({\sf ID}_0,{\sf ID}^\prime_0,{\sf ID}^{\prime\prime}_0)\neq({\sf ID}_1,{\sf ID}^\prime_1, {\sf ID}^{\prime\prime}_1)\). Weak robustness here means that the robustness holds for honestly generated ciphertexts. The formal definition is as follows.

Definition 3 (Weak Robustness).  We define the following experiment.

\[\begin{gathered} \begin{split} {\sf Exp}&_{{\sf HIBE},{\mathcal A}}^{\sf wrob}(\lambda):\\ &({\sf MPK},{\sf MSK})\leftarrow {\sf HIBE.Setup}(1^\lambda)\\ &V:=\emptyset\\ &(({\sf ID}_0,{\sf ID}^\prime_0,{\sf ID}^{\prime\prime}_0),({\sf ID}_1,{\sf ID}^\prime_1,{\sf ID}^{\prime\prime}_1),M^\ast)\\ &~~~\leftarrow{\mathcal A}^{{\sf HIBE.KeyGen}({\sf MPK},{\sf MSK},\cdot)}({\sf MPK})\\ &~~~~\textit{s.t.}~{\sf ID}_0,{\sf ID}_1\not\in V\wedge ({\sf ID}_0,{\sf ID}^\prime_0,{\sf ID}^{\prime\prime}_0)\neq({\sf ID}_1,{\sf ID}^\prime_1,{\sf ID}^{\prime\prime}_1)\\ &~~~~\wedge M^\ast\in{\sf Mspace}\wedge M^\ast\neq \bot\\ &{\sf ct_{HIBE}}\leftarrow{\sf HIBE.Enc}({\sf MPK},({\sf ID}_0,{\sf ID}^\prime_0,{\sf ID}^{\prime\prime}_0),M^\ast)\\ &{\sf sk}_{{\sf ID}_1}\leftarrow{\sf HIBE.KeyGen}({\sf MPK},{\sf MSK},{\sf ID}_1)\\ &{\sf sk}_{{\sf ID}_1,{\sf ID}^\prime_1}\leftarrow{\sf HIBE.KeyGen}({\sf MPK},{\sf sk}_{{\sf ID}_1},{\sf ID}^\prime_1)\\ &{\sf sk}_{{\sf ID}_1,{\sf ID}^\prime_1,{\sf ID}^{\prime\prime}_1}\leftarrow{\sf HIBE.KeyGen}({\sf MPK},{\sf sk}_{{\sf ID}_1,{\sf ID}^\prime_1},{\sf ID}^{\prime\prime}_1)\\ &\textit{If}~{\sf HIBE.Dec}({\sf MPK},{\sf ct_{HIBE}},{\sf sk}_{{\sf ID}_1,{\sf ID}^\prime_1,{\sf ID}^{\prime\prime}_1})\neq\bot,\\ &\textit{then output}~1,~\textit{and}~0~\textit{otherwise.} \end{split} \end{gathered}\]

The key extraction oracle \({\sf HIBE.KeyGen}\) takes \({\sf ID}\in{\sf IDspace}\) as input, returns \({\sf sk}_{{\sf ID}}\leftarrow{\sf HIBE.KeyGen}({\sf MPK},{\sf MSK},{\sf ID})\), and updates \(V\leftarrow V\cup\{{\sf ID}\}\). We say that a HIBE scheme \({\sf HIBE}\) is weakly robust if the advantage \({\sf Adv}_{{\sf HIBE},{\mathcal A}}^{\sf wrob}(\lambda) :=\Pr[{\sf Exp}_{{\sf HIBE},{\mathcal A}}^{\sf wrob}(\lambda)=1]\) is negligible for all PPT adversaries \({\mathcal A}\) in the security parameter \(\lambda\).

The above definition follows that of Abdalla et al. that contains the key extraction oracle. We mention that the security of our generic construction holds even if the underlying HIBE scheme is weakly robust without the key extraction oracle.

Next, we demonstrate that the Abdalla et al. transformation [31], [32] works even for 3-level HIBE. Let \({\sf IDspace}=\{0,1\}^\lambda\) (basically, we assume that \(\lambda=128\) to provide 128-bit security level). For IBE⁹, weak robustness can be easily obtained such that a random value \(K\in\{0,1\}^{6\lambda}\) is chosen and is contained in \({\sf MPK}\). For encryption of a plaintext \(M\), \(M||K\) is encrypted. The decryption algorithm outputs \(\bot\) if \(K\) is not recovered, and \(M\) otherwise. Abdalla et al. required that \(K\) needs to be sufficiently larger than the identities because \({\sf Adv}_{{\sf IBE},{\mathcal A}}^{\sf wrob}(\lambda)\leq {\sf Adv}_{{\sf IBE},{\mathcal B}}^{\sf Anon\text{-}CPA}(\lambda)+2^{2|{\sf ID}|+\lceil \log_2(t) \rceil-|K|}\) holds (Theorem 4.1 in [31]), where \({\mathcal B}\) is an adversary for Anon-CPA security and \(t\) is the running time of an adversary of weak robustness \({\mathcal A}\). Abdalla et al. demonstrated a concrete example: assume \(|{\sf ID}|=256\) and \(t\leq 2^{128}\), then \(|K|=768\) provides \(2^{2|{\sf ID}|+\lceil \log_2(t) \rceil-|K|}=2^{-128}\). Thus, we set \(|K|=6\lambda\) here.

We revisited the reason behind that \(K\) needs to be sufficiently larger than the identities. The reason is that an adversary (of weak robustness of IBE) can encode the key \(K\) into the identities \({\sf ID}_0\) and \({\sf ID}_1\). Then, there is an counterexample that the transformation fails to provide weak robustness. In the 3-level HIBE setting, an adversary can encode the key \(K\) into the hierarchical identities \(({\sf ID}_0,{\sf ID}^\prime_0,{\sf ID}^{\prime\prime}_0)\) and \(({\sf ID}_1,{\sf ID}^\prime_1,{\sf ID}^{\prime\prime}_1)\). Thus, the transformation still works when we set \(|K|=13\lambda\). The parameter selection is relatively conservative in the searchable encryption context. For example, if we assume that the size of keyword space is relatively small, then the identity-space of the second-level identities could be small, e.g., if we set \(|{\sf KWspace}|=2^{18}\) and \(\lambda=128\), then, \(|{\sf KWspace}|\approx \lambda/7\) and \(|K|\) could be estimated as \((4+2/7+4+1+1)\lambda\approx 10.3\lambda\)¹⁰. We note that \(|K|\) could be estimated as \(6.3\lambda\) in the 2-level HIBE setting which is sufficient to construct BEKS with outsider CPA anonymity where no test oracle is defined.

4.  Definition of BEKS

In this section, we introduce the definition of BEKS. We modify the definition of BAEKS [28]. Let \(N\) be the maximum number of receivers and \(U=\{i\}_{i\in[1,N]}\) be the set of all receivers’ indexes.

Definition 4 (Syntax of BEKS).   A BEKS scheme \({\sf BEKS}\) consists of the following four algorithms \(({\sf BEKS.Setup}\), \({\sf BEKS.Enc}\), \({\sf BEKS.Trapdoor}\), \({\sf BEKS.Test})\) defined as follows. Here, \({\sf KWspace}\) is a keyword space.

• \({\sf BEKS.Setup}\): The setup algorithm takes a security parameter \(\lambda\) and the maximum number of receivers \(N\) as input, and outputs a master public key \({\sf MPK}\) and secret keys \(\{{\sf sk}_{{\sf R}[i]}\}_{i\in[1,N]}\). Here, \({\sf R}\) stands for receiver and \({\sf sk}_{{\sf R}[i]}\) is a secret key of the \(i\)-th receiver.

• \({\sf BEKS.Enc}\): The keyword encryption algorithm takes \({\sf MPK}\), a set of receivers \(S\subseteq U\) where \(|S|=N^\prime\leq N\), and a keyword \(kw\in {\sf KWspace}\) as input, and outputs a ciphertext \({\sf ct_{BEKS}}\).

• \({\sf BEKS.Trapdoor}\): The trapdoor algorithm takes \({\sf MPK}\), \({\sf sk_{R}}\), and a keyword \(kw^\prime\in {\sf KWspace}\) as input, and outputs a trapdoor \({\sf td}_{{\sf R},kw^\prime}\).

• \({\sf BEKS.Test}\): The test algorithm takes \({\sf MPK}\), \({\sf ct_{BEKS}}\) and \({\sf td}_{{\sf R},kw^\prime}\) as input, and outputs 1 or 0.

Correctness. For any security parameter \(\lambda\) and \(({\sf MPK},\{{\sf sk}_{{\sf R}[i]}\}_{i\in[1,N]})\leftarrow{\sf BEKS.Setup}(1^\lambda,N)\), \({\sf BEKS.Test}({\sf MPK}, {\sf ct_{BEKS}}, {\sf td}_{{\sf R},kw})=1\) holds where \({\sf ct_{BEKS}}\leftarrow{\sf BEKS.Enc}({\sf MPK},S,kw)\), \({\sf td}_{{\sf R},kw}\leftarrow{\sf BEKS.Trapdoor}({\sf MPK}, {\sf sk}_{{\sf R}[i]},kw)\), \(kw\in {\sf KWspace}\), and \(i\in S\subseteq U\).

Consistency. We define consistency that basically requires that for any security parameter \(\lambda\) and \(({\sf MPK},\{{\sf sk}_{{\sf R}[i]}\}_{i\in[1,N]})\leftarrow{\sf BEKS.Setup}(1^\lambda,N)\), \({\sf BEKS.Test}({\sf MPK},{\sf ct_{BEKS}},{\sf td}_{{\sf R},kw^\prime})=0\) holds where \({\sf ct_{BEKS}}\leftarrow{\sf BEKS.Enc}({\sf MPK},S,kw)\), \({\sf td}_{{\sf R},kw^\prime}\leftarrow{\sf BEKS.Trapdoor}({\sf MPK},{\sf sk}_{{\sf R}[i]},kw^\prime)\), and either \(kw\neq kw^\prime\) or \(i\not\in S\). We introduce computational consistency because the transformation for providing weak robustness [31], [32] assumes that the underlying IBE scheme is anonymous and IND-CPA secure.

Definition 5 (Computational Consistency).  We define the following experiment.

\[\begin{gathered} \begin{split} {\sf Exp}&_{{\sf BEKS},{\mathcal A}}^{\sf consist}(\lambda,N):\\ &({\sf MPK},\{{\sf sk}_{{\sf R}[i]}\}_{i\in[1,N]})\leftarrow {\sf BEKS.Setup}(1^\lambda,N)\\ &(kw,kw^\prime,S^\ast,i^\ast)\leftarrow{\mathcal A}({\sf MPK})\\ &~~~\textit{s.t.}~S^\ast\subseteq U\wedge i^\ast\in[1,N]\wedge kw,kw^\prime\in{\sf KWspace}\\ &~~~\wedge (kw\neq kw^\prime \vee i^\ast\not\in S^\ast)\\ &{\sf ct_{BEKS}}\leftarrow{\sf BEKS.Enc}({\sf MPK},S^\ast,kw)\\ &{\sf td}_{{\sf R},kw^\prime}\leftarrow{\sf BEKS.Trapdoor}({\sf MPK},{\sf sk}_{{\sf R}[i^\ast]},kw^\prime)\\ &\textit{If}~{\sf BEKS.Test}({\sf MPK},{\sf ct_{BEKS}},{\sf td}_{{\sf R},kw^\prime})=1,\\ &\textit{then output}~1,~\textit{and}~0~\textit{otherwise.} \end{split} \end{gathered}\]

We say that a BEKS scheme \({\sf BEKS}\) is computationally consistent if the advantage \({\sf Adv}_{{\sf BEKS},{\mathcal A}}^{\sf consist}(\lambda,N) :=\Pr[{\sf Exp}_{{\sf BEKS},{\mathcal A}}^{\sf consist}(\lambda,N)=1]\) is negligible for all PPT adversaries \({\mathcal A}\) in the security parameter \(\lambda\).

Next, we introduce outsider anonymity, where an adversary \({\mathcal A}\) is allowed to obtain secret keys of outsiders who belong to neither \(S^\ast_0\) nor \(S^\ast_1\) via the corruption oracle, and is allowed to obtain trapdoors of all receivers via the trapdoor oracle with the restriction that if the receivers belong to \(S^\ast_0\cup S^\ast_1\), then \(kw\not\in\{kw^\ast_0,kw^\ast_1\}\) where \(kw^\ast_0\) and \(kw^\ast_1\) are challenge keywords. We consider CCA security here where \({\mathcal A}\) is allowed to issue test queries \((i,kw,{\sf ct_{BEKS}})\). If \(i\in S^\ast_0\cup S^\ast_1\) and \({\sf ct_{BEKS}}={\sf ct}^\ast_{\sf BEKS}\), then \(kw\not\in\{kw^\ast_0,kw^\ast_1\}\) is required. If \(S^\ast_0=S^\ast_1\), then the definition is the same as that of IND-CCA security. Thus, outsider CCA anonymity implies IND-CCA security.

Definition 6 (Outsider Anonymity).  We define the following experiment.

\[\begin{gathered} \begin{split} &{\sf Exp}_{{\sf BEKS},{\mathcal A}}^{{\sf outsider\text{-}anon}\text{-}b}(\lambda,N):\\ &~({\sf MPK},\{{\sf sk}_{{\sf R}[i]}\}_{i\in[1,N]})\leftarrow {\sf BEKS.Setup}(1^\lambda,N)\\ &~V:=\emptyset;~V^\prime:=\emptyset\\ &~(kw_0^\ast,kw_1^\ast,S_0^\ast,S_1^\ast,{\sf st})\\ &~~~\leftarrow{\mathcal A}^{{\sf BEKS.Trapdoor}(\cdot,\cdot),{\sf Corrupt}(\cdot),{\sf BEKS.Test}(\cdot,\cdot,\cdot)}({\sf MPK})\\ &~~~~\textit{s.t.}~S_0^\ast, S_1^\ast\subseteq U\wedge |S_0^\ast|=|S_1^\ast| \wedge V\cap (S^\ast_0\cup S^\ast_1)=\emptyset\\ &~~~~\wedge kw_0^\ast,kw_1^\ast\in{\sf KWspace}\\ &~~~~\wedge\forall(i,kw)\in V^\prime,\\ &~~~~~~~~~~(i\not\in S^\ast_0\cup S^\ast_1\wedge kw\in{\sf KWspace})\\ &~~~~~~~\vee(i\in S^\ast_0\cup S^\ast_1\wedge kw\in{\sf KWspace}\setminus\{kw_0^\ast,kw_1^\ast\})\\ &~{\sf ct}^\ast_{\sf BEKS}\leftarrow{\sf BEKS.Enc}({\sf MPK},S_b^\ast,kw^\ast_b)\\ &~b^\prime\leftarrow{\mathcal A}^{{\sf BEKS.Trapdoor}(\cdot,\cdot),{\sf Corrupt}(\cdot),{\sf BEKS.Test}(\cdot,\cdot,\cdot)}({\sf ct}^\ast_{\sf BEKS},{\sf st})\\ &~\textit{If}~b=b^\prime,~\textit{then output}~1,~\textit{and}~0~\textit{otherwise.} \end{split} \end{gathered}\]

Here, the trapdoor oracle \({\sf BEKS.Trapdoor}\) takes \(i\in [1,N]\) and \(kw\in{\sf KWspace}\), returns the trapdoor generated as \({\sf td}_{{\sf R},kw}\leftarrow{\sf BEKS.Trapdoor}({\sf MPK},{\sf sk}_{{\sf R}[i]}, kw)\), and updates \(V^\prime:=V^\prime\cup\{(i,kw)\}\). In the post-challenge phase, the oracle returns \(\bot\) if \(i\in S^\ast_0\cup S^\ast_1\) and \(kw\in\{kw_0^\ast,kw_1^\ast\}\). The corruption oracle \({\sf Corrupt}\) takes \(i\in[1,N]\) as input, returns \({\sf sk}_{{\sf R}[i]}\), and updates \(V\leftarrow V\cup\{i\}\). In the post-challenge phase, the oracle returns \(\bot\) if \(i\in S^\ast_0\cup S^\ast_1\). The test oracle \({\sf BEKS.Test}\) takes \((i,kw,{\sf ct_{BEKS}})\) as input where \(i\in[1,N]\) and \(kw\in{\sf KWspace}\), computes \({\sf td}_{{\sf R},kw}\leftarrow{\sf BEKS.Trapdoor}({\sf MPK},{\sf sk}_{{\sf R}[i]}, kw)\), and returns the result of \({\sf BEKS.Test}({\sf MPK}, {\sf ct_{BEKS}}, {\sf td}_{{\sf R},kw})\). The oracle returns \(\bot\) if \(i\in S^\ast_0\cup S^\ast_1\), \(kw\in\{kw^\ast_0,kw^\ast_1\}\), and \({\sf ct_{BEKS}}={\sf ct}^\ast_{\sf BEKS}\). We say that a BEKS scheme \({\sf BEKS}\) is outsider anonymous if the advantage \({\sf Adv}_{{\sf BEKS},{\mathcal A}}^{\sf outsider\text{-}anon}(\lambda,N) :=|\Pr[{\sf Exp}_{{\sf BEKS},{\mathcal A}}^{{\sf outsider\text{-}anon}\text{-}0}(\lambda,N)=1]-\Pr[{\sf Exp}_{{\sf BEKS},{\mathcal A}}^{{\sf outsider\text{-}anon}\text{-}1}(\lambda,N)=1]|\) is negligible for all PPT adversaries \({\mathcal A}\) in the security parameter \(\lambda\).

5.  Proposed Generic Construction

In this section, we give the proposed generic construction of \({\sf BEKS}\) from 3-level anonymous and weakly robust \({\sf HIBE}\). Let \(U\) be the set of all receivers and \(S\subseteq U\) be a set of receivers specified in the encryption algorithm. We denote \(N=|U|\), \(R=|U|-|S|\), and \(L=\lfloor R\log(N/R) \rfloor\). Moreover, let \(\ell=|{\sf cover}|\) where \({\sf cover}=\{x_1,\ldots,x_\ell\}\) is the set of nodes determined by the CS method, and \({\sf BT}\) be a binary tree with \(N\) leaves (i.e., assume that \(N\) is represented as \(2^n\) for some \(n\in\mathbb{N}\)). Let \({\sf dummy}\) and \({\sf dummy}^\prime\) be dummy identities.

If we directly employ the Abdalla et al. generic construction [52], then a random plaintext \(R\) is contained in a BEKS ciphertext and it increases the ciphertext size. Here, we pay attention to the fact that the Fazio-Perera generic construction of anonymous broadcast encryption [15] requires that the underlying IBE scheme is weakly robust. Thus, we employ the Boneh et al. generic construction of PEKS [1] here that reduces the ciphertext size.

5.1  A Trivial Construction from IBE and Its Limitation

Before giving the proposed construction, we consider to directly employ the Boneh et al. generic construction of PEKS and discuss its limitation. For the sake of simplicity, we consider CPA security here where no test oracle is defined. Let \({\sf IBE}=({\sf IBE.Setup}, {\sf IBE.KeyGen}, {\sf IBE.Enc}, {\sf IBE.Dec})\) be an IBE scheme. In the Boneh et al. construction, a receiver runs \(({\sf MPK},{\sf MSK})\leftarrow{\sf IBE.Setup}(1^\lambda)\) and \({\sf MSK}\) is used for generating a trapdoor by spesifying a keyword as the identity. Thus, a direct construction is described as follows. The \({\sf BEKS.Setup}\) algorithm runs \(({\sf MPK}_j,{\sf MSK}_j)\leftarrow{\sf IBE.Setup}(1^\lambda)\) for \(j=1,\ldots,N\), and outputs \({\sf MPK}=\{{\sf MPK}_j\}_{j\in[1,N]}\) and \(\{{\sf sk}_{{\sf R}[j]}={\sf MSK}_j\}_{j\in[1,N]}\). The \({\sf BEKS.Enc}\) algorithm, that takes \(S\subseteq U\) where \(|S|=N^\prime\), specifies \({\sf RSet}:=U\setminus S\) and runs \({\sf cover}\leftarrow {\sf CompSubTree}({\sf BT},{\sf RSet})\) where \({\sf cover}=\{x_1,\ldots,x_\ell\}\). Then, the algorithm runs \({{\sf ct}_{{\sf IBE},j}}\leftarrow{\sf IBE.Enc}({\sf MPK}_j,x_j||kw,0^\lambda)\) for \(j=1,2,\ldots,\ell\), runs \({{\sf ct}_{{\sf IBE},j}}\leftarrow{\sf IBE.Enc}({\sf MPK}_j,{\sf dummy},\tilde{M})\) for \(j=\ell+1,\ldots,L\) where \(\tilde{M}\xleftarrow{＄}\{0,1\}^\lambda\), and outputs \({\sf ct_{BEKS}}=\{{{\sf ct}_{{\sf IBE},\pi(j)}}\}_{j\in[1,L]}\) where \(\pi:\{1,\ldots,L\}\rightarrow \{1,\ldots,L\}\) is a random permutation. The \({\sf BEKS.Trapdoor}\) algorithm runs \({\sf sk}_{k}\leftarrow{\sf IBE.KeyGen}({\sf MSK}_i,x^\prime_k||kw^\prime)\) for \(k=1,\ldots,h\) where the receiver \(i\) is assigned to the leaf node \(i\) and \({\sf Path}(i)=\{x^\prime_1,\ldots,x^\prime_h\}\). Output \({\sf td}_{{\sf R},kw^\prime}=(i,\{{\sf sk}_k\}_{k\in[1,h]})\). Then, the \({\sf BEKS.Test}\) algorithm, that takes \({\sf MPK}=\{{\sf MPK}_j\}_{j\in[1,N]}\), \({\sf ct_{BEKS}}=\{{{\sf ct}_{{\sf IBE},j}}\}_{j\in[1,L]}\), and \({\sf td}_{{\sf R},kw^\prime}=(i,\{{\sf sk}_k\}_{k\in[1,h]})\), runs:

• For \(k=1\) to \(h\) 

  • For \(j=1\) to \(L\) 

    • ＊  Run \(M\leftarrow {\sf IBE.Dec}({\sf MPK}_i,{{\sf ct}_{{\sf IBE},j}},{\sf sk}_k)\).

    • ＊  If \(M=0^\lambda\), then return 1. Otherwise, if \(j=L\), break the loop. Otherwise, \(j\leftarrow j+1\).

  • If \(k=h\), return \(0\). Otherwise, \(k\leftarrow k+1\).

If \(i\in S\), then \({\sf cover}\cap {\sf Path}(i)\neq \emptyset\) due to the CS method. Let \(x_j\in {\sf cover}\cap {\sf Path}(i)\). If \(kw=kw^\prime\), then for \({\sf ct_{BEKS}}\ni{\sf ct_{IBE}}\leftarrow{\sf IBE.Enc}({\sf MPK}_i,x_j||kw,0^\lambda)\) and \({\sf td}_{{\sf R},kw^\prime}\ni\{{\sf sk}_k\}_{k\in[1,h]}\ni {\sf sk}\leftarrow{\sf IBE.KeyGen}({\sf sk}_{{\sf R}[i]},x_j||kw^\prime)\), \(0^\lambda\leftarrow {\sf IBE.Dec}({\sf MPK}_i, {\sf ct_{IBE}},{\sf sk})\) holds. Thus, correctness directly holds due to the correctness of the underlying IBE scheme. Since the construction is almost the same as the Fazio-Perera construction, except that a keyword is appended to each node, the construction provides outsider anonymity. Moreover, due to the anonymity of the underlying IBE scheme, no information about keyword is revealed. However, to provide consistency, this construction requires the following robustness: for \({\sf ct_{IBE}}\leftarrow{\sf IBE.Enc}({\sf MPK}_i,{\sf ID},M)\) and \({\sf sk}_{{\sf ID}^\prime}\leftarrow{\sf IBE.KeyGen}({\sf MPK}_j,{\sf MSK}_j,{\sf ID}^\prime)\), \({\sf IBE.Dec}({\sf MPK}_j,{\sf ct_{IBE}},{\sf sk}_{{\sf ID}^\prime})=\bot\) holds if not only the case \({\sf ID}\neq {\sf ID}^\prime\) but also the case \({\sf MPK}_i\neq {\sf MPK}_j\). This robustness across the different master public keys is not directly provided even if the underlying IBE scheme is robust.

5.2  Our Construction

Next, we give the proposed generic construction. To employ a single master public key, we employ \({\sf HIBE}\) in the proposed construction where a keyword is regarded as a second-level identity and a trapdoor is generated by using the key derivation algorithm of the underlying HIBE scheme.

For Providing CCA Security. As mentioned in Sect. 2.4, the Fazio-Perera generic construction provides CCA security (in the broadcast encryption context) if the underlying IBE scheme is CCA secure. Note that they employ a one-time signature scheme in addition to employ IBE because a set of IBE ciphertexts \(\{{{\sf ct}_{{\sf IBE},j}}\}_{j\in[1,L]}\) is malleable (e.g., by a simple permutation) even if an IBE ciphertext \({{\sf ct}_{{\sf IBE},j}}\) is non-malleable due to the CCA security. That is, a verification key \({\sf vk}\) is contained as \({{\sf ct}_{{\sf IBE},j}}\leftarrow{\sf IBE.Enc}({\sf MPK},x_j,M||{\sf vk})\) for \(j=1,2,\ldots,\ell\), and \({{\sf ct}_{{\sf IBE},j}}\leftarrow{\sf IBE.Enc}({\sf MPK},{\sf dummy},\tilde{M})\) for \(j=\ell+1,\ldots,L\) where \(\tilde{M}\xleftarrow{＄}\{0,1\}^{|M|+|{\sf vk}|}\). A signature \(\sigma\) is generated on \({\sf vk}||\{{{\sf ct}_{{\sf IBE},j}}\}_{j\in[1,L]}\) and \((\sigma,{\sf vk},\{{{\sf ct}_{{\sf IBE},j}}\}_{j\in[1,L]})\) is a ciphertext.

By using the Fazio-Perera methodology, one direct BEKS construction is: (1) construct a CCA secure 2-level HIBE from 3-level HIBE and one-time signatures via the CHK transformation, (2) convert the 2-level HIBE to be weakly robust, and (3) construct a CCA secure BEKS from the 2-level HIBE and one-time signatures via the Fazio-Perera methodology. However, one-time signatures are employed twice for providing CCA security for HIBE and for BEKS, respectively. For providing more efficient construction, we employ 3-level CPA secure HIBE and one-time signatures and directly construct BEKS that employs one-time signatures once.

The Proposed Generic Construction

• \({\sf BEKS.Setup}(1^\lambda,N)\): Run \(({\sf MPK}^\prime,{\sf MSK})\leftarrow{\sf HIBE.Setup}(1^\lambda)\). For \(j=1,\ldots,N\), let \({\sf Path}(j)=\{x^\prime_1,\ldots, x^\prime_h\}\) where \(h\) is the depth of \({\sf BT}\) and \(x^\prime_1={\sf root}\). For \(k=1,\ldots,h\), run \({\sf sk}^{(j)}_{k}\leftarrow{\sf HIBE.KeyGen}({\sf MSK}, x^\prime_k)\). Output \({\sf MPK}=({\sf MPK}^\prime,N)\) and \(\{{\sf sk}_{{\sf R}[j]}\}_{j\in[1,N]}\) where \({\sf sk}_{{\sf R}[j]}=\{{\sf sk}^{(j)}_{k}\}_{k\in[1,h]}\). Here, \({\sf KWspace}={\sf IDspace}\).¹¹

• \({\sf BEKS.Enc}({\sf MPK},S,kw)\): Parse \({\sf MPK}=({\sf MPK}^\prime,N)\). Run \(({\sf vk},{\sf sigk})\leftarrow{\sf OTS.KeyGen}(1^\lambda)\). Specify \({\sf RSet}:=U\setminus S\) and run \({\sf cover}\leftarrow {\sf CompSubTree}({\sf BT},{\sf RSet})\) where \({\sf cover}=\{x_1,\ldots,x_\ell\}\). For \(j=1,\ldots,\ell\), run \({{\sf ct}_{{\sf HIBE},j}}\leftarrow{\sf HIBE.Enc}({\sf MPK}^\prime,(x_j,kw,{\sf vk}),0^\lambda)\). For \(j=\ell+1,\ldots,L\), run \({{\sf ct}_{{\sf HIBE},j}}\leftarrow{\sf HIBE.Enc}({\sf MPK}^\prime,({\sf dummy}, {\sf dummy}^\prime,{\sf vk}),\tilde{M})\) where \(\tilde{M}\xleftarrow{＄}\{0,1\}^{\lambda}\). Run \(\sigma\leftarrow{\sf OTS.Sign}({\sf sigk},\{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L]})\) where \(\pi:\{1,\ldots,L\}\rightarrow \{1,\ldots,L\}\) is a random permutation. Output \({\sf ct_{BEKS}}=({\sf vk},\sigma,\{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L]})\).

• \({\sf BEKS.Trapdoor}({\sf MPK},{\sf sk_{R}},kw^\prime)\): Parse \({\sf MPK}=({\sf MPK}^\prime,N)\). Assume that the receiver is assigned to the leaf node \(i\) and \({\sf sk_{R}}={\sf sk}_{{\sf R}[i]}\). Parse \({\sf sk}_{{\sf R}[i]}=\{{\sf sk}^{(i)}_{k}\}_{k\in[1,h]}\). For \(k=1,\ldots,h\), run \({\sf sk}^{(i)}_{k,kw^\prime}\leftarrow{\sf HIBE.KeyDer}({\sf MPK}^\prime,{\sf sk}^{(i)}_{k},kw^\prime)\). Output \({\sf td}_{{\sf R},kw^\prime}=\{{\sf sk}^{(i)}_{k,kw^\prime}\}_{k\in[1,h]}\).

• \({\sf BEKS.Test}({\sf MPK},{\sf ct_{BEKS}},{\sf td}_{{\sf R},kw^\prime})\): Parse \({\sf MPK}=({\sf MPK}^\prime,N)\), \({\sf ct_{BEKS}}=({\sf vk},\sigma,\{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L]})\) and \({\sf td}_{{\sf R},kw^\prime}=\{{\sf sk}_{k,kw^\prime}\}_{k\in[1,h]}\). Output 0 if \({\sf OTS.Verify}({\sf vk},\sigma, \{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L]})=0\). Otherwise, for \(k=1\) to \(h\), run \({\sf sk}_{k,kw^\prime,{\sf vk}}\leftarrow{\sf HIBE.KeyDer}({\sf MPK}^\prime,{\sf sk}_{k,kw^\prime},{\sf vk})\).
  

  • For \(k=1\) to \(h\) 

    • For \(j=1\) to \(L\) 

      • ＊  Run \(M\leftarrow {\sf HIBE.Dec}({\sf MPK}^\prime,{{\sf ct}_{{\sf HIBE},j}}, {\sf sk}_{k,kw^\prime,{\sf vk}})\).

      • ＊  If \(M=0^\lambda\), then return 1. Otherwise, if \(j=L\), break the loop. Otherwise, \(j\leftarrow j+1\).

    • If \(k=h\), return \(0\). Otherwise, \(k\leftarrow k+1\).

If \(i\in S\), then \({\sf cover}\cap {\sf Path}(i)\neq \emptyset\) due to the CS method. Let \(x_j\in {\sf cover}\cap {\sf Path}(i)\). If \(kw=kw^\prime\), then for \({\sf ct_{HIBE}}\leftarrow{\sf HIBE.Enc}({\sf MPK}^\prime,(x_j,kw,{\sf vk}),0^\lambda)\) contained in \({\sf ct_{BEKS}}\) and \({\sf sk}\leftarrow{\sf HIBE.KeyGen}({\sf MPK}^\prime, {\sf MSK},x_j)\), \({\sf td}_{{\sf R},kw}\ni{\sf sk}_{kw}\leftarrow{\sf HIBE.KeyDer}({\sf MPK}^\prime,{\sf sk},kw)\), and \({\sf sk}_{kw,{\sf vk}}\leftarrow{\sf HIBE.KeyDer}({\sf MPK}^\prime,{\sf sk}_{kw},{\sf vk})\), \(0^\lambda\leftarrow {\sf HIBE.Dec}({\sf MPK}^\prime,{\sf ct_{HIBE}},{\sf sk}_{kw,{\sf vk}})\) holds. Thus, correctness directly holds due to the correctness of the underlying IBE scheme and one-time signature scheme. We remark that one may require that there exists only one \({{\sf ct}_{{\sf HIBE},j}}\) such that \(0^\lambda\leftarrow {\sf HIBE.Dec}({\sf MPK}^\prime,{{\sf ct}_{{\sf HIBE},j}},{\sf sk}_{k,kw^\prime,{\sf vk}})\) holds for some \(k\in[1,h]\). For example, let a content be also encrypted and the ciphertext be preserved together with \({{\sf ct}_{{\sf HIBE},j}}\). The cloud server returns the \(j\)-th content ciphertext if the test algorithm finds \(j\) where \(0^\lambda\leftarrow {\sf HIBE.Dec}({\sf MPK}^\prime,{{\sf ct}_{{\sf HIBE},j}},{\sf sk}_{k,kw^\prime,{\sf vk}})\) holds. If a different content is chosen according to the receiver, then finding the unique \(j\) is mandatory, and then the \({\sf BEKS.Trapdoor}\) algorithm outputs \(0\) if there exist two or more ciphertexts that the decryption results are \(0^\lambda\). Actually, the proposed construction provides the correctness in this stronger notion when the underlying HIBE scheme is weakly robust. Note that we need to introduce computational correctness in this case.

6.  Security Analysis

Theorem 1. The proposed construction is computationally consistent if \({\sf HIBE}\) is weakly robust.

Proof. Let \({\mathcal A}\) be an adversary of computational consistency of the proposed construction and \({\mathcal C}\) be the challenger of weak robustness of \({\sf HIBE}\). We construct an algorithm \({\mathcal B}\) that breaks weak robustness as follows. \({\mathcal C}\) runs \(({\sf MPK}^\prime,{\sf MSK})\leftarrow{\sf HIBE.Setup}(1^\lambda)\) and sends \({\sf MPK}^\prime\) to \({\mathcal B}\). \({\mathcal B}\) sends \({\sf MPK}=({\sf MPK}^\prime,N)\) to \({\mathcal A}\). \({\mathcal A}\) declares \((kw,kw^\prime,S^\ast,i^\ast)\) where either \(kw\neq kw^\prime\) or \(i^\ast\not\in S^\ast\). \({\mathcal B}\) runs \(({\sf vk},{\sf sigk})\leftarrow{\sf OTS.KeyGen}(1^\lambda)\), specifies \({\sf RSet}:=\{i~|~i\in U\wedge i\not\in S^\ast\}\) and runs \({\sf cover}\leftarrow {\sf CompSubTree}({\sf BT},{\sf RSet})\) where \({\sf cover}=\{x_1,\ldots,x_\ell\}\). Moreover, let \({\sf Path}(i^\ast)=\{x^\prime_1,\ldots, x^\prime_h\}\). \({\mathcal B}\) randomly chooses \(x\xleftarrow{＄}{\sf cover}\) and \(x^\prime\xleftarrow{＄}{\sf Path}(i^\ast)\), and sets \(({\sf ID}_0,{\sf ID}^\prime_0,{\sf ID}^{\prime\prime}_0)=(x,kw,{\sf vk})\) and \(({\sf ID}_1,{\sf ID}^\prime_1,{\sf ID}^{\prime\prime}_1)=(x^\prime,kw^\prime,{\sf vk})\). \({\mathcal B}\) sends \(({\sf ID}_0,{\sf ID}^\prime_0,{\sf ID}^{\prime\prime}_0)=(x,kw,{\sf vk})\), \(({\sf ID}_1,{\sf ID}^\prime_1,{\sf ID}^{\prime\prime}_1)=(x^\prime,kw^\prime,{\sf vk})\), and \(M^\ast=0^\lambda\) to \({\mathcal C}\).

We estimate the success probability of \(\mathcal{B}\) as follows. Now, for \({\sf ct_{BEKS}}\leftarrow{\sf BEKS.Enc}({\sf MPK}^\prime,S^\ast,kw)\) and \({\sf td}_{{\sf R},kw^\prime}\leftarrow{\sf BEKS.Trapdoor}({\sf MPK}^\prime\), \({\sf sk}_{{\sf R}[i^\ast]}\), \(kw^\prime)\), \({\sf BEKS.Test}({\sf MPK}^\prime\), \({\sf ct_{BEKS}}\), \({\sf td}_{{\sf R},kw^\prime})=1\) holds. That is, there exist at least one \({{\sf ct}_{{\sf HIBE},j}}\) and \({\sf sk}^{(i^\ast)}_{k,kw^\prime,{\sf vk}}\) such that \(0^\lambda\leftarrow {\sf HIBE.Dec}({\sf MPK}^\prime,{{\sf ct}_{{\sf HIBE},j}},{\sf sk}_{k,kw^\prime,{\sf vk}})\) holds. This implies that, with the probability at least \(1/|{\sf cover}||{\sf Path}(i^\ast)|=1/\ell h>1/Lh\), \({\sf HIBE.Dec}({\sf MPK}^\prime,{{\sf ct}_{{\sf HIBE},j}},{\sf sk}_{k,kw^\prime,{\sf vk}})=0^\lambda\) holds where \({{\sf ct}_{{\sf HIBE},j}}\) is a ciphertext of \(0^\lambda\) under the identities \((x,kw,{\sf vk})\), \({\sf sk}_{k,kw^\prime,{\sf vk}}\) is a secret key for the identities \((x^\prime,kw^\prime,{\sf vk})\), and \((x,kw,{\sf vk})\neq (x^\prime,kw^\prime,{\sf vk})\). Note that if \(i^\ast\not\in S^\ast\), then \({\sf cover}\cap{\sf Path}(i^\ast)=\emptyset\). Thus, either \(kw\neq kw^\prime\) or \(i^\ast\not\in S^\ast\) implies \((x,kw)\neq (x^\prime,kw^\prime)\). \({\mathcal B}\) breaks weak robustness with the probability at least \(1/Lh\). \(\tag*{◻}\)

Theorem 2.The proposed construction is outsider anonymous if \({\sf HIBE}\) is Anon-CPA secure and \({\sf OTS}\) is sEUF-CMA secure.

Proof. Let \((kw_0^\ast,kw_1^\ast,S_0^\ast,S_1^\ast)\) be the output by the adversary \({\mathcal A}\) in the experiment. Let \(R^\ast\) be the number of revoked users in the challenge ciphertext, i.e., \(R^\ast=N-|S^\ast_b|\) for \(b=0,1\), and \(L^\ast\) be \(\lfloor R^\ast\log(N/R^\ast) \rfloor\). For \(b=0,1\), let \({\sf cover}_b=\{x^{(b)}_1,\ldots,x^{(b)}_{\ell_b}\}\) be determined by \({\sf RSet}_b:=\{i~|~i\in U\wedge i\not\in S_b^\ast\}\) and \({\sf cover}_b\leftarrow {\sf CompSubTree}({\sf BT},{\sf RSet}_b)\).

We define a sequence of games \({\sf Game}^{0}_{0},{\sf Game}^{0}_{1},\ldots,{\sf Game}^{0}_{\ell_0}={\sf Game}^{1}_{\ell_1},\ldots,{\sf Game}^{1}_{1},{\sf Game}^{1}_{0}\). In \({\sf Game}^{0}_{0}\), the challenge ciphertext is generated by \(S_0^\ast\) for \(kw_0^\ast\) and in \({\sf Game}^{1}_{0}\), the challenge ciphertext is generated by \(S_1^\ast\) for \(kw_1^\ast\). Before giving the game descriptions, first, we construct an algorithm \({\mathcal B}_1\) that breaks sEUF-CMA security when \({\mathcal A}\) (in \({\sf Game}^{0}_{0}\)) sends a test query \((i,kw,{\sf ct_{BEKS}})\) where \({\sf ct_{BEKS}}=({\sf vk}^\ast,\sigma,\{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L]})\), \({\sf vk}^\ast\) is the verification key used for generating the challenge ciphertext, and \({\sf OTS.Verify}({\sf vk}^\ast,\sigma,\{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L]})=1\). The challenger of sEUF-CMA runs \(({\sf vk}^\ast,{\sf sigk}^\ast)\leftarrow{\sf OTS.KeyGen}(1^\lambda)\) and sends \({\sf vk}^\ast\) to \({\mathcal B}_1\). \({\mathcal B}_1\) generates other parameters and thus \({\mathcal B}_1\) can respond any query issued by \({\mathcal A}\). In the challenge phase, the challenge ciphertext \({\sf ct}^\ast_{\sf BEKS}\) is generated as follows. Set \(\tilde{M}\xleftarrow{＄}\{0,1\}^{\lambda}\).

• For \(j=1,\ldots,\ell_0\): Run \({{\sf ct}_{{\sf HIBE},j}}\leftarrow{\sf HIBE.Enc}({\sf MPK}^\prime,(x^{(0)}_j,kw^\ast_0,{\sf vk}^\ast),0^\lambda)\).

• For \(j=\ell_0+1,\ldots,L^\ast\): Run \({{\sf ct}_{{\sf HIBE},j}}\leftarrow{\sf HIBE.Enc}({\sf MPK}^\prime,({\sf dummy},{\sf dummy}^\prime,{\sf vk}^\ast),\tilde{M})\).

\({\mathcal B}_1\) sends \(\{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L^\ast]}\) to the challenger, obtains \(\sigma^\ast\leftarrow{\sf OTS.Sign}({\sf sigk}^\ast,\{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L^\ast]})\), and sets \({\sf ct}^\ast_{\sf BEKS}=({\sf vk}^\ast,\sigma^\ast,\{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L^\ast]})\). Assume that \({\mathcal A}\) sends a test query \((i,kw,{\sf ct_{BEKS}})\) such that \({\sf ct_{BEKS}}=({\sf vk}^\ast,\sigma^\prime,\{{{\sf ct}^\prime_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L]})\) and \({\sf OTS.Verify}({\sf vk}^\ast,\sigma^\prime,\{{{\sf ct}^\prime_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L]})=1\). Let \({\sf ct_{BEKS}}={\sf ct}^\ast_{\sf BEKS}\). Then, either \(i\not\in S^\ast_0\cup S^\ast_1\) or \(kw\not\in \{kw_0^\ast,kw_1^\ast\}\). Thus, \({\mathcal B}_1\) returns 0. Let \({\sf ct_{BEKS}}\neq {\sf ct}^\ast_{\sf BEKS}\) and \({\sf vk}^\prime={\sf vk}^\ast\) that implies \((\sigma^\ast,\{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L^\ast]})\neq (\sigma^\prime,\{{{\sf ct}^\prime_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L]})\). Because \({\sf OTS.Verify}({\sf vk}^\ast,\sigma^\prime,\{{{\sf ct}^\prime_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L]})=1\), \({\mathcal B}_1\) outputs \((\sigma^\prime,\{{{\sf ct}^\prime_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L]})\) and breaks sEUF-CMA security. We remark that \({\mathcal B}_1\) fails to make a reduction for an (artificial) adversary where it works when \(b=1\) and does not work when \(b=0\). However, in this case, we can define a sequence of games in the reverse order, i.e., the challenge ciphertext is generated by \(S^\ast_1\) for \(kw^\ast_1\) in the first game, and is generated by \(S^\ast_0\) for \(kw^\ast_0\) in the last game. Thus, without loss of generality, we start \({\sf Game}^{0}_{0}\) in our security proof.

Next, we give game descriptions of \({\sf Game}^{0}_{0},{\sf Game}^{0}_{1},\ldots,{\sf Game}^{0}_{\ell_0}={\sf Game}^{1}_{\ell_1},\ldots,{\sf Game}^{1}_{1},{\sf Game}^{1}_{0}\) as follows. In all games, we exclude the case that \({\mathcal A}\) issues a test query containing \({\sf vk}^\ast\) and contained signature \(\sigma\) is valid under \({\sf vk}^\ast\).

• \({\sf Game}^{0}_{t}\) \((t=0,1,\ldots,\ell_0)\): The challenge ciphertext \({\sf ct}^\ast_{\sf BEKS}\) is generated as follows. Set \(\tilde{M}\xleftarrow{＄}\{0,1\}^{\lambda}\). Run \(({\sf vk}^\ast,{\sf sigk}^\ast)\leftarrow{\sf OTS.KeyGen}(1^\lambda)\).
  

  • For \(j=1,\ldots,\ell_0-t\): Run \({{\sf ct}_{{\sf HIBE},j}}\leftarrow{\sf HIBE.Enc}({\sf MPK}^\prime,(x^{(0)}_j,kw^\ast_0,{\sf vk}^\ast), 0^\lambda)\).

  • For \(j=\ell_0-t+1,\ldots,L^\ast\): Run \({{\sf ct}_{{\sf HIBE},j}}\leftarrow{\sf HIBE.Enc}({\sf MPK}^\prime,({\sf dummy},{\sf dummy}^\prime,{\sf vk}^\ast),\tilde{M})\).

  
  Run \(\sigma^\ast\leftarrow{\sf OTS.Sign}({\sf sigk}^\ast,\{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L^\ast]})\) and set \({\sf ct}^\ast_{\sf BEKS}=({\sf vk}^\ast,\sigma^\ast,\{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L^\ast]})\).

• \({\sf Game}^{1}_{\ell_1}\): This is the same as \({\sf Game}^{0}_{\ell_0}\). In this game, all HIBE ciphertexts are \({{\sf ct}_{{\sf HIBE},j}}\leftarrow{\sf HIBE.Enc}({\sf MPK}^\prime,({\sf dummy},{\sf dummy}^\prime,{\sf vk}^\ast),\tilde{M})\) for all \(j=1,2,\ldots,L^\ast\).

• \({\sf Game}^{1}_{t^\prime}\) \((t^\prime=\ell_1-1,\ldots,1,0)\): The challenge ciphertext \({\sf ct}^\ast_{\sf BEKS}\) is generated as follows. Set \(\tilde{M}\xleftarrow{＄}\{0,1\}^{\lambda}\). Run \(({\sf vk}^\ast,{\sf sigk}^\ast)\leftarrow{\sf OTS.KeyGen}(1^\lambda)\).
  

  • For \(j=1,\ldots,\ell_1-t^\prime\): Run \({{\sf ct}_{{\sf HIBE},j}}\leftarrow{\sf HIBE.Enc}({\sf MPK}^\prime,(x^{(1)}_j,kw^\ast_1,{\sf vk}^\ast), 0^\lambda)\).

  • For \(j=\ell_1+t^\prime+1,\ldots,L^\ast\): Run \({{\sf ct}_{{\sf HIBE},j}}\leftarrow{\sf HIBE.Enc}({\sf MPK}^\prime,({\sf dummy},{\sf dummy}^\prime, {\sf vk}^\ast),\tilde{M})\).

  
  Run \(\sigma^\ast\leftarrow{\sf OTS.Sign}({\sf sigk}^\ast,\{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L^\ast]})\) and set \({\sf ct}^\ast_{\sf BEKS}=({\sf vk}^\ast,\sigma^\ast, \{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L^\ast]})\).

Let \({\sf Adv}_{{\sf BEKS},{\mathcal A}}^{0,t}(\lambda,N)\) and \({\sf Adv}_{{\sf BEKS},{\mathcal A}}^{1,t^\prime}(\lambda,N)\) be \({\mathcal A}\)’s advantage of winning in \({\sf Game}^{0}_{t}\) and \({\sf Game}^{1}_{t^\prime}\), respectively. By definition, \({\sf Adv}_{{\sf BEKS},{\mathcal A}}^{\sf outsider\text{-}anon}(\lambda,N)=|{\sf Adv}_{{\sf BEKS},{\mathcal A}}^{0,0}(\lambda,N)-{\sf Adv}_{{\sf BEKS},{\mathcal A}}^{1,0}(\lambda,N)|\). We show that there exists a series of algorithms \({\mathcal B}^\prime_t\) and \({\mathcal B}^\prime_{t^\prime}\) where \(|{\sf Adv}_{{\sf BEKS},{\mathcal A}}^{0,0}(\lambda,N)-{\sf Adv}_{{\sf BEKS},{\mathcal A}}^{1,0}(\lambda,N)|\leq \sum_{t=1}^{L^\ast} {\sf Adv}_{{\sf HIBE},{\mathcal B}^\prime_t}^{\sf Anon\text{-}CPA}(\lambda)+\sum_{t^\prime=1}^{L^\ast}\) \({\sf Adv}_{{\sf HIBE},{\mathcal B}^\prime_{t^\prime}}^{\sf Anon\text{-}CPA}(\lambda)\) as follows.

Lemma 1. For \(t=1,\ldots,\ell_0\), there exists an algorithm \({\mathcal B}^\prime_t\) where \(|{\sf Adv}_{{\sf BEKS},{\mathcal A}}^{0,t-1}(\lambda,N)-{\sf Adv}_{{\sf BEKS},{\mathcal A}}^{0,t}(\lambda,N)|\leq {\sf Adv}_{{\sf HIBE},{\mathcal B}^\prime_t}^{\sf Anon\text{-}CPA}(\lambda)\) holds.

Proof. We construct an algorithm \({\mathcal B}^\prime_t\) that breaks Anon-CPA security as follows. Let \({\mathcal C}\) be the challenger of Anon-CPA. \({\mathcal C}\) runs \(({\sf MPK}^\prime,{\sf MSK})\leftarrow{\sf HIBE.Setup}(1^\lambda)\) and sends \({\sf MPK}^\prime\) to \({\mathcal B}^\prime_t\). \({\mathcal B}^\prime_t\) sends \({\sf MPK}=({\sf MPK}^\prime,N)\) to \({\mathcal A}\). \({\mathcal B}^\prime_t\) runs \(({\sf vk}^\ast,{\sf sigk}^\ast)\leftarrow{\sf OTS.KeyGen}(1^\lambda)\).

• When \({\mathcal A}\) issues a trapdoor query \((i,kw)\), \({\mathcal B}^\prime_t\) sets \({\sf Path}(i)=\{x^\prime_1,\ldots, x^\prime_h\}\). For \(j=1,\ldots,h\), \({\mathcal B}^\prime_t\) sends \((x^\prime_j,kw)\) to \({\mathcal C}\) as a key extraction query. \({\mathcal C}\) runs \({\sf sk}_{j}\leftarrow{\sf HIBE.KeyGen}({\sf MSK}, x^\prime_j)\) and \({\sf sk}^{(i)}_{j,kw}\leftarrow{\sf HIBE.KeyDer}({\sf MPK}^\prime,{\sf sk}_{j},kw)\), and sends \({\sf sk}^{(i)}_{j,kw}\) to \({\mathcal B}^\prime_t\). \({\mathcal B}^\prime_t\) returns \({\sf td}_{{\sf R},kw}=\{{\sf sk}^{(i)}_{j,kw}\}_{j\in[1,h]}\) to \({\mathcal A}\).

• When \({\mathcal A}\) issues a corruption query \(i\), \({\mathcal B}^\prime_t\) sets \({\sf Path}(i)=\{x^\prime_1,\ldots, x^\prime_h\}\). For \(j=1,\ldots,h\), \({\mathcal B}^\prime_t\) sends \(x^\prime_j\) to \({\mathcal C}\) as a key extraction query. \({\mathcal C}\) runs \({\sf sk}_{j}\leftarrow{\sf HIBE.KeyGen}({\sf MSK}, x^\prime_j)\) and sends \({\sf sk}_{j}\) to \({\mathcal B}^\prime_t\). \({\mathcal B}\) returns \({\sf sk}_{{\sf R}[j]}=\{{\sf sk}^{(j)}_{k}\}_{k\in[1,h]}\) to \({\mathcal A}\).

• When \({\mathcal A}\) issues a test query \((i,kw,{\sf ct_{BEKS}})\) such that \({\sf ct_{BEKS}}=({\sf vk},\sigma,\{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L]})\) and \({\sf vk}\neq {\sf vk}^\ast\), \({\mathcal B}^\prime_t\) returns \(0\) if \({\sf OTS.Verify}({\sf vk},\sigma,\{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L]})=0\). Otherwise, \({\mathcal B}^\prime_t\) sets \({\sf Path}(i)=\{x^\prime_1,\ldots, x^\prime_h\}\), and for \(k=1,\ldots,h\), \({\mathcal B}^\prime_t\) sends \((x^\prime_k,kw,{\sf vk})\) to \({\mathcal C}\) as a key extraction query. \({\mathcal C}\) runs \({\sf sk}_{k}\leftarrow{\sf HIBE.KeyGen}({\sf MSK}, x^\prime_k)\), \({\sf sk}^{(i)}_{k,kw}\leftarrow{\sf HIBE.KeyDer}({\sf MPK}^\prime,{\sf sk}_{k},kw)\), and \({\sf sk}^{(i)}_{k,kw,{\sf vk}}\leftarrow{\sf HIBE.KeyDer}({\sf MPK}^\prime,{\sf sk}_{k,kw},{\sf vk})\), and sends \({\sf sk}^{(i)}_{k,kw,{\sf vk}}\) to \({\mathcal B}^\prime_t\). \({\mathcal B}^\prime_t\) responds the test query as follows.

  • For \(k=1\) to \(h\) 

    • ＊  For \(j=1\) to \(L\) 

      • Run \(M\leftarrow {\sf HIBE.Dec}({\sf MPK}^\prime,{{\sf ct}_{{\sf HIBE},j}}, {\sf sk}_{k,kw,{\sf vk}})\).

      • If \(M=0^\lambda\), then return 1. Otherwise, if \(j=L\), break the loop. Otherwise, \(j\leftarrow j+1\).

    • ＊  If \(k=h\), return \(0\). Otherwise, \(k\leftarrow k+1\).

In the challenge phase, \({\mathcal A}\) declares \((kw_0^\ast,kw_1^\ast,S_0^\ast,S_1^\ast)\). \({\mathcal B}\) specifies \({\sf RSet}_0:=\{i~|~i\in U\wedge i\not\in S_0^\ast\}\) and \({\sf cover}_0\leftarrow {\sf CompSubTree}({\sf BT},{\sf RSet}_0)\). Let \({\sf cover}_0=\{x^{(0)}_1,\ldots,x^{(0)}_{\ell_0}\}\). Here, \({\mathcal B}^\prime_t\) did not send a key extraction query for all \(x\in {\sf cover}_0\) directly because \(V\cap (S^\ast_0\cup S^\ast_1)=\emptyset\). More precisely, if \({\mathcal B}^\prime_t\) issued a key extraction query for \(x\in {\sf cover}_0\), then \({\mathcal B}^\prime_t\) sends either (1) \((x,kw)\) where \(kw\not\in \{kw_0^\ast,kw_1^\ast\}\) or (2) \((x,kw,{\sf vk})\) where \({\sf vk}\neq{\sf vk}^\ast\). Thus, we can set \(({\sf ID}_0,{\sf ID}^\prime_0,{\sf ID}^{\prime\prime}_0)=(x^{(0)}_j,kw^\ast_0,{\sf vk}^\ast)\) below. \({\mathcal B}^\prime_t\) generates the challenge ciphertext \({\sf ct}^\ast_{\sf BEKS}\) as follows. Set \(\tilde{M}\xleftarrow{＄}\{0,1\}^{\lambda}\).

• For \(j=1,\ldots,\ell_0-t\): Run \({{\sf ct}_{{\sf HIBE},j}}\leftarrow{\sf HIBE.Enc}({\sf MPK}^\prime,(x^{(0)}_j,kw^\ast_0,{\sf vk}^\ast),0^\lambda)\).

• For \(j=\ell_0-t+1\), \({\mathcal B}^\prime_t\) sets \(({\sf ID}_0,{\sf ID}^\prime_0,{\sf ID}^{\prime\prime}_0)=(x^{(0)}_j,kw^\ast_0,{\sf vk}^\ast)\), \(({\sf ID}_1,{\sf ID}^\prime_1,{\sf ID}^{\prime\prime}_1)=({\sf dummy},{\sf dummy}^\prime, {\sf vk}^\ast)\), \(M_0^\ast=0^\lambda\), and \(M^\ast_1=\tilde{M}\), and sends \((({\sf ID}_0,{\sf ID}^\prime_0,{\sf ID}^{\prime\prime}_0),({\sf ID}_1,{\sf ID}^\prime_1,{\sf ID}^{\prime\prime}_1),M_0^\ast,M^\ast_1)\) to \({\mathcal C}\) as the challenge query. \({\mathcal C}\) generates \({\sf ct^\ast_{HIBE}}\leftarrow {\sf HIBE.Enc}({\sf MPK}^\prime,({\sf ID}_b,{\sf ID}^\prime_b,{\sf vk}^\ast),M^\ast_b)\) and sends \({\sf ct^\ast_{HIBE}}\) to \({\mathcal B}^\prime_t\). \({\mathcal B}^\prime_t\) sets \({{\sf ct}_{{\sf HIBE},j}}={\sf ct^\ast_{HIBE}}\).

• For \(j=\ell_0-t+2,\ldots,L^\ast\): Run \({{\sf ct}_{{\sf HIBE},j}}\leftarrow{\sf HIBE.Enc}({\sf MPK}^\prime,({\sf dummy},{\sf dummy}^\prime,{\sf vk}^\ast),\tilde{M})\).

\({\mathcal B}^\prime_t\) runs \(\sigma^\ast\leftarrow{\sf OTS.Sign}({\sf sigk}^\ast,\{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L^\ast]})\) and sets \({\sf ct}^\ast_{\sf BEKS}=({\sf vk}^\ast,\sigma^\ast,\{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L^\ast]})\). \({\mathcal B}^\prime_t\) sends \({\sf ct}^\ast_{\sf BEKS}=({\sf vk}^\ast,\sigma^\ast,\{{{\sf ct}_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L^\ast]})\) to \({\mathcal A}\).

• When \({\mathcal A}\) issues a trapdoor query \((i,kw)\), \({\mathcal B}^\prime_t\) returns \(\bot\) if \(i\in S^\ast_0\cup S^\ast_1\) and \(kw\in\{kw^\ast_0,kw^\ast_1\}\). Otherwise, \({\mathcal B}^\prime_t\) proceeds as in the pre-challenge phase.

• When \({\mathcal A}\) issues a corruption query \(i\), \({\mathcal B}^\prime_t\) returns \(\bot\) if \(i\in S^\ast_0\cup S^\ast_1\). Otherwise, \({\mathcal B}\) proceeds as in the pre-challenge phase.

• When \({\mathcal A}\) issues a test query \((i,kw,{\sf ct_{BEKS}})\) such that \({\sf ct_{BEKS}}=({\sf vk},\sigma,\{{{\sf ct}^\prime_{{\sf HIBE},\pi(j)}}\}_{j\in[1,L]})\), \({\mathcal B}^\prime_t\) returns \(\bot\) if \(i\in S^\ast_0\cup S^\ast_1\) and \({\sf ct_{BEKS}}={\sf ct}^\ast_{\sf BEKS}\). Otherwise, \({\mathcal B}\) proceeds as in the pre-challenge phase.

Finally, \({\mathcal A}\) outputs \(b^\prime\). \({\mathcal B}^\prime_t\) outputs \(b^\prime\). If \(b=0\), then \({\mathcal B}^\prime_t\) simulates \({\sf Game}^{0}_{t-1}\) and if \(b=1\), then \({\mathcal B}^\prime_t\) simulates \({\sf Game}^{0}_{t}\). Thus, the claim holds.\(\tag*{◻}\)

The proof of Lemma 2 is almost the same as that of Lemma 1, except that \({\mathcal B}^\prime_{t^\prime}\) specifies \({\sf RSet}_1:=\{i~|~i\in U\wedge i\not\in S_1^\ast\}\) and \({\sf cover}_1\leftarrow {\sf CompSubTree}({\sf BT},{\sf RSet}_1)\) in the challenge phase. Thus, we omit the proof.

Lemma 2. For \(t^\prime=\ell_1-1,\ldots,0\), there exists an algorithm \({\mathcal B}^\prime_{t^\prime}\) where \(|{\sf Adv}_{{\sf BEKS},{\mathcal A}}^{1,t^\prime+1}(\lambda,N)-{\sf Adv}_{{\sf BEKS},{\mathcal A}}^{1,t^\prime}(\lambda,N)|\leq {\sf Adv}_{{\sf HIBE},{\mathcal B}^\prime_{t^\prime}}^{\sf Anon\text{-}CPA}(\lambda)\) holds.

By Lemma 1 and Lemma 2, we conclude the proof of Theorem 2.\(\tag*{◻}\)

7.  Conclusion

In this paper, from 3-level anonymous and weakly robust HIBE we proposed a generic construction of outsider anonymous BEKS with sublinear size ciphertexts. Our result could be regarded as a stepping stone to propose an outsider anonymous BAEKS scheme with sublinear-size ciphertexts. Since we employed the CS method, the subset difference (SD) method could be employed by adding more hierarchy level, due to the SD method in the public key setting from HIBE [53]. We leave them as open problems. Also, it would be interesting to investigate whether other efficient outsider anonymous schemes, e.g. [54], [55], can be employed in the BEKS/BAEKS context or not.

The proposed construction requires approximately \(L/2\)-times HIBE decryption procedures where \(L=\lfloor R\log(N/R) \rfloor\). To reduce the number of decryption attempts in the generic construction of anonymous broadcast encryption, Libert et al. [14] proposed an anonymous hint system that provides \(O(1)\) decryption cost in terms of the number of cryptographic operations. Moreover, Fazio and Perera [15] also considered to reduce the number of decryption procedure by employing trapdoor test of twin Diffie-Hellman problem [56]. In both attempts, additional secret values are introduced in addition to the decryption key. That is, as mentioned in [28], if these systems are employed in BEKS, then the cloud server, that runs the \({\sf BEKS.Test}\) algorithm, obtains information about the receivers before running the test algorithm. Consequently, we did not employ these systems in this paper. We leave this task as an interesting future work.

Acknowledgments

The main part of this study was done when the first author, Keita Emura, was with the National Institute of Information and Communications Technology, Japan. This work was supported by JSPS KAKENHI Grant Number JP21K11897.

References

[1] D. Boneh, G.D. Crescenzo, R. Ostrovsky, and G. Persiano, “Public key encryption with keyword search,” EUROCRYPT, pp.506-522, 2004.

[2] N. Attrapadung, J. Furukawa, and H. Imai, “Forward-secure and searchable broadcast encryption with short ciphertexts and private keys,” ASIACRYPT, pp.161-177, 2006.

[3] S. Chatterjee and S. Mukherjee, “Keyword search meets membership testing: Adaptive security from SXDH,” INDOCRYPT, pp.21-43, 2018.

[4] M. Ambrona, G. Barthe, and B. Schmidt, “Generic transformations of predicate encodings: Constructions and applications,” CRYPTO, pp.36-66, 2017.

[5] J. Chen, R. Gay, and H. Wee, “Improved dual system ABE in prime-order groups via predicate encodings,” EUROCRYPT, pp.595-624, 2015.

[6] J. Chen and J. Gong, “ABE with tag made easy ― Concise framework and new instantiations in prime-order groups,” ASIACRYPT, pp.35-65, 2017.

[7] P. Jiang, F. Guo, and Y. Mu, “Efficient identity-based broadcast encryption with keyword search against insider attacks for database systems,” Theoretical Computer Science, vol.767, pp.51-72, 2019.

[8] A. Kiayias, O. Oksuz, A. Russell, Q. Tang, and B. Wang, “Efficient encrypted keyword search for multi-user data sharing,” ESORICS, pp.173-195, 2016.

[9] M. Ma, S. Fan, and D. Feng, “Multi-user certificateless public key encryption with conjunctive keyword search for cloud-based telemedicine,” Journal of Information Security and Applications, vol.55, p.102652, 2020.

[10] T. Feng and J. Si, “Certificateless searchable encryption scheme in multi-user environment,” Cryptography, vol.6, no.4, p.61, 2022.

[11] K. Zhang, M. Wen, R. Lu, and K. Chen, “Multi-client sub-linear boolean keyword searching for encrypted cloud storage with owner-enforced authorization,” IEEE Trans. Dependable Secure Comput., vol.18, no.6, pp.2875-2887, 2021.

[12] N. Yang, Q. Zhou, Q. Huang, and C. Tang, “Multi-recipient encryption with keyword search without pairing for cloud storage,” J. Cloud Comp., vol.11, p.10, 2022.

[13] M. Ali, H. Ali, T. Zhong, F. Li, Z. Qin, and A.A. Ahmed Abdelrahaman, “Broadcast searchable keyword encryption,” IEEE CSE, pp.1010-1016, 2014.

[14] B. Libert, K.G. Paterson, and E.A. Quaglia, “Anonymous broadcast encryption: Adaptive security and efficient constructions in the standard model,” Public Key Cryptography, pp.206-224, 2012.

[15] N. Fazio and I.M. Perera, “Outsider-anonymous broadcast encryption with sublinear ciphertexts,” Public Key Cryptography, pp.225-242, 2012.

[16] A. Barth, D. Boneh, and B. Waters, “Privacy in encrypted content distribution using private broadcast encryption,” Financial Cryptography and Data Security, pp.52-64, 2006.

[17] H. Kobayashi, Y. Watanabe, K. Minematsu, and J. Shikata, “Tight lower bounds and optimal constructions of anonymous broadcast encryption and authentication,” Des. Codes Cryptogr., vol.91, no.7, pp.2523-2562, 2023.

[18] A. Kiayias and K. Samari, “Lower bounds for private broadcast encryption,” Information Hiding, pp.176-190, 2012.

[19] J. Li and J. Gong, “Improved anonymous broadcast encryptions ― Tight security and shorter ciphertext,” ACNS, pp.497-515, 2018.

[20] X. Liu, K. He, G. Yang, W. Susilo, J. Tonien, and Q. Huang, “Broadcast authenticated encryption with keyword search,” ACISP, pp.193-213, 2021.

[21] B. Qin, H. Cui, X. Zheng, and D. Zheng, “Improved security model for public-key authenticated encryption with keyword search,” ProvSec, pp.19-38, 2021.

[22] L. Cheng and F. Meng, “Public key authenticated encryption with keyword search from LWE,” ESORICS, pp.303-324, 2022.

[23] K. Emura, “Generic construction of public-key authenticated encryption with keyword search revisited: Stronger security and efficient construction,” ACM APKC, pp.39-49, 2022.

[24] Q. Huang and H. Li, “An efficient public-key searchable encryption scheme secure against inside keyword guessing attacks,” Information Sciences, vols.403-404, pp.1-14, 2017.

[25] Z. Liu, Y. Tseng, R. Tso, M. Mambo, and Y. Chen, “Public-key authenticated encryption with keyword search: Cryptanalysis, enhanced security, and quantum-resistant instantiation,” ACM ASIACCS, pp.423-436, 2022.

[26] L. Yao, J. Weng, A. Yang, X. Liang, Z. Wu, Z. Jiang, and L. Hou, “Scalable CCA-secure public-key authenticated encryption with keyword search from ideal lattices in cloud computing,” Information Sciences, vol.624, pp.777-795, 2023.

[27] S. Mukherjee, “Statistically consistent broadcast authenticated encryption with keyword search: Adaptive security from standard assumptions,” ACISP, pp.523-552, 2023.

[28] K. Emura, “Generic construction of fully anonymous broadcast authenticated encryption with keyword search with adaptive corruptions,” IET Information Security, vol.2023, pp.9922828:1-9922828:12, 2023.

[29] D. Naor, M. Naor, and J. Lotspiech, “Revocation and tracing schemes for stateless receivers,” CRYPTO, pp.41-62, 2001.

[30] R. Canetti, S. Halevi, and J. Katz, “Chosen-ciphertext security from identity-based encryption,” EUROCRYPT, pp.207-222, 2004.

[31] M. Abdalla, M. Bellare, and G. Neven, “Robust encryption,” J. Cryptol., vol.31, no.2, pp.307-350, 2018.

[32] M. Abdalla, M. Bellare, and G. Neven, “Robust encryption,” TCC, pp.480-497, 2010.

[33] S.C. Ramanna and P. Sarkar, “Efficient (anonymous) compact HIBE from standard assumptions,” ProvSec, pp.243-258, 2014.

[34] R. Langrehr and J. Pan, “Hierarchical identity-based encryption with tight multi-challenge security,” Public-Key Cryptography, pp.153-183, 2020.

[35] O. Blazy, E. Kiltz, and J. Pan, “(Hierarchical) Identity-based encryption from affine message authentication,” CRYPTO, pp.408-425, 2014.

[36] S. Agrawal, D. Boneh, and X. Boyen, “Efficient lattice (H)IBE in the standard model,” EUROCRYPT, pp.553-572, 2010.

[37] D. Boneh and X. Boyen, “Efficient selective-ID secure identity-based encryption without random oracles,” EUROCRYPT, pp.223-238, 2004.

[38] S. Yamada, “Asymptotically compact adaptively secure lattice IBEs and verifiable random functions via generalized partitioning techniques,” CRYPTO, pp.161-193, 2017.

[39] K. Asano, K. Emura, and A. Takayasu, “More efficient adaptively secure lattice-based IBE with equality test in the standard model,” ISC, pp.75-83, 2022.

[40] T. Jager, R. Kurek, and D. Niehues, “Efficient adaptively-secure IB-KEMs and VRFs via near-collision resistance,” Public-Key Cryptography, pp.596-626, 2021.

[41] S.C. Ramanna and P. Sarkar, “Anonymous constant-size ciphertext HIBE from asymmetric pairings,” IMACC, pp.344-363, 2013.

[42] K. Lee, J.H. Park, and D.H. Lee, “Anonymous HIBE with short ciphertexts: Full security in prime order groups,” Des. Codes Cryptogr., vol.74, no.2, pp.395-425, 2015.

[43] S. Agrawal, D. Boneh, and X. Boyen, “Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE,” CRYPTO, pp.98-115, 2010.

[44] D. Cash, D. Hofheinz, E. Kiltz, and C. Peikert, “Bonsai trees, or how to delegate a lattice basis,” J. Cryptol., vol.25, no.4, pp.601-639, 2012.

[45] X. Boyen and Q. Li, “Towards tightly secure lattice short signature and ID-based encryption,” ASIACRYPT, pp.404-434, 2016.

[46] D. Boneh and X. Boyen, “Efficient selective-ID secure identity based encryption without random oracles,” IACR Cryptology ePrint Archive, p.172, 2004. https://eprint.iacr.org/2004/172

[47] T. Yamakawa and M. Zhandry, “Classical vs quantum random oracles,” EUROCRYPT, pp.568-597, 2021.

[48] M. Zhandry, “Secure identity-based encryption in the quantum random oracle model,” CRYPTO, pp.758-775, 2012.

[49] K. Singh, C.P. Rangan, and A.K. Banerjee, “Adaptively secure efficient lattice (H)IBE in standard model with short public parameters,” SPACE, pp.153-172, 2012.

[50] W. Aiello, S. Lodha, and R. Ostrovsky, “Fast digital identity revocation (extended abstract),” CRYPTO, pp.137-152, 1998.

[51] A. Boldyreva, V. Goyal, and V. Kumar, “Identity-based encryption with efficient revocation,” ACM CCS, pp.417-426, ACM, 2008.

[52] M. Abdalla, M. Bellare, D. Catalano, E. Kiltz, T. Kohno, T. Lange, J. Malone-Lee, G. Neven, P. Paillier, and H. Shi, “Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions,” J. Cryptol., vol.21, no.3, pp.350-391, 2008.

[53] Y. Dodis and N. Fazio, “Public key broadcast encryption for stateless receivers,” ACM DRM, pp.61-80, 2002.

[54] M. Mandal and R. Dutta, “Efficient identity-based outsider anonymous public-key trace and revoke with constant ciphertext-size and fast decryption,” Inscrypt, pp.365-380, 2019.

[55] M. Mandal and K. Nuida, “Identity-based outsider anonymous broadcast encryption with simultaneous individual messaging,” Network and System Security, pp.167-186, 2020.

[56] D. Cash, E. Kiltz, and V. Shoup, “The twin Diffie-Hellman problem and applications,” EUROCRYPT, pp.127-145, 2008.

Footnotes

1. Note that Chatterjee and Mukherjee [3] called a BEKS scheme anonymous, if the challenge ciphertext hides associated challenge keyword.

2. In PAEKS, the encryption algorithm takes a sender secret key (in addition to a receiver public key and a keyword) as input, and the trapdoor generation algorithm takes a sender public key (in addition to a receiver secret key and a keyword) as input. This setting allows us to prevent the keyword guessing attack. See [21]-[26] for details.

3. As mentioned by Boneh et al. [1], PEKS implies a one-bit encryption scheme where for a plaintext \(m\in\{0,1\}\), a ciphertext of \(m\) is a PEKS ciphertext for the keyword \(m\), and a decryption key is two trapdoors for the keywords 0 and 1, respectively. By using the transformation, a one-bit broadcast encryption scheme can be constructed from BAEKS. However, it is not clear whether the lower bound of the ciphertext size can be adopted in BAEKS. Especially, a secret key is required for encryption in BAEKS unlike to broadcast encryption. Thus, further analysis is required whether the linear-size ciphertext is mandatory when full anonymity is required in BAEKS, and we leave it as a future work of this paper.

4. When the \(k\)-linear assumption is employed, we state it the SXDH assumption by setting \(k=1\) in Table 1.

5. This is a reason why the keyword guessing attack has been widely researched: an adversary \({\mathcal A}\), that has a trapdoor, generates a PEKS ciphertext for a keyword \(kw\) chosen by \({\mathcal A}\) and runs the test algorithm with the trapdoor. If the test algorithm outputs 1, then \({\mathcal A}\) can detect that \(kw\) is associated to the trapdoor. Otherwise, \({\mathcal A}\) selects other keyword. If the size of keyword space is relatively small or keywords have low entropy, then this keyword guessing attack is a real threat.

6. Though Asano et al. did not formally mention that 3-level HIBE schemes are anonymous, they showed that an HIBE ciphertext is indistinguishable from random in their security proof.

7. In the security proof, they showed that almost all elements of ciphertext are indistinguishable from random which is sufficient to prove that no information of keyword is revealed from ciphertexts. However, an element is selected from receiver’s public key related distribution. Thus, it is not clear whether the Cheng-Meng PAEKS scheme provides anonymity. We emphasize that Cheng and Meng did not claim that their scheme provides anonymity.

8. More precisely, as mentioned in [50], [51], \(|{\sf cover}|\) is estimated as \(O(R\log(N/R))\) if \(R\leq N/2\) and is estimated as \(O(N-R)\) if \(N/2 < R \leq N\). We assume that \(R\) is relatively smaller than \(N\) and then our construction provides sublinear-size ciphertext.

9. Precisely, Abdalla et al. gave the transformation for general encryption that implies IBE and PKE.

10. Oxford English Dictionary (the second edition of the 20-volume) contains 171,476 words. \(2^{18}=262,144\) can cover the number of words. See https://wordcounter.io/blog/how-many-words-are-in-the-english-language.

11. In Definition 1, a hierarchical identity is represented as a tuple of three elements in the same space \({\sf IDspace}\). This does not prevent the correctness of the proposed construction since (H)IBE allows us to employ any string as a public key. More precisely, if the size of keyword space \({\sf KWspace}\) is relatively small (e.g., \(|{\sf KWspace}|=2^{18}\) as mentioned in Sect. 3), then we regard \({\sf KWspace}\subset {\sf IDspace}\).

Authors

Keita EMURA
  Kanazawa University,National Institute of Information and Communications Technology

Kaisei KAJITA
  Japan Broadcasting Corporation

Go OHTAKE
  Japan Broadcasting Corporation

Keyword

broadcast encryption with keyword search,  outsider anonymity,  CCA security