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

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‐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: 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.

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.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.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.

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.

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\).

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.

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})\).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|\).

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. Formally, MSK evaluatability is defined as follows.

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.

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:

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:

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}}\):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: 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: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|\).

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}\).

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. 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).

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. and output . Run and output . Run 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}}')) })\). Run and outputCorrectness. 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.

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

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 holdseven 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.

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 runFinally, \(\mathcal {B}_{\ell ^\star }\) returnsto \(\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 onwhile \(\mathcal {B}_{\ell ^\star }\) makes HIBE secret-key reveal queries on the following identity \({\texttt {id}}_q \ (q \in [Q])\):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.

The aim of our second construction is to get rid of MSK evaluatability from the first construction while keeping 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.

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. then output .

Output \(( \textsf {hk}_{{\texttt {id}}, 0 }^{( \ell )} )_{\ell \in [0,L]}\). For \(i \in [\ell +1,L]\), run 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]}\). 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]}\). For \(\ell \in [L]\), run OutputCorrectness. 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.

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

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 }\) submitsas 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 holdseven 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: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: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:All the above pseudo-plaintexts are properly distributed.

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.

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})\).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 )]\).

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. then output . Here, \((0 \Vert {\texttt {id}}, \textsf {T}_{[-1,0]}, \textsf {verk})\) means \((0\Vert {\texttt {id}}, \textsf {verk})\). 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 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

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

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.

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 \)