Enhancing Attribute-Based Encryption with Attribute Hierarchy

Abstract

Attribute-based encryption (ABE) has been envisioned as a promising cryptographic primitive for realizing secure and flexible access control. However, ABE is being criticized for its high scheme overhead as extensive pairing operations are usually required. In this paper, we focus on improving the efficiency of ABE by leveraging a previously overlooked fact, i.e., the often-found hierarchical relationships among the attributes that are inherent to many access control scenarios. As the first research effort along this direction, we coin the notion of hierarchical ABE (HABE), which can be viewed as the generalization of traditional ABE in the sense that both definitions are equal when all attributes are independent. We further give a concrete HABE construction considering a tree hierarchy among the attributes, which is provably secure. More importantly, our construction exhibits significant improvements over the traditional ABE when attribute hierarchies exist.

1 Introduction

Recently, much attention has been attracted by a new public-key primitive called Attribute-based encryption (ABE). ABE has significant advantage over the traditional PKC primitives as it achieves flexible one-to-many encryption instead of one-to-one. ABE thus is envisioned as an important tool for addressing the problem of secure and fine-grained data sharing and access control. In ABE, the encryption keys and/or ciphertexts are labeled with sets of descriptive attributes defined for the system users. And a particular user private key can decrypt a particular ciphertext only if the two match. A party could encrypt a document to all users who have a certain set of attributes drawn from a pre-defined attribute universe. For example, one can encrypt a tenure-evaluation related document to all of tenured faculty in computer science department. In this case the document would be encrypted to the attribute subset {“Faculty”, “CS Dept.”, “Tenured”}, and only users with all of these three attributes in the university can hold the corresponding private keys and thus decrypt the document, while others cannot.

ABE, on the other hand, is often being criticized for its high scheme overhead as extensive pairing operations are usually required. In this paper, we focus on improving the efficiency of ABE by leveraging a previously overlooked fact, i.e., the often-found hierarchical relationships among the attributes that are inherent to many access control scenarios. The notion of HABE is proposed in this paper to address the tree hierarchy structure, which can be viewed as the generalization of traditional ABE in the sense that both definitions are equal when all attributes are independent. In HABE, the universal attributes are classified into trees according to their relationship defined in the access control system. Every node in this tree is associated with an attribute, and an ancestral node can derive its descendant’s key, but the reverse is not allowed. Assume the attributes form n trees. For attribute ω, we assume its depth is k in the i-th tree, and its path from root ω _i0 in the i-th tree is defined as (ω _i0, ω _i1, ⋯ , ω _{i,k − 1}, ω _ik ), where ω _ik  = ω ¹. We say that ω covers ω′ with path (ω′_j0, ω′_j1, ⋯ , ω′_jk′) if ω _iδ  = ω′ _jδ for 0 ≤ δ ≤ k. It means that ω has higher level priority than ω′ in the access control system if ω covers ω′. For convenience, we first define some notations. Recall that we wish to create an HABE scheme in which a ciphertext can be decrypted only by users with the following property: the number of users’ attributes that cover the attributes included in ciphertext is no less than a pre-defined number d. Before decryption, the user can get an attribute set $\textsf{U}$ from the attribute center. Assume the ciphertext is created with respect to an attribute set $\textsf{U}'$. The user with $\textsf{U}$ is able to decrypt the ciphertext for $\textsf{U}'$ if and only if the number of attributes in $\textsf{U}$ that cover $\textsf{U}'$ is no less than d. This kind of ABE could be used in distributed systems so that a user is able to access data only if he or she possesses a certain set of credentials or attributes. To construct such ABE directly without taking advantage of the hierarchical structure, the size of private key or the ciphertext will grow linearly with the number of decedents or depth of the attribute. In our HABE, part of attributes are allowed to have hierarchical tree relationship and the remaining attributes are independent. Therefore, our construction can achieve both flexibility and practicality.

1.1 Related work

ABE is one of the important applications of fuzzy identity-based encryption (fuzzy IBE, in short) [20] proposed by Sahai and Waters. In fuzzy IBE, the identity is viewed as a set of descriptive attributes. A user with secret key for ω is able to decrypt a ciphertext encrypted with ω′ if and only if ω and ω′ are within a certain distance of each other as judged by some metric. As for [20], this distance is measured by set-overlap between identities. Due to the error-tolerance property, fuzzy IBE can be applied to enable encryption by using biometric inputs as identities. To reduce the trust of attribute authority, Chase [6] proposed a multi-authority attribute-based encryption scheme. In this protocol, each authority controls some of the attributes, and this scheme can also be extended to support tree-structure [11]. Recently, there are several attempts to construct attribute-based signature in both [15, 17]. They presented attribute (ring) signature to achieve signer privacy. These schemes are not trivial to be constructed by using technique in [9] since the anonymity for user is required.

