Hidden Policy Attribute-Based Data Sharing with Direct Revocation and Keyword Search in Cloud Computing

Abstract

Attribute-based encryption can be used to realize fine-grained data sharing in open networks. However, in practical applications, we have to address further challenging issues, such as attribute revocation and data search. How do data users search for the data they need in massive amounts of data? When users leave the system, they lose the right to decrypt the shared data. In this case, how do we ensure that revoked users cannot decrypt shared data? In this paper, we successfully address these issues by proposing a hidden policy attribute-based data sharing scheme with direct revocation and keyword search. In the proposed scheme, the direct revocation of attributes does not need to update the private key of non-revoked users during revocation. In addition, a keyword search is realized in our scheme, and the search time is constant with the increase in attributes. In particular, the policy is hidden in our scheme, and hence, users’ privacy is protected. Our security and performance analyses show that the proposed scheme can tackle the security and efficiency concerns in cloud computing.

1. Introduction

With the application of intelligent terminals in our lives, a large amount of data can be generated quickly. These collected data are closely related to our lives. By analyzing personal data, one’s behavior can be predicted, and by analyzing the enterprise data, a lot of business secrets can be obtained which can pose a serious threat to individuals [1] or enterprises [2]. Furthermore, there are many threats to data privacy during the processes of data processing [3,4], data transmission [5], data storage [6,7], data search [8], data confidentiality [9,10] and data access [11,12]. Among these security problems, we focus on security issues in cloud storage and cloud computing.

While the rapid development of cloud computing brings convenience to enterprises and individuals because of its storage services, computing services, scalability and so on, data security and user privacy are also a big problem [13,14] owing to data being exposed in open network environments [15]. Encrypting data before uploading data to the cloud server can solve data security and user privacy issues very well [16,17]. However, the encryption of data causes the loss of some characteristics of plaintext, and data sharing among numerous data users becomes another problem. Fortunately, attribute-based encryption (ABE) [18] provides a good solution to the data sharing and access control on cloud storage and cloud computing. After Sahai et al. proposed the notion of ABE, much work was done to improve the function and efficiency of the ABE. For example, Li et al. [19] proposed a multi-authority, fine-grained access control scheme. Zhang et al. [20] proposed an anonymous access control scheme for proxy re-encryption. Shen et al. [21] proposed a data sharing scheme with anonymous tracking. These schemes are extensions of the ABE scheme and can be applied to some specific environments. In the scenario of data sharing, the Ciphertext Policy Attribute-Based Encryption (CP-ABE) [22] is more popular. In the CP-ABE system, the data owner specifies the access control structure related to ciphertexts. Only when the user attributes connected with the user secret key satisfy the access control structure, can the data be decrypted correctly. For example, Cai et al. [23] applied CP-ABE to the medical cloud which can help to improve the quality of medical services. Zhang et al. [24] applied CP-ABE to the mobile cloud computing, which makes it possible for resource-limited users to share data with others.

Although CP-ABE can bring a lot of convenience to our lives, there are still many problems to be considered in practical applications. For example, how can we ensure that revoked users cannot decrypt shared data? How do data users search for the data they want among massive amounts of data? In addition, in the CP-ABE system, the access control structure is also uploaded to the cloud server with the ciphertext, which may also leakage some sensitive information. In order to solve the above problems, the typical CP-ABE scheme is no longer suitable for the complex cloud computing environment. Therefore, searchable attribute-based encryption schemes (SABE) [25] and revocable attribute-based encryption schemes (RABE) [26] have been put forward.

In SABE [27,28], the data owner will upload the encrypted keyword index together with the ciphertext. When data users want to use data, he will generate a keyword trapdoor with his secret key, then uploads it to the cloud server. The cloud server checks whether the ciphertext containing the keyword index exists on the server without knowing the keyword. If it exists, the ciphertext will be returned to data users. Therefore, data users can retrieve the data they want based the keyword trapdoor. However, the search time in most searchable attribute-based encryption schemes increases with the number of attributes, which increases the burden on the server and reduces the user experience. In addition, when the access control structure is uploaded, it will also leakage some sensitive information.

The revocation scheme has practical application in dynamic networks and systems. For example, when a user leaves the system, the user identity is revoked in the system [29] which increases the security of the system. The RABE scheme can be divided into indirectly revocable attribute-based encryption (IRABE) schemes [30,31] and directly revocable attribute-based encryption (DRABE) schemes [32,33,34,35]. In the IRABE schemes, the revocation list is maintained by the authority center. When the user is removed from the system, the authority center updates the secret key of the non-revoked user. In DRABE schemes, the user’s revocation list is held by the user. When a user is revoked, the user’s private key does not need to be updated. Comparing the two schemes, the direct revocation scheme is more suitable for open network environments. In order to prevent the revoked users from decrypting the previous ciphertext, we can use the powerful computing power of cloud computing to update the ciphertext when the user is revoked from the system.

In order to make the data sharing scheme of CP-ABE more applicable to practical applications, it is necessary to propose a data sharing scheme with the functions of direct revocation and keyword search.

1.1. Our Contribution

In order to solve the problem described above and make the data sharing scheme of ABE more practical, we propose a hidden policy attribute-based data sharing scheme with direct revocation and keyword search (ABERS). Our scheme has the following advantages:

• Direct revocation of attributes: We use subset covering theorem to achieve the direct revocation of attributes. After revocation, there is no need to update the private key of the non-revoked user. In order to ensure that the users who have been revoked cannot decrypt the previous ciphertext, the ciphertext is updated.
• Fast keyword search: We use aggregation technology to achieve the fast search of keywords. Keyword search time is constant and will not increase with the numbers of attributes.
• Hidden policy: We use the AND gate access control structure to achieve the hidden policy. When the ciphertext is uploaded, the access control structure does not need to be uploaded. Thus, the function of the hidden policy can be realized.

1.2. Related Work

