# Research on Ciphertext-Policy Attribute-Based Encryption with Attribute Level User Revocation in Cloud Storage

Authors: Guangbo Wang; Jianhua Wang
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

Attribute-based encryption (ABE) scheme is more and more widely used in the cloud storage, which can achieve fine-grained access control. However, it is an important challenge to solve dynamic user and attribute revocation in the original scheme. In order to solve this problem, this paper proposes a ciphertext-policy ABE (CP-ABE) scheme which can achieve attribute level user attribution. In this scheme, if some attribute is revoked, then the ciphertext corresponding to this attribute will be updated so that only the individuals whose attributes meet the access control policy and have not been revoked will be able to carry out the key updating and decrypt the ciphertext successfully. This scheme is proved selective-structure secure based on theq-Parallel Bilinear Diffie-Hellman Exponent (BDHE) assumption in the standard model. Finally, the performance analysis and experimental verification have been carried out in this paper, and the experimental results show that, compared with the existing revocation schemes, although our scheme increases the computational load of storage service provider (CSP) in order to achieve the attribute revocation, it does not need the participation of attribute authority (AA), which reduces the computational load of AA. Moreover, the user does not need any additional parameters to achieve the attribute revocation except for the private key, thus saving the storage space greatly.


---

## Body

## 1. Introduction

With the advent of big data era, there is an increasing number of user data. In order to achieve the sharing of data and reduce the cost at the same time, using the third party, namely, cloud storage provider (CSP), will be an excellent priority. The cloud storage, which emerged as the extension and development of cloud computing, achieves the function that the users can access the data conveniently at any time and at any place by any networking equipment; therefore, it has been more and more extensively used. However, the users’ data are stored in the CSP and got rid of the users’ actual control; therefore, how to guarantee the users privacy and data security as much as possible without reducing the quality of service has become a key problem of secure cloud storage.Sahai and Waters in 2005 proposed the notation of attribute-based encryption (ABE) [1] in which the ciphertext and key are, respectively, associated with a series of attributes, and an access structure is specified to define the attribute set that can be used to decrypt the ciphertext successfully. ABE can achieve fine-grained access control by using the flexible access structure, so it has been widely used in the cloud storage. The initial ABE schemes can only achieve the threshold operations so that the policy expression is not rich enough. To solve this problem, some scholars have proposed the ciphertext-policy ABE (CP-ABE) mechanism [2–4] and key-policy ABE (KP-ABE) mechanism [5, 6], which can realize rich attribute operations so as to support flexible access control policy.However, the application of ABE in cloud storage also brings serious security challenges. There are a large number of users in the cloud storage environment, and different users may share the same attribute in the application of ABE. Therefore, if some attribute of a user is revoked, how to recall the user’s corresponding access permissions without affecting the normal access of other legitimate users and posing a large load on the system has become an urgent problem to be solved. Therefore, this paper mainly pursues the relative research on this issue.Recently, individuals pay more and more attention to the problem of user revocation in the practical application of ABE. Ostrovsky et al. proposed an ABE scheme with system level user revocation [7]. In this scheme, the revocation is carried out by implementing the “NOT” operation on “AND” gates; however, the efficiency is rather low.Subsequently, Staddon et al. proposed a KP-ABE scheme [8] which can achieve the revocation of users; however, this scheme is limited to be used if and only if the number of attributes associated with ciphertext is just half of the whole attributes in the system; therefore, the limit is too high which impedes its actual application. Liang et al. proposed a CP-ABE scheme [9] which achieved the revocation by using a binary tree. In this scheme, an attribute authority is responsible for generating the updating key for implementing the revocation; however, the efficiency is also very low. Moreover, it increases the computation and communication burden on the attribute authority greatly which may become the bottleneck. In addition, all the above schemes can only achieve the system level user revocation; namely, once some attribute of a user is revoked, he will lose not only the access permission corresponding to the revoked attribute but also the access permissions corresponding to the other legitimate attributes.In the aspect of attribute revocation, individuals in the literatures [10–12] strove to achieve the revocation by setting the validity period for each attribute. This method is called coarse-grained revocation because it cannot realize the timely revocation. To solve this problem, Hur and Noh proposed a novel CP-ABE scheme in the literature [13] to realize the revocation by using a key encryption key tree, which can also achieve attribute level user revocation; namely, the revocation to some attribute of a user cannot affect the normal access of other legitimate attributes. In this scheme, if an attribute is revoked, then the CSP will generate a new key encryption key and reencrypts the ciphertext. However, each user needs to store log⁡nu+1 key encryption keys additionally, where nu denotes the number of all the users in this scheme. Moreover, the scheme is proved to be secure in the generic group model which possesses heuristic security rather than provable security; therefore, some schemes proved secure in the generic group model are found to be unsafe in practical application. Subsequently, Yang et al. proposed a CP-ABE scheme [14] in the environment of cloud storage. In this scheme, the attribute authority generates two corresponding public parameters for each attribute, and once the revocation is implemented, the attribute authority needs to update the public parameters for the revoked attribute and the secret key for the user, which increases not only the computation load on the attribute authority but also the communication load between the attribute authority and the user.In this paper, we propose a CP-ABE scheme that combines proxy reencryption methods to achieve the revocation. In this scheme, we achieve the revocation with the help of CSP, which offloads most of revocation operations for the attribute authority that has limited resources. If some attribute is revoked, then the ciphertext corresponding to this attribute will be updated by the CSP so that only the users whose attributes meet the access control policy and have not been revoked will be able to carry out the key updating and decrypt the ciphertext successfully. Additionally, in this scheme, we achieve the fine-grained attribute level user revocation; namely, the revocation to an attribute of some user cannot affect the normal access of this user’s other legitimate attributes. Finally, we carry out the performance analysis and experimental verification to demonstrate the characteristics, which shows that, compared with the existing revocation schemes, although our scheme increases the computational load of CSP in order to achieve the attribute revocation, it does not need the participation of AA. Moreover, the user does not need any additional parameters to achieve the attribute revocation except of the private key, thus saving the storage space greatly.


## 2. Preliminaries

Before proposing the concrete scheme in this paper, we first introduce the related technologies that will be used including bilinear group, linear secret-sharing scheme (LSSS), and deterministicq-Parallel Bilinear Diffie-Hellman Exponent (BDHE) assumption.


### 2.1. Bilinear Map

In this part, we will briefly take a view to several facts related to the bilinear group as follows.Definition 1 (bilinear map).
The bilinear group has been widely used in various cryptographic systems after it was proposed for the first time. Letψ be a group parameters generation algorithm which takes as input the security parameter λ and outputs the group parameters (p,G,GT,e). In these group parameters, p denotes a big prime whose size is determined by the security parameter λ, G and GT are two multiplicative cyclic groups with order p, and e:G×G→GT is a bilinear map satisfying the following properties: (1)
Bilinearity:∀u,v∈G,a,b∈Zp, we have e(ua,vb)=e(u,v)ab.(2)
Nondegeneracy:∃g∈G satisfying that e(g,g) has order p in GT.(3)
Computability: there exists an efficient algorithm to compute the bilinear pairing.


### 2.2. Linear Secret-Sharing Scheme

Definition 2 (linear secret-sharing scheme (LSSS) [15]).
A secret-sharing scheme∏ over a set of parties P is a LSSS (over Zp) if it satisfies the following properties:
(1) The secret share of each party constitutes a vector overZp.
(2) For each secret-sharing scheme∏, there exists a share-generation matrix M(l×n) where, for each row Mi of the matrix M, we define a function ρ: {1,…,l}→P that maps it to the corresponding party ρ(i). Considering a vector v→=(s,r2,…,rn), where s∈Zp is the sharing secret and parameters r2,…,rn∈Zp are chosen randomly to conceal the secret, then Mv→ is a vector that is composed of l shares of the secret s. Moreover, λi=(Mv→)i denotes the secret share possessed by the party ρ(i).
Suppose∏ is a LSSS for the access structure (M,ρ) and S denotes any authorized set for (M,ρ). We define the set D⊂{1,2,…,l} as D={i:ρ(i)∈S}; then, the constants {wi∈Zp}i∈D can be computed in polynomial time such that if {λi} are valid shares of any secret s according to ∏, then we have ∑i∈Dwiλi=s.


### 2.3. Decisionalq-Parallel Bilinear Diffie-Hellman Exponent Assumption

Definition 3 (q-parallel BDHE assumption [16]).
LetG denote the bilinear group with prime order p, the parameters a,s,b1,…,bq are chosen randomly in Zp, and g is a generator of G. Then, the decisional q-Parallel BDHE assumption is that if there is an attacker A who is given the parameters(1)y→=g,gs,ga,…,gaq,,gaq+2,…,ga2q,y→=gsbj,ga/bj,…,gaq/bj,…,ga2q/bj,∀1≤j≤q,y→=gasbk/bj,…,gaqsbk/bj∀1≤k,j≤q,
then, it is hard forA to distinguish e(g,g)aq+1s from a random element in GT. In addition, a polynomial time algorithm B will use the output of A to make a guess, and we define the advantage of B to solve the q-Parallel BDHE assumption in G and GT as (2)PrBy→,eg,gaq+1s=0-PrBy→,R=0.
If there is no polynomial time algorithm to solve theq-Parallel BDHE assumption with a nonnegligible advantage, then we can say that the assumption holds in G and GT.


## 2.1. Bilinear Map

In this part, we will briefly take a view to several facts related to the bilinear group as follows.Definition 1 (bilinear map).
The bilinear group has been widely used in various cryptographic systems after it was proposed for the first time. Letψ be a group parameters generation algorithm which takes as input the security parameter λ and outputs the group parameters (p,G,GT,e). In these group parameters, p denotes a big prime whose size is determined by the security parameter λ, G and GT are two multiplicative cyclic groups with order p, and e:G×G→GT is a bilinear map satisfying the following properties: (1)
Bilinearity:∀u,v∈G,a,b∈Zp, we have e(ua,vb)=e(u,v)ab.(2)
Nondegeneracy:∃g∈G satisfying that e(g,g) has order p in GT.(3)
Computability: there exists an efficient algorithm to compute the bilinear pairing.


## 2.2. Linear Secret-Sharing Scheme

Definition 2 (linear secret-sharing scheme (LSSS) [15]).
A secret-sharing scheme∏ over a set of parties P is a LSSS (over Zp) if it satisfies the following properties:
(1) The secret share of each party constitutes a vector overZp.
(2) For each secret-sharing scheme∏, there exists a share-generation matrix M(l×n) where, for each row Mi of the matrix M, we define a function ρ: {1,…,l}→P that maps it to the corresponding party ρ(i). Considering a vector v→=(s,r2,…,rn), where s∈Zp is the sharing secret and parameters r2,…,rn∈Zp are chosen randomly to conceal the secret, then Mv→ is a vector that is composed of l shares of the secret s. Moreover, λi=(Mv→)i denotes the secret share possessed by the party ρ(i).
Suppose∏ is a LSSS for the access structure (M,ρ) and S denotes any authorized set for (M,ρ). We define the set D⊂{1,2,…,l} as D={i:ρ(i)∈S}; then, the constants {wi∈Zp}i∈D can be computed in polynomial time such that if {λi} are valid shares of any secret s according to ∏, then we have ∑i∈Dwiλi=s.


## 2.3. Decisionalq-Parallel Bilinear Diffie-Hellman Exponent Assumption

