You Can Sign but Not Decrypt: Hierarchical Integrated Encryption and Signature

Abstract

Recently, Chen et al. (ASIACRYPT 2021) introduced a notion called hierarchical integrated signature and encryption (HISE), which provides a new principle for combining public key schemes. It uses a single public key for both signature and encryption schemes, and one can derive a decryption key from the signing key but not vice versa. Whereas, they left the dual notion where the signing key can be derived from the decryption key as an open problem.

In this paper, we resolve the problem by formalizing the notion called hierarchical integrated encryption and signature (HIES). Similar to HISE, it features a unique public key for both encryption and signature components and has a two-level key derivation mechanism, but reverses the hierarchy between signing key and decryption key, i.e. one can derive a signing key from the decryption key but not vice versa. This property enables secure delegation of signing capacity in the public key reuse setting. We present a generic construction of HIES from constrained identity-based encryption. Furthermore, we instantiate our generic HIES construction and implement it. The experimental result demonstrates that our HIES scheme is comparable to the best Cartesian product combined public-key scheme in terms of efficiency, and is superior in having richer functionality as well as retaining merits of key reuse.

1 Introduction

Combined usage of public key schemes is a practically relevant topic in the context of public key cryptography, especially combining public key encryption (PKE) and signature schemes. In many real-word applications, the two primitives are commonly used in combination to guarantee confidentiality and authenticity simultaneously, such as secure communication software (like PGP [2], WhatsApp [5]) and privacy-preserving cryptocurrency (like Zether [10], PGC [13]).

Typically, there are two principles for combining these two schemes, key separation and key reuse, each of which has its own strengths and weaknesses. Key separation, which means using two independent key pairs for two schemes, supports secure escrow¹ for both signing key and decryption key, while the key management and certificate costs² are doubled. Key reuse, which means using a unique key pair for both PKE and signature schemes, can reduce key management and certificate costs, but it does not support secure key escrow, and its joint security is not immediate.

Recently, Chen et al. [14] proposed a new notion called hierarchical integrated signature and encryption (HISE), which strikes a sweet balance between key separation and key reuse. It employs a single public key for both encryption and signature schemes, and allows one to derive a decryption key from signing key. This feature gives HISE advantages that (i) key management and certificate costs are reduced by half and (ii) secure delegation of decryption capacity is admitted.

Nevertheless, since the signing key is regarded as the master key in HISE, it is not applicable to some scenarios such as where one wants to delegate his signing capacity while retaining his decryption capacity. Chen et al. remarked that it is possible to consider a dual version of HISE, and it could be useful in scenarios where decryption capability is a first priority. However, they did not give the formal definition, construction and applications of it, and left it as an open problem. Therefore, the motivation for this work is two-fold: (i) find a proper key usage strategy for scenarios where key management costs are desired to be cheap, and signature delegation is needed; (ii) solve the open problem left in [14], and complete the key usage strategies.

1.1 Our Contributions

In this work, we resolve the open problem in [14] and our contributions can be summarized as follows:

Formal Definition of HIES. We start off by formalizing the definition and the joint security of the dual notion of HISE, called hierarchical integrated encryption and signature (HIES). It allows one to derive a signing key from the decryption key, such that secure delegation of signature capacity is allowed. In terms of joint security, the PKE component is IND-CCA secure even when the adversary is given the signing key and the signature component is EUF-CMA secure in the presence of an additional decryption oracle.

Generic Construction from CIBE. We present a generic construction of HIES from constrained identity-based encryption (CIBE) and give a rigorous proof of its joint security.

Fig. 1.

HISE and HIES from CIBE

Our generic construction is inspired by HISE from CIBE. We notice that CIBE inherently implies a binary tree, where the root node is served as Private Key Generator (PKG) who possesses the master secret key, and each leaf node is viewed as a user, specified by an ID, who owns an ID-based private key. Indeed, each ID can be interpreted as identifying a unique path from root node to corresponding leaf node. We refer the reader to Sect. 2.3 for formal definition of CIBE. As for HISE from CIBE (shown as Fig. 1(a)), users each forms a CIBE binary tree, employs the master secret key of the root node as the signing key, and lets the secret key of its right child node be the decryption key, i.e. $sk_{f_{\textbf {1}}}$, the secret key for prefix predicate $f_{{\textbf {1}}}$, from which all secret keys for ID prefixed with “1" can be derived (we use $sk_{f_{\textbf {v}}}$ to denote the constrained secret key for prefix predicate $f_{\textbf {v}}$, where $f_{\textbf {v}}(\text {ID})=1$ iff ID prefixed with ${\textbf {v}}$). Thus, the whole tree is divided into two parts. The left one containing IDs prefixed with “0" is used for PKE component and the right one containing IDs prefixed with “1" is used for signature component. Based on above observations, we naturally get a construction of HIES by switching the roles the two secret keys play (shown in Fig. 1(b)).

Extensions. We propose three extensions with different purposes. The first one is for flexible delegation, with which the user is able to delegate his/her decryption and signing capacities separately to different entities. It is actually the combination of HISE and HIES. The second is for limited delegation, with which the user can limit the decryption or signing capacity given to the escrow. The last one is for finegrained delegation, which is designed to generate keys labeled by time or identifier information. We believe these extensions is useful in scenarios where delegation is not straightforward.

Applications. We give several scenarios where HIES is useful. The first one is a concern reported in [7]. In a confidential payment system like Zether [10] and PGC [13], which currently is equipped with a key reuse mechanism, if the signing key needs to be revoked or rotated, then all encrypted assets of an account need to be transferred to a new account, which leads to high overhead. While there is no such trouble if HIES is used, in which one can derive time labeled signing keys. The second one is the following scenario discussed in Viafirma [4]. In a company, the president needs to deal with multifarious documents everyday, including but not limited to commercial contracts, applications for the procurement of goods and so on. It is quite necessary to delegate his signing right to assistant presidents so that they can help settle documents which are less important. Meanwhile, the president may require keeping the decryption key secret for the security of some confidential business documents. Many similar scenarios where signature delegation is needed widely appear in other institutions, such as schools and government departments [1, 3].

Indeed, signature delegation, also known as Proxy Signature which was first introduced by Mambo et al. [28], has numerous applications, such as distributed systems [29], mobile agent [26] and electronic commerce [16]. Various schemes and extensions of it were proposed during the last few decades [8, 12, 22,23,24, 34]. In contrast to these schemes, HIES not only considers delegating signing right, but also combines an additional PKE scheme without increasing the size of public key, yielding a scheme with richer functionality. In general, HIES is suitable for the scenarios where low key management costs are desired, while the signing key is not permanent, or the signature delegation is needed.

Instantiation and Implementation. We instantiate our HIES and implement it with 128-bit security. The performance of our HIES scheme is comparable to the best Cartesian product combined public-key scheme [30] in terms of efficiency, and is superior in having richer functionality as well as retaining merits of key reuse.