There are two methods for access control based on ABE: Key-policy ABE (KP-ABE) and ciphertext-policy ABE (CP-ABE). Both notions are proposed in [11] by Goyal et al. In KP-ABE, each attribute private key is associated with an access structure and each ciphertext is labeled with a set of attributes. The attribute private key can only decrypt a specific type of ciphertext if the access policy defined in the attribute private key matches the attributes listed in the ciphertext. The first KP-ABE construction [11] can realize the monotonic access structures for key policies. To enable more flexible access policy, Ostrovsky et al. [19] presented the first KP-ABE system that supports the expression of non-monotone formulas in key policies. In a CP-ABE system, a user’s key is associated with a set of attributes and an encrypted ciphertext will specify an access policy over attributes. CP-ABE is different from KP-ABE in the sense that the encryptor assigns certain access policy for the ciphertext. When a message is being encrypted, it will be associated with an access structure over a pre-defined set of attributes. Bethencourt et al. [2] proposed the first CP-ABE construction. However, the construction in [2] is only proved under the generic group model. In view of this weakness, Cheung and Newport [7] presented another construction that is proved to be secure under the standard model. Later, in [10], Goyal et al. gave another construction for more advanced access structures based on number theoretic assumption. To better protect user privacy, anonymous CP-ABE was constructed in [12] and further improved in [14, 18]. Recently, the accountability in the ABE-based access control has been considered by [14, 16, 22] to prevent the key-abuse problem, for both CP-ABE and KP-ABE schemes. Boneh and Waters [5] proposed a predicate encryption scheme based on the primitive called Hidden Vector Encryption. Their scheme can also realize the anonymous CP-ABE by using the opposite semantics of subset predicates. Katz, Sahai, and Waters [13] proposed a novel predicate encryption scheme supporting inner product predicates and their scheme is very general and can realize both KP-ABE and hidden CP-ABE schemes.

1.2 Contribution

In this paper, we make the following contributions: (i) The model of HABE is formalized; (ii) To obtain a provably secure HABE under tree hierarchy, the technique of hierarchical identity-based encryption is utilized in combination with the secret sharing techniques in ABE; (iii) We show through detailed analysis that our construction is very efficient: the computation cost in generation of ciphertext is low and the length of the ciphertext is short.

Organization

In Section 2, the model for HABE is formalized, as well as the construction. Its security analysis under the established model is also presented. In Section 3, we show how to implement such HABE and give its efficiency analysis. Section 4 is the concluding remarks.

2 Building blocks: the HABE schemes

2.1 Syntax

In this section, we first give the definition and security model of HABE. Then, a provably secure construction of HABE is presented. When one encrypts a message m for a set of target attributes (without loss of generality, let $\textsf{U}=\{\omega_1$, ⋯, ω _k }), anyone can decrypt the ciphertext if he has at least d attributes that cover the attributes in $\textsf{U}$. The distance d should be pre-determined in setup algorithm, which will be used in the encryption and decryption algorithms. However, in some applications, the size of d is not fixed. To solve this problem, we will explain later how to make d flexible for the distance under different scenarios. The definition of HABE is similar to ordinary ABE through the definition of overlap between attributes sets, except that in HABE the attributes have hierarchical structure. It is assumed that the universal attributes form hierarchical structure according to the definition of access control system. Note that we call an attribute ω covers ω′ if ω = ω′ or ω belongs to a higher level than ω′.

Definition 1

The HABE scheme consists of four algorithms (Setup, KeyGen, Enc, Dec), which are defined as follows:

• Setup: The setup algorithm takes as input security parameter 1^λ, and generates public parameters $\textsf{para}$ and sk. It retains sk as the secret key for attribute center and outputs $\textsf{para}$.

• KeyGen(U, para, sk): The private key generation algorithm takes as input attribute set $\textsf{U}$, public parameters $\textsf{para}$, and sk. It outputs a private key $d_{\textsf{U}}$.