Definition 3 (q-parallel BDHE assumption [16]).
LetG denote the bilinear group with prime order p, the parameters a,s,b1,…,bq are chosen randomly in Zp, and g is a generator of G. Then, the decisional q-Parallel BDHE assumption is that if there is an attacker A who is given the parameters(1)y→=g,gs,ga,…,gaq,,gaq+2,…,ga2q,y→=gsbj,ga/bj,…,gaq/bj,…,ga2q/bj,∀1≤j≤q,y→=gasbk/bj,…,gaqsbk/bj∀1≤k,j≤q,
then, it is hard forA to distinguish e(g,g)aq+1s from a random element in GT. In addition, a polynomial time algorithm B will use the output of A to make a guess, and we define the advantage of B to solve the q-Parallel BDHE assumption in G and GT as (2)PrBy→,eg,gaq+1s=0-PrBy→,R=0.
If there is no polynomial time algorithm to solve theq-Parallel BDHE assumption with a nonnegligible advantage, then we can say that the assumption holds in G and GT.


## 3. Attribute-Based Encryption

In this part, we will first give the system model for our proposed CP-ABE scheme with attribute level user revocation, and then we give a selectively secure model in terms of the ciphertext indistinguishability under a chosen plaintext attack (IND-CPA) [17] which is defined between a polynomial time attacker A and challenger B. Finally, we will give the detailed construction.


### 3.1. System Model

The concrete system model of our proposed CP-ABE scheme is shown as in Figure1, which mainly consists of four entities as follows.Figure 1
System model.(
1) Attribute Authority (AA). It is responsible for implementing the system setup algorithm to generate the system parameters and implementing the key generating algorithm to generate the secret key for the data user.(
2) Data Owner (DO). He is responsible for implementing the data encryption algorithm on the plaintext data and sends the generated ciphertext to the CSP. If the DO decides that some attribute needs to be revoked, he will first designate the responding revoked users list and then send the list to the CSP.(
3) Data User (DU). He is responsible for implementing the decryption algorithm. If the DU wants to access the data in the CSP, he will first send his transformation key to the CSP for partial decryption. Once the DU receives the partially decrypted ciphertext, he will use his secret key to implement the final decryption.(
4) Cloud Storage Provider (CSP). He is responsible for implementing the data reencryption algorithm to achieve the ciphertext updating and implementing the partial decryption algorithm for the DU. Here, we assume that the CSP is curious but honest; namely, he will honestly execute the tasks assigned by other legitimate entities in the system; however, he has the incentive to learn the contents of encrypted data as much as possible.


### 3.2. Selectively Secure Model

This security model mainly draws lessons from the technique proposed by Tu et al. in the literature [18]. In this model, the attacker A firstly needs to submit a challenge access structure and a revocation list, and as a response he will obtain the corresponding public key parameters. Subsequently, A begins to make a series of secret key queries and ciphertext reencryption queries. In the challenge phase, A will give two messages with the equal length, and then the challenger B chooses to encrypt one of these two messages based on the random sampling. Next, A continues to make the secret key query and ciphertext reencryption query and finally outputs a random guess. If the guess is correct, then we can say A wins the game. The specific definition of this security model is given as follows.Init. The attacker A initially chooses the challenge access control structure A∗ and the revocation users list RLx∗ of attribute x∗.Setup. The challenger B runs the algorithmSetup to obtain the public key PK and the master key MK. Finally, B gives PK to the attacker A and keeps MK private to itself.Query Phase 1. The attacker A adaptively makes a series of secret key queries corresponding to the identity-attribute tuple, namely, (ID1,S1),…,(IDq1,Sq1); if IDi∉RLx∗, then we set Si′=Si; otherwise, we set Si′=Si/{x∗}. Note that it must satisfy the restriction that any attributes set Si′ cannot satisfy the challenge access control structure A∗ in this phase. In addition, A can also make a series of ciphertext reencryption queries associated with the revocation users list of some attribute and the ciphertext.Challenge. The attacker A outputs two messages m0 and m1 with the equal length to the challenger B. Then, B chooses a random bit β∈{0,1} and encrypts the message mβ under the access control structure A∗ to generate the ciphertext CT∗. Finally, B sends CT∗ to A as the challenge ciphertext.Query Phase 2. The attacker A continues to make a series of secret key queries and ciphertext reencryption queries as inQuery Phase 1 with the same restriction.Guess. The attacker A outputs its guess β′ for β, and if β′=β, then A wins the game. In addition, the advantage of A in this game is defined as AdvA=Pr⁡β′=β-1/2.If there is no polynomial time algorithm to break the security model above with a nonnegligible advantage, then we can say that our proposed CP-ABE scheme with attribute level user revocation is secure.


### 3.3. Construction

In this part, we will give the concrete construction of our proposed CP-ABE scheme. In our scheme, the attribute authority will first generate the system parameters that will be used in the subsequent algorithms. If the data owner DO wants to store his data on the CSP, he will first encrypt the data with some access control policy to generate the corresponding ciphertext, then he will send the ciphertext to the CSP. Once the DO decides that an attribute of some users list needs to be revoked, he will send the users list to the CSP. Then, the CSP will implement the reencryption on the ciphertext so that only the users whose attributes meet the access control policy associated with the ciphertext and have not been revoked will be able to carry out the key updating and decrypt the ciphertext successfully. In addition, we use the outsourcing decryption to improve the efficiency; namely, the data user (DU) can send his transformation key to the CSP for partial decryption, which makes full use of the computing resources in the CSP. Once the DU gets the partially decrypted ciphertext, he will implement the final decryption faster with less computing resources.


#### 3.3.1. System Setup

In this phase, the attribute authority will generate the corresponding system parameters including the public key and the master key. The public key is accessible by all the entities in the system and the master key is kept private to the attribute authority.(
1) Setup
(
s
e
t
u
p
λ
,
U
,
n
→
(
P
K
,
M
K
)
). The setup algorithm takes as input the security parameter λ, the attributes set U, and the number n of users in the system; then, it runs the group parameters generation function ψ to obtain (G,GT,p,e), where p denotes a big prime, G and GT are two cyclic groups with order p, and e is a bilinear map. Let g be the generator of G. Then, the algorithm chooses random exponents α,β∈Zp and sets gi=g(αi)∈G, where i=1,2,…,n,n+2,…,2n. Next, it chooses a random exponent γ∈Zp and sets v=gγ. For each attribute i∈U, the algorithm chooses random parameters hi∈G. Finally, the system public key PK is set as PK=(p,g,g1,…,gn,gn+2,…,g2n,v,e(g,g)β,h1,…,hU) and the master key MK is set as MK=(α,γ,gβ).


#### 3.3.2. Data Encryption

If the data owner wants to store his datam∈GT on the CSP, then he will first define an access control policy (M,ρ) where M is a l×n matrix, and the function ρ maps each row Mi of M to one corresponding attribute ρ(i) with the restriction that ρ cannot map two distinct rows to one attribute just as in literature [19]. Next, the data encryption algorithm runs Encrypt(PK,m,(M,ρ)) to encrypt the data m. Note that the encryption on the data m needs to multiply it with some group element in GT; therefore, m is also defined as an element in GT. If we want to encrypt some arbitrary data, then we can define a hash function: H:Zp→GT which maps the arbitrary data to an element in the group GT.(
2) Encrypt
(
e
n
c
r
y
p
t
(
P
K
,
m
,
(
M
,
ρ
)
)
→
C
T
). The encryption algorithm takes as input the public key PK, the plaintext message m, and an access control policy (M,ρ); then, it chooses random parameters s,v2,…,vn∈Zp and defines the vector v=(s,v2,…,vn). For each row Mi of  M, the algorithm computes the inner product λi=Mi·v, and then it chooses a random exponent ri∈Zp and outputs the ciphertext as follows: (3)CT=M,ρ,C=m·eg,gβs,C0=gs,Ci,1=g1λihρi-ri,Ci,2=grii=1l.


#### 3.3.3. Data Reencryption

If the DO decides that the attributex of users list RLx needs to be revoked, then he will send (x,RLx) to the CSP. Once the CSP receives (x,RLx), he will use the broadcast encryption to update the ciphertext for the purpose of revoking the access permission corresponding to attribute x without affecting the normal access of other legitimate attributes for the users in RLx.(
3) Re-Encrypt
(
R
e
-
e
n
c
r
y
p
t
(
P
K
,
C
T
,
R
L
x
)
→
C
T
′
′
). The reencryption algorithm takes as input the public key PK, the ciphertext CT=(C,C0,{Ci,1,Ci,2}i=1l), and the revocation users list RLx, and then it chooses a random exponent vx∈Zp∗ and outputs the reencrypted ciphertext as follows:(4)CT′=A,ρ,C′=C,C0′=C0,ρi≠x:Ci,1′=Ci,1,Ci,2′=Ci,2,ρi=x:Cx,1′=Cx,1,Cx,2′=Cx,21/vx=grx1/vx.Next, the algorithm chooses random parameterss~,v~2,…,v~n∈Zp and defines the vector v~=(s~,v~2,…,v~n). Note that the reencryption algorithm will use the same access control policy (M,ρ) as in theEncrypt algorithm. For each row Mi of the matrix M, it computes the inner product λ~i=Mi·v~ and chooses a random exponent r~i∈Zp. Then, the algorithm defines a broadcast users set N=n∖{RLx} and outputs the ciphertext header generated by encrypting the exponent vx as follows: (5)Hdrx=RLx,C~=vx·egn,g1s~,C~0=gs~,C~1=v∏j∈Ngn+1-j-1s~,C~i,1=g1λ~ihρi-r~i,C~i,2=gr~ii=1l.Finally, it returns the ciphertext asCT′′=(CT′,Hdrx).


#### 3.3.4. Key Generation

In order to improve the decryption efficiency, we outsource the decryption of ciphertext to the CSP that has plenty of computing resources. The concrete key generation algorithm is given as follows.(
4) KeyGen
(
k
e
y
g
e
n
o
u
t
(
P
K
,
M
K
,
I
D
,
S
)
→
S
K
). The key generation algorithm takes as input the public key PK, the master key MK, a user’s identity ID, and the attributes set S, and then it chooses a random exponent r′∈Zp and generates the corresponding key SK′=(K′,K~′,L′,{Ki′}i∈S), where(6)K′=gαIDγgαr′,K~′=gβgαr′,L′=gr′,Ki′=hir′i∈S.Next, the algorithm continues to choose a random exponentz∈Zp∗ and computes (7)K=K′1/z=gαIDγ1/zgαr′1/z,K~=K~′1/z=gβ1/zgαr′1/z,L=L′1/z=gr′1/z,Ki=Ki′1/z=hir′1/zi∈S.Letr=r′/z; then, we have(8)K=gαIDγ1/zgαr,K~=gβ1/zgαr,L=gr,Ki=hiri∈S.Finally, we set the outsourced transformation key asTK=(K,K~,L,{Ki=hir}i∈S) and the secret key as SK=(z,TK).


#### 3.3.5. Partial Decryption

