Attribute-Based Encryption with Efficient Keyword Search and User Revocation

Abstract

Ciphertext policy attribute-based encryption (CP-ABE) is a promising cryptographic technology and a key component that enable secure data sharing in a cloud environment through fine-grained access control. Since it was introduced, many interesting schemes have been proposed. However, in addition to managing data sharing through access control, a comprehensive scheme should also cater for user revocation and ciphertext queries. This is because in a cloud environment new users may join while existing users may leave the system. At the same time, given the potentially large amount of data stored in a cloud storage, user should be able to retrieve the required files efficiently in a privacy-preserving manner. To address the above issue, in this paper, we propose a practical searchable CP-ABE scheme supporting user revocation. In contrast to existing schemes that provide only single keyword query, our efficient search function provides conjunctive search, which allows user to locate a ciphertext related to a set of keywords. The computation overhead of our user revocation is at least on par with existing schemes. Besides, the security analysis indicates that the proposed scheme is secure under the decisional Bilinear Diffie-Hellman assumption. We also provide extensive experimental results to confirm the efficiency and feasibility of our proposed construction.

1 Introduction

Data sharing has been regarded as one of the most promising applications of cloud computing in current research community as well as for commercial usage. A great number of companies and individuals nowadays prefer to outsource or upload their data to the cloud to enjoy the benefits provided by cloud server [29]. However, there still exist potential risks that threaten users’ security. The key concern is data privacy when sensitive data outsourced to the third-party cloud server provider [4, 21]. This is because once the data is stored in the cloud storage, generally the user loses control of the data if no security measure prepared. The data may be leaked due to unintentional human error or the cloud storage being compromised. As a result numerous mechanisms, including proposals based on attribute-based encryption, have been proposed by researchers to prevent data leakage and make sure only legitimate users can access these data [10, 14, 18, 31].

Attribute-based encryption (ABE), which was first proposed by Sahai and Water in [23], can be considered as a promising solution to the problem described above. ABE mainly consists of ciphertext-policy ABE (CP-ABE) [2] and key-policy ABE (KP-ABE) [6]. In CP-ABE, ciphertext is associated with an access structure and user’s secret key is associated with an attribute set. Only when the attribute set related to user’s secret key satisfies the access structure hidden in the ciphertext can the user perform decryption. This is in contrast to KP-ABE, where the secret key is associated with an access structure. As a reliable method to preserve privacy of data stored in the cloud, the access structure of CP-ABE is defined by data owner (DO), which makes CP-ABE more suitable in the context of cloud data sharing [16].

1.1 Our Motivation

Although CP-ABE fits the cloud environment well in addressing the issue of data privacy, there still exist some challenges that prevent its wide adoption in commercial applications. Consider a company that creates a project consisting of a group of employees, where the related file, encrypted under an access policy, are stored in the cloud server. Employees responsible for this project are assigned with several attributes (e.g., “group G”, “project P”). Only employees with these attributes can access the data of the project. However, when one of the employees resign from the company or he moves to another group, how can we revoke his access ability? Besides, a company may have lots of projects in the cloud server. How can the staff retrieve files efficiently and safely?

One of the main solutions is to construct a user revocation mechanism for the system [33]. After revocation, the revoked users will not be able to decrypt the ciphertext anymore even if his attribute set satisfies the access structure. Collusion resistance mechanism should also be provided to prevent collusion attack launched by revoked users at the same time [9]. Besides, searching for the exact ciphertext in the cloud is not easy, especially when the number of ciphertext in the cloud server is large. Most of the existing ABE scheme assumed that the system is able to locate the correct ciphertext for data user (DU) automatically. We design and construct an efficient ciphertext search function to help data users search quickly with some keywords in the cloud server. In fact, it only needs twice bilinear pairing computation.

1.2 Our Contributions

Inspired by [25], we propose a practical ciphertext-policy attribute based encryption system, which focus on the problem of user revocation and ciphertext search. The contributions of our work are as follows:

• 1. Effective ciphertext search. We propose ciphertext (encrypted) search that cost only twice bilinear pairing computation. Specifically, when data owner (DO) upload the ciphertext to the cloud server, a set of related encrypted keywords will be attached to the ciphertext. If a data user wishes to access some of the encrypted data in the system, he should generate and send a trapdoor of the related keywords to cloud server provider (CSP). On receiving the trapdoor, CSP first checks whether this data user is authorized to access the ciphertext. Only if the data user has sufficient attributes can he access the data. Then CSP compares the trapdoor with the encrypted keywords in the ciphertext by a short bilinear pairing computation.

• 2. User revocation. We propose a new mechanism, in which the notion of version control is used to realize the function of user revocation. In our system, ciphertext and secret key are managed by a parameter called “ver”. When a data user is removed from the system, trusted authority will randomly select a new “ver” so that cloud server provider and the remaining data users can update ciphertext alone with secret key by themselves. As a result, cloud server provider do not have to manage the revocation list. If the “ver” in the access request is not the same with the one in the system, then the request will not be performed.

• 3. Collusion resistance. The proposed system is resistant to collusion attack launched by revoked data users and the remaining data users in the system. Specifically, the secret key of each data user in the system is generated according to “ver” and the identity information both, so that the secret keys will be different even if the attribute set of two users are the same.

We further prove security of our system under the decisional Bilinear Diffie-Hellman assumption. Besides, we simulate the experiment and compare the performance of our system with existing works.

1.3 Related Work

ABE provides fine-grained access control to ciphertext stored in the cloud. This means data owners only need to outsource their data to third-party cloud server providers without worrying about data management. By doing so, the cloud server providers can assist the data owner to communicate with data users. However, the separation of data and the data owner brings new problems. When the information to be shared is sensitive, data owner may have concern on data leakage. To protect their data, many schemes have been proposed to secure data against unauthorized access [11, 20]. For example, Ning et al. [17] proposed a solution to trace the malicious users who leaks their decryption keys to keep their data from leakage. On the other hand, cloud providers’ resource is not infinite, they need to make full use of their platform to provide reliable server with minimal cost. Schemes focus on outsourcing computing such as [13, 15] can greatly relief the expense of data user in the system.