1.2 Related Works

Here we briefly review the works related to combined usage of public key schemes.

Key Separation. It is the folklore principle for combining PKE and signature schemes, which indicates using two independent key pairs for two public key schemes. Paterson et al. formalized it via the notion of “Cartesian product” combined public key scheme (CP-CPK) [30], which means using arbitrary encryption and signature schemes as components, and combining two key pairs into one simply through concatenating the public/private keys of the component schemes. They pointed out that CP-CPK provides a benchmark by which other constructions can be judged, so we use it as a baseline.

Key Reuse. The first work to formally study the security of key reuse was by Haber and Pinkas [20]. They introduced the concept of a combined public key (CPK) scheme, where an encryption scheme and a signature scheme are combined. CPK preserves the existing algorithms of sign, verify, encrypt and decrypt, while the two key generation algorithms are modified into a single algorithm, which outputs two key pairs for PKE and signature components respectively, with the key pairs no longer necessarily being independent. In addition, they formalized the joint security of CPK scheme, i.e., the encryption component is IND-CCA secure even in the presence of an additional signing oracle, and the signature component is EUF-CMA secure even in the presence of an additional decryption oracle. Integrated signature and encryption (ISE) is an extreme case of CPK. It uses an identical key pair for both PKE and signature components, which in turn makes it not support key delegation. In subsequent works, both Coron et al. [15] and Komano et al. [25] considered building ISE from trapdoor permutations in the random oracle model. Paterson et al. [30] gave an ISE construction from identity-based encryption.

Hierarchical Integrated Signature and Encryption. It is a new notion presented by Chen et al. in [14]. HISE employs a unique public key for both PKE and signature components, and serves the signing key as the master secret key from which the decryption key can be derived. Thus, HIES supports secure delegation of decryption power and achieves stronger joint security than ISE, that is, the encryption component is IND-CCA secure even in the presence of an additional signing oracle, while the signature component is EUF-CMA secure even in the presence of the decryption key.

Our notion is dual to HISE, where the hierarchy between signing key and decryption key is reversed. It completes the last piece of the key usage strategy puzzle, as shown in Fig. 2. We use index e to indicate keys for PKE component and s to signature component.

Fig. 2.

Different key usage strategies

2 Preliminaries

Notations. We use $m\xleftarrow {\text {R}}M$ to denote that m is sampled uniformly at random from a set M and $y\leftarrow A(x)$ to denote the algorithm A that on input x outputs y. We use the abbreviation PPT to indicate probabilistic polynomial-time. We denote by $\textsf{negl}(\lambda )$ a negligible function in $\lambda$. Let tuple $\left( \mathbb {G}_{1},\mathbb {G}_{2}, \mathbb {G}_{T}, p, g_{1}, g_{2}, e\right)$ denote the descriptions of asymmetric pairing groups where $\mathbb {G}_{1}$, $\mathbb {G}_{2}$ and $\mathbb {G}_{T}$ are cyclic groups of the same prime order p, and $g_{1},g_{2}$ are generators of $\mathbb {G}_{1} , \mathbb {G}_{2}$ respectively, and $e:\mathbb {G}_{1}\times \mathbb {G}_{2}\rightarrow \mathbb {G}_{T}$ is the bilinear map.

2.1 Public Key Encryption

Definition 1

A public key encryption (PKE) scheme consists of four polynomial-time algorithms:

• $\textsf{Setup}(1^\lambda )$: on input a security parameter $\lambda$, outputs public parameters pp, including the descriptions of plaintext space $\mathcal {M}$, ciphertext space $\mathcal {C}$, and randomness space $\mathcal {R}$.

• $\textsf{KeyGen}(pp)$: on input public parameters pp, outputs a public encryption key ek and a secret decryption key dk.

• $\textsf{Enc}(ek, m)$: on input an encryption key ek and a plaintext m, outputs a ciphertext c.

• $\textsf{Dec}(dk, c)$: on input a decryption key dk and a ciphertext c, outputs a plaintext m or a special reject symbol $\bot$ denoting failure. This algorithm is typically deterministic.

Correctness. For any $pp\leftarrow \textsf{Setup}(1^\lambda )$, any $(ek, dk) \leftarrow \textsf{KeyGen}(pp)$, any $m \in \mathcal {M}$ and any $c \leftarrow \textsf{Enc}(ek, m)$, it holds that $\textsf{Dec}(dk, c) = m$.

Security. Let $\mathcal {O}_\textsf{dec}$ be a decryption oracle that on input a ciphertext, outputs a plaintext. A public key encryption scheme is IND-CCA secure if for any PPT adversary $\mathcal {A}$ there is a negligible function $\textsf{negl}(\lambda )$ such that:

$$\begin{aligned} \Pr \left[ \beta =\beta ': \begin{array}{l} pp \leftarrow \textsf{Setup}(1^\lambda ); \\ (ek, dk) \leftarrow \textsf{KeyGen}(pp);\\ (m_0, m_1) \leftarrow \mathcal {A}^{\mathcal {O}_\textsf{dec}}(pp, ek);\\ \beta \xleftarrow {\text {R}}\{0, 1\}, c^* \leftarrow \textsf{Enc}(ek, m_\beta ); \\ \beta ' \leftarrow \mathcal {A}^{\mathcal {O}_\textsf{dec}}(c^*); \end{array} \right] \le \frac{1}{2}+ \textsf{negl}(\lambda ) . \end{aligned}$$

$\mathcal {A}$ is not allowed to query $\mathcal {O}_\textsf{dec}$ for $c^{*}$ in the guess stage. The IND-CPA security can be defined similarly by denying the decryption oracle.

2.2 Digital Signature

Definition 2

A digital signature scheme consists of four polynomial-time algorithms:

• $\textsf{Setup}(1^\lambda )$: on input the security parameter $\lambda$, outputs public parameters pp, including the descriptions of message space $\mathcal {M}$ and signature space $\varSigma$.

• $\textsf{KeyGen}(pp)$: on input pp, outputs a public verification key vk and a secret signing key sk.

• $\textsf{Sign}(sk, m)$: on input a signing key sk and a message m, outputs a signature $\sigma$.

• $\textsf{Vrfy}(vk, m, \sigma )$: on input a verification key vk, a message m, and a signature $\sigma$, outputs a bit b, with $b=1$ meaning valid and $b=0$ meaning invalid.

Correctness. For any $(vk,sk)\leftarrow \textsf{KeyGen}(pp)$, any $m \in \mathcal {M}$ and any $\sigma \leftarrow \textsf{Sign}(sk, m)$, it holds that $\textsf{Vrfy}(pk, m, \sigma ) = 1$.

Security. Let $\mathcal {O}_\textsf{sign}$ be a signing oracle that on input a message, outputs a signature. A digital signature scheme is EUF-CMA secure if for any PPT adversary $\mathcal {A}$ there is a negligible function $\textsf{negl}(\lambda )$ such that:

$$\begin{aligned} \Pr \left[ \begin{array}{c} \textsf{Vrfy}(vk, m^*, \sigma ^*)=1\\ \wedge ~m^* \notin \mathcal {Q} \end{array}: \begin{array}{l} pp \leftarrow \textsf{Setup}(1^\lambda );\\ (vk, sk) \leftarrow \textsf{KeyGen}(pp);\\ (m^*, \sigma ^*) \leftarrow \mathcal {A}^{\mathcal {O}_\textsf{dec}}(pp, vk);\\ \end{array} \right] \le \textsf{negl}(\lambda ). \end{aligned}$$

The set $\mathcal {Q}$ records queries to $\mathcal {O}_\textsf{sign}$. The strong EUF-CMA security can be defined similarly by asking $\mathcal {A}$ to output a fresh valid message-signature tuple. The one-time signature can also be defined similarly by restricting the adversary to access $\mathcal {O}_\textsf{sign}$ only once.

2.3 Constrained Identity-Based Encryption

We recall the definition of constrained IBE introduced by Chen et al. [14] below.

Definition 3

A constrained identity-based encryption (CIBE) scheme consists of seven polynomial-time algorithms:

• $\textsf{Setup}(1^\lambda )$: on input a security parameter $\lambda$, outputs public parameters pp. Let $\mathcal {F}$ be a family of predicates over identity space $\mathcal {I}$.

• $\textsf{KeyGen}(pp)$: on input public parameters pp, outputs a master public key mpk and a master secret key msk.

• $\textsf{Extract}(msk, id)$: on input a master secret key msk and an identity $id \in \mathcal {I}$, outputs a user secret key $sk_{id}$.

• $\textsf{Constrain}(msk, f)$: on input a master secret key msk and a predicate $f \in \mathcal {F}$, outputs a constrained secret key $sk_f$.

• $\textsf{Derive}(sk_f, id)$: on input a constrained secret key $sk_f$ and an identity $id \in \mathcal {I}$, outputs a user secret key $sk_{id}$ if $f(id) = 1$ or $\bot$ otherwise.

• $\textsf{Enc}(mpk, id, m)$: on input mpk, an identity $id \in \mathcal {I}$, and a message m, outputs a ciphertext c.

• $\textsf{Dec}(sk_{id}, c)$: on input a user secret key $sk_{id}$ and a ciphertext c, outputs a message m or a special reject symbol $\bot$ denoting failure.

Correctness. For any $pp\leftarrow \textsf{Setup}(1^\lambda )$, any $(mpk, msk) \leftarrow \textsf{KeyGen}(pp)$, any identity $id \in \mathcal {I}$, any $sk_{id} \leftarrow \textsf{Extract}(msk, id)$, any message m, and any $c \leftarrow \textsf{Enc}(mpk, id, m)$, it always holds that $\textsf{Dec}(sk_{id}, c) = m$. Besides, for any $f \in \mathcal {F}$ such that $f(id) = 1$, the outputs of $\textsf{Extract}(msk, id)$ and $\textsf{Derive}(sk_f, id)$ have the same distribution.

Security. Let $\mathcal {O}_\textsf{extract}$ be an oracle of $\textsf{Extract}$ that on input an identity id outputs $sk_{id}$. Let $\mathcal {O}_\textsf{constrain}$ be an oracle of $\textsf{Constrain}$ that on input a predicate f outputs $sk_{f}$. A CIBE scheme is IND-CPA secure, if for all PPT adversary $\mathcal {A}$ there is a negligible function $\textsf{negl}(\lambda )$ suth that:

$$\begin{aligned} \Pr \left[ \beta =\beta ': \begin{array}{l} pp \leftarrow \textsf{Setup}(1^\lambda ); \\ (mpk, msk) \leftarrow \textsf{KeyGen}(pp);\\ (id^{*},(m_{0},m_{1}))\leftarrow \mathcal {A}^{\mathcal {O}_\textsf{extract},\mathcal {O}_\textsf{constrain}} (pp,mpk);\\ \beta {\mathop {\leftarrow }\limits ^{R}}\{0,1\},c^{*}\leftarrow \textsf{Enc}(mpk,id^{*},m_{\beta });\\ \beta '\leftarrow \mathcal {A}^{\mathcal {O}_\textsf{extract},\mathcal {O}_\textsf{constrain}}(c^{*}); \end{array} \right] \le \frac{1}{2}+\textsf{negl}(\lambda ). \end{aligned}$$

$\mathcal {A}$ is not allowed to query the $\mathcal {O}_\textsf{extract}$ with $id^{*}$ or query the $\mathcal {O}_\textsf{constrain}$ with f such that $f(id^{*})=1$. Meanwhile, two weaker security notions can be defined similarly. One is OW-CPA security, in which the adversary is required to recover the plaintext from a random ciphertext. The other is selective-identity IND-CPA security, in which the adversary must commit ahead of time (non-adaptively) to the identity it intends to attack before seeing the mpk.

3 Hierarchical Integrated Encryption and Signature

3.1 Definition of HIES

As mentioned in the introduction, HIES allows one to derive the signing key from the decryption key, which is opposite to HISE. Next, we give a self-contained description of the formal definition of HIES.

Definition 4

A hierarchical integrated encryption and signature (HIES) scheme is defined by seven polynomial-time algorithms:

• $\textsf{Setup}(1^\lambda )$: on input a security parameter $\lambda$, outputs public parameters pp including the description of plaintext space $\mathcal {M}$ and message space $\mathcal {\widetilde{M}}$.

• $\textsf{KeyGen}(pp)$: on input public parameters pp, outputs a public key pk and a decryption key dk. Here, dk serves as a master secret key, which can be used to derive signing key.

• $\textsf{Derive}(dk)$: on input a decryption key dk, outputs a signing key sk.

• $\textsf{Enc}(pk, m)$: on input a public key pk and a plaintext $m \in \mathcal {M}$, outputs a ciphertext c.

• $\textsf{Dec}(dk, c)$: on input a decryption key dk and a ciphertext c, outputs a plaintext m or a special reject symbol $\bot$ denoting failure.

• $\textsf{Sign}(sk, \widetilde{m})$: on input a signing key sk and a message $\widetilde{m} \in \mathcal {\widetilde{M}}$, outputs a signature $\sigma$.

• $\textsf{Vrfy}(pk, \widetilde{m}, \sigma )$: on input a public key pk, a message $\widetilde{m}$, and a signature $\sigma$, outputs a bit b, with $b=1$ meaning valid and $b=0$ meaning invalid.