In order to achieve the outsourced decryption, the user needs to send his transformation keyTK to the CSP. Note that the transformation key cannot leak any useful information associated with the secret key SK and the plaintext data m. The concrete partial decryption algorithm is given as follows.(
5) Transform
(
transform
out
(
T
K
,
C
T
′
′
)
→
T
C
T
). The transformation algorithm takes as input the transformation key TK=(K,K~,L,{Ki=hir}i∈S) and the ciphertext CT′′=(CT′,Hdrx).(1) If there is no attribute revoked, namely,Hdrx=Φ, then we have the following.Here, we haveCT′′=((M,ρ),C,C0,{Ci,1,Ci,2}i=1l), and if the attributes set S associated with TK satisfies the access control policy (M,ρ) included in CT′′, then the CSP computes the values {wi∈Zp}i∈I satisfying ∑i∈IwiMi=(1,0,…,0) in polynomial time. Next, it computes(9)B=∏i∈IeCi,1,LwieCi,2,Kρiwi=∏i∈Ieg1λihρi-ri,grwiegri,hρirwi=eg,gαrs,D=eC0,K~=egs,gβ/zgαr=eg,gβs/zeg,gαrs,E=DB=eg,gβs/zeg,gαrseg,gαrs=eg,gβs/z.Once the partial decryption is over, the CSP sendsTCT=(C,E) to the corresponding user for the final decryption.(2) If the attributex of users list RLx is revoked, namely, Hdrx≠Φ, then we have the following.Here, we haveCT′=((M,ρ),C′,C0′,{Ci,1′,Ci,2′}i=1l) and Hdrx=(RLx,C~,C~0,C~1,{C~i,1,C~i,2}i=1l), and if the attributes set S satisfies the access control policy (M,ρ) and ID∉RLx, then the CSP implements the partial decryption on the ciphertext header Hdrx. It also computes the values {w~i∈Zp}i∈I~ satisfying ∑i∈I~w~iMi=(1,0,…,0) and then continues to compute (10)Bx=∏i∈I~eC~i,1,Lw~ieC~i,2,Kρiw~i=∏i∈I~eg1λ~ihρi-r~i,grw~ieg-r~i,hρirw~i=eg,gαrs′,Dx=eC~0,K=eg,gαIDγs~/zeg,gαrs~,Ex=DxBx=eg,gαIDγs~/z,Fx=egID,C~1e∏j∈Nj≠IDgn+1-j+ID,C~0-1=egID,v∏j∈Ngn+1-j-1s~e∏j∈Nj≠IDgn+1-j+ID,gs~-1=egID,vs~·egn+1,g-s~.Therefore, the partially decrypted ciphertext header is set asHdrx′=(C~,Ex,Fx).Next, the CSP implements the partial decryption on the ciphertextCT′ as follows:(11)Bi=eCi,1′,LeCi,2′,Kρi=eg,gαrλiρi≠x,D=eC0′,K~=egs,gβ/zgαr=eg,gβs/zeg,gαrsρi=x.Therefore, the partially decrypted ciphertext is set as(12)TCT′=M,ρ,C′=m·eg,gβs,Biρi≠x,Cx,1′,Cx,2′,D.Once the partial decryption is over, the CSP sendsTCT=(TCT′,Hdrx′) to the corresponding user for the final decryption.


#### 3.3.6. Decryption

Once the user gets the partially decrypted ciphertext, he will use his secret key to implement the final decryption for obtaining the plaintext message as follows.(
6) Decrypt
(
d
e
c
r
y
p
t
(
T
C
T
,
S
K
)
→
m
). The decryption algorithm takes as input the partially decrypted ciphertext TCT and the user’s secret key SK. Then, it decrypts the ciphertext as follows:(1) If there is no attribute revoked, namely,TCT=(C,E), then the user computes(13)CEz=m·eg,gβseg,gβs/zz=m.(2) If the attributex of users list RLx is revoked, namely, TCT=(TCT′,Hdrx′), then we have the following.Here, we haveTCT′=(C′,{Bi}ρi≠x,Cx,1′,Cx,2′,D) and Hdrx′=(C~,Ex,Fx), and then the user computes (14)C~·FxExz=vx·egn,g1s~·egID,vs~·egn+1,g-s~eg,gαIDγs~/zz=vx.If the attributes setS satisfies the access control policy (M,ρ), then the CSP computes the values {wi∈Zp}i∈I satisfying ∑i∈IwiMi=(1,0,…,0) in polynomial time and continues to compute(15)Bx=eCx,1′,LeCx,2′,Kρxvx=eg1λxhρx-rx,gr·egrx1/vx,hρxrvx=eg1λx,gr=eg,gαrλx,B=∏i∈IBiwi=∏i∈Ieg,gαrλiwi=eg,gαrs,E=DB=eg,gβs/zeg,gαrseg,gαrs=eg,gβs/z,CEz=m·eg,gβseg,gβs/zz=m.


### 3.4. Security Proof

Theorem 4.
If the decisionalq-Parallel BDHE assumption holds in G and GT, then there exists no polynomial time attacker to break our proposed CP-ABE scheme with attribute level user revocation selectively, where the challenge matrix is M∗(l∗×n∗) with l∗,n∗≤q.Proof.
If there exists an attackerA who can selectively break our proposed CP-ABE scheme with a nonnegligible advantage ε=AdvA, where the challenge matrix is M∗(l∗×n∗) with l∗,n∗≤q, then we can construct a challenger B to break the decisional q-Parallel BDHE assumption successfully.Init. The challenger B takes as input a q-Parallel BDHE challenge y→,T. In addition, the attacker A gives the challenge access control policy (M∗,ρ∗) and the revocation users list RLx∗ of attribute x∗ where the matrix M∗ has n∗ columns.Setup. The challenger B chooses a random exponent β′∈Zp and computes e(g,g)β=e(g,g)β′·egα,gαq, where it implicitly sets β=β′+αq+1. In addition, it sets the broadcast users set as(16)N^=RLx∗∩1,2,…,n,N=1,2,…,n∖N^.Then,B selects a random exponent u∈Zp and sets v=gu∏k∈Ngq+1-k.Next,B sets the group parameters h1,h2,…,hU, and for each x(1≤x≤U), B selects a random exponent zx∈Zp. Let X denote the set of i satisfying ρ∗(i)=x; then, hx is set as(17)hx=gzx∏i∈XgaMi,1∗/bi·ga2Mi,2∗/bi⋯gan∗Mi,n∗∗/bi.Note that ifX=⌀, then we have hx=gzx. In addition, we can say that hx is distributed randomly because of the randomness of zx.Finally,B sends to A the public key PK as(18)PK=g,g1,…,gq,gq+2,…,g2q,v,eg,gβ,h1,…,hU.Query Phase 1. A makes to B a series of queries including the key generation query Okg and the ciphertext reencryption query Oree.(i)A makes to B a key generation query Okg associated with the identity IDj and the attributes set Sj; if IDj∉RLx∗, then we set the attributes set Sj′=Sj; otherwise, we set Sj′=Sj∖{x∗}. In addition, if Sj′ satisfies the challenge access control policy (M∗,ρ∗), then B outputs ⊥; otherwise, it generates the secret key as follows.B first computes the vector w→=(w1,…,wn∗)∈Zpn, where w1=-1, and for all ρ∗(i)∈Sj′, it satisfies Mi∗w→T=0. Note that the vector can be found in polynomial time according to the definition of LSSS.Then,B chooses a random parameter t∈Zp and defines the exponent r as(19)r=t+w1αq+w2αq-1+⋯+wn∗α.Next,B computes the key component L′ as (20)L′=gt·∏i=1,…,n∗gαq+1-iwi=gr.According to the definition ofr and w1=-1, we know that gαr includes the item g-αq+1. Although g-αq+1 is not given in the assumption, it can be canceled by multiplying gαr with gβ=gβ′gαq+1, because we implicitly set β=β′+αq+1 when generating the key component K~′. In detail, it is constructed as follows:(21)K~′=gβ′gαq+1gαtg-αq+1∏i=2,…,n∗gαq+2-iwi=gβ′gαt∏i=2,…,n∗gαq+2-iwi.Then,B will compute the key component Ki′,∀i∈Sj′. For each attribute i∈Sj′, if there exists no row k satisfying ρ∗(k)=i, then we set Ki′=(L′)zi; otherwise, let X denote the set of all the rows k satisfying ρ∗(k)=i, and then we set Ki′ as(22)Ki′=L′zi∏i∈X∏j=1,…,n∗gαj/bit·∏k=1,…,n∗,k≠jgαq+1+j-k/biwkMi,j∗.Next,B  will set the key component K′ for the user IDj∉RLx∗. Similarly, gαr includes the item g-αq+1 that is not given in the assumption. However, we set the value v as v=gu∏k∈Ngq+1-k and we have gαIDjγ=(gu∏k∈N^gq+1-k)αIDj. Moreover, because IDj∉RLx∗, namely, IDj∈N, gαIDγ includes the term gαq+1 that can be canceled by the term g-αq+1 included in gαr:(23)K′=gαIDγgαr=gu∏k∈Ngq+1-kαID·gαtg-αq+1∏i=2,…,n∗gαq+2-iwi=gαIDu∏k∈N∖IDjgq+1-k+IDj·gq+1-IDj+IDj·gαtg-αq+1∏i=2,…,n∗gαq+2-iwi=gαIDu∏k∈N∖IDjgq+1-k+IDj·gαt∏i=2,…,n∗gαq+2-iwi.Once the key components are all generated, the challengerB will select a random exponent z∈Zp∗ and set the outsourced transformation key TK as (24)TK=K=K′1/z,K~=K~′1/z,L=L′1/z,Kii∈Sj′=Ki′1/zi∈Sj′.Therefore, the secret key is set asSK=(z,TK). Finally, B sends the transformation key TK to the attacker A.(ii)A makes to B a ciphertext reencryption query Oree associated with the revocation users list RLx of attribute x and the ciphertext CT=(C,C0,{Ci,1,Ci,2}i=1l). Then, B generates the reencrypted ciphertext as follows.B first selects a random exponent vx∈Zp∗ and computes(25)CT′=C′=C,C0′=C0,ρi≠x:Ci,1′=Ci,1,Ci,2′=Ci,2,ρi=x:Ci,1′=Ci,1,Ci,2′=Ci,21/vx.Next,B selects random parameters s~,v~2,…,v~n∈Zp and defines the vector v~=(s~,v~2,…,v~n). For each row Mi of the matrix M, B computes the inner product λ~i=Mi·v~. Then, B selects a random exponent r~i∈Zp and defines the broadcast users set as N=q∖{RLx}. Finally, it encrypts the exponent vx to generate the ciphertext header as follows:(26)Hdrx∗=RLx∗,C~=vx·egn,g1s~,C~0=gs~,C~1=gus~,C~i,1=g1λ~ihρi-r~i,C-i,2=gr~ii=1l.Note thatC~1 is a correctly distributed ciphertext component which is demonstrated as follows:(27)C~1=gus~=gu∏k∈Ngq+1-k·∏j∈Ngq+1-k-1s~=v∏j∈Ngq+1-k-1s~.Therefore, the final reencrypted ciphertext is set asCT′′=(CT′,Hdrx).Challenge. The attacker A submits to the challenger B two messages m0 and m1 with the equal length. Then, B selects a random coin β∈{0,1} and generates the challenge ciphertext components as (28)C∗=mβ·T·egs,gβ′,C0∗=gs.Next,B selects random parameters y2′,…,yn∗′∈Zp and then sets the vector v→=(s,sa+y2′,sa2+y3′,…,san-1+yn∗′)∈Zpn∗ to implicitly share the key s. For i=1,2,…,n∗, B defines Ri as the set of all k≠i satisfying ρ∗(i)=ρ∗(k). Finally, B selects random exponents r1′,r2′,…,rl′∈Zp and sets the challenge ciphertext components Ci,1∗ and Ci,2∗ as follows:(29)Ci,1∗=g-ri′g-sbi,Ci,2∗=hρ∗ir′∏j=2,…,n∗gαMi,j∗yj′·gsbi-zρ∗i·∏k∈Ri∏j=1,…,n∗gαj·s·bi/bkMk,j∗.Query Phase 2. A continues to make to B a series of queries including the key generation query Okg and the ciphertext reencryption query Oree as inQuery Phase 1.Guess. The attacker A outputs its guess β′ for β. If β=β′, then A outputs 0 denoting T=e(g,g)αq+1s; otherwise, it outputs 1 denoting T is a random parameter in GT.IfT=e(g,g)αq+1s, then B plays the proper security game, so we have(30)Pr⁡By→,T=eg,gαq+1s=0=12+AdvA.Otherwise,T is a random element in GT; namely, mβ is completely random in the view of A, so we have (31)Pr⁡By→,T=R=0=12.