The conventional solution to search over encrypted data is to download all the ciphertext in the cloud and retrieve the required data, which is inefficient and infeasible [12]. Practical schemes were then proposed. Since first introduced by Song et al. in [24], searchable encryption schemes [26, 32] have been adopted by many researchers. Xiong et al. [30] provided a searchable CP-ABE in the cloud. In their scheme, homomorphic encryption is used to realize the search function. They encrypt the message under homomorphic encryption and the key of homomorphic encryption is encrypted by CP-ABE. But the computing expense is relatively high, which brings no benefit to its application. Su et al. [25] proposed a practical searchable CP-ABE scheme, which minimized computation of search phrase. However, their scheme only focuses on the problem of keyword search. We rich our scheme with the function of user revocation. Padhya et al. [22] proposed a searchable CP-ABE, which hides ciphertext policy. Wang et al. [27] proposed a method to achieve fast keyword search on ciphertext. However, both of their computation costs in the search algorithm require at least three times of bilinear pairing operation, which is more than that of ours. [5] proposed a scheme supporting fuzzy keyword search, so that data users can get all the related ciphertext with his keywords, but it cost a lot more in search phase than our’s scheme.

User revocation is another concern for data sharing in the cloud. It is a common phenomenon to revoke a user from accessing sensitive data when he is no longer a member of the system. This means the ciphertext should be updated so that the revoked user cannot use his old secret key to decrypt the updated ciphertext anymore. In recent years, many CP-ABE scheme supporting user revocation have been proposed in the literature. Cui et al. [4] addressed this problem through disabling the search capability of revoked user. When a user should be revoked, the administrator in the system only has to update a secret value stored on the cloud server. Their scheme is efficient, but it is not clear how they classify the revoked users and non-revoked users. Padhya et al. [22] realized user revocation by adding a user revocation list to the ciphertext in the phase of encryption. But it only fits the situation when the number of system user is small. It will be complex to manage a revocation list in the cloud environment. Besides, employ an accountable authority to audit malicious operation in the system is also a smart solution to prevent the malicious attacks [19].

1.4 Organization

In Sect. 2, we state the preliminaries, including bilinear pairings, linear secret-sharing schemes, access structure, access tree and the computational assumption. Section 3 outlines the system model, definition and security model. In Sect. 4, an attribute-based encryption with efficient keyword search and user revocation is proposed. In Sect. 5, a security analysis about our scheme is given. We test the proposed scheme with an experiment in Sect. 6. Finally, Sect. 7 concludes this paper.

2 Preliminary

2.1 Bilinear Pairings

Let $\mathbb {G}$ and $\mathbb {G}_{T}$ be cyclic groups with prime order p and g is the generator of $\mathbb {G}$. A bilinear map e [8] has the following properties:

• 1. Bilinearity: For any ${u,v}\in \mathbb {G}$ and ${a,b}\in \mathbb {Z}_{p}$, $e(u^{a},v^{b})=e(u,v)^{ab}$.

• 2. Non-degeneracy: There exists ${u,v}\in \mathbb {G}$ such that $e(u,v)\ne 1$.

• 3. Computability: For all ${u,v}\in \mathbb {G}$, there is an efficient computation e(u, v).

2.2 Linear Secret-Sharing Schemes (LSSS)

Let $p$ be a prime and $\mathbb {U}$ be the attribute universe. A secret-sharing scheme $\prod$ with domain of secrets $\mathbb {Z}_{p}$ realizing access structures on $\mathbb {U}$ is linear over $\mathbb {Z}_{p}$ if:

• 1. The shares of a secret $p \in \mathbb {Z}_{p}$ for each attribute form a vector over $\mathbb {Z}_{p}$.

• 2. For each access structure $\mathbb {A}$ on $\mathbb {U}$, there exists a matrix $\mathbb {M}\in \mathbb {Z}^{l \times n }_{p}$, called the share-generating matrix, and a function $\rho$, that labels the rows of $\mathbb {M}$ with attributes from $\mathbb {U}$ (details can be found in [1]), which satisfy the following rules:

  During the generation of the shares, we consider the column vector $\mathbf {v} =(s , r _{2}, r _{3}, \dots , r _{n})^{\perp }$, where $s \in \mathbb {Z}_{p}$ is the secret to be shared and $r _{2}, \dots , r _{n}\in \mathbb {Z}_{p}$ are randomly chosen. Then the vector of $l$ shares of the secret $s$ according to $\prod$ is equal to $\mathbb {M}\mathbf {v}\in \mathbb {Z}^{l \times 1 }_{p}$. The share $(\mathbb {M}\mathbf {v})_{j }$ where j “belongs” to attribute $\rho (j )$.

  Generally speaking, access structure $\mathbb {A}$ will be represented by the pair $(\mathbb {M}, \rho ).$

2.3 Access Structure

Let $\{A_{1},A_{2}, \ldots , A_{n}\}$ be a group of attributes. For $\forall B,C$, if $B\in A$ and $B\subseteq C$, then $C\in A$, we say that $A\subseteq 2^{\{A_{1},A_{2}, \ldots , A_{n}\}}$ is monotone. An access structure contains a set A of non-empty subsets of $\{A_{1},A_{2}, \ldots , A_{n}\}$. Elements in A are named the authorized elements, and the other elements are referred to as unauthorized elements.

2.4 Access Tree

Let $\mathcal {T}$ represents an access tree and x be a node of $\mathcal {T}$. Every non-leaf node x of $\mathcal {T}$ denotes a threshold gate, which is stated by the number of its children $num_{x}$ and its threshold $l_{x}$, where $l_{x}\in [1,num_{x}]$. The threshold gate means an OR gate when $l_{x}=1$. It means an AND gate when $l_{x}=num_{x}$. Each leaf node x of T is stated by an attribute and a threshold $l_{x}=1$.

In the access tree, some functions are defined to facilitate working with $\mathcal {T}$. We depict the parent for the node x of the tree by parent(x). The attribute associate with the leaf node x of the tree is represented by function att(x). We use 1 to $num_{x}$ to define the order of every node in the access tree $\mathcal {T}$. The function index(x) denotes a number associated with the node x, where the index values are uniquely assigned to nodes of the access policy for a given ciphertext in an arbitrary manner.