• Enc(m, $\textsf{U}'$, $\textsf{para}$): The encryption algorithm takes as input a message m, attribute set $\textsf{U}'$, and public parameters $\textsf{para}$. It outputs ciphertext $\mathcal{C}$.

• Dec($\mathcal{C}$, $\textsf{U}'$, $\textsf{para}$, $\textsf{U}$, $d_\textsf{U}$): The decryption algorithm takes as input a ciphertext $\mathcal{C}$ for $\textsf{U}'$, public parameters $\textsf{para}$, and secret key $d_\textsf{U}$ with respect to $\textsf{U}$. It first checks whether the number of attributes in $\textsf{U}$ that cover the attributes from $\textsf{U}'$ is at least d. If it is true, output the plaintext m with $d_\textsf{U}$. Otherwise, output a symbol of $\bot$.

2.2 Security model

Because the HABE can be viewed as a generalization of ordinary ABE, the security requirements for HABE is also indistinguishable against adaptively chosen attributes and chosen ciphertext attacks (IND-Atr-CCA). Description of the security game is the same as ABE, except that the attributes here are hierarchical. The formal definition of IND-Atr-CCA is based on the following game involving an adversary $\mathcal{A}$.

Game IND-Atr-CCA

• Setup(d) The challenger chooses a sufficiently large security parameter 1^λ and runs Setup to get a key pair (pk,sk) and other public parameters para. It retains secret key sk and gives pk, para to $\mathcal{A}$.

• Phase 1$\mathcal{A}$ can perform a polynomially bounded number of queries in an adaptive manner to the oracles, including attribute private key extraction oracle and ciphertext decryption oracle.

• Challenge$\mathcal{A}$ outputs a target attribute set $\textsf{U}^*$ and two messages m₀, m₁ on which it wishes to be challenged. The only restriction is that $\mathcal{A}$ did not previously issue a key query on $\textsf{U}$ such that the number of attributes in $\textsf{U}$ that cover the attributes in $\textsf{U}^*$ is not less than d. The challenger randomly chooses a bit b ∈ {0,1}, computes $\mathcal{C}= \textsf{Enc}(m_b,\textsf{U}^*,\textsf{para})$ and sends $\mathcal{C}$ to $\mathcal{A}$.

• Phase 2$\mathcal{A}$ can perform a polynomially bounded number of queries to the decryption and private key extraction oracles in an adaptive manner. $\mathcal{A}$ is not allowed to issue decryption query on $(\mathcal{C}, \textsf{U})$ or private key query on an attribute set U such that the number of attributes in U that cover the attributes in $\textsf{U}^*$ is not less than d.

• Guess$\mathcal{A}$ outputs a guess bit b′.

$\mathcal{A}$ wins the game if b = b′. The advantage of $\mathcal{A}$ in game IND-Atr-CCA is defined as the probability that $\mathcal{A}$ wins the game minus 1/2.

Definition 2

We say that an HABE scheme is IND-Atr-CCA secure if there is no adversary $\mathcal{A}$ can win the game with non-negligible probability.

In this paper, we also use a weaker notion called indistinguishable against selective attributes and chosen plaintext attacks (IND-sAtr-CPA). The definition is similar to IND-Atr-CCA, except here it requires the adversary to submit its challenge target attribute set $\textsf{U}^*$ before the setup phase. Furthermore, according to the definition of chosen plaintext attack, the decryption oracle is not available to the adversary. Also, the attributes in the challenge ciphertext should be chosen in different hierarchy components. Description of the security game is described based on the following game involving an adversary $\mathcal{A}$.

Game IND-sAtr-CPA

• Initial Phase The adversary $\mathcal{A}$ chooses a challenge attribute set $\textsf{U}^*$ and the threshold d. $\textsf{U}^*$ and d will be sent to the challenger before the setup phase.

• Setup(d) After receiving $\textsf{U}^*$ and d, the challenger chooses a sufficiently large security parameter 1^λ and runs Setup to get a key pair (pk,sk) and other public parameters para. It retains secret key sk and gives pk, para to $\mathcal{A}$.

• Phase 1$\mathcal{A}$ can perform a polynomially bounded number of queries in an adaptive manner attribute private key extraction oracle.

• Challenge$\mathcal{A}$ outputs a target attribute set $\textsf{U}^*$ and two messages m₀, m₁ on which it wishes to be challenged. The only restriction is that $\mathcal{A}$ did not previously issue a key query on $\textsf{U}$ such that the number of attributes in $\textsf{U}$ that cover the attributes in $\textsf{U}^*$ is not less than d. The challenger randomly chooses a bit b ∈ {0,1}, computes $\mathcal{C}= \textsf{Enc}(m_b,\textsf{U}^*,\textsf{para})$ and sends $\mathcal{C}$ to $\mathcal{A}$.

• Phase 2$\mathcal{A}$ can perform a polynomially bounded number of queries to the private key extraction oracle in an adaptive manner. $\mathcal{A}$ is not allowed to issue private key query on an attribute set U such that the number of attributes in U that cover the attributes in $\textsf{U}^*$ is not less than d.

• Guess$\mathcal{A}$ outputs a guess bit b′.

$\mathcal{A}$ wins the game if b = b′. The advantage of $\mathcal{A}$ in game IND-sAtr-CPA is defined as the probability that $\mathcal{A}$ wins the game minus 1/2.

Definition 3

We say that an HABE scheme is IND-sAtr-CPA secure if there is no adversary $\mathcal{A}$ can win the game above with non-negligible probability.

Actually, the selective model has been used in many other papers to get hierarchical identity-based encryption [3]. However, it is still an open problem to construct efficient and fully secure schemes without the selective secure model in hierarchical identity-based encryption.

2.3 HABE scheme with tree hierarchy

In this construction, the attributes are assumed to be divided into n trees with roots ω ₁₀, ⋯, ω _n0. For the tree with root ω _i0, we assume its depth is ℓ _i . Let ω _ik be an attribute of depth k with path (ω _i0, ⋯ , ω _ik ) from root ω _i0. We show how the attributes are categorized and constructed in Fig. 1. In this figure, the attributes with blue nodes are issued to a user. This attribute private key is valid for the ciphertext with respect to attribute with red arrow path which starts from the blue node. It is easy to verify that this construction is indeed a generalization of ABE. When all attributes are independent, i.e., they do not have any relationship for access control, the construction is just an ordinary ABE. Similar to other constructions of ABE, the number d, which will be used as the distance for the decryption, should be chosen and defined in setup algorithm.

Fig. 1

Hierarchical attribute structure

We now give a brief review on the property of pairings and its related hard problems that will be used in this paper. Let G ₁, G ₂ be cyclic groups of prime order p, writing the group action multiplicatively. Let g be a generator of G ₁, and $\hat{e}: G_1\times G_1\rightarrow G_2$ be a map with the following properties:

• 1). Bilinearity: $\hat{e}(g_1^a, g_2^b) = \hat{e}(g_1, g_2)^{ab}$ for all g ₁, g ₂ ∈ G ₁, and a, b ∈  _R Z _p ;

• 2). Non-degeneracy: there exists g ₁, g ₂ ∈ G ₁ such that $\hat{e}(g_1,g_2) \neq 1$, in other words, the map does not send all pairs in G ₁×G ₁ to the identity in G ₂;