## 3.1. System Model

The concrete system model of our proposed CP-ABE scheme is shown as in Figure1, which mainly consists of four entities as follows.Figure 1
System model.(
1) Attribute Authority (AA). It is responsible for implementing the system setup algorithm to generate the system parameters and implementing the key generating algorithm to generate the secret key for the data user.(
2) Data Owner (DO). He is responsible for implementing the data encryption algorithm on the plaintext data and sends the generated ciphertext to the CSP. If the DO decides that some attribute needs to be revoked, he will first designate the responding revoked users list and then send the list to the CSP.(
3) Data User (DU). He is responsible for implementing the decryption algorithm. If the DU wants to access the data in the CSP, he will first send his transformation key to the CSP for partial decryption. Once the DU receives the partially decrypted ciphertext, he will use his secret key to implement the final decryption.(
4) Cloud Storage Provider (CSP). He is responsible for implementing the data reencryption algorithm to achieve the ciphertext updating and implementing the partial decryption algorithm for the DU. Here, we assume that the CSP is curious but honest; namely, he will honestly execute the tasks assigned by other legitimate entities in the system; however, he has the incentive to learn the contents of encrypted data as much as possible.


## 3.2. Selectively Secure Model

This security model mainly draws lessons from the technique proposed by Tu et al. in the literature [18]. In this model, the attacker A firstly needs to submit a challenge access structure and a revocation list, and as a response he will obtain the corresponding public key parameters. Subsequently, A begins to make a series of secret key queries and ciphertext reencryption queries. In the challenge phase, A will give two messages with the equal length, and then the challenger B chooses to encrypt one of these two messages based on the random sampling. Next, A continues to make the secret key query and ciphertext reencryption query and finally outputs a random guess. If the guess is correct, then we can say A wins the game. The specific definition of this security model is given as follows.Init. The attacker A initially chooses the challenge access control structure A∗ and the revocation users list RLx∗ of attribute x∗.Setup. The challenger B runs the algorithmSetup to obtain the public key PK and the master key MK. Finally, B gives PK to the attacker A and keeps MK private to itself.Query Phase 1. The attacker A adaptively makes a series of secret key queries corresponding to the identity-attribute tuple, namely, (ID1,S1),…,(IDq1,Sq1); if IDi∉RLx∗, then we set Si′=Si; otherwise, we set Si′=Si/{x∗}. Note that it must satisfy the restriction that any attributes set Si′ cannot satisfy the challenge access control structure A∗ in this phase. In addition, A can also make a series of ciphertext reencryption queries associated with the revocation users list of some attribute and the ciphertext.Challenge. The attacker A outputs two messages m0 and m1 with the equal length to the challenger B. Then, B chooses a random bit β∈{0,1} and encrypts the message mβ under the access control structure A∗ to generate the ciphertext CT∗. Finally, B sends CT∗ to A as the challenge ciphertext.Query Phase 2. The attacker A continues to make a series of secret key queries and ciphertext reencryption queries as inQuery Phase 1 with the same restriction.Guess. The attacker A outputs its guess β′ for β, and if β′=β, then A wins the game. In addition, the advantage of A in this game is defined as AdvA=Pr⁡β′=β-1/2.If there is no polynomial time algorithm to break the security model above with a nonnegligible advantage, then we can say that our proposed CP-ABE scheme with attribute level user revocation is secure.


## 3.3. Construction

In this part, we will give the concrete construction of our proposed CP-ABE scheme. In our scheme, the attribute authority will first generate the system parameters that will be used in the subsequent algorithms. If the data owner DO wants to store his data on the CSP, he will first encrypt the data with some access control policy to generate the corresponding ciphertext, then he will send the ciphertext to the CSP. Once the DO decides that an attribute of some users list needs to be revoked, he will send the users list to the CSP. Then, the CSP will implement the reencryption on the ciphertext so that only the users whose attributes meet the access control policy associated with the ciphertext and have not been revoked will be able to carry out the key updating and decrypt the ciphertext successfully. In addition, we use the outsourcing decryption to improve the efficiency; namely, the data user (DU) can send his transformation key to the CSP for partial decryption, which makes full use of the computing resources in the CSP. Once the DU gets the partially decrypted ciphertext, he will implement the final decryption faster with less computing resources.


### 3.3.1. System Setup

In this phase, the attribute authority will generate the corresponding system parameters including the public key and the master key. The public key is accessible by all the entities in the system and the master key is kept private to the attribute authority.(
1) Setup
(
s
e
t
u
p
λ
,
U
,
n
→
(
P
K
,
M
K
)
). The setup algorithm takes as input the security parameter λ, the attributes set U, and the number n of users in the system; then, it runs the group parameters generation function ψ to obtain (G,GT,p,e), where p denotes a big prime, G and GT are two cyclic groups with order p, and e is a bilinear map. Let g be the generator of G. Then, the algorithm chooses random exponents α,β∈Zp and sets gi=g(αi)∈G, where i=1,2,…,n,n+2,…,2n. Next, it chooses a random exponent γ∈Zp and sets v=gγ. For each attribute i∈U, the algorithm chooses random parameters hi∈G. Finally, the system public key PK is set as PK=(p,g,g1,…,gn,gn+2,…,g2n,v,e(g,g)β,h1,…,hU) and the master key MK is set as MK=(α,γ,gβ).


### 3.3.2. Data Encryption

If the data owner wants to store his datam∈GT on the CSP, then he will first define an access control policy (M,ρ) where M is a l×n matrix, and the function ρ maps each row Mi of M to one corresponding attribute ρ(i) with the restriction that ρ cannot map two distinct rows to one attribute just as in literature [19]. Next, the data encryption algorithm runs Encrypt(PK,m,(M,ρ)) to encrypt the data m. Note that the encryption on the data m needs to multiply it with some group element in GT; therefore, m is also defined as an element in GT. If we want to encrypt some arbitrary data, then we can define a hash function: H:Zp→GT which maps the arbitrary data to an element in the group GT.(
2) Encrypt
(
e
n
c
r
y
p
t
(
P
K
,
m
,
(
M
,
ρ
)
)
→
C
T
). The encryption algorithm takes as input the public key PK, the plaintext message m, and an access control policy (M,ρ); then, it chooses random parameters s,v2,…,vn∈Zp and defines the vector v=(s,v2,…,vn). For each row Mi of  M, the algorithm computes the inner product λi=Mi·v, and then it chooses a random exponent ri∈Zp and outputs the ciphertext as follows: (3)CT=M,ρ,C=m·eg,gβs,C0=gs,Ci,1=g1λihρi-ri,Ci,2=grii=1l.


### 3.3.3. Data Reencryption

If the DO decides that the attributex of users list RLx needs to be revoked, then he will send (x,RLx) to the CSP. Once the CSP receives (x,RLx), he will use the broadcast encryption to update the ciphertext for the purpose of revoking the access permission corresponding to attribute x without affecting the normal access of other legitimate attributes for the users in RLx.(
3) Re-Encrypt
(
R
e
-
e
n
c
r
y
p
t
(
P
K
,
C
T
,
R
L
x
)
→
C
T
′
′
). The reencryption algorithm takes as input the public key PK, the ciphertext CT=(C,C0,{Ci,1,Ci,2}i=1l), and the revocation users list RLx, and then it chooses a random exponent vx∈Zp∗ and outputs the reencrypted ciphertext as follows:(4)CT′=A,ρ,C′=C,C0′=C0,ρi≠x:Ci,1′=Ci,1,Ci,2′=Ci,2,ρi=x:Cx,1′=Cx,1,Cx,2′=Cx,21/vx=grx1/vx.Next, the algorithm chooses random parameterss~,v~2,…,v~n∈Zp and defines the vector v~=(s~,v~2,…,v~n). Note that the reencryption algorithm will use the same access control policy (M,ρ) as in theEncrypt algorithm. For each row Mi of the matrix M, it computes the inner product λ~i=Mi·v~ and chooses a random exponent r~i∈Zp. Then, the algorithm defines a broadcast users set N=n∖{RLx} and outputs the ciphertext header generated by encrypting the exponent vx as follows: (5)Hdrx=RLx,C~=vx·egn,g1s~,C~0=gs~,C~1=v∏j∈Ngn+1-j-1s~,C~i,1=g1λ~ihρi-r~i,C~i,2=gr~ii=1l.Finally, it returns the ciphertext asCT′′=(CT′,Hdrx).


### 3.3.4. Key Generation

In order to improve the decryption efficiency, we outsource the decryption of ciphertext to the CSP that has plenty of computing resources. The concrete key generation algorithm is given as follows.(
4) KeyGen
(
k
e
y
g
e
n
o
u
t
(
P
K
,
M
K
,
I
D
,
S
)
→
S
K
). The key generation algorithm takes as input the public key PK, the master key MK, a user’s identity ID, and the attributes set S, and then it chooses a random exponent r′∈Zp and generates the corresponding key SK′=(K′,K~′,L′,{Ki′}i∈S), where(6)K′=gαIDγgαr′,K~′=gβgαr′,L′=gr′,Ki′=hir′i∈S.Next, the algorithm continues to choose a random exponentz∈Zp∗ and computes (7)K=K′1/z=gαIDγ1/zgαr′1/z,K~=K~′1/z=gβ1/zgαr′1/z,L=L′1/z=gr′1/z,Ki=Ki′1/z=hir′1/zi∈S.Letr=r′/z; then, we have(8)K=gαIDγ1/zgαr,K~=gβ1/zgαr,L=gr,Ki=hiri∈S.Finally, we set the outsourced transformation key asTK=(K,K~,L,{Ki=hir}i∈S) and the secret key as SK=(z,TK).


### 3.3.5. Partial Decryption

