Efficient revocable hierarchical identity-based encryption using cryptographic accumulators

Abstract

Hierarchical identity-based encryption is an important extension from IBE and has found many applications in the network world. Private key revocation is a crucial requirement for any public key system. In this paper, we propose a novel revocation method for the hierarchical identity-based encryption. Existing revocable hierarchical identity-based encryption schemes have several disadvantages: the key update size increases logarithmically with the number of users in the system, the public information of key update received by each user is different and always related to the level of the identity hierarchy and the security proof of the revocable scheme is very complex. In our scheme, cryptographic accumulators are used to compress hierarchical levels and revoked users’ information into constant values. So we achieve almost constant size of private key update which is irrelevant with the user number in the system. Because of the compression of hierarchical information we can use simple dual system encryption techniques to prove our scheme to be fully secure under several common assumptions without resorting to complex nested dual system encryption techniques.

1 Introduction

Identity-based encryption (IBE) scheme allowing any bit-string to be the public key of a user was first introduced by Shamir [1]. Since Boneh and Franklin [2] gave the first efficient realization using bilinear pairings over elliptic curves, IBE has found many applications in securing today’s network world such as access control in the grid and cloud computing [3]. Several variations of IBE systems have been proposed by adding various special functionalities. In particular, the hierarchical identity-based encryption with private key delegation is especially useful for large organizations because such organization always has hierarchical structure and each department has the ability to generate private keys for users belonging to this department.

Although several efficient revocation schemes have been proposed for IBE, it is still difficult to directly apply previous revocation methods [13] to the hierarchical IBE. There are two difficulties in constructing revocable hierarchical IBE:

• 1. Ordinary approaches always lead to exponentially large secret keys in the corresponding hierarchical level.

• 2. The private key generations and private key updates are defined recursively which lead to some difficulties in proving the security of the hierarchical IBE.

To our best knowledge, there are three revocation schemes for the hierarchical IBE system. Tung-Tso TSAI [8] proposed a revocable HIBE in which a user’s private key (decryption key) is divided into two components: a fixed initial secret key and a changing time update key. Any user needed to get both the fixed initial secret key and the changing time update key to decrypt the ciphertext. They had proved the scheme to be fully secure but the key update overhead was not optimized and was proportional to the hierarchical level. When an organization had many hierarchical levels, the key update overhead in their scheme was very large. Jae Hong Seo [7] proposed another revocable hierarchical IBE system by applying the tree revocation structure to the hierarchical identity. The revocation cost for a user was the same as Boldyreva’s scheme [12]. The key update overhead was still high and the proof was very complex. Geumsook Ryu [9] first proposed an unbounded HIBE scheme where the maximum hierarchy depth was not limited by modifying an attribute-based encryption scheme and proved its selective security under a q-type assumption. Then they proposed an efficient unbounded RHIBE scheme by combining the unbounded HIBE scheme and a binary tree structure, and proved its selective security. The main contribution of [9] was solving the open problem of removing the limitation on maximum hierarchy. While our scheme aims at providing efficient revocation solution to practical HIBE applications and is proved to be fully secure using the dual system encryption techniques. This is the main difference between our scheme and [9].

In this work, we propose a novel revocable hierarchical IBE scheme with almost constant key update size which is irrelevant with hierarchical levels. We also prove our scheme to be fully secure using dual system encryption techniques.

1.1 Organization

The remainder of the work is organized as follows. Preliminary knowledge is given in Sect. 2. The concrete construction of our RHIBE scheme is proposed in Sect. 3. We analyze and prove the security of the proposed RHIBE in Sect. 4. We compare our scheme with three mostly related works in Sect. 5. In Sect. 6, we give the conclusion and future work.

2 Preliminaries

2.1 Bilinear map

We construct our revocable hierarchical IBE scheme based on the composite order bilinear groups. We let $\textit{F}$ denote an algorithm which takes a security parameter $\lambda$ as input and outputs a description of a bilinear map. We will define F’s output as $(N,G,G_T,e)$, where $N=p_1p_2p_3$ is a product of three distinct primes, G and $G_T$ are two cyclic groups with composite order N, and e is a bilinear map having the following characteristics:

• 1. (Bilinear) $\forall g,h\in G, a,b \in Z_N, e(g^a,h^b)=e(g,h)^{ab}$

• 2. (Non-degenerate) $\exists g \in G$ such that e(g, g) has order N in $G_T$. The group operations in G and $G_T$ are computable in polynomial time with respect to $\lambda$, and the group descriptions of G and $G_T$ include a generator of each group. We let $G_{p_1}$,$G_{p_2}$,$G_{p_3}$ denote the subgroups of order $p_1, p_2, p_3$ in G. We note that these subgroups are orthogonal to each other under the bilinear map e: i.e., if $h_i \in G_{p_i}$ and $h_j \in G_{p_j}$ for $i \ne j$, then $e(h_i, h_j)$ is the identity element in $G_T$. If $g_1$ generates $G_{p_1}, g_2$ generates $G_{p_2}$, and $g_3$ generates $G_{p_3}$, then every element h of G can be expressed as $g_1^xg_2^yg_3^z$ for some values $x, y, z \in Z_N$. We will refer to $g_1^x$ as the $G_{p_1}$ part of h, for example.

2.2 Complexity assumptions

In the assumptions below, we let $G_{p_1p_2}$ denote the subgroup of order $p_1p_2$ in G. We use the notation $X \leftarrow S$ to express that X is chosen uniformly randomly from the finite set S. We note that except for Assumption 2 and Assumption 5, all of these assumptions are special cases of the General Subgroup Decision Assumption defined in [10]. Informally, the General Subgroup Decision Assumption can be described as follows: in a bilinear group of order $N = p_1p_2 \ldots p_n$, there is a subgroup of order $\prod _{i\in S}{p_i}$ for each subset $S \subseteq \{1,2, \ldots ,n\}$. We let $S_0, S_1$ denote two such subsets. It should be hard to distinguish a random element from the subgroup corresponding to $S_0$ from a random element of the subgroup corresponding to $S_1$, even if one is given random elements from subgroups corresponding to other sets $S_i$ which satisfy either that $S_0 \cap S_i = \emptyset =S_1 \cap S_i$ or $S_0 \cap S_i \ne \emptyset \ne S_1 \cap S_i$.

Assumption 1

Given a group generator $\mathcal {G}$, we define the following distribution:

$$\begin{aligned} \varPsi= & {} (N=p_1p_2p_3, G, G_T, e) \mathop {\longleftarrow }\limits ^{R} \mathcal {G}\\&g\mathop {\longleftarrow }\limits ^{R} G_{p_1}\\ D= & {} (\varPsi , g);\\&T_1\mathop {\longleftarrow }\limits ^{R} G_{p_1p_2}, T_2\mathop {\longleftarrow }\limits ^{R} G_{p_1} \end{aligned}$$

We define the advantage of an algorithm $\mathcal {A}$ in breaking Assumption 1 to be:

$$\begin{aligned} Adv1_{\mathcal {G},\mathcal {A}}(\lambda ) =\left| Pr[\mathcal {A}(D, T_1) = 1] - Pr[\mathcal {A}(D, T_2) = 1] \right| \end{aligned}$$

We say that $\mathcal {G}$ satisfies Assumption 1 if $Adv1_{\mathcal {G},\mathcal {A}}(\lambda )$ is a negligible function of $\lambda$ for any PPT algorithm $\mathcal {A}$.

Assumption 2

Given a group generator $\mathcal {G}$, we define the following distribution:

$$\begin{aligned} \varPsi= & {} (N=p_1p_2p_3, G, G_T, e) \mathop {\longleftarrow }\limits ^{R} \mathcal {G}g\mathop {\longleftarrow }\limits ^{R} G_{p_1},\\&g_2,X_2,Y_2\mathop {\longleftarrow }\limits ^{R} G_{p_2},g_3\mathop {\longleftarrow }\limits ^{R} G_{p_3}, \alpha , s\mathop {\longleftarrow }\limits ^{R}Z_N\\ D= & {} (\varPsi , g,g_2,g_3,g^\alpha X_2, g^sY_2)\\ T_1= & {} e(g,g)^{\alpha s}, T_2\mathop {\longleftarrow }\limits ^{R} G_T \end{aligned}$$

We define the advantage of an algorithm $\mathcal {A}$ in breaking Assumption 2 to be:

$$\begin{aligned} Adv2_{\mathcal {G},\mathcal {A}}(\lambda ) =\left| Pr[\mathcal {A}(D, T_1) = 1] - Pr[\mathcal {A}(D, T_2) = 1] \right| \end{aligned}$$

We say that $\mathcal {G}$ satisfies Assumption 2 if $Adv2_{\mathcal {G},\mathcal {A}}(\lambda )$ is a negligible function of $\lambda$ for any PPT algorithm $\mathcal {A}$.

Assumption 3

Given a group generator $\mathcal {G}$, we define the following distribution:

$$\begin{aligned} \varPsi= & {} (N=p_1p_2p_3, G, G_T, e) \mathop {\longleftarrow }\limits ^{R} \mathcal {G}\\&g, X_1\mathop {\longleftarrow }\limits ^{R} G_{p_1}, g_2 \mathop {\longleftarrow }\limits ^{R} G_{p_2},X_3\mathop {\longleftarrow }\limits ^{R} G_{p_3}\\ D= & {} (\varPsi , g,g_2, X_1X_3)\\ T_1= & {} G_{p_1}, T_2\mathop {\longleftarrow }\limits ^{R} G_{p_1p_3} \end{aligned}$$

We define the advantage of an algorithm $\mathcal {A}$ in breaking Assumption 3 to be:

$$\begin{aligned} Adv3_{\mathcal {G},\mathcal {A}}(\lambda ) =\left| Pr[\mathcal {A}(D, T_1) = 1] - Pr[\mathcal {A}(D, T_2) = 1] \right| \end{aligned}$$

We say that $\mathcal {G}$ satisfies Assumption 3 if $Adv3_{\mathcal {G},\mathcal {A}}(\lambda )$ is a negligible function of $\lambda$ for any PPT algorithm $\mathcal {A}$.