We review the work of the AND-gate attribute based encryption, the revocable attribute based encryption and the authorized keyword search in this section.

AND-gate attribute based encryption: Sahai and Waters [18] proposed the ABE scheme to solve data sharing and data access control. After Sahai et al. had proposed the ABE, much work was done to improve the function and efficiency of the ABE. In order to apply the function of the ABE scheme more flexibly, ABE was divided into key-policy ABE (KP-ABE) [36] and ciphertext-policy ABE (CP-ABE) [22,37]. In order to facilitate the application of terminal devices, some work was also done in references [38,39]. An AND-gate access structure ABE was introduced by Cheung and Newprot [40]. Unfortunately, there is no hidden access policy in this scheme. Due to the appearance of inner product encryption schemes, several other schemes [28,41,42] follow this structure, while hiding the access policy.

Revocable attribute based encryption: The RABE scheme is divided into IRABE schemes [30,31] and DRABE schemes [32,33,34]. In IRABE schemes, the revocation list is maintained by the authority center. When the user is removed from the system, the authority center updates the secret key of the non-revoked user. In DRABE schemes, the user’s revocation list is held by the user. When a user is revoked, the user’s private key does not need to be updated. In order to prevent revoked users from decrypting ciphertexts that existed before revocation, some work on the re-encryption proxy was done in reference [31] without interacting with data owners and in reference [43] without interacting with non-revoked users.

Authorized keyword search: The search encryption scheme can be traced back to Perrig et al. [44]. Unfortunately, the scheme has a high computational cost. To accelerate the search, Lee et al. [45] implemented search encryption through hash tables. To make the application scene more flexible, a keyword search encryption scheme based on a public key was proposed in reference [46,47]. In order to make the search more secure, the authentication search encryption scheme was proposed in reference [48,49]. Further work was done in references [50,51]. In reference [50], the authorized keyword search was implemented through ABE technology with multi-keywords. The scheme presented in reference [51] can be applied to multi-user and multi-owner scenes; however, it is not suitable for dynamic network environments.

2. Preliminary

In this section, we mainly introduce the basic knowledge about attribute revocation and keyword search.

2.1. Access Control Structure

The “AND gate” access structure [52] is described as follows: Let $S=(x_1,x_2,\dots ,x_n)$ represent an attribute list of a user. Let $W=(w_1,w_2,\dots ,w_n)$ represent an access policy. The attributes satisfy the access control structure, if and only if $x_i=w_i,i\in [1,\dots ,n]$. Because the access control structure and attribute set have the same structure, when uploading ciphertext, there is no need to upload the control structure. So, the hidden policy can be achieved.

2.2. Multilinear Maps

The concept of multilinear mapping was first proposed by Boneh and Silverberg, as the following [53]. First, run $\Gamma (1^{\lambda },n)$ to get $G=(<$$G_1$>$,\dots ,$<$G_n$>), where $\lambda$ is a security parameter. The description of the prime number group, $G_i$, whose order is $p>2^{\lambda }$ and contains the generator, $g_i$, of $G_i$, is expressed by $<G_i>$. A series of linear maps, $\{e_{i,j}:G_i\times G_j|i,j\ge 1;i+j\le n\}$, are defined as follows:

$$e_{i,j}(g_i^u,g_j^v)=g_{i+j}^{uv}\forall u,v\in Z_p.$$

We simplify the description as $e(g_i^u,g_j^v)=g_{i+j}^{uv}$.

2.3. Subset Cover

First, we introduce the full binary tree T of depth d, in which two functions $depth\left(x\right)$ and $path\left(x\right)$ are involved. Both $depth\left(x\right)$ and $path\left(x\right)$ take node x as the input. The function $depth\left(x\right)$ takes the depth of node x as the output. The function $path\left(x\right)$ takes the path from the roo,t $P_{x,0}=root$, to the node, $P_{x,denpth\left(x\right)}=x$, as the output. The use of subset cover theorem to solve the user revocation was referred to by Naor et al. [54]. Let the leaf node express the user in the system. For a set of revoked users, R, we can get all paths, ${\left\{path\left(x\right)\right\}}_{\forall x\in R}$, of the revocation node $x\in R$. The $cover\left(R\right)$ is the smallest set that can cover the unmarked nodes. For ease of understanding, we give a simple example, shown in Figure 1. Eight leaves $x_8,\dots ,x_{15}$ are contained in the full binary tree, T. If $R=\{x_8,x_{11}\}$ is a revocation set. The paths of nodes $x_8$ and $x_{11}$ are $path\left(x_8\right)=(x_1,x_2,x_4,x_8)$ and $path\left(x_{11}\right)=(x_1,x_2,x_5,x_{11})$, respectively. The $cover\left(R\right)$ set is $\{x_3,x_9,x_{10}\}$. The non-revoked leaf nodes are covered by $cover\left(R\right)$.

Assumption 1.n-$Multi-linearDecisionalDiffie$–$Hellman$ (n-$MDDH$): Run $\Gamma (1^{\gamma },n)$ to get $G=($<$G_1$>$,\dots ,$<$G_n$>). Select $v_0,\dots ,v_n\in Z_p$. Compute $g_1^{v_0},\dots ,g_1^{v_n}$. For any poly-time algorithm, it is difficult with non-negligible advantage to tell $g_n^{{\prod }_{j\in [0,\dots ,n]}{v}_j}$ from a random element in $G_n$. Please refer to [55] for more details.

3. Definition

In this section, we mainly introduce the deployment of the model, the definition of the scheme and the security model of the scheme.

3.1. Deployment

ABERS can be applied to real environments. The data sharing system is shown in Figure 2. It involves four entities: data owner, data user, attribute authority and cloud server. Now, we will introduce their specific functions and functions.