Correctness. The correctness of HIES is divided into two parts, the correctness of PKE and signature components: (i) the PKE component satisfies correctness if for any $pp \leftarrow \textsf{Setup}(1^\lambda )$, any $(pk, dk) \leftarrow \textsf{KeyGen}(pp)$, any $m\in \mathcal {M}$ and any $c\leftarrow \textsf{Enc}(pk,m)$, it holds that $\textsf{Dec}(dk, c)=m$; (ii) the signature component satisfies correctness if for any $pp \leftarrow \textsf{Setup}(1^\lambda )$, any $(pk,dk)\leftarrow \textsf{KeyGen}(pp)$, any $sk \leftarrow \textsf{Derive}(dk)$, any $\widetilde{m} \in \mathcal {\widetilde{M}}$ and any $\sigma \leftarrow \textsf{Sign}(sk, \widetilde{m})$, it holds that $\textsf{Very}(pk, \widetilde{m}, \sigma ) = 1$.

Security. (Joint security) The joint security for HIES needs to be considered from two aspects as well. The PKE component requires to satisfy IND-CCA security in the presence of a signing key and the signature component requires to satisfy EUF-CMA security in the presence of a decryption oracle. Let $\mathcal {O}_\textsf{dec}$ be the decryption oracle and $\mathcal {O}_\textsf{sign}$ be the signing oracle. The formal security notion is defined as below.

Definition 5

HIES is joint secure if its encryption and signature components satisfy the following security notions:

• (i) The PKE component is IND-CCA secure in the presence of a signing key, if for any PPT adversary $\mathcal {A}$ there is a negligible function $\textsf{negl}(\lambda )$ such that:

  $$\begin{aligned} \Pr \left[ \beta =\beta ': \begin{array}{l} pp \leftarrow \textsf{Setup}(1^\lambda ); \\ (pk, dk) \leftarrow \textsf{KeyGen}(pp);\\ sk \leftarrow \textsf{Derive}(dk);\\ (m_{0},m_{1})\leftarrow \mathcal {A}^{\mathcal {O}_\textsf{dec}} (pp,pk,sk);\\ \beta {\mathop {\leftarrow }\limits ^{R}}\{0,1\},c^{*}\leftarrow \textsf{Enc}(pk,m_{\beta });\\ \beta '\leftarrow \mathcal {A}^{\mathcal {O}_\textsf{dec}}(c^{*}); \end{array} \right] \le \frac{1}{2}+\textsf{negl}(\lambda ). \end{aligned}$$

  $\mathcal {A}$ is not allowed to query $\mathcal {O}_\textsf{dec}$ with $c^{*}$ in the guess stage.

• (ii) The signature component is EUF-CMA secure in the presence of a decryption oracle, if for all PPT adversary $\mathcal {A}$ there is a negligible function $\textsf{negl} (\lambda )$ such that:

  $$\begin{aligned} \Pr \left[ \begin{array}{c} \textsf{Vrfy}(pk,m^{*},\sigma ^{*})=1\\ \wedge m^{*}\notin \mathcal {Q} \end{array} : \begin{array}{l} pp \leftarrow \textsf{Setup}(1^\lambda ); \\ (pk, dk) \leftarrow \textsf{KeyGen}(pp);\\ (m^{*},\sigma ^{*})\leftarrow \mathcal {A}^{\mathcal {O}_\textsf{dec},\mathcal {O}_\textsf{sign}} (pp,pk);\\ \end{array} \right] \le \textsf{negl}(\lambda ). \end{aligned}$$

  The set $\mathcal {Q}$ records queries to $\mathcal {O}_\textsf{sign}$.

3.2 HIES from Constrained IBE

In this section, we give a generic construction of HIES from constrained identity-based encryption. Let CIBE be a constrained IBE scheme and OTS be a strong one-time signature scheme, then an HIES scheme can be created as Fig. 3. We assume the identity space of CIBE is $\mathcal {I}=\{0,1\}^{\ell +1}$, and the verification space of OTS is $\{0,1\}^{\ell }$.

Fig. 3.

A generic construction of HIES from CIBE

The correctness of the scheme follows directly from the correctness of CIBE and OTS. The joint security of the HIES scheme is formalized as below.

Theorem 1

Assume CIBE satisfies IND-CPA security and OTS satisfies strong EUF-CMA security, then the HIES scheme constructed as Fig. 3 satisfies joint security.

This theorem comes straightforwardly from two lemmas.

Lemma 1

If CIBE scheme is OW-CPA secure, then the signature component is EUF-CMA secure in the presence of the decryption oracle.

Proof

If there exists a PPT adversary $\mathcal {A}$ against the signature component, we can construct a PPT adversary $\mathcal {B}$ that uses $\mathcal {A}$ as a subroutine and attacks the CIBE. $\mathcal {B}$ is given public parameters $pp_\text {cibe}$, public key mpk and access to $\mathcal {O}_\textsf{extract}$ and $\mathcal {O}_\textsf{constrain}$ by its own challenger $\mathcal{C}\mathcal{H}_\text {cibe}$, then it simulates $\mathcal {A}$’s challenger $\mathcal{C}\mathcal{H}_\text {sign}$ as below.

• Setup: $\mathcal {B}$ runs $pp_\text {ots}\leftarrow \text {OTS}.\textsf{Setup}(1^{\lambda })$, sets $pp=(pp_\text {cibe},pp_\text {ots})$ and $pk=mpk$, then sends (pp, pk) to $\mathcal {A}$.

• Signing query: when $\mathcal {A}$ requests a signature on message $\widetilde{m}$, $\mathcal {B}$ queries $\mathcal {O}_\textsf{extract}$ with identity $id =1||\widetilde{m}$ to obtain $sk_{id}$, outputs $\sigma =sk_{id}$.

• Decryption query: when $\mathcal {A}$ requests the plaintext of a ciphertext c, $\mathcal {B}$ first parses c as $(ovk, c_\text {cibe}, \sigma _\text {ots})$, then checks whether $\text {OTS}.\textsf{Vrfy}(ovk, c_\text {cibe}, \sigma _\text {ots})=1$, and returns $\bot$ if not; else it queries $\mathcal {O}_\textsf{extract}$ for $id=0||ovk$ to obtain $sk_{id}$ and returns the plaintext $m \leftarrow \text {CIBE}.\textsf{Dec}(sk_{id}, c_\text {cibe})$ to $\mathcal {A}$.

• Forgery: when $\mathcal {A}$ outputs a forged message-signature pair $(\widetilde{m}^{*},\sigma ^{*})$, $\mathcal {B}$ first submits $id^{*} =1||\widetilde{m}$ as the target identity to $\mathcal{C}\mathcal{H}_\text {cibe}$ and receives back $c^{*}_{cibe}\leftarrow \text {CIBE}.\textsf{Enc}(mpk,id^{*},m)$ for a random plaintext $m\xleftarrow {\text {R}}\mathcal {M}$, then it parses $\sigma ^{*}=sk_{id^{*}}$, and computes $m'\leftarrow \text {CIBE}.\textsf{Dec}(sk_{id^{*}},c^{*}_{cibe})$. $\mathcal {B}$ wins if $m'=m$.