Assumption 4

Given a group generator $\mathcal {G}$, we define the following distribution:

$$\begin{aligned} \varPsi= & {} (N=p_1p_2p_3, G, G_T, e) \mathop {\longleftarrow }\limits ^{R} \mathcal {G}\\&g, X_1\mathop {\longleftarrow }\limits ^{R} G_{p_1}, X_2,Y_2 \mathop {\longleftarrow }\limits ^{R} g_3, Y_3\mathop {\longleftarrow }\limits ^{R} G_{p_3}\\ D= & {} (\varPsi , g,g_3, X_1X_2,Y_2Y_3)\\ T_1= & {} G_{p_1p_3}, T_2\mathop {\longleftarrow }\limits ^{R} G \end{aligned}$$

We define the advantage of an algorithm $\mathcal {A}$ in breaking Assumption 4 to be:

$$\begin{aligned} Adv4_{\mathcal {G},\mathcal {A}}(\lambda ) =\left| Pr[\mathcal {A}(D, T_1) = 1] - Pr[\mathcal {A}(D, T_2) = 1] \right| \end{aligned}$$

We say that $\mathcal {G}$ satisfies Assumption 4 if $Adv4_{\mathcal {G},\mathcal {A}}(\lambda )$ is a negligible function of $\lambda$ for any PPT algorithm $\mathcal {A}$.

Assumption 5

Given a group generator $\mathcal {G}$, we define the following distribution:

$$\begin{aligned} \varPsi= & {} (G, G_T, e) \mathop {\longleftarrow }\limits ^{R} \mathcal {G}, \alpha \mathop {\longleftarrow }\limits ^{R} Z_N\\&g, f\mathop {\longleftarrow }\limits ^{R} G\\ \varPsi= & {} \left( G, f, g^\alpha , g^{\alpha ^2}, \ldots ,g^{\alpha ^l},g^{\alpha ^{l+2}}, \ldots ,g^{\alpha ^{2l}}\right) \\ T_1= & {} e(g^{\alpha ^{l+1}},f), T_2\mathop {\longleftarrow }\limits ^{R} G_T \end{aligned}$$

We define the advantage of an algorithm $\mathcal {A}$ in breaking Assumption 5 to be:

$$\begin{aligned} Adv5_{\mathcal {G},\mathcal {A}}(\lambda ) =\left| Pr[\mathcal {A}(D, T_1) = 1] - Pr[\mathcal {A}(D, T_2) = 1]\right| \end{aligned}$$

We say that $\mathcal {G}$ satisfies Assumption 5 if $Adv5_{\mathcal {G},\mathcal {A}}(\lambda )$ is a negligible function of $\lambda$ for any PPT algorithm $\mathcal {A}$.

2.3 Dynamic cryptographic accumulator

We use the dynamic cryptographic accumulator construction defined in [14] as the core component in our scheme. The construction of dynamic accumulator consists of five algorithms: AccGen, AccAdd, AccUpdate, AccWitUpdate and AccVerify.

2.4 Definition of the revocable HIBE

Definition 1

(Revocable HIBE) A RHIBE scheme for the identity space $\mathcal {I}$, time space $\mathcal {T}$, and the message space $\mathcal {M}$, consists of eight algorithms $\mathbf{Setup }$, $\mathbf{KeyGen }$, $\mathbf{Enc }$, $\mathbf{Dec }$, $\mathbf{KeyUpdate }$, $\mathbf{DecKeyGen }$, $\mathbf{KeyDelegate }$, $\mathbf{Revoke }$, which are defined as follows:

• Setup($\mathbf{1}^{\iota })$ : This algorithm takes as input a security parameter $\iota$. It outputs public parameters $PP$, a master secret key $MSK$, an (empty) revocation list $RL$, a state information $ST$.

• KeyGen($ID,PP,MSK$): This algorithm is run by the PKG. On input of a user’s identity ID, the public parameters PP, the master private key $MSK$, it outputs a private key $SK_{ID}$ for the identity $ID$.

• Enc($ID, M, PP, T_{val}$): This algorithm takes as input an identity ID, a message M, the public parameters PP and a time related value $T_{val}$. It outputs a ciphertext CT.

• Dec($DK _{ID}, PP, CT$): This algorithm takes as input a decryption key $DK_{ID}$, the public parameters $PP$, and the ciphertext CT. It outputs a plaintext message $M\in \text {M}$ or $\perp$ (invalid ciphertext).

• KeyUpdate($PP, MSK, RL, ST,T$): It takes the public parameters PP and the master secret key $MSK$, the revocation list RL and the state information ST and time T. It outputs the key update information KU at time T.

• DecKeyGen($SK_{ID}, PP, KU$): Given a private key $SK_{ID}$, key update information KU, and the public parameters PP, it outputs a decryption key $\hbox {DK}_{\mathrm{ID}}$, that can be used to decrypt matching ciphertext or $\perp$ which means the identity ID has been revoked.

