A New Technique for Compacting Secret Key in Attribute-Based Broadcast Encryption

Abstract

Public-key encryption has been generalized to adapt to more and more practical applications. Broadcast encryption, introduced by Fiat and Naor in 1993, aims for applications in pay-TV or satellite transmission and allows a sender to securely send private messages to any subset of users, the target set. Sahai and Waters introduced Attribute-based Encryption (ABE) to define the target set in a more structural way via access policies on attributes. Attribute-based Broadcast Encryption (ABBE) combines the functionalities of both in an efficient way. In the relevant applications such as pay-TV, the users are given a relatively small device with very limited secure memory in a smartcard. Therefore, it is of high interest to construct schemes with compact secret key of users. Even though extensively studied in the recent years, it is still an open question of constructing an efficient ABBE with constant-size private keys for general forms of access policy such as CNF or DNF forms. This question was partially solved at ESORICS ’15 where Phuong et al. introduced a constant secret-key size ABBE. But they manage restrictive access policies only supporting AND-gates and wildcards. In this paper, we solve this open question and propose an efficient constant-size private key ciphertext-policy attribute-based broadcast encryption scheme for DNF form. In particular, we also present the optimization in implementing our proposed scheme.

1 Introduction

We are actually in a very active period of development of cryptography. Modern technologies, namely cloud computing and big data, require the design of advanced cryptographic schemes supporting new functionalities. In many applications that involve a large set of users, one needs to have stronger and more flexible capabilities to encrypt data than the traditional public key encryption: the encryption should take into account specific policies in such a way that only receivers with suitable rights can decrypt the encrypted messages.

Attribute-Based Encryption. Sahai and Waters [14] introduced the concept of attribute-based encryption ($\mathsf {ABE}$) in which the encryption and decryption can be based on the user’s attributes. Since then, there are a lot of development in this area with many interesting results [7, 11, 13, 14, 16], to name a few. Actually, there are two categories of $\mathsf {ABE}$: ciphertext-policy attribute-based encryption ($\mathsf {CP}$-$\mathsf {ABE}$) and key-policy attribute-based encryption ($\mathsf {KP}$-$\mathsf {ABE}$). In a $\mathsf {CP}$-$\mathsf {ABE}$ scheme, the secret key is associated with a set of attributes and the ciphertext is associated with an access policy (structure) over the universe of attributes: a user can then decrypt a given ciphertext if the set of attributes related to his/her secret key satisfies the access policy underlying the ciphertext. In contrast, in a $\mathsf {KP}$-$\mathsf {ABE}$ scheme, each secret key corresponds to an access policy and a set of attributes is associated with the ciphertext. Concerning the access structure, fine-grained access control is the most desired and also well formalized as boolean formula in disjunctive normal form (DNF) or in conjunctive normal form (CNF).

Attribute-Based Broadcast Encryption. In some practical cases, one may want to remove the right to decrypt to some specific users. The notion of attribute-based broadcast encryption ($\mathsf {ABBE}$) has then been introduced in [10] to address the problem of user revocation. More precisely, in such a system, the broadcaster is capable of revoking any receiver and the collusion of revoked users cannot decrypt any ciphertext even if they possess sufficient attributes to satisfy the access policy. In traditional attribute-based encryption schemes, the revocation can be performed based on attributes (resp., negative attributes as some non-monotonic schemes [11, 16]), by adding the AND of a clause containing the attributes corresponding to non-revoked users (resp., negative attributes corresponding to revoked users). However, this will give an inefficient solution as the ciphertext grows linearly to the number of non–revoked users (resp., revoked users), which is large. An attribute-based broadcast encryption (ABBE) scheme should allow individual receivers to be directly revoked in an efficient way.

