Efficient identity-based encryption with Hierarchical key-insulation from HIBE

Abstract

Hierarchical key-insulated identity-based encryption (HKIBE) is identity-based encryption (IBE) that allows users to update their secret keys to achieve (hierarchical) key-exposure resilience, which is an important notion in practice. However, existing HKIBE constructions have limitations in efficiency: sizes of ciphertexts and secret keys depend on the hierarchical depth. In this paper, we first triumph over the barrier by proposing simple but effective design methodologies to construct efficient HKIBE schemes. First, we show a generic construction from any hierarchical IBE (HIBE) scheme that satisfies a special requirement, called MSK evaluatability introduced by Emura et al. (Des. Codes Cryptography 89(7):1535–1574, 2021). It provides several new and efficient instantiations since most pairing-based HIBE schemes satisfy the requirement. It is worth noting that it preserves all parameters’ sizes of the underlying HIBE scheme, and hence we obtain several efficient HKIBE schemes under the k-linear assumption in the standard model. Since MSK evaluatability is dedicated to pairing-based HIBE schemes, the first construction restricts pairing-based instantiations. To realize efficient instantiation from various assumptions, we next propose a generic construction of an HKIBE scheme from any plain HIBE scheme. It is based on Hanaoka et al.’s HKIBE scheme (Asiacrypt 2005), and does not need any special properties. Therefore, we obtain new efficient instantiations from various assumptions other than pairing-oriented ones. Though the sizes of secret keys and ciphertexts are larger than those of the first construction, it is more efficient than Hanaoka et al.’s scheme in the sense of the sizes of master public/secret keys.

1 Introduction

1.1 Background

Identity-based encryption (IBE) [12] allows us to use arbitrary strings (e.g., user names, e-mail addresses) as users’ public keys. After earlier seminal works [10, 56], considerable research related to IBE has been conducted from various perspectives such as efficiency improvements [33, 42, 57], weakening assumptions [22], post-quantum constructions [4, 5, 14, 16], and additional security properties [8, 9, 13, 14, 19, 30]. Similar results have been obtained in the context of hierarchical IBE (HIBE)[27, 31], which is one of the important extensions of IBE; e.g., efficiency improvements [18, 28, 36, 37, 42,43,44, 57], weakening assumptions [21], post-quantum constructions [4, 5, 16], and additional security properties [13, 41, 49].

According to Cisco’s report [1], tens of billions of IoT devices are expected to be deployed over the next few years. Therefore, one of the key challenges is how to make communications over IoT devices fast and reliable. Recently, IBE is expected to be used in the IoT environments (e.g., [6, 35]) since devices’ identities (serial numbers, MAC addresses, etc.) can be set as their public keys.¹ Therefore, IoT devices can make reliable and fast communication without PKI (i.e., without verifying public-key certificates). Another practical security requirement for robust IoT systems is key-exposure resilience. Secure IoT systems using IBE should still be available and guarantee a certain security level even if some devices in the system are corrupted, and their secret keys are exposed. Particularly in the IoT setting, it is difficult to manually revoke and re-setup corrupted IoT devices since it seems hard to detect when and which devices leak their secret keys. Therefore, the key-exposure resilience is important in practice; it guarantees that even if some devices (partially) leak their secret keys, the devices are still available in some sense. Thus, we focus on the problem is how to achieve the key-exposure resilience (as efficient as possible) in the IBE setting.

One of promising approaches to address the above problem is the key-updating approach. This paper considers the following key-insulation mechanism [20, 30]. We prepare two kinds of secret keys depending on their roles: helper keys, stored on physically-secure devices, and decryption keys, which are stored on weak devices that may be tampered. Ciphertexts can be decrypted by decryption keys, which are periodically and non-interactively updated by helper keys. This approach is suitable for the above IoT scenario (and, of course, the more standard usage scenario) since (a) decryption keys are updated in a non-interactive way, and (b) decryption keys can be renewed and continue to be used regardless of whether the system owner knows which decryption keys are leaked. IBE with the key-insulation mechanism is called key-insulated IBE (KIBE) [30], and the security which should be achieved in this approach is:

• (1) even if many decryption keys are exposed, KIBE can guarantee the security of non-exposed decryption keys;

• (2) even if the helper key is exposed, no information on any decryption keys is leaked as long as no decryption keys are exposed.

The key-insulation structure can be extended to a hierarchical one, and IBE with the hierarchical key-insulated property is called hierarchical KIBE (HKIBE) [30].² In HKIBE, helper keys are separated into multiple levels. Helper keys can update lower-level helper keys, and the lowest-level helper keys update decryption keys. Thus, the impact of key leakage can be significantly reduced by storing helper keys at different levels in different devices.

Although HKIBE seems to provide practical applications as above, an efficiency issue in HKIBE constructions remains unsolved. Hanaoka et al. [30] showed a generic construction from any HIBE scheme. It can be instantiated from various assumptions, however essentially sacrifices sizes of ciphertexts and decryption keys; it requires at least O(L) HIBE ciphertexts and O(L) HIBE secret keys for the resulting ciphertexts and decryption keys, respectively, where L is the maximum depth of hierarchical key-insulation. Therefore, even if the underlying HIBE scheme achieves compact ciphertexts and/or secret keys, those of the resultant HKIBE scheme cannot be compact. Although Hanaoka et al. [30] also showed a concrete HKIBE scheme from computational bilinear Diffie-Hellman (CBDH) assumption, which is more efficient than the generic construction, it relies on the random oracle and do not have compact parameters, in the sense that sizes of ciphertexts and decryption keys are not constant. The work of [52, 55] proposed adaptively secure HKIBE schemes with compact ciphertexts and decryption keys from pairings; however, unfortunately, we found a flaw in the security proofs (which we communicated to the authors).³ Thus, there are no secure HKIBE constructions that achieve compact ciphertexts and decryption keys.

Table 1 A comparison between Hanaoka et al.’s generic construction and ours. “Generic HHSI05” means the generic construction shown in [30]

1.2 Our contributions

In this paper, we successfully make significant progress in constructing efficient HKIBE schemes. Specifically, we show two generic constructions of HKIBE schemes.

Generic construction from HIBE with MSK evaluatability We take note of the similarities in security games in HKIBE and revocable HIBE (RHIBE) [9, 49, 51]; unlike standard (H)IBE, an adversary is allowed to get (a part of) a secret key of a challenge identity in both games. Based on the observation, we take a similar approach to the recent RHIBE construction [24], and propose our first construction from any HIBE scheme that satisfies MSK evaluatability, which is the special algebraic property introduced in [24]. Although the property restricts an applicable class of HIBE schemes to our construction, most pairing-based HIBE schemes, including most-efficient-ever ones [17, 18, 28], meet it. Our generic construction provides several concrete HKIBE schemes with new features as follows.

• The first HKIBE schemes with compact ciphertexts and decryption keys from [17, 18] under the standard k-linear assumption. Note that there are no known schemes with similar efficiency even when we ignore the adaptive security, standard assumptions, and the standard model.⁴

• The first HKIBE scheme with compact master public keys in the standard model from [28] under the k-linear assumption.

Generic construction from any HIBE Our second construction aims to get rid of the special property required in our first construction, and is a generic construction from any plain HIBE schemes. While this construction is based on [30], it achieves compact master keys⁵ and does not require random oracles. We get the following concrete HKIBE schemes with new features from the second construction.

• The first (almost) tightly and adaptively secure HKIBE scheme with compact master keys from the k-linear assumption in the standard model from [36, 37].

• The first selectively secure HKIBE scheme with compact master keys from the various assumptions in the standard model: the learning with errors [4, 16]; learning from parity with noise [14]; computational Diffie-Hellman without pairing; and factoring Blum integers [22].

Achieving CCA security Although we basically consider CPA-secure HKIBE schemes, we can easily extend them to CCA-secure schemes as follows. The first construction can be lifted to a CCA-secure scheme by just replacing the underlying CPA-secure HIBE scheme with a CCA-secure one. Note that since there is a well-known transformation [11] from CPA-secure HIBE schemes to CCA-secure ones that preserve almost the same efficiency, the CCA-secure version of our first construction achieves similar efficiency to the CPA-secure construction. Unlike the first constrution, we obtain a CCA-secure version of our second construction by applying the transformation technique to multiple ciphertexts of the underlying CPA-secure HIBE scheme at once, not each of them. Note that as observed in the HHSI05 paper [30], it is also applicable to their scheme.

Efficiency comparison We compare our constructions with previous schemes. Table 1 provides efficiency comparisons between Hanaoka et al.’s generic construction [30] and our constructions. Our first construction preserves all parameter sizes of the underlying HIBE scheme. Our second construction has similar efficiency to the HHSI05 scheme but achieves constant-size master keys. Although our first construction, which is more efficient than others, requires the special property for the underlying HIBE scheme and the factor Q, which is the number of queries in the HKIBE security game, for its security reduction, our second construction requires neither of them. Table 2 shows concrete efficiency among existing schemes and instantiations of our first construction, which is more efficient than our second construction. The state-of-the-art pairing-based HIBE schemes [17, 18, 28] provide efficient HKIBE schemes. In particular, the instantiation of the first construction from [17, 18] is CPA-secure under the k-linear assumption and achieves the same efficiency as the SW18 scheme [52] when setting $k=1$, i.e., the symmetric external Diffie-Hellman (SXDH) assumption. We again would like to emphasize that the security proof in [52] was flawed. Furthermore, the first scheme can be easily extended to CCA-security by replacing the underlying CPA-secure HIBE scheme with CCA-secure one. Note that, as we noted above, we know the transformation [11] for HIBE that lifts CPA security to CCA security without sacrificing efficiency.

Table 2 A comparison among previous CCA-secure instantiations and the CCA-secure version of our first construction.

1.3 Related work

The notion of key-insulated cryptography was first introduced by Dodis et al. [20]. Specifically, they formalized two kinds of key-insulated security notions: the one is weak security, which only satisfies the condition (1) described earlier; the other is strong security, which satisfies both (1) and (2). Bellare and Palacio [7] showed that weakly secure key-insulated public-key encryption is equivalent to (a restricted form of) IBE. Thus far, the key-insulated security have been considered in the IBE setting (with additional properties) [58, 59]. The key-insulation structure was extended to the hierarchical one by Hanaoka et al. [30], where the security captures the strong security, and they proposed an adaptively secure HKIBE scheme both with and without random oracles. Watanabe and Shikata [55] proposed an adaptively secure HKIBE scheme with compact ciphertexts and decryption keys. Later, the same authors [52] found out a bug in the security proof in [55] and fixed it and the corresponding construction. However, it contains another bug in their security proof, and our proposal fixes it as mentioned earlier.

Another key-updating approach is forward security [15], which guarantees that even if the secret key is leaked, no information of previously-encrypted plaintexts is leaked by updating the secret key by themselves. However, it is inapplicable to the IoT scenario since it only prevents the leakage of data previously encrypted before the key leakage, and the exposed secret keys will not be able to be used.

R(H)IBE [9, 49] is (H)IBE with efficient revocation functionality, and has a similar key-updating procedure and security notion to HKIBE. Each user needs to periodically update their decryption key, and the update is successful unless the user is revoked. In the security game, an adversary is allowed to get some decryption keys associated with a challenge identity. A lot of constructions have been proposed in the context of RIBE [9, 26, 32, 38, 39, 45, 50, 54] and RHIBE [23, 24, 34, 40, 47, 49, 51, 53] thus far.

Organization In Sect. 2, we briefly review hierarchical time-period map functions, which make us consistently deal with several layers of time periods in HKIBE, and HIBE with MSK evaluatability. We give the definition of HKIBE in Sect. 3, and show our two generic constructions in Sects. 4 and 5, respectively.

2 Preliminaries

2.1 Notations

Let $\mathbb {N}$ be the set of all natural numbers. For non-negative integers $a,b \in \mathbb {N}$ with $a \le b$, we define $[a,b] :=\{a, a+1,\dots , b\}$ and $[a] :=[1,a]$. As a special case, $[a,b]=\emptyset$ for $a>b$. For a finite set S, let $x \leftarrow _RS$ denote sampling x from S uniformly at random. For a $\kappa _1$-bit binary string ${\texttt {id}}_1 \in \{0,1\}^{\kappa _1}$ and a $\kappa _2$-bit binary string ${\texttt {id}}_2 \in \{0,1\}^{\kappa _2}$, let ${\texttt {id}}_1 \Vert {\texttt {id}}_2 \in \{0,1\}^{\kappa _1+\kappa _2}$ denote a $(\kappa _1+\kappa _2)$-bit concatenation of ${\texttt {id}}_1$ and ${\texttt {id}}_2$.

2.2 Hierarchical time-period map functions

To properly deal with key-updating functionality, we consider (discrete) time periods, which are time spans during which a specific secret key is authorized for cryptographic operations such as decryption or in which the secret keys may remain in effect. Let $\mathcal {T}$ be a set of time periods. It is natural to consider that such a time period for key updates is related to actual time, i.e., clock time that we usually use in our daily lives. For instance, we can set a set of time periods $\mathcal {T}$ as days, say, $\mathcal {T}:=\{ \texttt {2020\_Sep\_1},\texttt {2020\_Sep\_2},\ldots \}$. To connect time periods and actual time, we consider time-period map functions [30]. A time-period map function $\textsf {T}: \mathcal {T}_{act}\rightarrow \mathcal {T}$ maps actual times to time periods, where $\mathcal {T}_{act}$ is a (possibly countably infinite) set of actual times.

Time-period map functions can be extended so that they have a certain hierarchical structure. Let $L:=\textsf {poly}( \lambda )$, and $\mathcal {T}_\ell$ for $\ell \in [0, L]$ be a finite set of time periods. We assume $|\mathcal {T}_L| \le \cdots \le |\mathcal {T}_1| \le | \mathcal {T}_{0}|$ and $|\mathcal {T}_L|=1$ (i.e., for any ${\texttt {t}}$) for simplicity. The reason why we consider several layers of time periods is that in HKIBE, we consider several secret keys, called helper keys for $\mathcal {T}_L,\ldots ,\mathcal {T}_{1}$ and decryption keys for $\mathcal {T}_0$. More specifically, we consider different time intervals for the helper and decryption keys; the helper key at the highest level (i.e., $\mathcal {T}_{L}$) is never updated, and other helper keys are more frequently updated as the level decreases. The decryption key, which is related to $\mathcal {T}_0$, is most often updated. The hierarchical version of time-period map functions for the depth L captures this situation, and can be defined as a set of L time-period map functions $\textsf {T}_L,\ldots ,\textsf {T}_1,\textsf {T}_{0}$ for distinct time-period sets $\mathcal {T}_L,\ldots ,\mathcal {T}_1,\mathcal {T}_{0}$. We use the hierarchical time-period map functions to manage several time periods consistently; one actual time ${\texttt {t}}\in \mathcal {T}_{act}$ produces an $(L+1)$-dimensional time-period vector $(t_{L},\ldots ,t_1,t_{0}) \in \mathcal {T}_{L} \times \cdots \times \mathcal {T}_1 \times \mathcal {T}_{0}$ via the functions $\textsf {T}_{L},\ldots ,\textsf {T}_1,\textsf {T}_{0}$. Let us give an example for readers: for $L=3$ and ${\texttt {t}}=\texttt {2020\_Sep\_10\_23:59}$, we have , $\textsf {T}_{ 2 }({\texttt {t}})=\texttt {2020}$, , and . $\textsf {T}_3$ in this example indicates “no update”, and $\textsf {T}_2$, $\textsf {T}_1$, and $\textsf {T}_0$ capture yearly, monthly, and daily updates, respectively. For notational convenience, we use a shortened form of time-period vectors for ${\texttt {t}}\in \mathcal {T}_{act}$: , where $\ell \in [0,L-1]$.⁶ Note that the order of $[\cdot ]$ of $\textsf {T}_{[\cdot ]}(\cdot )$ is reversed compared with the order of $[\cdot ]$ defined in Sect. 2.1.

2.3 HIBE

Hierarchical identity Let an $\ell$-dimensional identity vector ${\texttt {ID}}_{\ell } :=({\texttt {id}}_1,\ldots ,{\texttt {id}}_{\ell })$ denote an identity at a level (or, a hierarchy depth) $\ell$. In this paper, we may sometimes call ${\texttt {ID}}_{\ell } = ({\texttt {id}}_1,\ldots , {\texttt {id}}_{\ell })$ and each ${\texttt {id}}_i$ a hierarchical identity and an element identity, respectively. Let $\mathcal {I}$ be an element-identity space which is determined only by the security parameter $\lambda$, and therefore, a hierarchical-identity space at level $\ell$ is $\mathcal {I}^\ell$.

We define several notations for ${\texttt {ID}}_\ell = ({\texttt {id}}_1,\ldots , {\texttt {id}}_\ell )$ below. For a non-negative integer $k \le \ell$, an k-dimensional prefix of ${\texttt {ID}}_\ell$ is denoted by $\mathtt {ID}_{[k]} :=({\texttt {id}}_1, \ldots ,{\texttt {id}}_k)$. We denote by $\textsf {prefix}^+( {\texttt {ID}}_\ell ) :=\{\mathtt {ID}_{[1]}, \mathtt {ID}_{[2]}, \ldots , \mathtt {ID}_{[\ell -1]}, {\texttt {ID}}_\ell \}$ a set of all prefixes of ${\texttt {ID}}_\ell$ and itself. We often omit the subscript from ${\texttt {ID}}_\ell$ and simply describe ${\texttt {ID}}$ for simplicity, and use $|{\texttt {ID}}|:=\ell$ to denote a hierarchical level of the hierarchical identity.

Syntax An HIBE scheme $\Sigma$ with the depth L consists of four algorithms $(\textsf {Init}, \textsf {Enc}, \textsf {GenSK}, \textsf {Dec})$.

• $\textsf {Init}(1^{\lambda }, L) \rightarrow (\textsf {MPK}, \textsf {MSK})$: given the security parameter $\lambda$ and the maximum hierarchical depth L, it outputs a master-key pair $(\textsf {MPK},\textsf {MSK})$.

• $\textsf {Enc}(\textsf {MPK}, {\texttt {ID}}, \textsf {M}) \rightarrow \textsf {C}_{ {\texttt {ID}} }$: given $\textsf {MPK}$, user’s identity ${\texttt {ID}}\in \mathcal {I}^{|{\texttt {ID}}|}$, and a plaintext $\textsf {M}$, it outputs a ciphertext $\textsf {C}_{ {\texttt {ID}} }$.

• $\textsf {GenSK}(\textsf {MPK}, {\textsf {SK}}_{ {\texttt {ID}}' }, {\texttt {ID}}) \rightarrow {\textsf {SK}}_{ {\texttt {ID}} }$: given $\textsf {MPK}$, a user’s secret key ${\textsf {SK}}_{ {\texttt {ID}}' }$, and an identity ${\texttt {ID}}\in \mathcal {I}^{|{\texttt {ID}}|}$ s.t. ${\texttt {ID}}$’s parent is ${\texttt {ID}}'$, it outputs a secret key ${\textsf {SK}}_{ {\texttt {ID}} }$. The second input ${\textsf {SK}}_{ {\texttt {ID}}' }$ can be replaced by $\textsf {MSK}$. For notational convenience, we regard ${\textsf {SK}}_{ {\texttt {ID}}_0 }$ as the master secret key (MSK) $\textsf {MSK}$.

• $\textsf {Dec}(\textsf {MPK}, {\textsf {SK}}_{ {\texttt {ID}} }, \textsf {C}_{ {\texttt {ID}} }) \rightarrow \textsf {M}$: given $\textsf {MPK}$, a secret key ${\textsf {SK}}_{ {\texttt {ID}} }$, and a ciphertext $\textsf {C}_{ {\texttt {ID}} }$, it outputs the decryption result $\textsf {M}$.