• KeyDelegate($SK_{ID},{\textit{ID}}^{'} )$: It takes a private key for the identity ID and a user identity ${\textit{ID}}^{'}$ where the identity vector ID is a prefix of the identity ${\textit{ID}}^{'}$. This algorithm generates a private key for the identity ${\textit{ID}}^{'}$.

• Revoke($ID, T_{val}, RL, ST$): It takes an identity ID, a time related value $T_{val}$, the revocation list RL and the state information $ST$. It updates the revocation list RL and state information $ST$ by adding $ID$ as a revoked user at time T.

2.5 Security model of the revocable HIBE

Security is defined through the following game between a challenger and an attacker. We call the Game RHIBE.

Definition 2

We say that a RHIBE scheme is secure if no PPT adversary $\mathcal {A}$ has a non-negligible advantage in the following Game RHIBE played with a challenger $\mathcal {C}$.

• Phase 1. The challenger $\mathcal {C}$ runs the $Setup$ algorithm of RHIBE to generate a master secret key $MSK$, public parameters $PP$, a revocation list $RL$ and a state information $ST$. Then the challenger $\mathcal {C}$ gives the adversary $\mathcal {A}$ the $PP$ and keeps $MSK$, $RL$ and $ST$ to itself. We let S denote the set of private keys that the challenger has generated but not yet given to the adversary. We initialize $S = \phi$.

• Phase 2. The adversary $\mathcal {A}$ may issue a number of different queries to $\mathcal {C}$ as follows:

  • Key generation query. Upon receiving this query with an identity vector $ID = ({\textit{ID}}_1, \ldots ,{\textit{ID}}_j)$ at level j, the challenger $\mathcal {C}$ runs key generation algorithm to generate the secret key $SK_{ID}$ and places this key in the set S. The challenger $\mathcal {C}$ gives the adversary $\mathcal {A}$ only a reference to this secret key $SK_{ID}$, not the key itself.

  • Key delegation query. Upon receiving this query with a secret key $SK_{ID}$ in the set S and an identity vector ${\textit{ID}}^{'} = ({\textit{ID}}_1, \ldots {\textit{ID}}_j,{\textit{ID}}_{j+1})$ at level $j + 1$, the challenger $\mathcal {C}$ runs the key delegation algorithm to generate a secret key $SK_{ID'}$ for the identity vector ${\textit{ID}}^{'}$. The challenger $\mathcal {C}$ adds this key to the set S and gives the adversary $\mathcal {A}$ only a reference to this key.

  • Key reveal query. Upon receiving this query with an element of the set S, the challenger $\mathcal {C}$ gives this secret key to the adversary $\mathcal {A}$ and removes it from the set S.

  • Key update query. Upon receiving this query at time T, then $\mathcal {C}$ gives an update key KU by running the KeyUpdate($PP, MSK, RL, ST, T$) algorithm to the adversary $\mathcal {A}$.

  • Decryption key query. The adversary specifies an identity $ID$ whose private key is in the set S and queries its decryption key. Then $\mathcal {C}$ gives a decryption key $DK_{ID}$ by running the algorithm DecKeyGen($SK_{ID}, PP, KU$).

  • Key revocation query. If it is a revocation query for a private key of the identity ID at time T, then $\mathcal {C}$ updates the revocation list RL by running Revoke($ID, T_{val}, RL, ST$).

  • There is a restriction: $\mathcal {A}$ cannot request a revocation query for ID on time T if he already requested an update key query for ID.

• Phase 3. The adversary $\mathcal {A}$ gives a target identity vector ${\textit{ID}}^*$, a period $t^*$ and a plaintext pair $(M^*_0,M^*_1)$ to $\mathcal {B}$. A restriction here is that either ${\textit{ID}}^*$ or $({\textit{ID}}^*,t^*)$ did not appear in Phase 2. This identity vector must satisfy the property that no revealed identity in Phase 2 was a prefix of it. Then the challenger $\mathcal {B}$ chooses a random $b\in \{0, 1\}$ and computes $C^*$ by running the Enc algorithm. Then $\mathcal {B}$ sends $C^*$ to $\mathcal {A}$.

• Phase 4. The adversary $\mathcal {A}$ may issue more queries as in Phase 2. A restriction here is that either ${\textit{ID}}^*$ or $({\textit{ID}}^*,t^*)$ is disallowed to be queried in Phase 2. Any revealed identity in Phase 2 was not a prefix of ${\textit{ID}}^*$.

• Phase 5. The adversary $\mathcal {A}$ outputs $b'\in \{0, 1\}$ and wins this game if $b'= b$.

We define the adversary $\mathcal {A}$’s advantage in attacking the RHIBE scheme in the security game as $Adv^{{\textit{RHIBE}}}_\mathcal {A}(\iota )=|Pr[b=b']-1/2|$.

3 Construction of revocable hierarchical identity-based encryption

3.1 Main idea

We add revocation functionality to Lewko and Waters’ HIBE scheme [16] through the novel use of cryptographic accumulators. In our hierarchical identity-based encryption scheme, users are organized as hierarchical nodes in the organization tree. The non-leaf nodes corresponding to departments in a large organization can delegate private keys to their children nodes while the leaf nodes corresponding to ordinary members in the organization have no delegation capabilities. At the system startup, the root node constructs K subtree accumulator sets named $ACC^j_{subtree}, 0\le j \le K$. Each set comprises of all the nodes in each subtree of root node where the value of K is the number of the sub-trees of the root node and the root node is also included in each subtree accumulator set. Each non-leaf node i including the root node needs to construct and maintain its own children accumulator set called $ACC^i_{child}$ which includes all his child nodes. These two kinds of accumulator sets are all constructed at the system setup phase and maintained by their constructors. Then each node i except the root node lies in two accumulator sets, one is the subtree accumulator set $ACC^j_{subtree}$ where j denotes the jth subtree including node i, the other is the child accumulator set $ACC^k_{child}$ where k denotes the identifying number of node i’s parent node (Fig. 1).

Fig. 1

cryptographic accumulators on hierarchical nodes

When all subtree and child accumulator sets are constructed, each node i except the root node will receive two witness values from the root node and its parent node. We also call the root node root PKG and each non-leaf node sub-PKG. We assume that the root PKG generates private key for his children users while other users get private keys from their parent user through the private key delegation. The root PKG first generates a HIBE private key as the initial key, then it combines the witness of root node in the subtree accumulator set and the witness of the child node in the child accumulator set with the initial private key to form the final decryption key. Only when the initial private key is valid and each witness matches corresponding accumulator set value in the ciphertext, can the receiver decrypt the ciphertext. The most difficult problem for us is how to coordinate the revocation and delegation of the private key using cryptographic accumulators.

Revocation: When a user is revoked, this user and all his descendant nodes will be removed from the corresponding accumulator set. So the second witness in this user’s private key and the first witness in the children nodes’ private keys are unable to be updated. This will lead to the mismatching between witnesses in private keys and accumulator values in the ciphertext. Finally, private keys of affected users are revoked.

Delegation: Because a user lies in two cryptographic accumulator sets, so this user will get two witnesses. One is the witness of the subtree accumulator set, the other is the witness of the child accumulator set. When the non-leaf node i delegates private key to its child node, it first delegates initial private key to the child using the traditional method in HIBE. Then the child node’s first witness is set using node i’s witness in the subtree accumulator set and the child node’s second witness is set as the child node’s own witness in the child accumulator set constructed by node i.

3.2 Concrete construction

Our revocable hierarchical IBE scheme consists of eight algorithms: $\mathbf{Setup }$, $\mathbf{KeyGen }$, $\mathbf{Enc }$, $\mathbf{KeyUpdate }$, $\mathbf{DecKeyGen }$, $\mathbf{Dec }$,$\mathbf{KeyDelegate }$, $\mathbf{Revoke }$.

• $\mathbf{Setup }:$ The root PKG takes a security parameter $\iota$. The PKG generates two groups G and $G_T$ of order $N=p_1p_2p_3$, where $p_1,p_2,p_3$ are distinct primes, and a bilinear map $\hat{e}: G \times G \longrightarrow G_T$. Let $G_{p_i}$ denote the subgroup of order $p_i$ in G. Let $g_2$ denote a generator of $G_{p_2}$ and $g_3$ denote a generator of $G_{p_3}$. The root PKG randomly chooses $g, u, h, v, \varepsilon , z, f$ from $G_{p_1}$, and $\alpha , \gamma \in Z_N$. It also computes $e(g,g)^\alpha \in G_T$. Next, the root PKG prepares the basic public parameters for the construction of accumulators and let every non-leaf node use these parameters to construct its own cryptographic accumulator.

  • 1. runs the $PKSGen$ algorithm to generate a private-public key pair $(sk_i, pk_i)$ for each non-leaf node including the root node.

  • 2. calculates $z=e(g,g)^{\gamma ^{n+1}}\in G_T$ and $P_i=g^{(\gamma ^i)}\in G_{p_1}$ for $i=1,2, \ldots ,n,n+2, \ldots ,2n$ where $\gamma$ is randomly chosen from $Z_N$.

  • 3. chooses a random $\beta \in Z_N$ and computes $g^\beta \in G_{p_1}$. So the public parameter is set as

    $$\begin{aligned} PP= & {} \left( N,G,G_T,\hat{e}, g, u, h, v, \varepsilon , z, f, g^\beta , e(g,g)^\alpha ,\right. \\&z, pk_i, P_1, \ldots , P_n, P_{n+2}, \ldots ,P_{2n},\\&\left. P^\beta _1, \ldots , P^\beta _n, P^\beta _{n+2}, \ldots ,P^\beta _{2n}\right) , \end{aligned}$$

    the master secrete key $MK=(\alpha , \beta , \gamma , sk_{root})$. The $\mathbf{Setup }$ algorithm also constructs an empty revocation list $RL$ and the corresponding state information $ST$. Each node i also has its signing key $sk_i$ to be kept secret. The setup algorithm also chooses a collision-resistant hash function $\phi ()$ to hash a hierarchical identity ${\textit{ID}}=({\textit{ID}}_1, \ldots , {\textit{ID}}_j)$ into a value in the set [1 : n] to facilitate the computation in the cryptographic accumulator, $i=\phi (ID)$.

• $\mathbf{KeyGen }:$ The private key $SK_i$ for user i can be divided into two parts: One part is the initial private key $K_{init}$, the other is the witness key $K_{wit}$. Thus, the private key can be described as $SK_i =<K_{init}, K_{wit}>$. So the key generation algorithm is also divided into two parts.

  • Initial key generation: Given a user’s identity ${\textit{ID}}=({\textit{ID}}_1, \ldots , {\textit{ID}}_j)$, the root PKG chooses random values $r_1, \ldots , r_j, y_1, \ldots ,y_j$ from $Z_N$ and random values $\lambda _1,\lambda _2, \ldots ,\lambda _j \in Z_N$ subject to the constraint that $\alpha =\lambda _1+\lambda _2+ \ldots +\lambda _j$, and computes the initial key $K_{init}$ as follows:

    $$\begin{aligned}&K_{init}=<K_{l,0}, K_{l,1}, K_{l,2}, K_{l,3}>, \forall l \in \{1, \ldots ,j\},\\&\quad K_{l,0}=g^{\lambda _l}\varepsilon ^{y_l}, K_{l,1}=g^{y_l},\\&quad K_{l,2}=v^{y_l}(u^{{\textit{ID}}_l}h)^{r_l}, K_{l,3}=g^{r_l}, \end{aligned}$$

  • Witness key generation: The key generation algorithm chooses random values $R_3, R_3' \in G_{p_3}$. Let V denotes the set of identities that have currently been accumulated, so U and Q are subsets of V. The root PKG then performs the following steps:

    • 1. computes $w^{i'}_U=\prod \limits _{l\in U, l\ne i'}P_{n+1-l+i'}$

    • 2. computes $w^i_Q=\prod \limits _{l\in Q, j\ne i}P_{n+1-l+i}$

    • 3. updates the accumulator and corresponding state such that

      $$\begin{aligned} AC_{U\bigcup \{i'\}}= & {} AC_U\cdot P_{n+1-i'},\\ ST _{U\cup \{i'\}}= & {} \left\{ U\cup \{i'\},P_1, \ldots P_n,P_{n+2}, \ldots P_{2n}\right\} ,\\ AC_{Q\bigcup \{i\}}= & {} AC_Q\cdot P_{n+1-i},\\ ST _{Q\cup \{i\}}= & {} \left\{ Q\cup \{i\},P_1, \ldots P_n,P_{n+2}, \ldots P_{2n}\right\} . \end{aligned}$$

  In fact, when the root PKG updates the accumulator, the parent node $i'$ has already been added into the accumulator. The root PKG can computes the witness of the user’s parent at the same way. Then the witness key is computed as the follows:

  $$\begin{aligned} K_{wit}= & {} <K^1_w, K^2_w>\\ K^1_w= & {} P^\beta _{\phi ({\textit{ID}}^{'})}w^{\phi ({\textit{ID}}^{'})}_UR_3', K^2_w=P^\beta _{\phi (ID)}w^{\phi (ID)}_QR_3 \end{aligned}$$

• $\mathbf{Enc }:$ This algorithm takes as input a message M, a receiver’s identity ${\textit{ID}}=({\textit{ID}}_1, \ldots , {\textit{ID}}_j)$, the public parameters PP and a time related value $T_{val}$ which contains two up-to-date values $AC_U, AC_Q$ at time T. The $AC_U$ denotes the accumulated value of the subtree accumulator set U which is a simplified notation of $ACC^j_{subtree}$ containing the target receiver node and it’s parent node, and $AC_Q$ denotes the accumulated value of the child accumulator set Q containing the target receiver node. The identity of the parent node of the receiver is ${\textit{ID}}^{'}=({\textit{ID}}_1, \ldots , {\textit{ID}}_{j-1})$. The encryptor randomly chooses values $s,s', t_1, \ldots , t_j \in Z_n$ and computes the ciphertext as

  $$\begin{aligned}&C=(C_0,C_1,C_2,C_{l,3},C_{l,4},C_{l,5},C_6,C_7,C_8,C_9), \forall l \in \{1, \ldots ,j\}\\&C_0=\dfrac{Me(g,g)^{\alpha s}}{z^{s+s'}}, C_1=g^s, C_2=g^{s'}, C_{l,3}=\varepsilon ^sv^{t_l},\\&C_{l,4}=g^{t_l}, C_{l,5}=(u^{{\textit{ID}}_l}h)^{t_l}, \forall l \in \{1, \ldots ,j\}\\&C_6=\left( g^\beta AC_Ug^{\phi (ID)}\right) ^s, C_7=\left( g^\beta AC_Qg^{\phi ({\textit{ID}}^{'})}\right) ^{s'},\\&C_8=P^s_{\phi (ID)}, C_9=P^{s'}_{\phi ({\textit{ID}}^{'})} . \end{aligned}$$

• $\mathbf{KeyUpdate }:$ Each PKG reconstructs the cryptographic accumulator set by changing nodes in the set and computing the accumulated value. This algorithm outputs a public key update information KU and broadcasts it to corresponding user group.

  • 1. removes $h'=\phi (t')$ associated with the just expired time period $t'$ from V;

  • 2. removes all user identifier i that corresponds to $t'$ in RL from V.

  • 3. updates the accumulator which is $AC_V=\prod \limits _{i'\in V}P_{n+1-i'}$ for all $i'$ in the updated V.

  • 4. adds the new time period $q=\phi (t)\in [n]$ following the same steps as before in $KeyGen$ algorithm to compute the latest accumulator $AC_{V\cup \{q\}}$. It then generates a signature $\sigma _q$ on $AC_{V\cup \{q\}}$. The algorithm also prepares a set $\varDelta V$, which contains a list of recently joined and revoked users’ identifiers within the last (just expired) epoch. Then the $KeyUpdate$ algorithm broadcasts $KU = <AC_{V\cup \{q\}},\sigma _q,w_q>$ together with the set $\varDelta V$ to all users where the $w_q$ denotes the witness of new time t in the new accumulator set.

• $\mathbf{DecKeyGen }:$ This algorithm is run by each user to update his private key using the key update information. It takes as input the user’s private key $SK_{ID}$ and the public key update information. Each user i updates two witnesses in the private key after receiving the broadcasted key update information. User i first checks if:

  • 1. $\sigma _q$ is a valid signature associated with $AC_{V\cup \{q\}}$ using the $PKSVer$ algorithm and corresponding public key pk;

  • 2. $e(P_q, AC_{V \cup q} )=e(g, w_q) = z$ to ensure the correctness of $AC_V$. We set a Boolean flag denoted by $UpdKeyChk$ to 0 if any of the above two checks fails. If all the two conditions are satisfied, we set $UpdKeyChk$ = 1. If $UpdKeyChk$ = 0, then the key update algorithm outputs a special symbol $\perp$. Otherwise, user i replaces the existing accumulator with an up-to-date one. It then updates the witness as defined in [14]:

  • 1. if $i'\in U$ , computes

    $$\begin{aligned} (w^{i'}_U)'= w^{i'}_U\cdot \dfrac{\prod _{j\in U{\setminus } U_{i'}}P_{n+1-j+i}}{\prod _{j\in U_{i'}{\setminus } U}P_{n+1-j+i'}} \end{aligned}$$

  • 2. if $i \in Q$, computes

    $$\begin{aligned} (w^i_Q)'= w^i_Q\cdot \dfrac{\prod _{j\in Q{\setminus } Q_i}P_{n+1-j+i}}{\prod _{j\in Q_i{\setminus } Q}P_{n+1-j+i}} \end{aligned}$$

  where $U_{i'}$ and $Q_i$ are bookkeeping information sets recording the whole elements in sets U and Q when $i'$ and i got their witnesses $w^{i'}_U$ and $w^i_Q$. The expression $U{\setminus } U_{i'}$ means removing elements common to $U_{i'}$ and U from set U. This algorithm outputs the updated private key as the final decryption key.

• $\mathbf{KeyDelegate }:$ This algorithm is performed by each non-leaf node in the organization tree. The algorithm takes as input a secret key $SK _{ID}=(K_{l,0}, K_{l,1}, K_{l,2}, K_{l,3}, K^1_w, K^2_w), \forall l \in \{1, \ldots ,j\}$ for a user’s identity ${\textit{ID}}=({\textit{ID}}_1, \ldots , {\textit{ID}}_j)$ and its children identity ${\textit{ID}}^{''}=({\textit{ID}}_1, \ldots , {\textit{ID}}_j,{\textit{ID}}_{j+1})$ at level $j+1$. Its parent node identity is ${\textit{ID}}^{'}=({\textit{ID}}_1, \ldots , {\textit{ID}}_{j-1})$. The private key generation algorithm also takes in some public parameters corresponding to nodes ${\textit{ID}}^{'}, {\textit{ID}}_i, {\textit{ID}}^{''}$ : $P^\beta _{i'}, P^\beta _{i}, P^\beta _{i''}$. Then computes $\rho _1=(P_i/P_{i'})^\beta , \rho _2=(P_{i''}/P_i)^\beta$. In our scheme, the private key generation is divided into two parts: initial key generation and witness key generation. So the private key input is also divided and used by the two delegation parts separately.

  • Initial key delegation: The initial key delegation part chooses random values $r_1', \ldots , r_j',r_{j+1}',y_1', \ldots ,y_j',y_{j+1}'$ from $Z_N$ and random values $\lambda _1',\lambda _2', \ldots ,\lambda _j', \lambda _{j+1}'\in Z_N$ subject to the constraint that $\lambda _1'+\lambda _2'+ \ldots +\lambda _j'+\lambda _{j+1}'=0$. Finally, this algorithm computes the initial key for the user at level $j+1$ with the identity ${\textit{ID}}^{''}=({\textit{ID}}_1, \ldots , {\textit{ID}}_j,{\textit{ID}}_{j+1})$:

    $$\begin{aligned} K_{l,0}'= & {} K_{l,0}\cdot g^{\lambda _l'}\cdot w^{y_l'}, K_{l,1}'=K_{l,1}\cdot g^{y_l'},\\ K_{l,2}'= & {} K_{l,2}\cdot v^{y_l'}(u^{{\textit{ID}}_l}h)^{r_l'},\\ K_{l,3}'= & {} K_{l,3}\cdot g^{r_l'}, \forall l\in \{1, \ldots , j+1\}, \end{aligned}$$

    where $K_{j+1,1}, K_{j+1,2}, K_{j+1,3}$ are defined to be the identity element in G.

  • Witness key delegation: The witness key delegation part chooses randomly two group elements $T_3, T_3' \in G_{p_3}$, and computes:

    $$\begin{aligned} K^{1'}_w=K^1_w\rho _1T_3w^i_U/w^{i'}_U, K^{2'}_w =K^2_w\rho _2T_3'w^{i''}_{Q'}/w^i_Q. \end{aligned}$$

    where $Q'$ denotes the children accumulator set of node i and ID is the identity of its parent while ${\textit{ID}}^{''}$ is the identity of its children.

• $\mathbf{Dec }:$ The decryption algorithm takes in a decryption key

  $$\begin{aligned} DK_{ID} =\langle K_{l,0}, K_{l,1}, K_{l,2}, K_{l,3}, K^1_w, K^2_w\rangle , \forall l \in \{1, \ldots ,j\}, \end{aligned}$$

  the public parameters PP and a ciphertext CT which was encrypted using the identity $({\textit{ID}}_1, \ldots ,{\textit{ID}}_l)$. Assuming ${\textit{ID}}_1, \ldots , {\textit{ID}}_j$ is a prefix of $({\textit{ID}}_1, \ldots ,{\textit{ID}}_l)$, the message can be decrypted as follows. The decryption algorithm first computes:

  $$\begin{aligned} B'= & {} \prod \limits _{l=1}^j \dfrac{e(C_1,K_{l,0})e(C_{l,4}, K_{l,2})}{e(C_{l,3},K_{l,1})e(C_{l,5},K_{l,3})}\\= & {} e(g,g)^{\alpha s}\\ B''= & {} \dfrac{e\left( C_1,K^2_w\right) e\left( C_2,K^1_w\right) e\left( C_8,g^{\phi (ID)}\right) e\left( C_9, g^{\phi ({\textit{ID}}^{'})}\right) }{e\left( P_{\phi (ID)},C_6\right) e\left( P_{\phi ({\textit{ID}}^{'})},C_7\right) }\\= & {} 1/(z^{s+s'}) \end{aligned}$$

  The plaintext message in the ciphertext $C_0$ can be recovered by the following computation:

  $$\begin{aligned} M=C_0/(B'B'') \end{aligned}$$

• $\mathbf{Revoke }:$ When a user i is to be revoked, then this user and all its descendants will be revoked by adding them to the revocation list RL and removing corresponding nodes from the two accumulator sets.

3.3 Correctness

We give the complete correctness proof of the encryption scheme:

$$\begin{aligned} B'= & {} \prod \limits _{l=1}^j \dfrac{e(C_1,K_{l,0})e(C_{l,4}, K_{l,2})}{e(C_{l,3},K_{l,1})e(C_{l,5},K_{l,3})}\\= & {} \prod \limits _{l=1}^j \dfrac{e(g^s, g^{\lambda _l}\varepsilon ^{y_l})e\left( g^{t_l}, v^{y_l}(u^{{\textit{ID}}_l}h)^{r_l}\right) }{e(w^sv^{t_l},g^{y_l}) e\left( (u^{{\textit{ID}}_l}h)^{t_l},g^{r_l}\right) }\\= & {} \prod \limits _{l=1}^j \dfrac{e(g,g)^{s\lambda _l}e(g,\varepsilon )^{sy_l} e(g,v)^{t_ly_l}e(g,u^{{\textit{ID}}_l}h)^{t_lr_l}}{e(\varepsilon ,g)^{sy_l}e(v,g)^{t_ly_l}e(u^{{\textit{ID}}_l}h,g)^{t_lr_l}}\\= & {} \prod \limits _{l=1}^j e(g,g)^{s\lambda _i}\\= & {} e(g,g)^{s\alpha } \end{aligned}$$

since $\varSigma ^j_{l=1} \lambda _l =\alpha$

$$\begin{aligned}&B''=\dfrac{e\left( C_1,K^2_w\right) e\left( C_2,K^1_w\right) e\left( C_8,g^{\phi (ID)}\right) e\left( C_9, g^{\phi ({\textit{ID}}^{'})}\right) }{e\left( P_{\phi (ID)},C_6\right) e\left( P_{\phi ({\textit{ID}}^{'})},C_7\right) }\\&\quad =\dfrac{e\left( g^s, P^\beta _{\phi (ID)}w_{\phi (ID)}\right) e\left( g^{s'},P^\beta _{\phi ({\textit{ID}}^{'})} w_{\phi ({\textit{ID}}^{'})}\right) e\left( P^s_{\phi (ID)}, g^i\right) e\left( P^{s'}_{\phi ({\textit{ID}}^{'})}, g^{i'}\right) }{e\left( P_i, \left( g^\beta AC_P\phi (ID)\right) ^s\right) e\left( P_i', \left( g^\beta AC_Q\phi ({\textit{ID}}^{'})\right) ^{s'}\right) }\\&\quad =\dfrac{e(g,P_i)^{\beta s}e(g,P_{i'})^{\beta s'}e\left( g,w^i_Q\right) ^se\left( g,w^{i'}_U\right) ^{s'}e\left( P_i,g^i\right) ^s e\left( P_{i'}, g^{i'}\right) ^{s'}}{e(P_i, g)^{\beta s}e(P_i, AC_P)^se\left( P_i, g^i\right) ^se(P_{i'}, g)^{\beta s'}e(P_{i'}, AC_Q)^{s'}e\left( P_{i'}, g^{i'}\right) ^{s'}}\\&\quad =\dfrac{e\left( g,w^i_Q\right) ^se\left( g,w^{i'}_U\right) ^{s'}}{e(P_i, AC_P)^se(P_{i'}, AC_Q)^{s'}}\\&\quad =\Bigg (\dfrac{1}{e(g,g)^{\gamma ^{n+1}}}\Bigg )^{s+s'}\\&\qquad \hbox {since } \dfrac{e\left( P_i, AC_V\right) }{e(g,w^i_V)}=\dfrac{e(g,g)^{\varSigma _{k\in V}(\gamma ^{n+1-k+i})}}{e(g,g)^{\varSigma _{k\in V,k\ne i}(\gamma ^{n+1-k+i})}}\\&\quad =e(g,g)^{\gamma ^{n+1}}=z \end{aligned}$$

Thus the plaintext message M can be recovered by computing $M=C_0/(B'B'')$

4 Security proof

We use ordinary dual system encryption similar to proof techniques used in [15] to prove the security of our revocable hierarchical identity-based encryption scheme. In the proof, we will use several sequential security games. Next is the definition of main security games:

4.1 Security games

Game ${\textit{RHIBE}}_{{\textit{ND}}}$: Game ${\textit{RHIBE}}_{{\textit{ND}}}$ is the same as the Game RHIBE, except without delegation. For key delegation query, instead of making initial key generation, initial key delegation and initial key reveal queries, the adversary simply sends initial key generation queries to the challenger. For witness key delegation, instead of making witness key generation, witness key delegation, and witness key reveal queries, the adversary simply makes witness key generation queries. The only restriction is that no queried identity vectors can be prefixes of the challenge identity vector provided for the challenge ciphertext.

Game ${\textit{RHIBE}}_{{\textit{C}}}$: Game ${\textit{RHIBE}}_{{\textit{C}}}$ is the same as Game ${\textit{RHIBE}}_{{\textit{ND}}}$, except that the challenge ciphertext is generated by a call to $EncSF$ algorithm instead of the Enc algorithm (i.e., a semi-functional ciphertext is given to the adversary).

Game ${\textit{RHIBE}}_{{\textit{SF}}}$: Game ${\textit{RHIBE}}_{{\textit{SF}}}$ is the same as Game ${\textit{RHIBE}}_{{\textit{C}}}$, except that the challenger replaces all initial key generation and witness key update calls with calls to initial key generation SF and witness key update SF algorithms, respectively. Thus the challenge ciphertext, all the initial secret keys and all the witness update keys given to the adversary will be semi-functional.

4.2 Security properties of encryption scheme

Similar to four security properties of Lewko and Waters’s dual system encryption HIBE scheme, we need define four security properties for our dual system encryption RHIBE as follows:

Initial key and witness key delegation invariance: A RHIBE scheme D using dual system encryption techniques has initial key and witness key delegation invariance if for any PPT adversary $\mathcal {A}$, there exists another PPT adversary $\mathcal {A}$ such that the advantage of $\mathcal {A}$ in Game RHIBE is negligibly close to advantage of $\mathcal {A}$ in Game ${\textit{RHIBE}}_{{\textit{ND}}}$. We denote this as follows:

$$\begin{aligned} \left| Adv^{\mathcal {A}}_{\textit{RHIBE}} (\iota )-Adv^{\mathcal {A}}_{{\textit{RHIBE}}_{{\textit{ND}}}}(\iota )\right| = negl(\iota ). \end{aligned}$$

Semi-functional ciphertext invariance:A RHIBE scheme D using dual system encryption techniques has semi-functional ciphertext invariance if for any PPT adversary $\mathcal {A}$, the advantage of $\mathcal {A}$ in Game ${\textit{RHIBE}}_{{\textit{ND}}}$ is negligibly close to its advantage in Game ${\textit{RHIBE}}_{{\textit{C}}}$. We denote this as follows:

$$\begin{aligned} Adv^{\mathcal {A}}_{{\textit{RHIBE}}_{{\textit{ND}}}} (\iota )- Adv^{\mathcal {A}}_{{\textit{RHIBE}}_{{\textit{C}}}} (\iota )= negl(\iota ). \end{aligned}$$

Semi-functional initial key and witness key invariance: A RHIBE scheme D using dual system encryption techniques has semi-functional initial key and witness key invariance if for any PPT adversary $\mathcal {A}$, the advantage of $\mathcal {A}$ in Game ${\textit{RHIBE}}_{{\textit{C}}}$ is negligibly close to its advantage in Game ${\textit{RHIBE}}_{{\textit{SF}}}$. We denote this as follows:

$$\begin{aligned} Adv^{\mathcal {A}}_{{\textit{RHIBE}}_{{\textit{C}}}}(\iota )- Adv^{\mathcal {A}}_{ {\textit{RHIBE}}_{{\textit{SF}}} }(\iota )= negl(\iota ). \end{aligned}$$

Semi-functional security: A RHIBE scheme D using dual system encryption techniques has semi-functional security if for any PPT adversary $\mathcal {A}$, the advantages of $\mathcal {A}$ in Game ${\textit{RHIBE}}_{{\textit{SF}}}$ is negligible. We denote this as follows:

$$\begin{aligned} Adv^{\mathcal {A}}_{ {\textit{RHIBE}}_{{\textit{SF}}} } (\iota ) = negl(\iota ). \end{aligned}$$

Theorem 1

If a dual system encryption RHIBE scheme D = (System Setup, Enc, EncSF, Initial key generation, Initial key generation SF, Initial key delegation, Witness key generation, Witness key generation SF, Witness key delegation, Dec and Revoke) has initial key and witness key delegation invariance, semi-functional ciphertext invariance, semi-functional initial key and witness key invariance and semi-functional security, then $D'$=(System Setup, Enc, Initial key generation, Initial key delegation, Witness key generation, Witness key delegation, Dec and Revoke) is a secure RHIBE scheme.

Proof

Assume that an adversary $\mathcal {A}$ is a PPT adversary and there are no calls to the semi-functional algorithms EncSF, Initial key generate SF, Witness key generate SF of D in the real RHIBE game. Hence, from the adversary $\mathcal {A}$’s perspective, the adversary $\mathcal {A}$ plays the RHIBE game with D is the same as plays the RHIBE game with $D'$ which is presented as follows. By initial key and witness key delegation invariance, semi-functional ciphertext invariance, semi-functional initial key and witness key invariance, we have

$$\begin{aligned} Adv^{\mathcal {A}}_{\textit{RHIBE}}(\iota )-Adv^{\mathcal {A}}_{ {\textit{RHIBE}}_{{\textit{ND}}} } (\iota )= & {} negl(\iota ),\\ Adv^{\mathcal {A}}_{{\textit{RHIBE}}_{{\textit{ND}}}}(\iota )- Adv^{\mathcal {A}}_{{\textit{RHIBE}}_{{\textit{C}}}}(\iota )= & {} negl(\iota ),\\ Adv^{\mathcal {A}}_{{\textit{RHIBE}}_{{\textit{C}}}}(\iota ) -Adv^{\mathcal {A}}_{ {\textit{RHIBE}}_{{\textit{SF}}} }(\iota )= & {} negl(\iota ). \end{aligned}$$

Thus, from these three equalities above, we may conclude that

$$\begin{aligned} Adv^{\mathcal {A}}_{\textit{RHIBE}}(\iota )- Adv^{\mathcal {A}}_{ {\textit{RHIBE}}_{{\textit{SF}}} }(\iota )= negl(\iota ). \end{aligned}$$

The formula $Adv^{\mathcal {A}}_{\textit{RHIBE}} (\iota )$ must be negligible in the above triangle inequality, because semi-functional security is an existing property that implies the formula $Adv^{\mathcal {A}}_{ {\textit{RHIBE}}_{{\textit{SF}}} }(\iota )$ is negligible. Thus, we can say that the RHIBE scheme $D'$ is secure. In the following, we will give four lemmas to prove that our RHIBE scheme D = (System Setup, Enc, EncSF, Initial key generation, Initial key generation SF, Initial key delegation, Witness key delegation, KeyUpdate, KeyUpdate SF, Dec and Revoke) has four security properties including initial key and witness key delegation invariance, semi-functional ciphertext invariance, semi-functional initial key and witness key invariance, as well as semi-functional security. In our scheme, the ciphertext can be divided into two parts, one is the initial ciphertext which is the same as the one defined in [16] and we omit corresponding proof. The other is the accumulator related ciphertext. Our private key is also divided into two parts. One is the initial private key and the other is the witness key. The proof of the initial private key is the same as the proof in [16] and we omit here also. Next, we only give two semi-functionality definitions used in our proof and omit other semi-functional definitions used in the proof of the initial private key security. $\square$

Semi-functional accumulator ciphertext definition:

Let $g_2$ denote a generator of the subgroup $G_{p_2}$. A semi-functional accumulator ciphertext is then created as the following: first, generates a normal ciphertext $C_1, C_2, C_6, C_7, C_8, C_9$ using the encryption algorithm, then randomly chooses exponents $z_c, z_d, x,y\in Z_N$ and sets

$$\begin{aligned} C_1'= & {} C_1g^x_2, C_2'=C_2g^y_2,\\ C_6'= & {} C_6g^{z_d}_2, C_7=C_7g^{z_c}_2, C_8'=C_8, C_9'=C_9, \end{aligned}$$

The resulting tuple $(C_1', C_2', C_5', C_6', C_7', C_8', C_9')$ is a semi-functional accumulator ciphertext.

Semi-functional witness key definition:

We create semi-functional witness key as follows: firstly, generates the normal witness key $K^1_w, K^2_w$ using the witness key generation algorithm; then chooses random exponents $z^1_k, z^2_k\in Z_N$ and sets $K^1_{w'}= K^1_w\cdot g^{z^1_k}_2$ and $K^2_{w'}= K^2_w\cdot g^{z^2_k}_2$. Then $K^1_{w'}, K^2_{w'}$ is the semi-functional witness key. Next, we give definitions of four lemmas to prove THEOREM 1.

Lemma 1

Our dual system encryption RHIBE scheme has initial key and witness key delegation invariance.

Proof

For initial key delegation invariance, the Initial key delegation algorithm additively chooses random values

$$\begin{aligned} r_1', \ldots , r_j', r_{j+1}', y_1', \ldots , y_j', y_{j+1}', \lambda _1', \ldots , \lambda _j', \lambda _{j+1}'\in Z_N \end{aligned}$$

subject to the constraint that

$$\begin{aligned} \lambda _1' +\lambda _2' +\cdot \cdot \cdot +\lambda _j' +\lambda _{j+1}' = 0. \end{aligned}$$

It is obvious that the distribution of this initial secret key obtained through any sequence of delegations is the same as the distribution of the initial secret key for the same identity vector generated by a direct call to the initial key generation algorithm. For witness key delegation invariance, witness key delegation part of the algorithm also chooses two random values from $G_{p_3}$. The witness key $K^1_w$ is multiplied by $\rho _1$ and the random value $T_3$. After the multiplication the $P^\beta _{i'}$ part is transformed into $P^\beta _i$ which is the corresponding value of its children i. The delegation of the $K^2_w$ part of the witness key has similar property. So it is obvious that the distribution of the delegated witness key obtained through any sequence of delegations is the same as the distribution of the witness key for the same identity vector and period generated by a direct call to witness key generation algorithm. For any PPT adversary $\mathcal {A}$ in Game RHIBE, we can define a PPT adversary $\mathcal {A'}$ in Game ${\textit{RHIBE}}_{{\textit{ND}}}$ that obtains the same advantage. When $\mathcal {A}$ makes initial key generation, witness key generation, initial key delegation, witness key delegation and witness key update queries, $\mathcal {A'}$ makes no query. If $\mathcal {A}$ makes initial key reveal queries, then $\mathcal {A'}$ makes initial key generate queries for the same identity. When $\mathcal {A}$ makes witness key reveal queries, then $\mathcal {A'}$ makes witness key update queries for the same identity and period. Since the initial secret keys and the witness update keys that $\mathcal {A'}$ obtains have the same distribution as those keys that $\mathcal {A}$ obtains, their advantages are identical. $\square$

Lemma 2

Under Assumption 1, our dual system encryption RHIBE scheme has semi-functional ciphertext invariance.

Proof

Assume that there exists an adversary $\mathcal {A}$ which can distinguish Game ${\textit{RHIBE}}_{{\textit{ND}}}$ from Game ${\textit{RHIBE}}_{{\textit{C}}}$ with non-negligible advantage. We may construct a PPT algorithm $\mathcal {B}$ to break Assumption 1 with non-negligible advantage. We assume that the algorithm $\mathcal {B}$ is given $g \in G_{p_1}$ and t. $\mathcal {B}$ then chooses $a, b, c, d, n, \alpha , \beta , \gamma \in Z_N$ and computes $z = e(g, g)^{\gamma ^{n+1}}, P_i = g^{\gamma ^i}$, for $i \in [2n] \diagdown \{n + 1\}$, and sets $AC_P=1,AC_Q=1$; and generates a public-private key pair (pk, sk) using $PKSGen$ algorithm. Then $\mathcal {B}$ gives the public parameters

$$\begin{aligned} PP= & {} \left( N,G,G_T, \hat{e}, g, g^\beta , u=g^a,h = g^b, v = g^c,\varepsilon = g^d,\right. \\ f= & {} \left. g^n, \hat{e}(g, g)^\alpha , z, pk, AC_U, AC_Q, P_i, P^\beta _i \right) \end{aligned}$$

to the adversary $\mathcal {A}$. The algorithm $\mathcal {B}$ can use the system secret keys $\alpha$ and the witness secret key $\beta$ to respond to $\mathcal {A'}$s initial secret key and witness update key requests by calling Initial key generation and Witness key generation algorithms to return $\mathcal {A}$ the resulting keys, respectively. At some point, the adversary $\mathcal {A}$ provides a plaintext pair $(M^*_0,M^*_1 )$, a target identity vector ${\textit{id}}^*$ and a period $t^*$ to the algorithm $\mathcal {B}$. $\mathcal {B}$ then chooses random values $\eta , m_1, \ldots ,m_j \in Z_N$ and $b \in \{0, 1\}$, and computes the ciphertext $C^*$ as follows:

$$\begin{aligned}&C^*=(C^*_0, C^*_1, C^*_2, C^*_{l,3}, C^*_{l,4}, C^*_{l,5}, C^*_6, C^*_7, C^*_8, C^*_9), \forall l \in \{1, \ldots ,j\}\\&\quad =\Bigg (M^*_b \cdot \dfrac{e(g,T)^{\alpha }}{e(g,T)^{\gamma ^{n+1}} e(g,T)^{\eta \gamma ^{n+1}}}, T, T^\eta , T^dv^{m_i}, g^{m_i}, (u^{id^*_i}h)^{m_i},\\&\qquad \quad T^{\beta + \phi (ID)+\varSigma _{k\in U}\gamma ^{n+1-k}}, T^{\eta (\beta + \phi ({\textit{ID}}^{'})+\varSigma _{k\in Q}\gamma ^{n+1-k})}, T^{\gamma ^{\phi (ID)}}, T^{\eta {\gamma ^{\phi ({\textit{ID}}^{'})}}}\Bigg ) \end{aligned}$$

Since $C^*_1=T$,it implicitly sets $g^s$ equal to the $G_{p_1}$ part of T. If $T \in G_{p_1}$, $C^*$ is a well distributed normal ciphertext, and $\mathcal {B}$ has properly simulated Game ${\textit{RHIBE}}_{{\textit{ND}}}$. If $T \in G_{p_1p_2}$, $C^*$ is a well distributed semi-functional ciphertext (since the value of d modulo $p_2$ is uncorrelated from its value modulo $p_1$ by the Chinese Remainder Theorem). Hence, $\mathcal {B}$ has properly simulated Game ${\textit{RHIBE}}_{{\textit{C}}}$ in this case. By the above discussions, we say that $\mathcal {B}$ perfectly simulates the ciphertext $C^*$. Thus, $\mathcal {B}$ can use the output of $\mathcal {A}$ to achieve a non-negligible advantage against Assumption 1. It is obvious that the successful probability of $\mathcal {B}$ in breaking Assumption 1 is presented as

$$\begin{aligned} Adv1_{\mathcal {G},\mathcal {B}}= & {} |Pr[\mathcal {B}(G, g, T \in G_{p_1}) = 1]\\&-Pr[\mathcal {B}(G, g, T \in G_{p_1p_2} ) = 1]|. \end{aligned}$$

$\square$

Lemma 3

Under Assumptions 3 and 4, our dual system encryption RHIBE scheme has semi-functional initial key and semi-functional witness key invariance.

Proof

In our dual system encryption RHIBE, the semi-functional initial secret key and the semi-functional witness key are:

$$\begin{aligned} K_{init}&= \langle \tilde{K}_{l,0}, \tilde{K}_{l,1}, \tilde{K}_{l,2}, \tilde{K}_{l,3}\rangle , \text {for l}\in \left\{ 1, \ldots ,j\right\} \\&= {\left\{ \begin{array}{ll} \langle K_{l,0}, K_{l,1}, K_{l,2}, K_{l,3}\rangle , \text {for } l \in \left\{ 1, \ldots ,j-1\right\} .\\ \langle K_{l,0}\cdot (g_2g_3)^{\eta \cdot \hat{y}_j}, K_{l,1}\cdot (g_2g_3)^{\hat{y}_j},\\ \quad K_{l,2}\cdot (g_2g_3)^{\zeta \cdot \hat{y}_j},K_{l,3}\rangle , \text { for } l=j. \end{array}\right. }. \\ K_{wit'}&=\langle K^1_{w'}, K^2_{w'}\rangle \\&= \langle K^1_w\cdot g^{z^1_k}_2, K^2_w\cdot g^{z^2_k}_2 \rangle \end{aligned}$$

We add revocation functionality to Lewko’s HIBE scheme [16]. From the concrete construction, it is clear that the revocation security can be proved separately. The basic part of our scheme can still use the proof in [16]. In order to use dual system encryption in hierarchical IBE with limited public parameters, the proof in [16] becomes very complex. While in our revocation system, the hierarchical information is compressed using cryptographic accumulator and we needn’t to worry about the hierarchical information. So we can use ordinary dual system encryption techniques to prove the security of our revocation functionality. Next, we prove that our scheme has the semi-functional witness key invariance property. First, we define hybrid game ${\textit{RHIBE}}_{{\textit{k}}}$ with $0\le k \le q$, where q denotes the number of private key queries the attacker makes. In game ${\textit{RHIBE}}_{{\textit{k}}}$, the ciphertext given to the adversary $\mathcal {A}$ is semi-functional and the first k private keys are semi-functional. The rest of the keys are normal. In Game ${\textit{RHIBE}}_{0}$, all the keys are normal and the ciphertext is semi-functional. In Game ${\textit{RHIBE}}_{{\textit{q}}}$, the ciphertext and all of the keys are semi-functional. So the game ${\textit{RHIBE}}_{0}$ is exactly the game ${\textit{RHIBE}}_{{\textit{C}}}$ and the game ${\textit{RHIBE}}_{{\textit{q}}}$ is exactly the game ${\textit{RHIBE}}_{{\textit{SF}}}$. $\mathcal {B}$ first receives $g, X_1X_2, X_3, Y_2Y_3, T$. Then $\mathcal {B}$ sets the public parameters as follows: chooses random exponents $\eta , a, b, \alpha , \beta , \gamma \in Z_N$ and sets $g =g, u=g^a, h=g^b$; computes $z=e(g,g)^{\gamma ^{n+1}}, P_i= g^{\gamma ^i}$ for $i \in [2n] \diagdown \{n + 1\}$, and sets $AC_U=1, AC_Q=1$; and generates a public-private key pair (pk, sk) using $PKSGen$. $\mathcal {B}$ then forwards the public parameters $<N, u, g, h, g^\beta , e(g,g)^\alpha , z, pk, AC_U, AC_Q, P_i>$ to $\mathcal {A}$. Whenever $\mathcal {B}$ is asked to generate a private key for any identity ${\textit{ID}}_i$ where $i<k$, it chooses random exponents $t_1, t_2 \in Z_N$. Using the two sets U, Q containing the corresponding two sets of accumulated values, $\mathcal {B}$ sets the semi-functional witness key as:

$$\begin{aligned} K^1_{w'}= & {} P^\beta _i\prod \limits _{l\in U, l\ne i}P_{n+1-l+i}(Y_2Y_3)^{t_1}\\ K^1_{w'}= & {} P^\beta _{i'}\prod \limits _{l\in Q, l\ne i'}P_{n+1-l+i'}(Y_2Y_3)^{t_2}. \end{aligned}$$

This is a properly distributed semi-functional witness key with $Y^{t_1}_2=g^{z^1_k}_2$, $Y^{t_2}_2=g^{z^2_k}_2$. If the adversary $\mathcal {A}$ requests for the ith key for ${\textit{ID}}_i$ where $i > k$, $\mathcal {B}$ chooses a random exponent $t_1, t_2 \in Z_N$ and sets normal witness key as:

$$\begin{aligned} K^1_{w'}= & {} P^\beta _i\prod \limits _{l\in U, l\ne i}P_{n+1-l+i}X^{t_1}_3,\\ K^2_{w'}= & {} P^\beta _{i'}\prod \limits _{l\in Q, l\ne i'}P_{n+1-l+i'}X^{t_2}_3. \end{aligned}$$

To deal with the kth private key query, $\mathcal {B}$ sets $z_k=a\cdot {\textit{ID}}_K+b$, and chooses a random exponent $t_1, t_2\in Z_N$, then sets:

$$\begin{aligned} K^1_{w'}= & {} T^{z_k}P^\beta _i\prod \limits _{l\in U, l\ne i}P_{n+1-l+i}X^{t_1}_3,\\ K^2_{w'}= & {} T^{z_k}P^\beta _{i'}\prod \limits _{l\in Q, l\ne i'}P_{n+1-l+i'}X^{t_2}_3. \end{aligned}$$

At the challenge phase, the adversary sends two messages $M_0$ and $M_1$, with a challenge identity vector time pair $(ID^*, t^*)$. $\mathcal {B}$ first uses the current accumulator associated with time $t^*$ and the challenge pair to check the value of $UpdKeyChk$. If $UpdKeyChk = 0$ then $\mathcal {B}$ just guesses the value randomly, otherwise $\mathcal {B}$ chooses $d \in \{0,1\}$ randomly and sets the accumulator ciphertext as:

$$\begin{aligned} C_0= & {} M_d\dfrac{e(g,X_1X_2)^\alpha }{e(g, X_1X_2)^{\gamma ^{n+1}}e(g, X_1X_2)^{\eta \gamma ^{n+1}}},\\ C_1= & {} X_1X_2, C_2=(X_1X_2)^\eta \\ C_6= & {} (X_1X_2)^{\beta + \phi (ID)+\varSigma _{k\in V}\gamma ^{n+1-k}},\\ C_7= & {} (X_1X_2)^{\eta (\beta + \phi ({\textit{ID}}^{'})+\varSigma _{k\in V}\gamma ^{n+1-k})},\\ C_8= & {} (X_1X_2)^{\gamma ^{\phi (ID)}}, C_9=(X_1X_2)^{\eta \gamma ^{\phi ({\textit{ID}}^{'})}}. \end{aligned}$$

So the tuple ${<}C_0, C_1, C_2, C_6, C_7, C_8, C_9{>}$ is a properly distributed semi-functional accumulator ciphertext. If $T \in G_{p_1p_3}$, then $\mathcal {B}$ has properly simulated $Game_{k-1}$. If $T \in G$, then $\mathcal {B}$ has properly simulated $Game_k$. So if the adversary $\mathcal {A}$ can find differences between $Game_{k-1}$ and $Game_{k}$, then $\mathcal {B}$ could distinguish the possibilities for the value of T. According to the relationship among games ${\textit{RHIBE}}_{{\textit{C}}}$, ${\textit{RHIBE}}_{0}$, ${\textit{RHIBE}}_{{\textit{q}}}$, ${\textit{RHIBE}}_{{\textit{SF}}}$, we can conclude that:

$$\begin{aligned} Adv^{\mathcal {A}}_{{\textit{RHIBE}}_{{\textit{C}}}}(\iota )- Adv^{\mathcal {A}}_{ {\textit{RHIBE}}_{{\textit{SF}}} }(\iota )= negl(\iota ). \end{aligned}$$

$\square$

Lemma 4

Under Assumption 2 and Assumption 5, our dual system encryption RHIBE scheme has semi-functional security. We take into account two types of adversaries:

• Type I adversaries that never make a private key query on the target identity ID at any time throughout the game.

• Type II adversaries that are allowed to make a private key query on the target identity ID at some point of the game, provided that the queried identity must subsequently be revoked before the challenge time $t^*$. Then we split game ${\textit{RHIBE}}_{{\textit{SF}}}$ into two games corresponding to two types of adversaries, as follows:

  ${\textit{RHIBE}}_{{\textit{SF1}}}$ is the same as game ${\textit{RHIBE}}_{{\textit{SF}}}$ except that the challenge ciphertext is a semi-functional encryption of a random message, embedded with an instance of the hard problem defined by Assumption 2.

  ${\textit{RHIBE}}_{{\textit{SF2}}}$ is the same as game ${\textit{RHIBE}}_{{\textit{SF1}}}$, except that here, we embed a instance of the hard problem defined by Assumption 5. At the outset of the game, the simulator $\mathcal {B}$ flips a coin $r\longleftarrow \{0,1\}$ as the guess for the type of adversary it will face: 0 for Type I and 1 for Type II. The game then proceed from ${\textit{RHIBE}}_{{\textit{C}}}$ to ${\textit{RHIBE}}_{{\textit{q}}}$. After ${\textit{RHIBE}}_{{\textit{q}}}$, if $\mathcal {B}$ faces a Type I adversary, it will proceed to ${\textit{RHIBE}}_{{\textit{SF1}}}$, otherwise, it will proceed to game ${\textit{RHIBE}}_{{\textit{SF2}}}$. In what follows, we prove that these games are indistinguishable from the attacker’s viewpoint. The proof of lemma 4 is divided into two parts. One is for the negligibility of the adversary’s advantage in game ${\textit{RHIBE}}_{{\textit{SF1}}}$, the other for game ${\textit{RHIBE}}_{{\textit{SF2}}}$. Finally, we can get that the adversary’s advantage in game ${\textit{RHIBE}}_{{\textit{SF}}}$ is negligible.

  Proof for the first game: The simulator $\mathcal {B}$ first receives challenge tuple $\langle g, g^\alpha X_2, X_3, g^sY_2, Z_2, T\rangle$. Then it set the public parameters as those in lemma 3 except that it sets $e(g,g)^\alpha$ as $e(g^\alpha X_2,g)$ without choosing a random exponent $\alpha$. $\mathcal {B}$ computes $z^s=e(g, g^sY_2)^{\gamma ^{n+1}}$ and give it to the adversary $\mathcal {A}$. When $\mathcal {A}$ requests for the private key for ${\textit{ID}}_i$, $\mathcal {B}$ chooses random exponents $\eta , t_1,t_2, c_1,c_2\in Z_N$ and computes the semi-functional witness key as :

  $$\begin{aligned} K^1_w= & {} P^\beta _i\prod \limits _{l\in U, l\ne i}P_{n+1-l+i}Z^{c_1}_2X^{t_1}_3,\\ K^2_w= & {} P^\beta _{i'}\prod \limits _{l\in Q, l\ne i'}P_{n+1-l+i'}Z^{c_2}_2X^{t_2}_3\\ \end{aligned}$$

  At the challenge phase, the adversary sends two messages $M_0$ and $M_1$, with a challenge identity vector time pair $(ID^*, t^*)$. $\mathcal {B}$ first uses the current accumulator associated with $t^*$ and the challenge pair to check the value of $UpdKeyChk$. If $UpdKeyChk = 0$ then $\mathcal {B}$ just guesses the value randomly, otherwise $\mathcal {B}$ chooses $d \in \{0,1\}$ randomly and sets the accumulator ciphertext as:

  $$\begin{aligned} C_0= & {} M_d\dfrac{T}{e(g, g^sY_2)^{\gamma ^{n+1}}e(g, g^sY_2)^{\eta \gamma ^{n+1}}}, \\ C_1= & {} g^sY_2, C_2=(g^sY_2)^\eta ,\\ C_6= & {} (g^sY_2)^{\beta + \phi (ID)+\varSigma _{k\in V}\gamma ^{n+1-k}},\\ C_7= & {} (g^sY_2)^{\eta ({\beta + \phi ({\textit{ID}}^{'})+\varSigma _{k\in V}\gamma ^{n+1-k}})},\\ C_8= & {} (g^sY_2)^{\gamma ^{\phi (ID)}}, C_9=(g^sY_2)^{\eta \gamma ^{\phi ({\textit{ID}}^{'})}}. \end{aligned}$$

  Given the value $z^s=e(g, g^sY_2)^{\gamma ^{n+1}}$, the adversary $\mathcal {A}$ tries to distinguish the possibilities of T. If $T = e(g, g)^{\alpha s}$, then this is a properly generated semi-functional ciphertext with message $M_d$. If T is a random element of $G_T$, then the ciphertext is a semi-functional accumulator ciphertext with a random message. Thus $\mathcal {B}$ could use the output of $\mathcal {A}$ to distinguish between possible values of T.

  Proof for the second game: The simulator $\mathcal {B}$ first receives an instance of the OBDHE hard problem.

  $$\begin{aligned} g, f, \{P_i\}_{i\in [1, \ldots 2n]/(n+1)}, v, T \end{aligned}$$

  where $f=g^s$ for some random $s \in Z_N, P_i=g^{\gamma ^i}, v= g^\beta$. $\mathcal {B}$ also has oracle access to $\varOmega ^{D,H}_{g,e}$ which is specified by the assumption. $\mathcal {B}$ is required to distinguish if $T=e(g^{\gamma ^{n+1}}, f)$ or T is a random element of $G_T$. $\mathcal {B}$ then chooses a random exponent $\alpha \in Z_N$. It can compute $z=e(g,g)^{\gamma ^{n+1}}$ using the pair $e(P_{n+1-i}, P_i)$ formed by the given values $(P_{n+1-i}, P_i)$ for any i. It sets $AC_U=1, AC_Q=1$. Then $\mathcal {B}$ generates a public-private key pair (sk, pk) using $PKSGen$ and gives the public parameters

  $$\begin{aligned} \langle N, g, g^\beta , e(g,g)^\alpha , z, pk, AC_U, AC_Q, P_i, P^{\beta }_i\rangle \end{aligned}$$

  to the adversary $\mathcal {A}$. $\mathcal {B}$ also needs to compute and give $e(g,g)^{\alpha s}= e(g, f)^\alpha$ to $\mathcal {A}$. When the adversary $\mathcal {A}$ requests for the private key for ${\textit{ID}}_i$, $\mathcal {B}$ first chooses random exponents $c_1, c_2, y_1, y_2 \in Z_N$ and selects $Z_2 \in G_{p_2}, X_3 \in G_{p_3}$, then $\mathcal {B}$ queries the oracle $\varOmega ^{D,H}_{g,e}(P_i, v)$ and gets the output $P^\beta _i$ since $v = g^\beta$. $\mathcal {B}$ can get $P^\beta _{i'}$ using oracle query $\varOmega ^{D,H}_{g,e}(P_{i'}, v)$ and computes the semi-functional witness key as :

  $$\begin{aligned} K^1_w= & {} P^\beta _i\prod \limits _{l\in U, l\ne i}P_{n+1-l+i}Z^{c_1}_2X^{y_1}_3,\\ K^2_w= & {} P^\beta _{i'}\prod \limits _{l\in Q, l\ne i'}P_{n+1-l+i'}Z^{c_2}_2X^{y_2}_3 \end{aligned}$$

  Table 1 Efficiency comparison

  At the challenge phase, the adversary sends two messages $M_0$ and $M_1$, with a challenge identity vector time pair $(ID^*, t^*)$. $\mathcal {B}$ first uses the current accumulator associated with $t^*$ and the challenge pair to check the value of $UpdKeyChk$. If $UpdKeyChk = 0$ then $\mathcal {B}$ just guesses the value randomly, otherwise $\mathcal {B}$ chooses $d \in \{0,1\}$ randomly and selects random values $\eta \in Z_N, Y_2 \in G_{p_2}$. Then $\mathcal {B}$ computes the accumulator ciphertext as:

  $$\begin{aligned} C_0= & {} M_d\dfrac{e(g,f)^\alpha }{T\cdot T^{\eta }}, C_1=fY_2, C_2=(fY_2)^{\eta }\\ C_6= & {} (fY_2)^{\beta + \phi (ID)+\varSigma _{k\in U}\gamma ^{n+1-k}},\\ C_7= & {} (fY_2)^{\eta (\beta + \phi ({\textit{ID}}^{'})+\varSigma _{k\in Q}\gamma ^{n+1-k})},\\ C_8= & {} (fY_2)^{\gamma ^{\phi (ID)}}, C_9=(fY_2)^{\eta (\gamma ^{\phi ({\textit{ID}}^{'})})}. \end{aligned}$$

  $\mathcal {B}$ needs to transform the ciphertext $C_6, C_7$ into semi-functional without knowing the value of $\beta$. So $\mathcal {B}$ computes $\omega = v\varSigma _{j \in U}P_{n+1-j}g^{\phi (ID)}$, $\omega '= v\varSigma _{j' \in Q}P_{n+1-j'}g^{\phi ({\textit{ID}}^{'})}$ and makes two oracle queries $\zeta =\varOmega ^{D,H}_{g,e}(\omega , f)$ and $\zeta '=\varOmega ^{D,H}_{g,e}(\omega ', f^\eta )$. Next, $\mathcal {B}$ receives two outputs of the oracle and computes:

  $$\begin{aligned} \zeta= & {} \left( g^\beta \varSigma _{j \in U}P_{n+1-j}g^{\phi (ID)}\right) ^s = \left( g^\beta AC_Ug^{\phi (ID)}\right) ^s\\ \zeta '= & {} \left( g^\beta \varSigma _{j' \in Q}P_{n+1-j'}g^{\phi ({\textit{ID}}^{'})}\right) ^{\eta s} = \left( g^\beta AC_Qg^{\phi ({\textit{ID}}^{'})}\right) ^{\eta s} \end{aligned}$$

  $\mathcal {B}$ chooses a random value $u_i,u_i'\in Z_N$ and sets

  $$\begin{aligned} C_6=\zeta Y^{u_i}_2, C_7=\zeta ' Y^{u_i'}_2. \end{aligned}$$

Given the value $e(g, g)^{\alpha s} = e(g, f)^\alpha$, the remaining task of $\mathcal {A}$ is simply to distinguish the possibilities of T. If $T = e(g^{\gamma ^{n+1}},f)=e(g,g)^{\gamma ^{n+1}s}=z^s$, then this is a properly generated semi-functional accumulator ciphertext with message $M_d$. If T is a random element of $G_T$, then the ciphertext is a semi-functional accumulator one with a random message. Thus $\mathcal {B}$ could use the output of $\mathcal {A}$ to distinguish between the possibilities of T. From the proof of the two games above, we can conclude that the advantages of $\mathcal {A}$ in Game ${\textit{RHIBE}}_{{\textit{SF}}}$ is negligible and then We can prove THEOREM 1 based on proofs of the four lemmas.

5 Efficiency comparison

As far as we know, there are three revocable hierarchical identity-based encryption schemes which are related to our scheme. In [7], the ciphertext size of the scheme is almost the same as that of the [11] and only adds one additional group element. Thus the ciphertext size is $l+3$ where l denotes the identity hierarchical level. The revocation cost of each user increases logarithmically in the number of users. Moreover, a user with identity level l needs to manage $O(l^2 logN)$-size secret key (polynomial in the hierarchical depth). This revocable hierarchical IBE is proved to be selective-ID secure under the Decisional Bilinear Diffie-Hellman (DBDH) assumption in the standard model.

Tung-Tso TSAI [8] proposed a new revocation scheme for hierarchical identity-based encryption where a user’s private key is divided into two parts: One is the initial private key and the other is the time key. The private key update equals to time key update. When a user is revoked, the PKG sends time key update information which contains $4l_i$ group elements related to hierarchical identity level $l_i$ of user i to each non-revoked user via public channel to update the time key. So the key update size for each revocation is $4l_i$ where $l_i$ is the hierarchical identity level of user i. Ryu [9] proposed a tree-based revocation method for HIBE supporting unbounded hierarchical levels, so the key update cost was similar to [7].

Our scheme achieves almost constant private key update size by utilizing several cryptographic accumulators. Cryptographic accumulators are constructed and maintained by each sub-PKG and the root PKG, so the computation burden is distributed among all PKGs. Only when the membership changes, does the corresponding PKG reconstruct the accumulator and recompute the membership witness. Each user in the hierarchical structure belongs to two cryptographic accumulators: One is subtree accumulator set maintained by the root PKG, the other is child accumulator set maintained by the user’s parent node. When a user is revoked, it only affects these two accumulators. Only the non-revoked users in these two accumulator sets can update the private key after receiving public information. The two PKGs need sending the following public information to all users belonging to the two accumulator sets :

$$\begin{aligned}&\langle AC_U, Sig_{PKG_i}(AC_U) , w_t, \varDelta _U\rangle , \langle AC_Q,\\&\quad Sig_{PKG_j}(AC_Q) , w_{t'}, \varDelta _Q \rangle \end{aligned}$$

where $PKG_i$ and $PKG_j$ denotes the PKG in charge of the accumulation set U and Q. All non-revoked users in the accumulator set can update their witness part of private keys using received public information which is irrelevant with user’s hierarchical identity level while each revoked user can not update their private key. So we can conclude that our scheme achieves almost constant size of private key update during each user revocation. The generation and verification of the signature on the accumulator value constitute one major part of the additional computation cost for sub-PKGs and users, but they will not seriously affect the efficiency of our scheme because of the low computation complexity for each sub-PKG and user. The other computation cost for each PKG composes of the maintenance of its child accumulator set. So the additional computational cost compared with other similar RHIBE schemes is distributed among each non-leaf node and slightly reduces the efficiency of our scheme.

We compare our scheme with these three works in Table 1 where the l denotes a user’s identity level and the n denotes the number of all users.

6 Conclusion and future work

In this work, we propose a novel revocable hierarchical identity-based encryption with almost constant size of private key update. Information compression and simple security proof are two outstanding features of the cryptographic accumulator in constructing revocable public encryption scheme. Caution is needed to construct such scheme because naive combination of cryptographic accumulator with public encryption scheme will incur collusion attacks. Properly dividing system users into different accumulator sets can satisfy different requirements such as revocation in the hierarchical structure and distribute the overhead of accumulator update among different sub-PKGs. The hierarchical attribute-based encryption still lacks proper revocation mechanism. Applying cryptographic accumulator to hierarchical attribute-based encryption will be a challenging task because of the complexity of hierarchical attributes. we prepare to construct a revocable hierarchical attribute-based encryption scheme using similar techniques in the future.