Several $\mathsf {ABBE}$ schemes have been proposed in [3, 7–10]. As in a broadcast encryption, it is of great importance to construct a scheme with compact secret key. Such a scheme can have practical applications such as in pay-TV or satellite transmission where the user’s device are relatively small and the secure memory is often implemented in a smartcard. While broadcast encryption with constant-size secret key has been solved by Boneh, Gentry and Waters in [2], the extension of BGW technique to $\mathsf {ABBE}$ setting make the secret key longer, due to the obligation of combining different attributes in the decryption, as shown in [7]. The problem of designing constant-size private key $\mathsf {ABBE}$ schemes supporting fine-grained access control was partially solved in ESORICS ’15 [12]. But the problem is still open since the proposed non-monotonic scheme only manages restrictive access policies supporting AND-gates and wildcards: they do not treat the case of CNF or DNF forms. More precisely, if the access policy is $A_1\wedge * \wedge A_2$, where $*$ is a wildcard, then any user whose attribute set contains exactly three attributes (no more no less) and two of them are $A_1, A_2$ can decrypt the ciphertext. This obliviously can reduce the ciphertext size, however in exchange, the secret key size now is $3+2(N_1+1)$ elements, where $N_1$ is the maximal number of wildcards can appear in an access policy, $N_1$ is fixed at the setup phase.

Our Contributions. Even though extensively studied in the recent years, it is still an open question of constructing an efficient $\mathsf {ABBE}$ with constant-size private keys for general forms of access policy such as CNF or DNF. We here solve this open question for the DNF form by providing several new techniques in this field.

Our initial new idea is to extend the Delerablée’s technique (for constructing an $\mathsf {IBBE}$ scheme [5]) to our context of $\mathsf {CP}$-$\mathsf {ABBE}$. More precisely, each attribute in our $\mathsf {ABBE}$ corresponds to an identity in Delerablée’s $\mathsf {IBBE}$ scheme. To obtain the “broadcast” property, we also add an additional identity for each user. The resulting scheme then contains two kinds of “$\mathsf {IBBE}$ identities”: one user’s identity and the additional identities that represent the attributes the user possesses. We then succeed in combining all these information into a compact secret key. More intuition behind our construction as well as the security proof of our scheme will be given further in the paper.

We give in Table 1 a detailed comparison among our scheme and several other $\mathsf {CP}$-$\mathsf {ABE}$ and $\mathsf {CP}$-$\mathsf {ABBE}$ schemes supporting fine-grained access control. It shows that, regarding the efficiency, our $\mathsf {CP}$-$\mathsf {ABBE}$ scheme enjoys the following properties:

• it is the first efficient $\mathsf {CP}$-$\mathsf {ABBE}$ scheme which simultaneously achieves constant-size private key and supports fine-grained access control;

• regarding the decryption, a user in our scheme only needs to compute two parings, in contrast to almost existing $\mathsf {CP}$-$\mathsf {ABE}$ and $\mathsf {CP}$-$\mathsf {ABBE}$ schemes supporting fine-grained access control where each user needs to perform at least |I| pairings computations in the decryption, where |I| is the number of attributes needed to satisfy a ciphertext policy. Moreover, as we will see, one of the two pairing can be delegated to a third party.

We show at the full version of the paper that our scheme can be truly implemented in a prototype for a smartphone based cloud storage use case. In particular, we show how to alleviate some parts of our scheme so as to obtain a very practical system, and we give some concrete benchmarks.