• Data owner: The data owner is responsible for encrypting the data and generating the keyword index, I, and then uploading the ciphertext, $CT$, and keyword index, I. When the revocation list changes, the revocation list, $R{}^{\prime }$, is sent to the cloud server by the data owners.
• Data user: When data users want to download data, they should first use their own private keys to generate a keyword trapdoor, T, and then send T to the cloud server to check it. If the request is legal, then the desired data $CT$ can be obtained.
• Attribute authority: The attribute authority is responsible for managing all users in the system, initializing the system, publishing the system’s public parameters, $PK$, and generating the secret key, $SK$, for the user.
• Cloud server: The cloud server is responsible for storing the ciphertext of the data owner. When the data user sends the keyword trapdoor to the cloud server, the cloud server searches for it. If the file exists, it is returned to the data user. When the new revocation list is received from the data owner, the cloud server updates the ciphertext with the $Updata\left(R{}^{\prime }\right)$ algorithm.

3.2. Definition of the System Model

Our construction algorithm consists of the following eight algorithms.

$Setup(1^{\lambda },d,I,U)\to PK,MSK$: The algorithm takes the security parameters, $\lambda$, the depth of the tree, d, the set of the user identity, I, and the collection of attributes, U, as inputs with the common system parameters, $PK$, and the main secret key, $MSK$, as the outputs.

$Keygen(PK,MSK,S,id)\to S{K}_S$: The algorithm uses $PK$, $MSK$, the user attribute, S, and the user identity, $id$, as inputs, with $S{K}_S$ as the output.

$Encrypt(PK,M,W,R,w)\to C{T}_{W,R},I_{\omega }$: This algorithm uses $PK$, the message, M, an AND-gate access structure, W, a revocation list, R and the keyword, w, as inputs, with the ciphertext, $C{T}_{W,R}$, and keyword index, $I_{\omega }$, as the outputs.

$Trapdoor(S{K}_S,w)\to t_{\omega }$: This algorithm takes the user’s secret key, $S{K}_S$, and a keyword, w, as inputs with a trapdoor, $t_{\omega }$, as the output.

$Test(I_{\omega },t_{\omega })\to 0$$or$ 1: This algorithm takes the keyword index, $I_{\omega }$, and a trapdoor, $t_{\omega }$, as inputs with a Boolean value, $\{0,1\}$, as the output.

$Decryption(PK,C{T}_{W,R},S{K}_S)\to m$ or ⊥: This algorithm takes $PP,C{T}_{W,R}$ and $S{K}_S$ as inputs, with m or ⊥ as the output.

$Update(C{T}_{W,R},R{}^{\prime })\to C{T}_{W,R{}^{\prime }}$: This algorithm takes $C{T}_{W,R}$ and $R{}^{\prime }$ as inputs with $C{T}_{W,R{}^{\prime }}$ as the output.

3.3. Definition of System Security

The adversaries against the ABERS scheme include unauthorized data users and revoked data users. For unauthorized users, their attributes do not satisfy the access control structure. For revoked data users, their identities are in the revocation list. Both of them try their best to get the information of the ciphertext. Their behavior also includes a secret key recovery attack. They want to get a private key from a keyword trapdoor. The concrete models are as follows:

Indistinguishability against chosen plaintext attack (IND-CPA):

This security game is defined as follows:

• Init: The adversary, A, sends a revocation list, $R^{*}$, chosen by A to the challenger, B.
• Setup: B calls the algorithm $Setup(1^{\lambda },d,I,U)\to PP,MSK$, and then sends $PP$ to A.
• Phase 1: The adversary, A, is able to ask B about the private key of user $(S,id)$.
  When $id\notin R$${}^{*}$, the enquiry is aborted. Otherwise, B calls the algorithm $Keygen(PP,MSK,S,id)\to S{K}_S$ and then sends $S{K}_S$ to A.
• Challenge: A sends two messages $m_0^{*}$, $m_1^{*}$ ($|m_0^{*}|=|m_1^{*}|$) and a challenge access structure, W, to B. B randomly selects $b\in \{0,1\}$ and then calls the algorithm $Encrypt(PP,m_b^{*},W,R)\to C{T}_{W,R}$ and finally, sends $C{T}_{W,R}$ to A.
• Phase 2: A does the same inquiries as in Phase 1.
• Guess: A outputs the guess of b as $b{}^{\prime }\in \{0,1\}$.

In this game, the advantage of adversary A is defined as follows:

$$P{r}_A=|Pr[b=b{}^{\prime }]-\frac{1}{2}|$$

Definition 1.

If the advantage, $P{r}_A$, of any polynomial-time adversary A is negligible, then the ABERS scheme is selectively indistinguishable under the $(d+3)$-$MDDH$ assumption.

Indistinguishability against chosen keyword attack (IND-CKA):

This security game is defined as follows:

• Setup: B calls the algorithm $Setup(1^{\lambda },d,I,U)\to PP,MSK$ and then sends $PP$ to A.
• Phase 1: The adversary, A, is able to ask B about the private key of user $(S,id)$. B calls the algorithm $Keygen(PP,MSK,S,id)\to S{K}_S$ and then sends $S{K}_S$ to A.
• Challenge: A sends two messages, $w_0^{*}$, $w_1^{*}$ ($|w_0^{*}|=|w_1^{*}|$), and a challenge access structure, W, to B. B randomly selects $b\in \{0,1\}$ and then calls the algorithm $Encrypt(PP,M,W,R,w_b^{*})\to C{T}_{W,R},I_{\omega }$ and finally, sends $I_{\omega }$ to A.
• Phase 2: A does the same inquiries as in Phase 1.
• Guess: A outputs the guess of b as $b{}^{\prime }\in \{0,1\}$.

In this game, the advantage of adversary A is defined as follows:

$$P{r}_A=|Pr[b=b{}^{\prime }]-\frac{1}{2}|$$

Definition 2.

If the advantage, $P{r}_A$, of any polynomial-time adversary, A, is negligible, then the ABERS scheme is indistinguishable against the chosen keyword attack.