Satisfying an Access Tree: Let $\mathcal {T}$ be an access tree with root R, and $\mathcal {T}_{x}$ represents the subtree rooted at the node x in $\mathcal {T}$. Namely, $\mathcal {T}$ can be replaced by $\mathcal {T}_{R}$. $\mathcal {T}_{x}(S)=1$ is used to denote the situation that attribute set S satisfies $\mathcal {T}_{x}$. $\mathcal {T}_{x}(S)$ is evaluated recursively as follows: if x is a non-leaf node, we compute $\mathcal {T}_{x'}(S)$ for all children $x'$ in node x. $\mathcal {T}_{x}(S)$ outputs 1 if and only if at least $l_{x}$ children return 1. If x is a leaf node, then $\mathcal {T}_{x}(S)$ outputs 1 if and only if $att(x)\in S$.

2.5 The Decisional Bilinear Diffie-Hellman Assumption

A challenger selects a group G with prime order p according to the security parameter. Let g be a generator of G and $a, b, s\in Z_{p}$ be selected at random. If the challenger gives an adversary $(g, g^{a}, g^{b}, g^{s})$, it must be difficult for the adversary to distinguish a valid tuple $e(g, g)^{abs}\in G_{T}$ from a random element $R\in G_{T}$. An algorithm $\mathcal {B}$ that outputs $\vartheta \in \{0, 1\}$ has advantage $\varepsilon$ in solving DBDH in G if:

$$\begin{aligned} |Pr[\mathcal {B}(g,g^{a},g^{b},g^{s},Z=e(g,g)^{abs})=0]-Pr[\mathcal {B}(g,g^{a},g^{b},g^{s},Z=R)=0]|\geqslant \varepsilon . \end{aligned}$$

Definition 1

The DBDH assumption holds if all poly-time algorithms have at most a negligible advantage in solving DHDH problem.

3 An Attribute-Based Encryption System with Efficient Keyword Search

3.1 System Model

As illustrated in Fig. 1, in the proposed scheme, there exists four types of entities: a trusted authority (TA), a cloud server provider (CSP), data user (DU) and data owner (DO).

Fig. 1.

System model of attribute-based encryption with efficient keyword search and user revocation

TA: It is the only trusted entity in the system. It is responsible for not just generating system parameters, but also attribute authorizing and secret key issuing for the new enrolled users.

CSP: t is the manager of cloud server in the system. It provides the service of data storage, keyword search and ciphertext update. It is also a semi-trusted entity in the system, which means it will collect users’ information as much as possible.

DU: Data user is a kind of user in the system. They would like to access the encrypted data in the cloud server. According to attribute-based encryption scheme, a data user is able to access the encrypted data, if and only if his attribute set satisfies the access tree defined by data owner.

DO: Data owner is another kind of user in the system. They would like to share their data in the cloud to some qualified people. Before they upload their data to the cloud server provider, data owners usually encrypt their data with an access policy defined by themselves. Besides, some encrypted keywords related to the data will also be attached to the ciphertext for the easement of searching.

3.2 Definition

Attribute-based encryption with efficient keyword search and user revocation is defined as follow:

• $\mathbf{Setup}(1^{\lambda },L)\rightarrow (PK,MSK)$: This is an initialization algorithm. On input a security parameter $\lambda$ and an attribute universe $L=\{a_{1},a_{2},\ldots ,a_{m}\}$, the algorithm outputs the public key PK and the master key MSK.

• $\mathbf{KeyGen}(MSK,UID,S)\rightarrow SK_{0}$: This is a secret key generation algorithm. On input MSK, user identity UID and an attribute set S that depicts the key, the algorithm outputs a secret key SK.

• The encryption phrase consists of two parts. Firstly, data owner randomly selects a symmetric key ck to encrypt the data by employing a symmetric encryption algorithm, the encrypted data is denoted by $E_{ck}(M)$. Secondly, data owner encrypts ck with the following algorithms: $\mathbf{Encryption}(PK,ck,\mathcal {T})\rightarrow CT$: This is a encryption algorithm. On input the PK, symmetric key ck and an access tree $\mathcal {T}$, the algorithm outputs ciphertext CT which will be delivered to cloud server provider.

• $\mathbf{Update}(PK,v_{ver})\rightarrow (v_{ver+1},Re-Key_{ver\rightarrow ver+1})$: This is an update algorithm. On input PK, and current version number $v_{ver}$, the algorithm outputs $v_{ver+1}$ and re-encryption key $Re-Key_{ver\rightarrow ver+1}$. Moreover, CSP sends a $UP_{ver}$ to users who still in the system so that they can update their secret key.

• $\mathbf{User\_update}(SK_{ver},UP_{ver})\rightarrow SK_{ver+1}$: This is an user update algorithm. Once DU receives the $UP_{ver}$ from TA then he can update his secret key. The algorithm takes the old secret key $SK_{ver}$ and update parameters $UP_{ver}$ as input, and outputs new secret key $SK_{ver+1}$.

• $\mathbf{Re}\text {-}{} \mathbf{Encryption}(CT_{ver},Re-Key_{ver\rightarrow ver+1})\rightarrow CT_{ver+1}$: This is a re-encryption algorithm. On input the old version ciphertext $CT_{ver}$ and $Re-Key_{ver\rightarrow ver+1}$, the algorithm outputs the updated ciphertext $CT_{ver+1}$. Besides, in order to facilitate the ciphertext search, DO encrypts several keywords and attaches them to the ciphertext.

• $\mathbf{KW\_Encryption}(PK,KW)\rightarrow CT_{W}$: This is a keyword encryption algorithm. On input PK and a set of keywords selected by data owner, the algorithm outputs the encrypted keywords $CT_{W}$.

• $\mathbf{Trapdoor}(SK_{ver},SKW)\rightarrow trapdoor$: This is a trapdoor generation algorithm. On input data user’s secret key $SK_{ver}$ and the keywords SKW that need to be search, the algorithm (run by data user) outputs the encrypted keywords trapdoor.

• $\mathbf{Search}(CT_{W},trapdoor)\rightarrow CT_{ver}$: This is a search algorithm. On input the $CT_{W}$ and trapdoor, the algorithm outputs the matched ciphertext $CT_{ver}$.

• $\mathbf{Decryption}(CT_{ver},SK_{ver},PK)\rightarrow ck$: This is a decryption algorithm. On input $CT_{ver}$, $SK_{ver}$ and PK, the algorithm outputs the symmetric key ck. Then data owner can further decrypt the $E_{ck}(m)$ by ck.

3.3 Chosen Plaintext Attack (CPA) Security

The proposed attribute-based encryption with efficient keyword search and user revocation is chosen-plaintext attack secure, which can be defined by the security game below.

• Init: A probabilistic polynomial time (PPT) adversary $\mathcal {A}$ submits the challenge access policy $\mathcal {\mathcal {T}^{*}}$ and version number $ver^{*}$ to the challenger $\mathcal {B}$.

• Setup: $\mathcal {B}$ runs the Setup() algorithm to generate public key PK. $\mathcal {B}$ randomly selects $v_{0}$ as version secret key. Then $\mathcal {B}$ runs the Update() algorithm to update the version secret key from 0 to $ver^{*}$ and generate the corresponding $UP_{ver+1},ver\in [0,ver-1]$. Finally, $\mathcal {B}$ sends the PK and $\{UP_{ver+1}\}_{0\leqslant ver\leqslant ver^{*}-1}$ to $\mathcal {A}$.

• Phrase 1: Adversary $\mathcal {A}$ selects a UID and adaptively submits the attribute set S to B to query the secret key $SK_{0}$ about S. The restriction is that all queried attribute sets should not satisfy $\mathcal {T}^{*}$. Then, the adversary $\mathcal {A}$ can update $SK_{0}$ to $SK_{ver^{*}}$ according to the $\{UP_{ver+1}\}_{0\leqslant ver\leqslant ver^{*}-1}$.

• Challenge: The adversary $\mathcal {A}$ submits the equal length message $M_{0}$ and $M_{1}$ to challenger $\mathcal {B}$. After receiving the message, $\mathcal {B}$ randomly chooses c from $\{0,1\}$ and runs Encryption() to generate the ciphertext $CT_{b}$. Certainly, $\mathcal {B}$ should run the $Re-Encryption()$ algorithm to get the version of $ver^{*}$ of the challenger ciphertext $CT_{c}$.

• Phrase 2: $\mathcal {A}$ launches queries as phrase 1 and $\mathcal {B}$ answers as phrase 1.

• Guess: When the query phrase is over, $\mathcal {A}$ outputs its guess $c^{'}\in \{0,1\}$. $\mathcal {A}$ wins the game if $c^{'}=c$ with the advantage of $Adv^{\mathcal {A}}=|Pr[c=c^{'}]-1/2|$.

Definition 2

An attribute-based encryption with effective keyword search and user revocation scheme is CPA-secure if there exist no polynomial time adversaries can win this security game with a non-negligible advantage.

3.4 Chosen-Keyword Attack (CKA) Security

The proposed attribute-based encryption with efficient keyword search and user revocation is chosen-keyword attack secure, which can be defined by the security game below.

• Init: A probabilistic polynomial time adversary $\mathcal {A}$ submits t keywords $\{W_{1},W_{2},\ldots ,W_{t}\}$ and to the challenger $\mathcal {B}$.

• Setup: $\mathcal {B}$ runs the Setup() algorithm to generate public key PK. $\mathcal {B}$ randomly selects $v_{0}$ as version secret key. Then $\mathcal {B}$ sends the PK to $\mathcal {A}$.

• Phrase 1: Adversary $\mathcal {A}$ selects a set of keywords SKW and submits it to B to query the Trapdoor about SKW. The restriction is that all queried keywords should not contain $W_{1}$.

• Challenge: $\mathcal {B}$ randomly selects c from $\{0,1\}$ and runs $KW\_Encryption()$ algorithm to generate the encrypted keywords $CT_{c}$.

• Phrase 2: $\mathcal {A}$ launches queries as phrase 1 and $\mathcal {B}$ answers as phrase 1.

• Guess: When the query phrase is over, $\mathcal {A}$ outputs its guess $c^{'}\in \{0,1\}$. And $\mathcal {A}$ wins the game if $c^{'}=c$ with the advantage of $Adv^{\mathcal {A}}=|Pr[c=c^{'}]-1/2|$.

Definition 3

An attribute-based encryption with effective keyword search and user revocation scheme is CKA-secure if there exist no polynomial time adversaries can win this security game with a non-negligible advantage.

4 Attribute-Based Encryption with Efficient Keyword Search and User Revocation

For simplicity, we suppose that there are m attributes denoted by $L=\{a_{0},a_{1},\ldots ,a_{m}\}$ in the system. Let $e:G\times G\rightarrow G_{T}$ be a bilinear map, and G be a bilinear group with prime order p and generator g. Let $H:(0,1)^{*}\rightarrow G$ be a security hash function, which maps any attribute to a random member of G. For any $i\in Z_{p}$, the Lagrange coefficient is $\varDelta _{i,L}(x)=\Pi _{l\in L,l\ne i}\frac{x-l}{i-l}$. The detailed construction are as follows:

• $\mathbf{Setup}(1^{\lambda },L)\rightarrow (PK,MSK)$: The algorithm runs by TA. Its inputs are a security parameter $\lambda$ and the universe attribute set L. This algorithm randomly selects a generator $g\in G$ and $\alpha , \beta , \gamma \in Z^{*}_{p}$. Then, TA calculates $g^{\alpha },e(g,g)^{\beta }$ and $g^{\gamma }$. For each attribute $j\in L$, TA chooses a random $v_{j}\in Z^{*}_{p}$ and calculates $A_{j}=H(j)^{v_{j}}$. TA publishes the public key as $PK=\{G,g,g^{\alpha },e(g,g)^{\beta },g^{\gamma },A_{j}\}$ and keeps the master key as $MSK=\{\alpha ,\beta ,v_{j}\}$ to its own.

• $\mathbf{KeyGen}(MSK,UID,S)\rightarrow SK_{0}$: When a new user wants to join in the system, he should submit his attribute set $S=\{a_{1},a_{2},\ldots ,a_{n}\}$ to TA so that he can get the secret key to decrypt and search. In our scheme, we use ver to present the currently version number. When user revocation occurs, the secret key will be updated to a new version. Specifically, TA randomly selects $v_{0},t,r_{1}\in Z^{*}_{p}$. Then TA computes $D=(g\times H(UID)^{\alpha })^{v_{ver}t}$, for $\forall j\in S:D_{j}=H(UID)^{v_{ver}t}\times H(j)^{v_{j}t}$, and $D^{'}_{j}=H(j)^{\alpha t}$, so that $SK={D,\forall j\in S:D_{j},D^{'}_{j}}$. Then it sends the secret key as t, SK to DU secretly. After that, TA computes $\widehat{S_{a}}=g^{r_{1}}$ and $\widehat{S_{b}}=(g^{\gamma }H(j)^{\sum _{j\in S}v_{j}})^{r_{1}}$ as the key to search for DU. Finally, TA computes $\{UID,H(UID)^{r}\}$ in case that DU need to update his secret key.

• The encryption algorithm consists of two steps.

  Symmetric encryption: As symmetric encryption is more efficient than asymmetric encryption, we decide to encrypt the data M by a symmetric algorithm first. Let the symmetric key be ck, and the symmetric ciphertext be $E_{ck}(M)$.

  $\mathbf{Encryption}(PK,ck,\mathcal {T})\rightarrow CT$: DO defines an access tree $\mathcal {T}$ and encrypts ck by running the encryption algorithm to output the $CT^{'}$. Specifically, for each node x in the access tree $\mathcal {T}$, the DO first selects a random polynomial $q_{x}$ with degree $d_{x}=k_{x}-1$, where $k_{x}$ is the threshold value in the node x. Beginning from the root node R, these polynomials are selected in a top-down manner. The DO randomly chooses $d_{R}$ other points of $q_{R}$ to completely define them after selecting a random number $s\in Z^{*}_{p}$, and setting $q_{R}(0)=s$. For any other node x, it sets $q_{x}(0)=q_{parent(x)}(index(x))$ and selects $d_{x}$ other points to completely define them. Let the set of leaf nodes in the access tree $\mathcal {T}$ be Y and the ciphertext $CT^{'}$ is as follows:

  $$\begin{aligned} CT^{'}=\left\{ \begin{aligned} \mathcal {T},\widetilde{C}=ck\cdot e(g,g)^{s(\beta +v_{ver})},C=g^{s},C^{'}=g^{\alpha s},\\ \forall y\in Y:C_{y}=g^{\alpha q_{y}(0)},C^{'}_{y}=g^{q_{y}(0)v_{att(y)}} \end{aligned} \right\} \end{aligned}$$

• $\mathbf{Update}(PK,v_{ver})\rightarrow \{v_{ver+1},Re-Key_{ver\rightarrow ver+1}\}$: Considering the situation of user revocation, TA performs the update algorithm to generate the new version secret key $v_{ver+1}$, and the re-encryption key $Re-Key_{ver\rightarrow ver+1}$ so that the updated ciphertext would not be accessed by revoked user. Besides, for every DU in the system, TA produces a secret key update component according their identity. So that they can update their secret key after the re-encryption. TA selects a $v_{ver+1}$ as the new version secret key. Then TA computes $Re-Key_{ver\rightarrow ver+1}=g^{(v_{ver+1}-v_{ver})/\alpha }$. For each user in the system, TA generates a secret key update component by computing $H(UID)^{v_{ver+1}-v_{ver}}$ and $(g\times H(UID)^{\alpha })^{v_{ver+1}-v_{ver}}$. TA sends the $Re-Key_{ver\rightarrow ver+1}$ to CSP to perform the re-encryption algorithm, and distributes the $UP_{ver+1}=\{UID,H(UID)^{v_{ver+1}-v_{ver}},(g\times H(UID)^{\alpha })^{v_{ver+1}-v_{ver}}\}$ to corresponding DU to update their secret key.

• $\mathbf{User\_update}(SK_{ver},UP_{ver})\rightarrow SK_{ver+1}$: Upon receiving the $UP_{ver}$ from TA, DU computes $D=D\times (g\times H(UID)^{\alpha })^{t(v_{ver+1}-v_{ver})}=(g\times H(UID)^{\alpha })^{tv_{ver+1}}$. $\forall j\in S:D_{j}=D_{j}\times H(UID)^{t(v_{ver+1}-v_{ver})}=H(UID)^{v_{ver+1}t}\times H(j)^{v_{j}t}$. Then the updated secret key is as follow:

  $$\begin{aligned} SK=\{(f\times H(UID)^{\alpha })^{v_{ver+1}t},\forall j\in S:H(UID)^{v_{ver+1}t},H(j)^{\alpha t}\} \end{aligned}$$

• $\mathbf{Re}\text {-}{} \mathbf{Encryption}(CT_{ver},Re-Key_{ver\rightarrow ver+1})\rightarrow CT_{ver+1}$: CSP is responsible for not only keeping the encrypted data, but also updating them when user revocation happens. The computing process is as follow:

  $$\begin{aligned} \begin{aligned} \widetilde{C}&=\widetilde{C}\times Re-Key_{ver\rightarrow ver+1}\\&=ck\cdot e(g,g)^{s(\beta +v_{ver+1})} \end{aligned} \end{aligned}$$

  So that the revoked user will not be able to access again.

• $\mathbf{KW\_Encryption}(PK,KW)\rightarrow CT_{W}$: Let $KW=\{kw_{1},kw_{2},\ldots ,kw_{k}\}$ denote the keywords related to the data. DO have to attach the encrypted keywords to the ciphertext formed in Encryption algorithm. Then DO randomly chooses a $u\in Z^{*}_{p}$ and prepares an attribute set $S^{'}$ that contains all the attributes in the access tree. DO computes $\widehat{C_{a}}=g^{\frac{u}{H(kw_{1}||kw_{2}||\ldots ||kw_{k})}},\widehat{C_{b}}=(g^{\gamma }\prod _{j\in S^{'}}A_{j})^{u}$ and $CT_{kw}=\{\widehat{C_{a}},\widehat{C_{b}}\}$. Finally, DO sends the complete ciphertext $CT=\{E_{ck}(M),CT^{'},CT_{kw}\}$ to the CSP.

• $\mathbf{Trapdoor}(SK_{ver},SKW)\rightarrow trapdoor$: When DU wants to search the data in the CSP, he first generates a trapdoor about the keywords he wants to search. Let $SKW=\{skw_{1},skw_{2},\ldots ,skw_{k}\}$ denotes the keywords DU chooses. DU randomly selects $x\in Z^{*}_{p}$. Then DU computes $T_{b}=\widehat{S}_{b}^{x}$, $T_{a}=\widehat{S_{a}}^{\frac{x}{H(skw_{1}||skw_{2}||\ldots ||skw{k})}}$. Finally, DU sends the $trapdoor=\{T_{a},T_{b}\}$ to CSP to search the data he needs.

• Search: Once the trapdoor is received, CSP conducts the search algorithm to check if the authorization of the user’s keywords satisfies the keywords in the ciphertext. By computing $e(\widehat{C_{a}},T_{b})$ and $e(\widehat{C_{b}},T_{a})$, the ciphertext wanted will be send to DU later if the equation holds.

• $\mathbf{Decryption}(CT_{ver},SK_{ver},PK)\rightarrow ck$: When DU gets the wanted ciphertext, he can decryption the data by the symmetric key ck encrypted in the $CT^{'}$. The detailed process is as follow: The decryption procedure is defined as a recursive algorithm $DecryptNode(CT^{'}$ , SK, x), where x is a node in the access tree $\mathcal {T}$. If x is a leaf node. Let $j=att(x)$. If $j\notin S$, then $DecryptNode(CT^{'},SK,x)=null$. But if $j\in S$, then:

  $$\begin{aligned} \begin{aligned} DecryptNode(ct^{'},SK,x)&=\frac{e(D_{j},C_{y})}{e(D^{'}_{j},C^{'}_{y})}\\&=\frac{e(H(UID)^{v_{ver}t}\times H(j)^{v_{j}t},g^{\alpha q_{x}(0)})}{e(H(j)^{\alpha t},g^{q_{x}(0)v_{att(x)}})}\\&=\frac{e(H(UID),g)^{\alpha tv_{ver}q_{x}(0)}e(H(j),g)^{\alpha tv_{j}q_{x}(0)}}{e(H(j),g)^{\alpha tv_{j}q_{x}(0)}}\\&=e(H(UID),g)^{\alpha tv_{ver}q_{x}(0)} \end{aligned} \end{aligned}$$

  If x is a non-leaf node, the recursive algorithm $DecryptNode(CT^{'},SK,x)$ is defined as: for all nodes z that are children of x, it performs $F_{z}=DecryptNode(CT^{'},Sk,z)$. Let $S_{x}$ be an arbitrary $K_{x}$ sized child nodes set $\{z\}$, then $F_{z}\ne null$. If not, $F_{z}$ is calculated as:

  $$\begin{aligned} \begin{aligned} F_{z}&=\prod _{Z\in S_{x}}F^{\varDelta _{j,S^{'}_{x}(0)}}_{Z}\\&=\prod _{Z\in S_{x}}(e(H(UID),g)^{\alpha tv_{ver}q_{z}(0)})^{\varDelta _{j,S^{'}_{x}(0)}}\\&=\prod _{Z\in S_{x}}(e(H(UID),g)^{\alpha tv_{ver}q_{parent(z)}(index(z))})^{\varDelta _{j,S^{'}_{x}(0)}}\\&=\prod _{Z\in S_{x}}(e(H(UID),g)^{\alpha tv_{ver}q_{x}(j)})^{\varDelta _{j,S^{'}_{x}(0)}}\\&=e(H(UID),g)^{\alpha tv_{ver}q_{x}(0)} \end{aligned} \end{aligned}$$

  where $j=index(z)$ and $S^{'}_{x}=\{index(x):z\in S_{x}\}$ If DU’s attribute set S satisfies the access tree $\mathcal {T}$, the decryption algorithm can be called from the root node R of $\mathcal {T}$. And the result is as follow:

  $$\begin{aligned} \begin{aligned} F_{R}&=DecryptNoode(CT^{'},SK,R)\\&=e(H(UID),g)^{\alpha tv_{ver}q_{R}(0)}\\&=e(H(UID),g)^{\alpha tv_{ver}s} \end{aligned} \end{aligned}$$

  Compute $D^{'}=D^{1/t}g^{\beta }=g^{\beta }g^{v_{ver}}H(UID)^{\alpha v_{ver}}$, $F^{'}_{R}=F^{1/t}_{R}=e(H(UID),g)^{\alpha v_{ver}s}$. Then Compute:

  $$\begin{aligned} \begin{aligned} \frac{\widetilde{C}\cdot F^{'}{R}}{e(D^{'},C)}&=\frac{ck\cdot e(g,g)^{s(\beta +v_{ver})}e(H(UID),g)^{\alpha v_{ver}s}}{e(g^{\beta }g^{v_{ver}H(UID)^{\alpha v_{ver}}},g^{s})}\\&=\frac{ck\cdot e(g,g)^{s(\beta +v_{ver})}e(H(UID),g)^{\alpha v_{ver}s}}{e(g,g)^{s(\beta +v_{ver})}e(H(UID),g)^{\alpha v_{ver}s}}\\&=ck \end{aligned} \end{aligned}$$

  $E_{ck}(M)$ can be decrypted with ck by applying the symmetric decryption algorithm.

5 Security Analysis

5.1 Chosen Plaintext Attack Security

Theorem 1

If there is a PPT adversary $\mathcal {A}$ that can break the scheme with non-negligible advantage $\varepsilon >0$, then there exists a PPT algorithm $\mathcal {B}$ that can distinguish a DBDH tuple from a random tuple with the advantage of $\varepsilon /2$.

Proof.  We can construct an algorithm $\mathcal {B}$ that breaks DBDH assumption with the advantage $\varepsilon /2$. Namely, $\mathcal {B}$ can decide if $Z=e(g,g)^{\theta }$ according the tuple $\langle g,g^{a},g^{b},g^{c},Z=e(g,g)^{\theta }\rangle$. Let $G,G_{T}$ be bilinear groups of prime order p with generator g and $e:G\times G\rightarrow G_{T}$. $\mathcal {B}$ randomly select $a,b,s\in Z^{*}_{p}$ and an random element $E\in G_{T}$.

• Init: $\mathcal {A}$ submits a challenge access tree $\mathcal {T}^{*}$ and version number $ver^{*}$ to the challenger $\mathcal {B}$.

• Setup: $\mathcal {B}$ randomly selects $\alpha ,\beta ,\gamma ,v_{0}$ where $\beta =\beta ^{'}+ab$, then $\mathcal {B}$ calculates $g^{\alpha },g^{\gamma }$ and $e(g,g)^{\beta }=e(g,g)^{\beta ^{'}+ab}$. For each attribute $j\in L$, TA chooses a random $v_{j}\in Z^{*}_{p}$ and calculates $A_{j}=H(j)^{v_{j}}$. Finally, $\mathcal {B}$ sends the public key $PK=\{G_{0},g,g^{\alpha },e(g,g)^{\beta },g^{\gamma },A_{j}\}$ to $\mathcal {A}$.

• Phase 1: In this phrase, $\mathcal {A}$ can launch two types of query: secret key query and update query. In secret key query, $\mathcal {A}$ submits an UID and an attribute set $S\in L$ which do not satisfy the access tree to get the secret key SK from $\mathcal {B}$. When $\mathcal {B}$ receives the query, it randomly selects $t,r_{1}\in Z^{*}_{p}$ and computes $D=(g\times H(UID)^{\alpha })^{v_{0}t}$,$D_{j}=H(UID)^{v_{0}t}\times H(j)^{v_{j}t}$,$D^{'}_{j}=H(j)^{\alpha t}$ for $\forall j\in S$. $\mathcal {B}$ sends the secret key $SK=\{D,\forall j\in S:D_{j},D^{'}_{j}\}$ to $\mathcal {A}$. In order to update SK to the version of $ver^{*}$, $\mathcal {A}$ needs to perform the update query. Then $\mathcal {B}$ sends the $\{UP_{ver+1}\}_{0\le ver\le ver^{*}-1}$ to $\mathcal {A}$, so that $\mathcal {A}$ can compute $D=D\times (g\times H(UID)^{\alpha })^{t(v_{ver+1}-v_{ver})}$ and $\forall j\in S:D_{j}\times H(UID)^{t(v_{ver+1}-v_{ver})}=H(UID)^{v_{ver+1}t}\times H(j)^{v_{j}t}$. And the final $SK=\{(g\times H(UID)^{\alpha })^{v_{ver^{*}}t},\forall j\in S:H(UID)^{v_{ver^{*}}t}\times H(j)^{v_{j}t},H(j)^{\alpha t}\}$.

• Challenge: $\mathcal {A}$ submits two equal length message $M_{0}$ and $M_{1}$ to challenger $\mathcal {B}$. After receiving the message, $\mathcal {B}$ randomly chooses c from $\{0,1\}$ and runs Encryption() to generate the ciphertext $CT_{c}$. If $c=0$, then $Z=E$. Otherwise, $\mathcal {B}$ computes $\widetilde{C}=M_{c}\cdot e(g,g)^{s(\beta +v_{ver})}=M_{c}\cdot e(g,g)^{s(\beta ^{'}+v_{ver})},C=g^{s},C^{'}=g^{\alpha s}$ then $\mathcal {B}$ performs as follow. For each node x in the access tree $\mathcal {T}^{*}$, $\mathcal {B}$ first selects a random polynomial $q_{x}$ with degree $d_{x}=k_{x}-1$, where $k_{x}$ is the threshold value in the node x. Beginning from the root node R, these polynomials are select in a top-down manner. $\mathcal {B}$ randomly chooses $d_{R}$ other points of $q_{R}$ to completely define them, and then set $q_{R}(0)=s$. For any other node x, it sets $q_{x}(0)=q_{parent(x)}index(x)$, then selects $d_{x}$ other points to completely define them. Let the set of leaf nodes in the access tree $\mathcal {T}^{*}$ be Y.

• Phase 2: $\mathcal {A}$ launches queries as phrase 1 and $\mathcal {B}$ answers as phrase 1 too.

• Guess: $\mathcal {A}$ outputs its guess $c^{'}\in \{0,1\}$. If $c^{'}=c$, then $\mathcal {B}$ outputs 0, which means that $Z=e(g,g)^{abs}$; otherwise, $\mathcal {B}$ outputs 1 means that $Z=E$. If $Z=e(g,g)^{abs}$, $CT^{*}$ is a legal ciphertext and $\mathcal {A}'$s advantage is $\varepsilon$. Thus:

  $$\begin{aligned} Pr[\mathcal {B}(g,g^{a},g^{b},Z=e(g,g)^{abs})=0]=1/2+\varepsilon . \end{aligned}$$

  If $Z=E$, then the $CT^{'}$ is invalid and:

  $$\begin{aligned} Pr[\mathcal {B}(g,g^{a},g^{b},Z=E=0]=1/2. \end{aligned}$$

  At last, the advantage of $\mathcal {A}$ is:

  $$\begin{aligned} \frac{1}{2}Pr\left[ \mathcal {B}\left( g,g^{a},g^{b},Z\!=\!e(g,g)^{abs}\right) \!=\!0\right] + \frac{1}{2}Pr\left[ \mathcal {B}\left( g,g^{a},g^{b},Z=E\right) =0\right] -\frac{1}{2}\!=\!\frac{\varepsilon }{2}. \end{aligned}$$

5.2 Chosen-Keyword Attack Security

Theorem 2

If there is a PPT adversary $\mathcal {A}$ that can break the scheme with non-negligible advantage $\varepsilon >0$, then there exists a PPT algorithm $\mathcal {B}$ that can distinguish a DBDH tuple from a random tuple with the advantage of $\varepsilon /2$.

Proof.  We can construct an algorithm $\mathcal {B}$ that breaks DBDH assumption with the advantage $\varepsilon /2$. Namely, $\mathcal {B}$ can decide if $Z=e(g,g)^{\theta }$ according the tuple $\langle g,g^{a},g^{b},g^{c},Z=e(g,g)^{\theta }\rangle$. Let $G,G_{T}$ be bilinear groups of prime order p with generator g and $e:G\times G\rightarrow G_{T}$. $\mathcal {B}$ randomly selects $u,v\in Z^{*}_{p}$ and two random element $h_{1},h_{2}\in G$.

• Init: A probabilistic polynomial time adversary $\mathcal {A}$ submits t keywords $\{W_{1}, W_{2}, \ldots , W_{t}\}$ to the challenger $\mathcal {B}$.

• Setup: $\mathcal {B}$ randomly selects $\alpha ,\beta ,\gamma$, then $\mathcal {B}$ calculates $g^{\alpha },g^{\gamma }$ and $e(g,g)^{\beta }$. For each attribute $j\in L$, TA chooses a random $v_{j}\in Z^{*}_{p}$ and calculates $A_{j}=H(j)^{v_{j}}$. Finally, $\mathcal {B}$ sends the public key $PK=\{G_{0},g,g^{\alpha },e(g,g)^{\beta },g^{\gamma },A_{j}\}$ to $\mathcal {A}$.

• Phrase 1: Adversary $\mathcal {A}$ submits a set of keywords SKW, where $\{W_{1},W_{2}\}\notin SKW$, to $\mathcal {B}$ to get the Trapdoor. On receiving the query, $\mathcal {B}$ computes $T_{a}=g^{\frac{v}{H(skw_{1}||skw_{2}||\ldots ||skw{k})}}$, $T_{b}=(g^{\gamma }H(j)^{\sum _{j\in S}v_{j}})^{v}$. Finally, $\mathcal {B}$ sends the $trapdoor = \{T_{a}, T_{b}\}$ to Adversary $\mathcal {A}$.

• Challenge: $\mathcal {B}$ randomly selects c from $\{0,1\}$ and runs $KW\_Encryption()$ algorithm to generate the encrypted keywords $CT_{c}$. If $c=0$, $\mathcal {B}$ randomly selects $h_{1}, h_{2}\in G$ and let $\widehat{C_{a}}=h_{1}, \widehat{C_{b}}=h_{2}$. Otherwise, it prepares an attribute set $S^{'}$ that contains all the attributes in the access tree. $\mathcal {B}$ computes $\widehat{C_{a}}=g^{\frac{u}{H(kw_{1}||kw_{2}||\ldots ||kw_{k})}},\widehat{C_{b}}=(g^{\gamma }\prod _{j\in S^{'}}A_{j})^{u}$. Finally, $\mathcal {B}$ sends the encryption keywords $CT_{c}=\{\widehat{C_{a}},\widehat{C_{b}}\}$ to the $\mathcal {A}$.

• Phrase 2: $\mathcal {A}$ launches queries as phrase 1 and $\mathcal {B}$ answers as phrase 1.

• Guess: $\mathcal {A}$ outputs its guess $c^{'}\in \{0,1\}$. If $c^{'}=c$, then $\mathcal {B}$ outputs 1, which means that $\widehat{C_{a}}=g^{\frac{u}{H(kw_{1}||kw_{2}||\ldots ||kw_{k})}},\widehat{C_{b}}=(g^{\gamma }\prod _{j\in S^{'}}A_{j})^{u}$. Let $v=bc, \frac{u}{H(kw_{1}||kw_{2}||\ldots ||kw_{k})}=a$ and $Z=e(\widehat{C_{a}}, T_{b})$. Otherwise, $\mathcal {B}$ outputs 0 means that $\widehat{C_{a}}=h_{1}, \widehat{C_{b}}=h_{2}$, $Z=e(h_{1},T_{b})$.

  If $\widehat{C_{a}}=g^{\frac{u}{H(kw_{1}||kw_{2}||\ldots ||kw_{k})}},\widehat{C_{b}}=(g^{\gamma }\prod _{j\in S^{'}}A_{j})^{u}$, $CT_{c}$ is a legal encrypted keyword and $\mathcal {A}'$s advantage is $\varepsilon$. Thus:

  $$\begin{aligned} Pr[\mathcal {B}(g,\widehat{C_{b}},T_{a},Z)=0]=1/2+\varepsilon . \end{aligned}$$

  If $\widehat{C_{a}}=h_{1}, \widehat{C_{b}}=h_{2}$, then the $CT_{b}$ is invalid and:

  $$\begin{aligned} Pr[\mathcal {B}(g,\widehat{C_{b}},T_{a},Z)=0]=1/2. \end{aligned}$$

  At last, the advantage of $\mathcal {A}$ is:

  $$\begin{aligned} \frac{1}{2}Pr\left[ \mathcal {B}\left( g,\widehat{C_{b}},T_{a},Z\right) =0\right] + \frac{1}{2}Pr\left[ \mathcal {B}\left( g,\widehat{C_{b}},T_{a},Z\right) =0\right] -\frac{1}{2}=\frac{\varepsilon }{2}. \end{aligned}$$

  And $\mathcal {A}$ wins the game if $c^{'}=c$ with the advantage of $Adv^{\mathcal {A}}=|Pr[b=b^{'}]-1/2|$.

5.3 Collusion Resistance

In the phase of secret key generation, trusted authority generates the secret key with the parament of user’s identity UID. So that the secret key of two user will not be the same even if their attributes are the same, which means data user in the system cannot use the secret key belong to others. Besides, the “ver” is used to manage the user revocation. When user revocation occurs, the “ver” will be update to “ver+1”, which means the ciphertext alone with the secret keys will all be update. So that the revoked user’s secret key won’t be able to be used again.

5.4 Trapdoor Unlinkability

As the CSP is a semi-trusted entity in the system, it will be always curious about DU’s information. If a DU wants to conceal the nature of his search, the trapdoor must be encrypted. When DU needs to generate the trapdoor in our scheme, a random number x will be chose to obfuscate the keywords. As a result, CSP will not be able to distinguish the keywords in the trapdoor, even the keywords in the trapdoor are the same with the other one. Thus, the trapdoor in our scheme is unlinkability.

6 Performance Evaluation

6.1 Theoretical Analysis

We analyze the efficiency of the proposed scheme, and compare it with [4, 25, 28]. We note that there exist some novel schemes which addressed the problem of user revocation and ciphertext search like [7, 28]. In [7], the authors achieve the revocation with the help of a revocation list. Besides, their scheme is designed based on the multi-authority, which differ from the scheme in this paper. We assume that the hash computation is not included in the calculation.

Table 1. Storage cost analysis.

The storage cost analysis is shown in Table 1. As we can see, the size of public key, secret key and ciphertext in our scheme is less than that in scheme [4]. In Table 2, the efficiency of encryption and search in our scheme is more superior compare to that in scheme [4]. Compare to the scheme in [25], the size of secret key and ciphertext is larger in our scheme. The reason is that the access structure in [25] is AND gate, and we use the tree structure. But we implement the function of user revocation which was not provided in [25]. In [28], the size of master secret key and secret key is much larger than that in our scheme. In the search phrase, the computing cost grows linearly with the size of keywords in the trapdoor, which will incur poor performance in efficient. Considering both the functions of revocation and ciphertext search are achieved, we believe our’s scheme is more efficient and practical.

Table 2. Computing cost analysis.

6.2 Experiment Analysis

In this section, we evaluate the performance of the proposed scheme presented in Sect. 4. The experiment is performed on the Windows 7 system with an intel core i5-3210M CPU 2.50 GHz and 12 GB memory. We use JDK1.8 and java pairing-based cryptography 2.0.0 (JPBC) [3] to implement our scheme.

We analyze the performance of our scheme by comparing it with Cui’s scheme [4] for the reason that this is the closest work to compare in terms of keyword encryption algorithm, trapdoor generation algorithm and search algorithm. As the cost of computing is closely related to the complexity of the access policy, we generate all the access policy in the form of n of ($\mathcal {S}_{1}$, $\mathcal {S}_{2}$, $\dots$, $\mathcal {S}_{n}$), where $\mathcal {S}_{i}$ is an attribute and n denotes the number of attributes in the policy. As depicted in Fig. 2(a) and (b), we examine the time cost of keyword encryption and trapdoor generation. In the process of keywords encryption, instead of dealing with every one of the keyword, we sum all the keywords together. As a result, the encrypted keyword is constant in size and the expense is small. To relief the time cost of trapdoor generation, we generate parts of the trapdoor in the secret key generation algorithm, so that we only need to do a little exponential operation. In addition, as we said before, the search operation is efficient in our scheme. We can see the time cost in Fig. 2(c) is very small, we only need twice bilinear pairing operation to finish the search operation while scheme [4] need three times. The time cost of the system initialization algorithm, secret key generation algorithm, encryption algorithm and decryption algorithm are depicted in Fig. 2(d), (e), (f) and (g). As the number of attributes grows, the time cost grows linearly.

Fig. 2.

Experimental results

7 Conclusion

In this paper, an attribute-based encryption with efficient keyword search and user revocation is proposed. Our scheme is practical and comprehensive. In addition to fine-grained access control through ABE scheme, our scheme also provides the function of user revocation and efficient keyword search. Specifically, it only takes twice bilinear mapping operation to get the search result in the search phrase. Our security analysis implied that the proposed scheme is secure under DBDH assumption. The efficiency analysis and experience demonstrate that the overhead of our scheme is acceptable.