Correctness We require that for all security parameters $\lambda \in \mathbb {N}$, hierarchy levels $L \in \mathbb {N}$, $(\textsf {MPK}, \textsf {MSK}) \leftarrow \textsf {Init}(1^{\lambda }, L)$, identities ${\texttt {ID}}\in \mathcal {I}^{|{\texttt {ID}}|}$, and plaintexts $\textsf {M}$, it holds $\textsf {Dec}(\textsf {MPK},{\textsf {SK}}_{ {\texttt {ID}} },\textsf {Enc}(\textsf {MPK},{\texttt {ID}},\textsf {M})) = \textsf {M}$ with overwhelming probability, where ${\textsf {SK}}_{ {\texttt {ID}} } \leftarrow \textsf {GenSK}(\textsf {MPK}, \textsf {MSK}, {\texttt {ID}})$. Moreover, given ${\textsf {SK}}_{ {{\texttt {ID}}'} }$ for any identity ${\texttt {ID}}\in \mathcal {I}^{|{\texttt {ID}}|}$, $\textsf {GenSK}(\textsf {MPK}, \textsf {MSK}, {\texttt {ID}})$ and $\textsf {GenSK}(\textsf {MPK}, {\textsf {SK}}_{ {\texttt {ID}}' }, {\texttt {ID}})$ s.t. ${\texttt {ID}}'\in \textsf {prefix}^+( {\texttt {ID}} )$ are identically distributed.

Adaptive security Intuitively, HIBE requires that it is hard for an adversary who adaptively obtains polynomially many secret keys ${\textsf {SK}}_{ {\texttt {ID}} }$ such that ${\texttt {ID}}\notin \textsf {prefix}^+( {\texttt {ID}}^\star )$ to extract secret information from $\textsf {C}_{ {\texttt {ID}}^\star }$.

More formally, let $\Sigma$ be an HIBE scheme, and we consider a game between an adversary $\mathcal {A}$ and the challenger ${\mathcal {C}}$. The game is parameterized by the security parameter $\lambda$ and the maximum hierarchical depth L. The game proceeds as follows: ${\mathcal {C}}$ first runs $(\textsf {MPK}, \textsf {MSK}) \leftarrow \textsf {Init}(1^{\lambda }, L)$ and gives $\textsf {MPK}$ to $\mathcal {A}$. $\mathcal {A}$ may adaptively make the following secret-key reveal query: upon a query ${\texttt {ID}}\in \mathcal {I}^{|{\texttt {ID}}|}$ from $\mathcal {A}$, ${\mathcal {C}}$ returns ${\textsf {SK}}_{ {\texttt {ID}} } \leftarrow \textsf {GenSK}(\textsf {MPK}, \textsf {MSK}, {\texttt {ID}})$ to $\mathcal {A}$. $\mathcal {A}$ is also allowed to make the following challenge query only once: upon a query $({\texttt {ID}}^\star , \textsf {M}^\star _0, \textsf {M}^\star _1)$ from $\mathcal {A}$ such that $|\textsf {M}^\star _0| = |\textsf {M}^\star _1|$, ${\mathcal {C}}$ returns $\textsf {C}_{ {\texttt {ID}}^\star }^\star \leftarrow \textsf {Enc}(\textsf {MPK}, {\texttt {ID}}^\star , \textsf {M}^\star _b)$ to $\mathcal {A}$, where $b \leftarrow _R\{0,1\}$. Note that $\mathcal {A}$ is not allowed to make the secret-key reveal query on ${\texttt {ID}}^\star$ and its prefix in this game. At some point, $\mathcal {A}$ outputs $b' \in \{0,1\}$ as its guess for b and terminates. In this game, $\mathcal {A}$’s adaptive security advantage is defined by $\textsf {Adv}^\mathtt{{HIBE}}_{\Sigma ,L,\mathcal {A}}(\lambda ) :=2 \cdot | \Pr [b' = b] - 1/2|$.

Definition 1

(CPA security for HIBE) We say that an HIBE scheme $\Sigma$ with depth L satisfies adaptive-identity CPA security (or adaptive security for brevity), if the advantage $\textsf {Adv}^\mathtt{{HIBE}}_{\Sigma ,L,\mathcal {A}}(\lambda )$ is negligible for all PPT adversaries $\mathcal {A}$.

The selective-identity CPA security (selective security for short) is analogously defined except that the challenge identity ${\texttt {ID}}^\star$ is submitted to ${\mathcal {C}}$ at the beginning of the game, instead of the challenge query. Furthermore, CCA security is also defined by allowing $\mathcal {A}$ to submit the following decryption query: upon a query $({\texttt {ID}},\textsf {C}_{ {\texttt {ID}} }) \ (\ne ({\texttt {ID}}^\star ,\textsf {C}_{ {\texttt {ID}}^\star }^\star ))$ from $\mathcal {A}$, ${\mathcal {C}}$ returns $\textsf {Dec}(\textsf {MPK}, {\textsf {SK}}_{ {\texttt {ID}} }, \textsf {C}_{ {\texttt {ID}} })$ to $\mathcal {A}$.

MSK evaluatability [24]. We require that an HIBE scheme used in our first construction satisfies the MSK evaluatability, which is a special algebraic property introduced in [24]. In the following, we use a notation ${\textsf {SK}}_{ {\texttt {ID}} } [ \textsf {MSK} ]$, instead of ${\textsf {SK}}_{ {\texttt {ID}} }$, to explicitly describe the MSK-part of ${\textsf {SK}}_{ {\texttt {ID}} }$, i.e., which element of $\mathcal {MSK}$ is used to compute ${\textsf {SK}}_{ {\texttt {ID}} }$.

Intuitively, MSK evaluatability has the following two properties.

• (1) Anyone can sample a random element ${\widehat{\textsf {MSK}}}\in \mathcal {MSK}$, called a pseudo-MSK, where $\mathcal {MSK}$ is a space of possible master secret keys. We describe the sampling procedure as a pseudo-MSK sampling algorithm $\textsf {SampMSK}$. Furthermore, anyone create secret keys ${\textsf {SK}}_{ {\texttt {ID}} } [ {\widehat{\textsf {MSK}}} ]$ for any ${\texttt {ID}}\in \mathcal {I}^{|{\texttt {ID}}|}$ under a pseudo-MSK ${\widehat{\textsf {MSK}}}$. This pseudo-MSK ${\widehat{\textsf {MSK}}}$ is, of course, different from the true MSK $\textsf {MSK}$ with overwhelming probability.⁷

• (2) Suppose that $\mathcal {MSK}$ has some algebraic structure and allows one to compute ${\widehat{\textsf {MSK}}}_1\cdot {\widehat{\textsf {MSK}}}_2$ and ${\widehat{\textsf {MSK}}}_1 / {\widehat{\textsf {MSK}}}_2$ for any ${\widehat{\textsf {MSK}}}_1,{\widehat{\textsf {MSK}}}_2 \in \mathcal {MSK}$. Note that ${\widehat{\textsf {MSK}}}_1$ and ${\widehat{\textsf {MSK}}}_2$ might be the true MSK. Let ${\textsf {SK}}_{ {\texttt {ID}} } [ {\widehat{\textsf {MSK}}}_1 ]$ and ${\textsf {SK}}_{ {\texttt {ID}} } [ {\widehat{\textsf {MSK}}}_2 ]$ be HIBE secret keys for the same identity ${\texttt {ID}}\in \mathcal {I}^{|{\texttt {ID}}|}$ but under ${\widehat{\textsf {MSK}}}_1$ and ${\widehat{\textsf {MSK}}}_2$, respectively. Then, there exists an efficient algorithm $\textsf {EvalMSK}$ which merges the two secret keys into one secret key ${\textsf {SK}}_{ {\texttt {ID}} } [ {\widehat{\textsf {MSK}}}_1 \cdot {\widehat{\textsf {MSK}}}_2 ]$ (resp., ${\textsf {SK}}_{ {\texttt {ID}} } [ {\widehat{\textsf {MSK}}}_1 / {\widehat{\textsf {MSK}}}_2 ]$) with a label $\mathtt {mul}$ (resp., $\mathtt {div}$).

Formally, MSK evaluatability is defined as follows.

Definition 2

(MSK Evaluatability [24]) Let $\Sigma$ be an HIBE scheme. We say that $\Sigma$ supports MSK evaluatability if there exist algorithms $\textsf {SampMSK}$ and $\textsf {EvalMSK}$:

• $\textsf {SampMSK}(\textsf {MPK}) \rightarrow {\widehat{\textsf {MSK}}}$: This is the pseudo-MSK sampling algorithm that, given $\textsf {MPK}$, outputs a pseudo-MSK ${\widehat{\textsf {MSK}}}\in \mathcal {MSK}$.

• $\textsf {EvalMSK}(\textsf {MPK}, {\textsf {SK}}_{ {\texttt {ID}} } [ {\widehat{\textsf {MSK}}}_1 ], {\textsf {SK}}_{ {\texttt {ID}} } [ {\widehat{\textsf {MSK}}}_2 ], \textsf {lab}) \rightarrow {\textsf {SK}}_{ {\texttt {ID}} } [ f_{\textsf {lab}}({\widehat{\textsf {MSK}}}_1, {\widehat{\textsf {MSK}}}_2) ]$: This is the MSK evaluation algorithm that, given two secret keys ${\textsf {SK}}_{ {\texttt {ID}} } [ {\widehat{\textsf {MSK}}}_1 ]$, ${\textsf {SK}}_{ {\texttt {ID}} } [ {\widehat{\textsf {MSK}}}_2 ]$ for the same ${\texttt {ID}}\in \mathcal {I}^{|{\texttt {ID}}|}$ under ${\widehat{\textsf {MSK}}}_1,{\widehat{\textsf {MSK}}}_2\in \mathcal {MSK}$, and a label $\textsf {lab}\in \{ \mathtt {mul}, \mathtt {div} \}$, it outputs a secret key ${\textsf {SK}}_{ {\texttt {ID}} } [ f_{\textsf {lab}}({\widehat{\textsf {MSK}}}_1, {\widehat{\textsf {MSK}}}_2) ]$, where $f_{\mathtt {mul}}({\widehat{\textsf {MSK}}}_1, {\widehat{\textsf {MSK}}}_2) = {\widehat{\textsf {MSK}}}_1 \cdot {\widehat{\textsf {MSK}}}_2$ and $f_{\mathtt {div}}({\widehat{\textsf {MSK}}}_1, {\widehat{\textsf {MSK}}}_2) = {\widehat{\textsf {MSK}}}_1 / {\widehat{\textsf {MSK}}}_2$.

Moreover, the following two requirements are satisfied:

$\triangleright$:

Pseudo-MSK indistinguishability For any $lab\in \{ \mathtt {mul}, \mathtt {div} \}$ and any ${\widehat{\textsf {MSK}}}\in \mathcal {MSK}$, given $\textsf {MPK}$ and ${\widehat{\textsf {MSK}}}$, the two distributions $\textsf {SampMSK}(\textsf {MPK})$ and $f_{\textsf {lab}}({\widehat{\textsf {MSK}}}, \textsf {SampMSK}(\textsf {MPK}))$ are identically distributed.

$\triangleright$:

Evaluation correctness For any $\textsf {lab}\in \{ \mathtt {mul},\mathtt {div} \}$, any ${\widehat{\textsf {MSK}}}_1,{\widehat{\textsf {MSK}}}_2 \in \mathcal {MSK}$, and any ${\texttt {ID}}\in \mathcal {I}^{|{\texttt {ID}}|}$, given $\textsf {MPK}$ and ${\textsf {SK}}_{ {\texttt {ID}} } [ {\widehat{\textsf {MSK}}}_1 ], {\textsf {SK}}_{ {\texttt {ID}} } [ {\widehat{\textsf {MSK}}}_2 ]$, the two distributions $\textsf {GenSK}(\textsf {MPK}, f_{\textsf {lab}}({\widehat{\textsf {MSK}}}_1, {\widehat{\textsf {MSK}}}_2), {\texttt {ID}})$ and $\textsf {EvalMSK}(\textsf {MPK}, {\textsf {SK}}_{ {\texttt {ID}} } [ {\widehat{\textsf {MSK}}}_1 ], {\textsf {SK}}_{ {\texttt {ID}} } [ {\widehat{\textsf {MSK}}}_2 ], \textsf {lab})$ are identically distributed.

Note that most pairing-based HIBE schemes can satisfy MSK evaluatability. For example, as noted in [24], several state-of-the-art pairing-based HIBE schemes [17, 18, 28] have this property. Let us give an intuition with the following abstract example. Let $\mathbb {G}_1$, $\mathbb {G}_2$, and $\mathbb {G}_T$ be cyclic groups (group operations in all are written in multiplicative forms) of prime-order p, and $e: \mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T$ be a non-degenerate bilinear map. We use the implicit notation [25]: for $a\in \mathbb {Z}_p$ and generators $g_i \in \mathbb {G}_i \ (i \in \{ 1,2,T \})$, $[a]_i :=g_i^a \in \mathbb {G}_i$, and for a vector $\mathbf {a}:=(a_1,\ldots , a_d) \in \mathbb {Z}_p^{ d}$, $[\mathbf {a}]_i:=([a_1]_i,\ldots ,[a_d]_i) \in \mathbb {G}_i^{ d}$. In several pairing-based HIBE schemes based on the k-linear assumption (e.g., [17, 18]), the MSK is in the form of $[\mathbf {k}]_2 \in \mathbb {G}_2^{k+1}$ and the secret key ${\textsf {SK}}_{ {\texttt {ID}} } [ \textsf {MSK} ]$ contains $[\mathbf {k}]_2 \cdot \textsf {F}({\texttt {ID}})^r$, where $\textsf {F}: \mathcal {I}\rightarrow \mathbb {G}_2^{k+1}$ is a certain public function and $r\in \mathbb {Z}_p$ is a randomness. It is obvious that since anyone can compute a pseudo-MSK ${\widehat{\textsf {MSK}}}:=[{\widehat{\mathbf {k}}}]_2$ for uniformly sampled ${\widehat{\mathbf {k}}}\in \mathbb {Z}_p^{k+1}$, there exists the $\textsf {SampMSK}$ algorithm. Moreover, it clearly satisfies pseudo-MSK indistinguishability since even given $[\mathbf {k}]_2$, $[\mathbf {k}]_2 \cdot [{\widehat{\mathbf {k}}}]_2 = [\mathbf {k}+{\widehat{\mathbf {k}}}]_2$ (or $[\mathbf {k}]_2 / [{\widehat{\mathbf {k}}}]_2 = [\mathbf {k}-{\widehat{\mathbf {k}}}]_2$) and $[{\widehat{\mathbf {k}}}]_2$ are identically distributed. Furthermore, it is easy to confirm that it also provides $\textsf {EvalMSK}$: for any ${\widehat{\textsf {MSK}}}_1 :=[{\widehat{\mathbf {k}}}_1]_2,{\widehat{\textsf {MSK}}}_2 :=[{\widehat{\mathbf {k}}}_2]_2 \in \mathbb {G}_2^{k+1}$, the corresponding component of ${\textsf {SK}}_{ {\texttt {ID}} } [ {\widehat{\textsf {MSK}}}_1 \cdot {\widehat{\textsf {MSK}}}_2 ]$ can be computed as $([{\widehat{\mathbf {k}}}_1]_2 \cdot \textsf {F}({\texttt {ID}})^{r_1}) \cdot ([{\widehat{\mathbf {k}}}_2]_2 \cdot \textsf {F}({\texttt {ID}})^{{r_2}}) = [{\widehat{\mathbf {k}}}_1+{\widehat{\mathbf {k}}}_2]_2 \cdot \textsf {F}({\texttt {ID}})^{r_1+r_2}$ (other components can be computed in a similar way). It is clear that the component $[{\widehat{\mathbf {k}}}_1+{\widehat{\mathbf {k}}}_2]_2 \cdot \textsf {F}({\texttt {ID}})^{r_1+r_2}$ is identically distributed to a secret key directly computed by $\textsf {GenSK}$ with ${\widehat{\textsf {MSK}}}_1\cdot {\widehat{\textsf {MSK}}}_2$.⁸ Hence, it satisfies evaluation correctness. We omit the case of the division since it is straightforward.

On the other hand, it seems difficult for HIBE schemes over pairing-free groups [21] and lattice-based HIBE schemes [4, 5, 16] to satisfy MSK evaluatability since they do not have such a simple algebraic structure.

3 HKIBE

We review a definition of HKIBE based on [30, 52, 55] which present the most strict security model. Please keep in mind that an identity ${\texttt {id}}\in \mathcal {I}$ in HKIBE is always a (non-hierarchical) one-dimensional vector.

3.1 Model