Selective security game on updated ciphertext:

This security game is defined as follows:

• Setup: The adversary, A, sends two revocation lists, R and $R^{*}$, and an attribute, $S^{*}$, that chosen by A to the challenger, B. B calls the algorithm $Setup(1^{\lambda },d,I,U)\to PP,MSK$ and then sends $PP$ to A.
• Phase 1: The adversary, A, is able to ask B about the private key of user $(S^{*},id)$. When $id\notin R^{*}$, the enquiry is aborted. Otherwise, B calls the algorithm $Keygen(PP,MSK,S,id)\to S{K}_S$ and then sends $S{K}_S$ to A.
• Challenge: A sends two messages, $m_0^{*}$, $m_1^{*}$ ($|m_0^{*}|=|m_1^{*}|$), and a challenge access structure, W, to B. B randomly selects $b\in \{0,1\}$ and then calls the algorithm $Encrypt(PP,m_b^{*},W,R,w)\to C{T}_{W,R},I_{\omega }$ and $Update(C{T}_{W,R},R{}^{\prime })\to C{T}_{W,R{}^{\prime }}$ and finally, sends $C{T}_{W,R{}^{\prime }}$ to A.
• Phase 2: A does the same inquiries as in Phase 1.
• Guess: A outputs the guess of b as $b{}^{\prime }\in \{0,1\}$.

In this game, the advantage of adversary A is defined as follows:

$$P{r}_A=|Pr[b=b{}^{\prime }]-\frac{1}{2}|$$

Definition 3.

If the advantage, $P{r}_A$, of any polynomial-time adversary, A, is negligible, then the ABERS scheme has selective security under the $(d+3)$-$MDDH$ assumption.

4. Data Sharing System

In this section, we mainly introduce the concrete scheme, which contains the following seven algorithms System initialization, User registration, Ciphertext upload, Trapdoor generation, Ciphertext retrieval, Ciphertext decryption and Ciphertext update. The attribute authority executes the System initialization algorithm to generate public parameters and a master key for the system. Next, a secret key is generated by the attribute authority by running the User registration algorithm for each legitimate user based on their attributes. After that, ciphertext generated by the Ciphertext upload algorithm based on the access control structure can be uploaded to the cloud server to share data. If a data user wants to use data that is shared by a data owner, he first generates a keyword trapdoor with the Trapdoor generation algorithm based on his private key and keyword and uploads the keyword trapdoor to the server. After receiving the request, the cloud server checks whether the ciphertext containing the keyword trapdoor exists by calling the Ciphertext retrieval algorithm. If it exists, the ciphertext is returned to the data user. Then, the data user can decrypt the information with the Ciphertext decryption algorithm if his attributes satisfy the access control structure. In addition, when the cloud service receives the new revocation list from the data owner, the server updates the ciphertext with the Ciphertext update algorithm. The concrete implementation is as follows:

4.1. System Initialization

The attribute authority runs the $Setup$ algorithm according to the system model definition. It runs the group generation algorithm to get $G=(<G_1>,\dots ,<G_{d+3}>)$. Then, it selects a random number, $\alpha ,\beta ,a\in Z_p$ and a hash function, $H_1:{\{0,1\}}^{*}\to G_1$, $H_2:{\{0,1\}}^{*}\to G_1$. Finally, the $PP$ and $MSK$ are as follows:

$$PK=(G,g_{d+3}^{\alpha },g_1^{\beta },g_1^a,H_1,H_2).$$

$$MSK=(\alpha ,\beta ).$$

4.2. User Registration

At the user registration stage, the interaction between the attribute authority and the system user is as shown Figure 3—when the attribute authority receives the user’s attributes, S, and identity, $id$, the $Keygen$ algorithm is called and returns the secret key, $SK$, to the system user safely.

The concrete algorithms are as follows: Suppose that the path of $id$ is $path\left(id\right)=\{p_{id,0},\dots ,p_{id,d}\}$, where $p_{id,0}=root$ and $p_{id,d}=x$. The algorithm sets $P_{id,-1}=g_1^a$. Then, it calls the following recursive algorithm: $P_{id,j}=e(H_2\left(P_{id,j}\right),P_{id,j-1})$, for $j\in [0,d],P_{id,j}\in path\left(id\right)$. Then, for $\forall x_i\in S$, it randomly selects $r_i\in Z_p$. In addition, a random number, $r{}^{\prime }\in Z_p$, is selected. Finally, it calculates $r={\sum }_{i=1}^n{r}_i$, $K_0=g_{d+2}^{\frac{\alpha +r}{\beta }}·P_{id,d}^{r{}^{\prime }}$, $K_1=g_1^{r{}^{\prime }}$, $K_2=g_1^{\beta r{}^{\prime }}$, $k_3={\prod }_{i=1}^n{H}_1{\left(x_i\right)}^{\beta }$, ${\{K_i=g_{d+2}^{r_i}·H_1{\left(x_i\right)}^{r{}^{\prime }}\}}_{x_i\in S}$. The secret key is $S{K}_S=\{K_0,K_1,K_2,K_3,{\left\{K_i\right\}}_{x_i\in S}\}$.

4.3. Ciphertext Uploading

At the ciphertext uploading phase, the interaction between the cloud server and the data owner is as shown as Figure 4: The data owner calls the $Encryption$ algorithm and then uploads the ciphertext, $CT$, and keyword index, I, to the cloud server.

The concrete algorithms are as follows: The algorithm randomly selects $s,s{}^{\prime }\leftarrow Z_p^{*}$ and then calculates $C_0=M·g_{d+3}^{\alpha ·s}$, $C_1=g_1^s$, $C_2=g_1^{\beta s}$, $C_{1,i}=H_1{\left(W_i\right)}^s$, ${\tilde{C}}_1=e(g_1^{\beta },g_1^{ws{}^{\prime }})$, ${\tilde{C}}_2=g_1^{ss{}^{\prime }}$.

