Identity-Based Hierarchical Key-Insulated Encryption Without Random Oracles

Abstract

Key-insulated encryption is one of the effective solutions to a key exposure problem. Recently, identity-based encryption (IBE) has been used as one of fundamental cryptographic primitives in a wide range of various applications, and it is considered that the identity-based key-insulated security has a huge influence on the resulting applications. At Asiacrypt’05, Hanaoka et al. proposed an identity-based hierarchical key-insulated encryption (hierarchical IKE) scheme. Although their scheme is secure in the random oracle model, it has a “hierarchical key-updating structure,” which is attractive functionality that enhances key exposure resistance.

In this paper, we first propose the hierarchical IKE scheme without random oracles. Our hierarchical IKE scheme is secure under the symmetric external Diffie–Hellman (SXDH) assumption, which is known as the simple and static one. Furthermore, when the hierarchy depth is one (i.e. not hierarchical case), our scheme is the first IKE scheme that achieves constant-size parameters including public parameters, secret keys, and ciphertexts.

1 Introduction

1.1 Background

A key exposure problem is unavoidable since human errors cannot seem to be eliminated in the future, and many researchers have tackled this problem in modern cryptography area so far. Key-insulation, which is introduced by Dodis et al. [12], is one solution to this problem. Specifically, they proposed public key encryption with the key-insulated property, which is called public-key-based key-insulated encryption (PK-KIE). In PK-KIE, a user has two kinds of secret keys, so-called a decryption key and a helper key. The decryption key is used for decrypting ciphertexts and assumed to be stored in a powerful but insecure device such as laptops and smartphones. Meanwhile, the helper key is used for updating the decryption key and assumed to be stored in a physically-secure but computationally-limited device such as USB pen drives. Traditionally, in key-insulated cryptography, the following two kinds of security notions are considered:

• 1. If a number of decryption keys are exposed, the fact does not affect decryption keys at other time-periods.

• 2. Even if a helper key is exposed, the security is not compromised unless at least one decryption key is exposed.

We say a key-insulated system is secure if it satisfies 1; and it is strongly secure if it satisfies both 1 and 2. Specifically, the lifetime of the system is divided into discrete time-periods, and the user can decrypt the ciphertext encrypted at some time-period t by using a decryption key updated at the same time-period t. Therefore, even if the decryption key at t is exposed, the fact does not affect decryption keys at other time-periods, and hence the impact of the exposure can be significantly reduced.

Following a seminal work by Dodis et al. [12], symmetric-key-based key-insulated encryption [14], key-insulated signatures [13], and parallel key-insulated encryption [17, 18, 23] have been proposed so far. In addition to key-insulated cryptography, researchers have tackled the key exposure problem in various flavors. In forward-secure cryptography [1, 8], users update their own secret keys at the beginning of each time-period. Even if the secret key is exposed, an adversary cannot get any information of ciphertexts encrypted at previous time-periods. Intrusion-resilient cryptography [10, 11, 20] realizes both key-insulated security and forward security simultaneously at the sacrifice of efficiency and practicality.

In this paper, we focus on the key-insulation paradigm in the identity-based setting. Since identity-based encryption (IBE) has been used as one of fundamental cryptographic primitives in a wide range of various applications, we believe that the identity-based key-insulated security has a huge influence on the resulting applications. Also, developing key-insulated cryptography in the identity-based area is the first step to consider the key-insulated security in the attribute-based [3, 26] and functional encryption [7] settings. Thus, we consider that it is important to consider the identity-based key-insulated security. However, in the IBE context, there are only few researches on key-insulation. Hanaoka et al. [19] proposed the first identity-based (hierarchical) key-insulated encryption (IKE) scheme in the random oracle model. In their hierarchical IKE scheme, the key-updating mechanism has the hierarchical structure (and the scheme does not have a delegating property). Namely, not only a decryption key but also a helper key can be updated by a higher-level helper key. Since this “hierarchy” is not the same as that of hierarchical IBE (HIBE) [16], only applying techniques used in the HIBE context is insufficient for constructing secure (in particular, strongly secure) IKE schemes. The hierarchical property is attractive since it enhances resistance to key exposure and there seem to be various applications due to progress in information technology (e.g., the popularization of smartphones). Let us consider an example: Suppose that each employee has a smartphone for business use, a laptop, and a PC at his office. A decryption key is stored in the smartphone, and it is updated by a 1-st level helper key stored in his laptop every day. However, the 1-st level helper key might be leaked since he carries around the laptop, and connects to the Internet via the laptop. Thus, the 1-st level helper key is also updated by a 2-nd level helper key stored in his PC every two–three months. Since the PC is not completely isolated from the Internet, every half a year, his boss updates the 2-nd level helper key is updated by 3-rd level helper key stored in an isolated private device. Thus, we believe hierarchical IKE has many potential applications.

After the proposal of hierarchical IBE by Hanaoka et al., two (not hierarchical) IKE schemes with additional properties in the standard model were proposed. One is the so-called parallel IKE scheme, which was proposed by Weng et al. [31]. The other is the so-called threshold IKE scheme, which was proposed by Weng et al. [32]. These two schemes enhance the resistance to helper key exposure by splitting a helper key into multiple ones. However, once the (divided) helper key is leaked, the security cannot be recovered. We now emphasize that the hierarchical key-updating structure is useful since even if some helper key is exposed, the helper key can be updated. However, there have been no hierarchical IKE schemes without random oracles so far.

1.2 Our Contribution

In this paper, our aim is to construct a hierarchical IKE scheme such that: (1) we can prove the security in the standard model from simple computational assumptions; and (2) when the hierarchy depth is one (i.e., not hierarchical case), the scheme achieves all constant-size parameters including public parameters, secret keys, and ciphertexts.

As a result, we propose the first hierarchical IKE scheme in the standard model. Specifically, we construct the hierarchical IKE scheme from the symmetric external Diffie–Hellman (SXDH) assumption, which is a static and simple one. Further, the proposed scheme achieves the constant-size parameters when the hierarchy is one, whereas public parameters of the (not hierarchical) existing scheme [32] depend on sizes of identity spaces (also see Sect. 4.1 for comparison). This is due to differences of base IBE schemes of each scheme. Our (hierarchical) IKE scheme is based on the Jutla–Roy IBE [22] and its variant [25], whereas the existing scheme (but not hierarchical one) [32] is based on the Waters IBE [29]. In the following, we explain why a naive solution is insufficient and why achieving (1) and (2) is challenging.

Why a (Trivial) Hierarchical IKE Scheme from HIBE is Insufficient. ¹ One may think that a hierarchical IKE scheme can be easily obtained from an arbitrary HIBE scheme. However, the resulting IKE scheme is insecure in our security model, which was first formalized in [19]. The reason for this is that our security model includes the strong security model, and hence the fact makes a hierarchical IKE scheme from HIBE insecure. More specifically, a trivial construction is as follows. Let $sk_{\texttt {I}}$ be a secret key for some identity $\texttt {I}$ in HIBE, and $hk_{\texttt {I}}^{(\ell )}$ be an $\ell$-th level helper key for $\texttt {I}$ in IKE. We set $sk_{\texttt {I}}$ as $hk_{\texttt {I}}^{(\ell )}$, and lower-level helper and decryption keys can be obtained from $sk_{\texttt {I}}$ by regarding time-periods as descendants’ identity. However, it is easy to see that if $\ell$-th level helper key is exposed, then an adversary can obtain all lower-level keys, and thus, the resulting scheme does not meet the strong security. In fact, Bellare and Palacio [2] showed that not strongly secure PK-KIE is equivalent to IBE for a similar reason.

Difficulties in Constructing a Constant-Size IKE Scheme from Simple Computational Assumptions. The main difficulty in constructing an IKE scheme is that an adversary can get various keys regarding a target identity $\texttt {I}^*$, whereas in (H)IBE, the adversary cannot get any information on a secret key for $\texttt {I}^*$. This point makes a construction methodology non-trivial. Actually, it seems difficult to apply the Waters dual-system IBE [30] (and its variant [24]) as the underlying basis of IKE schemes. Technically, in their scheme each of secret keys and ciphertexts contains some random exponent, so-called $tag_K$ and $tag_C$, respectively. In their proof, these tags for some $\texttt {I}$ are needed to be generated by inputting $\texttt {I}$ into some pairwise independent function, which is embedded into public parameters in advance. This generating procedure is necessary for cancellation of values and hence the security proof. Although it holds $tag_K=tag_C$ for the same identity $\texttt {I}$, the proof works well since it is enough to generate only $tag_K$ for all identities $\texttt {I}\ne \texttt {I}^*$ and only $tag_C$ for the target identity $\texttt {I}^*$. However, in the IKE setting, not only $tag_C$ but also $tag_K$ for $\texttt {I}^*$ have to be generated since an adversary can get leaked decryption and helper keys for $\texttt {I}^*$, and hence, the proof does not go well. To overcome this challenging point, we set (the variant of) the Jutla–Roy IBE [22, 25], which is another type of constant-size IBE schemes, as the basis of our IKE scheme, and thus we can realize the first constant-size IKE scheme under the SXDH assumption. Further, we can also obtain the hierarchical IKE scheme by extending the technique into the hierarchical setting.

Organization of This Paper. In Sect. 2, we describe the notation used in this paper, asymmetric pairings, complexity assumptions, and functions which map time to discrete time-periods. In Sect. 3, we give a model and security definition of hierarchical IKE. In Sect. 4, we propose a direct construction of our hierarchical IKE scheme, and give the efficiency comparison among our scheme and existing schemes. In Sect. 5, we show the security proof of our scheme. In Sect. 6, we show a CCA-secure hierarchical IKE scheme. In Sect. 7, we conclude this paper.

2 Preliminaries

Notation. In this paper, “probabilistic polynomial-time” is abbreviated as “PPT”. Let $\mathbb {Z}_p:=\{0,1,\ldots ,p-1\}$ and $\mathbb {Z}_p^{\times }:=\mathbb {Z}_p{\setminus }\{0\}$. If we write $(y_1,y_2,\ldots ,y_m)\leftarrow \mathcal {A}(x_1,x_2,\ldots ,x_n)$ for an algorithm $\mathcal {A}$ having n inputs and m outputs, it means to input $x_1, x_2,\ldots ,x_n$ into $\mathcal {A}$ and to get the resulting output $y_1,y_2,\ldots ,y_m$. We write $(y_1,y_2,\ldots ,y_m)\leftarrow \mathcal {A}^{\mathcal {O}}(x_1,x_2,\ldots ,x_n)$ to indicate that an algorithm $\mathcal {A}$ that is allowed to access an oracle $\mathcal {O}$ takes $x_1,x_2,\ldots ,x_n$ as input and outputs $(y_1,y_2,\ldots ,y_m)$. If $\mathcal {X}$ is a set, we write to mean the operation of picking an element x of $\mathcal {X}$ uniformly at random. We use $\lambda$ as a security parameter. $\mathcal {M}$ and $\mathcal {I}$ denote sets of plaintexts and IDs, respectively, which are determined by a security parameter $\lambda$.