There are two types of keys, i.e., helper keys and decryption keys, and they depend on an identity ${\texttt {id}}$ and each of the hierarchical time periods $\mathcal {T}_L,\ldots ,\mathcal {T}_0$. Every user ${\texttt {id}}$ has a level-$\ell$ helper key for $\ell = 1,2,\ldots ,L$ and a decryption key . The upper level-$(\ell +1)$ helper key can derive a level-$\ell$ key update for updating the lower level-$\ell$ helper key to be . Similarly, the decryption key is updated by using a key update derived from a level-1 helper key. A ciphertext of HKIBE depends on a receiver’s identity ${\texttt {id}}\in \mathcal {I}$ and actual time ${\texttt {t}}\in \mathcal {T}_{act}$, and can be decrypted by a decryption key $\textsf {dk}_{{\texttt {id}}, \textsf {T}_{0}({\texttt {t}}')}$ if .

Specifically, HKIBE consists of six algorithms $(\textsf {Setup}, \textsf {Encrypt}, \textsf {GenHK}, \textsf {KeyUp}, \textsf {Upd}, \textsf {Decrypt})$ and proceeds as follows. First of all, the key generation center (KGC) runs $\textsf {Setup}$ to generate a master-key pair $({\textsf {pp}},{\textsf {mk}})$. Upon a request from a user ${\texttt {id}}$, the KGC runs $\textsf {GenHK}$ to get a set of initial helper keys as a secret key for ${\texttt {id}}$. Suppose that each helper key is stored in a different (physically-secure) device. The level-0 helper key is used as a decryption key, and we often write it as $\textsf {dk}_{{\texttt {id}}, t_0}$. A plaintext $\textsf {M}$ is encrypted by $\textsf {Encrypt}$ with not only an identity ${\texttt {id}}$ but (current) time ${\texttt {t}}$. The resulting ciphertext, which is denoted by , can be decrypted by $\textsf {Decrypt}$ with ${\texttt {id}}$’s decryption key if and only if . Here, we describe how to update helper and decryption keys as follows. Suppose that the user ${\texttt {id}}$ has and wants to update it for ${\texttt {t}}$. The level-L helper key is never updated, and therefore, for any ${\texttt {t}}\in \mathcal {T}_{act}$. For every $\ell = L-1,\ldots ,0$, the user ${\texttt {id}}$ first runs $\textsf {KeyUp}$ to generate ${\texttt {id}}$’s level-$\ell$ key update by running $\textsf {KeyUp}$ with . The user then runs $\textsf {Upd}$ with the key update to update ${\texttt {id}}$’s level-$\ell$ helper key to . At the end of this updating procedure, the user obtains a decryption key .

Syntax An HKIBE scheme consists of the six algorithms $(\textsf {Setup}, \textsf {Encrypt}, \textsf {GenHK}, \textsf {KeyUp}, \textsf {Upd}, \textsf {Decrypt})$ defined as follows:

• $\textsf {Setup}(1^{\lambda }, L) \rightarrow ({\textsf {pp}}, {\textsf {mk}})$: This is the setup algorithm that, given the security parameter $\lambda$ and the maximum depth of the hierarchy $L \in \mathbb {N}$, it outputs a master-key pair $({\textsf {pp}},{\textsf {mk}})$.

• : This is the encryption algorithm that, given ${\textsf {pp}}$, an element identity ${\texttt {id}}\in \mathcal {I}$, current time ${\texttt {t}}\in \mathcal {T}_{act}$, and a plaintext $\textsf {M}\in \mathcal {M}$, it outputs a ciphertext .

• : This is the helper-key generation algorithm that, given ${\textsf {pp}}$, ${\textsf {mk}}$, and an element identity ${\texttt {id}}\in \mathcal {I}$, it outputs a set of initial helper keys . The level-0 helper key is also called a decryption key and set as .

• or $\bot$: This is the key update information generation algorithm that, given ${\textsf {pp}}$, actual time ${\texttt {t}}\in \mathcal {T}_{act}$, and an ${\texttt {id}}$’s level-$(\ell +1)$ helper key at a time period $t_{\ell +1} \in \mathcal {T}_{\ell +1}$, it outputs an ${\texttt {id}}$’s level-$\ell$ key update at a time period if . Otherwise, it outputs $\bot$.

• : This is the helper key update algorithm that, given ${\textsf {pp}}$, an ${\texttt {id}}$’s level-$\ell$ helper key at a time period $\tau _\ell \in \mathcal {T}_\ell$, and an ${\texttt {id}}$’s level-$\ell$ key update $\textsf {ku}_{{\texttt {id}}, t_\ell }^{( \ell )}$ at a time period $t_\ell \in \mathcal {T}_\ell$, it outputs an updated helper key at a time period $t_\ell$.

• or $\bot$: This is the decryption algorithm that, given ${\textsf {pp}}$, an ${\texttt {id}}$’s decryption key $\textsf {dk}_{{\texttt {id}}, t_0}$ at a time period $t_0 \in \mathcal {T}_0$, and a ciphertext , it outputs $\textsf {M}$ or $\bot$ which indicates decryption failure.

Remark 1

(Update Frequency) For simplicity, we assume that the lower-level helper key is more frequently updated than the upper-level helper key. Namely, several level-$\ell$ helper keys $\textsf {hk}_{{\texttt {id}}, \textsf {T}_{\ell }({\texttt {t}}^{(1)}) }^{( \ell )}, \ldots , \textsf {hk}_{{\texttt {id}}, \textsf {T}_{\ell }({\texttt {t}}^{(m)}) }^{( \ell )}$ are updated by the same level-$(\ell +1)$ helper key $\textsf {hk}_{{\texttt {id}}, t }^{( \ell +1 )}$, where ${\texttt {t}}^{(1)}, \ldots ,{\texttt {t}}^{(m)} \in \mathcal {T}_{act}$ and $t=\textsf {T}_{\ell +1}({\texttt {t}}^{(1)}) = \cdots = \textsf {T}_{\ell +1}({\texttt {t}}^{(m)})$. This assumption of use frequency captures actual situations: the upper level of helper keys is, the more rarely they should be used, i.e., the more isolated they should be from the Internet.

Correctness We require a ciphertext associated with $({\texttt {id}}, {\texttt {t}})$ to be properly decrypted by a decryption key $\textsf {dk}_{{\texttt {id}}, t_0}$ for the same ${\texttt {id}}$ and if $\textsf {dk}_{{\texttt {id}}, t_0}$ is correctly generated from any updating path.

More formally, for all security parameter $1^\lambda$, all hierarchical depth $L \in \mathbb {N}$, all $({\textsf {pp}}, {\textsf {mk}}) \leftarrow \textsf {Setup}(1^\lambda , L)$, all $\textsf {M}\in \mathcal {M}$, all ${\texttt {id}}\in \mathcal {I}$, and all sequence $({\texttt {t}}_1,\ldots , {\texttt {t}}_n) \in \mathcal {T}_{act}^{n}$ for arbitrary number $n = \textsf {poly}( \lambda )$, we consider the following experiment:

• $\textsf {ct}_{ {\texttt {id}}, {\texttt {t}}_n} \leftarrow \textsf {Encrypt}({\textsf {pp}}, {\texttt {id}}, {\texttt {t}}_n, \textsf {M})$.

• $( \textsf {hk}_{{\texttt {id}}, 0 }^{( \ell )} )_{\ell \in [0,L]} \leftarrow \textsf {GenHK}({\textsf {pp}}, {\textsf {mk}}, {\texttt {id}})$.

• Let ${\texttt {t}}_0 :=0$ for simplicity. For all $j = 1,2,\ldots , n$, execute the following procedures for $\ell = L-1, L-2, \ldots , 0$:

  • $\textsf {ku}_{{\texttt {id}}, \textsf {T}_{\ell }({\texttt {t}}_j) }^{( \ell )} \leftarrow \textsf {KeyUp}({\textsf {pp}}, {\texttt {t}}_j, \textsf {hk}_{{\texttt {id}}, \textsf {T}_{\ell +1}({\texttt {t}}_j) }^{( \ell +1 )})$.

  • $\textsf {hk}_{{\texttt {id}}, \textsf {T}_\ell ({\texttt {t}}_j) }^{( \ell )} \leftarrow \textsf {Upd}({\textsf {pp}}, \textsf {hk}_{{\texttt {id}}, \textsf {T}_\ell ({\texttt {t}}_{j-1}) }^{( \ell )}, \textsf {ku}_{{\texttt {id}}, \textsf {T}_\ell ({\texttt {t}}_j) }^{( \ell )})$.

• $\textsf {M}' \leftarrow \textsf {Decrypt}({\textsf {pp}}, \textsf {dk}_{{\texttt {id}}, \textsf {T}_0({\texttt {t}}_n)}, \textsf {ct}_{ {\texttt {id}}, {\texttt {t}}_n})$.

Definition 3

(Correctness) We say that an HKIBE scheme $\Pi$ with depth L satisfies correctness, if the probability $\textsf {M}' = \textsf {M}$ in the above experiment holds with overwhelming probability.

3.2 Security

Let $\Pi$ be an HKIBE scheme. We consider the adaptive-identity CPA security for HKIBE (the adaptive security for short), which is defined via a game between an adversary $\mathcal {A}$ and the challenger ${\mathcal {C}}$. The game is parameterized by the security parameter $\lambda$ and the maximum hierarchical depth $L \in \mathbb {N}$. Intuitively, $\mathcal {A}$ is able to receive all helper keys as long as they are insufficient for deriving a decryption key $\textsf {dk}_{ {\texttt {id}}^\star , {\texttt {t}}^\star }$ for the target tuple $({\texttt {id}}^\star , {\texttt {t}}^\star )$. The game proceeds as follows:

${\mathcal {C}}$ first runs $({\textsf {pp}}, {\textsf {mk}}) \leftarrow \textsf {Setup}(1^{\lambda }, L)$ and gives ${\textsf {pp}}$ to $\mathcal {A}$. ${\mathcal {C}}$ prepares $\mathtt {HKList}$ and stores all identity/initial helper keys $({\texttt {id}}, ( \textsf {hk}_{{\texttt {id}}, 0 }^{( \ell )} )_{\ell \in [0,L]})$ generated during the game in $\mathtt {HKList}$ while we will not explicitly mention this procedure.

$\mathcal {A}$ may adaptively make the following four types of queries to ${\mathcal {C}}$:

• Helper-key generation query Upon a query ${\texttt {id}}\in \mathcal {I}$ from $\mathcal {A}$, ${\mathcal {C}}$ checks if $({\texttt {id}}, *) \notin \mathtt {HKList}$, and returns $\bot$ to $\mathcal {A}$ if this is not the case. Otherwise, ${\mathcal {C}}$ executes $( \textsf {hk}_{{\texttt {id}}, 0 }^{( \ell )} )_{\ell \in [0,L]} \leftarrow \textsf {GenHK}({\textsf {pp}}, {\textsf {mk}}, {\texttt {id}})$ and returns nothing to $\mathcal {A}$.

  We require that all identities ${\texttt {id}}$ appearing in the following queries (except the challenge query) are “activated”, in the sense that $( \textsf {hk}_{{\texttt {id}}, 0 }^{( \ell )} )_{\ell \in [0, L]}$ is generated via this query and hence $({\texttt {id}}, ( \textsf {hk}_{{\texttt {id}}, 0 }^{( \ell )} )_{\ell \in [0, L]}) \in \mathtt {HKList}$.

• Initial helper-key reveal query Until the challenge query, upon a query ${\texttt {id}}\in \mathcal {I}$ from $\mathcal {A}$, ${\mathcal {C}}$ finds $( \textsf {hk}_{{\texttt {id}}, 0 }^{( \ell )} )_{\ell \in [0, L]}$ from $\mathtt {HKList}$ and returns $( \textsf {hk}_{{\texttt {id}}, 0 }^{( \ell )} )_{\ell \in [0, L]}$ to $\mathcal {A}$. After the challenge query, ${\mathcal {C}}$ checks whether ${\texttt {id}}\ne {\texttt {id}}^\star$ and returns $\bot$ if this is not the case. Otherwise, ${\mathcal {C}}$ returns $( \textsf {hk}_{{\texttt {id}}, 0 }^{( \ell )} )_{\ell \in [0, L]}$ to $\mathcal {A}$ in the same way.

• Key-insulation query Until the challenge query, upon a query $({\texttt {id}}, {\texttt {t}}, \ell ) \in \mathcal {I}\times \mathcal {T}_{act}\times [0,L]$ from $\mathcal {A}$, ${\mathcal {C}}$ finds $( \textsf {hk}_{{\texttt {id}}, 0 }^{( \ell )} )_{\ell \in [0,L]}$ from $\mathtt {HKList}$ and runs

• ,

• ,

for $i = L-1,\ldots ,\ell$ to obtain . Then, ${\mathcal {C}}$ returns to $\mathcal {A}$. After the challenge query, when ${\texttt {id}}= {\texttt {id}}^\star$, ${\mathcal {C}}$ checks whether there exists the following special hierarchical level $\ell ^\star$ after answering the query:

• (i) $\textsf {hk}_{ {\texttt {id}}^\star , t_{\ell ^\star } }^{( \ell ^\star )}$ of any $t_{\ell ^\star } \in \mathcal {T}_{\ell ^\star }$ are not revealed to $\mathcal {A}$. Namely, no level-$\ell ^\star$ helper keys have been revealed to $\mathcal {A}$ ever.

• (ii) For all $i \in [0, \ell ^\star -1]$ and all ${\texttt {t}}\in \mathcal {T}_{act}$ such that holds, are not revealed to $\mathcal {A}$.

If this is not the case, ${\mathcal {C}}$ returns $\bot$ to $\mathcal {A}$. Otherwise, ${\mathcal {C}}$ returns to $\mathcal {A}$ in the same way.

Challenge query $\mathcal {A}$ is allowed to make this query only once. Upon a query $({\texttt {id}}^\star , {\texttt {t}}^\star , \textsf {M}^\star _0, \textsf {M}^\star _1)$ from $\mathcal {A}$ such that $|\textsf {M}^\star _0| = |\textsf {M}^\star _1|$, ${\mathcal {C}}$ checks whether the following conditions simultaneously hold:

• $\mathcal {A}$ does not make the initial helper-key reveal query on ${\texttt {id}}^\star$.

• There is a special hierarchical level $\ell ^\star$ as explained in the key-insulation query.

If the conditions are not simultaneously satisfied, ${\mathcal {C}}$ returns $\bot$ to $\mathcal {A}$. Otherwise, ${\mathcal {C}}$ picks a bit $b \in \{0,1\}$ uniformly at random, runs $\textsf {ct}_{ {\texttt {id}}^\star ,{\texttt {t}}^\star }^\star \leftarrow \textsf {Encrypt}({\textsf {pp}}, {\texttt {id}}^\star , {\texttt {t}}^\star , \textsf {M}^\star _b)$, and returns the challenge ciphertext $\textsf {ct}_{ {\texttt {id}}^\star ,{\texttt {t}}^\star }^\star$ to $\mathcal {A}$.

At some point, $\mathcal {A}$ outputs $b' \in \{0,1\}$ as its guess for b and terminates.

The above completes the description of the game. In this game, $\mathcal {A}$’s adaptive security advantage is defined by $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda ) :=2 \cdot | \Pr [b' = b] - 1/2|$.

Definition 4

([30]) We say that an HKIBE scheme $\Pi$ with depth L satisfies adaptive-identity CPA security (or adaptive security for brevity), if the advantage $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )$ is negligible for all PPT adversaries $\mathcal {A}$.

Why we need the restrictions We briefly explain the restrictions $\mathrm (i)$ and $\mathrm (ii)$ appeared in key-insulation query, i.e., why we need the special hierarchical level $\ell ^\star$. To define as strong security as possible while preventing trivial attacks, we should allow $\mathcal {A}$ to make as many queries as possible unless $\mathcal {A}$ can trivially create $\textsf {dk}_{ {\texttt {id}}^\star ,\textsf {T}_{0}({\texttt {t}}^\star ) }$. As for the restriction $\mathrm (i)$, if at least one level-i helper key for ${\texttt {id}}^\star$ is leaked at every level $i\in [0,L]$, it also means that $\mathcal {A}$ can create all decryption keys including $\textsf {dk}_{ {\texttt {id}}^\star ,\textsf {T}_{0}({\texttt {t}}^\star ) }$. As for the restriction $\mathrm (ii)$, suppose that for some $i \in [0,\ell ^\star -1]$, $\mathcal {A}$ gets $( \textsf {hk}_{ {\texttt {id}}^\star , \textsf {T}_{j}({\texttt {t}}_j) }^{( j )} )_{j\in [0,i-1]}$ such that $\textsf {T}_{j}({\texttt {t}}_j) \ne \textsf {T}_{j}({\texttt {t}}^\star )$ for $j \in [0,i-1]$ via key-insulation queries. Then, one helper key such that is enough for $\mathcal {A}$ to compute a decryption key $\textsf {dk}_{ {\texttt {id}}^\star ,\textsf {T}_{0}({\texttt {t}}^\star ) }$ even if $\mathcal {A}$ has no level-$\ell ^\star$ helper key for any ${\texttt {t}}\in \mathcal {T}_{act}$. Hence, we need the restriction about the special level $\ell ^\star$ to the key-insulation query for ${\texttt {id}}^\star$. For the same reason, we, of course, disallow $\mathcal {A}$ to make the initial helper-key reveal query for ${\texttt {id}}^\star$.

Selective security and CCA security The selective-identity CPA security is analogously defined. The only exception is that $\mathcal {A}$ should send a challenge identity and time $({\texttt {id}}^\star , {\texttt {t}}^\star )$ to ${\mathcal {C}}$ before receiving a master public key ${\textsf {pp}}$. Moreover, CCA security is also defined by allowing $\mathcal {A}$ to submit the following decryption query: upon a query from $\mathcal {A}$, ${\mathcal {C}}$ returns to $\mathcal {A}$.

Remark 2

(Weak vs. strong security) The security defined above is referred to as the strong security [20, 30], which is the standard security requirement in key-insulated cryptography in the sense that $\mathcal {A}$ is allowed to get helper keys at a higher level than the special level $\ell ^\star$. In the weak security definition, the special level $\ell ^\star$ turns to the threshold level $\ell ^\star$. Namely, $\mathcal {A}$ cannot get any helper keys at level $\ell \in [\ell ^\star ,L]$. As we claimed earlier, Bellare and Palacio’s work [7] implies that any HIBE scheme can be transformed into an HKIBE scheme with weak security.

Remark 3

(A variant of security definition) One may consider a stronger variant of our security definition so that $\mathcal {A}$ can designate a derivation path of helper keys with a key-insulation query on $({\texttt {id}},{\texttt {t}},\ell )$; that is, $\mathcal {A}$ is allowed to designate how the helper key is derived. Since such a strong notion makes formalization complicated, we do not consider it for simplicity. Nevertheless, our constructions satisfy such a strong definition.

4 Generic construction from HIBE with MSK evaluatability

We propose a generic construction of an HKIBE scheme with key-insulation depth L from an HIBE scheme with identity depth $L+1$ supporting MSK evaluatability. We assume that $\mathcal {I}, \mathcal {T}_0, \ldots , \mathcal {T}_{L} \subseteq \mathcal {I}_{\textsc {hibe}}$ holds, where $\mathcal {I}_{\textsc {hibe}}$ is an element identity space of HIBE.

Fig. 1

The intuition of our first construction

4.1 Construction idea

The basic idea is quite simple: to encrypt a message $\textsf {M}$ with an identity ${\texttt {id}}$ and time ${\texttt {t}}$, run the HIBE encryption algorithm $\textsf {Enc}$ with $\textsf {M}$ and a hierarchical identity (i.e., ). Therefore, to make the decryption procedure consistent, we set a decryption key . However, if we set each helper key similarly, the resultant construction is the same as Bellare and Palacio’s transformation [7] mentioned in Remark 2; it does not achieve strong security. Our construction’s core spirit is that we use L pseudo-MSKs ${\widehat{\textsf {MSK}}}_{{\texttt {id}},0},\ldots ,{\widehat{\textsf {MSK}}}_{{\texttt {id}},L-1}$ to mask the highest-level helper key and gradually remove them with $\textsf {EvalMSK}$ as the hierarchy of key-insulation levels is lowered.⁹ More specifically, when executing $\textsf {GenHK}$ with any ${\texttt {id}}$, we mask the true MSK $\textsf {MSK}$ with all the pseudo-MSKs ${\widehat{\textsf {MSK}}}_{{\texttt {id}},0},\ldots ,{\widehat{\textsf {MSK}}}_{{\texttt {id}},L-1}$ (in the fraction form) and set the highest-level helper key $\textsf {hk}_{{\texttt {id}}, 0 }^{( L )}$ as ${\textsf {SK}}_{ {\texttt {id}} } [ \textsf {MSK}/ \prod _{i=0}^{L-1} {\widehat{\textsf {MSK}}}_{{\texttt {id}},i} ]$. Besides, for every $\ell \in [0,L-1]$, an level-$\ell$ helper key $\textsf {hk}_{{\texttt {id}}, t_\ell }^{( \ell )}$ contains the pseudo-MSK ${\widehat{\textsf {MSK}}}_{{\texttt {id}}, \ell }$ and is updated in the following two steps.

• (1) Run $\textsf {GenSK}$ with its higher-level helper key to obtain .

• (2) Run $\textsf {EvalMSK}$ with the obtained key , the level-$\ell$ pseudo-MSK ${\widehat{\textsf {MSK}}}_{{\texttt {id}}, \ell }$, and $\textsf {lab}= \mathtt {mul}$ to get , which is set as an updated level-$\ell$ helper key .

In the end, the mask is entirely removed at the lowest level, i.e., . We illustrate the idea in Fig. 1. As can be seen above, all the masks cannot be removed unless an adversary gets secret keys at all levels; the adversary is not allowed to do so due to the security definition (i.e., there exists a special level $\ell ^\star$ that the adversary cannot access).

4.2 Construction

Our HKIBE scheme $\Pi = (\textsf {Setup}, \textsf {Encrypt}, \textsf {GenHK}, \textsf {KeyUp}, \textsf {Upd}, \textsf {Decrypt})$ from an HIBE scheme $\Sigma = (\textsf {Init}, \textsf {Enc}, \textsf {GenSK}, \textsf {Dec}, \textsf {SampMSK}, \textsf {EvalMSK})$ is as follows.

• $\textsf {Setup}(1^{\lambda }, L) \rightarrow ({\textsf {pp}}, {\textsf {mk}})$: Run $(\textsf {MPK}, \textsf {MSK}) \leftarrow \textsf {Init}(1^{\lambda }, L+1)$, then output ${\textsf {pp}}:=\textsf {MPK}$ and ${\textsf {mk}}:=\textsf {MSK}$.

• : Parse ${\textsf {pp}}=\textsf {MPK}$. Run

$\cdot$:

and output .

• $\textsf {GenHK}({\textsf {pp}}, {\textsf {mk}}, {\texttt {id}}) \rightarrow ( \textsf {hk}_{{\texttt {id}}, 0 }^{( \ell )} )_{\ell \in [0, L]}$: Parse ${\textsf {pp}}=\textsf {MPK}$ and ${\textsf {mk}}=\textsf {MSK}$. First, compute ${\widehat{\textsf {MSK}}}_{{\texttt {id}}, \ell } \leftarrow \textsf {SampMSK}(\textsf {MPK})$ for $\ell \in [0,L-1]$. Then, for $\ell \in [0, L]$, run

  $$\begin{aligned} \left\{ \begin{array}{ll} {\textsf {SK}}_{ {\texttt {id}} }\!\left[ \frac{\textsf {MSK}}{\prod _{i \in [0, L-1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}, i}} \right] \leftarrow \textsf {GenSK}\!\left( \textsf {MPK}, \frac{\textsf {MSK}}{\prod _{i \in [0, L-1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}, i}}, {\texttt {id}} \right) \quad &{} \text {if } \ell = L,\\ {\textsf {SK}}_{ ({\texttt {id}}, \textsf {T}_{[L-1,\ell ]}(0)) }\!\left[ \frac{\textsf {MSK}}{\prod _{i \in [0, \ell -1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}, i}} \right] \\ \qquad \qquad \qquad \leftarrow \textsf {GenSK}\!\left( \textsf {MPK}, \frac{\textsf {MSK}}{\prod _{i \in [0, \ell -1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}, i}}, ({\texttt {id}}, \textsf {T}_{[L-1,\ell ]}(0)) \right) &{} \text {if } \ell \in [L-1],\\ {\textsf {SK}}_{ ({\texttt {id}},\textsf {T}_{[L-1,0]}(0)) }\!\left[ \textsf {MSK} \right] \leftarrow \textsf {GenSK}\!\left( \textsf {MPK}, \textsf {MSK}, ({\texttt {id}},\textsf {T}_{[L-1,0]}(0)) \right) &{} \text {if } \ell =0. \end{array} \right. \end{aligned}$$

  Note that without loss of generality, we assume $0 \in \mathcal {T}_{act}$ to describe initial helper keys simply. Output $( \textsf {hk}_{{\texttt {id}}, 0 }^{( \ell )} )_{\ell \in [0, L]}$, where

  • $\textsf {hk}_{{\texttt {id}}, 0 }^{( L )} :={\textsf {SK}}_{ {\texttt {id}} } \! \!\left[ \frac{\textsf {MSK}}{\prod _{i \in [0, L-1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}, i}} \right]$,

  • $\textsf {hk}_{{\texttt {id}}, 0 }^{( \ell )} :=\!\left( {\widehat{\textsf {MSK}}}_{{\texttt {id}}, \ell }, {\textsf {SK}}_{ ({\texttt {id}}, \textsf {T}_{[L-1,\ell ]}(0)) } \! \!\left[ \frac{\textsf {MSK}}{ \prod _{i \in [0, \ell -1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}, i}} \right] \right)$ for $\ell \in [L-1]$.

  • $\textsf {hk}_{{\texttt {id}}, 0 }^{( 0 )} (= \textsf {dk}_{{\texttt {id}}, 0}) :=\!\left( {\widehat{\textsf {MSK}}}_{{\texttt {id}}, 0}, {\textsf {SK}}_{ ({\texttt {id}}, \textsf {T}_{[L-1,0]}(0)) } \right)$.

• or $\bot$: If , output $\bot$. Otherwise, parse

$\triangleright$:

${\textsf {pp}}= \textsf {MPK}$

$\triangleright$:

.

Run

$\cdot$:

,

and output .

• $\textsf {Upd}({\textsf {pp}}, \textsf {hk}_{{\texttt {id}}, \tau _\ell }^{( \ell )}, \textsf {ku}_{{\texttt {id}}, t_\ell }^{( \ell )}) \rightarrow \textsf {hk}_{{\texttt {id}}, t_\ell }^{( \ell )}$: Suppose and $t_\ell = \textsf {T}_\ell ({\texttt {t}}')$. Parse

$\triangleright$:

${\textsf {pp}}= \textsf {MPK}$,

$\triangleright$:

,

$\triangleright$:

$\textsf {ku}_{{\texttt {id}}, t_{\ell } }^{( \ell )} = {\textsf {SK}}_{ ({\texttt {id}}, \textsf {T}_{[L-1,\ell ]}({\texttt {t}}')) } \! \!\left[ \frac{\textsf {MSK}}{\prod _{i \in [0, \ell ]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}, i}} \right]$.

Run

$\cdot$:

${\textsf {SK}}_{ ({\texttt {id}}, \textsf {T}_{[L-1,\ell ]}({\texttt {t}}')) } \! \!\left[ {\widehat{\textsf {MSK}}}_{{\texttt {id}}, \ell } \right] \leftarrow \textsf {GenSK}\!\left( \textsf {MPK}, {\widehat{\textsf {MSK}}}_{{\texttt {id}}, \ell }, \!\left( {\texttt {id}}, \textsf {T}_{[L-1,\ell ]}({\texttt {t}}') \right) \right)$,

$\cdot$:

${\textsf {SK}}_{ ({\texttt {id}}, \textsf {T}_{[L-1,\ell ]}({\texttt {t}}')) } \! \!\left[ \frac{\textsf {MSK}}{\prod _{i \in [0, \ell -1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}, i}} \right] \ \leftarrow \textsf {EvalMSK}\!\left( \textsf {MPK}, {\textsf {SK}}_{ ({\texttt {id}}, \textsf {T}_{[L-1,\ell ]}({\texttt {t}}')) } \! \!\left[ \frac{\textsf {MSK}}{\prod _{i \in [0, \ell ]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}, i}} \right] , {\textsf {SK}}_{ ({\texttt {id}}, \textsf {T}_{[L-1,\ell ]}({\texttt {t}}')) } \! \!\left[ {\widehat{\textsf {MSK}}}_{{\texttt {id}}, \ell } \right] , \mathtt {mul} \right)$,

Output $\textsf {hk}_{{\texttt {id}}, t_{\ell } }^{( \ell )} :=\!\left( {\widehat{\textsf {MSK}}}_{{\texttt {id}}, \ell }, {\textsf {SK}}_{ ({\texttt {id}}, \textsf {T}_{[L-1,\ell ]}({\texttt {t}}')) } \! \!\left[ \frac{\textsf {MSK}}{ \prod _{i \in [0, \ell -1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}, i}} \right] \right)$.

As the special case for $\ell =0$, $\textsf {hk}_{{\texttt {id}}, t_{0} }^{( 0 )} :=({\widehat{\textsf {MSK}}}_{{\texttt {id}}, 0}, {\textsf {SK}}_{ ({\texttt {id}}, \textsf {T}_{[L-1,0]}({\texttt {t}}')) })$.

• : Parse

$\triangleright$:

${\textsf {pp}}= \textsf {MPK}$,

$\triangleright$:

,

$\triangleright$:

.

Run and output

• .

Correctness. Thanks to the evaluation correctness of MSK evaluatability, decryption keys of our HKIBE scheme follow the same distributions as those of the underlying HIBE scheme; hence, the correctness of our HKIBE scheme readily follows from that of the underlying HIBE scheme.

4.3 Security

The security of the HKIBE scheme is reduced to from that of the underlying HIBE scheme supporting MSK evaluatability.

Theorem 1

If the underlying HIBE scheme with hierarchical depth $L+1$ supporting MSK evaluatability satisfies adaptive security, then the above HKIBE scheme with hierarchical depth L also satisfies adaptive security. Specifically, if there exists an adversary $\mathcal {A}$ to break adaptive security of the above HKIBE scheme with advantage $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )$, then there exists a reduction algorithm $\mathcal {B}$ to break adaptive security of the underlying HIBE scheme with advantage $\textsf {Adv}^\mathtt{{HIBE}}_{\Sigma ,L+1,\mathcal {B}}(\lambda ) \ge \textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )/\Theta (QL)$, where Q denotes the number of helper-key generation queries.

Proof overview First of all, we divide $\mathcal {A}$’s attack strategy into $L+1$ types with respect to a special hierarchical level $\ell ^\star \in [0,L]$ defined in the key-insulation query. Let $\mathcal {A}_{\ell ^\star }$ be an adversary $\mathcal {A}$ that makes key-insulation queries so that there exists a special level $\ell ^\star$. Since this covers all the possible strategies, the proof against a fixed $\mathcal {A}_{\ell ^\star }$ is sufficient for a proof against $\mathcal {A}$ of a general strategy with $\Theta (L)$ reduction loss.

Now, we use $\mathcal {A}_{\ell ^\star }$ as a building block and construct a reduction algorithm $\mathcal {B}_{\ell ^\star }$ against the underlying HIBE scheme. The main observation is that $\mathcal {B}_{\ell ^\star }$ can answer all $\mathcal {A}_{\ell ^\star }$’s queries by making HIBE secret-key reveal queries for the corresponding identity, say, , as long as it holds

$$\begin{aligned} ({\texttt {id}}, \textsf {T}_{ [L-1,\ell ] }({\texttt {t}})) \notin \textsf {prefix}^+( ({\texttt {id}}^\star , \textsf {T}_{[L-1,0]}({\texttt {t}}^\star )) ) \end{aligned}$$

(1)

even without the knowledge of the challenge tuple $({\texttt {id}}^\star , {\texttt {t}}^\star )$. Obviously, $\mathcal {B}_{\ell ^\star }$ answers all queries for ${\texttt {id}}\ (\ne {\texttt {id}}^\star )$ by making HIBE secret-key reveal queries since such a case always satisfies the condition (1). Therefore, the challenge is how $\mathcal {B}_{\ell ^\star }$ answers $\mathcal {A}_{\ell ^\star }$’s queries for ${\texttt {id}}^\star$, which might not meet the condition (1). Roughly speaking, we look at the MSK-part of $(\textsf {hk}_{ {\texttt {id}}^\star ,0 }^{( \ell )})_{\ell \in [0,L]}$ differently: In the construction, for every $\ell \in [0,L]$, the MSK-part of $\textsf {hk}_{ {\texttt {id}}^\star ,0 }^{( \ell )}$ is $\textsf {MSK}/ \prod _{i \in [0, \ell -1]} {\widehat{\textsf {MSK}}}_{{\texttt {id}}^\star , i}$, where ${\widehat{\textsf {MSK}}}_{{\texttt {id}}^\star , 0}, \ldots , {\widehat{\textsf {MSK}}}_{{\texttt {id}}^\star , L-1}$ are pseudo-MSKs for ${\texttt {id}}^\star$. In this proof, $\mathcal {B}_{\ell ^\star }$ samples a level-$\ell$ pseudo-MSK ${\widehat{\textsf {MSK}}}_{{\texttt {id}}^\star , \ell }$ for $\ell \in [0, L] \setminus \{\ell ^\star \}$. Note that ${\widehat{\textsf {MSK}}}_{{\texttt {id}}^\star , L}$ is picked instead of ${\widehat{\textsf {MSK}}}_{{\texttt {id}}^\star , \ell ^\star }$. Then, $\mathcal {B}_{\ell ^\star }$ (implicitly) sets ${\widehat{\textsf {MSK}}}_{{\texttt {id}}^\star , \ell ^\star } :=\textsf {MSK}/ \prod _{i \in [0, L] \setminus \{\ell ^\star \}}{\widehat{\textsf {MSK}}}_{{\texttt {id}}^\star , i}$. All the above pseudo-MSKs are properly distributed. A key-insulation query $({\texttt {id}}^\star , {\texttt {t}}, \ell )$ that contradicts the condition (1) satisfies $\textsf {T}_{ \ell }({\texttt {t}}) = \textsf {T}_{\ell }({\texttt {t}}^\star )$ and $\ell \in [\ell ^\star +1,L]$ since a query that satisfies $\textsf {T}_{ \ell }({\texttt {t}}) = \textsf {T}_{\ell }({\texttt {t}}^\star )$ is not allowed for $\ell \in [0,\ell ^\star -1]$ by definition. Indeed, $\mathcal {B}_{\ell ^\star }$ can answer such a query since the corresponding helper key $\textsf {hk}_{ {\texttt {id}}^\star ,\textsf {T}_{ \ell }({\texttt {t}}) }^{( \ell )}$ can be computed with only the above pseudo-MSKs by $\mathcal {B}_{\ell ^\star }$ itself. In particular, the distribution of the helper keys is identically distributed as that of helper keys created as in the construction thanks to pseudo-MSK indistinguishability in Def. 2. Note that $\mathcal {A}_{\ell ^\star }$ does not make any key-insulation query for $\ell ^\star$ by definition. On the other hand, a key-insulation query $({\texttt {id}}^\star ,{\texttt {t}},\ell )$ for $\ell \in [0,\ell ^\star -1]$ such that $\textsf {T}_{ \ell }({\texttt {t}}) \ne \textsf {T}_{\ell }({\texttt {t}}^\star )$ satisfies the condition (1). Therefore, $\mathcal {B}_{\ell ^\star }$ makes an HIBE secret-key reveal query on $({\texttt {id}}^\star ,\textsf {T}_{ [L-1,\ell ] }({\texttt {t}}))$ to get ${\textsf {SK}}_{ ({\texttt {id}}^\star ,\textsf {T}_{ [L-1,\ell ] }({\texttt {t}})) } [ \textsf {MSK} ]$, and runs $\textsf {EvalMSK}$ to return $\textsf {hk}_{ {\texttt {id}}^\star ,{\textsf {T}_{ \ell }({\texttt {t}})} }^{( \ell )}$ to $\mathcal {A}_{\ell ^\star }$. The output is properly distributed thanks to the evaluation correctness in Def. 2.

The above simulation can be done only when $\mathcal {B}_{\ell ^\star }$ knows ${\texttt {id}}^\star$ (i.e., selective security). Nonetheless, it is applicable even to adaptive security by guessing when the target identity ${\texttt {id}}^\star$ is queried at the beginning of the game: let ${\texttt {id}}_q$ be an identity on which $\mathcal {A}_{\ell ^\star }$ makes q-th helper-key generation query, and $\mathcal {B}_{\ell ^\star }$ first guesses the number $Q^\star \in [Q]$ such that ${\texttt {id}}_{Q^\star } = {\texttt {id}}^\star$ with $\Theta (Q)$ reduction loss.¹⁰ Then, $\mathcal {B}_{\ell ^\star }$ sets the pseudo-MSKs for ${\texttt {id}}_{Q^\star }$ as above, instead of ${\texttt {id}}^\star$, although it will turn out ${\texttt {id}}_{Q^\star }={\texttt {id}}^\star$ after the challenge query.

Proof of Theorem 1

We formally describe the proof as follows. As above, let $\mathcal {B}_{\ell ^\star }$ be a reduction algorithm against the underlying HIBE scheme. We show how to construct $\mathcal {B}_{\ell ^\star }$ by using $\mathcal {A}_{\ell ^\star }$ as follows. First of all, please keep in mind that $\mathcal {B}_{\ell ^\star }$ will set

$$\begin{aligned} ({\texttt {id}}^\star , \textsf {T}_{[L-1,0]}({\texttt {t}}^\star )) \end{aligned}$$

as the challenge identity in the HIBE security game. Therefore, $\mathcal {B}_{\ell ^\star }$ does not make HIBE secret-key reveal queries on the challenge identity itself and its prefix identities during the game. At first, $\mathcal {B}_{\ell ^\star }$ is given an HIBE’s master public key $\textsf {MPK}$ from an HIBE challenger ${\mathcal {C}}$. Then, $\mathcal {B}_{\ell ^\star }$ initializes $\mathtt {HKList}= \emptyset$ and sends ${\textsf {pp}}:=\textsf {MPK}$ to an HKIBE adversary $\mathcal {A}_{\ell ^\star }$.

Let ${\texttt {id}}_q$ be an identity on which $\mathcal {A}_{\ell ^\star }$ makes a q-th helper-key generation query. Then, $\mathcal {B}_{\ell ^\star }$ guesses the number $Q^\star \in [Q]$ such that ${\texttt {id}}_{Q^\star } = {\texttt {id}}^\star$. If the guess is incorrect, $\mathcal {B}_{\ell ^\star }$ outputs a random bit and aborts the game. The guess is correct with probability 1/Q. In the following, we assume that the guess is correct.

$\mathcal {B}_{\ell ^\star }$ answers $\mathcal {A}_{\ell ^\star }$’s queries by interacting with ${\mathcal {C}}$ as follows:

Helper-key generation query Upon a query ${\texttt {id}}_q$ from $\mathcal {A}_{\ell ^\star }$, $\mathcal {B}_{\ell ^\star }$ checks if $({\texttt {id}}, \cdot ) \notin \mathtt {HKList}$ holds, and returns $\bot$ to $\mathcal {A}_{\ell ^\star }$ if this is not the case. Otherwise, $\mathcal {B}_{\ell ^\star }$ proceeds as follows:

Case for $q \ne Q^\star$] To get $({\textsf {SK}}_{ ({\texttt {id}}_q,\textsf {T}_{[L-1,\ell ]}(0)) })_{\ell \in [0,L]}$, $\mathcal {B}_{\ell ^\star }$ makes secret-key reveal queries on $(({\texttt {id}}_q,\textsf {T}_{[L-1,\ell ]}(0)))_{\ell \in [0,L]}$.¹¹$\mathcal {B}_{\ell ^\star }$ runs

• ${\widehat{\textsf {MSK}}}_{{\texttt {id}}_q, \ell } \leftarrow \textsf {SampMSK}(\textsf {MPK})$ for $\ell \in [0,L-1]$

Then, for $\ell \in [1,L]$, $\mathcal {B}_{\ell ^\star }$ executes

• ${\textsf {SK}}_{ ({\texttt {id}}_q,\textsf {T}_{[L-1,\ell ]}(0)) } \! \!\left[ \prod _{i \in [0, \ell -1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_q,i} \right] \leftarrow \textsf {GenSK}(\textsf {MPK}, \prod _{i \in [0, \ell -1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_q,i}, ({\texttt {id}}_q,\textsf {T}_{[L-1,\ell ]}(0)))$,

• ${\textsf {SK}}_{ ({\texttt {id}}_q,\textsf {T}_{[L-1,\ell ]}(0)) } \! \!\left[ \frac{\textsf {MSK}}{\prod _{i \in [0, \ell -1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_q,i}} \right] \leftarrow \textsf {EvalMSK}(\textsf {MPK}, {\textsf {SK}}_{ ({\texttt {id}}_q,\textsf {T}_{[L-1,\ell ]}(0)) },$${\textsf {SK}}_{ ({\texttt {id}}_q,\textsf {T}_{[L-1,\ell ]}(0)) } \! \!\left[ \prod _{i \in [0, \ell -1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_q,i} \right] , \mathtt {div})$,

and stores an initial helper key $({\texttt {id}}_q, ( \textsf {hk}_{ {\texttt {id}}_q, 0 }^{( \ell )} )_{\ell \in [0, L]})$ in $\mathtt {HKList}$, where

• $\textsf {hk}_{ {\texttt {id}}_q, 0 }^{( L )} :={\textsf {SK}}_{ {\texttt {id}}_q } \! \!\left[ \frac{\textsf {MSK}}{\prod _{i \in [0, L-1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_q, i}} \right]$,

• $\textsf {hk}_{ {\texttt {id}}_q, 0 }^{( \ell )} :=\!\left( {\widehat{\textsf {MSK}}}_{{\texttt {id}}_q, \ell }, {\textsf {SK}}_{ ({\texttt {id}}_q,\textsf {T}_{[L-1,\ell ]}(0)) } \! \!\left[ \frac{\textsf {MSK}}{\prod _{i \in [0, \ell -1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_q,i}} \right] \right)$ for $\ell \in [0, L-1]$.

Observe that the helper keys created by $\mathcal {B}_{\ell ^\star }$ are properly distributed as follows: For every $\ell \in [1,L]$, ${\textsf {SK}}_{ ({\texttt {id}}_q,\textsf {T}_{[L-1,\ell ]}(0)) } \! \!\left[ \textsf {MSK}/ \prod _{i \in [0, L-1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_q, i} \right]$, which is the component of the level-$\ell$ helper key $\textsf {hk}_{ {\texttt {id}}_q, 0 }^{( \ell )}$, is created by running

• ${\textsf {SK}}_{ ({\texttt {id}}_q,\textsf {T}_{[L-1,\ell ]}(0)) } \! \!\left[ \frac{\textsf {MSK}}{\prod _{i \in [0, L-1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_q, i}} \right] \leftarrow \textsf {GenSK}\!\left( \textsf {MPK}, \frac{\textsf {MSK}}{\prod _{i \in [0, L-1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_q, i}}, ({\texttt {id}}_q,\textsf {T}_{[L-1,\ell ]}(0)) \right)$,

in the construction while $\mathcal {B}_{\ell ^\star }$ runs $\textsf {EvalMSK}$ algorithm in the reduction. Thanks to the evaluation correctness in Def. 2, the both of ${\textsf {SK}}_{ ({\texttt {id}}_q,\textsf {T}_{[L-1,\ell ]}(0)) } [ \textsf {MSK}/ \prod _{i \in [0, L-1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_q, i} ]$ follow the same distribution. Note that the case for $\ell =0$ (i.e., ${\textsf {SK}}_{ ({\texttt {id}}_q,\textsf {T}_{[L-1,0]}(0)) }$) is the same procedure as in the construction.

Case for $q = Q^\star$: $\mathcal {B}_{\ell ^\star }$ runs

• ${\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, \ell } \leftarrow \textsf {SampMSK}(\textsf {MPK})$ for $\ell \in [0, L] \setminus \{\ell ^\star \}$,

• ${\textsf {SK}}_{ ( {\texttt {id}}_{Q^\star },\textsf {T}_{[L-1,\ell ]}(0) ) } \! \!\left[ \prod _{i\in [\ell ,L]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star },i} \right] \leftarrow \textsf {GenSK}\!\left( \textsf {MPK}, \prod _{i\in [\ell ,L]} {\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star },i},( {\texttt {id}}_{Q^\star },\textsf {T}_{[L-1,\ell ]}(0) ) \right)$ for $\ell \in [\ell ^\star +1,L]$,

and stores a part of an initial helper key $({\texttt {id}}_{Q^\star }, (\textsf {hk}_{ {\texttt {id}}_{Q^\star },0 }^{( \ell )})_{\ell \in [\ell ^\star +1, L]}, ({\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star },\ell })_{\ell \in [0,\ell ^\star ]})$ in $\mathtt {HKList}$, where

• $\textsf {hk}_{ {\texttt {id}}_{Q^\star }, 0 }^{( \ell )} :=\!\left( {\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star },\ell }, {\textsf {SK}}_{ ( {\texttt {id}}_{Q^\star },\textsf {T}_{[L-1,\ell ]}(0) ) } \! \!\left[ \prod _{i\in [\ell ,L]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star },i} \right] \right)$ for $\ell \in [\ell ^\star +1,L]$,

$\mathcal {B}_{\ell ^\star }$ does not create the rest of the initial helper key $( \textsf {hk}_{ {\texttt {id}}^\star ,0 }^{( \ell )} )_{\ell \in [0,\ell ^\star ]}$ at this point, and on key-insulation query, helper keys for any ${\texttt {t}}\in \mathcal {T}_{act}$ and $\ell \in [0,\ell ^\star -1]$ will be computed directly from the pseudo-MSKs, not the corresponding initial helper keys.

We show that the level-$\ell$ helper keys for $\ell \in [\ell ^\star +1,L]$ and the pseudo-MSKs created above and are properly distributed as follows. Since the above procedure is the same as that of the construction if $\ell ^\star = L$, we consider the case for $\ell ^\star \ne L$. In the case, $\mathcal {B}_{\ell ^\star }$ implicitly sets

• ${\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, \ell } = {\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, \ell }$ for $\ell \in [0, L] \setminus \{\ell ^\star \}$,

• ${\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, \ell ^\star } = \frac{\textsf {MSK}}{\prod _{i \in [0, L] \setminus \{\ell ^\star \}}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, i}}$.

• Case for $\ell \in [0, \ell ^{\star }-1]$: The level-$\ell$ pseudo-MSK $\textsf {MSK}_{{\texttt {id}}_{Q^\star }, \ell } ={\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, \ell }$ is created in the same way as the construction by running $\textsf {SampMSK}$ algorithm.

• Case for $\ell ^\star$: The level-$\ell ^\star$ pseudo-MSK ${\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, \ell ^\star }$ is created by running $\textsf {SampMSK}$ algorithm in the construction (i.e., ${\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, \ell ^\star }$ is the output of $\textsf {SampMSK}$). In the reduction, we assume that the level-$\ell ^\star$ pseudo-MSK is ${\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, \ell ^\star }=\textsf {MSK}/ \prod _{i \in [0, L-1] \setminus \{\ell ^\star \}}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, i}$ although $\mathcal {B}_{\ell ^\star }$ does not compute it explicitly. Thanks to the pseudo-MSK indistinguishability in Def. 2, the level-$\ell ^\star$ pseudo-MSK ${\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, \ell ^\star }$ follows the same distribution as the construction.

• Case for $\ell \in [\ell ^\star +1,L]$: First of all, the main component ${\textsf {SK}}_{ {\texttt {id}}_{Q^\star } } [ \textsf {MSK}/ \prod _{i \in [0, L-1]} {\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, i} ]$ of level-L helper key $\textsf {hk}_{ {\texttt {id}}_{Q^\star }, 0 }^{( L )}$ is created by

• ${\textsf {SK}}_{ {\texttt {id}}_{Q^\star } } \! \!\left[ \frac{\textsf {MSK}}{\prod _{i \in [0, L-1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, i}} \right] \leftarrow \textsf {GenSK}\!\left( \textsf {MPK}, \frac{\textsf {MSK}}{\prod _{i \in [0, L-1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, i}}, {\texttt {id}}_{Q^\star } \right)$

in the construction. The difference between the construction and the reduction is that the MSK-part $\textsf {MSK}/ \prod _{i \in [0, L-1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, i}$ is replaced by the pseudo-MSK ${\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star },L}$. Observe that

$$\begin{aligned}&\frac{\textsf {MSK}}{\prod _{i \in [0, L-1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, i}} \\&\qquad = \frac{\textsf {MSK}}{{\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, \ell ^\star } \cdot \prod _{i \in [0, L-1] \setminus \{\ell ^\star \}}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, i}}\\&\qquad = \frac{\textsf {MSK}}{(\textsf {MSK}/ \prod _{i \in [0, L] \setminus \{\ell ^\star \}}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, i}) \cdot \prod _{i \in [0, L-1] \setminus \{\ell ^\star \}}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, i}}\\&\qquad = {\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, L}. \end{aligned}$$

Therefore, thanks to the evaluation correctness in Def. 2, the level-L helper key follows the same distribution as in the construction. Similarly, for $\ell \in [\ell ^\star +1,L-1]$ the main component of level-$\ell$ helper key $\textsf {hk}_{ {\texttt {id}}_{Q^\star }, 0 }^{( \ell )}$ is ${\textsf {SK}}_{ {\texttt {id}}_{Q^\star } } [ \textsf {MSK}/ \prod _{i \in [0, \ell -1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, i} ]$ in the construction, and its MSK-part is replaced with $\prod _{i \in [\ell ,L]} {\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star }, i}$ in the reduction. It is easy to see that the level-$\ell$ helper key follows the same distribution as in the construction thanks to the evaluation correctness in Def. 2.

Initial helper-key reveal query Upon a query ${\texttt {id}}_q$ from $\mathcal {A}_{\ell ^\star }$, $\mathcal {B}_{\ell ^\star }$ finds $( \textsf {hk}_{ {\texttt {id}}_q, 0 }^{( \ell )} )_{\ell \in [0, L]}$ from $\mathtt {HKList}$ and returns $( \textsf {hk}_{ {\texttt {id}}_q, 0 }^{( \ell )} )_{\ell \in [0, L]}$ to $\mathcal {A}_{\ell ^\star }$. $\mathcal {B}_{\ell ^\star }$ can answer all $\mathcal {A}_{\ell ^\star }$’s queries since $\mathcal {A}_{\ell ^\star }$ does not make the query on ${\texttt {id}}^\star \ (= {\texttt {id}}_{Q^\star })$ due to the restriction in the query.

Key-insulation query Upon a query $({\texttt {id}}_q, {\texttt {t}}, \ell )$ from $\mathcal {A}_{\ell ^\star }$, $\mathcal {B}_{\ell ^\star }$ proceeds as follows:

Case for  ${\texttt {id}}_q \ne {\texttt {id}}_{Q^\star }$: $\mathcal {B}_{\ell ^\star }$ finds the initial helper keys $( \textsf {hk}_{ {\texttt {id}}_q, 0 }^{( \ell )} )_{\ell \in [0,L]}$ from $\mathtt {HKList}$ and creates $\textsf {hk}_{ {\texttt {id}}_q,\textsf {T}_{ \ell }({\texttt {t}}) }^{( \ell )}$ in the same way as the construction.

Case for  ${\texttt {id}}_q = {\texttt {id}}_{Q^\star }$: Due to the Type-$\ell ^\star$ strategy and the restriction on the special level $\ell ^\star$, $\mathcal {A}_{\ell ^\star }$ does not make any key-insulation queries on $\ell = \ell ^\star$. $\mathcal {B}_{\ell ^\star }$ finds a part of the initial helper key $((\textsf {hk}_{ {\texttt {id}}_{Q^\star },0 }^{( \ell )})_{\ell \in [\ell ^\star +1, L]}, ({\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star },\ell })_{\ell \in [0,\ell ^\star ]})$ from $\mathtt {HKList}$ and performs as follows:

Level-$\ell$ for $\ell \in [\ell ^\star +1,L]$: $\mathcal {B}_{\ell ^\star }$ creates $\textsf {hk}_{ {\texttt {id}}_{Q^\star },\textsf {T}_{ \ell }({\texttt {t}}) }^{( \ell )}$ in the same way as the construction.

Level-$\ell$ for $\ell \in [0, \ell ^\star -1]$: $\mathcal {B}_{\ell ^\star }$ first makes an HIBE secret-key reveal query on $({\texttt {id}}_{Q^\star }, \textsf {T}_{ [L-1,\ell ] }({\texttt {t}}))$ and receives ${\textsf {SK}}_{ ({\texttt {id}}_{Q^\star }, \textsf {T}_{ [L-1,\ell ] }({\texttt {t}})) }$ from ${\mathcal {C}}$. Then, $\mathcal {B}_{\ell ^\star }$ uses $( {\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star },i} )_{i \in [0, \ell -1]}$ to run

• ${\textsf {SK}}_{ ({\texttt {id}}_{Q^\star }, \textsf {T}_{ [L-1,\ell ] }({\texttt {t}})) } \! \!\left[ \prod _{i \in [0, \ell -1]} {\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star },i} \right] \leftarrow \textsf {GenSK}(\textsf {MPK}, \prod _{i \in [0, \ell -1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star },i}, ({\texttt {id}}_{Q^\star }, \textsf {T}_{ [L-1,\ell ] }({\texttt {t}})))$,

• ${\textsf {SK}}_{ ({\texttt {id}}_{Q^\star }, \textsf {T}_{ [L-1,\ell ] }({\texttt {t}})) } \! \!\left[ \frac{\textsf {MSK}}{\prod _{i \in [0, \ell -1]} {\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star },i}} \right] \quad \leftarrow \textsf {EvalMSK}(\textsf {MPK}, {\textsf {SK}}_{ ({\texttt {id}}_{Q^\star }, \textsf {T}_{ [L-1,\ell ] }({\texttt {t}})) }, {\textsf {SK}}_{ ({\texttt {id}}_{Q^\star }, \textsf {T}_{ [L-1,\ell ] }({\texttt {t}})) } \! \!\left[ \prod _{i \in [0, \ell -1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star },i} \right] , \mathtt {div})$.

Finally, $\mathcal {B}_{\ell ^\star }$ returns

$$\begin{aligned} \textsf {hk}_{ {\texttt {id}}_{Q^\star }, {\texttt {t}} }^{( \ell )} = \!\left( {\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star },\ell }, {\textsf {SK}}_{ ({\texttt {id}}_{Q^\star }, \textsf {T}_{ [L-1,\ell ] }({\texttt {t}})) } \! \!\left[ \frac{\textsf {MSK}}{\prod _{i \in [0, \ell -1]}{\widehat{\textsf {MSK}}}_{{\texttt {id}}_{Q^\star },i}} \right] \right) \end{aligned}$$

to $\mathcal {A}_{\ell ^\star }$. Observe that the level-$\ell$ helper key is properly distributed thanks to the evaluation correctness in Def. 2.

Challenge query Upon a query $({\texttt {id}}^\star , {\texttt {t}}^\star , \textsf {M}^\star _0, \textsf {M}^\star _1)$ from $\mathcal {A}_{\ell ^\star }$ such that $|\textsf {M}^\star _0| = |\textsf {M}^\star _1|$, $\mathcal {B}_{\ell ^\star }$ makes a challenge query on $(({\texttt {id}}^\star , \textsf {T}_{[L-1,0]}({\texttt {t}}^\star )), \textsf {M}^\star _0, \textsf {M}^\star _1)$ and receives an HIBE challenge ciphertext $\textsf {C}_{ ({\texttt {id}}^\star , \textsf {T}_{[L-1,0]}({\texttt {t}}^\star )) }$. Then, $\mathcal {B}_{\ell ^\star }$ sends an HKIBE challenge ciphertext $\textsf {ct}_{ {\texttt {id}}^\star ,{\texttt {t}}^\star } :=\textsf {C}_{ ({\texttt {id}}^\star , \textsf {T}_{[L-1,0]}({\texttt {t}}^\star )) }$ to $\mathcal {A}_{\ell ^\star }$.

Observe that $\textsf {C}_{ ({\texttt {id}}^\star , \textsf {T}_{[L-1,0]}({\texttt {t}}^\star )) }$ is created in the same way as the construction.

After $\mathcal {B}_{\ell ^\star }$ receives a bit $b'$ from $\mathcal {A}_{\ell ^\star }$, $\mathcal {B}_{\ell ^\star }$ sends ${\mathcal {C}}$ $\beta ' :=b'$ as its own guess.

The above completes the description of $\mathcal {B}_{\ell ^\star }$. Observe that $\mathcal {B}_{\ell ^\star }$ can answer all of $\mathcal {A}$’s queries with ${\mathcal {C}}$. $\mathcal {B}_{\ell ^\star }$ makes the HIBE challenge query on

$$\begin{aligned} ({\texttt {id}}^\star , \textsf {T}_{[L-1,0]}({\texttt {t}}^\star )), \end{aligned}$$

while $\mathcal {B}_{\ell ^\star }$ makes HIBE secret-key reveal queries on the following identity ${\texttt {id}}_q \ (q \in [Q])$:

• For all $q \in [Q] \setminus \{Q^\star \}$, we have ${\texttt {id}}_q \notin \textsf {prefix}^+( ({\texttt {id}}^\star , \textsf {T}_{[L-1,0]}({\texttt {t}}^\star )) )$. Therefore, $\mathcal {B}_{\ell ^\star }$ can make the HIBE secret-key reveal queries on $({\texttt {id}}_q,\textsf {T}_{[L-1,\ell ]}(0))_{\ell \in [0,L]}$ for the helper-key generation query on ${\texttt {id}}_q$ (if $\mathcal {B}_{\ell ^\star }$’s guess of the number $Q^\star$ is correct).

• For $q = Q^\star$ (i.e., ${\texttt {id}}_q = {\texttt {id}}_{Q^\star } = {\texttt {id}}^\star$), $\mathcal {A}_{\ell ^\star }$ might make a key-insulation query on $({\texttt {id}}_{Q^\star }, \textsf {T}_{ [L-1,\ell ] }({\texttt {t}}))$ for ${\texttt {t}}\in \mathcal {T}_{act}$ and $\ell \in [0, \ell ^\star -1]$. $\mathcal {B}_{\ell ^\star }$ can make the HIBE secret-key generation query on $({\texttt {id}}_{Q^\star }, \textsf {T}_{ [L-1,\ell ] }({\texttt {t}}))$ since it holds $({\texttt {id}}_{Q^\star }, \textsf {T}_{ [L-1,\ell ] }({\texttt {t}})) \notin \textsf {prefix}^+( ({\texttt {id}}^\star , \textsf {T}_{[L-1,0]}({\texttt {t}}^\star )) )$ due to the restriction on the special level $\ell ^\star$.¹²

As we already observed, $\mathcal {B}_{\ell ^\star }$ perfectly simulates the adaptive security game against $\mathcal {A}_{\ell ^\star }$ with probability 1/Q. Since the probability that $\beta '$ is a correct guess is the same as that of $b'$, $\mathcal {B}_{\ell ^\star }$’s advantage is $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}_{\ell ^\star }}(\lambda ) = Q \cdot \textsf {Adv}^\mathtt{{HIBE}}_{\Sigma , L+1, \mathcal {B}_{\ell ^\star }}(\lambda )$.

Therefore, $\mathcal {B}$’s advantage against $\mathcal {A}$ of general attack strategy is $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L+1,\mathcal {A}}(\lambda ) = \sum _{\ell ^\star \in [0, L]} Q \cdot \textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}_{\ell ^\star }}(\lambda ) \le Q(L+1) \cdot \textsf {Adv}^\mathtt{{HIBE}}_{\Sigma , L, \mathcal {B}}(\lambda )$. $\square$

If the underlying HIBE scheme is selectively secure, our HKIBE scheme then satisfies selective security. Similarly, if the underlying HIBE scheme is CCA-secure, our HKIBE scheme meets CCA security. We omit the proofs since they can be done in the same manner as Theorem 1.

Corollary 1

If the underlying HIBE scheme with hierarchical depth $L+1$ supporting MSK evaluatability satisfies selective security, then the above HKIBE scheme with hierarchical depth L also satisfies selective security. Specifically, if there exists an adversary $\mathcal {A}$ to break selective security of our HKIBE scheme with advantage $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )$, then there exists a reduction algorithm $\mathcal {B}$ to break selective security of the underlying HIBE scheme with advantage $\textsf {Adv}^\mathtt{{HIBE}}_{\Sigma ,L+1,\mathcal {B}}(\lambda ) \ge \textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )/\Theta (L)$.

Corollary 2

If the underlying HIBE scheme with hierarchical depth $L+1$ supporting MSK evaluatability satisfies (adaptive) CCA security, then the above HKIBE scheme with hierarchical depth L also satisfies (adaptive) CCA security. Specifically, if there exists an adversary $\mathcal {A}$ to break adaptive CCA security of our HKIBE scheme with advantage $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )$, then there exists a reduction algorithm $\mathcal {B}$ to break adaptive CCA security of the underlying HIBE scheme with advantage $\textsf {Adv}^\mathtt{{HIBE}}_{\Sigma ,L+1,\mathcal {B}}(\lambda ) \ge \textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )/\Theta (QL)$.

5 Generic construction from plain HIBE

We provide a generic construction of an HKIBE scheme with depth L from any plain HIBE scheme with depth $L+1$. This construction is based on Hanaoka et al.’s HKIBE scheme [30], and can be easily extended to an adaptive-identity CCA secure scheme (see Sect. 5.4). We suppose that the first $\lceil \log (L+1) \rceil$ bits of each identity of our HKIBE scheme is used for indicating the hierarchical level $\ell$, and the rest expresses the identity (i.e., $\ell \Vert {\texttt {id}}\in \mathcal {I}_{\textsc {hibe}} \approx [0,L] \times \mathcal {I}$). For instance, if the bit-length of identities in the underlying HIBE scheme is 256 bits and $L=250$ (i.e., $\lceil \log (L+1) \rceil = 8$), then the identity in our HKIBE scheme is 248 bits.

Fig. 2

The intuition of our second construction

5.1 Construction idea

The aim of our second construction is to get rid of MSK evaluatability from the first construction while kee** the security. The basic idea is to employ an $(L+1)$-out-of-$(L+1)$ secret sharing scheme for plaintexts, where as the first construction employs it for MSK-parts of helper keys. Specifically, this construction’s core spirit is that a ciphertext consists of $L+1$ HIBE ciphertexts $( ( \textsf {C}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}}) } )_{\ell \in [L]},\textsf {C}_{ 0 \Vert {\texttt {id}} } )$, where the first L ciphertexts are encryptions of uniformly random pseudo-plaintexts $( \textsf {M}_\ell )_{\ell \in [L]}$ and the last ciphertext is an encryption of the plaintext masked with all pseudo-plaintexts $\textsf {M}\bigoplus _{\ell \in [L]}\textsf {M}_\ell$. The plaintext and all pseudo-plaintexts can be viewed as shares of an $(L+1)$-out-of-$(L+1)$ secret sharing scheme. We design the scheme so that each user ${\texttt {id}}$ can decrypt a ciphertext only if the user is able to decrypt all the $L+1$ HIBE ciphertexts. Indeed, the similar design concept is employed in the HHSI05 scheme [30]. However, our design requires only one HIBE scheme with the hierarchical depth $L+1$ while the HHSI05 scheme consists of $L+1$ HIBE schemes for the different depth $\ell \in [L+1]$. This design improvement makes master public/secret keys be constant sizes.