Table 1. n is the maximal number of users, N is the maximal number of attributes, m is the number of clauses in a CNF/DNF access policy, (in some systems from linear secret sharing matrix framework, $\ell$ denotes the number of rows of the LSSS matrix (the number of attributes in an access formula, counting the reused attributes), $\ell ^*$ denotes the maximal of $\ell$ which is equal to the size of the attribute universe, $|S_u|$ denotes the number of attributes of a private key, |I| is the number of attributes of a private key to satisfy a ciphertext policy, |p| denotes element in $\mathbb {Z}_p$, P denotes pairing computation, $\textsf {ex}$ denotes the exponentiation, $\textsf {mex}[v]$ the multi-exponentiation with v terms, $\textsf {mul}$ denotes the multiplication, $k_{max}$ denotes the maximal number of times where one attribute can be reused in an access formula. Note that [8, 9] support fully collusion-resistant blackbox traceability

Organization of the Paper. The paper is now organized as follows. The next section presents the security definitions and the assumptions we need to prove the security. In Sect. 3, we present our new construction. Section 4 is devoted to the security proof of the scheme. Finally, in Sect. 5, we talk about our real implementation.

2 Preliminaries

We give here our main scenario, several preliminaries regarding definition and security model for a $\mathsf {CP}$-$\mathsf {ABBE}$ scheme and the security assumptions we will need.

2.1 Practical Scenario

All along the paper, we will consider the following scenario. A company wishes to put in place a $\mathsf {CP}$-$\mathsf {ABBE}$ scheme for its staff, so that they can store and share sensitive documents, using a non-trusted cloud platform for storage (such as e.g., Dropbox or GoogleDrive). More precisely, we consider three kinds of attributes in the studied system.

• The role of the user in the company: boss, manager, developer, expert.

• The team in which the user is: team $_1$, $\cdots$, team $_k$.

• The project on which the user can work: project $_1$, $\cdots$, project $_\ell$.

Based on that attributes, and a unique specific identity, anyone can encrypt and upload documents, using the $\mathsf {CP}$-$\mathsf {ABBE}$ scheme and a chosen DNF access control policy of the form

$$\begin{aligned} \beta = \textsf {boss} \vee (\textsf {manager}\wedge \textsf {team}_4) \vee (\textsf {developer}\wedge \textsf {project}_5) \vee (\textsf {expert}\wedge \textsf {project}_2). \end{aligned}$$

Finally, anyone with the correct attributes will be able to obtain the document in clear.

2.2 Ciphertext-Policy Attribute-Based Broadcast Encryption

In this paper, we will consider the similar definition and security model for a $\mathsf {CP}$-$\mathsf {ABBE}$ scheme as in [7]. Formally, a $\mathsf {CP}$-$\mathsf {ABBE}$ scheme consists of three probabilistic algorithms as follows.

 

Setup $(1^\lambda , n, \{S_{u}\}_{u\in [n]})$ : :

Takes as input the security parameter $\lambda$, the maximal number of users n, and the attribute repartition $S_{u}$ (the user’s attribute set) for each user u. It returns the public parameters $\mathsf {param}$ of the system, and n private keys $sk_{u}$ which will be distributed to each respective user. The set $\mathcal {K}$ corresponds to the key space for session keys.

Encrypt $(\mathsf {param}, \mathbb {A}, S)$ : :

Takes as input an access policy $\mathbb {A}$, the target set S, and public parameter $\mathsf {param}$. It outputs the session key $K\in \mathcal {K}$, and the header $\mathsf {Hdr}$ which includes the access policy $\mathbb {A}$ and the target set S.

Decrypt $(sk_{u},\mathsf {Hdr},\mathsf {param})$ : :

Takes as input the header $\mathsf {Hdr}$, the private key $sk_{u}$ of a user u, together with the parameters $\mathsf {param}$. It outputs the session key K if and only if $S_{u}$ satisfies $\mathbb {A}$ and $u\in S$. Otherwise, it outputs $\perp$.

 

Security Model. This security model is called semantic security with full static collusions. In fact, a $\mathsf {CP}$-$\mathsf {ABBE}$ scheme is said to be secure in this model if given a challenge header and all private keys of revoked users to an adversary. It is impossible for the adversary to infer any information about the session key. Formally, we now recall the security model for a $\mathsf {CP}$-$\mathsf {ABBE}$ scheme by the following probabilistic game between an attacker $\mathcal {A}$ and a challenger $\mathcal {C}$.

• 1. The challenger $\mathcal {C}$ and the adversary $\mathcal {A}$ are given a system consisting of N attributes.

• 2. $\mathcal {A}$ outputs a target access policy $\mathbb {A}$, target set S as well as a repartition $\{S_{u}\}_{u\in [n]}$ which he intends to attack.

• 3. $\mathcal {C}$ runs the algorithm $\mathbf {Setup}(1^\lambda , n, \{S_{u}\}_{u\in [n]})$ and gives to $\mathcal {A}$ the public parameters $\mathsf {param}$ and the private keys $sk_{u}$ corresponding to the users u that $\mathcal {A}$ may control, i.e., $S_{u}$ doesn’t satisfy $\mathbb {A}$ or $S_{u}$ satisfies $\mathbb {A}$ but $u\notin S$.

• 4. $\mathcal {C}$ runs the algorithm $\mathbf {Encrypt}(\mathsf {param}, \mathbb {A}, S)$ and obtains a header $\mathsf {Hdr}$ and a session key $K\in \mathcal {K}$. Next, $\mathcal {C}$ draws a bit b uniformly at random, sets $K' = K$ if bit $b=0$, $K' \mathop {\leftarrow }\limits ^{\$}\mathcal {K}$ if bit $b=1$ and finally gives $(K', \mathsf {Hdr})$ to $\mathcal {A}$.

• 5. The adversary $\mathcal {A}$ outputs a guess bit $b'$.

As usual, $\mathcal {A}$ wins the game if $b = b'$, and its advantage is defined as

$$\begin{aligned} Adv^{ind}(\lambda , n, \{S_{u}\}_{u\in [n]}, \mathcal {A}) = |2Pr[b=b']-1| \end{aligned}$$

where the probability is taken over the random bit b and all the bits used in the simulation of the algorithms $\mathbf {Setup}(.)$, and $\mathbf {Encrypt}(.)$. The semantic security against full static collusions is defined as follows.

Definition 1

A $\mathsf {CP}$-$\mathsf {ABBE}$ scheme is semantically secure against full static collusions if for all randomized polynomial-time adversaries $\mathcal {A}$ and for all access policies involving at most N attributes defined by $\{S_{u}\}_{\in [n]}$,

$$\begin{aligned} Adv^{ind}(1^\lambda , n, \{S_{u}\}_{u\in [n]}, \mathcal {A}) \end{aligned}$$

is a negligible function of $\lambda$ when N, n are at most polynomial in $\lambda$.

2.3 Access Structures

Definition 2 (Access Structures)

Let $\{P_1$, $P_2$, $\dots$, $P_n\}$ be a set of parties. A collection $\mathbb {A}\subseteq 2^{\{P_1,P_2,\dots ,P_n\}}$ is monotone if $\forall B, C:$ if $B\in \mathbb {A}$ and $B \subseteq C$ then $C\in \mathbb {A}$. An access structure (respectively, monotone access structure) is a collection (respectively, monotone collection) $\mathbb {A}$ of non-empty subsets of $\{P_1,P_2,\dots ,P_n\}$, $i.e, \mathbb {A} \subseteq 2^{\{P_1,P_2,\dots ,P_n\}}\setminus \{\emptyset \}$. The sets in $\mathbb {A}$ are called the authorized sets, and the sets not in $\mathbb {A}$ are called the unauthorized sets.

In this paper, we consider the monotone access structures. However, as shown in [15], it is also possible to extend such case to the general access structures, at the cost of a doubled number of attributes in the system.

2.4 Bilinear Maps and $(P,Q,f)-\mathsf {GDDHE}$ Assumptions

Let $\mathbb {G}$, $\widetilde{\mathbb {G}}$ and $\mathbb {G}_T$ denote three finite multiplicative abelian groups of large prime order $p>2^\lambda$ where $\lambda$ is the security parameter. Let g be a generator of $\mathbb {G}$ and $\tilde{g}$ be a generator of $\widetilde{\mathbb {G}}$. We assume that there exists an admissible asymmetric bilinear map $e:\mathbb {G}\times \widetilde{\mathbb {G}}\rightarrow \mathbb {G}_T$, meaning that for all $a,b\in \mathbb {Z}_{p}$, (i) $e(g^a,\tilde{g}^b)=e(g,\tilde{g})^{ab}$, (ii) $e(g^a,\tilde{g}^b)=1$ iff $a=0$ or $b=0$, and (iii) $e(g^a,\tilde{g}^b)$ is efficiently computable. In the sequel, the set $(p,\mathbb {G},\widetilde{\mathbb {G}},\mathbb {G}_T,e)$ is called a bilinear map group system.

Let $(p,\mathbb {G},\widetilde{\mathbb {G}},\mathbb {G}_T,e)$ be a bilinear map group system and $g \in \mathbb {G}$ (resp. $\tilde{g} \in \widetilde{\mathbb {G}}$) be a generator of $\mathbb {G}$ (resp. $\widetilde{\mathbb {G}}$). We set $g_T = e(g,\tilde{g}) \in \mathbb {G}_T$. Let s, n be positive integers and $P, Q, R \in \mathbb {F}_{p}[X_1, \dots , X_n]^s$ be three s-tuples of n-variate polynomials over $\mathbb {F}_{p}$. Thus, P, Q and R are just three lists containing s multivariate polynomials each. We write $P = (p_1, p_2, \dots , p_s)$, $Q = (q_1, q_2, \dots , q_s)$, $R = (r_1, r_2, \dots , r_s)$ and impose that $p_1 = q_1 = r_1 = 1$. For any function $h:\mathbb {F}_{p} \rightarrow \varOmega$ and any vector $(x_1, \dots , x_n)\in \mathbb {F}_{p}^{n}$, $h(P(x_1, \dots , x_n))$ stands for $\big (h(p_1(x_1, \dots , x_n))$, $\dots$, $h(p_s(x_1, \dots , x_n))\big ) \in \varOmega ^s$. We use a similar notation for the s-tuples Q and R. Let $f \in \mathbb {F}_{p}[X_1, \dots , X_n]$. It is said that f depends on (P, Q, R), which denotes $f \in \langle P, Q,R\rangle$, when there exists a linear decomposition (with an efficient isomorphism between $\mathbb {G}$ and $\widetilde{\mathbb {G}}$):

$$\begin{aligned} f= \sum _{1\le i,j\le s} a_{i,j}\cdot p_i\cdot q_j+\sum _{1\le i,j\le s} b_{i,j}\cdot p_i\cdot p_j+ \sum _{1\le i\le s} c_i\cdot r_i, \end{aligned}$$

where $a_{i,j}, b_{i,j}, c_i \in \mathbb {Z}_{p}$.

We moreover have $b_{i,j} = 0$ when there is no efficiently computable homomorphism between $\mathbb {G}$ and $\widetilde{\mathbb {G}}$. Let P, Q, R be as above and $f \in \mathbb {F}_{p}[X_1, \dots , X_n]$. The $(P,Q,R,f)-\mathsf {GDDHE}$ problem is defined as follows.

Definition 3

$((P,Q,R,f)-\mathsf {GDDHE})$ [1].

Given the vector $H(x_1, \dots , x_n)=(g^{P(x_1, \dots , x_n)}$, $\tilde{g}^{Q(x_1, \dots , x_n)}$, $g_T^{R(x_1, \dots , x_n)}) \in \mathbb {G}^s \times \widetilde{\mathbb {G}}^s \times \mathbb {G}^{s}_{T}$ as above and $T\in \mathbb {G}_T$ decide whether $T = g_{T}^{f(x_1, \dots , x_n)}$.

The $(P,Q,R,f)-\mathsf {GDDHE}$ assumption says that it is hard to solve the $(P,Q,R,f)-\mathsf {GDDHE}$ problem if f is linearly independent of (P, Q, R). In this paper, we will prove that our scheme is semantically secure under this assumption.

3 Construction

3.1 Intuition Behind Our Construction

Delerablée’s technique. In this paper, we extend the Delerablée’s technique of constructing an $\mathsf {IBBE}$ scheme [5] into our $\mathsf {CP}$-$\mathsf {ABBE}$ context. In [5], the user’s private key is of the form $g^{\frac{1}{\alpha +\mathsf {ID}_u}}$, the ciphertext is constructed corresponding to a target set of identities $S = (\mathsf {ID}_{i_1}, \dots , \mathsf {ID}_{i_k})$ is of the form

$$\begin{aligned} g^{\prod _{j=i_1}^{j=i_k}(\alpha +\mathsf {ID}_j)} \end{aligned}$$

and as long as user’s identity is “divided” by S (it means $\mathsf {ID}_u \in S$), she can decrypt. In our scheme, each user u possesses a set of attributes $S_u$ and each clause in the DNF access policy is a set of attributes $\beta _i$: as long as there is at least a set $\beta _i$ which is “divided” by $S_u$ then the user u can decrypt.

Our adaptation. When applying the above technique in ABE’s context, the result is in the reversed form in which a user can decrypt if $S_u$ is “divided” by $\beta _i$. To deal with this problem, we employ a reversed technique to generate the user’s private key by using the user’s “reversed” attribute set $\mathcal {U}\setminus S_u$, where $\mathcal {U}$ is the attribute universe. Now, if $\beta _i$ is “divided” by $S_u$ then $\mathcal {U}\setminus S_u$ is “divided” by $\mathcal {U}\setminus \beta _i$. We then produce the ciphertext in the same way as in [5] (by using $\mathcal {U}\setminus \beta _i$ instead of $\beta _i$).

Re-use randomness vs. collusion. In our $\mathsf {ABBE}$ scheme, the access policy contains many clauses, each clause $\beta _i$ corresponds to a target set in the Delerablée’s IBBE scheme, and it is related to a ciphertext component $C_i$. In order to make the decryption work, all the components $C_i$ are required to use the same randomness and the collusion can take some advantage in exploiting this point. In order to neutralize the advantage of the adversary, we will make use of the “dummy technique” by choosing a random dummy attribute set in creating each $C_i$. Consequently, each $C_i$ is randomized since the random dummy attribute set now plays the role of a fresh randomness.

3.2 Our Scheme

We now describe our scheme which uses the type 3 paring.

 

Setup $(1^\lambda , n, \{S_{u}\}_{\in [n]})$ : :

Assume that the maximum number of attributes is N, the maximum number of clauses in an access policy is $N'$.

Assume that the attribute universe is $\mathcal {U} = \{A_1$, $\dots$, $A_N\} \in \mathbb {Z}_p^N$, the dummy attribute universe is $\mathcal {U'} = \{B_{i,j}\}_{i\in [N'] \atop j\in [N']} \in \mathbb {Z}_p^{N'\times N'}$, suppose that the set of identities of users in the system is $\mathcal {ID} = \{\mathsf {ID}_1, \dots , \mathsf {ID}_n\} \in \mathbb {Z}_p^n$. The algorithm generates a bilinear map group system $D = (p,\mathbb {G},\widetilde{\mathbb {G}},\mathbb {G}_T,e)$, then chooses $h \mathop {\leftarrow }\limits ^{\$}\widetilde{\mathbb {G}}, g \mathop {\leftarrow }\limits ^{\$}\mathbb {G}$ and $\alpha , \gamma \mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_p$. Finally, it outputs:

$$\begin{aligned}&\mathsf {param}= (\mathcal {U}, \mathcal {U'},\mathcal {ID}, D, \{h^{\alpha ^r\cdot \gamma ^t}\}_{r = 0,\dots ,N \atop t = 0, \dots , n+N'}, h^{\frac{\gamma }{\alpha }}, \dots , h^{\frac{\gamma ^{n+N'}}{\alpha }},g^{\alpha }, e(g,h))&\end{aligned}$$

and

$$\begin{aligned} sk_{u} = g^{\frac{1}{(\gamma +\mathsf {ID}_u)\cdot \prod _{i\in \mathcal {U}\setminus S_{u}} (\alpha +A_i)}}. \end{aligned}$$

Encrypt $(\mathsf {param},\beta = (\beta _1 \vee \beta _2 \vee \dots \vee \beta _m), S)$ : :

the algorithm first checks that $\beta _i \ne \beta _j$ for all $i,j\in [m], i\ne j$, then picks a random $k\in \mathbb {Z}_p$ then computes:

Finally, it outputs K and $\mathsf {Hdr}= (C_0, C_{1}, \dots , C_m)$ which includes $\beta$ and S.

Decrypt $(sk_{u},\mathsf {Hdr}, \mathsf {param})$ : :

the algorithm first finds the set $\beta _j$ such that $\beta _j \subset S_{u}$ and checks that $u\in S$, then computes $K'=$

$$\begin{aligned} h^{\frac{1}{\alpha }(\prod _{i\in [m]}(\gamma +B_{j,i}).\prod _{i\in S_{u} \setminus \beta _j}(\alpha +A_i).\prod _{i\in S,i\ne u}(\gamma +\mathsf {ID}_i)-\prod _{i\in [m]}B_{j,i}.\prod _{i\in S_{u} \setminus \beta _j}A_i.\prod _{i\in S,i\ne u}\mathsf {ID}_i)} \end{aligned}$$

Note that it is able to compute $K'$ from the $\mathsf {param}$. It finally computes

$$\begin{aligned} K = (e(C_0,K')\cdot e(sk_{u}, C_j))^{\frac{1}{\prod _{i\in [m]}B_{j,i}.\prod _{i\in S_{u} \setminus \beta _j}A_i.\prod _{i\in S,i\ne u}\mathsf {ID}_i}}. \end{aligned}$$

 

4 Security

Intuitively, following the security model in the Sect. 2.2 we need to prove that given all elements corresponding to the public global parameters, the private decryption keys of corrupted users, and the challenge header, the adversary $\mathcal {A}$ cannot distinguish between a real session key K and a random element in $\mathbb {G}_T$. Therefore, if we define P, Q, R to be the list of polynomials consisting of all elements corresponding to the public global parameters, the private decryption keys of corrupted users, and the challenge header, we need to prove that the following $(P,Q,R,f)- \mathsf {GDDHE}$ assumption holds (that means f is independent to (P, Q, R)), where f corresponds to the real session key. The definition of P, Q, R and f for our $(P,Q,R,f)- \mathsf {GDDHE}$ instance is given by Fig. 1.

Fig. 1.

$(P,Q,R,f)- \mathsf {GDDHE}$ instance

Lemma 1

In the $(P,Q,R,f)- \mathsf {GDDHE}$ assumption above, (P, Q, R) and f are linearly independent.

The semantic security of our scheme now is stated as follows.

Theorem 1

If there exists an adversary $\mathcal {A}$ that solves the semantic security of our scheme with advantage $Adv^{ind}(.)$, then we can construct a simulator to solve an instance of the $(P,Q,R,f)- \mathsf {GDDHE}$ problem above with the same advantage $Adv^{ind}(.)$.

We refer the proofs of the above lemma and theorem to the full version of the paper.

5 Implementation and Optimization

We have implemented our $\mathsf {CP}$-$\mathsf {ABBE}$ in the scenario given in Sect. 2.1. We have tested several values for the number n of users and the maximum number of attributes N, we also give some tricks when implementing to optimize the encryption phase and decryption phase. We refer the optimization and benchmarks of our implementation to the full version of the paper.