Bilinear Group. A bilinear group generator $\mathcal {G}$ is an algorithm that takes a security parameter $\lambda$ as input and outputs a bilinear group $(p, \mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, g_1, g_2, e)$, where p is a prime, $\mathbb {G}_1$, $\mathbb {G}_2$, and $\mathbb {G}_T$ are multiplicative cyclic groups of order p, $g_1$ and $g_2$ are (random) generators of $\mathbb {G}_1$ and $\mathbb {G}_2$, respectively, and e is an efficiently computable and non-degenerate bilinear map $e: \mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T$ with the following bilinear property: For any $u, u'\in \mathbb {G}_1$ and $v, v' \in \mathbb {G}_2$, $e(uu',v)=e(u,v)e(u',v)$ and $e(u,vv')=e(u,v)e(u,v')$, and for any $u\in \mathbb {G}_1$ and $v\in \mathbb {G}_2$ and any $a\in \mathbb {Z}_p$, $e(u^a,v)=e(u,v^a)=e(u,v)^a$.

A bilinear map e is called symmetric or a “Type-1” pairing if $\mathbb {G}_1=\mathbb {G}_2$. Otherwise, it is called asymmetric. In the asymmetric setting, e is called a “Type-2” pairing if there is an efficiently computable isomorphism either from $\mathbb {G}_1$ to $\mathbb {G}_2$ or from $\mathbb {G}_2$ to $\mathbb {G}_1$. If no efficiently computable isomorphisms are known, then it is called a “Type-3” pairing. In this paper, we focus on the Type-3 pairing, which is the most efficient setting (For details, see [9, 15]).

Symmetric External Diffie–Hellman (SXDH) Assumption. We give the definition of the decisional Diffie–Hellman (DDH) assumption in $\mathbb {G}_1$ and $\mathbb {G}_2$, which are called the DDH1 and DDH2 assumptions, respectively.

Let $\mathcal {A}$ be a PPT adversary and we consider $\mathcal {A}$’s advantage against the DDH1 problem as follows.

Definition 1

(DDH1 Assumption). The DDH1 assumption relative to a generator $\mathcal {G}$ holds if for all PPT adversaries $\mathcal {A}$, $Adv^{DDH1}_{\mathcal {G},\mathcal {A}}(\lambda )$ is negligible in $\lambda$.

Similarly, we define the DDH2 problem. Let $\mathcal {A}$ be a PPT adversary and we consider $\mathcal {A}$’s advantage against the DDH2 problem as follows.

Definition 2

(DDH2 Assumption). The DDH2 assumption relative to a generator $\mathcal {G}$ holds if for all PPT adversaries $\mathcal {A}$, $Adv^{DDH2}_{\mathcal {G},\mathcal {A}}(\lambda )$ is negligible in $\lambda$.

Definition 3

(SXDH Assumption). We say that the SXDH assumption relative to a generator $\mathcal {G}$ holds if both the DDH1 and DDH2 assumptions relative to $\mathcal {G}$ hold.

Fig. 1.

Intuition of time-period map functions.

Time-Period Map Functions. In this paper, we deal with several kinds of time-periods since we consider that update intervals of each level key are different. For example, in some practical applications, it might be suitable that a decryption key (i.e. 0-th level key) and a 1-st level helper key should be updated every day and every three months, respectively. To describe such different update intervals of each level key, we use functions, which is so-called time-period map functions. This functions were also used in [19]. Now, let $\mathcal {T}$ be a (possibly infinite) set of time, and $\mathcal {T}_j \ (0 \le j \le \ell -1)$ be a finite set of time-periods. We assume $|\mathcal {T}_0|\ge |\mathcal {T}_1|\ge \cdots \ge |\mathcal {T}_{\ell -1}|$. This means that a lower-level key is updated more frequently than the higher-level keys. Then, we assume there exists a function $T_j \ (0 \le j \le \ell -1)$ which map time $\texttt {time}\in \mathcal {T}$ to a time-period $t_j\in \mathcal {T}_j$. For the understanding of readers, by letting $\texttt {time}=\texttt {9:59/7th/Oct./2015}$ and $\ell :=4$, we give an example in Fig. 1 and below. For example, we have $T_0(\texttt {time})=t_0^{(19)}=\texttt {1st-15th/Oct./2015}$, $T_1(\texttt {time})=t_1^{(10)}=\texttt {Oct./2015}$, $T_2(\texttt {time})=t_2^{(5)}=\texttt {Oct.-Dec./2015}$, and $T_3(\texttt {time})=t_3^{(2)}=\texttt {Jul.-Dec./2015}$. Namely, in this example, it is assumed that the decryption key, and 1-st, 2-nd, and 3-rd helper keys are updated every half a month, every month, every three months, and every half a year. Further, we can also define a function $T_\ell$ such that $T_\ell (\texttt {time})=0$ for all $\texttt {time}\in \mathcal {T}$.

3 Identity-Based Hierarchical Key-Insulated Encryption

3.1 The Model