We illustrate the overview in Fig. 2. As mentioned above, we consider $L+1$ hierarchical identities for ciphertexts in the underlying HIBE scheme: $(L\Vert {\texttt {id}},\textsf {T}_{ [L-1,0] }({\texttt {t}}))$, $(L-1\Vert {\texttt {id}},\textsf {T}_{ [L-2,0] }({\texttt {t}}))$, $\ldots$, $(1\Vert {\texttt {id}},\textsf {T}_{ 0 }({\texttt {t}}))$, and $0\Vert {\texttt {id}}$. Obviously, each ciphertext $\textsf {C}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}})) }$ of can be decrypted by ${\textsf {SK}}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}})) }$ of $\textsf {dk}_{{\texttt {id}}, \textsf {T}_{ 0 }({\texttt {t}})}$ for $\ell \in [0,L]$.¹³ Each helper key $\textsf {hk}_{{\texttt {id}}, \textsf {T}_{ \ell }({\texttt {t}}) }^{( \ell )}$ includes $L-\ell$ HIBE secret keys $({\textsf {SK}}_{ j\Vert {\texttt {id}},\textsf {T}_{ [j-1,\ell ] }({\texttt {t}}) })_{j\in [\ell +1,L]}$, which are delegated from their upper-level helper keys $({\textsf {SK}}_{ j\Vert {\texttt {id}},\textsf {T}_{ [j-1,\ell +1] }({\texttt {t}}) })_{j\in [\ell +1,L]}$, and a new HIBE secret key ${\textsf {SK}}_{ \ell \Vert {\texttt {id}} }$. Since there exists a special level $\ell ^\star$ such that no level-$\ell ^\star$ helper keys are compromised, an adversary does not have ${\textsf {SK}}_{ \ell ^\star \Vert {\texttt {id}} }$. In addition to this, the adversary cannot obtain any secret keys which can derive ${\textsf {SK}}_{ (\ell ^\star \Vert {\texttt {id}},\textsf {T}_{[\ell ^\star ,0]}({\texttt {t}}^\star )) }$ due to the restriction in the security game, the adversary cannot decrypt the challenge ciphertext.