The view of $\mathcal {A}$ when it interacts with $\mathcal {B}$ is identical to the view of $\mathcal {A}$ interacting with a real challenger, which implies the simulation of $\mathcal {B}$ is perfect. If no PPT adversary $\mathcal {B}$ has non-negligible probability to break the OW-CPA security of the CIBE scheme, then no PPT adversary $\mathcal {A}$ has non-negligible probability to break the EUF-CMA security of signature component. This proves Lemma 1.

Lemma 2

If the OTS scheme satisfies strong EUF-CMA security and the CIBE scheme satisfies selective-identity IND-CPA security, then the encryption component PKE satisfies IND-CCA security even in the presence of signing key.

Proof

Consider following games. Let $\mathcal {A}$ be an adversary against the PKE component and $S_{i}$ be the event that $\mathcal {A}$ wins in Game i.

Game 0

This is the standard IND-CCA security experiment for PKE component in the presence of a signing key, $\mathcal{C}\mathcal{H}_\text {pke}$ interacts with $\mathcal {A}$ as below.

• Setup: $\mathcal{C}\mathcal{H}_\text {pke}$ runs $pp_\text {cibe} \leftarrow \text {CIBE}. \textsf{Setup}(1^\lambda )$ and $pp_\text {ots} \leftarrow \text {OTS}.\textsf{Setup}(1^\lambda )$, sets $pp=(pp_\text {cibe},pp_\text {ots})$, then runs $(mpk, msk)\leftarrow \text {CIBE}.\textsf{KeyGen}(pp_\text {cibe})$ , sets $pk=mpk$ and $dk=msk$, runs $sk\leftarrow \textsf{Derive}(dk)$, and gives (pp, pk, sk) to $\mathcal {A}$.

• Decryption query: upon receiving a ciphertext c, $\mathcal{C}\mathcal{H}_\text {pke}$ first parses $c = (ovk, c_\text {cibe}, \sigma )$, checks if $\text {OTS}.\textsf{Vrfy}(ovk, c_\text {cibe}, \sigma )=1$, outputs $\bot$ if not; else sets $id=0||ovk$, parses $dk=msk$, runs $sk_{id}\leftarrow \text {CIBE}.\textsf{Extract}(msk,id)$ and outputs $m \leftarrow \text {CIBE}.\textsf{Dec}(sk_{id}, c_\text {cibe})$.

• Challenge: $\mathcal {A}$ outputs a pair of messages $(m_{0}$,$m_{1})$. $\mathcal{C}\mathcal{H}_\text {pke}$ chooses a random bit $b\xleftarrow {\text {R}}\{0,1\}$, runs $(ovk^{*}, osk^{*}) \leftarrow \text {OTS}.\textsf{KeyGen}(pp_\text {ots})$, sets $id^{*} = 0||ovk^{*}$, computes $c^{*}_\text {cibe} \leftarrow \text {CIBE}.\textsf{Enc}(mpk, id^{*}, m_{b})$, and $\sigma ^{*} \leftarrow \text {OTS}.\textsf{Sign}(osk^{*}, c^{*}_\text {cibe})$, outputs $c^{*} = (ovk^{*}, c^{*}_\text {cibe}, \sigma ^{*})$ to $\mathcal {A}$. Then $\mathcal {A}$ can continue to query the decryption oracle, but it is not allowed to query for $c^{*}$.

• Guess: Eventually, $\mathcal {A}$ outputs a bit $b'$. $\mathcal {A}$ wins if $b'=b$.

Game 1

Same as Game 0 except that $\mathcal{C}\mathcal{H}_\text {pke}$ generates the OTS keypair $(ovk^{*},osk^{*}) \leftarrow \text {OTS}.\textsf{KeyGen}(pp_\text {ots})$ in the setup stage rather than in the challenge stage. The modification is only conceptual and does not affect the advantage of $\mathcal {A}$, so we have:

$$\begin{aligned} \Pr \left[ S_{1}\right] =\Pr \left[ S_{0}\right] . \end{aligned}$$

Game 2

Same as Game 1 except that the experiment directly aborts when one of following two events happens:

$E_{1}$::

in phase 1, $\mathcal {A}$ queries the decryption oracle with $c=(ovk^{*}, c_\text {cibe}, \sigma )$ such that $\text {OTS}.\textsf{Vrfy}(ovk^{*}, c_\text {cibe}, \sigma )=1$.

$E_{2}$::

in phase 2, $\mathcal {A}$ queries the decryption oracle with $c=(ovk^{*}, c^{*}_\text {cibe}, \sigma )$ such that $\text {OTS}.\textsf{Vrfy}(ovk^{*}, c^{*}_\text {cibe}, \sigma )=1$ and $\sigma \ne \sigma ^{*}$.

Let E be the event that $E_{1}$ or $E_{2}$ happens, then we have (Game 1 $\wedge \, \lnot E)=($Game 2 $\wedge \, \lnot E)$. According to the difference lemma, we have:

$$\begin{aligned} \left| \Pr \left[ S_{2}\right] -\Pr \left[ S_{1}\right] \right| \le \Pr \left[ E\right] . \end{aligned}$$

Actually, the two events mean a successful attack on the OTS, while the strong EUF-CMA security of OTS ensures that for any PPT $\mathcal {A}$, it holds that $\Pr \left[ E\right] = \textsf{negl}(\lambda )$.

Claim 1

If the CIBE scheme is selective-identity IND-CPA secure, then for any PPT adversary $\mathcal {A}$, there is a negligible function $\textsf{negl}(\lambda )$ such that:

$$\begin{aligned} \left| \Pr \left[ S_{2}\right] -\frac{1}{2}\right| \le \textsf{negl}(\lambda ). \end{aligned}$$

Proof

Let $\mathcal {B}$ be an adversary against CIBE scheme. It is given public parameters $pp_\text {cibe}$ and access to $\mathcal {O}_\textsf{extract}$ and $\mathcal {O}_\textsf{constrain}$ by its own challenger $\mathcal{C}\mathcal{H}_\text {cibe}$. $\mathcal {B}$ simulates $\mathcal {A}$’s challenger as below.

• Setup: $\mathcal {B}$ runs $pp_\text {ots}\leftarrow \text {OTS}.\textsf{Setup}(1^{\lambda })$, $(ovk^{*},osk^{*})\leftarrow \text {OTS}.\textsf{KeyGen}(pp_\text {ots})$, sets $id^{*}=0||ovk^{*}$, then commits to $id^{*}$ and sends the commitment to its own challenger $\mathcal{C}\mathcal{H}_\text {cibe}$ as the target identity and receives back public key $pk=mpk$. Next, $\mathcal {B}$ queries $\mathcal {O}_\textsf{constrain}$ with $f_\textbf{1}$, and obtains the signing key $sk=sk_{f_\textbf{1}}$. $\mathcal {B}$ gives $pp=(pp_\text {cibe},pp_\text {ots})$, $pk=mpk$ and $sk=sk_{f_\textbf{1}}$ to $\mathcal {A}$.