In $\ell$-level hierarchical IKE, a key generation center (KGC) generates an initial decryption key $dk_{\texttt {I},0}$ and $\ell$ initial helper keys $hk_{\texttt {I},0}^{(1)},\ldots ,hk_{\texttt {I},0}^{(\ell )}$ as a secret key for a user $\texttt {I}$. Suppose that all time-period map functions $T_0,\ldots ,T_{\ell -1}$ are available to all users. The key-updating procedure when the user wants to get a decryption key at current time $\texttt {time}\in \mathcal {T}$ from the initial helper keys is as follows. The $\ell$-th level helper key $hk_{\texttt {I},0}^{(\ell )}$ is a long-term one and is never updated. First, the user generates key update $\delta _{t_{\ell -1}}^{(\ell -1)}$ for the $(\ell -1)$-th level helper key from $hk_{\texttt {I},0}^{(\ell )}$ and a time-period $t_{\ell -1}:=T_{\ell -1}(\texttt {time})\in \mathcal {T}_{\ell -1}$. Then, the $(\ell -1)$-th level helper key $hk_{\texttt {I},0}^{(\ell -1)}$ can be updated by the key update $\delta _{t_{\ell -1}}^{(\ell -1)}$, and the user get the helper key $hk_{\texttt {I},t_{\ell -1}}^{(\ell -1)}$ at the time-period $t_{\ell -1}$. Similarly, the i-th level helper key $hk_{\texttt {I},t_{i}}^{(i)}$ at the time-period $t_{i}:=T_i(\texttt {time})\in \mathcal {T}_i$ can be obtained from $hk_{\texttt {I},0}^{(i)}$ and $\delta _{t_{i}}^{(i)}$, where $\delta _{t_{i}}^{(i)}$ is generated from the $(i+1)$-th level helper key $hk_{\texttt {I},t_{i+1}}^{(i+1)}$. The user can finally get the decryption key $dk_{\texttt {I},t_0}$ at a time-period $t_0:=T_0(\texttt {time})\in \mathcal {T}_0$ from the 1-st level helper key $hk_{\texttt {I},T_1(\texttt {time})}^{(1)}$. Anyone can encrypt a plaintext M with the identity $\texttt {I}$ and current time $\texttt {time}^*$, and the user can decrypt the ciphertext C with his decryption key $dk_{\texttt {I},t_0}$ only if $t_0=T_0(\texttt {time}^*)$. At $\texttt {time}'\in \mathcal {T}$, the user can update the time-period of the decryption key from any time-period $t_0$ to $t'_0:=T_0(\texttt {time}')\in \mathcal {T}_0$ by using key update $\delta _{T_0(\texttt {time}')}^{(0)}$. The key update $\delta _{T_0(\texttt {time}')}^{(0)}$ can be obtained from $hk_{\texttt {I}, t'_1}^{(1)}$ only if $t'_1=T_1(\texttt {time}')$. If not, it is necessary to get $\delta _{T_1(\texttt {time}')}^{(1)}$ and update $hk_{\texttt {I}, t'_1}^{(1)}$. In this manner, the decryption and helper keys are updated.

An $\ell$-level hierarchical IKE scheme $\varPi _{\textit{IKE}}$ consists of six-tuple algorithms (PGen, Gen, $\varDelta$ -Gen, Upd, Enc, Dec) defined as follows. For simplicity, we omit a public parameter in the input of all algorithms except for the PGen algorithm.

• $(pp,mk)\leftarrow \textsf {PGen}(\lambda ,\ell )$: A probabilistic algorithm for parameter generation. It takes a security parameter $\lambda$ and the maximum hierarchy depth $\ell$ as input, and outputs a public parameter pp and a master key mk.

• $(dk_{\texttt {I},0},hk_{\texttt {I},0}^{(1)},\ldots ,hk_{\texttt {I},0}^{(\ell )})\leftarrow \textsf {Gen}(mk, \texttt {I})$: An algorithm for user key generation. It takes mk and an identity $\texttt {I}\in \mathcal {I}$ as input, and outputs an initial secret key $dk_{\texttt {I},0}$ associated with $\texttt {I}$ and initial helper keys $hk_{\texttt {I},0}^{(1)},\ldots ,hk_{\texttt {I},0}^{(\ell )}$, where $hk_{\texttt {I},0}^{(i)} \ (1 \le i \le \ell )$ is assumed to be stored user’s i-th level private device.

• $\delta _{T_{i-1}(\texttt {time})}^{(i-1)}$ or $\bot \leftarrow \varDelta \textsf {-Gen}(hk_{\texttt {I},t_i}^{(i)}, \texttt {time})$: An algorithm for key update generation. It takes an i-th helper key $hk_{\texttt {I},t_i}^{(i)}$ at a time period $t_i\in \mathcal {T}_i$ and current time $\texttt {time}$ as input, and outputs key update $\delta _{T_{i-1}(\texttt {time})}^{(i-1)}$ if $t_i=T_{i}(\texttt {time})$; otherwise, it outputs $\bot$.

• $hk_{\texttt {I},\tau _i}^{(i)}\leftarrow \textsf {Upd}(hk_{\texttt {I},t_i}^{(i)}, \delta _{\tau _i}^{(i)})$: A probabilistic algorithm for decryption key generation. It takes an i-th helper key $hk_{\texttt {I},t_i}^{(i)}$ at a time-period $t_i\in \mathcal {T}_i$ and key update $\delta _{\tau _i}^{(i)}$ at a time-period ${\tau _i}\in \mathcal {T}_i$ as input, and outputs a renewal i-th helper key $hk_{\texttt {I},\tau _i}^{(i)}$ at ${\tau _i}$. Note that for any $t_0\in \mathcal {T}_0$, $hk_{\texttt {I},t_0}^{(0)}$ means $dk_{\texttt {I},t_0}$.

• $\langle C, \texttt {time}\rangle \leftarrow \textsf {Enc}(\texttt {I}, \texttt {time}, M)$: A probabilistic algorithm for encryption. It takes an identity $\texttt {I}$, current time $\texttt {time}$, and a plaintext $M \in \mathcal {M}$ as input, and outputs a pair of a ciphertext and current time $\langle C,\texttt {time}\rangle$.

• M or $\bot \leftarrow \textsf {Dec}(dk_{\texttt {I},t_0}, \langle C,\texttt {time}\rangle )$: A deterministic algorithm for decryption. It takes $dk_{\texttt {I},t_0}$ and $\langle C,\texttt {time}\rangle$ as input, and outputs M or $\bot$, where $\bot$ indicates decryption failure.

In the above model, we assume that $\varPi _{\textit{IKE}}$ meets the following correctness property: For all security parameter $\lambda$, all $\ell :=poly(\lambda )$, all $(mk,pp)\leftarrow \textsf {PGen}(\lambda ,\ell )$, all $M\in \mathcal {M}$, all $(dk_{\texttt {I},0},hk_{\texttt {I},0}^{(1)},\ldots ,hk_{\texttt {I},0}^{(\ell )})\leftarrow \textsf {Gen}(mk, \texttt {I})$, and all $\texttt {time}\in \mathcal {T}$, it holds that $M\leftarrow \textsf {Dec}(dk_{\texttt {I},T_0(\texttt {time})}, \textsf {Enc}(\texttt {I}, \texttt {time}, M) )$, where $dk_{\texttt {I},T_0(\texttt {time})}$ is generated as follows: For $i=\ell ,\ldots ,1$, $hk_{\texttt {I},T_{i-1}(\texttt {time})}^{(i-1)}\leftarrow \textsf {Upd}(hk_{\texttt {I},t_{i-1}}^{(i-1)}, \varDelta \textsf {-Gen}(hk_{\texttt {I},T_i(\texttt {time})}^{(i)}, \texttt {time}))$, where some $t_i\in \mathcal {T}_i$ and $hk_{\texttt {I},T_{0}(\texttt {time})}^{(0)}:=dk_{\texttt {I},T_0(\texttt {time})}$.

3.2 Security Definition

We consider a security notion for indistinguishability against key exposure and chosen plaintext attack for IKE (IND-KE-CPA). Let $\mathcal {A}$ be a PPT adversary, and $\mathcal {A}$’s advantage against IND-KE-CPA security is defined by

where KG $(\cdot )$ and KI $(\cdot ,\cdot ,\cdot )$ are defined as follows.

• KG $(\cdot ){\varvec{:}}$ For a query $\texttt {I}\in \mathcal {I}$, it stores and returns $(dk_{\texttt {I},0},hk_{\texttt {I},0}^{(1)},\ldots ,hk_{\texttt {I},0}^{(\ell )})$ by running $\textsf {Gen}(mk,\texttt {I})$.

• KI $(\cdot ,\cdot ,\cdot ){\varvec{:}}$ For a query $(i,\texttt {I},\texttt {time})\in \{0,1,\ldots ,\ell \}\times \mathcal {I}\times \mathcal {T}$, it returns $hk_{\texttt {I},T_i(\texttt {time})}^{(i)}$ by running $\delta _{T_{j-1}(\texttt {time})}^{(j-1)}\leftarrow \varDelta \textsf {-Gen}(hk_{\texttt {I},T_j(\texttt {time})}^{(j)}, \texttt {time})$ and $hk_{\texttt {I},T_{j-1}(\texttt {time})}^{(j-1)}\leftarrow \textsf {Upd}(hk_{\texttt {I},t}^{(j-1)},$ $\delta _{T_{j-1}(\texttt {time})}^{(j-1)})$ for $j=\ell ,\ldots ,i+1$ (if $(dk_{\texttt {I},0},hk_{\texttt {I},0}^{(1)},\ldots ,hk_{\texttt {I},0}^{(\ell )})$ is not stored, it first generates and stores them by running $\textsf {Gen}$).

$\texttt {I}^*$ is never issued to the KG oracle. $\mathcal {A}$ can issue any queries $(i,\texttt {I},\texttt {time})$ to the KI oracle if there exists at least one special level $j\in \{0,1,\ldots ,\ell \}$ such that

• 1. For any $\texttt {time}\in \mathcal {T}$, $(j,\texttt {I}^*,\texttt {time})$ is never issued to KI.

• 2. For any $(i,\texttt {time})\in \{0,1,\ldots ,j-1\}\times \mathcal {T}$ such that $T_i(\texttt {time})=T_i(\texttt {time}^*)$, $(i,\texttt {I}^*,\texttt {time})$ is never issued to KI.

Fig. 2.

Pictorial representation of secret keys for $\texttt {I}^*$ that $\mathcal {A}$ can obtain by issuing to KI.

In Fig. 2, we give intuition of keys that $\mathcal {A}$ can obtain by issuing to the KI oracle. In this example, let $\ell =4$ and a special level $j=2$.

Definition 4

(IND-KE-CPA [19]). An IKE scheme $\varPi _{ IKE }$ is said to be IND-KE-CPA secure if for all PPT adversaries $\mathcal {A}$, $Adv^{\textit{IND-KE-CPA}}_{\varPi _{ IKE },\mathcal {A}}(\lambda )$ is negligible in $\lambda$.

Remark 1

As also noted in [19], there is no need to consider key update exposure explicitly (i.e. consider an oracle which returns any key update as much as possible) since in the above definition, $\mathcal {A}$ can get such key update from helper keys obtained from the KI oracle.

Remark 2

As explained in Sect. 1, in key-insulated cryptography including the public key setting [2, 12, 17] and the identity-based setting [19, 31, 32], two kinds of security notions have been traditionally considered: standard security and strong security. In most of previous works [2, 12, 17–19, 23, 31, 32], authors have considered how their scheme could achieve the strong security. We note that IND-KE-CPA security actually includes the strong security, and the fact is easily checked by setting $\ell =1$.

By modifying the above IND-KE-CPA game so that $\mathcal {A}$ can access to the decryption oracle Dec $(\cdot ,\cdot )$, which receives $(\texttt {I},\langle C, \texttt {time}\rangle )$ and returns M or $\bot$, we can also define indistinguishability against key exposure and chosen ciphertext attack for IKE (IND-KE-CCA). $\mathcal {A}$ is not allowed to issue $(\texttt {I}^*,\langle C^*, \texttt {time}\rangle )$ such that $T_0(\texttt {time})=T_0(\texttt {time}^*)$ to Dec. Let $Adv^{\textit{IND-KE-CCA}}_{\varPi _{ IKE },\mathcal {A}}(\lambda )$ be $\mathcal {A}$’s advantage against IND-KE-CCA security.

Definition 5

(IND-KE-CCA [19]). An IKE scheme $\varPi _{ IKE }$ is said to be IND-KE-CCA secure if for all PPT adversaries $\mathcal {A}$, $Adv^{\textit{IND-KE-CCA}}_{\varPi _{ IKE },\mathcal {A}}(\lambda )$ is negligible in $\lambda$.

4 Our Construction

Our basic idea is a combination of (the variant of) the Jutla–Roy HIBE [22, 25] and threshold secret sharing schemes [4, 27]. A secret B is divided into $\ell$ shares $\beta _0,\ldots ,\beta _{\ell -1}$, and both the secret and shares are used in exponent of a generator $g_2\in \mathbb {G}_2$. B is embedded into the exponent of a secret key for $\texttt {I}^*$ of the Jutla–Roy HIBE, and the resulting key is an $\ell$-th level initial helper key $hk_{\texttt {I},0}^{(\ell )}$. Roughly speaking, B works as “noise”. Other initial helper keys $hk_{\texttt {I},0}^{(i)}$ and an initial decryption key contain $g_2^{-\beta _i}$ and $g_2^{-\beta _0}$, respectively. As a lower-level key is generated, shares are eliminated from the secret B, and finally B is entirely removed when generating (or updating) a decryption key. Intuitively, since no secret keys at some special level $j\in \{0,\ldots ,\ell \}$ are exposed, an adversary cannot get all $\beta _i$. Hence, he cannot generate valid decryption keys that can decrypt the challenge ciphertext for $\texttt {I}^*$ at $\texttt {time}^*$.

An IKE scheme $\varPi _{\textit{IKE}}=$(PGen, Gen, $\varDelta$ -Gen, Upd, Enc, Dec) is constructed as follows.

• PGen $(\lambda ,\ell )$: It runs $(\mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, p, g_1, g_2, e)\leftarrow \mathcal {G}$. It chooses $x_0,y_0,\{(x_{1,j},y_{1,j})\}_{j=0}^{\ell },$ and , and sets

  $$\begin{aligned}&z=e(g_1,g_2)^{-x_0\alpha +y_0}, \ u_{1,j}:=g_1^{-x_{1,j}\alpha +y_{1,j}} \ (0 \le j \le \ell ), \\&w_{1}:=g_1^{-x_{2}\alpha +y_2}, \ h_{1}:=g_1^{-x_{3}\alpha +y_3}. \ \end{aligned}$$

  It outputs

  $$\begin{aligned}&pp:=(g_1,g_1^{\alpha },\{u_{1,j}\}_{j=0}^{\ell },w_1,h_1,g_2,\{(g_2^{x_{1,j}},g_2^{y_{1,j}})\}_{j=0}^{\ell },g_2^{x_2},g_2^{x_3},g_2^{y_2},g_2^{y_3},z),\\&mk:=(x_0,y_0). \end{aligned}$$

• Gen(mk, ID): It chooses , and let $B:=\sum ^{\ell -1}_{i=0}\beta _i$. It computes

  $$\begin{aligned}&R_j\; :=g_2^{-\beta _j} \ (0 \le j < \ell ), \\&D_{1}:=(g_2^{y_2})^{r}, \ D'_{1}:=g_2^{y_0}\Bigl ((g_2^{y_{1,\ell }})^{\texttt {I}}g_2^{y_3}\Bigr )^{r}, \\&D_{2}:=(g_2^{x_2})^{-r}, \ D'_{2}:=g_2^{-x_0}\Bigl ((g_2^{x_{1,\ell }})^{\texttt {I}}g_2^{x_3}\Bigr )^{-r}, \\&D_3:=g_2^{r+B}, \\&K_j\; :=(g_2^{y_{1,j}})^{r} \ (0 \le j \le \ell -1), \ K'_j :=(g_2^{x_{1,j}})^{-r} \ (0 \le j \le \ell -1). \end{aligned}$$

  It outputs

  $$\begin{aligned}&dk_{\texttt {I},0}:=R_0, \ hk^{(i)}_{\texttt {I},0}:=R_i \ (1 \le i \le \ell -1), \\&hk^{(\ell )}_{\texttt {I},0}:=(D_{1},D'_{1},D_{2},D'_{2},D_3,\{(K_j,K'_j)\}_{j=0}^{\ell -1}). \end{aligned}$$

• $\varDelta$ -Gen $(hk_{\texttt {I},t_i}^{(i)},\texttt {time})$: If $t_i\ne T_i(\texttt {time})$, it outputs $\bot$. Otherwise, parse $hk_{\texttt {I},t_i}^{(i)}$ as $(R_i, D_{1},D'_{1},D_{2},D'_{2},D_3, \{(K_j,K'_j)\}_{j=0}^{i-1})$.² It chooses $\hat{r}\leftarrow \mathbb {Z}_p$, and let $t_{j}:=T_{j}(\texttt {time}) \ (i-1 \le j \le \ell -1)$. It computes

  $$\begin{aligned}&\hat{d}_{1}:=D_{1} (g_2^{y_2})^{\hat{r}}, \ \hat{d}'_{1}:=D'_{1} (K_{i-1})^{t_{i-1}}\Bigl ((g_2^{y_{1,\ell }})^{\texttt {I}}\prod _{j=i-1}^{\ell -1}\bigl ((g_2^{y_{1,j}})^{t_j}\bigr )g_2^{y_3}\Bigr )^{\hat{r}}, \\&\hat{d}_{2}:=D_{2} (g_2^{x_2})^{-\hat{r}}, \ \hat{d}'_{2}:=D'_{2} (K'_{i-1})^{t_{i-1}}\Bigl ((g_2^{x_{1,\ell }})^{\texttt {I}}\prod _{j=i-1}^{\ell -1}\bigl ((g_2^{x_{1,j}})^{ t_j}\bigr )g_2^{x_3}\Bigr )^{-\hat{r}}, \\&\hat{d}_3:=D_3 g_2^{\hat{r}}, \\&\hat{k}_j\, := K_j (g_2^{y_{1,j}})^{\hat{r}} \ (0 \le j \le i-2), \ \hat{k}'_j:=K'_j (g_2^{x_{1,j}})^{-\hat{r}} \ (0 \le j \le i-2). \end{aligned}$$

  It outputs $\delta _{t_{i-1}}^{(i-1)}:=(\hat{d}_{1},\hat{d}'_{1},\hat{d}_{2},\hat{d}'_{2},\hat{d}_3, \{(\hat{k}_j,\hat{k}'_j)\}_{j=0}^{i-2})$.³

• Upd $(hk_{\texttt {I},t_i}^{(i)}, \delta _{\tau _i}^{(i)})$: Parse $hk_{\texttt {I},t_i}^{(i)}$ and $\delta _{\tau _i}^{(i)}$ as $(R_i, D_{1},D'_{1},D_{2},D'_{2},D_3, \{(K_j,K'_j)\}_{j=0}^{i-1})$ and $(\hat{d}_{1},\hat{d}'_{1},\hat{d}_{2},\hat{d}'_{2},\hat{d}_3, \{(\hat{k}_j,\hat{k}'_j)\}_{j=0}^{i-1})$, respectively. It computes $D_3:=\hat{d}_3R_i$, and sets $(D_j,D'_j):=(\hat{d}_j,\hat{d}'_j) \ (j=1,2)$ and $(K_j,K'_j):=(\hat{k}_j,\hat{k}'_j) \ (0 \le j \le i-1)$. Finally, it outputs $hk_{\texttt {I},\tau _i}^{(i)}:=(R_i, D_{1},D'_{1},D_{2},D'_{2},D_3, \{(K_j,K'_j)\}_{j=0}^{i-1})$.

• Enc $(\texttt {I}, \texttt {time}, M)$: It chooses . For $M\in \mathbb {G}_T$, it computes

  $$\begin{aligned}&C_0:=Mz^{s}, \ C_1:=g_1^{s}, \ C_2:=(g_1^{\alpha })^{s}, \ C_3:=\Bigl (\prod _{j=0}^{\ell -1}\bigl (u_{1,j}^{t_j}\bigr )u_{1,\ell }^{\texttt {I}}w_1^{\texttt {tag}}h_1\Bigr )^{s}, \end{aligned}$$

  where $t_j:=T_j(\texttt {time}) \ (0 \le j \le \ell -1)$. It outputs $C:=(C_0,C_1,C_2,C_3,\texttt {tag})$.

• Dec $(dk_{\texttt {I},t_0}, \langle C,\texttt {time}\rangle )$: If $t_0\ne T_0(\texttt {time})$, then it outputs $\bot$. Otherwise, parse $dk_{\texttt {I},t_0}$ and C as $(R_0, D_{1},D'_{1},D_{2},D'_{2},D_3)$ and $(C_0,C_1,C_2,C_3,\texttt {tag})$, respectively. It computes

  $$\begin{aligned} M=\frac{C_0 e(C_3,D_3)}{e(C_1,D_1^{\texttt {tag}}D'_1)e(C_2,D_2^{\texttt {tag}}D'_2)}. \end{aligned}$$

We show the correctness of our $\varPi _{\textit{IKE}}$. Suppose that r denotes internal randomness of $hk_{\texttt {I},0}^{(\ell )}$, which are generated when running Gen $(mk,\texttt {I})$, and $r^{(j)}$ denotes internal randomness of $\delta _{\texttt {I},t_{j-1}}^{(j-1)} \ (1 \le j \le \ell )$, which is generated when running $\varDelta$ -Gen $(hk_{\texttt {I},t_{j}}^{(j)},\texttt {time})$. Then we can write $dk_{\texttt {I},\tau _0}:=(R_0, D_{1},D'_{1},D_{2},D'_{2},D_3)$ as

$$\begin{aligned}&D_{1}:=g_2^{y_2\tilde{r}}, \ D'_{1}:=g_2^{y_0+\tilde{r}(\texttt {I}y_{1,\ell }+\sum _{j=0}^{\ell -1}\bigl (t_j y_{1,j}\bigr )+y_3)}, \\&D_{2}:=g_2^{x_2\tilde{r}}, \ D'_{2}:=g_2^{-x_0-\tilde{r}(\texttt {I}x_{1,\ell }+\sum _{j=0}^{\ell -1}\bigl (t_j x_{1,j}\bigr )+x_3)}, \ D_3:=g_2^{\tilde{r}}, \end{aligned}$$

where $\tilde{r}:=r+\sum _{i=1}^{\ell }r^{(j)}$.

Suppose that $dk_{\texttt {I},t_0}=(R_0, D_{1},D'_{1},D_{2},D'_{2},D_3)$ and $C=(C_0,C_1,C_2,C_3,\texttt {tag})$ are correctly generated. Then, we have

$$\begin{aligned}&\frac{C_0 e(C_3,D_3)}{e(C_1,D_1^{\texttt {tag}}D'_1)e(C_2,D_2^{\texttt {tag}}D'_2)}\\&=\,M e(g_1,g_2)^{(-x_0 \alpha +y_0)s} \\&\cdot \frac{e(g_1^{s(\sum _{j=0}^{\ell -1}t_j(-x_{1,j}\alpha +y_{1,j})+\texttt {I}(-x_{1,\ell }\alpha +y_{1,\ell })+\texttt {tag}(-x_2\alpha +y_2)-x_3 \alpha +y_3)},g_2^{\tilde{r}})}{e(g_1^{s},g_2^{y_2\tilde{r}\texttt {tag}+y_0+\tilde{r}(\texttt {I}y_{1,\ell }+\sum _{j=0}^{\ell -1}\bigl (t_j y_{1,j}\bigr )+y_3)}) e(g_1^{\alpha s},g_2^{-x_2\tilde{r}\texttt {tag}-x_0-\tilde{r}(\texttt {I}x_{1,\ell }+\sum _{j=0}^{\ell -1}\bigl (t_j x_{1,j}\bigr )+x_3)})} \\&=\,M e(g_1,g_2)^{(-x_0 \alpha +y_0)s} \frac{1}{e(g_1^{s},g_2^{y_0})e(g_1^{\alpha s},g_2^{-x_0})} =M. \end{aligned}$$

We obtain the following theorem. The proof is postponed to Sect. 5.

Theorem 1

If the SXDH assumption holds, then the resulting $\ell$-level hierarchical IKE scheme $\varPi _{ IKE }$ is IND-KE-CPA secure.

Table 1. Parameters evaluation of our $\ell$-level hierarchical IKE scheme. $\mathbb {G}_1$, $\mathbb {G}_2$, and $\mathbb {G}_T$ are cyclic groups of order p, and $|\mathbb {G}|$ denotes the bit-length of a group element in $\mathbb {G}_1$, $\mathbb {G}_2$, or $\mathbb {G}_T$, for simplicity. $|\mathcal {M}|$ and $|\mathbb {Z}_p|$ also denote the bit-length of plaintext and an element in $\mathbb {Z}_p$, respectively. $\#pp$, $\#dk$, $\#hk_i$, and $\#C$ denote sizes of public parameters, decryption keys, i-th helper keys, and ciphertexts, respectively. In computational cost analysis, $[\cdot ,\cdot ,\cdot ,\cdot ]$ means the number of [pairing, multi-exponentiation, regular exponentiation, fixed-based exponentiation]. For comparison we mention that relative tunings for the various operations are as follows: [$\mathrm {pairing} \approx 5$, multi-exp $\approx 1.5$, $\text {regular-exp}\,:=\,1$, ${\text {fixed-based-exp}}\,\ll \,0.2$].

Table 2. Efficiency comparison between our construction and existing schemes. The notation used here is the same as that in Table 1 except for $\#hk$, which denotes the helper key size. What n appears in public-parameter sizes means that the public-parameter size depends on the size of its identity space.

4.1 Parameters Evaluation and Comparison

First, we show the parameter sizes and computational costs of our hierarchical IKE scheme in Table 1.

Also, an efficiency comparison between our IKE scheme and the existing IKE schemes [19, 32] is given in Table 2. In fact, the WLC+08 scheme [32] has the threshold property and does not have a hierarchical structure, and therefore, we set the threshold value is one in the WLC+08 scheme and the hierarchy depth is one in the HHSI05 scheme [19] and our scheme for the fair comparison. The HHSI05 scheme meets the IND-KE-CCA security, however the scheme is secure only in the random oracle model (ROM). Both the WLC+08 scheme and ours meet the IND-KE-CPA security in the standard model (i.e. without random oracles). Although assumptions behind these schemes (i.e. the computational bilinear Diffie–Hellman (CBDH), decisional bilinear Diffie–Hellman (DBDH),⁴ and SXDH assumptions) are different, they all are static and simple. We emphasize that the threshold structure does not strengthen the underlying DBDH assumption of the WLC+08 scheme since the structure was realized via only threshold secret sharing techniques [4, 27]. Note that we do not take into account the parallel IKE scheme [31] since the model of the scheme is slightly different from those of the above schemes. However, the public parameter size of the parallel IKE scheme also depends on the size of its identity space, and we mention that this is due to the underlying Waters IBE [29], not due to the parallel property.

As can be seen, we first achieve the IKE scheme with constant-size parameters in the standard model. Again, we also get the first IKE scheme in the hierarchical setting without random oracles.

5 Proof of Security

We describe how semi-functional ciphertexts and secret keys are generated as follows.

• Semi-functional Ciphertext: Parse a normal ciphertext C as $(C_0,C_1,C_2,C_3,$ $\texttt {tag})$. A semi-functional ciphertext $\widetilde{C}:=(\tilde{C}_0,\tilde{C}_1,\tilde{C}_2,\tilde{C}_3,\widetilde{\texttt {tag}})$ is computed as follows:

  $$\begin{aligned} \tilde{C}_0&:=C_0 e(g_1,g_2)^{-x_0\mu }=M e(g_1,g_2)^{-x_0(\alpha s + \mu )+ y_0 s}, \\ \tilde{C}_1&:=C_1, \\ \tilde{C}_2&:=C_2g_1^{\mu }=g_1^{\alpha s+\mu }, \\ \tilde{C}_3&:=C_3 \Bigl ( (g_1^{x_{1,\ell }})^{\texttt {I}}\prod _{j=0}^{\ell -1}\bigl ((g_1^{x_{1,j}})^{t_j}\bigr )(g_1^{x_2})^{\texttt {tag}}g_1^{x_3} \Bigr )^{-\mu }\\&\;=\,C_3g_1^{-\mu (\texttt {I}x_{1,\ell }+\sum _{j=0}^{\ell -1}(t_j x_{1,j})+x_2 \texttt {tag}+ x_3 )} \\&\;=\,g_1^{-(\alpha s + \mu )(\texttt {I}x_{1,\ell }+\sum _{j=0}^{\ell -1}(t_j x_{1,j})+x_2 \texttt {tag}+ x_3)}g_1^{s(\texttt {I}y_{1,\ell }+\sum _{j=0}^{\ell -1}(t_j y_{1,j})+y_2 \texttt {tag}+ y_3 )}, \end{aligned}$$

  and $\widetilde{\texttt {tag}}:=\texttt {tag}$, where .

• Semi-functional Decryption and Helper Key: Parse a normal helper key $hk_{\texttt {I},t_i}^{(i)}$ as $(R_i, D_{1},D'_{1},D_{2},D'_{2},D_3, \{(K_j,K'_j)\}_{j=0}^{i-1})$. A semi-functional helper key $\widetilde{hk}_{\texttt {I},t_i}^{(i)}:=(\tilde{R}_i, \tilde{D}_{1},\tilde{D}'_{1},\tilde{D}_{2},\tilde{D}'_{2},\tilde{D}_3, \{(\tilde{K}_j,\tilde{K}'_j)\}_{j=0}^{i-1})$ is computed as follows: $R_i:=\tilde{R}_i$,

  $$\begin{aligned}&\tilde{D}_1:=D_1 g_2^{\gamma }=g_2^{y_2r+\gamma }, \\&\tilde{D}'_1:=D_1 g_2^{\gamma \phi }=g_2^{y_0+r(\texttt {I}y_{1,\ell } + \sum _{j=i}^{\ell -1}(t_j y_{1,j}) + y_3)+\gamma \phi }, \\&\tilde{D}_2:=D_2 g_2^{-\frac{\gamma }{\alpha }}=g_2^{-r x_2 - \frac{\gamma }{\alpha }}, \\&\tilde{D}'_2:=D_2 g_2^{-\frac{\gamma \phi }{\alpha }} =g_2^{-x_0-r(\texttt {I}x_{1,\ell } + \sum _{j=i}^{\ell -1}(t_j x_{1,j}) + x_3)-\frac{\gamma \phi }{\alpha }}, \\&\tilde{D}_3:=D_3, \\&\tilde{K}_j\, :=K_j g_2^{\gamma \phi _j} = g_2^{r y_{1,j}+\gamma \phi _j} \ (0 \le j \le i-1), \\&\tilde{K}'_j\, :=K'_j g_2^{-\frac{\gamma \phi _j}{\alpha }} = g_2^{-r x_{1,j}-\frac{\gamma \phi _j}{\alpha }} \ (0 \le j \le i-1), \end{aligned}$$

  where . Note that $hk_{\texttt {I},t_0}^{(0)}$ means $dk_{\texttt {I},t_0}$ for any $t_0\in \mathcal {T}_0$. In particular, $\widetilde{hk}_{\texttt {I},t_0}^{(0)}$ ($=\widetilde{dk}_{\texttt {I},t_0}$) is called a semi-functional decryption key. We also note that in order to generate the semi-functional decryption or helper key, $g_2^{\frac{1}{\alpha }}$ is needed in addition to the public parameter.

A semi-functional ciphertext can be decrypted with a normal key. This fact can be easily checked by

$$\begin{aligned} \frac{e(g_1^{\mu (\texttt {I}y_{1,\ell }+\sum _{j=0}^{\ell -1}(t_j y_{1,j})+y_2 \texttt {tag}+ y_3 )},D_3)e(g_1,g_2)^{-x_0\mu }}{e(g_1^{\mu },D_1^{\texttt {tag}}D'_1)}=1. \end{aligned}$$

Also, a normal ciphertext can be decrypted with a semi-functional decryption key since it holds $e(C_1,g_2^{\gamma \texttt {tag}}g_2^{\gamma \phi })e(C_2,g_2^{-\frac{\gamma }{\alpha }\texttt {tag}}g_2^{-\frac{\gamma \phi }{\alpha }})=1$.

A helper or decryption key obtained by running the $\varDelta$ -Gen and Upd algorithms with a semi-functional helper key is also semi-functional.

Proof

(of Theorem 1). Based on [22, 25], we prove the theorem through a sequence of games. We first define the following games:

• ${{\mathbf {\mathsf{{Game}}}}}_{{\mathbf {\mathsf{{Real}}}}}{\varvec{:}}$ This is the same as the IND-KE-CPA game described in Sect. 3.

• ${{\mathbf {\mathsf{{Game}}}}}_{0}{\varvec{:}}$ This is the same as $\textsf {Game}_{\textsf {Real}}$ except that the challenge ciphertext is semi-functional.

• ${{\mathbf {\mathsf{{Game}}}}}_{k} \ (1 \le k \le q){\varvec{:}}$ This is the same as $\textsf {Game}_{0}$ except for the following modification: Let q be the maximum number of identities issued to the KG or KI oracles, and $\texttt {I}_i \ (1 \le i \le q)$ be an i-th identity issued to the oracles. If queries regarding the first k identities $\texttt {I}_1,\ldots ,\texttt {I}_{k}$ are issued, then semi-functional decryption and/or helper keys are returned. The rest of keys (i.e., keys regarding $\texttt {I}_{k+1},\ldots ,\texttt {I}_{q}$) are normal.

• ${{\mathbf {\mathsf{{Game}}}}}_{{\mathbf {\mathsf{{Final}}}}}{\varvec{:}}$ This is the same as $\textsf {Game}_{q}$ except that the challenge ciphertext is a semi-functional one of a random element of $\mathbb {G}_T$.

Let $S_{\textsf {Real}}$, $S_{k} \ (0 \le k \le q)$, and $S_{\textsf {Final}}$ be the probabilities that the event $b'=b$ occurs in $\textsf {Game}_{\textsf {Real}}$, $\textsf {Game}_{k}$, and $\textsf {Game}_{\textsf {Final}}$, respectively. Then, we have

$$\begin{aligned} Adv^{\textit{IND-KE-CPA}}_{\varPi _{ IKE },\mathcal {A}}(\lambda ) \le |S_{\textsf {Real}}-S_{0}|+\sum _{i=1}^{q}|S_{i-1}-S_{i}|+|S_{q}-S_{\textsf {Final}}|+|S_{\textsf {Final}}-\frac{1}{2}|. \end{aligned}$$

The rest of the proof follows from the following lemmas.

Lemma 1

If the DDH1 assumption holds, then it holds that $|S_{\textsf {Real}}-S_{0}|\le Adv^{DDH1}_{\mathcal {G},\mathcal {B}}(\lambda )$.

Proof

At the beginning, a PPT adversary $\mathcal {B}$ receives an instance $(g_1,g_1^{c_1},g_1^{c_2},g_2,T)$ of the DDH1 problem. Then, $\mathcal {B}$ randomly chooses $x_0,y_0,\{(x_{1,j},y_{1,j})\}_{j=0}^{\ell },x_2,y_2,x_3,$ , and creates

$$\begin{aligned}&z:=e(g_1^{c_1},g_2)^{-x_0}e(g_1,g_2)^{y_0}, \ u_{1,j}:=(g_1^{c_1})^{-x_{1,j}}g_1^{y_{1,j}} \ (0 \le j \le \ell ), \\&w_{1}:=(g_1^{c_1})^{-x_2}g_1^{y_2}, \ h_{1}:=(g_1^{c_1})^{-x_3}g_1^{y_3}. \end{aligned}$$

$\mathcal {B}$ sends $pp:=(g_1,g_1^{\alpha },\{u_{1,j}\}_{j=0}^{\ell },w_1,h_1,g_2,\{(g_2^{x_{1,j}},g_2^{y_{1,j}})\}_{j=0}^{\ell },g_2^{x_2},g_2^{x_3},g_2^{y_2},g_2^{y_3},z)$ to $\mathcal {A}$. Note that $\mathcal {B}$ knows a master key $mk:=(x_0,y_0)$ and we implicitly set $\alpha :=c_1$.

$\mathcal {B}$ can simulate the KG and KI oracles since $\mathcal {B}$ knows the master key.

In the challenge phase, $\mathcal {B}$ receives $(M_0^*,M_1^*,\texttt {I}^*,\texttt {time}^*)$ from $\mathcal {A}$. $\mathcal {B}$ chooses . $\mathcal {B}$ chooses , and let $t_j^*:=T_j(\texttt {time}^*) \ (0 \le j \le \ell -1)$. $\mathcal {B}$ computes

$$\begin{aligned}&C^*_0:=M_d e(T,g_2)^{-x_0}e(g_1^{c_2},g_2)^{y_0}, \ C^*_1:=g_1^{c_2}, \ C^*_2:=T, \\&C^*_3:=T^{-\texttt {I}^* x_{1,\ell }-\sum _{j=0}^{\ell -1}(t^*_j x_{1,j})-x_2 \texttt {tag}^* - x_3}(g_1^{c_2})^{\texttt {I}^* y_{1,\ell }+\sum _{j=0}^{\ell -1}(t^*_j y_{1,j}) + y_2 \texttt {tag}^* + y_3}. \end{aligned}$$

$\mathcal {B}$ sends $C^*:=(C^*_0,C^*_1,C^*_2,C^*_3,\texttt {tag}^*)$ to $\mathcal {A}$.

If $b=0$, then the above ciphertext is normal by setting $s:=c_2$. If $b=1$, then the above ciphertext is semi-functional since it holds

$$\begin{aligned} C^*_0&=\,M_d e(g_1,g_2)^{-x_0(c_1c_2+\mu )+ y_0 c_2}=M_d e(g_1,g_2)^{-x_0(\alpha s+\mu )+y_0 s}, \\ C^*_2&=\,g_1^{c_1 c_2+\mu }=g_1^{\alpha s+\mu }, \\ C^*_3&=\,g^{-(c_1c_2+\mu )(\texttt {I}^* x_{1,\ell }+\sum _{j=0}^{\ell -1}(t^*_j x_{1,j})+x_2 \texttt {tag}^* + x_3)}g_1^{c_2(\texttt {I}^* y_{1,\ell }+\sum _{j=0}^{\ell -1}(t^*_j y_{1,j}) + y_2 \texttt {tag}^* + y_3)} \\&=\,g^{-(\alpha s+\mu )(\texttt {I}^* x_{1,\ell }+\sum _{j=0}^{\ell -1}(t^*_j x_{1,j})+x_2 \texttt {tag}^* + x_3)}g_1^{s(\texttt {I}^* y_{1,\ell }+\sum _{j=0}^{\ell -1}(t^*_j y_{1,j}) + y_2 \texttt {tag}^* + y_3)}. \end{aligned}$$

After receiving $d'$ from $\mathcal {A}$, $\mathcal {B}$ sends $b'=1$ to the challenger of the DDH1 problem if $d'=d$. Otherwise, $\mathcal {B}$ sends $b'=0$ to the challenger.    $\square$

Lemma 2

For every $k\in \{1,\ldots ,q\}$, if the DDH2 assumption holds, then it holds that $|S_{k-1}-S_{k}|\le Adv^{DDH2}_{\mathcal {G},\mathcal {B}}(\lambda )$.

Proof

At the beginning, a PPT adversary $\mathcal {B}$ receives an instance $(g_1,g_2,g_2^{c_1},g_2^{c_2},T)$ of the DDH2 problem. Then, $\mathcal {B}$ randomly chooses $x'_0,y_0,\{(x'_{1,j},y'_{1,j},y''_{1,j})\}_{j=0}^{\ell },x'_2,x'_3,$ and , and (implicitly) sets

$$\begin{aligned}&x_0:=\frac{x'_0+y_0}{\alpha }, \ x_{1,j}:=\frac{x'_{1,j}+y_{1,j}}{\alpha }, \text { where } y_{1,j}:=y'_{1,j}+c_2 y''_{1,j} \ (0 \le j \le \ell ), \\&x_2:=\frac{x'_2+c_2}{\alpha }, \ y_2:=c_2, \\&x_3:=\frac{x'_3+y_3}{\alpha }, \text { where } y_3:=y'_3+c_2 y''_3. \end{aligned}$$

$\mathcal {B}$ creates

$$\begin{aligned}&z:=e(g_1,g_2)^{-x'_0}, \ u_{1,j}:=g_1^{-x'_{1,j}} \ (0 \le j \le \ell ), \ w_{1}:=g_1^{-x'_2}, \ h_{1}:=g_1^{-x'_3}, \\&g_2^{x_{1,j}}:=g_2^{\frac{x'_{1,j}+y'_{1,j}}{\alpha }}(g_2^{c_2})^{\frac{y''_{1,j}}{\alpha }} \ (0 \le j \le \ell ), \ g_2^{y_{1,j}}:=g_2^{y'_{1,j}}(g_2^{c_2})^{y''_{1,j}} \ (0 \le j \le \ell ), \\&g_2^{x_{2}}:=g_2^{\frac{x'_2}{\alpha }}(g_2^{c_2})^{\frac{1}{\alpha }}, \ g_2^{y_2}:=g_2^{c_2}, \ g_2^{x_3}:=g_2^{\frac{x'_{3}+y'_{3}}{\alpha }}(g_2^{c_2})^{\frac{y''_{3}}{\alpha }}, \ g_2^{y_{3}}:=g_2^{y'_{3}}(g_2^{c_2})^{y''_{3}}. \end{aligned}$$

$\mathcal {B}$ sends $pp:=(g_1,g_1^{\alpha },\{u_{1,j}\}_{j=0}^{\ell },w_1,h_1,g_2,\{(g_2^{x_{1,j}},g_2^{y_{1,j}})\}_{j=0}^{\ell },g_2^{x_2},g_2^{y_2},g_2^{x_3},g_2^{y_3},z)$ to $\mathcal {A}$. Note that $\mathcal {B}$ knows a master key $mk:=(x_0,y_0)$.

We show how $\mathcal {B}$ simulates the KG and KI oracles. Let $\texttt {I}_i \ (1 \le i \le q)$ be an i-th identity issued to the oracles. Without loss of generality, we consider $\mathcal {A}$ issues all identities $\texttt {I}_i \ne \texttt {I}^*$ to the KG oracle, and issues only queries regarding $\texttt {I}^*$ to the KI oracle.

KG Oracle. $\mathcal {B}$ creates $k-1$ semi-functional decryption and helper keys, and embeds T into the k-th keys. The rest of keys are normal.

• Case $i<k{\varvec{:}}$ After receiving $\texttt {I}_i$, $\mathcal {B}$ creates and returns semi-functional keys. Since $\mathcal {B}$ knows the master key and $\alpha$, $\mathcal {B}$ can create both normal and semi-functional keys.

• Case $i=k{\varvec{:}}$ After receiving $\texttt {I}_k$, $\mathcal {B}$ creates semi functional keys by embedding T as follows: $\mathcal {B}$ chooses and sets $B:=\sum _{j=0}^{\ell -1}\beta _{j}$. $\mathcal {B}$ computes

  $$\begin{aligned} R_j&:=g_2^{-\beta _j} \ (0 \le j < \ell ), \\ D_{1}&:=T, \\ D'_{1}&:=g_2^{y_0}(g_2^{c_1})^{\texttt {I}_k y'_{1,\ell }+y'_3}T^{\texttt {I}_k y''_{1,\ell }+y''_3}, \\ D_{2}&:=\Bigl ((g_2^{c_1})^{x'_2}T\Bigr )^{-\frac{1}{\alpha }}, \\ D'_{2}&:= g_2^{-\frac{x'_0}{\alpha }}(g_2^{c_1})^{-\frac{\texttt {I}_k(x'_{1,\ell }+y'_{1,\ell })+x'_3+y'_3}{\alpha }}g_2^{-\frac{y_0}{\alpha }}T^{-\frac{\texttt {I}_k y''_{1,\ell }+y''_3}{\alpha }}, \\ D_3&:=g_2^{c_1}g_2^{B}, \\ K_j&:=(g_2^{c_1})^{y'_{1,j}}(T)^{y''_{1,j}} \ (0 \le j \le \ell -1), \\ K'_j&:=(g_2^{c_1})^{-\frac{x'_{1,j}+y'_{1,j}}{\alpha }}T^{-\frac{y''_{1,j}}{\alpha }} \ (0 \le j \le \ell -1). \end{aligned}$$

  $\mathcal {B}$ sets $dk_{\texttt {I},0}:=R_0$, $hk^{(i)}_{\texttt {I},0}:=R_i \ (1 \le i \le \ell -1)$, $hk^{(\ell )}_{\texttt {I},0}:=(D_{1},D'_{1},D_{2},D'_{2},D_3,$ $\{(K_j,K'_j)\}_{j=0}^{\ell -1})$. If $b=0$, then it is easy to see that the above keys are normal by setting $r:=c_1$. If $b=1$, then the above ciphertext is semi-functional since it holds

  $$\begin{aligned} D_{1}:=&\, T=g_2^{c_1 c_2 +\gamma }=g_2^{y_2 r + \gamma }, \\ D'_{1}:=&\, g_2^{y_0}(g_2^{c_1})^{\texttt {I}_k y'_{1,\ell }+y'_3}T^{\texttt {I}_k y''_{1,\ell }+y''_3} \\ =&\, g_2^{y_0+c_1(\texttt {I}_k(y'_{1,\ell }+c_2 y''_{1,\ell })+y'_3+c_2 y''_3)}g_2^{\gamma (\texttt {I}_k y''_{1,\ell }+y''_3)} =g_2^{y_0+r(\texttt {I}_k y_{1,\ell }+y_3)}g_2^{\gamma \phi }, \\ D_{2}:=&\, \Bigl ((g_2^{c_1})^{x'_2}T\Bigr )^{-\frac{1}{\alpha }} =g_2^{-\frac{c_1(x'_2+c_2)}{\alpha }}g_2^{-\frac{\gamma }{\alpha }} =g_2^{-r x_2}g_2^{-\frac{\gamma }{\alpha }}, \\ D'_{2}:=&\, g_2^{-\frac{x'_0}{\alpha }}(g_2^{c_1})^{-\frac{\texttt {I}_k(x'_{1,\ell }+y'_{1,\ell })+x'_3+y'_3}{\alpha }}g_2^{-\frac{y_0}{\alpha }}T^{-\frac{\texttt {I}_k y''_{1,\ell }+y''_3}{\alpha }} \\ =&\, g_2^{-\frac{(x'_0+y_0)+c_1(\texttt {I}_k (x'_{1,\ell }+y'_{1,\ell }+c_2 y''_{1,\ell })+(x'_3+y'_3+ c_2y''_3))}{\alpha }}g_2^{-\frac{\gamma (\texttt {I}_k y''_{1,\ell }+y''_3)}{\alpha }} \\ =&\, g_2^{-x_0-r(\texttt {I}_k x_{1,\ell }+x_3)}g_2^{-\frac{\gamma \phi }{\alpha }}, \\ K_j:=&\, (g_2^{c_1})^{y'_{1,j}}(T)^{y''_{1,j}} =g_2^{c_1(y'_{1,j}+c_2 y''_{1,j})}g_2^{\gamma y''_{1,j}} =g_2^{r y_{1,j}}g_2^{\gamma \phi _{j}} \ (0 \le j \le \ell -1), \\ K'_j:=&\, (g_2^{c_1})^{-\frac{x'_{1,j}+y'_{1,j}}{\alpha }}T^{-\frac{y''_{1,j}}{\alpha }}\\ =&\, g_2^{-\frac{c_1(x'_{1,j}+y'_{1,j}+c_2 y''_{1,j})}{\alpha }}g_2^{-\frac{\gamma y''_{1,j}}{\alpha }} =g_2^{-r x_{1,j}}g_2^{-\frac{\gamma \phi _j}{\alpha }} \ (0 \le j \le \ell -1), \end{aligned}$$

  where $T:=g_2^{c_1 c_2 + \gamma }$, $r:=c_1$, $\phi :=\texttt {I}_k y''_{1,\ell }+y''_3$, and $\phi _j:=y''_{1,j} \ (0 \le j \le \ell -1)$. Since $y''_{1,j}$ and $y''_3$ are chosen uniformly at random, $\phi$ and $\phi _j$ are also uniformly distributed.

• Case $i>k{\varvec{:}}$ After receiving $\texttt {I}_i$, $\mathcal {B}$ creates and returns normal keys by using the master key.

KI Oracle. Suppose that $\mathcal {A}$ issues $k-1$ identities $\texttt {I}_1,\ldots ,\texttt {I}_{k-1}$ to the KG oracle, and then issues a query $(i, \texttt {I}^*, \texttt {time})$ (i.e., $\texttt {I}^*(=\texttt {I}_k)$) to the KI oracle. Note that for some special level $j\in \{0,\ldots ,\ell \}$, $\mathcal {A}$ cannot issue $\texttt {time}$ such that $T_i(\texttt {time})=T_i(\texttt {time}^*)$ if $i<j$ ($\mathcal {B}$ does not need to know where level is special one in advance). $\mathcal {B}$ creates and stores semi-functional decryption and helper keys $(\widetilde{d}_{\texttt {I}^*,0},\widetilde{hk}^{(1)}_{\texttt {I}^*,0},\ldots ,\widetilde{hk}^{(\ell )}_{\texttt {I}^*,0})$ as in the case $i=k$ of the KG oracle. We also note that from the second query, $\mathcal {B}$ answers queries by using the stored keys. Then, $\mathcal {B}$ repeatedly runs $\delta _{t_{j-1}}^{(j-1)}\leftarrow \varDelta$ -Gen $(hk^{(j)}_{\texttt {I}^*,t_j},\texttt {time}^*)$ and $hk^{(j-1)}_{\texttt {I}^*,t^*_{j-1}}$ Upd $(hk^{(j-1)}_{\texttt {I}^*,0},\delta _{t_{j-1}}^{(j-1)})$ for $j=\ell ,\ldots ,i+1$, where $t_\ell :=0$ and $t_j:=T_j(\texttt {time}) \ (0 \le j \le \ell -1)$. Again, the key generated by semi-functional helper keys is also semi-functional. $\mathcal {B}$ returns $hk^{(i)}_{\texttt {I}^*,t_{i}}$ to $\mathcal {A}$.

In the challenge phase, $\mathcal {B}$ receives $(M_0^*,M_1^*,\texttt {I}^*,\texttt {time}^*)$ from $\mathcal {A}$. $\mathcal {B}$ chooses , and sets $t_j^*:=T_j(\texttt {time}^*) \ (0 \le j \le \ell -1)$. However, $\mathcal {B}$ cannot create the semi-functional ciphertext for $\texttt {I}^*$ without knowledge of $c_2$ (and hence $y_{1,j} \ (0 \le j \le \ell )$ and $y_3$). To generate the semi-functional ciphertext without the knowledge, $\mathcal {B}$ sets

$$\begin{aligned} \widetilde{\texttt {tag}}^*\,:=\,-\sum _{j=0}^{\ell -1}(t^*_j y''_{1,j})-\texttt {I}^* y''_{1,\ell }-y''_3. \end{aligned}$$

Since $y''_{1,0},\ldots ,y''_{1,\ell }$ and $y''_3$ are chosen uniformly at random, probability distribution of $\widetilde{\texttt {tag}}^*$ is also uniformly at random from $\mathcal {A}$’s view.⁵ Then, $\mathcal {B}$ chooses , and computes

$$\begin{aligned} \tilde{C}^*_0:=\,&M^*_d z^{s} e(g_1,g_2)^{-x_0 \mu }=M^*_d e(g_1,g_2)^{-x_0(\alpha s + \mu )+y_0 s}, \\ \tilde{C}^*_1:=\,&g_1^{s}, \\ \tilde{C}^*_2:=\,&g_1^{\alpha s + \mu } \\ \tilde{C}^*_3:=\,&\Bigl (\prod _{j=0}^{\ell -1}\bigl (u_{1,j}^{t^*_j}\bigr )u_{1,\ell }^{\texttt {I}}w_1^{\widetilde{\texttt {tag}}^*}h_1\Bigr )^{s}g_1^{\mu (y'_3+\sum _{j=0}^{\ell -1}(t^*_j y'_{1,j})+\texttt {I}^* y'_{1,\ell })}\\ =\,&\Bigl (\prod _{j=0}^{\ell -1}\bigl (u_{1,j}^{t^*_j}\bigr )u_{1,\ell }^{\texttt {I}}w_1^{\widetilde{\texttt {tag}}^*}h_1\Bigr )^{s} \\&\cdot g_1^{\mu (\sum _{j=0}^{\ell -1}(t^*_j (y'_{1,j}+c_2 y''_{1,j}))+\texttt {I}^*(y'_{1,\ell }+c_2 y''_{1,\ell })+ c_2 \widetilde{\texttt {tag}}^*+y'_3+c_2 y''_3 )} \\&\qquad \qquad \qquad \qquad \qquad \qquad \cdot g_1^{-c_2 \mu (\sum _{j=0}^{\ell -1}(t^*_jy''_{1,j})+ \texttt {I}^* y''_{1,\ell }+\widetilde{\texttt {tag}}^*+y''_{3})} \\ =\,&\Bigl (\prod _{j=0}^{\ell -1}\bigl (u_{1,j}^{t^*_j}\bigr )u_{1,\ell }^{\texttt {I}}w_1^{\widetilde{\texttt {tag}}^*}h_1\Bigr )^{s} g_1^{\mu (\sum _{j=0}^{\ell -1}(t^*_j y_{1,j})+\texttt {I}^* y_{1,\ell }+ y_2 \widetilde{\texttt {tag}}^*+y_3)}. \end{aligned}$$

$\mathcal {B}$ sends $\widetilde{C}^*:=(\tilde{C}^*_0,\tilde{C}^*_1,\tilde{C}^*_2,\tilde{C}^*_3,\widetilde{\texttt {tag}}^*)$ to $\mathcal {A}$.

After receiving $d'$ from $\mathcal {A}$, $\mathcal {B}$ sends $b'=1$ to the challenger of the DDH2 problem if $d'=d$. Otherwise, $\mathcal {B}$ sends $b'=0$ to the challenger.    $\square$

Lemma 3

$|S_{q}-S_{\textsf {Final}}|\le \frac{q}{p}$.

Proof

We modify the setup procedure and the semi-functional keys generation procedure in $\textsf {Game}_{q}$, and the modification turns out $\textsf {Game}_{\textsf {Final}}$. We show that before and after the modification are statistically indistinguishable without probability $\frac{q}{p}$.

In the setup phase, we randomly choose $x'_0,y_0,\{(x'_{1,j},y_{1,j})\}_{j=0}^{\ell },x'_2,y_2,x'_3,y_3$ and , and set

$$\begin{aligned} x_0:=\frac{x'_0+y_0}{\alpha }, \ x_{1,j}:=\frac{x'_{1,j}+y_{1,j}}{\alpha } \ (0 \le j \le \ell ), \ x_2:=\frac{x'_2+y_2}{\alpha }, \ x_3:=\frac{x'_3+y_3}{\alpha }. \end{aligned}$$

$\mathcal {B}$ creates

$$\begin{aligned}&z:=e(g_1,g_2)^{-x'_0}, \ u_{1,j}:=g_1^{-x'_{1,j}} \ (0 \le j \le \ell ), \ w_{1}:=g_1^{-x'_2}, \ h_{1}:=g_1^{-x'_3}, \\&g_2^{x_{1,j}}:=g_2^{\frac{x'_{1,j}+y_{1,j}}{\alpha }} \ (0 \le j \le \ell ), \ g_2^{x_{2}}:=g_2^{\frac{x'_2+y_2}{\alpha }}, \ g_2^{x_3}:=g_2^{\frac{x'_3+y_3}{\alpha }}. \end{aligned}$$

We set $pp:=(g_1,g_1^{\alpha },\{u_{1,j}\}_{j=0}^{\ell },w_1,h_1,g_2,\{(g_2^{x_{1,j}},g_2^{y_{1,j}})\}_{j=0}^{\ell },g_2^{x_2},g_2^{y_2},g_2^{x_3},g_2^{y_3},z)$ and $mk:=(x_0,y_0)$.

When generating (initial) semi-functional keys, we choose $\beta _0,\ldots ,\beta _{\ell -1},r,{}\phi ',\phi '_{0},\ldots ,$ , and (implicitly) set $B:=\sum _{j=0}^{\ell -1}\beta _i$, $\phi ':=y_0+r(\texttt {I}y_{1,\ell }+y_3)+\gamma \phi$, and $\phi '_j:=r y_{1,j}+\gamma \phi _j \ (0 \le j \le \ell -1)$. We compute

$$\begin{aligned}&\tilde{R}_j\,:=\, g_2^{-\beta _j} \ (0 \le j \le \ell -1), \\&\tilde{D}_1\,:=\, g_2^{y_2 r + \gamma }, \\&\tilde{D}'_1\,:=\, g_2^{\phi '}=g_2^{y_0+r(\texttt {I}y_{1,\ell }+y_3)+\gamma \phi }, \\&\tilde{D}_2\,:=\, g_2^{-r\frac{x'_2+y_2}{\alpha }-\frac{\gamma }{\alpha }} =g_2^{-r x_2-\frac{\gamma }{\alpha }}, \\&\tilde{D}'_2\,:=\, g_2^{-\frac{1}{\alpha }(\phi '+x'_0+r(x'_3+\texttt {I}x'_{1,\ell }))} \\&\quad \;\;\, =\,g_2^{-\frac{1}{\alpha }(x'_0+y_0+r \texttt {I}(x'_{1,\ell }+y_{1,\ell })+\gamma \phi +r(x'_3+y_3))}\, =\,g_2^{-x_0-r (\texttt {I}x_{1,\ell }+ x_3)-\frac{\gamma \phi }{\alpha }}, \\&\tilde{D}_3\,:=\, g_2^{r+B}, \\&\tilde{K}_j\,:=\, g_2^{\phi '_j}=g_2^{r y_{1,j}+\gamma \phi _j} \ (0 \le j \le \ell -1), \\&\tilde{K}'_j\,:=\, g_2^{-\frac{r x'_{1,j}+\phi '_j}{\alpha }}=g_2^{-\frac{r (x'_{1,j}+y_{1,j})+\gamma \phi _j}{\alpha }}=g_2^{-r x_{1,j}-\frac{\gamma \phi _j}{\alpha }} \ (0 \le j \le \ell -1). \end{aligned}$$

We set $dk_{\texttt {I},0}:=\tilde{R}_0$, $hk_{\texttt {I},0}^{(j)}:=\tilde{R}_j \ (1 \le j \le \ell -1)$, and $hk_{\texttt {I},0}^{(\ell )}:=(\tilde{D}_1,\tilde{D}'_1,\tilde{D}_2,\tilde{D}'_2,\tilde{D}_3,$ $\{(\tilde{K}_j,\tilde{K}'_j)\}_{j=0}^{\ell -1})$. We emphasize that although the above secret keys are well-formed, $y_0$, $\{y_{1,j}\}_{j=0}^{\ell }$, and $y_3$ are not used in the above procedure.

On the other hand, the first component of the challenge ciphertext is generated as $\tilde{C}^*_0:= M_b z^s e(g_1,g_2)^{-x_0\mu }=M_b e(g_1,g_2)^{-x_0(\alpha s+\mu )+y_0}$. This means that $y_0$, which is independent of secret keys and public parameters, masks $\tilde{C}^*_0$, and hence $\tilde{C}^*_0$ becomes the ciphertext of a random element of $\mathbb {G}_T$.

Since $\gamma$ is chosen uniformly at random, $\phi$ and $\phi _j$ are distributed uniformly at random if $\gamma \ne 0$. An event that $\gamma = 0$ occurs with probability 1 / p. Every query regarding $\texttt {I}_i \ (1 \le i \le q)$ may cause this event, and hence, we have $|S_{q}-S_{\textsf {Final}}|\le \frac{q}{p}$.    $\square$

Proof of Theorem 1. From Lemmas 1, 2, and 3, we have $Adv^{\textit{IND-KE-CPA}}_{\varPi _{ IKE },\mathcal {A}}(\lambda ) \le |S_{\textsf {Real}}-S_{0}|+\sum _{i=1}^{q}|S_{i-1}-S_{i}|+|S_{q}-S_{\textsf {Final}}|+|S_{\textsf {Final}}-\frac{1}{2}|\le Adv^{\textit{DDH1}}_{\mathcal {G},\mathcal {B}}(\lambda )+q \cdot Adv^{\textit{DDH2}}_{\mathcal {G},\mathcal {B}}(\lambda )+\frac{q}{p}$.    $\square$

6 Chosen-Ciphertext Security

Boneh et al. [6] proposed an well-known transformation from $\ell +1$-level CPA-secure HIBE (and one-time signature (OTS)) to $\ell$-level CCA-secure HIBE. We cannot apply this transformation to a hierarchical IKE scheme in a generic way since it does not have delegating functionality. However, we can apply their techniques to the underlying Jutla–Roy HIBE of our hierarchical IKE, and therefore we obtain CCA-secure scheme. We show the detailed construction as follows. We assume a verification key vk is appropriately encoded as an element of $\mathbb {Z}_p$ when it is used in exponent of ciphertexts.

Let $\varPi _{\textit{OTS}}=(\textsf {KGen}, \textsf {Sign}, \textsf {Ver})$ be an OTS scheme.⁶ An $\ell$-level hierarchical IKE scheme $\varPi _{\textit{IKE}}=$(PGen, Gen, $\varDelta$ -Gen, Upd, Enc, Dec) is constructed as follows.

• PGen $(\lambda ,\ell )$: It runs $(\mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, p, g_1, g_2, e)\leftarrow \mathcal {G}$. It chooses $x_0,y_0,{}\{(x_{1,j},y_{1,j})\}_{j=0}^{\ell },$ and , and sets

  $$\begin{aligned}&z=e(g_1,g_2)^{-x_0\alpha +y_0}, \ u_{1,j}:=g_1^{-x_{1,j}\alpha +y_{1,j}} \ (0 \le j \le \ell ), \\&\hat{u}_1:=g_1^{-\hat{x}_{1}\alpha +\hat{y}_{1}}, \ w_{1}:=g_1^{-x_{2}\alpha +y_2}, \ h_{1}:=g_1^{-x_{3}\alpha +y_3}. \end{aligned}$$

  It outputs

  $$\begin{aligned}&pp:=(g_1,g_1^{\alpha },\{u_{1,j}\}_{j=0}^{\ell },\hat{u}_1,w_1,h_1,g_2,\{(g_2^{x_{1,j}},g_2^{y_{1,j}})\}_{j=0}^{\ell },\\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \;\;\, g_2^{\hat{x}_{1}},g_2^{\hat{y}_{1}},g_2^{x_2},g_2^{x_3},g_2^{y_2},g_2^{y_3},z),\\&msk:=(x_0,y_0). \end{aligned}$$

• Gen(mk, ID): It chooses , and let $B:=\sum ^{\ell -1}_{i=0}\beta _i$. It computes

  $$\begin{aligned}&R_j \; :=g_2^{-\beta _j} \ (0 \le j < \ell ), \\&D_{1}:=(g_2^{y_2})^{r}, \ D'_{1}:=g_2^{y_0}\Bigl ((g_2^{y_{1,\ell }})^{\texttt {I}}g_2^{y_3}\Bigr )^{r}, \\&D_{2}:=(g_2^{x_2})^{-r}, \ D'_{2}:=g_2^{-x_0}\Bigl ((g_2^{x_{1,\ell }})^{\texttt {I}}g_2^{x_3}\Bigr )^{-r}, \\&D_3:=g_2^{r+B}, \\&K_j \; :=(g_2^{y_{1,j}})^{r} \ (0 \le j \le \ell -1), \ K'_j:=(g_2^{x_{1,j}})^{-r} \ (0 \le j \le \ell -1), \\&K_{vk}:=(g_2^{\hat{y}_{1}})^{r}, \ K'_{vk}:=(g_2^{\hat{x}_{1}})^{-r}. \end{aligned}$$

  It outputs

  $$\begin{aligned}&dk_{\texttt {I},0}:=R_0, \ hk^{(i)}_{\texttt {I},0}:=R_i \ (1 \le i \le \ell -1), \\&hk^{(\ell )}_{\texttt {I},0}:=(D_{1},D'_{1},D_{2},D'_{2},D_3,\{(K_j,K'_j)\}_{j=0}^{\ell -1}, K_{vk}, K'_{vk}). \end{aligned}$$

• $\varDelta$ -Gen $(hk_{\texttt {I},t_i}^{(i)},\texttt {time})$: If $t_i\ne T_i(\texttt {time})$, it outputs $\bot$. Otherwise, parse $hk_{\texttt {I},t_i}^{(i)}$ as $(R_i, D_{1},D'_{1},$ $D_{2},D'_{2},D_3, \{(K_j,K'_j)\}_{j=0}^{i-1},K_{vk}, K'_{vk})$. It chooses $\hat{r}\leftarrow \mathbb {Z}_p$, and let $t_{j}:=T_{j}(\texttt {time}) \ (i-1 \le j \le \ell -1)$. It computes

  $$\begin{aligned}&\hat{d}_{1}:=D_{1} (g_2^{y_2})^{\hat{r}}, \ \hat{d}'_{1}:=D'_{1} (K_{i-1})^{t_{i-1}}\Bigl ((g_2^{y_{1,\ell }})^{\texttt {I}}\prod _{j=i-1}^{\ell -1}\bigl ((g_2^{y_{1,j}})^{t_j}\bigr )g_2^{y_3}\Bigr )^{\hat{r}}, \\&\hat{d}_{2}:=D_{2} (g_2^{x_2})^{-\hat{r}}, \ \hat{d}'_{2}:=D'_{2} (K'_{i-1})^{t_{i-1}}\Bigl ((g_2^{x_{1,\ell }})^{\texttt {I}}\prod _{j=i-1}^{\ell -1}\bigl ((g_2^{x_{1,j}})^{ t_j}\bigr )g_2^{x_3}\Bigr )^{-\hat{r}}, \\&\hat{d}_3:=D_3 g_2^{\hat{r}}, \\&\hat{k}_j\; :=K_j (g_2^{y_{1,j}})^{\hat{r}} \ (0 \le j \le i-2), \ \hat{k}'_j:=K'_j (g_2^{x_{1,j}})^{-\hat{r}} \ (0 \le j \le i-2), \\&\hat{k}_{vk}:=K_{vk} (g_2^{\hat{y}_{1}})^{\hat{r}}, \ \hat{k}'_{vk}:=K'_{vk} (g_2^{\hat{x}_{1}})^{\hat{r}}. \end{aligned}$$

  It outputs $\delta _{t_{i-1}}^{(i-1)}:=(\hat{d}_{1},\hat{d}'_{1},\hat{d}_{2},\hat{d}'_{2},\hat{d}_3, \{(\hat{k}_j,\hat{k}'_j)\}_{j=0}^{i-2},\hat{k}_{vk},\hat{k}'_{vk})$.

• Upd $(hk_{\texttt {I},t_i}^{(i)}, \delta _{\tau _i}^{(i)})$: Parse $hk_{\texttt {I},t_i}^{(i)}$ and $\delta _{\tau _i}^{(i)}$ as $(R_i, D_{1},D'_{1},D_{2},D'_{2},D_3, \{(K_j,K'_j)\}_{j=0}^{i-1},$ $K_{vk},K'_{vk})$ and $(\hat{d}_{1},\hat{d}'_{1},\hat{d}_{2},\hat{d}'_{2},\hat{d}_3, \{(\hat{k}_j,\hat{k}'_j)\}_{j=0}^{i-1},\hat{k}_{vk},\hat{k}_{vk})$, respectively. It computes $D_3:=\hat{d}_3R_i$, and sets $(D_j,D'_j):=(\hat{d}_j,\hat{d}'_j) \ (j=1,2)$, $(K_j,K'_j):=(\hat{k}_j,\hat{k}'_j) \ (0 \le j \le i-1)$, and $(K_{vk},K'_{vk}):=(\hat{k}_{vk},\hat{k}'_{vk})$. Finally, it outputs $hk_{\texttt {I},\tau _i}^{(i)}:=(R_i, D_{1},D'_{1},D_{2},D'_{2},$ $D_3, \{(K_j,K'_j)\}_{j=0}^{i-1},K_{vk},K'_{vk})$.

• Enc $(\texttt {I}, \texttt {time}, M)$: It first runs $(vk, sk)\leftarrow \textsf {KGen}(\lambda )$. It chooses . For $M\in \mathbb {G}_T$, it computes

  $$\begin{aligned}&C_0:=Mz^{s}, \ C_1:=g_1^{s}, \ C_2:=(g_1^{\alpha })^{s}, \ C_3:=\Bigl (\prod _{j=0}^{\ell -1}\bigl (u_{1,j}^{t_j}\bigr )u_{1,\ell }^{\texttt {I}}\hat{u}_{1}^{vk}w_1^{\texttt {tag}}h_1\Bigr )^{s}, \end{aligned}$$

  where $t_j:=T_j(\texttt {time}) \ (0 \le j \le \ell -1)$. It also runs $\sigma \leftarrow \textsf {Sign}(sk, (C_0,C_1,C_2,C_3,$ $\texttt {tag}))$, and outputs $C:=(vk,C_0,C_1,C_2,C_3,\texttt {tag},\sigma )$.

• Dec $(dk_{\texttt {I},t_0}, \langle C,\texttt {time}\rangle )$: If $t_0\ne T_0(\texttt {time})$, then it outputs $\bot$. Otherwise, parse $dk_{\texttt {I},t_0}$ and C as $(R_0, D_{1},D'_{1},D_{2},D'_{2},D_3,K_{vk},K'_{vk})$ and $(vk,C_0,C_1,C_2,C_3,$ $\texttt {tag},\sigma )$, respectively. If $\textsf {Ver}(vk, C_0,C_1,C_2,C_3,\texttt {tag},\sigma )\rightarrow 0$, then it outputs $\bot$. Otherwise, it computes

  $$\begin{aligned} \hat{D}'_{1}:=D'_{1} (K_{vk})^{vk}, \ \hat{D}'_{2}:=D'_{2} (K'_{vk})^{vk}. \end{aligned}$$

  Finally, it outputs

  $$\begin{aligned} M=\frac{C_0 e(C_3,D_3)}{e(C_1,D_1^{\texttt {tag}}\hat{D}'_1)e(C_2,D_2^{\texttt {tag}}\hat{D}'_2)}. \end{aligned}$$

The correctness of the above IKE scheme $\varPi _{\textit{IKE}}$ can be checked as in our CPA-secure IKE scheme described in Sect. 4.

We obtain the following theorem. The proof is omitted since this theorem can be easily proved by combining Boneh et al.’s techniques [6] and our proof techniques of Theorem 1.

Theorem 2

If the underlying OTS scheme $\varPi _{ OTS }$ is sUF-OT secure and the SXDH assumption holds, then the resulting $\ell$-level hierarchical IKE scheme $\varPi _{ IKE }$ is IND-KE-CCA secure.

7 Conclusion

In this paper, we first proposed hierarchical IKE scheme in the standard model. When the hierarchy is one, our scheme achieves constant-size parameters including public parameters, decryption and helper keys, and ciphertexts, and hence our scheme is more efficient than the existing scheme [32] in the sense of parameter sizes. Our scheme is based on the Jutla–Roy HIBE [22] (and its variant [25]) and techniques of threshold secret sharing schemes [4, 27].

A Definitions

We give the formal definitions of the CBDH and DBDH assumptions and OTS. In the following, we assume the Type-1 pairing (i.e., $\mathbb {G}:=\mathbb {G}_1=\mathbb {G}_2$).

Computational Bilinear Diffie–Hellman (CBDH) Assumption. Let $\mathcal {A}$ be a PPT adversary and we consider $\mathcal {A}$’s advantage against the CBDH problem as follows.

Definition 6

The CBDH assumption relative to a generator $\mathcal {G}$ holds if for all PPT adversaries $\mathcal {A}$, $Adv^{CBDH}_{\mathcal {G},\mathcal {A}}(\lambda )$ is negligible in $\lambda$.

Decisional Bilinear Diffie–Hellman (DBDH) Assumption. Let $\mathcal {A}$ be a PPT adversary and we consider $\mathcal {A}$’s advantage against the DBDH problem as follows.

Definition 7

The DBDH assumption relative to a generator $\mathcal {G}$ holds if for all PPT adversaries $\mathcal {A}$, $Adv^{DBDH}_{\mathcal {G},\mathcal {A}}(\lambda )$ is negligible in $\lambda$.

One-Time Signature. An OTS scheme $\varPi _{OTS}$ consists of three-tuple algorithms (KGen, Sign, Ver) defined as follows.

• $(vk,sk)\leftarrow \textsf {KGen}(\lambda )$: It takes a security parameter $\lambda$ and outputs a pair of a public key and a secret key (vk, sk).

• $\sigma \leftarrow \textsf {Sign}(sk,m)$: It takes the secret key sk and a message $m\in \mathcal {M}$ and outputs a signature $\sigma$.

• 1 or $0\leftarrow \textsf {Ver}(vk,m,\sigma )$: It takes the public key vk and a pair of a message and a signature $(m,\sigma )$, and then outputs 1 or 0.

We assume that $\varPi _{OTS}$ meets the following correctness property: For all $\lambda \in \mathbb {N}$, all $(vk,sk)\leftarrow \textsf {KGen}(\lambda )$, and all $m\in \mathcal {M}$, it holds that $1\leftarrow \textsf {Ver}(vk,(m,\textsf {Sign}(sk,m)))$.

We describe the notion of strong unforgeability against one-time attack (sUF-OT). Let $\mathcal {A}$ be a PPT adversary, and $\mathcal {A}$’s advantage against sUF-OT security is defined by

$\textit{Sign}(\cdot )$ is a signing oracle which takes a message m as input, and then returns $\sigma$ by running $\textsf {Sign}(sk,m)$. $\mathcal {A}$ is allowed to access to the above oracle only once.

Definition 8

An OTS scheme $\varPi _{OTS}$ is said to be sUF-OT secure if for all PPT adversaries $\mathcal {A}$, $Adv^{\textit{sUF-OT}}_{\varPi _{OTS},\mathcal {A}}(\lambda )$ is negligible in $\lambda$.