5.2 Construction

Our HKIBE scheme $\Pi = (\textsf {Setup}, \textsf {Encrypt}, \textsf {GenHK}, \textsf {KeyUp}, \textsf {Upd}, \textsf {Decrypt})$ from a plain HIBE scheme $\Sigma = (\textsf {Init}, \textsf {Enc}, \textsf {GenSK}, \textsf {Dec})$ is as follows.

• $\textsf {Setup}(1^{\lambda }, L) \rightarrow ({\textsf {pp}}, {\textsf {mk}})$: Run $(\textsf {MPK}, \textsf {MSK}) \leftarrow \textsf {Init}(1^{\lambda }, L+1)$ and output ${\textsf {pp}}:=\textsf {MPK}$ and ${\textsf {mk}}:=\textsf {MSK}$.

• : Parse ${\textsf {pp}}=\textsf {MPK}$. Sample $\textsf {M}_\ell \leftarrow _R\mathcal {M}$ for $\ell \in [L]$ and set $\textsf {M}_0 = \textsf {M}\bigoplus _{\ell \in [L]}\textsf {M}_\ell$. Run

$\cdot$:

$\textsf {C}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}})) } \leftarrow \textsf {Enc}(\textsf {MPK}, (\ell \Vert {\texttt {id}}, \textsf {T}_{[\ell -1,0]}{({\texttt {t}})}), \textsf {M}_\ell )$ for $\ell \in [0,L]$,