• Decryption query: When $\mathcal {A}$ queries for a ciphertext $c=(ovk,c_\text {cibe},\sigma )$, $\mathcal {B}$ first checks whether $\text {OTS}.\textsf{Vrfy}(ovk,c_\text {cibe},\sigma )=1$, if not, outputs $\bot$; else if $ovk=ovk^{*}$ which means event $E_{1}$ happens, $\mathcal {B}$ aborts; otherwise it must have $ovk\ne ovk^{*}$, $\mathcal {B}$ queries $\mathcal {O}_\textsf{extract}$ with $id=0||ovk$ to obtain $sk_{id}$, and outputs $m\leftarrow \text {CIBE}.\textsf{Dec}(sk_{id},c_\text {cibe})$.

• Challenge: $\mathcal {A}$ submits two messages $(m_{0},m_{1})$ to $\mathcal {B}$. $\mathcal {B}$ sends the two messages to its own challenger and receives back a ciphertext $c_\text {cibe}^{*}$ which is a ciphertext of $m_{b}$ under the target identity $id^{*}=0||ovk^{*}$. $\mathcal {B}$ proceeds to compute a signature $\sigma ^{*}$ on $c_\text {cibe}^{*}$, then sends $c^{*}=(ovk^{*},c_\text {cibe}^{*},\sigma ^{*})$ to $\mathcal {A}$.

• Guess: Upon receiving $c^{*}$, $\mathcal {A}$ continues to query decryption oracle but is not allowed to query it with $c^{*}$. If $E_{2}$ happens, $\mathcal {B}$ aborts. Else it answers the query as before. Finally, $\mathcal {A}$ outputs $b'$, and $\mathcal {B}$ uses $b'$ as its own guess.

The view of $\mathcal {A}$ when it interacts with $\mathcal {B}$ is identical to the view of $\mathcal {A}$ in experiment Game 2 which implies the simulation of $\mathcal {B}$ is perfect. Due to the selective-identity IND-CPA security of CIBE, the advantage of $\mathcal {A}$ wins in Game 2 is negligible. This proves Claim 1.

Therefore, the proof of Lemma 2 is completed.

Remark 1

We strengthen PKE component to IND-CCA security via the Canetti-Halevi-Katz (CHK) transform [11] with the help of a one-time signature. To enhance the efficiency, we can get rid of OTS and use an $id_{0}=0^{\ell +1}$ as a fixed target identity for encryption, then apply the Fujisaki-Okamoto transformation [17] to achieve the IND-CCA security in the random oracle model.

4 Further Discussion

In this section, we discuss three simple extensions of HIES for different delegation purposes and each of them is in the public key reuse setting. The key observation is that the prefix predicates in a constrained IBE can be assigned different and specific meanings.

Flexible Delegation. One delegation function is insufficient sometimes, such as the cases when the president wants to give his signing right to his assistants and give his decryption right to vice president. Thus, it is attractive to give a more flexible notion that enables the secret key owner to delegate these two types of authorities to different entities. The key technique is equalizing two secret keys by deriving them both from the master secret key as shown in Fig. 4(a). It is evident that the extended version satisfies united joint security as long as the two agents are not in collusion, namely the PKE/signature component is IND-CCA secure even when the adversary is given the signing/decryption key.

Limited Delegation. In the signature proxy function introduced by Mambo et al. [27], the full delegation ( giving the full original secret key to the proxy signer) requests the proxy is authentic, since the proxy signer has the ability to sign any message and the proxy signature is indistinguishable from the created by the original signer. The decryption proxy suffers the similar discomfort if the decryption key is disclosed. In order to limit the decryption and signing capacity of proxy, we consider an extension which supports partial delegation. It divides the decryption/signing capacity into two parts so that the original user can retain the higher power while delegating partial power to agents as shown in Fig. 4(b).

Finegrained Delegation. Giving the prefix predicates with more specific meanings such as the ID (identifier information such as email address) of a person or the number of a department, more finegrained delegation keys can be derived.

Fig. 4.

Extensions of HIES from constrained IBE

5 Instantiation and Implementation

5.1 Instantiation of HIES

Towards efficient realizations, we choose the hierarchical IBE (cf. Appendix A.1) rather than the constrained IBE to instantiate our HIES scheme, where the security can be similarly demonstrated. By choosing Boneh-Boyen two-level hierarchical IBE scheme ($\mathsf {BB_{1}\text {-}IBE}$, cf. Appendix A.2), we instantiate our HIES scheme as below.

• $\textsf{Setup}(1^\lambda )$: on input the security parameter $\lambda$, generates an asymmetric pairing tuple $\left( \mathbb {G}_{1},\mathbb {G}_{2}, \mathbb {G}_{T}, p, g_{1}, g_{2}, e\right)$, picks two collision resistant hash functions $\textsf{H}_{j}:\{0,1\}^{*}\rightarrow \mathbb {G}_{2}$ for $j=1,2$, sets $\textsf{ID}_{0}=0^{n}$ and $\textsf{ID}_{1}=1^{n}$ with $n=\Theta (\lambda )$. The public parameter $pp=\left( \left( \mathbb {G}_{1},\mathbb {G}_{2}, \mathbb {G}_{T}, p, g_{1}, g_{2}, e\right) , \textsf{H}_{1}, \textsf{H}_{2}, \textsf{ID}_{0}, \textsf{ID}_{1}\right)$. The plaintext space is $\mathbb {G}_{T}$. The message space is $\{0,1\}^{*}$.

• $\textsf{KeyGen}(pp)$: on input the public parameters pp, picks a random $\alpha \in \mathbb {Z}_{p}$, sets $f_{1}=g_{1}^{\alpha }$ and $f_{2}=g_{2}^{\alpha }$, sets public key $mpk=f_{1}=g_{1}^{\alpha }$ and decryption key $dk=msk=f_{2}=g_{2}^{\alpha }$.