In order to achieve the outsourced decryption, the user needs to send his transformation keyTK to the CSP. Note that the transformation key cannot leak any useful information associated with the secret key SK and the plaintext data m. The concrete partial decryption algorithm is given as follows.(
5) Transform
(
transform
out
(
T
K
,
C
T
′
′
)
→
T
C
T
). The transformation algorithm takes as input the transformation key TK=(K,K~,L,{Ki=hir}i∈S) and the ciphertext CT′′=(CT′,Hdrx).(1) If there is no attribute revoked, namely,Hdrx=Φ, then we have the following.Here, we haveCT′′=((M,ρ),C,C0,{Ci,1,Ci,2}i=1l), and if the attributes set S associated with TK satisfies the access control policy (M,ρ) included in CT′′, then the CSP computes the values {wi∈Zp}i∈I satisfying ∑i∈IwiMi=(1,0,…,0) in polynomial time. Next, it computes(9)B=∏i∈IeCi,1,LwieCi,2,Kρiwi=∏i∈Ieg1λihρi-ri,grwiegri,hρirwi=eg,gαrs,D=eC0,K~=egs,gβ/zgαr=eg,gβs/zeg,gαrs,E=DB=eg,gβs/zeg,gαrseg,gαrs=eg,gβs/z.Once the partial decryption is over, the CSP sendsTCT=(C,E) to the corresponding user for the final decryption.(2) If the attributex of users list RLx is revoked, namely, Hdrx≠Φ, then we have the following.Here, we haveCT′=((M,ρ),C′,C0′,{Ci,1′,Ci,2′}i=1l) and Hdrx=(RLx,C~,C~0,C~1,{C~i,1,C~i,2}i=1l), and if the attributes set S satisfies the access control policy (M,ρ) and ID∉RLx, then the CSP implements the partial decryption on the ciphertext header Hdrx. It also computes the values {w~i∈Zp}i∈I~ satisfying ∑i∈I~w~iMi=(1,0,…,0) and then continues to compute (10)Bx=∏i∈I~eC~i,1,Lw~ieC~i,2,Kρiw~i=∏i∈I~eg1λ~ihρi-r~i,grw~ieg-r~i,hρirw~i=eg,gαrs′,Dx=eC~0,K=eg,gαIDγs~/zeg,gαrs~,Ex=DxBx=eg,gαIDγs~/z,Fx=egID,C~1e∏j∈Nj≠IDgn+1-j+ID,C~0-1=egID,v∏j∈Ngn+1-j-1s~e∏j∈Nj≠IDgn+1-j+ID,gs~-1=egID,vs~·egn+1,g-s~.Therefore, the partially decrypted ciphertext header is set asHdrx′=(C~,Ex,Fx).Next, the CSP implements the partial decryption on the ciphertextCT′ as follows:(11)Bi=eCi,1′,LeCi,2′,Kρi=eg,gαrλiρi≠x,D=eC0′,K~=egs,gβ/zgαr=eg,gβs/zeg,gαrsρi=x.Therefore, the partially decrypted ciphertext is set as(12)TCT′=M,ρ,C′=m·eg,gβs,Biρi≠x,Cx,1′,Cx,2′,D.Once the partial decryption is over, the CSP sendsTCT=(TCT′,Hdrx′) to the corresponding user for the final decryption.


### 3.3.6. Decryption

Once the user gets the partially decrypted ciphertext, he will use his secret key to implement the final decryption for obtaining the plaintext message as follows.(
6) Decrypt
(
d
e
c
r
y
p
t
(
T
C
T
,
S
K
)
→
m
). The decryption algorithm takes as input the partially decrypted ciphertext TCT and the user’s secret key SK. Then, it decrypts the ciphertext as follows:(1) If there is no attribute revoked, namely,TCT=(C,E), then the user computes(13)CEz=m·eg,gβseg,gβs/zz=m.(2) If the attributex of users list RLx is revoked, namely, TCT=(TCT′,Hdrx′), then we have the following.Here, we haveTCT′=(C′,{Bi}ρi≠x,Cx,1′,Cx,2′,D) and Hdrx′=(C~,Ex,Fx), and then the user computes (14)C~·FxExz=vx·egn,g1s~·egID,vs~·egn+1,g-s~eg,gαIDγs~/zz=vx.If the attributes setS satisfies the access control policy (M,ρ), then the CSP computes the values {wi∈Zp}i∈I satisfying ∑i∈IwiMi=(1,0,…,0) in polynomial time and continues to compute(15)Bx=eCx,1′,LeCx,2′,Kρxvx=eg1λxhρx-rx,gr·egrx1/vx,hρxrvx=eg1λx,gr=eg,gαrλx,B=∏i∈IBiwi=∏i∈Ieg,gαrλiwi=eg,gαrs,E=DB=eg,gβs/zeg,gαrseg,gαrs=eg,gβs/z,CEz=m·eg,gβseg,gβs/zz=m.


## 3.3.1. System Setup

In this phase, the attribute authority will generate the corresponding system parameters including the public key and the master key. The public key is accessible by all the entities in the system and the master key is kept private to the attribute authority.(
1) Setup
(
s
e
t
u
p
λ
,
U
,
n
→
(
P
K
,
M
K
)
). The setup algorithm takes as input the security parameter λ, the attributes set U, and the number n of users in the system; then, it runs the group parameters generation function ψ to obtain (G,GT,p,e), where p denotes a big prime, G and GT are two cyclic groups with order p, and e is a bilinear map. Let g be the generator of G. Then, the algorithm chooses random exponents α,β∈Zp and sets gi=g(αi)∈G, where i=1,2,…,n,n+2,…,2n. Next, it chooses a random exponent γ∈Zp and sets v=gγ. For each attribute i∈U, the algorithm chooses random parameters hi∈G. Finally, the system public key PK is set as PK=(p,g,g1,…,gn,gn+2,…,g2n,v,e(g,g)β,h1,…,hU) and the master key MK is set as MK=(α,γ,gβ).


## 3.3.2. Data Encryption

If the data owner wants to store his datam∈GT on the CSP, then he will first define an access control policy (M,ρ) where M is a l×n matrix, and the function ρ maps each row Mi of M to one corresponding attribute ρ(i) with the restriction that ρ cannot map two distinct rows to one attribute just as in literature [19]. Next, the data encryption algorithm runs Encrypt(PK,m,(M,ρ)) to encrypt the data m. Note that the encryption on the data m needs to multiply it with some group element in GT; therefore, m is also defined as an element in GT. If we want to encrypt some arbitrary data, then we can define a hash function: H:Zp→GT which maps the arbitrary data to an element in the group GT.(
2) Encrypt
(
e
n
c
r
y
p
t
(
P
K
,
m
,
(
M
,
ρ
)
)
→
C
T
). The encryption algorithm takes as input the public key PK, the plaintext message m, and an access control policy (M,ρ); then, it chooses random parameters s,v2,…,vn∈Zp and defines the vector v=(s,v2,…,vn). For each row Mi of  M, the algorithm computes the inner product λi=Mi·v, and then it chooses a random exponent ri∈Zp and outputs the ciphertext as follows: (3)CT=M,ρ,C=m·eg,gβs,C0=gs,Ci,1=g1λihρi-ri,Ci,2=grii=1l.


## 3.3.3. Data Reencryption

If the DO decides that the attributex of users list RLx needs to be revoked, then he will send (x,RLx) to the CSP. Once the CSP receives (x,RLx), he will use the broadcast encryption to update the ciphertext for the purpose of revoking the access permission corresponding to attribute x without affecting the normal access of other legitimate attributes for the users in RLx.(
3) Re-Encrypt
(
R
e
-
e
n
c
r
y
p
t
(
P
K
,
C
T
,
R
L
x
)
→
C
T
′
′
). The reencryption algorithm takes as input the public key PK, the ciphertext CT=(C,C0,{Ci,1,Ci,2}i=1l), and the revocation users list RLx, and then it chooses a random exponent vx∈Zp∗ and outputs the reencrypted ciphertext as follows:(4)CT′=A,ρ,C′=C,C0′=C0,ρi≠x:Ci,1′=Ci,1,Ci,2′=Ci,2,ρi=x:Cx,1′=Cx,1,Cx,2′=Cx,21/vx=grx1/vx.Next, the algorithm chooses random parameterss~,v~2,…,v~n∈Zp and defines the vector v~=(s~,v~2,…,v~n). Note that the reencryption algorithm will use the same access control policy (M,ρ) as in theEncrypt algorithm. For each row Mi of the matrix M, it computes the inner product λ~i=Mi·v~ and chooses a random exponent r~i∈Zp. Then, the algorithm defines a broadcast users set N=n∖{RLx} and outputs the ciphertext header generated by encrypting the exponent vx as follows: (5)Hdrx=RLx,C~=vx·egn,g1s~,C~0=gs~,C~1=v∏j∈Ngn+1-j-1s~,C~i,1=g1λ~ihρi-r~i,C~i,2=gr~ii=1l.Finally, it returns the ciphertext asCT′′=(CT′,Hdrx).


## 3.3.4. Key Generation

In order to improve the decryption efficiency, we outsource the decryption of ciphertext to the CSP that has plenty of computing resources. The concrete key generation algorithm is given as follows.(
4) KeyGen
(
k
e
y
g
e
n
o
u
t
(
P
K
,
M
K
,
I
D
,
S
)
→
S
K
). The key generation algorithm takes as input the public key PK, the master key MK, a user’s identity ID, and the attributes set S, and then it chooses a random exponent r′∈Zp and generates the corresponding key SK′=(K′,K~′,L′,{Ki′}i∈S), where(6)K′=gαIDγgαr′,K~′=gβgαr′,L′=gr′,Ki′=hir′i∈S.Next, the algorithm continues to choose a random exponentz∈Zp∗ and computes (7)K=K′1/z=gαIDγ1/zgαr′1/z,K~=K~′1/z=gβ1/zgαr′1/z,L=L′1/z=gr′1/z,Ki=Ki′1/z=hir′1/zi∈S.Letr=r′/z; then, we have(8)K=gαIDγ1/zgαr,K~=gβ1/zgαr,L=gr,Ki=hiri∈S.Finally, we set the outsourced transformation key asTK=(K,K~,L,{Ki=hir}i∈S) and the secret key as SK=(z,TK).


## 3.3.5. Partial Decryption

In order to achieve the outsourced decryption, the user needs to send his transformation keyTK to the CSP. Note that the transformation key cannot leak any useful information associated with the secret key SK and the plaintext data m. The concrete partial decryption algorithm is given as follows.(
5) Transform
(
transform
out
(
T
K
,
C
T
′
′
)
→
T
C
T
). The transformation algorithm takes as input the transformation key TK=(K,K~,L,{Ki=hir}i∈S) and the ciphertext CT′′=(CT′,Hdrx).(1) If there is no attribute revoked, namely,Hdrx=Φ, then we have the following.Here, we haveCT′′=((M,ρ),C,C0,{Ci,1,Ci,2}i=1l), and if the attributes set S associated with TK satisfies the access control policy (M,ρ) included in CT′′, then the CSP computes the values {wi∈Zp}i∈I satisfying ∑i∈IwiMi=(1,0,…,0) in polynomial time. Next, it computes(9)B=∏i∈IeCi,1,LwieCi,2,Kρiwi=∏i∈Ieg1λihρi-ri,grwiegri,hρirwi=eg,gαrs,D=eC0,K~=egs,gβ/zgαr=eg,gβs/zeg,gαrs,E=DB=eg,gβs/zeg,gαrseg,gαrs=eg,gβs/z.Once the partial decryption is over, the CSP sendsTCT=(C,E) to the corresponding user for the final decryption.(2) If the attributex of users list RLx is revoked, namely, Hdrx≠Φ, then we have the following.Here, we haveCT′=((M,ρ),C′,C0′,{Ci,1′,Ci,2′}i=1l) and Hdrx=(RLx,C~,C~0,C~1,{C~i,1,C~i,2}i=1l), and if the attributes set S satisfies the access control policy (M,ρ) and ID∉RLx, then the CSP implements the partial decryption on the ciphertext header Hdrx. It also computes the values {w~i∈Zp}i∈I~ satisfying ∑i∈I~w~iMi=(1,0,…,0) and then continues to compute (10)Bx=∏i∈I~eC~i,1,Lw~ieC~i,2,Kρiw~i=∏i∈I~eg1λ~ihρi-r~i,grw~ieg-r~i,hρirw~i=eg,gαrs′,Dx=eC~0,K=eg,gαIDγs~/zeg,gαrs~,Ex=DxBx=eg,gαIDγs~/z,Fx=egID,C~1e∏j∈Nj≠IDgn+1-j+ID,C~0-1=egID,v∏j∈Ngn+1-j-1s~e∏j∈Nj≠IDgn+1-j+ID,gs~-1=egID,vs~·egn+1,g-s~.Therefore, the partially decrypted ciphertext header is set asHdrx′=(C~,Ex,Fx).Next, the CSP implements the partial decryption on the ciphertextCT′ as follows:(11)Bi=eCi,1′,LeCi,2′,Kρi=eg,gαrλiρi≠x,D=eC0′,K~=egs,gβ/zgαr=eg,gβs/zeg,gαrsρi=x.Therefore, the partially decrypted ciphertext is set as(12)TCT′=M,ρ,C′=m·eg,gβs,Biρi≠x,Cx,1′,Cx,2′,D.Once the partial decryption is over, the CSP sendsTCT=(TCT′,Hdrx′) to the corresponding user for the final decryption.