then output .

• $\textsf {GenHK}({\textsf {pp}}, {\textsf {mk}}, {\texttt {id}}) \rightarrow ( \textsf {hk}_{{\texttt {id}}, 0 }^{( 0 )} )_{\ell \in [0, L]}$: Parse ${\textsf {pp}}= \textsf {MPK}$ and ${\textsf {mk}}= \textsf {MSK}$. For $\ell \in [0,L]$, compute $\textsf {hk}_{{\texttt {id}}, 0 }^{( \ell )} :=( {\textsf {SK}}_{ ( i \Vert {\texttt {id}}, \textsf {T}_{[i-1,\ell ]}(0) ) } )_{i \in [\ell ,L]}$ as follows: for $i \in [\ell , L]$, run

$\cdot$:

${\textsf {SK}}_{ ( i \Vert {\texttt {id}}, \textsf {T}_{[i-1, \ell ]}(0) ) } \leftarrow \textsf {GenSK}(\textsf {MPK}, {\textsf {MSK}}, ( i \Vert {\texttt {id}}, \textsf {T}_{[i-1, \ell ]}(0) ))$.

Output $( \textsf {hk}_{{\texttt {id}}, 0 }^{( \ell )} )_{\ell \in [0,L]}$.

• $\textsf {KeyUp}({\textsf {pp}}, {\texttt {t}}, \textsf {hk}_{{\texttt {id}}, t_{\ell +1} }^{( \ell +1 )}) \rightarrow \textsf {ku}_{{\texttt {id}}, \textsf {T}_{ \ell }({\texttt {t}}) }^{( \ell )}$ or $\bot$: Output $\bot$ if $t_{\ell +1} \ne \textsf {T}_{ \ell +1 }({\texttt {t}})$. Otherwise, parse

$\triangleright$:

${\textsf {pp}}= \textsf {MPK}$,

$\triangleright$:

$\textsf {hk}_{{\texttt {id}}, t_{\ell +1} }^{( \ell +1 )} = ( {\textsf {SK}}_{ (i \Vert {\texttt {id}}, \textsf {T}_{ [i-1,\ell +1] }({\texttt {t}})) } )_{i \in [\ell +1,L]}$.

For $i \in [\ell +1,L]$, run

$\cdot$:

${\textsf {SK}}_{ (i \Vert {\texttt {id}}, \textsf {T}_{ [i-1,\ell ] }({\texttt {t}})) } \qquad \qquad \leftarrow \textsf {GenSK}(\textsf {MPK}, {\textsf {SK}}_{ (i \Vert {\texttt {id}}, \textsf {T}_{ [i-1,\ell +1] }({\texttt {t}})) }, (i \Vert {\texttt {id}}, \textsf {T}_{ [i-1,\ell ] }({\texttt {t}})))$,

and output $\textsf {ku}_{{\texttt {id}}, \textsf {T}_{ \ell }({\texttt {t}}) }^{( \ell )} :=( {\textsf {SK}}_{ (i \Vert {\texttt {id}}, \textsf {T}_{ [i-1,\ell ] }({\texttt {t}})) } )_{i \in [\ell +1, L]}$.

• $\textsf {Upd}({\textsf {pp}}, \textsf {hk}_{{\texttt {id}}, \tau _\ell }^{( \ell )}, \textsf {ku}_{{\texttt {id}}, t_\ell }^{( \ell )}) \rightarrow \textsf {hk}_{{\texttt {id}}, t_\ell }^{( \ell )}$: Suppose $\tau _{\ell } = \textsf {T}_{ \ell }({\texttt {t}})$ and $t_\ell = \textsf {T}_\ell ({\texttt {t}}')$. Parse

$\triangleright$:

$\textsf {hk}_{{\texttt {id}}, \tau _\ell }^{( \ell )} = ( {\textsf {SK}}_{ \ell \Vert {\texttt {id}} }, ( {\textsf {SK}}_{ (i \Vert {\texttt {id}}, \textsf {T}_{ [i-1,\ell ] }({\texttt {t}})) } )_{i \in [\ell +1, L]}) =( {\textsf {SK}}_{ (i \Vert {\texttt {id}}, \textsf {T}_{ [i-1,\ell ] }({\texttt {t}})) } )_{i \in [\ell , L]}$,

$\triangleright$:

$\textsf {ku}_{{\texttt {id}}, t_{\ell } }^{( \ell )} = ( {\textsf {SK}}_{ (i \Vert {\texttt {id}}, \textsf {T}_{[i-1,\ell ]}({\texttt {t}}')) } )_{i \in [\ell +1,L]}$.

Output $\textsf {hk}_{{\texttt {id}}, t_\ell }^{( \ell )} :=({\textsf {SK}}_{ \ell \Vert {\texttt {id}} }, ( {\textsf {SK}}_{ (i \Vert {\texttt {id}}, \textsf {T}_{[i-1,\ell ]}({\texttt {t}}')) } )_{i \in [\ell +1, L]}) = ( {\textsf {SK}}_{ (i \Vert {\texttt {id}}, \textsf {T}_{[i-1,\ell ]}({\texttt {t}}')) } )_{i \in [\ell , L]}$.

• : Parse

$\triangleright$:

${\textsf {pp}}=\textsf {MPK}$,

$\triangleright$:

$\textsf {dk}_{{\texttt {id}}, \textsf {T}_{ 0 }({\texttt {t}})} = \textsf {hk}_{{\texttt {id}}, \textsf {T}_{ 0 }({\texttt {t}}) }^{( 0 )} = ( {\textsf {SK}}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}})) } )_{\ell \in [0,L]}$,

$\triangleright$:

.

For $\ell \in [L]$, run

$\cdot$:

$\textsf {M}_\ell \leftarrow \textsf {Dec}(\textsf {MPK}, {\textsf {SK}}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}})) }, \textsf {C}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}})) })$,

Output

• $\textsf {M}= \textsf {Dec}(\textsf {MPK}, {\textsf {SK}}_{ 0 \Vert {\texttt {id}} }, \textsf {C}_{ 0\Vert {\texttt {id}} }) \bigoplus _{\ell \in [L]}\textsf {M}_\ell$.

Correctness. Since ciphertexts and decryption keys of our HKIBE scheme consists of those the underlying HIBE scheme, the correctness of the HKIBE scheme readily follows from that of the underlying HIBE scheme.

5.3 Security

The security of the HKIBE scheme is reduced to that of the underlying HIBE scheme.

Theorem 2

If the underlying HIBE scheme with hierarchical depth $L+1$ satisfies the adaptive security, the above HKIBE scheme with hierarchical depth L also satisfies the adaptive security. Specifically, if there exists an adversary $\mathcal {A}$ to break the adaptive security of the above HKIBE scheme with advantage $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )$, then there exists a reduction algorithm $\mathcal {B}$ to break the adaptive security of the underlying HIBE scheme with advantage $\textsf {Adv}^\mathtt{{HIBE}}_{\Sigma , L+1, \mathcal {B}}(\lambda ) \ge \textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )/\Theta (L)$.

Proof overview In the proof, we divide $\mathcal {A}$’s attack strategy into $L+1$ types and define $\mathcal {A}_{\ell ^\star }$ for every $\ell ^\star \in [0,L]$ as in the proof of Theorem 1 with $\Theta (L)$ reduction loss. We show the proof against $\mathcal {A}_{\ell ^\star }$ for fixed $\ell ^\star$.

We use $\mathcal {A}_{\ell ^\star }$ as a building block and construct a reduction algorithm $\mathcal {B}_{\ell ^\star }$ against the underlying (plain) HIBE scheme. The challenge ciphertext for $({\texttt {id}}^\star ,{\texttt {t}}^\star )$ includes $L+1$ HIBE ciphertexts $\textsf {C}_{ ( L\Vert {\texttt {id}}^\star , \textsf {T}_{[L-1,0]}({\texttt {t}}^\star ) ) }^\star , \ldots , \textsf {C}_{ 0\Vert {\texttt {id}}^\star }^\star$, and one of them should be the HIBE challenge ciphertext to reduce to adaptive security of the underlying HIBE scheme. Since $\mathcal {A}_{\ell ^\star }$ does not make any key-insulation queries for $({\texttt {id}}^\star , {\texttt {t}}, \ell ^\star )$, $\mathcal {B}_{\ell ^\star }$ submits

$$\begin{aligned} (\ell ^\star \Vert {\texttt {id}}^\star ,\textsf {T}_{[\ell ^\star -1,0]}({\texttt {t}}^\star )), \end{aligned}$$

as the HIBE challenge identity. Therefore, $\mathcal {B}_{\ell ^\star }$ can answer all $\mathcal {A}_{\ell ^\star }$’s key-insulation queries, say, $({\texttt {id}}, {\texttt {t}}, \ell )$, by making HIBE secret-key reveal queries for the corresponding identities $( (j\Vert {\texttt {id}}, \textsf {T}_{ [j-1,\ell ] }({\texttt {t}})) )_{j\in [\ell ,L]}$ as long as it holds

$$\begin{aligned} (j \Vert {\texttt {id}}, \textsf {T}_{ [j-1,\ell ] }({\texttt {t}})) \notin \textsf {prefix}^+( (\ell ^\star \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell ^\star -1,0]}({\texttt {t}}^\star )) ) \text { for all } j\in [\ell ,L], \end{aligned}$$

(2)

even without the knowledge of the challenge tuple $({\texttt {id}}^\star , {\texttt {t}}^\star )$. Since $\mathcal {B}_{\ell ^\star }$ can obtain all HIBE secret keys such that $(\ell , {\texttt {id}}) \ne (\ell ^\star , {\texttt {id}}^\star )$ via HIBE secret-key generation queries, the condition (2) can be more specific:

$$\begin{aligned} (\ell ^\star \Vert {\texttt {id}}^\star , \textsf {T}_{ [\ell ^\star -1,\ell ] }({\texttt {t}})) \notin \textsf {prefix}^+( (\ell ^\star \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell ^\star -1,0]}({\texttt {t}}^\star )) ). \end{aligned}$$

(3)

Therefore, we should care only about the key-insulation query $({\texttt {id}}^\star , {\texttt {t}}, \ell )$ that produces $(\ell ^\star \Vert {\texttt {id}}^\star , \textsf {T}_{ [\ell ^\star -1,\ell ] }({\texttt {t}}))$. In the construction, only level-$\ell$ helper keys $\textsf {hk}_{ {\texttt {id}}^\star ,\textsf {T}_{ \ell }({\texttt {t}}) }^{( \ell )}$ for $\ell \in [0,\ell ^\star ]$ include HIBE secret keys for $(\ell ^\star \Vert {\texttt {id}}^\star , \textsf {T}_{ [\ell ^\star -1,\ell ] }({\texttt {t}}))$. All possible $\mathcal {A}_{\ell ^\star }$’s queries that contradict the condition (3) are:

• the initial helper-key reveal query on ${\texttt {id}}^\star$;

• the key-insulation query on $({\texttt {id}}^\star ,{\texttt {t}},\ell ^\star )$ for any ${\texttt {t}}\in \mathcal {T}_{act}$;

• the key-insulation query on $({\texttt {id}}^\star ,{\texttt {t}},\ell )$ for any ${\texttt {t}}\in \mathcal {T}_{act}$ and any $\ell \in [0,\ell ^\star -1]$ such that $\textsf {T}_{ [\ell ^\star -1,\ell ] }({\texttt {t}}) = \textsf {T}_{[\ell ^\star -1,\ell ]}({\texttt {t}}^\star )$.

However, all the above queries are not allowed in the security game (see Definition 4). Thus, the condition (3) always holds for all $\mathcal {A}_{\ell ^\star }$’s queries.

The remaining challenge is how $\mathcal {B}_{\ell ^\star }$ embeds the challenge plaintexts $(\textsf {M}^\star _0, \textsf {M}^\star _1)$ into HIBE challenge ciphertext on $(\ell ^\star \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell ^\star -1,0]}({\texttt {t}}^\star ))$. Roughly speaking, we look at the pseudo-plaintexts of the challenge ciphertext differently: In the construction, for every $\ell \in [L]$, the HIBE ciphertext on $(\ell \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell -1,0]}({\texttt {t}}^\star ))$ is an encryption of a level-$\ell$ pseudo-plaintext $\textsf {M}_\ell \leftarrow _R\mathcal {M}$ and that on $0 \Vert {\texttt {id}}^\star$ is an encryption of $\textsf {M}\bigoplus _{\ell \in [L]}\textsf {M}_\ell$. In the reduction $\mathcal {B}_{\ell ^\star }$ sets each plaintext as follows:

• For $\ell \in [0,L] \setminus \{\ell ^\star \}$, $\mathcal {B}_{\ell ^\star }$ randomly chooses a level-$\ell$ pseudo-plaintext ${\widehat{\textsf {M}}}_\ell$ and sets an HIBE ciphertext on $(\ell \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell -1,0]}({\texttt {t}}^\star ))$ is an encryption of ${\widehat{\textsf {M}}}_\ell$. Similarly, $\mathcal {B}_{\ell ^\star }$ randomly chooses a level-0 pseudo-plaintext ${\widehat{\textsf {M}}}_0$ and sets an HIBE ciphertext on $0 \Vert {\texttt {id}}^\star$ is an encryption of ${\widehat{\textsf {M}}}_0$.

• $\mathcal {B}_{\ell ^\star }$ (implicitly) sets HIBE challenge ciphertext on $(\ell ^\star \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell ^\star -1,0]}({\texttt {t}}^\star ))$ is an encryption of $\textsf {M}^\star _b \bigoplus _{\ell \in [0,L] \setminus \{\ell ^\star \}}{\widehat{\textsf {M}}}_\ell$.

All the above pseudo-plaintexts are properly distributed.

Proof of Theorem 2

We formally describe the proof as follows. Let $\mathcal {B}_{\ell ^\star }$ be a reduction algorithm against the underlying HIBE scheme. We show how to construct $\mathcal {B}_{\ell ^\star }$ by using $\mathcal {A}_{\ell ^\star }$ as follows. At first, $\mathcal {B}_{\ell ^\star }$ is given an HIBE’s master public key $\textsf {MPK}$ from an HIBE challenger ${\mathcal {C}}$. Then, $\mathcal {B}_{\ell ^\star }$ initializes $\mathtt {HKList}= \emptyset$ and sends ${\textsf {pp}}:=\textsf {MPK}$ to an HKIBE adversary $\mathcal {A}_{\ell ^\star }$.

$\mathcal {B}_{\ell ^\star }$ answers $\mathcal {A}_{\ell ^\star }$’s queries by interacting with ${\mathcal {C}}$ as follows:

Helper-key generation query Upon a query ${\texttt {id}}$ from $\mathcal {A}_{\ell ^\star }$, $\mathcal {B}_{\ell ^\star }$ checks if $({\texttt {id}}, \cdot ) \notin \mathtt {HKList}$, and returns $\bot$ to $\mathcal {A}_{\ell ^\star }$ if this is not the case. Otherwise, $\mathcal {B}_{\ell ^\star }$ makes an HIBE secret-key query on $\ell \Vert {\texttt {id}}$ for $\ell \in [0,L] \setminus \{\ell ^\star \}$ to ${\mathcal {C}}$, receives $( {\textsf {SK}}_{ \ell \Vert {\texttt {id}} } )_{\ell \in [0,L] \setminus \{\ell ^\star \}}$, and stores a part of an initial helper key $({\texttt {id}}, ( {\textsf {SK}}_{ \ell \Vert {\texttt {id}} } )_{\ell \in [0, L] \setminus \{\ell ^\star \}})$ in $\mathtt {HKList}$. Clearly, the part of the helper keys $( {\textsf {SK}}_{ \ell \Vert {\texttt {id}} } )_{\ell \in [0, L] \setminus \{\ell ^\star \}}$ are created in the same way as the construction.

Initial helper-key reveal queries Upon a query ${\texttt {id}}$ from $\mathcal {A}_{\ell ^\star }$, $\mathcal {B}_{\ell ^\star }$ finds $( {\textsf {SK}}_{ \ell \Vert {\texttt {id}} } )_{\ell \in [0, L] \setminus \{\ell ^\star \}}$ from $\mathtt {HKList}$. $\mathcal {B}_{\ell ^\star }$ retrieves ${\textsf {SK}}_{ \ell ^\star \Vert {\texttt {id}} }$ if $\mathtt {HKList}$ also contains it.¹⁴ If not, $\mathcal {B}_{\ell ^\star }$ makes an HIBE secret-key reveal query on $\ell ^\star \Vert {\texttt {id}}$ to get ${\textsf {SK}}_{ \ell ^\star \Vert {\texttt {id}} }$ and stores it in $\mathtt {HKList}$ together with $( {\textsf {SK}}_{ \ell \Vert {\texttt {id}} } )_{\ell \in [0, L] \setminus \{\ell ^\star \}}$. Then, $\mathcal {B}_{\ell ^\star }$ creates $( \textsf {hk}_{{\texttt {id}}, 0 }^{( \ell )} )_{\ell \in [0, L]}$ by using $( {\textsf {SK}}_{ \ell \Vert {\texttt {id}} } )_{\ell \in [0, L]}$ as in the construction, and returns it to $\mathcal {A}_{\ell ^\star }$. It is obvious that $\textsf {hk}_{{\texttt {id}}, 0 }^{( \ell ^\star )}$ is created in the same way as the construction.