• 3). Computability: There is an efficient algorithm to compute $\hat{e}(g_1,g_2)$ for all g ₁,g ₂ ∈ G ₁.

Throughout this paper, we assume that there is a trusted setup algorithm that takes as input a security parameter 1^λ and outputs the setup (p, G ₁, G ₂, g, $\hat{e}$), where group G ₁ = < g > of prime order p has a bilinear map $\hat{e}$, and $\hat{e}(g, g)$ generates G ₂ (which also has order p). We also define the Lagrange coefficient Δ _i,S for i ∈ Z _p and a set S with elements in Z _p :

$$ \Delta_{i,S}=\prod\limits_{\eta\in S,\eta\neq i} \frac{x-\eta}{i-\eta} $$

Setup ${\boldsymbol(d)}$

Let G ₁ be the bilinear group of prime order p and g be a generator of G ₁. Additionally, let $\hat{e}: G_1\times G_1\rightarrow G_2$ be a bilinear map. Assume there are N attributes in universe and n trees are formed based on the relationship of these attributes defined in the access control system. Define a hash function H: {0,1}^*→ $Z_p^*$. Let $\textsf{U}_0=\{\omega_{10}, \cdots, \omega_{n0}\}$ be the root attribute set. Assume the maximum depth of the i-th tree is ℓ _i for 1 ≤ i ≤ n, and ℓ =  max {ℓ₁, ⋯ , ℓ _n }. We can choose α from Z _p and compute $g_1=g^\alpha$. Meanwhile, we choose random elements g ₂, u′₁, ⋯ , u′ _n , u ₁, ⋯, u _ℓ from group G ₁.

The public parameters are $\textsf{para}=(g, g_1, g_2$, $\hat{e}$, (u′ _i )_{1 ≤ i ≤ n} , (u _i )_{1 ≤ i ≤ ℓ}). The master key is α.

KeyGen

To generate a private key for attribute set $\textsf{U}$, it proceeds as follows:

• A d − 1 degree polynomial q is randomly chosen such that q(0) = α;

• For each $\omega\in \textsf{U}$, assume its depth is k in the i-th tree with path (ω _i0, ω _i1, ⋯, ω _{i,k − 1}, ω). It chooses r ∈  _R Z _p and computes D _ω  = (d _i0, d _i , $d_{i,k_i+1}$, $\cdots, d_{i\ell_i}$), where $d_{i0}=g_2^{q(H(\omega))}(u'_i\Pi_{j=1}^{k}u_{j}^{\omega_{ij}})^{r}$, $d_i=g^{r}$, $d_{i,k+1}=u_{k+1}^{r}$, ⋯, $d_{i\ell_i}=u_{\ell_i}^{r}$;

• Finally, it outputs the private key of $\textsf{U}$ as

  $$ d_{\textsf{U}}=\{D_{\omega}\}_{\omega\in \textsf{U}} $$

Enc

To encrypt a message m ∈ G ₂ to an attribute set $\textsf{U}'$, it proceeds as follows. First, a random value s ∈ Z _p is chosen. For each $\omega'\in \textsf{U}'$, assume its depth is k′ in the j-th tree. Let the path for ω′ be (ω _j0, ω _j1′, ⋯, ω _{j,k′ − 1}′, ω′). It computes $\textsl{E}'=m\hat{e}(g_1,g_2)^s$ and $\textsl{T}=g^s$. Furthermore, it computes $\textsl{E}_{\omega'}=(u'_{j}\prod_{\delta=1}^{k'}u_{\delta}^{\omega'_{j\delta}})^s$ for each $\omega'\in \textsf{U}'$ and outputs the ciphertext as

$$ \mathcal{C}=(\textsl{E}', \textsl{T}, \{\textsl{E}_{\omega'}\}) $$

for all $\omega'\in \textsf{U}'$.

Dec