Suppose the path of element $x\in cover\left(R\right)$ is $path\left(x\right)=(p_{x,0},\dots ,p_{x,depth\left(x\right)})$, where $p_{x,0}$ represents $root$ and $p_{x,depth\left(x\right)}=x$. Then, the algorithm sets $P_{x,-1}=g_1^a$. Finally, it calls the recursive algorithm $P_{x,j}=e(H\left(P_{x,j}\right),P_{x,j-1})$ for $j\in [0,d]$ and calculates $C_{2,i}=P_{x,depth\left(x\right)}^s$. The ciphertext and keyword index are as follows:

$$C{T}_{W,R}=(C_0,C_1,C_2,\{C_{1,i},C_{2,i}\}).$$

$$I_w=({\tilde{C}}_1,{\tilde{C}}_2,\left\{C_{1,i}\right\}).$$

4.4. Trapdoor Generation

At the trapdoor generation phase, the interaction between the cloud server and the data user is as shown as Figure 5: The data user calls the algorithm $Trapdoor$, and then uploads the keyword trapdoor, T, to the cloud server.

The data user generates the keyword trapdoor with the following formula:

$$t_w=e(K_3,g_1^w)=e(\prod _{i=1}^n{H}_1{\left(x_i\right)}^{\beta },g_1^w).$$

No information about w can be obtained from $t_{\omega }$.

4.5. Ciphertext Retrieval

The cloud server runs the $Test$ algorithm according to the definition of the system model. It retrieves the file containing the keyword w with the following formula:

$$e({\tilde{C}}_2,t_w)=e(\prod _{i=1}^n{C}_{1,i},\tilde{C}1).$$

When the equation is correct, it returns 1. The file exists on the cloud server. When the equation is wrong, it returns 0. The file does not exist on the cloud server.

The correctness of the phase Ciphertext retrieval is verified as follows:

$$\begin{array}{cc}\hfill e({\tilde{C}}_2,t_w)& =e(g_1^{ss{}^{\prime }},e(\prod _{i=1}^n{H}_1{\left(x_i\right)}^{\beta },g_1^w))\hfill \\ & =e(\prod _{i=1}^n{H}_1{\left(x_i\right)}^s,e(g_1^{s{}^{\prime }w},g_1^{\beta }))\hfill \\ & =e(\prod _{i=1}^n{C}_{1,i},{\tilde{C}}_1).\hfill \end{array}$$

4.6. Ciphertext Decryption

At the ciphertext decryption stage, the interaction between the cloud server and the data user is as shown as Figure 6: The data user calls the $Decrypt$ algorithm. If the user is legal, the ciphertext will be deciphered.

The concrete algorithms are as follows: If $\exists i\in [1,\dots ,n]$ $x_i\ne W_i$, the attribute list S does not satisfy the access control structure. The algorithm returns ⊥. When $id\in R$, The algorithm outputs ⊥. Otherwise, it calculates the following process.

If $id$ does not belong to R, there will be a node, $x\in \left(path\right(id)\cap cover(R\left)\right)$, where $path\left(x\right)=(p_{x,0},\dots ,p_{x,depth\left(x\right)})$ and $path\left(id\right)=(p_{id,0},\dots ,p_{id,d})$. At the same time, there is $p_{id,j}=p_{x,j}$ for $j\in [0,\dots ,depth(x\left)\right]$.

The algorithm sets $P_{id,depth\left(x\right)}{}^{\prime }=P_{x,depth\left(x\right)}=C_{2,x}$. Then, it calls the recursive algorithm $P_{id,j}{}^{\prime }=e(H_2\left(P_{id,j}\right),P_{id,j-1}{}^{\prime })$ for $j\in [depth\left(x_i\right)+1,\dots ,d]$. The equation $P_{id,d}{}^{\prime }=P_{id,d}^s$ can be obtained.

Then, it calculates

$$\frac{e(K_0,C_2)}{{\prod }_{i=1}^n\frac{e(K_i,C_1)}{K_1,C_{1,i}}·e(P_{id,d}{}^{\prime },K_2)}=g_{d+3}^{\alpha s}.$$

Finally, the following formula is used to get the plaintext:

$$M=\frac{C_0}{g_{d+3}^{\alpha s}}.$$

The correctness of the Ciphertext decryption phase is verified as follows:

$$\begin{array}{cc}\hfill \prod _{i=1}^n\frac{e(K_i,C_1)}{e(K_1,C_{1,i})}& =\prod _{i=1}^n\frac{e(g_{d+2}^{r_i}{H}_1\left(x_i\right)r{}^{\prime },g_1^s)}{e{(g_1^{r{}^{\prime }},H_1\left(w_i\right))}^s}\hfill \\ & =\prod _{i=1}^{n}e(g_{d+2}^{r_i},g_1^s)\hfill \\ & =g_{d+3}^{sr}.\hfill \end{array}$$

$$\begin{array}{cc}\hfill \frac{e(K_0,C_2)}{{\prod }_{i=1}^n\frac{e(K_i,C_1)}{e(K_1,C_{1,i})}·e(p_{id,d}{}^{\prime },K_2)}& =\frac{e(g_{d+2}^{\frac{\alpha +r}{\beta }}·P_{id,d}^{r{}^{\prime }},g_1^{\beta s})}{g_{d+3}^{sr}·e(p_{id,d}^s,g_1^{\beta r{}^{\prime }})}\hfill \\ & =g_{d+3}^{\alpha s}.\hfill \end{array}$$

4.7. Ciphertext Update

When the revocation is changed, the ciphertext stored on the cloud server will be updated. The cloud server runs the $Update$ algorithm according to the definition of the system model. It inputs a ciphertext, $C{T}_{W,R}$, and a new revocation list, $R{}^{\prime }$, where $R\subset R{}^{\prime }$ outputs the updated ciphertext, $C{T}_{W,R{}^{\prime }}$.