Key-insulation query Upon a query $({\texttt {id}}, {\texttt {t}}, \ell )$, $\mathcal {B}_{\ell ^\star }$ makes all HIBE secret-key reveal queries for $\textsf {hk}_{{\texttt {id}}, \textsf {T}_{ \ell }({\texttt {t}}) }^{( \ell )}$, i.e., queries on $( (i \Vert {\texttt {id}}, \textsf {T}_{ [i-1,\ell ] }({\texttt {t}})) )_{i \in [\ell , L]}$ to get $( {\textsf {SK}}_{ (i \Vert {\texttt {id}}, \textsf {T}_{ [i-1,\ell ] }({\texttt {t}})) } )_{i \in [\ell ,L]}$. Finally, $\mathcal {B}_{\ell ^\star }$ returns $\textsf {hk}_{{\texttt {id}}, \textsf {T}_{ \ell }({\texttt {t}}) }^{( \ell )} :=( {\textsf {SK}}_{ (i \Vert {\texttt {id}}, \textsf {T}_{ [i-1,\ell ] }({\texttt {t}})) } )_{i \in [\ell , L]}$ to $\mathcal {A}_{\ell ^\star }$. It is obvious that the helper key is properly distributed thanks to the correctness of the underlying HIBE scheme.

Challenge query Upon a query $({\texttt {id}}^\star , {\texttt {t}}^\star , \textsf {M}^\star _0, \textsf {M}^\star _1)$ from $\mathcal {A}_{\ell ^\star }$, $\mathcal {B}_{\ell ^\star }$ samples ${\widehat{\textsf {M}}}_\ell \leftarrow _R\mathcal {M}$ for $\ell \in [0, L] \setminus \{\ell ^\star \}$ and makes an HIBE challenge query on $((\ell ^\star \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell ^\star -1,0]}({\texttt {t}}^\star )), \textsf {M}^\star _0 \bigoplus _{\ell \in [0,L] \setminus \{\ell ^\star \}}{\widehat{\textsf {M}}}_\ell , \textsf {M}^\star _1 \bigoplus _{\ell \in [0,L] \setminus \{\ell ^\star \}}{\widehat{\textsf {M}}}_\ell )$, and receives an HIBE challenge ciphertext $\textsf {C}_{ (\ell ^\star \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell ^\star -1,0]}({\texttt {t}}^\star )) }^\star$. Then, $\mathcal {B}_{\ell ^\star }$ runs

• $\textsf {C}_{ (\ell \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell -1,0]}({\texttt {t}}^\star )) }^\star \leftarrow \textsf {Enc}(\textsf {MPK}, (\ell \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell -1,0]}({\texttt {t}}^\star )), {\widehat{\textsf {M}}}_\ell )$ for $\ell \in [0,L] \setminus \{\ell ^\star \}$,

and returns $( \textsf {C}_{ (\ell \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell -1,0]}({\texttt {t}}^\star )) }^\star )_{\ell \in [0,L]}$ to $\mathcal {A}_{\ell ^\star }$ as an HKIBE challenge ciphertext.

Observe that the challenge ciphertext is properly distributed by implicitly setting

• $\textsf {M}_\ell ={\widehat{\textsf {M}}}_\ell$ for $\ell \in [0, L] \setminus \{\ell ^\star \}$,

• $\textsf {M}_{\ell ^\star } = \textsf {M}^\star _b \bigoplus _{\ell \in [0,L] \setminus \{\ell ^\star \}}{\widehat{\textsf {M}}}_\ell$,

where $b \leftarrow _R \{ 0,1 \}$. Level-$\ell$ pseudo-plaintext $\textsf {M}_\ell ={\widehat{\textsf {M}}}_\ell$ for $\ell \in [L] \setminus \{\ell ^\star \}$ is created in the same way as the construction. Since the level-0 pseudo-plaintext ${\widehat{\textsf {M}}}_{0}$ is uniformly distributed over the message space of the underlying HIBE scheme, the distribution of $\textsf {M}_{\ell ^\star }$ is independent of $\textsf {M}_b^\star$ and $( {\widehat{\textsf {M}}}_{\ell } )_{\ell \in [L] \setminus \{\ell ^\star \}}$, and uniformly random in the HIBE message space as in the construction. Therefore, the distribution of $( \textsf {C}_{ (\ell \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell -1,0]}({\texttt {t}}^\star )) }^\star )_{\ell \in [L]}$is identical to that in the construction. $\textsf {C}_{ 0 \Vert {\texttt {id}}^\star }^\star$ is an encryption of $\textsf {M}^\star _b \bigoplus _{\ell \in [L]}\textsf {M}_\ell$ in the construction while it is an encryption of ${\widehat{\textsf {M}}}_0$ in the reduction. Since

$$\begin{aligned} \textsf {M}^\star _b \bigoplus _{\ell \in [L]}\textsf {M}_\ell&= \textsf {M}^\star _b \oplus \textsf {M}_{\ell ^\star } \bigoplus _{\ell \in [L] \setminus \{\ell ^\star \}}\textsf {M}_\ell \\&= \textsf {M}^\star _b \oplus \textsf {M}^\star _b \bigoplus _{\ell \in [0, L] \setminus \{\ell ^\star \}}{\widehat{\textsf {M}}}_\ell \bigoplus _{\ell \in [L] \setminus \{\ell ^\star \}}{\widehat{\textsf {M}}}_\ell \\&= {\widehat{\textsf {M}}}_0 \end{aligned}$$

holds, the distribution of $\textsf {C}_{ 0 \Vert {\texttt {id}}^\star }^\star$ is the same as that of the construction.

After $\mathcal {B}_{\ell ^\star }$ receives $b'$ from $\mathcal {A}_{\ell ^\star }$, $\mathcal {B}_{\ell ^\star }$ returns $\beta ' \leftarrow b'$ as its own guess to ${\mathcal {C}}$.

The above completes the description of $\mathcal {B}_{\ell ^\star }$. Observe that $\mathcal {B}_{\ell ^\star }$ can answer all of $\mathcal {A}$’s queries with ${\mathcal {C}}$. $\mathcal {B}_{\ell ^\star }$ makes the HIBE challenge query on

$$\begin{aligned} (\ell ^\star \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell ^\star -1,0]}({\texttt {t}}^\star )), \end{aligned}$$

while $\mathcal {B}_{\ell ^\star }$ can make HIBE secret-key reveal queries in any case for the following reasons.

• The initial helper-key reveal query on ${\texttt {id}}$.

Case for ${\texttt {id}}\ne {\texttt {id}}^\star$: It is obvious that $\mathcal {B}_{\ell ^\star }$ can make HIBE secret-key reveal queries on $\ell \Vert {\texttt {id}}$ for every $\ell \in [0,L]$.

Case for ${\texttt {id}}= {\texttt {id}}^\star$: This query is not allowed in the game.

• The key-insulation query on $({\texttt {id}},{\texttt {t}},\ell )$.

Case for ${\texttt {id}}\ne {\texttt {id}}^\star$: $\mathcal {B}_{\ell ^\star }$ can make HIBE secret-key reveal queries to return $\textsf {hk}_{{\texttt {id}}, \textsf {T}_{ \ell }({\texttt {t}}) }^{( \ell )}$.

Case for ${\texttt {id}}= {\texttt {id}}^\star$: We take look at the following three cases.

• Case for $\ell \in [\ell ^\star +1,L]$: In this case, $\textsf {hk}_{ {\texttt {id}}^\star ,\textsf {T}_{ \ell }({\texttt {t}}) }^{( \ell )}$ does not include any HIBE secret key ${\textsf {SK}}_{ (\ell ^\star \Vert {\texttt {id}}^\star , \textsf {T}_{ [\ell ^\star -1,\ell ] }({\texttt {t}})) }$, which violates the condition (3), by the construction. Therefore, $\mathcal {B}_{\ell ^\star }$ can make HIBE secret-key reveal queries on $\ell \Vert {\texttt {id}}$ and $(i \Vert {\texttt {id}},\textsf {T}_{ [i-1,\ell ] }({\texttt {t}}))$ for every $i \in [\ell +1,L]$.

• Case for $\ell = \ell ^\star$: This case never occurs due to the restriction on $\ell ^\star$.

• Case for $\ell \in [0,\ell ^\star -1]$: Since it always holds $\textsf {T}_{ \ell }({\texttt {t}}) \ne \textsf {T}_{\ell }({\texttt {t}}^\star )$ due to the restriction on $\ell ^\star$, and it means that such a query always meets the condition (3). $\mathcal {B}_{\ell ^\star }$ can make HIBE secret-key reveal queries on $\ell \Vert {\texttt {id}}$ and $(i \Vert {\texttt {id}},\textsf {T}_{ [i-1,\ell ] }({\texttt {t}}))$ for every $i \in [\ell +1,L]$.

As we already observed, $\mathcal {B}_{\ell ^\star }$ perfectly simulates the adaptive security game against $\mathcal {A}_{\ell ^\star }$. Since the probability that $\beta '$ is a correct guess is the same as that of $b'$, $\mathcal {B}_{\ell ^\star }$’s advantage is $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}_{\ell ^\star }}(\lambda ) = \textsf {Adv}^\mathtt{{HIBE}}_{\Sigma , L+1, \mathcal {B}_{\ell ^\star }}(\lambda )$. Therefore, $\mathcal {B}$’s advantage against $\mathcal {A}$ of general attack strategy is $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda ) = \sum _{\ell ^\star \in [0, L]} \textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}_{\ell ^\star }}(\lambda ) = (L+1) \cdot \textsf {Adv}^\mathtt{{HIBE}}_{\Sigma , L+1, \mathcal {B}}(\lambda )$. $\square$

As in the first construction, if the underlying HIBE scheme is selectively secure, our HKIBE scheme then satisfies selective security. We omit the proof since it can be done in the same manner as Theorem 2.

Corollary 3

If the underlying HIBE scheme with hierarchical depth $L+1$ satisfies selective security, then the above HKIBE scheme with hierarchical depth L also satisfies selective security. Specifically, if there exists an adversary $\mathcal {A}$ to break selective security of our HKIBE scheme with advantage $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )$, then there exists a reduction algorithm $\mathcal {B}$ to break selective security of the underlying HIBE scheme with advantage $\textsf {Adv}^\mathtt{{HIBE}}_{\Sigma ,L+1,\mathcal {B}}(\lambda ) \ge \textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )/\Theta (L)$.

5.4 Achieving CCA security

Unlike the first construction, we cannot obtain a CCA-secure construction by just replacing the underlying CPA-secure HIBE scheme with a CCA-secure one. In other words, simply applying the CPA-to-CCA transformation [11] in a naive way is insufficient for updating our second construction to be CCA-secure. The reason is that the second construction requires $L+1$ HIBE ciphertexts for each HKIBE ciphertext, while the ciphertext of the first construction consists of only one HIBE ciphertext. If we just replace the underlying CPA-secure HIBE scheme with a CCA-secure one, there is the following trivial attack: an adversary $\mathcal {A}$ replaces $\textsf {C}_{ 0\Vert {\texttt {id}}^\star }^\star$ of the challenge ciphertext $\textsf {ct}_{ {\texttt {id}}^\star ,{\texttt {t}}^\star }^\star$ with $\textsf {Enc}(\textsf {MPK},0\Vert {\texttt {id}}^\star ,0^{|\textsf {M}^\star _0|})$ (the modified challenge ciphertext is denoted by $\textsf {ct}_{ {\texttt {id}}^\star ,{\texttt {t}}^\star }'$), makes a decryption query on $({\texttt {id}}^\star ,{\texttt {t}}^\star ,\textsf {ct}_{ {\texttt {id}}^\star ,{\texttt {t}}^\star }')$, and receives $\bigoplus _{\ell \in [L]}\textsf {M}_{\ell }$. Similarly, $\mathcal {A}$ replaces $\textsf {C}_{ (\ell \Vert {\texttt {id}}^\star ,\textsf {T}_{[\ell -1,0]}{({\texttt {t}}^\star )}) }^\star$ of $\textsf {ct}_{ {\texttt {id}}^\star ,{\texttt {t}}^\star }^\star$ with $\textsf {Enc}(\textsf {MPK},(\ell \Vert {\texttt {id}}^\star ,\textsf {T}_{[\ell -1,0]}{({\texttt {t}}^\star )}),0^{|\textsf {M}^\star _0|})$ for all $\ell \in [L]$ (the modified challenge ciphertext is denoted by $\textsf {ct}_{ {\texttt {id}}^\star ,{\texttt {t}}^\star }''$), makes a decryption query on $({\texttt {id}}^\star ,{\texttt {t}}^\star ,\textsf {ct}_{ {\texttt {id}}^\star ,{\texttt {t}}^\star }'')$, and receives $\textsf {M}^\star _{b}\bigoplus _{\ell \in [L]}\textsf {M}_{\ell }$. Therefore, $\mathcal {A}$ can get $\textsf {M}_{b}^\star$ and win the game with probability one.

To circumvent the above attack and achieve CCA security, we apply the CPA-to-CCA transformation technique [11] to all $(L+1)$ ciphertexts of the underlying CPA-secure HIBE scheme at once, not each of them, as in the previous work [30].

One-time signature (OTS) An OTS scheme $\Gamma$ consists of three algorithms $(\textsf {SSetup}, \textsf {Sign}, \textsf {Vrfy})$.

• $\textsf {SSetup}(1^{\lambda }) \rightarrow (\textsf {sigk}, \textsf {verk})$: given the security parameter $\lambda$, it outputs a key pair $(\textsf {sigk},\textsf {verk})$.

• $\textsf {Sign}(\textsf {sigk}, \textsf {M}) \rightarrow \sigma$: given the signing key $\textsf {sigk}$ and a message $\textsf {M}$, it outputs a signature $\sigma$.

• $\textsf {Vrfy}(\textsf {verk}, \textsf {M}, \sigma ) \rightarrow \top$ or $\bot$: given the verification key $\textsf {verk}$, a message $\textsf {M}$, and its signature $\sigma$, it outputs $\top$, which indicates “acceptance”, or $\bot$, which indicates “rejection”.

We require that for all security parameters $\lambda$, $(\textsf {sigk}, \textsf {verk}) \leftarrow \textsf {SSetup}(1^{\lambda })$, and messages $\textsf {M}$, it holds $\textsf {Vrfy}(\textsf {verk},\textsf {M},\textsf {Sign}(\textsf {sigk},\textsf {M})) = \top$ with overwhelming probability.

We define a security notion for OTS. Let $\Gamma$ be an OTS scheme, and we consider a game between an adversary $\mathcal {F}$ and the challenger ${\mathcal {C}}$. The game is parameterized by the security parameter $\lambda$. The game proceeds as follows: ${\mathcal {C}}$ first runs $(\textsf {sigk}, \textsf {verk}) \leftarrow \textsf {SSetup}(1^{\lambda })$ and gives $\textsf {verk}$ to $\mathcal {A}$. $\mathcal {F}$ is allowed to make the signature generation query only once: upon a query $\textsf {M}$ from $\mathcal {F}$, ${\mathcal {C}}$ returns $\sigma \leftarrow \textsf {Sign}(\textsf {sigk}, \textsf {M})$ to $\mathcal {A}$. $\mathcal {F}$ outputs $(\textsf {M}^\star ,\sigma ^\star )$ and terminates. In this game, $\mathcal {F}$’s adaptive security advantage is defined by $\textsf {Adv}^\mathtt{{OTS}}_{\Gamma ,\mathcal {F}}(\lambda ) :=\Pr [\textsf {Vrfy}(\textsf {verk},\textsf {M}^\star ,\sigma ^\star ) \rightarrow \top \wedge (\textsf {M}^\star ,\sigma ^\star ) \ne (\textsf {M},\sigma )]$.

Definition 5

(Strong Unforgeability) We say that an OTS scheme $\Gamma$ satisfies strong unforgeability, if the advantage $\textsf {Adv}^\mathtt{{OTS}}_{\Gamma ,\mathcal {F}}(\lambda )$ is negligible for all PPT adversaries $\mathcal {F}$.

Construction First of all, we change the maximum hierarchy depth $L+1$ of the underlying HIBE scheme to $L+2$. We then modify the $\textsf {Encrypt}$ and $\textsf {Decrypt}$ algorithms of the second construction as follows.

• : Parse ${\textsf {pp}}=\textsf {MPK}$. Generate $(\textsf {sigk},\textsf {verk}) \leftarrow \textsf {SSetup}(1^{\lambda })$. Sample $\textsf {M}_\ell \leftarrow _R\mathcal {M}$ for $\ell \in [L]$ and run

$\cdot$:

$\textsf {C}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}}),\textsf {verk}) } \leftarrow \textsf {Enc}(\textsf {MPK}, (\ell \Vert {\texttt {id}}, \textsf {T}_{[\ell -1,0]}{({\texttt {t}})},\textsf {verk}), \textsf {M}_\ell )$ for $\ell \in [L]$,

$\cdot$:

$\textsf {C}_{ (0 \Vert {\texttt {id}},\textsf {verk}) } \leftarrow \textsf {Enc}(\textsf {MPK}, (0 \Vert {\texttt {id}},\textsf {verk}), \textsf {M}\bigoplus _{\ell \in [L]}\textsf {M}_\ell )$,

$\cdot$:

$\sigma \leftarrow \textsf {Sign}(\textsf {sigk}, ( \textsf {C}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{[\ell -1,0]}{({\texttt {t}})},\textsf {verk}) } )_{\ell \in [0,L]})$,

then output . Here, $(0 \Vert {\texttt {id}}, \textsf {T}_{[-1,0]}, \textsf {verk})$ means $(0\Vert {\texttt {id}}, \textsf {verk})$.

• : Parse

$\triangleright$:

${\textsf {pp}}=\textsf {MPK}$,

$\triangleright$:

$\textsf {dk}_{{\texttt {id}}, \textsf {T}_{ 0 }({\texttt {t}})} = \textsf {hk}_{{\texttt {id}}, \textsf {T}_{ 0 }({\texttt {t}}) }^{( 0 )} = (( {\textsf {SK}}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}})) } )_{\ell \in [0,L]})$,

$\triangleright$:

.

Compute $\textsf {Vrfy}(\textsf {verk}, ( \textsf {C}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{[\ell -1,0]}{({\texttt {t}})},\textsf {verk}) } )_{\ell \in [0,L]},\sigma )$. If the output is $\bot$, then output $\bot$. Otherwise, for $\ell \in [L]$, run

$\cdot$:

${\textsf {SK}}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}}),\textsf {verk}) } \qquad \qquad \leftarrow \textsf {GenSK}(\textsf {MPK}, {\textsf {SK}}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}})) }, (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}}),\textsf {verk}))$,

$\cdot$:

$\textsf {M}_\ell \leftarrow \textsf {Dec}(\textsf {MPK}, {\textsf {SK}}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}}),\textsf {verk}) }, \textsf {C}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}}),\textsf {verk}) })$,

Compute ${\textsf {SK}}_{ (0 \Vert {\texttt {id}},\textsf {verk}) } \leftarrow \textsf {GenSK}(\textsf {MPK}, {\textsf {SK}}_{ 0 \Vert {\texttt {id}} }, (0 \Vert {\texttt {id}},\textsf {verk}))$. Output

$\cdot$:

$\textsf {M}= \textsf {Dec}(\textsf {MPK}, {\textsf {SK}}_{ (0 \Vert {\texttt {id}},\textsf {verk}) }, \textsf {C}_{ (0\Vert {\texttt {id}},\textsf {verk}) }) \bigoplus _{\ell \in [L]}\textsf {M}_\ell$.

Rest of the algorithms are the same as those of the CPA-secure construction.

Theorem 3

If the underlying HIBE scheme with hierarchical depth $L+2$ satisfies (adaptive-identity) CPA security and the underlying OTS scheme satisfies strong unforgeability, then the above HKIBE scheme with hierarchical depth L also satisfies (adaptive-identity) CCA security. Specifically, if there exists an adversary $\mathcal {A}$ to break (adaptive-identity) CCA security of our HKIBE scheme with advantage $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )$, then there exists a reduction algorithm $\mathcal {B}$ to break adaptive-identity CPA security of the underlying HIBE scheme with advantage $\textsf {Adv}^\mathtt{{HIBE}}_{\Sigma ,L+2,\mathcal {B}}(\lambda ) \ge \textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )/\Theta (L)$ or a reduction algorithm $\mathcal {F}$ to break strong unforgeability of the underlying OTS scheme with advantage $\textsf {Adv}^\mathtt{{OTS}}_{\Gamma ,\mathcal {F}}(\lambda ) \ge \textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )$.