Suppose that a ciphertext $\textsl{E}$ is encrypted to the attribute set $\textsf{U}'$. Assume one has a private key $d_{\textsf{U}}=\{D_{\omega}\}_{\omega\in \textsf{U}}$ for attribute set $\textsf{U}$ such that the number of attributes in $\textsf{U}$ that cover the attributes in $\textsf{U}'$ is no less than d. Then, it chooses an arbitrary d-element subset S with elements in $\textsf{U}$. For each ω in S with path (ω _i0, ω _i1, ⋯ , ω _{i,k − 1}, ω), assume ω′ is the attribute in $\textsf{U}'$ covered by ω with path from the same root ω _i0 as (ω _i0, ω _i1′, ⋯, ω _{i,k′ − 1}′, ω′) (It implies the depth for ω′ is k′ in the j-th tree). Then, we have ω _iδ  = ω′ _iδ for 1 ≤ δ ≤ k. Finally, it computes $d_{i0}'=d_{i0}d_{i,k+1}^{\omega'_{i,k+1}}\cdots d_{ik'}^{\omega'_{ik'}}$ and decrypts the ciphertext as

$$ m=\textsl{E}'/ \prod\limits_{\omega\in S}(\frac{\hat{e}(d'_{i0},T)}{\hat{e}(d_i,E_{\omega'})})^{\bigtriangleup_{H(\omega),S}(0)} $$

2.4 Security result

Before giving the security result, we introduce the Decisional ℓ-wBDHI* Assumption used in [1].

Decisional ℓ-wBDHI* problem

The Decisional ℓ-wBDHI* Problem is that, given g, $y_1 = g^{x}$, ⋯ , $y_{\ell}=g^{x^{\ell}}$ ∈ G ₁ for unknown random $x \in Z_p^*$ and T ∈ G ₂, to decide if $T=\hat{e}(g, g)^{x^{\ell+1}}$.

We say that a polynomial-time adversary $\mathcal{A}$ has advantage ε in solving the Decisional ℓ-wBDHI* Problem in groups (G ₁,G ₂) if $\mid Pr[ \mathcal{A}(g$, $y_1 = g^{x}$, ⋯ , $y_{\ell}=g^{x^{\ell}}$, $\hat{e}(g, g)^{x^{\ell+1}})= 1]$- Pr $[\mathcal{A}(g$, $y_1 = g^{x}$, ⋯ , $y_{\ell}=g^{x^{\ell}}$, $\hat{e}(g, g)^z) = 1]\mid$ ≥ 2ε, where the probability is taken over the randomly chosen x, z and the random bits consumed by $\mathcal{A}$.

Decisional ℓ-wBDHI* assumption

We say that the (t, ε)-ℓ-wBDHI* assumption holds in (G ₁,G ₂) if no t-time algorithm has the probability at least ε in solving the ℓ-wBDHI* problem for non-negligible ε.

Theorem 1

Under the ℓ-wBDHI* assumption, the HABE scheme is indistinguishable secure against selective attribute chosen plaintext attack.

Proof

See Appendix □

2.5 HABE scheme with flexible threshold d

Similar to [20], we have two methods to obtain flexible d. First, we can create multiple systems with different values of d. Then, each user will be issued all the attribute private keys with k ≤ d. One can encrypt message by choosing the appropriate value d.

In the second method, the attribute authority will reserve some root attributes, that is, dummy attributes, which will be issued to everyone. The party encrypting the message can decrease d by increasing the number of these dummy attributes included in the ciphertext. We show the construction as follows:

Setup ${\boldsymbol(d)}$

The algorithm of Setup is similar to the scheme in Section 2.3. The difference is that, in this scheme, a d − 1 default set V of attributes from Z _p , Ω = {Ω ₁,Ω ₂, ⋯, Ω _d − 1}, is given additionally. Meanwhile, we also choose random elements v ₀,v′₁, ⋯ , v′_d − 1 from group G ₁.

The public parameters are $\textsf{para}=(g, g_1, g_2$, $\hat{e}$, v′₁, ⋯ , v′_d − 1, (u′ _i )_{1 ≤ i ≤ n} , (u _i )_{1 ≤ i ≤ ℓ}). The master key is α.

KeyGen

To generate a private key for attribute set $\textsf{U}$, it proceeds as follows:

• A d − 1 degree polynomial q is randomly chosen such that q(0) = α;

• For each ω ∈ V, compute D _ω  = (d _i0, d _i ), where $d_{i0}=g_2^{q(H(\omega))}(v_0v'_i)^{r}$, $d_i=g^{r}$;

• For each $\omega\in \textsf{U}$, assume its depth is k in the i-th tree with path (ω _i0, ω _i1, ⋯, ω _{i,k − 1}, ω). It chooses r ∈  _R Z _p and computes D _ω  = (d _i0, d _i , $d_{i,k_i+1}$, $\cdots, d_{i\ell_i}$), where $d_{i0}=g_2^{q(H(\omega))}(u'_i\Pi_{j=1}^{k}u_{j}^{\omega_{ij}})^{r}$, $d_i=g^{r}$, $d_{i,k+1}=u_{k+1}^{r}$, ⋯, $d_{i\ell_i}=u_{\ell_i}^{r}$;

• Finally, it outputs the private key of $\textsf{U}$ as

  $$ d_{U}=\{D_{\omega}\}_{\omega\in U\cup V} $$

Enc

To encrypt a message m ∈ G ₂ to an attribute set $\textsf{U}'$ with threshold d′ satisfying d′ ≤ d, it proceeds as follows. First, a random value s ∈ Z _p and d − d′ default attribute set V′ from V are chosen.

• For each ω′ ∈ V′, it computes $(v_0v'_i)^s$;

• For each $\omega'\in \textsf{U}'$, assume its depth is k′ in the j-th tree. Let the path for ω′ be (ω _j0, ω _j1′, ⋯, ω _{j,k′ − 1}′, ω′). It computes $\textsl{E}'=m\hat{e}(g_1,g_2)^s$, $\textsl{T}=g^s$, and $\textsl{E}_{\omega'}=(u'_{j}\prod_{\delta=1}^{k'}u_{\delta}^{\omega'_{j\delta}})^s$;

• Finally, it outputs the ciphertext as

  $$ \mathcal{C}=(\textsl{E}', \textsl{T}, \{\textsl{E}_{\omega'}\}) $$

  for all $\omega'\in \textsf{U}'\cup V'$.

The decryption algorithm is similar to the construction in Section 2.3. The user can decrypt and get the message if the number of intersection of his attributes, including the default attributes, is not less than d.

2.6 HABE scheme with multiple authorities

The deployment implications of the HABE may not be entirely realistic because it relies on the existence of a single trusted party who monitors all attributes and issues all decryption keys. Instead, we often have different entities responsible for monitoring different attributes of a user. To reduce the trust of attribute authorities, Chase [6] proposed a multi-authority ABE scheme which supports many different authorities operating simultaneously, each handing out secret keys for a different set of attributes. To prevent collusion in such a setting, each user is required to have a unique global identifier (GID), which they must present to each authority. To extend our HABE scheme to multi-authority one, the technique of [6] can be applied in our scheme. More specifically, each user will have a global identifier and each attribute authority will issue an attribute private key based on this same identifier. The encryption and decryption proceed in a similar way as our HABE scheme, thus, they are omitted here.

2.7 The IND-Atr-CPA secure HABE scheme

In order to get IND-Atr-CPA HABE from IND-sAtr-CPA, the direct technique is to use random oracle model. However, this will give security reduction loose $(q_H)^n$.

In order to avoid the usage of random oracle model, we can use the technique of [23], i.e., replace each element u _i in setup algorithm by $u^1_{i}, \cdots, u^m_{i}$. Meanwhile, for any m-bit attribute ω = (ω ₁, ⋯ , ω _m )∈ {0,1}^m, $u_{i}^{\omega}$ is replaced by $\prod_{k=1}^m(u^k_{i})^{\omega_k}$. The revised structural attribute based encryption could be proved to be secure without random oracles. This secure construction loses a factor exponential in ℓ in the reduction to the underlying assumption. This limits the secure use of our schemes to very small hierarchy depths. This restriction is not so surprising because that HABE schemes are in fact a generalization of HIBE schemes, and that the same restriction arises in all currently-known HIBE constructions . It is still an open problem.

2.8 How to get CCA-secure HABE scheme

The most efficient transformation from IND-sAtr-CPA to IND-sAtr-CCA is to use the Fujisaki–Okamoto technique [8], which adds only a little computation on the original HABE scheme. So, the resulted IND-sAtr-CCA HABE construction is very efficient. However, it can only be proved to be secure in the random oracle model.

In order to achieve IND-sAtr-CCA security in the standard model, we can use the technique of simulation-sound NIZK proofs [21]. However, it is not efficient because of NIZK proofs. Another efficient technique we can use is the idea from [4], which showed how a CCA-secure encryption scheme can be built from weakly-secure (IND-sID-CPA) ID-based encryption scheme. The idea of our construction is similar from using a ℓ + 1-level CPA-secure HIBE to construct ℓ-level CCA-secure HIBE. In fact, HABE shares a lot of similarities with HIBE. Entities of both HABE and HIBE are hierarchical. For this technique, it requires a message authentication code and an encapsulation scheme. For details, please refer to [4].

3 Implementation and efficiency analysis

In the HABE with tree hierarchy, the attributes are first classified according to the relationships defined in the access control system. Assume there are n trees formed by part of universal attributes, and the remaining attributes are independent as the ordinary ABE. Actually, the independent attributes can be also viewed as trees with only roots, which is a special case from our HABE construction. Each attribute belongs to only one different tree. In HABE, the private key of higher level attributes can be utilized to decrypt the ciphertext for lower attributes. Similar to other ordinary ABE schemes, the encryptor defines the attributes set included in the ciphertext. The users are issued private keys of some attributes by the attribute center. If the user has several attributes belonging to the same path, then, only the highest level attribute will be issued. This is because in this access control system, the highest level attribute will cover all of its decedents in decryption. In ciphertext, the case is opposite. If there are several attributes belonging to the same path, only the lowest attribute will be included to create the ciphertext. This is because if one user has a private key for a higher level attribute, he or she can definitely decrypt the ciphertext for the lower level attributes. From the private key issuing, we can also understand the rule of this ciphertext generation. In decryption algorithm, only users with at least d of attributes that cover the attributes in ciphertext can decrypt the ciphertext. In our construction, the ciphertext consists of only 2 + k group elements, where k is the size of user’s attributes. If we directly apply the ABE here to realize the attribute hierarchical structure, $2+k+\Sigma_{i=1}^k N_i$ group elements will be required in the ciphertext, where N _i is the number of the i-th target attribute’s ancestors. There is also another way to reduce the ciphertext size by just issuing keys with all decedents of the user’s attributes. However, the attribute private key size will be 2(k + N _i ′), where N _i ′ is the number of the i-th target decedents.

4 Conclusion and future work

ABE has been applied extensively to the area of access control. However, the application of ABE is limited due to its high scheme overhead as extensive pairing operations are usually required.

In this paper, we focus on improving the efficiency of ABE by leveraging a previously overlooked fact, i.e., the often-found hierarchical relationships among the attributes that are inherent to many access control scenarios. As the first research effort along this direction, we coin the notion of hierarchical ABE (HABE), which can be viewed as the generalization of traditional ABE in the sense that both definitions are equal when all attributes are independent. We further give a concrete HABE construction considering a tree hierarchy among the attributes, which is provably secure. More importantly, our construction can exhibit significant improvement over the traditional ABE when attribute hierarchies exist.

This paper is the first work to address how to improve ABE by considering the relationships among the attributes. There are still several interesting open problems in this topic: 1) How can we construct more efficient schemes with attribute tree hierarchical structure? 2) How can we improve ABE by designing constructions dealing with more general relationships among the attributes in universe? In this paper, we consider the most common attributes structure, i.e., tree structure. Other attributes structure, such as partial-order tree, can also be utilized in some scenarios. Therefore, how to design ABE for more general attributes structure is our future work.

Appendix: Proof of Theorem 1

Proof

Assume that an attacker $\mathcal{A}$ breaks IND-sAtr-CPA with probability greater than ε within time t by making q _d private key extraction queries. Assume the attributes in universe form n trees. Denote depth of the i-th tree as ℓ _i for 1 ≤ i ≤ n, and let ℓ =  max {ℓ₁, ⋯ , ℓ _n }. We show that using $\mathcal{A}$, one can construct a ℓ-wBDHI* attacker $\mathcal{A}'$. Let g be a generator of G ₁ and $y_i = g^{x^i}$. Suppose that $\mathcal{A}'$ is given $(g, \hat{e}, G_1, G_2$, h, y ₁, ⋯, y _ℓ, T), where T is either $\hat{e}(g, g)^{x^{\ell+1}}$ or $\hat{e}(g, g)^\gamma$ for random γ ∈ Z _p , as an instance of the ℓ-wBDHI* problem. By ε′ and t′, we denote winning probability and running time of $\mathcal{A}'$, respectively. $\mathcal{A}$ is first given the attributes relationship trees for the access control system in advance. Then, algorithm $\mathcal{A}'$ works by interacting with $\mathcal{A}$ in a selective identity game as follows:

Suppose that $\mathcal{A}$ outputs challenge attributes $\textsf{U}^*$. Let $\mid\textsf{U}^*\mid=\upsilon$ and $\textsf{U}^*=(\omega^*_{i_1}$, ⋯, $\omega^*_{i_{\upsilon}}$) with the depth k ₁, ⋯, k _υ , respectively. The path for ω ^* is defined as $(\omega^*_{i0}, \cdots$, $\omega^*_{i,k_i-1}$, ω ^*) with depth k _i from the root $\omega^*_{i0}$ in the i-th tree. Upon receiving the challenge attributes, $\mathcal{A}'$ sets g ₁ = y ₁, g ₂ = y _ℓ, and u _i  = y _{ℓ − i + 1} for 1 ≤ i ≤ ℓ.

For any $i \not \in \{i_1, \cdots, i_{\upsilon}\}$, it chooses a _i from $Z_p^*$ and set $u_{i}'=g^{a_i}$.

For i ∈ {i ₁, ⋯ , i _υ }, let $u_i'=g^{a_i}/\Pi_{\delta=1}^{k_i}y^{\omega_{i\delta}^*}_{{\ell-i+1}}$.

para=(g, e, G₁, G₂, g₁, g₂, d, ($u_i')_{_{1 \leq i\leq n}}$, (u _i )_{1 ≤ i ≤ ℓ}) is given to $\mathcal{A}$.

$\mathcal{A}'$ answers $\mathcal{A}$’s attributes private key extraction queries as follows. Upon receiving a private key extraction query on $\textsf{U}$, it constructs an attributes subset Γ from $\textsf{U}$ such that the attributes in Γ cover attributes in $\textsf{U}^*$. We also define Γ′ such that $\Gamma \subseteq \Gamma'\subseteq \textsf{U}$ and |Γ′|=d − 1. Let S = Γ′ ∪ {0}. For each ω ∈ Γ′, a random value μ is chosen and let q(H(ω)) = μ.

Then, the d − 1 degree polynomial function q(z) could be determined from these d − 1 value together with q(0) = x. By using interpolation, for $\omega \not \in S$, q(H(ω)) = Σ _{ω ∈ Γ′} Δ _ω,S(H(ω)) q(H(ω)) + Δ _0,S (H(ω))q(0). So, the simulator can calculate the private key for ω ∈ S as D _ω  = (d _i0, d _i , $d_{i,k_i+1}$, ⋯ , $d_{i\ell_i}$), where $d_{i0}\!=\!g_2^{q(H(\omega))}$ $(u'_i\Pi_{j=1}^{k_i}u_{j}^{\omega_{ij}})^{r}$, $d_i\!=\!g^{r}$, $d_{i,k_i+1}=$ $u_{k_i+1}^{r}, \cdots, d_{i\ell_i}=u_{\ell_i}^{r}$ by choosing randomly $r\in Z_p^*$. Thus, the simulator can calculate the private key D _ω for $\omega \not \in S$ as follows:

For $(\omega_{j0}, \omega_{j1}, \cdots, \omega_{jt_j})$, if j ∈ {i ₁, ⋯, i _ℓ}, there is at least one 1 ≤ γ ≤ t _j , such that $\omega_{j\gamma}\neq \omega^*_{j\gamma}$. It chooses $r_j=\frac{ -\Delta_{0,S}(j\,)x}{a_j}+r'_j$ and outputs the simulated private key as $(g_2^{\Sigma_{i\in \Gamma'} \Delta_{i,S}(j\,) q(j\,)+\frac{-\Delta_{0,S}(j\,)b_{j\gamma}\omega^*_{j\gamma} \omega_{j\gamma}}{\omega^*_{j\gamma}-\omega_{j\gamma}}}$ $g_1^{(1-\frac{\omega_{j\gamma}}{\omega^*_{j\gamma}})r'_{j}}$ $g^{b_{j\gamma}\omega_{j\gamma}r_{j}}$ $\prod_{k\neq \gamma,k=1}^{k_j} (g_1u_{jk})^{r'_{j}}$, $g_2^{\frac{-\Delta_{0,S}(j\,)\omega^*_{j\gamma}}{\omega^*_{j\gamma}-\omega_{j\gamma}}}g^{r'_{j}}$, $u_{k_j+1}^{r}$, ⋯, $u_{\ell_j}^{r})$.

If $j \not \in \{i_1, \cdots, i_\ell\}$, then let $r_j=\frac{ -\Delta_{0,S}(j\,)x}{a_j}+r_j'$. Finally, it outputs the simulated private key as $(g_2^{\Sigma_{j\in \Gamma'} \Delta_{j,S}(i) q(j\,)}$ $g_2^{\frac{-\Delta_{0,S}(j\,)}{a_j}}u_j^{r_j'}$ $\prod_{\delta=1}^{k_j} (g_1u_{j\delta})^{r_{j\delta}}$, $g_2^{\frac{-\Delta_{0,S}(j\,)}{a_j}}$ $g^{r_j'}$, $u_{k_j+1}^{r}$, ⋯, $u_{\ell_j}^{r})$.

After these interactions, $\mathcal{A}$ outputs two messages m ₀, m ₁ and $\textsf{U}^*$. $\mathcal{A}'$ picks a random bit b ∈ {0,1} and responds with the ciphertext as $\mathcal{C}=(Tm_b, y_1, \{y_1^{a_{j}}\}_{1\leq j \leq v})$. The ciphertext is simulated correctly if $T=e(g,g)^{x^{\ell+1}}$ because let s = x, the ciphertext could be written as $\mathcal{C}=(m\hat{e}(g_1,g_2)^s$, g ^s, $\{(u'_{j}\prod_{\delta=1}^{k_{\delta}}u_{\delta}^{\omega^*_{j}})^s\})$ for each $\omega\in \textsf{U}$. $\mathcal{A}$ issues more private key queries $\textsf{U}$, restriction is that $\textsf{U}$ is not covered by $\textsf{U}^*$. $\mathcal{A}'$ responds as before.

This completes the description of algorithm $\mathcal{A}'$. Finally, $\mathcal{A}$ outputs guess b′ with advantage ε′. If $\mathcal{A}'$ does not abort, then, $\mathcal{A}'$ outputs b′ as the result to the ℓ-wBDHI* problem. Since $\mathcal{A}$ has an advantage ε in attacking the scheme, from the simulation, we can infer that $\mathcal{A}'$ can solve the ℓ-wBDHI* problem with advantage ε′ ≈ ε. □