• $\textsf{Derive}(dk)$: on input the decryption key dk, picks a random $r'\in \mathbb {Z}_{p}$, computes $d'_{0}=dk\cdot \textsf{H}_{1}(\textsf{ID}_{1}) ^{r'}$ and $d'_{1}=g_{1}^{r'}$, outputs $sk=\left( d'_{0},d'_{1} \right) \in (\mathbb {G}_{2},\mathbb {G}_{1})$.

• $\textsf{Enc}(pk, m)$: on input the public key $pk=mpk$ and a plaintext $m\in \mathbb {G}_{T}$, firstly picks a random $s\in \mathbb {Z}_{p}$ and computes $A=e(f_{1},g_{2})^{s}\cdot m$, $B=g_{1}^{s}$ and $C_{1}=\textsf{H}_{1}(\textsf{ID}_{0})^{s}$, outputs $c=\left( A,B,C_{1} \right) \in (\mathbb {G}_{T},\mathbb {G}_{1},\mathbb {G}_{2})$.

• $\textsf{Dec}(dk, c)$: on input $dk=f_{2}=g_{2}^{\alpha }$ and a ciphertext $c=\left( A,B,C_{1} \right)$, picks a random $r''\in \mathbb {Z}_{p}$, computes $d''_{0}=dk\cdot \textsf{H}_{1}(\textsf{ID}_{0}) ^{r''}$ and $d''_{1}=g_{1}^{r''}$, outputs $A\cdot e(d''_{1},C_{1})/e(B,d''_{0})=m$.

• $\textsf{Sign}(sk, \widetilde{m})$: on input a signing key $sk=sk_{\textsf{ID}_{1}}=\left( d'_{0},d'_{1} \right)$ and a message $\widetilde{m}\in \{0,1\}^{*}$, first picks a random $r\in \mathbb {Z}_{p}$, computes $d_{0}=d'_{0}\cdot \textsf{H}_{2}(\widetilde{m})^{r}$, $d_{1}=d'_{1}$ and $d_{2}=g_{1}^{r}$, outputs $\sigma =sk_\textsf{ID}=\left( d_{0},d_{1},d_{2}\right) \in (\mathbb {G}_{2},\mathbb {G}_{1},\mathbb {G}_{1})$.

• $\textsf{Vrfy}(pk, \widetilde{m}, \sigma )$: on input the public key $pk=mpk=f_{1}$, a message $\widetilde{m}\in \{0,1\}^{*}$ and a signature $\sigma =sk_\textsf{ID}=\left( d_{0},d_{1},d_{2}\right)$, outputs 1 if following equation holds, otherwise outputs 0.

  $$\begin{aligned} e\left( f_{1},g_{2}\right) \cdot e\left( d_{1},\textsf{H}_{1}(\textsf{ID}_{1})\right) \cdot e\left( d_{2},\textsf{H}_{2}(\widetilde{m})\right) =e\left( g_{1},d_{0}\right) . \end{aligned}$$

Remark 2

We simplify the $\textsf{Vrfy}$ algorithm based on the fact that if $\sigma$ is a valid signature for $\widetilde{m}$, then it can be used as the secret key for user $\textsf{ID}=\left\langle \textsf{ID}_{1}, \widetilde{m}\right\rangle$ to successfully decrypt any ciphertext $c=(A,B,C_{1},C_{2})$ for any plaintext m encrypted by mpk via $\mathsf {BB_{1}\text {-}IBE}$. Specifically, for any randomness s, it always holds that $e\left( f_{1},g_{2}\right) ^{s}\cdot e\left( d_{1},C_{1}\right) \cdot e\left( d_{2},C_{2}\right) =e\left( B,d_{0}\right)$.

5.2 Implementation

Since our HIES is a newly proposed notion, there is no similar schemes can be used to judge its performance. As mentioned before (see Sect. 1.2), the “Cartesian product” construction of combined public key (CP-CPK) scheme introduced by Paterson et al. [30], which uses arbitrary public key encryption and signature schemes as components, provides a benchmark for any bespoke construction. Thus, we build a concrete CP-CPK scheme by choosing the most efficient encryption and signature schemes, i.e. ElGamal PKE and Schnorr signature and use it as a baseline.

We implement the concrete CP-CPK scheme atop elliptic curve secp256k1 with 128-bit security in which $|\mathbb {G}|=256$ bits and $|\mathbb {Z}_{p}|=256$ bits, and implement our HIES scheme atop pairing-friendly curve bls12-381 with 128-bit security level [32] in which $|\mathbb {G}_1| = 381$ bits, $|\mathbb {G}_2| = 762$ bits, $|\mathbb {Z}_p| = 256$ bits, and $|\mathbb {G}_T| = 1524$ bits (by exploiting compression techniques [31]).

Both of them are implemented in C++ based on the mcl library [33], and all the experiments are carried out on a MacBook Pro with Intel i7-9750H CPU (2.6 GHz) and 16 GB of RAM. Our implementation is released on GitHub and is available on https://github.com/yuchen1024/HISE/tree/master/hies. The code follows KEM-DEM paradigm.

Table 1. Efficiency comparison between CP-CPK and our HIES scheme

Table 1 offers a comparison of HIES against the previous CP-CPK. In terms of functionality, it shows that HIES is in the public key reuse setting while CP-CPK is not. Moreover, HIES reduces the key management and key certificate costs. In terms of the experimental results, we admit the efficiency of our HIES scheme is slower than CP-CPK, but it is fortunately still considerable.

6 Conclusion

In this work, we resolve the problem left in [14] by formalizing the definition and the joint security of HIES. Similar to HISE, HIES also has a two-level key derive system, but the hierarchy between signing key and decryption key are reversed, thus it enables secure delegation of signature capacity. In addition, we present a generic construction of HIES from constrained identity-based encryption and give a rigorous proof of its joint security. Furthermore, we discuss three simple extensions of HIES for different delegation purposes. In the end, we implement our HIES scheme with 128-bit security. Though the construction here is a straightforward variant of HISE from constrained IBE, we emphasize the theoretical significance of HIES for completing the last piece of the key usage strategy puzzle. We leave the more ingenious and efficient constructions for future work.

A Hierarchical Identity-Based Encryption

Hierarchical identity-based encryption (HIBE) is first introduced in [19, 21]. We formally describe the definition of HIBE below. In an HIBE scheme, users having a position in the hierarchy, are specified by an ID-tuple $\textsf{ID}=\left( I_{1},\cdots ,I_{j}\right)$, where $I_{i}$ corresponds to the identity at level i.

1.1 A.1 Definition of HIBE

Definition 6

A hierarchical identity-based encryption scheme consists of five polynomial-time algorithms:

• $\textsf{Setup}(1^\lambda )$: on input a security parameter $\lambda$, outputs public parameters pp, including the plaintext space $\mathcal {M}$, the ciphertext space $\mathcal {C}$ and the identity space $\mathcal {I}$ in every level.

• $\textsf{KeyGen}(pp)$: on input the public parameters pp, outputs a public key mpk and a master secret key msk (i.e. root secret in level-0).

• $\textsf{Extract}(mpk,sk_{\textsf{ID}},\left\langle \textsf{ID},I\right\rangle )$: on input the public key mpk, a secret key for ID-tuple $\textsf{ID}$, and an ID-tuple $\left\langle \textsf{ID},I\right\rangle$ which is a child node of $\textsf{ID}$, outputs $sk_{\left\langle \textsf{ID},I\right\rangle }$.

• $\textsf{Enc}(mpk, \textsf{ID}, m)$: on input public key mpk, the ID-tuple of the intended message recipient $\textsf{ID}$ and a message $m\in \mathcal {M}$, outputs a ciphertext $c\in \mathcal {C}$.

• $\textsf{Dec}(sk_\textsf{ID},c)$: on input a secret key $sk_\textsf{ID}$ and a ciphertext c, outputs a message m or a special reject symbol $\bot$ denoting failure.

Correctness. An HIBE scheme is correct, if encryption algorithm $\textsf{Enc}$ and decryption algorithm $\textsf{Dec}$ satisfy the standard consistency constraint, namely, when $sk_\textsf{ID}$ is the secret key generated by the extraction algorithm $\textsf{Extract}$ for user $\textsf{ID}$, then for any $m\in \mathcal {M}$ and $c\leftarrow \textsf{Enc}(mpk, \textsf{ID}, m)$, it always holds that $\textsf{Dec}(sk_\textsf{ID},c)=m$.

Security. Let $\mathcal {O}_\textsf{extract}$ be an oracle of $\textsf{Extract}$ that on input an ID-tuple $\textsf{ID}$ and outputs $sk_{\textsf{ID}}$. An HIBE scheme is IND-CPA secure, if for all PPT adversary $\mathcal {A}$ there is a negligible function $\textsf{negl}(\lambda )$ such that:

$$\begin{aligned} \Pr \left[ b=b': \begin{array}{l} pp \leftarrow \textsf{Setup}(1^\lambda ); \\ (mpk, msk) \leftarrow \textsf{KeyGen}(pp);\\ (\textsf{ID}^{*},(m_{0},m_{1}))\leftarrow \mathcal {A}^{\mathcal {O}_\textsf{extract}} (pp,mpk);\\ b{\mathop {\leftarrow }\limits ^{R}}\{0,1\},c^{*}\leftarrow \textsf{Enc}(mpk,\textsf{ID}^{*},m_{b});\\ b'\leftarrow \mathcal {A}^{\mathcal {O}_\textsf{extract}}(c^{*}); \end{array} \right] \le \frac{1}{2}+\textsf{negl}(\lambda ). \end{aligned}$$

In guess stage, $\mathcal {A}$ is not allowed to query the $\mathcal {O}_\textsf{extract}$ for $\textsf{ID}^{*}$ or the ancestor nodes of it (i.e. $\textsf{ID}$s which are prefixed with $\textsf{ID}^{*}$). Meanwhile, two weaker security notions can be defined similarly. One is OW-CPA security, in which the adversary is required to recover the plaintext from a random ciphertext. The other is selective-identity IND-CPA security, in which the adversary must commit ahead of time (non-adaptively) to the identity it intends to attack before seeing the mpk.

1.2 A.2 Boneh-Boyen HIBE Scheme

We review the $\ell$-HIBE scheme of Boneh-Boyen ($\mathsf {BB_{1}\text {-}IBE}$) [9] as below. As [6, 18] noticed, compared to symmetric pairings, asymmetric pairings yield schemes having more efficiency in terms of both bandwidth and computation time. Therefore, we adjust the original Boneh-Boyen HIBE with asymmetric pairings.

• $\textsf{Setup}(1^{\lambda })$: on input the security parameter $\lambda$, generates an asymmetric pairings tuple $\left( \mathbb {G}_{1},\mathbb {G}_{2}, \mathbb {G}_{T}, p, g_{1}, g_{2}, e\right)$, and picks a family of collision resistant hash functions $\textsf{H}_{j}:\{0,1\}^{*}\rightarrow \mathbb {G}_{2}$ for $j\in [0,\ell ]$. The public parameters pp include the description of bilinear groups and the hash functions $\{\textsf{H}_{j}\}_{j\in [0,\ell ]}$. The $\textsf{ID}$ at level-j is $\mathcal {I}^{j}=(\{0,1\}^{*})^{j}$. The plaintext space is $\mathcal {M}=\mathbb {G}_{T}$.

• $\textsf{KeyGen}(pp)$: on input the public parameters pp, picks a random $\alpha \in \mathbb {Z}_{p}$, sets $f_{1}=g_{1}^{\alpha }$ and $f_{2}=g_{2}^{\alpha }$, sets public key $mpk=f_{1}=g_{1}^{\alpha }$ and master secret key $msk=f_{2}=g_{2}^{\alpha }$.

• $\textsf{Extract}( mpk,sk_{\textsf{ID}},\left\langle \textsf{ID},I\right\rangle )$: on input the public key mpk, a level-j private key $sk_\textsf{ID}=\left( d_{0},\dots ,d_{j} \right) \in \left( \mathbb {G}_{2},\mathbb {G}_{1}^{j}\right)$ and a level-$(j+1)$ ID-tuple $\left\langle \textsf{ID},I\right\rangle =\left( I_{1},\dots ,I_{j},I_{j+1}\right) \in (\{0,1\}^{*})^{j+1}$, first picks a random $r \in \mathbb {Z}_{p}$ and outputs

  $$\begin{aligned} sk_{\left\langle \textsf{ID},I\right\rangle }=\left( d_{0}\cdot \textsf{H}_{j+1}(I_{j+1})^{r},d_{1},\dots ,d_{j},g_{2}^{r}\right) \in \left( \mathbb {G}_{2},\mathbb {G}_{1}^{j+1}\right) \end{aligned}$$

  Note that (1) when $\textsf{ID}$ is an empty set denoted as $\epsilon$, $sk_\textsf{ID}$ is exactly the master secret key msk, that is $sk_{\epsilon }=f_{2}=g_{2}^{\alpha }$. (2) all the private keys can be also extracted directly from the master secret key msk through computing $sk_{\left\langle \textsf{ID},I\right\rangle }=\left( g_{2}^{\alpha }\cdot \prod _{k=1}^{j+1}\textsf{H}_{k}(I_{k})^{r_{k}},g_{1}^{r_{1}},\dots ,g_{1}^{r_{j+1}}\right)$ with random elements $r_{1},\dots ,r_{j+1}\in \mathbb {Z}_{p}$.

• $\textsf{Enc}( mpk, \textsf{ID}, m)$: on input the public key mpk, an ID-tuple $\textsf{ID}=\left( I_{1},\dots ,I_{j}\right) \in (\{0,1\}^{*})^{j}$ and a message $m\in \mathbb {G}_{T}$, picks a random $s\in \mathbb {Z}_{p}$ and outputs

  $$\begin{aligned} C=\left( e(f_{1},g_{2})^{s}\cdot m, g_{1}^{s}, \textsf{H}_{1}(I_{1})^{s},\dots , \textsf{H}_{j}(I_{j})^{s}\right) \in \left( \mathbb {G}_{T},\mathbb {G}_{1},\mathbb {G}_{2}^{j}\right) . \end{aligned}$$

• $\textsf{Dec}(sk_\textsf{ID},c)$: on input a private key $sk_\textsf{ID}=\left( d_{0},d_{1},\dots ,d_{j} \right)$ and a ciphertext $C=\left( A,B,C_{1},\dots ,C_{j}\right)$, outputs

  $$\begin{aligned} A\cdot \displaystyle {\frac{\prod _{k=1}^{j}e\left( d_{k},C_{k} \right) }{e\left( B,d_{0}\right) }}=m . \end{aligned}$$