If $x\in Cover\left(R\right)$, $x=y$ for $y\in Cover\left(R{}^{\prime }\right)$. $C_{2,i}{}^{\prime }=C_{2,i}$ is set.

For $x\in Cover\left(R\right)$, y is a child of x. Let $path\left(y\right)=path\left(x\right)\bigcup (p_{y,depth\left(x\right)+1},\dots ,p_{y,depth\left(y\right)})$ and set $p_{y,depth}{}^{\prime }=p_{x,depth}{}^{\prime }=C_{2,i}$. Then, it calls the recursive algorithm $P_{y,j}{}^{\prime }=e(H_2\left(P_{y,j}\right),P_{y,j-1})$ for $j\in \left[depth\right(x)+1,\dots ,depth(y\left)\right]$. Finally, it sets $C_{2,i}{}^{\prime }=P_{y,depth\left(y\right)}{}^{\prime }$, $C_0{}^{\prime }=C_0$, $C_1{}^{\prime }=C_1$, $C_2{}^{\prime }=C_2$, and $C_{1,i}{}^{\prime }=C_{1,i}$. The updated ciphertext is $C{T}_{W,R}=(C_0{}^{\prime },C_1{}^{\prime },C_2{}^{\prime },\{C_{1,i}{}^{\prime },C_{2,i}{}^{\prime }\})$.

5. Security Proof

Theorem 1.

The ABERS scheme is the $IND$-$CPA$ security under $(d+3)$-$MDDH$ assumption in the random oracle model.

If the adversary, A, can break through our scheme with an advantage that we cannot ignore, a simulator, B, can call the Adversary, A, to break the $(d+3)$-$MDDH$ assumption.

Simulator B inputs the group parameters, $(1^{\gamma },n)$, and instantiates the $(d+3)$-$MDDH$ instance $(g_1,g_1^{a_0},\dots ,g_2^{a_{d+3}},Z)$. The game between the simulator B and the attacker A is as follows:

Setup: Adversary A selects a revocation list, $R^{*}$, and sends it to B. For each element, $id\in R^{*}$, in the revocation list, $R^{*}$, the simulator B sets $P_{R^{*}}={\{p_{id,i}\in path\left(id\right)\}}_{id\in R^{*},i\in [0,\dots ,d]}$ and the hash functions $H_1$, $H_2$ are simulated as followed:

• ${\mathbb{O}}_{H_1}$: When $H_1$ is called by the adversary, A (or B), a random number, $z_i\in Z_p$, is selected (unless it has already been done), and the simulator returns $g_1^{z_i}$ as a response to $H_1\left(x_i\right)$.
• ${\mathbb{O}}_{H_2}$: When $p_{id,i}\in P_{R^{*}}$, $H_2$ is called by the adversary, A (or B), and a random number, $v_{id,i}\in Z_p$, will be selected (if it has already been done, the same result will be returned), and the simulator returns $g_1^{a_i+v_{id,i}}$ as a response to $H_2\left(p_{id,i}\right)$.
• When $p_{id,i}\notin P_{R^{*}}$, $H_2$ is called by the adversary, A (or B), a random number, $v_{id,i}\in Z_p$, will be selected (if it has already been done, the same result will be returned), and the simulator returns $g_1^{v_{id,i}}$ as a response to $H_2\left(p_{id,i}\right)$.

The challenger, B, randomly selects the random number, $\alpha ,\beta ,a\leftarrow Z_p$, and calculates $g_{d+3}^{\alpha },g_1^{\beta },g_1^a$ and then returns $(G,g_{d+3}^{\alpha },g_1^{\beta },g_1^a,{\mathbb{O}}_{H_1},{\mathbb{O}}_{H_2})$ to A.

$Phase1\&2$: The adversary A makes the following enquiries to the challenger.

• When $id\notin R^{*}$, the enquiry is aborted.
• When $id\in R^{*}$, if A asks the challenger about the secret key of the user’s identity, $id$, and attributes, $S=(x_1,x_2,\dots ,x_n)$, random numbers, $r{{}^{\prime }}_j\in Z_p$ and $r_i^j\in Z_p\forall x_i\in S$, will be selected. Then, the simulator B calculates $r^j={\sum }_{i=1}^n{r}_i^j$, $D=g_{d+2}^{\frac{\alpha +r^j}{\beta }}$, $K_1=g_1^{r_j{}^{\prime }},K_2=g_1^{\beta r_j{}^{\prime }}$, $K_3={\prod }_{i=1}^n{g}_1^{z_i\beta }$ and $K_i=g_1^{r_i^j+z_i{r}_j{}^{\prime }}$.
• The path of $id$ is represented as $path\left(id\right)=(p_{id,0},p_{id,d})$ and then $H_2\left(p_{id,i}\right)=g_1^{(a_i+v_{id,i})}$. After that, B computes $p_{id,d}=g_{d+2}^{a{\prod }_{i=0}^d(a_i+v_{id,i})}$ by calling multi-linear maps on $g_1^b,g_1^{a_0+v_{id,d}},\dots ,g_1^{a_d+v_{id,d}}$ and $K_0=g_{d+2}^{\frac{\alpha +r^j}{\beta }}·g_{d+2}^{b{\prod }_{i=0}^d(a_i+v_{id,i})}$.
• Finally, the secret key, $\{K_0,K_1,K_2,K_3,{\left\{K_i\right\}}_{x_i\in S}\}$, is returned to A.