## 3.3.6. Decryption

Once the user gets the partially decrypted ciphertext, he will use his secret key to implement the final decryption for obtaining the plaintext message as follows.(
6) Decrypt
(
d
e
c
r
y
p
t
(
T
C
T
,
S
K
)
→
m
). The decryption algorithm takes as input the partially decrypted ciphertext TCT and the user’s secret key SK. Then, it decrypts the ciphertext as follows:(1) If there is no attribute revoked, namely,TCT=(C,E), then the user computes(13)CEz=m·eg,gβseg,gβs/zz=m.(2) If the attributex of users list RLx is revoked, namely, TCT=(TCT′,Hdrx′), then we have the following.Here, we haveTCT′=(C′,{Bi}ρi≠x,Cx,1′,Cx,2′,D) and Hdrx′=(C~,Ex,Fx), and then the user computes (14)C~·FxExz=vx·egn,g1s~·egID,vs~·egn+1,g-s~eg,gαIDγs~/zz=vx.If the attributes setS satisfies the access control policy (M,ρ), then the CSP computes the values {wi∈Zp}i∈I satisfying ∑i∈IwiMi=(1,0,…,0) in polynomial time and continues to compute(15)Bx=eCx,1′,LeCx,2′,Kρxvx=eg1λxhρx-rx,gr·egrx1/vx,hρxrvx=eg1λx,gr=eg,gαrλx,B=∏i∈IBiwi=∏i∈Ieg,gαrλiwi=eg,gαrs,E=DB=eg,gβs/zeg,gαrseg,gαrs=eg,gβs/z,CEz=m·eg,gβseg,gβs/zz=m.


## 3.4. Security Proof

Theorem 4.
If the decisionalq-Parallel BDHE assumption holds in G and GT, then there exists no polynomial time attacker to break our proposed CP-ABE scheme with attribute level user revocation selectively, where the challenge matrix is M∗(l∗×n∗) with l∗,n∗≤q.Proof.
If there exists an attackerA who can selectively break our proposed CP-ABE scheme with a nonnegligible advantage ε=AdvA, where the challenge matrix is M∗(l∗×n∗) with l∗,n∗≤q, then we can construct a challenger B to break the decisional q-Parallel BDHE assumption successfully.Init. The challenger B takes as input a q-Parallel BDHE challenge y→,T. In addition, the attacker A gives the challenge access control policy (M∗,ρ∗) and the revocation users list RLx∗ of attribute x∗ where the matrix M∗ has n∗ columns.Setup. The challenger B chooses a random exponent β′∈Zp and computes e(g,g)β=e(g,g)β′·egα,gαq, where it implicitly sets β=β′+αq+1. In addition, it sets the broadcast users set as(16)N^=RLx∗∩1,2,…,n,N=1,2,…,n∖N^.Then,B selects a random exponent u∈Zp and sets v=gu∏k∈Ngq+1-k.Next,B sets the group parameters h1,h2,…,hU, and for each x(1≤x≤U), B selects a random exponent zx∈Zp. Let X denote the set of i satisfying ρ∗(i)=x; then, hx is set as(17)hx=gzx∏i∈XgaMi,1∗/bi·ga2Mi,2∗/bi⋯gan∗Mi,n∗∗/bi.Note that ifX=⌀, then we have hx=gzx. In addition, we can say that hx is distributed randomly because of the randomness of zx.Finally,B sends to A the public key PK as(18)PK=g,g1,…,gq,gq+2,…,g2q,v,eg,gβ,h1,…,hU.Query Phase 1. A makes to B a series of queries including the key generation query Okg and the ciphertext reencryption query Oree.(i)A makes to B a key generation query Okg associated with the identity IDj and the attributes set Sj; if IDj∉RLx∗, then we set the attributes set Sj′=Sj; otherwise, we set Sj′=Sj∖{x∗}. In addition, if Sj′ satisfies the challenge access control policy (M∗,ρ∗), then B outputs ⊥; otherwise, it generates the secret key as follows.B first computes the vector w→=(w1,…,wn∗)∈Zpn, where w1=-1, and for all ρ∗(i)∈Sj′, it satisfies Mi∗w→T=0. Note that the vector can be found in polynomial time according to the definition of LSSS.Then,B chooses a random parameter t∈Zp and defines the exponent r as(19)r=t+w1αq+w2αq-1+⋯+wn∗α.Next,B computes the key component L′ as (20)L′=gt·∏i=1,…,n∗gαq+1-iwi=gr.According to the definition ofr and w1=-1, we know that gαr includes the item g-αq+1. Although g-αq+1 is not given in the assumption, it can be canceled by multiplying gαr with gβ=gβ′gαq+1, because we implicitly set β=β′+αq+1 when generating the key component K~′. In detail, it is constructed as follows:(21)K~′=gβ′gαq+1gαtg-αq+1∏i=2,…,n∗gαq+2-iwi=gβ′gαt∏i=2,…,n∗gαq+2-iwi.Then,B will compute the key component Ki′,∀i∈Sj′. For each attribute i∈Sj′, if there exists no row k satisfying ρ∗(k)=i, then we set Ki′=(L′)zi; otherwise, let X denote the set of all the rows k satisfying ρ∗(k)=i, and then we set Ki′ as(22)Ki′=L′zi∏i∈X∏j=1,…,n∗gαj/bit·∏k=1,…,n∗,k≠jgαq+1+j-k/biwkMi,j∗.Next,B  will set the key component K′ for the user IDj∉RLx∗. Similarly, gαr includes the item g-αq+1 that is not given in the assumption. However, we set the value v as v=gu∏k∈Ngq+1-k and we have gαIDjγ=(gu∏k∈N^gq+1-k)αIDj. Moreover, because IDj∉RLx∗, namely, IDj∈N, gαIDγ includes the term gαq+1 that can be canceled by the term g-αq+1 included in gαr:(23)K′=gαIDγgαr=gu∏k∈Ngq+1-kαID·gαtg-αq+1∏i=2,…,n∗gαq+2-iwi=gαIDu∏k∈N∖IDjgq+1-k+IDj·gq+1-IDj+IDj·gαtg-αq+1∏i=2,…,n∗gαq+2-iwi=gαIDu∏k∈N∖IDjgq+1-k+IDj·gαt∏i=2,…,n∗gαq+2-iwi.Once the key components are all generated, the challengerB will select a random exponent z∈Zp∗ and set the outsourced transformation key TK as (24)TK=K=K′1/z,K~=K~′1/z,L=L′1/z,Kii∈Sj′=Ki′1/zi∈Sj′.Therefore, the secret key is set asSK=(z,TK). Finally, B sends the transformation key TK to the attacker A.(ii)A makes to B a ciphertext reencryption query Oree associated with the revocation users list RLx of attribute x and the ciphertext CT=(C,C0,{Ci,1,Ci,2}i=1l). Then, B generates the reencrypted ciphertext as follows.B first selects a random exponent vx∈Zp∗ and computes(25)CT′=C′=C,C0′=C0,ρi≠x:Ci,1′=Ci,1,Ci,2′=Ci,2,ρi=x:Ci,1′=Ci,1,Ci,2′=Ci,21/vx.Next,B selects random parameters s~,v~2,…,v~n∈Zp and defines the vector v~=(s~,v~2,…,v~n). For each row Mi of the matrix M, B computes the inner product λ~i=Mi·v~. Then, B selects a random exponent r~i∈Zp and defines the broadcast users set as N=q∖{RLx}. Finally, it encrypts the exponent vx to generate the ciphertext header as follows:(26)Hdrx∗=RLx∗,C~=vx·egn,g1s~,C~0=gs~,C~1=gus~,C~i,1=g1λ~ihρi-r~i,C-i,2=gr~ii=1l.Note thatC~1 is a correctly distributed ciphertext component which is demonstrated as follows:(27)C~1=gus~=gu∏k∈Ngq+1-k·∏j∈Ngq+1-k-1s~=v∏j∈Ngq+1-k-1s~.Therefore, the final reencrypted ciphertext is set asCT′′=(CT′,Hdrx).Challenge. The attacker A submits to the challenger B two messages m0 and m1 with the equal length. Then, B selects a random coin β∈{0,1} and generates the challenge ciphertext components as (28)C∗=mβ·T·egs,gβ′,C0∗=gs.Next,B selects random parameters y2′,…,yn∗′∈Zp and then sets the vector v→=(s,sa+y2′,sa2+y3′,…,san-1+yn∗′)∈Zpn∗ to implicitly share the key s. For i=1,2,…,n∗, B defines Ri as the set of all k≠i satisfying ρ∗(i)=ρ∗(k). Finally, B selects random exponents r1′,r2′,…,rl′∈Zp and sets the challenge ciphertext components Ci,1∗ and Ci,2∗ as follows:(29)Ci,1∗=g-ri′g-sbi,Ci,2∗=hρ∗ir′∏j=2,…,n∗gαMi,j∗yj′·gsbi-zρ∗i·∏k∈Ri∏j=1,…,n∗gαj·s·bi/bkMk,j∗.Query Phase 2. A continues to make to B a series of queries including the key generation query Okg and the ciphertext reencryption query Oree as inQuery Phase 1.Guess. The attacker A outputs its guess β′ for β. If β=β′, then A outputs 0 denoting T=e(g,g)αq+1s; otherwise, it outputs 1 denoting T is a random parameter in GT.IfT=e(g,g)αq+1s, then B plays the proper security game, so we have(30)Pr⁡By→,T=eg,gαq+1s=0=12+AdvA.Otherwise,T is a random element in GT; namely, mβ is completely random in the view of A, so we have (31)Pr⁡By→,T=R=0=12.


## 4. Analysis

In this part, we will compare our proposed CP-ABE scheme with several existing revocation schemes in terms of functionality, storage cost, communication cost, and computation efficiency. The notations that will be used are described as follows:|C1| denotes the bit size of an element in G; |CT| denotes the bit size of an element in GT; |Cp| denotes the bit size of an element in Zp∗; CT denotes the size of access control matrix associated with the ciphertext; Ck denotes the bit size of the key encryption key in Hur’s scheme [13]; t denotes the number of attributes associated with the ciphertext; k denotes the number of attributes associated with the secret key of a user; na denotes the number of all attributes in the system; nu denotes the number of all users in the system.


### 4.1. Functionality

The functionality comparison is demonstrated in Table1, from which we can see that Liang’s scheme achieve the system level user revocation; namely, once an attribute of some user is revoked, he will lose all the access permissions in the system, which is impractical in the normal application. However, our scheme, Hur’s scheme, and Yang’s scheme achieve the attribute level user revocation; namely, the revocation of some attribute has no effect on the access permissions of other legitimate attributes. In addition, compared with the generic group model of Hur’s scheme and the random oracle model of Yang’s scheme, only our scheme is provably secure based on q-Parallel BDHE assumption in the standard model, which has stronger security.Table 1
Comparison of functionalities.
Scheme
Access control granularity
Model
Assumption
Liang
System level user revocation
Standard
DBDH
Hur
Attribute level user revocation
Generic group
—
Yang
Attribute level user revocation
Random oracle
q-Parallel BDHE
Ours
Attribute level user revocation
Standard
q-Parallel BDHE