Proof

First of all, we consider two types of adversaries $\mathcal {A}$:

$\triangleright$:

$\mathcal {A}$ makes at least one decryption query that includes valid $\textsf {verk}^\star$, which is a challenge verification key generated at the beginning of the game.¹⁵ Here, “valid” $\textsf {verk}^\star$ means $\textsf {verk}^\star$ such that it holds $\textsf {Vrfy}(\textsf {verk}^\star , ( \textsf {C}_{ (\ell \Vert {\texttt {id}},\textsf {T}_{ [\ell -1,0] }({\texttt {t}}),\textsf {verk}^\star ) } )_{\ell \in [0,L]}, \sigma ) = \top$, where is a ciphertext of the decryption query.

$\triangleright$:

$\mathcal {A}$ does not make any decryption query that includes valid $\textsf {verk}^\star$.

If $\mathcal {A}$ is the former type, we can construct a reduction algorithm $\mathcal {F}$ against the underlying OTS scheme. Otherwise, i.e., if $\mathcal {A}$ is the latter type, we can construct a reduction algorithm $\mathcal {B}$ against the underlying HIBE scheme. The rest of the proof follows from the following Lemmas 1 and 2.

Lemma 1

If there exists an adversary $\mathcal {A}$ to break adaptive-identity CCA security of our HKIBE scheme with advantage $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )$ and $\mathcal {A}$ makes at least one decryption query that includes valid $\textsf {verk}^\star$, then there exists a reduction algorithm $\mathcal {F}$ to break strong unforgeability of the underlying OTS scheme with advantage $\textsf {Adv}^\mathtt{{OTS}}_{\Gamma ,\mathcal {F}}(\lambda ) \ge \textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )$.

Proof

At first, $\mathcal {F}$ is given a challenge verification key $\textsf {verk}^\star$ from an OTS challenger ${\mathcal {C}}$, and computes $(\textsf {MPK},\textsf {MSK}) \leftarrow \textsf {Init}(1^\lambda , L+2)$. Then, $\mathcal {F}$ initializes $\mathtt {HKList}= \emptyset$ and sends ${\textsf {pp}}:=\textsf {MPK}$ to an HKIBE adversary $\mathcal {A}$. $\mathcal {F}$ can answer all helper-key generation queries, initial helper-key reveal queries, key-insulation queries, and decryption queries since $\mathcal {F}$ has $\textsf {MSK}$. We here explicitly describe the challenge query.

Challenge query Upon a query $({\texttt {id}}^\star , {\texttt {t}}^\star , \textsf {M}^\star _0, \textsf {M}^\star _1)$ from $\mathcal {A}$, $\mathcal {F}$ samples $b \leftarrow _R \{ 0,1 \}$ and ${\widehat{\textsf {M}}}_\ell \leftarrow _R\mathcal {M}$ for $\ell \in [L]$ and runs

• $\textsf {C}_{ (\ell \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell -1,0]}({\texttt {t}}^\star ),\textsf {verk}^\star ) }^\star \leftarrow \textsf {Enc}(\textsf {MPK}, (\ell \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell -1,0]}({\texttt {t}}^\star ),\textsf {verk}^\star ), {\widehat{\textsf {M}}}_\ell )$ for $\ell \in [L]$,

• $\textsf {C}_{ (0 \Vert {\texttt {id}}^\star ,\textsf {verk}^\star ) }^\star \leftarrow \textsf {Enc}(\textsf {MPK}, (0 \Vert {\texttt {id}}^\star ,\textsf {verk}^\star ), \textsf {M}_b \bigoplus _{\ell \in [L]}{\widehat{\textsf {M}}}_{\ell }).$

$\mathcal {F}$ then makes a signature generation query $( \textsf {C}_{ (\ell \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell -1,0]}({\texttt {t}}^\star ),\textsf {verk}^\star ) }^\star )_{\ell \in [0,L]}$ and receives $\sigma ^\star$. $\mathcal {F}$ returns $( ( \textsf {C}_{ (\ell \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell -1,0]}({\texttt {t}}^\star ),\textsf {verk}^\star ) }^\star )_{\ell \in [0,L]}, \textsf {verk}^\star , \sigma ^\star )$ to $\mathcal {A}$.

At some point, $\mathcal {A}$ makes a decryption query such that

$$\begin{aligned} \textsf {Vrfy}(\textsf {verk}^\star , ( \textsf {C}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}}),\textsf {verk}^\star ) } )_{\ell \in [0,L]}, \sigma ) = \top , \end{aligned}$$

where . $\mathcal {F}$ then outputs $(( \textsf {C}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}}),\textsf {verk}^\star ) } )_{\ell \in [0,L]}, \sigma )$ as a forgery and terminates the game. Due to the restriction on decryption query, it holds

$$\begin{aligned} ( ( \textsf {C}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}}),\textsf {verk}^\star ) } )_{\ell \in [0,L]}, \textsf {verk}^\star , \sigma ) \ne ( ( \textsf {C}_{ (\ell \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell -1,0]}({\texttt {t}}^\star ),\textsf {verk}^\star ) }^\star )_{\ell \in [0,L]}, \textsf {verk}^\star ,\sigma ^\star ). \end{aligned}$$

Hence, $\mathcal {F}$ breaks strong unforgeability of the underlying OTS scheme, and we have $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda ) \le \textsf {Adv}^\mathtt{{OTS}}_{\Gamma , \mathcal {F}}(\lambda )$ if $\mathcal {A}$ queries at least one decryption query that includes valid $\textsf {verk}^\star$. $\square$

Lemma 2

If there exists an adversary $\mathcal {A}$ to break adaptive-identity CCA security of our HKIBE scheme with advantage $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )$ and $\mathcal {A}$ does not make any decryption query that includes valid $\textsf {verk}^\star$, then there exists a reduction algorithm $\mathcal {B}$ to break adaptive-identity CPA security of the underlying HIBE scheme with advantage $\textsf {Adv}^\mathtt{{HIBE}}_{\Sigma ,L+2,\mathcal {B}}(\lambda ) \ge \textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda )/\Theta (L)$.

Proof

We can prove this theorem in the same manner as Theorem 2. We divide $\mathcal {A}$’s attack strategy into $L+1$ types (with $\Theta (L)$ reduction loss), and show the proof against $\mathcal {A}$ of the Type-$\ell ^\star$ strategy (denoted by $\mathcal {A}_{\ell ^\star }$) for fixed $\ell ^\star$. Let $\mathcal {B}_{\ell ^\star }$ be a reduction algorithm against the underlying HIBE scheme. We show how to construct $\mathcal {B}_{\ell ^\star }$ by using $\mathcal {A}_{\ell ^\star }$ that does not make any decryption query that includes valid $\textsf {verk}^\star$.

At first, $\mathcal {B}_{\ell ^\star }$ is given an HIBE’s master public key $\textsf {MPK}$ from an HIBE challenger ${\mathcal {C}}$, and computes $(\textsf {sigk}^\star ,\textsf {verk}^\star ) \leftarrow \textsf {SSetup}(1^\lambda )$. Then, $\mathcal {B}_{\ell ^\star }$ initializes $\mathtt {HKList}= \emptyset$ and sends ${\textsf {pp}}:=\textsf {MPK}$ to an HKIBE adversary $\mathcal {A}_{\ell ^\star }$. $\mathcal {B}_{\ell ^\star }$ can answer all queries except for decryption and challenge queries in the same way as in the proof of Theorem 2. Therefore, we here describe how to answer decryption queries (that does not include valid $\textsf {verk}^\star$) and challenge query.

Decryption query Upon a query from $\mathcal {A}_{\ell ^\star }$, $\mathcal {B}_{\ell ^\star }$ checks the following two conditions:

$\triangleright$:

$({\texttt {id}}, \cdot ) \notin \mathtt {HKList}$,

$\triangleright$:

$\textsf {Vrfy}(\textsf {verk},( \textsf {C}_{ (\ell \Vert {\texttt {id}},\textsf {T}_{ [\ell -1,0] }({\texttt {t}}),\textsf {verk}) } )_{\ell \in [0,L]}, \sigma ) = \bot$,

where . If at least one condition holds, $\mathcal {B}_{\ell ^\star }$ returns $\bot$. Otherwise, $\mathcal {B}_{\ell ^\star }$ makes HIBE secret key queries on $(0\Vert {\texttt {id}},\textsf {verk})$ and $(\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}}), \textsf {verk})$ for $\ell \in [L]$, and obtains ${\textsf {SK}}_{ (0\Vert {\texttt {id}},\textsf {verk}) }$ and ${\textsf {SK}}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}}), \textsf {verk}) }$ for $\ell \in [L]$. From the assumption that $\mathcal {A}_{\ell ^\star }$ never makes any decryption queries that include valid $\textsf {verk}^\star$, $\textsf {verk}\ne \textsf {verk}^\star$ holds. Therefore, $\mathcal {B}_{\ell ^\star }$ can get the corresponding HIBE secret keys even if $({\texttt {id}},{\texttt {t}}) = ({\texttt {id}}^\star ,{\texttt {t}}^\star )$ for any decryption queries. $\mathcal {B}_{\ell ^\star }$ then runs

$\cdot$:

$\textsf {M}_\ell \leftarrow \textsf {Dec}(\textsf {MPK}, {\textsf {SK}}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}}),\textsf {verk}) }, \textsf {C}_{ (\ell \Vert {\texttt {id}}, \textsf {T}_{ [\ell -1,0] }({\texttt {t}}),\textsf {verk}) })$ for $\ell \in [L]$,

$\cdot$:

$\textsf {M}:=\textsf {Dec}(\textsf {MPK}, {\textsf {SK}}_{ (0 \Vert {\texttt {id}},\textsf {verk}) }, \textsf {C}_{ (0\Vert {\texttt {id}},\textsf {verk}) }) \bigoplus _{\ell \in [L]}\textsf {M}_\ell$.

$\mathcal {B}_{\ell ^\star }$ returns $\textsf {M}$ to $\mathcal {A}_{\ell ^\star }$.

Challenge query Upon a query $({\texttt {id}}^\star , {\texttt {t}}^\star , \textsf {M}^\star _0, \textsf {M}^\star _1)$ from $\mathcal {A}_{\ell ^\star }$, $\mathcal {B}_{\ell ^\star }$ samples ${\widehat{\textsf {M}}}_\ell \leftarrow _R\mathcal {M}$ for $\ell \in [0, L] \setminus \{\ell ^\star \}$ and makes an HIBE challenge query on $((\ell ^\star \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell ^\star -1,0]}({\texttt {t}}^\star ), \textsf {verk}^\star ), \textsf {M}^\star _0 \bigoplus _{\ell \in [0,L] \setminus \{\ell ^\star \}}{\widehat{\textsf {M}}}_\ell , \textsf {M}^\star _1 \bigoplus _{\ell \in [0,L] \setminus \{\ell ^\star \}}{\widehat{\textsf {M}}}_\ell )$, and receives an HIBE challenge ciphertext $\textsf {C}_{ (\ell ^\star \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell ^\star -1,0]}({\texttt {t}}^\star ),\textsf {verk}^\star ) }$. Then, $\mathcal {B}_{\ell ^\star }$ runs

• $\textsf {C}_{ (\ell \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell -1,0]}({\texttt {t}}^\star ),\textsf {verk}^\star ) } \leftarrow \textsf {Enc}(\textsf {MPK}, (\ell \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell -1,0]}({\texttt {t}}^\star ),\textsf {verk}^\star ), {\widehat{\textsf {M}}}_\ell )$ for $\ell \in [0,L] \setminus \{\ell ^\star \}$,

• $\sigma ^\star \leftarrow \textsf {Sign}(\textsf {sigk}^\star , ( \textsf {C}_{ (\ell \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell -1,0]}({\texttt {t}}^\star ),\textsf {verk}^\star ) } )_{\ell \in [0,L]})$.

Finally, $\mathcal {B}_{\ell ^\star }$ returns $( ( \textsf {C}_{ (\ell \Vert {\texttt {id}}^\star , \textsf {T}_{[\ell -1,0]}({\texttt {t}}^\star ),\textsf {verk}^\star ) } )_{\ell \in [0,L]}, \sigma ^\star , \textsf {verk}^\star )$ to $\mathcal {A}_{\ell ^\star }$ as an HKIBE challenge ciphertext.

Based on the same observation as in Theorem 2, the challenge ciphertext is properly distributed by implicitly setting

• $\textsf {M}_\ell ={\widehat{\textsf {M}}}_\ell$ for $\ell \in [0, L] \setminus \{\ell ^\star \}$,

• $\textsf {M}_{\ell ^\star } = \textsf {M}^\star _b \bigoplus _{\ell \in [0,L] \setminus \{\ell ^\star \}}{\widehat{\textsf {M}}}_\ell$ for $b \in \{0,1\}$.

After $\mathcal {B}_{\ell ^\star }$ receives $b'$ from $\mathcal {A}_{\ell ^\star }$, $\mathcal {B}_{\ell ^\star }$ returns $\beta ' :=b'$ as its own guess to ${\mathcal {C}}$.

As we already observed, $\mathcal {B}_{\ell ^\star }$ perfectly simulates the adaptive security game against $\mathcal {A}_{\ell ^\star }$. Since the probability that $\beta '$ is a correct guess is the same as that of $b'$, $\mathcal {B}_{\ell ^\star }$’s advantage is $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}_{\ell ^\star }}(\lambda ) = \textsf {Adv}^\mathtt{{HIBE}}_{\Sigma , L+2, \mathcal {B}_{\ell ^\star }}(\lambda )$ if $\mathcal {A}_{\ell ^\star }$ does not query any decryption query that includes valid $\textsf {verk}^\star$. Thus, we set $\mathcal {B}:=(\mathcal {B}_{0}, \ldots , \mathcal {B}_{L})$ and have $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda ) = \sum _{\ell ^\star \in [0, L]} \textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}_{\ell ^\star }}(\lambda ) \le \sum _{\ell ^\star \in [0, L]} \textsf {Adv}^\mathtt{{HIBE}}_{\Sigma ,L+2,\mathcal {B}_{\ell ^\star }}(\lambda ) = (L+1) \cdot \textsf {Adv}^\mathtt{{HIBE}}_{\Sigma , L+2, \mathcal {B}}(\lambda )$. $\square$

Proof of Theorem 3. Taken together, we have $\textsf {Adv}^\mathtt{{HKIBE}}_{\Pi ,L,\mathcal {A}}(\lambda ) \le (L+1) \cdot \textsf {Adv}^\mathtt{{HIBE}}_{\Sigma , L+1, \mathcal {B}}(\lambda ) + \textsf {Adv}^\mathtt{{OTS}}_{\Gamma , \mathcal {F}}(\lambda )$. $\square$

Appendix A Overview of the bug in the security Proof in [52]

The SW18 scheme [52] is flawed due to improper handling of dual system encryption [57]. We start from the basic concept of the dual system encryption and observe the bug in the security proof in [52]. Note that the earlier version [55] also contains the same bug. We follow the notations and terminologies used in the main body.

Dual system encryption Dual system encryption is one of the well-known techniques to prove adaptive security of plain HIBE, and utilizes two kinds of distributions for ciphertexts and secret keys. One is distributions that appear in a construction, called the normal distribution, and the other is distributions that only appear in the security proof, called the semi-functional distribution. Although normal secret keys can decrypt both normal and semi-functional ciphertexts, semi-functional secret keys cannot decrypt semi-functional ciphertexts. During the security proof, we first change a challenge ciphertext to be semi-functional, then change all secret keys queried by an adversary to be semi-functional one by one. Essentially, the reason why the changes succeed is that, in plain HIBE, the adversary is not allowed to query the challenge identity or its ancestors. Since the adversary completely loses decryption capability after the changes, it is easy to replace the underlying plaintext of the challenge ciphertext with a random one without being noticed by the adversary.

The overview of the bug To the authors’ credit, the SW18 scheme is the same as our first construction instantiated by [46]. It means that the flaw is due to the proof methodology they employed, not their construction. The proof of [52] employs dual system encryption in a naïve manner; the challenge ciphertext is first changed to be semi-functional, then all helper keys and decryption keys are changed to be semi-functional one by one. However, the latter changes failed in the sense that the changed keys do not distribute properly as the authors expected or an adversary is able to detect the changes. What is essential here is that the HKIBE adversary is allowed to make key-insulation queries on the challenge identity ${\texttt {id}}^\star$, whereas the HIBE adversary does not make any secret-key reveal queries on ${\texttt {ID}}^\star$. We explain the details below.

HIBE proof using dual system encryption If the adversary is allowed to make a query on the prefix of the challenge identity, the simulation fails since the randomness of the secret key for the query would be correlated to the randomness of the challenge ciphertext. Nevertheless, such a query is not allowed during the security game. Therefore, the dual system encryption goes through since the reduction algorithm does not need to create and reveal information on ${\texttt {ID}}^\star$ except for the challenge ciphertext $\textsf {C}_{ {\texttt {ID}}^\star }$; the randomness for $\textsf {C}_{ {\texttt {ID}}^\star }$ is independent of randomness for any secret keys from the viewpoint of the adversary.

Proof of [52] The HKIBE challenge ciphertext $\textsf {ct}_{ {\texttt {id}}^\star ,{\texttt {t}}^\star }$ can be regarded as a ciphertext for $({\texttt {id}}^\star , \textsf {T}_{[L-1,0]}({\texttt {t}}^\star ))$ in the HIBE scheme proposed by [46]. The randomness of the challenge ciphertext $\textsf {ct}_{ {\texttt {id}}^\star ,{\texttt {t}}^\star } :=\textsf {C}_{ ({\texttt {id}}^\star ,\textsf {T}_{[L-1,0]}({\texttt {t}}^\star )) }$ is correlated to the randomness of level-$\ell$ helper keys $\textsf {hk}_{{\texttt {id}}, \textsf {T}_{ \ell }({\texttt {t}}) }^{( \ell )}$ for the key-insulation query on $({\texttt {id}}^\star , {\texttt {t}}, \ell )$ such that $\ell > \ell ^\star$. This is due to the form of $\textsf {hk}_{{\texttt {id}}, \textsf {T}_{ \ell }({\texttt {t}}) }^{( \ell )}$: roughly speaking, the level-$\ell$ helper key $\textsf {hk}_{{\texttt {id}}, \textsf {T}_{ \ell }({\texttt {t}}) }^{( \ell )}$ is the HIBE secret key of [46] for a hierarchical identity $({\texttt {id}},\textsf {T}_{ [L-1,\ell ] }({\texttt {t}}))$ masked with a random group element. The adversary is allowed to make the key-insulation query $({\texttt {id}}^\star , {\texttt {t}}^\star , \ell \ (>\ell ^\star ))$, and hence can obtain the HIBE secret key of [46] for a hierarchical identity $({\texttt {id}}^\star ,\textsf {T}_{[L-1,\ell ]}({\texttt {t}}^\star )) \in \textsf {prefix}^+( ({\texttt {id}}^\star ,\textsf {T}_{[L-1,0]}({\texttt {t}}^\star )) )$ (with a random mask). As mentioned above, in the standard HIBE game, a query on such a hierarchical identity, i.e., the prefix of the challenge identity, is not allowed and spoils dual system encryption. The authors seemed to expect that the random mask of $\textsf {hk}_{ {\texttt {id}}^\star ,\textsf {T}_{\ell }({\texttt {t}}^\star ) }^{( \ell )}$ would help to resolve the issue, however, it does not; the query still leads to the correlation. Thus, the simulation fails when the adversary obtains both $\textsf {ct}_{ {\texttt {id}}^\star ,{\texttt {t}}^\star }$ and $\textsf {hk}_{ {\texttt {id}}^\star ,\textsf {T}_{\ell }({\texttt {t}}^\star ) }^{( \ell )}$ for $\ell \in [\ell ^\star +1,L]$.