Challenge: The adversary A sends two messages, $m_0^{*}$, $m_1^{*}$ ($|m_0^{*}|=|m_1^{*}|$), and a challenge access structure, W, to B, B randomly selects $b\in \{0,1\}$, and the encryption process is as follows: $C_0=m_b^{*}·Z$, $(C_1=g_1^{a_{d+3}}$, $C_2=g_1^{\beta a_{d+3}}$, $C_{1,i}=g_1^{t_i{a}_{d+3}}$. In addition, $P_{x,d}$ is generated according to the specified algorithm. $C_{2,i}=P_{x,d}^{a_{d+3}}$ is set. Finally, $(C_0,C_1,C_2,\{C_{1,i},C_{2,i}\})$ is sent to A.

Guess:$b{}^{\prime }\in \{0,1\}$ is output by A.

When $Z=g_{d+3}^{{\prod }_{j\in [0,\dots ,d]}{a}_j}$, A plays the security game with B. When Z is a random number in a group, $G_{d+3}$, the information that $C_0$ contains $m_b^{*}$ is lost. Therefore, the simulator, B, can call the A to break the $(d+3)$-$MDDH$ assumption. Because the assumption is difficult, our scheme is secure.

Theorem 2.

Suppose q is a bound on the total number of group elements in the $INK$-$CKA$ security game. The advantage in this security game is $O(q^2/p)$.

Simulator B inputs the group parameters $(1^{\gamma },n)$ and instantiates the $(d+3)$-$MDDH$ instance $(g_1,g_1^{a_0},\dots ,g_2^{a_{d+3}},Z)$. The game between the simulator B and the attacker A is as follows:

Setup: The hash function, $H_1$, is simulated as follows:

${\mathbb{O}}_{H_1}$: When $H_1$ is called by the adversary, A (or B), a random number, $z_i\in Z_p$, will be selected (unless it has already been done), and the simulator returns $g_1^{z_i}$ as a response to $H_1\left(x_i\right)$.

The challenger, B, randomly selects the random number, $\alpha ,\beta ,a\leftarrow Z_p$, and calculates $g_{d+3}^{\alpha },g_1^{\beta },g_1^a$ and then returns $(G,g_{d+3}^{\alpha },g_1^{\beta },g_1^a,{\mathbb{O}}_{H_1})$ to A.

$Phase1$: The adversary, A, makes the following enquiries to the challenger.

The adversary A asks for the keyword, w, connected with $S=(x_1,x_2,\dots ,x_n)$ and the user’s identity, $id$, for B. The random numbers $r{{}^{\prime }}_j\in Z_p$ and $r_i^j\in Z_p\forall x_i\in S$ will be selected. Then, the simulator, B, calculates $r^j={\sum }_{i=1}^n{r}_i^j$, $D=g_{d+2}^{\frac{\alpha +r^j}{\beta }}$, $K_1=g_1^{r_j{}^{\prime }},K_2=g_1^{\beta r_j{}^{\prime }}$, $K_3={\prod }_{i=1}^n{g}_1^{z_i\beta }$ and $K_i=g_1^{r_i^j+z_i{r}_j{}^{\prime }}$.

Finally, the simulator B produces trapdoor $t_w$ as $t_w=e(K_3,g_1^w)=e(g_1^{\beta {\sum }_{i=1}^n{z}_i},g_1^w)$. After that, the trapdoor $t_w$ is sent to A.

Challenge: The adversary, A, sends two keywords, $w_0^{*}$, $w_1^{*}$ ($|w_0^{*}|=|w_1^{*}|$) to B. At the same time, the challenge access control structure, W, will also be sent. B randomly selects $s,s{}^{\prime }\in Z_p$ and $b\in \{0,1\}$, and the encryption process is as follows: $C_{1,i}=g_1^{z_{i}s}$, ${\tilde{C}}_1=e(g_1^{\beta },g_1^{w_b^{*}s{}^{\prime }})$, ${\tilde{C}}_2=g_1^{ss{}^{\prime }}$. The challenge index, $I_w^{*}$, is sent to A.

Phase 2: This stage is the same as Phase 1, but there is the restriction that the trapdoors of generated attributes that satisfy the access control policy have not been queried before.

Guess:$b{}^{\prime }\in \{0,1\}$ is output by A.

The Schwartz–Zipple lemma [56] points out that the probability of an “unexpected collision” occurring is, at most, $O(q^2/p)$.

Theorem 3.

The ABERS scheme achieves selective security on updated ciphertext under the $(d+3)$-$MDDH$ assumption in the random oracle model.

We can see that any polynomial time adversary can not learn any information from the original ciphertext under Theorem 1. The key to proving Theorem 3 is determining whether the original ciphertext is distinguishable from the updated ciphertext.

Now let us take a look at whether the original ciphertext and the updated ciphertext generated by the same message, the attribute set, S, and the revocation list, $R{}^{\prime }$, are uniformly distributed.

The original ciphertext generated by calling $Encrypt(PP,M,W,R{}^{\prime },w)$ is

$$C{T}_{R{}^{\prime }}=(C_0,C_1,C_2,\{C_{1,i},C_{2,i}\}),$$

where $C_0=M·g_{d+3}^{\alpha ·s}$, $C_1=g_1^s$, $C_2=g_1^{\beta s}$, $C_{1,i}=H_1{\left(W_i\right)}^s$ and $C_{2,i}=P_{x,depth\left(x\right)}^s$.

The original ciphertext generated by calling $Encrypt(PP,M,W,R,w)$ is

$$C{T}_R=(C_0,C_1,C_2,\{C_{1,i},C_{2,i}\}),$$

where $C_0=M·g_{d+3}^{\alpha ·s^{*}}$, $C_1=g_1^{s^{*}}$, $C_2=g_1^{\beta s^{}}$, $C_{1,i}=H_1{\left(W_i\right)}^{s^{*}}$ and $C_{2,i}=P_{x,depth\left(x\right)}^{s^{*}}$.

The updated ciphertext generated by calling $Update(C{T}_R,R{}^{\prime })$ is

$$C{T}_{R^{{}^{″}}}=(C_0{}^{\prime },C_1{}^{\prime },C_2{}^{\prime },\{C_{1,i}{}^{\prime },C_{2,i}{}^{\prime }\}),$$

where $C_0=M·g_{d+3}^{\alpha ·s^{*}}$, $C_1=g_1^{s^{*}}$, $C_2=g_1^{\beta s^{}}$, $C_{1,i}=H_1{\left(W_i\right)}^{s^{*}}$ and $C_{2,i}=P_{x,depth\left(x\right)}^{s^{*}}$ for $\forall id\in (Cover\left(R\right)\bigcap Cover\left(R{}^{\prime }\right))$, $C_{2,i}{}^{\prime }=C_{2,i}=P_{x,depth\left(x\right)}^{s^{*}}$, and $\forall id\in (Cover\left(R{}^{\prime }\right)-Cover\left(R\right))$, $C_{2,i}{}^{\prime }=P_{x,depth\left(x\right)}^{s^{*}}$.

The original ciphertext and the updated ciphertext have the same terms, and each term is blinded by random numbers. Therefore, the original ciphertext and the updated ciphertext have the same distribution. At this point, similar to the analysis in [43], if the adversary, A, can break through our scheme, the simulator will be able to break the $(d+3)$-$MDDH$ assumption.

6. Comparison

In this section, we compare our scheme with some related schemes. We have chosen several representative solutions related to the keyword search of ciphertext [42,52,57] and direct revocation [43,57,58]. The results of the comparison are shown in

Table 1. Feature comparison of our scheme and other typical schemes ${}^{†}$.

Scheme	KS	FKS	DR	HP	CO	SO
[58]	×	×	√	×	−	$\left(\right|L|+|C|+2)\left|G\right|$
[43]	×	×	√	√	−	$\left(\right|S|+|C|+2)\left|G\right|$
[42]	√	×	×	√	$\left(2\right|S|+|Z|+1)\left|G\right|$	$\left(\right|P|+|P\left|\right|W|+2)\left|G\right|$
[52]	√	√	×	√	$\left|G\right|$	$\left(2\right|S|+5)\left|G\right|$
[57]	√	√	√	×	$\left(\right|N|+3|L|+|I\left|\right)\left|G\right|$	$\left(2\right|S|-2|R|+|W|+|M|+3)\left|G\right|$
Our scheme	√	√	√	√	$\left|G\right|$	$\left(2\right|S|+|C|+2)\left|G\right|$

${}^{†}$ The symbol √ (resp. ×) represents the corresponding feature is (resp. is not) achieved in the scheme. KS means keyword search, FKS means fast keyword search, DR means direct revocation, HP means hidden policy, CO means communication overhead and SO means storage sverhead. |S| means the number of user attributes, |Z| means the bit length of an element of $Z_p$, |G| means the bit length of an element of $G_i$, |I| means the bit length of user ID, |L| means the number of rows of the access control matrix, |P| means the number of columns of the access control structure, |C| means the cardinality of cover(R), |R| means the cardinality of a revocation list, |M| means the maximum number of revoked users and |N| means the number of keywords.

. Table 1 compares the functional differences between our schemes and related schemes from the perspective of keyword search, fast keyword search, direct revocation, hidden policy, communication overhead and storage overhead. Compared with other schemes, our scheme has better function. It is more accurate than the scheme [52]. The communication cost of the keyword trapdoor is the same, but the functioning of our scheme is greater. Compared with other schemes, the storage cost of our scheme is not very large.

Next, we compare the efficiency of the keyword search. In order to exclude other sources of interference and to make the result more accurate, we tested the schemes on the same platform, and the test results are shown in Figure 7. Figure 7 compares our scheme’s search efficiency with refs. [42,52,57]. We can see that, compared with schemes [42] and [57], the keyword search efficiency in our scheme is very high. The search time cost does not increase linearly with the number of attributes in ciphertext policies, which is not enabled in [42,57]. This is because our search scheme uses aggregated search key technology without pairing the secret key components with the corresponding ciphertext components. In the process of keyword trapdoor generation, only one linear pair operation is needed. In the process of ciphertext retrieval, by comparing whether the results of two pairs of linear pairs are equal, we can determine whether the required ciphertext exists. Although our scheme has the same efficiency in the search phase as that shown in reference [52], our scheme is more functional. From the point of view of function and efficiency, our scheme is more applicable to the practical environment.

7. Conclusions and Future Work

In this article, we have put forward a hidden policy attribute-based data sharing scheme with direct revocation and keyword search. The scheme has the following advantages. First, it uses subset covering theorem to achieve the direct revocation of attributes. After revocation, there is no need to update the private key of a non-revoked user. In order to ensure that the users who have been revoked cannot decrypt the previous ciphertext, the ciphertext is updated. In this way, some secret keys do not match some ciphertext, and users who are revoked can not decrypt the previous ciphertext. In addition, when there is a user leaving the system, we just need to send the revocation list to the cloud server and let the cloud server update the ciphertext. Then, the private key of the non-revoked user does not need to be updated. Second, we use aggregation technology to achieve the fast search of keywords. In the process of keyword trapdoor generation, only one linear pair operation is needed. In the process of ciphertext retrieval, by comparing whether the results of two pairs of linear pairs are equal, we can determine whether the required ciphertext exists. So, the keyword search time is constant and does not increase with the number of attributes. Third, the AND gate access control structure is used to achieve the hidden policy. When ciphertext is uploaded, the access control structure does not need to be uploaded. Thus, the function of the hidden policy can be achieved. In brief, when a lot of data is being shared, our solution can provide a good solution.

When a user leaves the system, the user needs to interact with the cloud server, and then, the server updates the ciphertext. This not only increases the cost of communication and computing, but the revoked user can decrypt the former ciphertext before the ciphertext is updated which is a threat to the security of the system. If there is no need to update the ciphertext, the revoked user will not be able to decrypt the ciphertext at the moment of revocation. So, in future work, we will solve the problem of how to ensure that the user can not decrypt the previous ciphertext without updating the ciphertext.