### 4.2. Storage Cost

The storage cost comparison is demonstrated in Table2. The storage cost of attribute authority (AA) is mainly generated by the master key MK. Our scheme and Hur’s scheme have short and constant master key; however, the master key in Liang’s scheme grows linearly with the number nu of all users in the system and in Yang’s scheme grows linearly with the number na of all attributes in the system. The storage cost of data owner (DO) is mainly generated by the public key PK. Hur’s scheme has the shortest public key which is constant. The public key in Yang’s scheme grows linearly with the number na of all attributes in the system and in Liang’s scheme grows linearly with the number na of all attributes and the column vector CT/t of access control matrix with each other as the slope and in our scheme grows linearly with the number na of all attributes and the number nu of all users, however, with constant slope compared with Liang’s scheme. The storage cost of cloud service provider (CSP) is mainly generated by the ciphertext and ciphertext header. Liang’s scheme only achieves user revocation in which the key updating is implemented by using the method of subset cover and the ciphertext needs not to be updated; therefore, the ciphertext grows linearly with the size CT of the access control matrix. Yang’s scheme updates the key through the interaction between the AA and the data user (DU) and also updates the corresponding ciphertext associated with the revoked attribute; therefore, the ciphertext grows linearly with the number t of attributes associated with the ciphertext. In Hur’s scheme, once the DO sends the ciphertext to the CSP, the CSP generates the corresponding ciphertext header for each attribute group. Therefore, the storage cost includes the ciphertext and ciphertext header; moreover, the ciphertext grows linearly with the number t of attributes associated with the ciphertext, and the ciphertext header grows linearly with the number t of attributes and the number nu of all users in the system with each other as the slope. In our scheme, if some attribute is revoked, then the CSP selects a new exponent to update the ciphertext corresponding to the revoked attribute and then encrypts the exponent to generate the corresponding ciphertext header. Therefore, the storage cost also includes the ciphertext and ciphertext header; moreover, the ciphertext and ciphertext header both grow linearly with the number t of attributes associated with the ciphertext. The storage cost of the DU is mainly generated by the secret key. Our scheme and Yang’s scheme have shorter secret key which grows linearly with the number k of attributes associated with the secret key. In Liang’s scheme, the secret key is generated by using a binary tree; therefore, the size of secret key is associated with the number k of attributes, the column vector CT/t of access control matrix, and the number nu of all users in the system. In addition, in Liang’s scheme, the key updating is implemented by using the method of subset cover, so the storage cost also includes the updating key that grows linearly with the smallest cover set. In Hur’s scheme, every user needs to store a plenty of key encryption keys to decrypt the corresponding exponents for key updating; therefore, the size of secret key not only grows linearly with the number k of attributes but only grows logarithmically with the number nu of all users in the system.Table 2
Comparison of storage costs.
Entity
Liang
Hur
Yang
Ours
AA
C
1
+
2
log
⁡
n
u
+
1
+
1
C
p
C
p
+
C
1
4
+
n
a
C
p
2
C
p
+
C
1
DO
C
T
/
t
⋅
n
a
+
6
|
C
1
|
+
C
T
+
C
p
2
C
1
+
C
T
2
n
a
+
4
C
1
+
C
T
n
a
+
2
n
u
+
1
C
1
+
C
T
CSP
(
C
T
+
3
)
|
C
1
|
+
|
C
T
|
2
t
+
1
C
1
+
C
T
+
t
⋅
n
u
/
2
C
p
(
3
t
+
1
)
|
C
1
|
+
|
C
T
|
4
t
+
3
C
1
+
2
C
T
DU
k
+
3
+
C
T
/
t
log
⁡
n
u
+
1
C
1
+
2
n
u
-
n
m
log
⁡
n
u
/
n
u
-
n
m
C
1
2
k
+
1
|
C
1
|
+
(
log
⁡
n
u
+
1
)
C
k
k
+
2
C
1
k
+
3
C
1
+
C
p


### 4.3. Communication Cost

The communication cost comparison is demonstrated in Table3. The communication cost is mainly generated by the key and the ciphertext. The communication cost between the attribute authority (AA) and the data user (DU) is mainly generated by the secret key of user. In Liang’s scheme, for every revocation, the AA needs to generate a new updating key which then is sent to the DU; therefore, it causes 2nu-nmlog⁡nu/nu-nm|C1| size communication cost additionally. In Yang’s scheme, for every revocation, the AA needs to communicate with the DU for updating the key; therefore, it causes 2|C1| size communication cost additionally between the AA and DU. In addition, the communication cost between the AA and data owner (DO) is mainly generated by the public key, and in Yang’s scheme, the AA needs to update the public key for every attribute revocation; therefore, it generates 2|C1| size communication cost also. The communication cost between the cloud service provider (CSP) and the DU is generated by the ciphertext, and in Hur’s scheme, the CSP needs not only to send the ciphertext but also to generate the key encryption keys, which causes log⁡nu+1Ck size communication cost; in addition, it also needs to send t·nu/2|Cp| size ciphertext header. In our proposed CP-ABE scheme, for every revoked attribute, the CSP selects a new exponent to implement the ciphertext updating and then encrypts the exponent to generate the ciphertext header, which causes (2t+2)|C1|+|CT| size communication size additionally. However, because we outsource the decryption to the CSP, the DU needs to send (k+3)|C1| size transformation key to the CSP for partial decryption. If there is no attribute revoked, then the CSP generates only two elements in GT; otherwise, the CSP generates t+1 elements in GT and two elements in G corresponding to the ciphertext and three elements in GT corresponding to the ciphertext header. In addition, the communication cost between the CSP and the DO is mainly generated by the ciphertext.Table 3
Comparison of communication costs.
Entity
Liang
Hur
Yang
Ours
AA & DU
k
+
3
+
C
T
/
t
log
⁡
n
u
+
1
C
1
+
2
n
u
-
n
m
log
⁡
n
u
/
n
u
-
n
m
C
1
2
k
+
1
C
1
k
+
4
C
1
k
+
3
C
1
+
C
p
AA & DO
(
(
C
T
/
t
)
⋅
n
a
+
6
)
|
C
1
|
+
|
C
T
|
+
|
C
p
|
2
C
1
+
C
T
2
n
a
+
6
C
1
+
C
T
n
a
+
2
n
u
+
1
C
1
+
C
T
CSP & DU
(
C
T
+
3
)
|
C
1
|
+
|
C
T
|
2
t
+
1
C
1
+
C
T
+
t
⋅
n
u
/
2
C
p
+
log
⁡
n
u
+
1
C
k
3
t
+
1
C
1
+
C
T
k
+
3
C
1
+
2
C
T
o
r
k
+
5
C
1
+
t
+
4
C
T
CSP & DO
C
T
+
3
C
1
+
C
T
2
t
+
1
C
1
+
C
T
3
t
+
1
C
1
+
C
T
2
t
+
1
C
1
+
C
T


### 4.4. Computation Efficiency

In order to evaluate the computation efficiency of our proposed CP-ABE scheme with attribute level user revocation, we implement our scheme on a 3.4 GHZ processor PC with 64-bit Ubuntu 14.04 operating system, Intel® Core™ i7-3770CPU and 4 G memory. The public key is selected to provide a 128-bit security level. In addition, the experiment uses a 160-bit elliptic curve group based on the pairing-based cryptography library (PBC-0.5.14) [20] and cpabe-0.11 [21] which selects the supersingular curve y2=x3+x over 512-bit finite field. The experimental data are obtained by computing the average value for 20 times. In this experiment, the time of PBC library computing a pairing operation is approximately 5.3 ms, and the time of computing an exponent operation in G and GT is approximately 6.2 ms and 0.6 ms, respectively. In addition, the selection time of a random element in G and GT is approximately 14 ms and 1.4 ms, respectively, by using the operation/dev/urandom in Ubuntu 14.04 operating system.In this paper, we compare our scheme with several related schemes in terms of key generation time, encryption time, decryption time, and reencryption time; moreover, we setCT/t=6,nu=8.From Figure2, we can see that the key generation time grows linearly with the number of attributes, and our key generation time is slightly higher than that of Yang’s scheme; however, it is better than that of Hur’s scheme and Liang’s scheme. In particular, the key generation time in Liang’s scheme is associated with not only the number of attributes but also the column vector CT/t of access control matrix and the number nu of all users in the system; therefore, its key generation time is much larger than the other three schemes.Figure 2
Key generation time.From Figure3, we can see that the encryption time grows linearly with the number of attributes associated with the access control policy. Our encryption time is slightly higher than that of Hur’s scheme and, however, is better than that of Yang’s scheme and Liang’s scheme. Note that the encryption in Hur’s scheme involves some polynomial operations; however, the running time is very short which is omitted here. The encryption time in Liang’s scheme is not only associated with the number of attributes corresponding to the access control policy but also associated with the column vector CT/t of access control matrix; therefore, the encryption time is much larger than the other three schemes.Figure 3
Encryption time.In the decryption experiment, the computation time is mainly influenced by the number of attributes used in decryption. In order to demonstrate the experimental results better, we suppose that all the intermediate nodes in the binary tree use the(n,n)-threshold gates. In addition, our scheme is demonstrated under two circumstances; namely, no attribute is revoked and 50% attributes are revoked. From Figure 4, we can see that the decryption time in our scheme with 50% attributes revoked, Liang’s scheme, Hur’s scheme, and Yang’s scheme grows linearly with the number of attributes used in decryption. Moreover, our scheme with no attribute revoked uses outsourced decryption, so the user needs only one exponent operation in GT. In addition, the decryption time of our scheme with 50% attributes revoked is a quadratic function for the attributes used in decryption; however, we also uses outsourced decryption which decreases the decryption time of user greatly. From Figure 4, we can see that when the number of attributes used in decryption locates in a certain range, the decryption time of our scheme with 50% attributes revoked is smaller than the other three schemes, and as the number of attributes used to decrypt increases, the decryption time goes over Yang’s scheme and Hur’s scheme successively, however, within acceptable range.Figure 4
Decryption time.In addition, the comparison of reencryption times is shown in Figure5. If there exists some attribute to be revoked, then the key or the ciphertext should be updated. Yang’s scheme and Liang’s scheme mainly implement the key updating while Hur’s scheme and our scheme mainly implement the ciphertext updating. Therefore, from Figure 5, we can see that the reencryption time in Hur’s scheme and our scheme is larger and grows linearly with the number of attributes associated with access control policy. However, all these computations are implemented by the CSP that has a plenty of computing resources. Although the reencryption time in Yang’s scheme and Liang’s scheme is shorter, it requires AA to implement the key updating. As we all know, the computation resources of AA are limited, which may be the bottleneck in the system.Figure 5
Reencryption time.


## 4.1. Functionality

The functionality comparison is demonstrated in Table1, from which we can see that Liang’s scheme achieve the system level user revocation; namely, once an attribute of some user is revoked, he will lose all the access permissions in the system, which is impractical in the normal application. However, our scheme, Hur’s scheme, and Yang’s scheme achieve the attribute level user revocation; namely, the revocation of some attribute has no effect on the access permissions of other legitimate attributes. In addition, compared with the generic group model of Hur’s scheme and the random oracle model of Yang’s scheme, only our scheme is provably secure based on q-Parallel BDHE assumption in the standard model, which has stronger security.Table 1
Comparison of functionalities.
Scheme
Access control granularity
Model
Assumption
Liang
System level user revocation
Standard
DBDH
Hur
Attribute level user revocation
Generic group
—
Yang
Attribute level user revocation
Random oracle
q-Parallel BDHE
Ours
Attribute level user revocation
Standard
q-Parallel BDHE


## 4.2. Storage Cost

The storage cost comparison is demonstrated in Table2. The storage cost of attribute authority (AA) is mainly generated by the master key MK. Our scheme and Hur’s scheme have short and constant master key; however, the master key in Liang’s scheme grows linearly with the number nu of all users in the system and in Yang’s scheme grows linearly with the number na of all attributes in the system. The storage cost of data owner (DO) is mainly generated by the public key PK. Hur’s scheme has the shortest public key which is constant. The public key in Yang’s scheme grows linearly with the number na of all attributes in the system and in Liang’s scheme grows linearly with the number na of all attributes and the column vector CT/t of access control matrix with each other as the slope and in our scheme grows linearly with the number na of all attributes and the number nu of all users, however, with constant slope compared with Liang’s scheme. The storage cost of cloud service provider (CSP) is mainly generated by the ciphertext and ciphertext header. Liang’s scheme only achieves user revocation in which the key updating is implemented by using the method of subset cover and the ciphertext needs not to be updated; therefore, the ciphertext grows linearly with the size CT of the access control matrix. Yang’s scheme updates the key through the interaction between the AA and the data user (DU) and also updates the corresponding ciphertext associated with the revoked attribute; therefore, the ciphertext grows linearly with the number t of attributes associated with the ciphertext. In Hur’s scheme, once the DO sends the ciphertext to the CSP, the CSP generates the corresponding ciphertext header for each attribute group. Therefore, the storage cost includes the ciphertext and ciphertext header; moreover, the ciphertext grows linearly with the number t of attributes associated with the ciphertext, and the ciphertext header grows linearly with the number t of attributes and the number nu of all users in the system with each other as the slope. In our scheme, if some attribute is revoked, then the CSP selects a new exponent to update the ciphertext corresponding to the revoked attribute and then encrypts the exponent to generate the corresponding ciphertext header. Therefore, the storage cost also includes the ciphertext and ciphertext header; moreover, the ciphertext and ciphertext header both grow linearly with the number t of attributes associated with the ciphertext. The storage cost of the DU is mainly generated by the secret key. Our scheme and Yang’s scheme have shorter secret key which grows linearly with the number k of attributes associated with the secret key. In Liang’s scheme, the secret key is generated by using a binary tree; therefore, the size of secret key is associated with the number k of attributes, the column vector CT/t of access control matrix, and the number nu of all users in the system. In addition, in Liang’s scheme, the key updating is implemented by using the method of subset cover, so the storage cost also includes the updating key that grows linearly with the smallest cover set. In Hur’s scheme, every user needs to store a plenty of key encryption keys to decrypt the corresponding exponents for key updating; therefore, the size of secret key not only grows linearly with the number k of attributes but only grows logarithmically with the number nu of all users in the system.Table 2
Comparison of storage costs.
Entity
Liang
Hur
Yang
Ours
AA
C
1
+
2
log
⁡
n
u
+
1
+
1
C
p
C
p
+
C
1
4
+
n
a
C
p
2
C
p
+
C
1
DO
C
T
/
t
⋅
n
a
+
6
|
C
1
|
+
C
T
+
C
p
2
C
1
+
C
T
2
n
a
+
4
C
1
+
C
T
n
a
+
2
n
u
+
1
C
1
+
C
T
CSP
(
C
T
+
3
)
|
C
1
|
+
|
C
T
|
2
t
+
1
C
1
+
C
T
+
t
⋅
n
u
/
2
C
p
(
3
t
+
1
)
|
C
1
|
+
|
C
T
|
4
t
+
3
C
1
+
2
C
T
DU
k
+
3
+
C
T
/
t
log
⁡
n
u
+
1
C
1
+
2
n
u
-
n
m
log
⁡
n
u
/
n
u
-
n
m
C
1
2
k
+
1
|
C
1
|
+
(
log
⁡
n
u
+
1
)
C
k
k
+
2
C
1
k
+
3
C
1
+
C
p


## 4.3. Communication Cost

The communication cost comparison is demonstrated in Table3. The communication cost is mainly generated by the key and the ciphertext. The communication cost between the attribute authority (AA) and the data user (DU) is mainly generated by the secret key of user. In Liang’s scheme, for every revocation, the AA needs to generate a new updating key which then is sent to the DU; therefore, it causes 2nu-nmlog⁡nu/nu-nm|C1| size communication cost additionally. In Yang’s scheme, for every revocation, the AA needs to communicate with the DU for updating the key; therefore, it causes 2|C1| size communication cost additionally between the AA and DU. In addition, the communication cost between the AA and data owner (DO) is mainly generated by the public key, and in Yang’s scheme, the AA needs to update the public key for every attribute revocation; therefore, it generates 2|C1| size communication cost also. The communication cost between the cloud service provider (CSP) and the DU is generated by the ciphertext, and in Hur’s scheme, the CSP needs not only to send the ciphertext but also to generate the key encryption keys, which causes log⁡nu+1Ck size communication cost; in addition, it also needs to send t·nu/2|Cp| size ciphertext header. In our proposed CP-ABE scheme, for every revoked attribute, the CSP selects a new exponent to implement the ciphertext updating and then encrypts the exponent to generate the ciphertext header, which causes (2t+2)|C1|+|CT| size communication size additionally. However, because we outsource the decryption to the CSP, the DU needs to send (k+3)|C1| size transformation key to the CSP for partial decryption. If there is no attribute revoked, then the CSP generates only two elements in GT; otherwise, the CSP generates t+1 elements in GT and two elements in G corresponding to the ciphertext and three elements in GT corresponding to the ciphertext header. In addition, the communication cost between the CSP and the DO is mainly generated by the ciphertext.Table 3
Comparison of communication costs.
Entity
Liang
Hur
Yang
Ours
AA & DU
k
+
3
+
C
T
/
t
log
⁡
n
u
+
1
C
1
+
2
n
u
-
n
m
log
⁡
n
u
/
n
u
-
n
m
C
1
2
k
+
1
C
1
k
+
4
C
1
k
+
3
C
1
+
C
p
AA & DO
(
(
C
T
/
t
)
⋅
n
a
+
6
)
|
C
1
|
+
|
C
T
|
+
|
C
p
|
2
C
1
+
C
T
2
n
a
+
6
C
1
+
C
T
n
a
+
2
n
u
+
1
C
1
+
C
T
CSP & DU
(
C
T
+
3
)
|
C
1
|
+
|
C
T
|
2
t
+
1
C
1
+
C
T
+
t
⋅
n
u
/
2
C
p
+
log
⁡
n
u
+
1
C
k
3
t
+
1
C
1
+
C
T
k
+
3
C
1
+
2
C
T
o
r
k
+
5
C
1
+
t
+
4
C
T
CSP & DO
C
T
+
3
C
1
+
C
T
2
t
+
1
C
1
+
C
T
3
t
+
1
C
1
+
C
T
2
t
+
1
C
1
+
C
T


## 4.4. Computation Efficiency

In order to evaluate the computation efficiency of our proposed CP-ABE scheme with attribute level user revocation, we implement our scheme on a 3.4 GHZ processor PC with 64-bit Ubuntu 14.04 operating system, Intel® Core™ i7-3770CPU and 4 G memory. The public key is selected to provide a 128-bit security level. In addition, the experiment uses a 160-bit elliptic curve group based on the pairing-based cryptography library (PBC-0.5.14) [20] and cpabe-0.11 [21] which selects the supersingular curve y2=x3+x over 512-bit finite field. The experimental data are obtained by computing the average value for 20 times. In this experiment, the time of PBC library computing a pairing operation is approximately 5.3 ms, and the time of computing an exponent operation in G and GT is approximately 6.2 ms and 0.6 ms, respectively. In addition, the selection time of a random element in G and GT is approximately 14 ms and 1.4 ms, respectively, by using the operation/dev/urandom in Ubuntu 14.04 operating system.In this paper, we compare our scheme with several related schemes in terms of key generation time, encryption time, decryption time, and reencryption time; moreover, we setCT/t=6,nu=8.From Figure2, we can see that the key generation time grows linearly with the number of attributes, and our key generation time is slightly higher than that of Yang’s scheme; however, it is better than that of Hur’s scheme and Liang’s scheme. In particular, the key generation time in Liang’s scheme is associated with not only the number of attributes but also the column vector CT/t of access control matrix and the number nu of all users in the system; therefore, its key generation time is much larger than the other three schemes.Figure 2
Key generation time.From Figure3, we can see that the encryption time grows linearly with the number of attributes associated with the access control policy. Our encryption time is slightly higher than that of Hur’s scheme and, however, is better than that of Yang’s scheme and Liang’s scheme. Note that the encryption in Hur’s scheme involves some polynomial operations; however, the running time is very short which is omitted here. The encryption time in Liang’s scheme is not only associated with the number of attributes corresponding to the access control policy but also associated with the column vector CT/t of access control matrix; therefore, the encryption time is much larger than the other three schemes.Figure 3
Encryption time.In the decryption experiment, the computation time is mainly influenced by the number of attributes used in decryption. In order to demonstrate the experimental results better, we suppose that all the intermediate nodes in the binary tree use the(n,n)-threshold gates. In addition, our scheme is demonstrated under two circumstances; namely, no attribute is revoked and 50% attributes are revoked. From Figure 4, we can see that the decryption time in our scheme with 50% attributes revoked, Liang’s scheme, Hur’s scheme, and Yang’s scheme grows linearly with the number of attributes used in decryption. Moreover, our scheme with no attribute revoked uses outsourced decryption, so the user needs only one exponent operation in GT. In addition, the decryption time of our scheme with 50% attributes revoked is a quadratic function for the attributes used in decryption; however, we also uses outsourced decryption which decreases the decryption time of user greatly. From Figure 4, we can see that when the number of attributes used in decryption locates in a certain range, the decryption time of our scheme with 50% attributes revoked is smaller than the other three schemes, and as the number of attributes used to decrypt increases, the decryption time goes over Yang’s scheme and Hur’s scheme successively, however, within acceptable range.Figure 4
Decryption time.In addition, the comparison of reencryption times is shown in Figure5. If there exists some attribute to be revoked, then the key or the ciphertext should be updated. Yang’s scheme and Liang’s scheme mainly implement the key updating while Hur’s scheme and our scheme mainly implement the ciphertext updating. Therefore, from Figure 5, we can see that the reencryption time in Hur’s scheme and our scheme is larger and grows linearly with the number of attributes associated with access control policy. However, all these computations are implemented by the CSP that has a plenty of computing resources. Although the reencryption time in Yang’s scheme and Liang’s scheme is shorter, it requires AA to implement the key updating. As we all know, the computation resources of AA are limited, which may be the bottleneck in the system.Figure 5
Reencryption time.


## 5. Conclusion

In this paper, we propose a CP-ABE scheme which can achieve the attribute level user revocation. In this scheme, if some attribute of a user is revoked, then the ciphertext corresponding to the revoked attribute is updated so that only the user, whose attributes set satisfies the access control policy and has not been revoked, can carry out the key updating to decrypt the ciphertext successfully. The security of our scheme is proved secure based on theq-Parallel BDHE assumption in the standard model. Finally, the performance analysis and experimental verification are carried out, and the experimental results show that although our scheme increases the computation cost of the CSP in order to achieve the attribute revocation, it does not require the participation of the AA, which decreases the computation cost of the AA. Moreover, the user does not need to store additional parameters to carry out the attribute revocation; thus, it greatly saves the storage space.



---

*Source: 4070616-2017-05-23.xml*