# You Are Revoked and Out: Towards Directly Revocable Ciphertext-Policy Attribute-Based Encryption

Authors: Feng Yang; Limin Liu; Weijing You; Jiwu Jing
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Ciphertext-policy attributed-based encryption (CP-ABE) is considered as a promising cryptographic primitive to enable fine-grained access control over encrypted data. Throughout the life circle of the data encrypted with CP-ABE, every single data user might opt out or be identified to be malicious and hence should be revoked to keep continuous access control over sensitive data. In this study, we propose a directly revocable CP-ABE with backward and forward secrecy, which means that a revoked user cannot successfully decrypt ciphertexts after sufficient revocation while valid users will not be disturbed. Combined with an effective proxy mechanism, the proposed scheme delegates complete workloads of re-encryption and ciphertext updating to a semi-trusted third party (e.g., a cloud service provider). In addition, even collusion among users is useless in our construction, which is not well addressed in previous works. The security analysis indicates that the presented CP-ABE is selectively secure against chosen-plaintext attacks in the standard model, and the performance analysis demonstrates that our proposal is practical compared with existing schemes.


---

## Body

## 1. Introduction

Nowadays, cloud computing has been increasingly used to facilitate data sharing [1]. For security purposes, cloud users often encrypt their data before outsourcing. However, when cloud users selectively share data to different recipients, it would be expensive to generate different encrypted data and transmit them respectively. A fine-grained level of access control over encrypted data in the cloud is desirable. Sahai and Waters [2] firstly address this obstacle by introducing attribute-based encryption (ABE), in which a user’s decryption keys and ciphertexts are labeled with a set of descriptive attributes, and the ciphertext can be decrypted only when there exists a “match” between attributes of this ciphertext and the decryption key. Based on where the access policies are embedded, ABE can be categorized into key-policy attribute-based encryption (KP-ABE) [3] and ciphertext-policy attribute-based encryption (CP-ABE) [4]. In a CP-ABE system, an access policy is specified in a ciphertext, while users obtain different decryption keys based on their own attributes. Since the access policy is embedded in the ciphertext and fully controlled by the data owner in CP-ABE, we focus on CP-ABE in this study. For instance, Alice owns an attribute set {“Student”, “Computer Science” ,“Undergraduate”}, Bob owns an attribute set {“Professor” ,“Computer Science” ,“In-Service”}, and Carol owns an attribute set {“Professor” ,“Astronomy” ,“Retired”}. Suppose that there is a ciphertext generated under the access policy {“Professor” AND “In-Service”}. Since only Bob has the attributes “Professor” and “In-Service” simultaneously, Bob can decrypt successfully.The access control is a fundamental functionality of CP-ABE, which definitely should be effective throughout the entire life circle of the encrypted data. However, the time for each user to get access to the data is not always identical, especially in the flexible clouds, and the users could be expired at different points. In addition, a user might lose its decryption key carelessly or disclose the key intensively for economic purposes, which can be detected by supporting traceability in CP-ABE [5–7].But if the revocation is missing in CP-ABE system, the traceability will become meaningless, and the access to the data will be disclosed to an unauthorized party, which violates the fundamental property of ABE system, i.e., the continuous access control. Therefore, an effective revocation mechanism is strongly desirable for the traceable CP-ABE.In a CP-ABE with revocation mechanism, the expired users or valid users whose decryption keys are disclosed should be blocked out of accessing the data to become who are called “revoked users” in general. A data user could retrieve the original data successfully if and only if the attribute sets he/she possesses can satisfy the access policy and, more, his/her identity is absent from the revocation list. In the light of the effect on non-revoked users, the revocation is categorized into indirect revocation [8–11] and direct revocation [12–15]. The difference lies in whether the non-revoked users’ decryption keys should be updated when a revocation event occurs.In indirect revocation schemes, the authority periodically issues key updates for non-revoked users. In addition, all non-revoked users need to communicate with the authority and update their decryption keys. In particular, the indirect revocation also consists of two stages. Firstly, the original indirect revocation mechanism was adopted from identity-based encryption (IBE) [16]. In the Boneh and Franklin construction [16], each user’s decryption key will expire after a valid period, so the revocation can be achieved by stopping issuing new decryption keys for revoked users. However, such a straightforward revocation brings a relatively large computational and communication overhead. The authority needs to generate a new decryption key for each non-revoked user separately and transmit it over a secure channel. Secondly, to improve the efficiency of key updates, Boldyreva et al. [17] introduced a binary tree data structure [18], in which each user is associated with a unique leaf node. Every user gets decryption keys computed on nodes of the path from the leaf node (corresponding to that user) to the root node. It means that different users would share some nodes in their path from a leaf node to the root node; for example, all users will share the root node. In this way, when a subset of the data users is revoked, we can find a minimum cover set of nodes that contains an ancestor (or the node itself) for each leaf node related to a non-revoked user. Then, the key update can be performed within this subset, thereby reducing the workload from linear to logarithmic in the number of non-revoked users.After the work of Boldyreva et al. [17], many indirectly revocable CP-ABE schemes [8–11, 19–21] that adopted binary tree data structure have been proposed. However, apart from the natural expiration, a data user may lose its decryption key or disclose the key deliberately for economic purposes. Such a user is supposed to be revoked immediately to guarantee continuous access control. In direct revocation mechanisms, a data owner embeds the latest revocation list into the ciphertext during the encryption phase so that the revoked users cannot decrypt a newly generated ciphertext anymore. There is no need for any key update. Even though in an indirect revocation, a data owner does not need to care about the revocation list. Since the revocation list can be published by the authority, it is not a tough task for a data owner to obtain the latest revocation list. Considering that in a traceable CP-ABE, when a malicious user is caught, it should be revoked immediately. A direct revocation mechanism is more suitable for traceable systems. Some researchers [15, 22] adapted the binary tree data structure into direct revocable constructions and realized traceable and revocable CP-ABE systems.However, most of the existing revocable CP-ABE schemes either do not support traceability or cannot resist collusion between a revoked user and a non-revoked user. One may think that we do not need to focus on such attacks since a non-revoked user can naturally decrypt the ciphertext and share the plaintext with a revoked user, but we note that this may only be somewhat acceptable in a CP-ABE without a traceable functionality. More concretely, in a CP-ABE with white-box traceability [15, 22], the system can catch a malicious user who discloses his/her decryption key (e.g., selling the key online). The trace mechanism needs a full disclosed decryption key to identify the malicious user. It will not work if there is only a partial decryption key. As a result, the trace mechanism would be meaningless if a non-revoked user’s partial decryption key is enough to restore a revoked user’s decryption privileges. Moreover, since it has been already supposed that a non-revoked user might disclose the full decryption key deliberately in a traceable CP-ABE, we can no longer require the user not to disclose a partial decryption key in a revocable CP-ABE that supports traceability. If a user is willing to disclose a full decryption key, he/she can reveal a partial decryption key since it will be safer than disclosing the full one. Therefore, for such a traceable and revocable CP-ABE scheme, the key generation is supposed to be completely controlled by the trusted authority, and any part of another user’s decryption key should be useless to revalidate a revoked user’s decryption key.Some researches [10, 19] focus on resisting the collusion between a revoked user and a non-revoked user, but these are indirectly revocable schemes and do not support traceability.There are another two special security properties that should be considered in revocable access control systems: forward secrecy and backward secrecy [23]. Forward secrecy and backward secrecy mean that a revoked user should be prevented from decrypting the subsequent and previous ciphertexts, respectively. Only systems that support both forward secrecy and backward secrecy can prevent a revoked user from learning any sensitive data [8]. Forward secrecy is implicitly realized during revocation, and a revoked user cannot access the data encrypted after the revocation. As the decryption key of a revoked user is still able to decrypt the ciphertext generated previously, a ciphertext update algorithm is further needed to achieve backward secrecy. An intuitive solution to handle this problem is to decrypt and re-encrypt the stored data whenever some users are revoked. However, this two-way communication makes the system cumbersome and inefficient. Sahai et al. [8] firstly discussed this situation and dealt with it by introducing a ciphertext delegation that allows a ciphertext to be updated using only public information. In the follow-up schemes, ciphertext update falls into two types: partial update [24, 25] and full update [26–29]. In the partial update, only those components associated with the revocation mechanism are updated. In the full update, almost all components except the underlying plaintext will be updated. The latter provides better protection as any intermediate values computed for the previous ciphertext will be useless for decrypting the refreshed ciphertext. Among recent published schemes that support ciphertext update functionality [24–29], only Li et al. [25] and Sethi et al. [27] realized traceability, but the access policy of [25] can only be expressed as AND gate that sacrifices the flexibility and expressiveness of the CP-ABE. Sethi et al. [27] adopted the expressive linear secret-sharing schemes (LSSS) into access policy, but their proposal is an indirect revocable scheme that allows malicious users to maintain decryption capabilities until the next key update.Traceable and revocable CP-ABE is a promising solution for data sharing and life cycle access control, but a large number of complex bilinear group operations bring non-negligible computational pressure on resource-constrained devices (e.g., mobile phones and IoT systems) or time-sensitive devices (e.g., ad-hoc vehicular networks).We revisit the existing CP-ABE schemes and find that most of them only focus on one specific functionality, or do not fully consider the compatibility between different functionalities. This hinders the CP-ABE for real-world applications. Motivated by the aforementioned limitations, we aim to propose a practical solution towards traceable and revocable CP-ABE for cloud computing applications. In this work, we build a directly revocable CP-ABE with traceability and ciphertext update to catch a malicious user and then revoke it immediately and achieve forward and backward secrecy. Besides, we present the ciphertext delegation to outsource to a semi-trusted third party (e.g., cloud service provider) the burden of re-encryption and updating ciphertexts, which is friendly to users with limited computing resources.


### 1.1. Contribution

The main contributions of the scheme developed in this study are as follows:(i)
Direct Revocation. We realize a directly revocable CP-ABE scheme whereby a revoked user cannot successfully decrypt ciphertexts anymore after the sufficient revocation, while legitimate (non-revoked) users will not be disturbed. We adopt the binary tree data structure to improve efficiency. Besides, our direct revocation mechanism saves the communication overhead between the authority and non-revoked users since there is no additional periodic key update.(ii)
Collusion Resistance. In our scheme, any component of another user’s decryption key will make no sense in revalidating a revoked user’s decryption key. As a white-box trace mechanism can identify a malicious user who discloses a full decryption key, the collusion resistance capability is necessary for ensuring the effectiveness of white-box traceability in CP-ABE. Combined with our revocation mechanism, we succeed in a continuous process from discovering malicious users to revoking malicious users.(iii)
Friendly to Resource-Constrained Devices. We propose a ciphertext delegation mechanism composed of an outsourced re-encryption algorithm and an outsourced ciphertext update algorithm. The algorithms make good use of computing resources provided by a semi-trusted party (e.g., a cloud service provider), reducing data owners’ burden in terms of communication and computation.(iv)
IND-CPA Secure. The scheme is proven secure in the security definition of indistinguishability under selective chosen-plaintext attacks (IND-CPA secure) in the standard model based on the decisional q-BDHE assumption.


### 1.2. Organization

The rest of the study is organized as follows. In Section2, we review necessary preliminaries used in our scheme. The formal definition and security model are described in Section 3. Section 4 presents the concrete structure of the scheme. The security analysis is given in Section 5. Comparisons of the proposed scheme are made with several related works in Section 6. Section 7 introduces some related works. Section 8 offers a conclusion.


## 1.1. Contribution

The main contributions of the scheme developed in this study are as follows:(i)
Direct Revocation. We realize a directly revocable CP-ABE scheme whereby a revoked user cannot successfully decrypt ciphertexts anymore after the sufficient revocation, while legitimate (non-revoked) users will not be disturbed. We adopt the binary tree data structure to improve efficiency. Besides, our direct revocation mechanism saves the communication overhead between the authority and non-revoked users since there is no additional periodic key update.(ii)
Collusion Resistance. In our scheme, any component of another user’s decryption key will make no sense in revalidating a revoked user’s decryption key. As a white-box trace mechanism can identify a malicious user who discloses a full decryption key, the collusion resistance capability is necessary for ensuring the effectiveness of white-box traceability in CP-ABE. Combined with our revocation mechanism, we succeed in a continuous process from discovering malicious users to revoking malicious users.(iii)
Friendly to Resource-Constrained Devices. We propose a ciphertext delegation mechanism composed of an outsourced re-encryption algorithm and an outsourced ciphertext update algorithm. The algorithms make good use of computing resources provided by a semi-trusted party (e.g., a cloud service provider), reducing data owners’ burden in terms of communication and computation.(iv)
IND-CPA Secure. The scheme is proven secure in the security definition of indistinguishability under selective chosen-plaintext attacks (IND-CPA secure) in the standard model based on the decisional q-BDHE assumption.


## 1.2. Organization

The rest of the study is organized as follows. In Section2, we review necessary preliminaries used in our scheme. The formal definition and security model are described in Section 3. Section 4 presents the concrete structure of the scheme. The security analysis is given in Section 5. Comparisons of the proposed scheme are made with several related works in Section 6. Section 7 introduces some related works. Section 8 offers a conclusion.


## 2. Preliminaries

This section describes the necessary background information for the proposed scheme, including bilinear maps, access structures, secret-sharing schemes, binary trees, and hardness assumptions.


### 2.1. Access Structure

Definition 1 (Access Structure [30]).
LetP=P1,P2,…,Pn be a set of parties. A collection A⊆2P is called monotone if ∀B,C: if B∈A and B⊆C, then C∈A. The (monotone) access structure is a (monotone) collection A of non-empty subsets of P, i.e., A⊆2P/∅. The sets in A are called authorized sets, or else the sets are called the unauthorized sets.
In CP-ABE, since the role of the parties is taken by the attributes, the access structure contains the authorized sets of attributes. We restrict our attention to the monotone access structure in this study.


### 2.2. Linear Secret-Sharing Scheme

Definition 2 (Linear Secret-Sharing Schemes (LSSS) [31]).
A secret-sharing schemeΠ over a set of parties P is called linear (over ℤp) if(i)
The shares for each party form a vector overℤp.(ii)
There exists a matrix M withℓ rows and n columns called the share-generating matrix for Π. For i=1,2,…,ℓ, the i’th row Mi of M is labeled by a party ρi, where ρ is a function that maps a row of M into a party ∈P. Consider the column vector v⟶=s,t2,t3,…,tn, where s∈ℤp is the secret to be shared and t2,t3,…,tn∈ℤp are randomly selected. Then, Mv⟶ is the vector of l shares of the secret s; here, the share λi=Mi⋅v⟶ belongs to the corresponding party ρi.
It is shown in [32] that according to the above definition, each secret-sharing scheme also enjoys the linear reconstruction property, defined as follows.
Assuming thatΠ is an LSSS for the access structure A, suppose S∈A is any authorized set, and let I∈1,2,…,ℓ be defined as I=i:ρi∈S. There exists a set of constants wi∈ℤpi∈I satisfying that ∑i∈IwiMi=1,0,…,0, such that, if λi are valid shares of the secret s according to Π, we have ∑i∈Iwiλi=s. In addition, those constants wi can be found in polynomial time in the size of the share-generating matrix M [32].


### 2.3. Binary Tree

LetU be the set of users and R be the revocation list in system. A binary tree will be used in both key generation and ciphertext generation processes. Now, we briefly introduce the binary tree BT [15] as follows. A leaf node in the binary tree is associated with a user in the system. Let d denote the depth of the binary tree, we have U=2d, and the number of nodes in this tree is 2U−1. Those nodes are numbered by the breadth-first search; as such, the root is 0 and the last node is 2U−2. Let pathu=root,…,uid denote the path from the root to a leaf node related to u, where root denotes the root node, and uid is the leaf node associated with the user u. The minimum cover set coverR is a minimum set of nodes that cover all users who are not in the revocation list R. Note that for ∀u∈R, we have coverR∩pathu=∅. As for user u∉R, there exists only one node in the intersection of coverR and pathu.We take Figure1 as an example of the binary tree and by supposing that the revoked user is u5 such that revocation list R=u5. Then, we get coverR=1,6,12. For a non-revoked user, u1 for example, pathu1=0,1,3,7. The interaction of coverR and pathu1 is {1}.Figure 1
Binary tree. (a) No user is revoked.R=∅ and coverR=0. (b) User u5 is revoked. R=u5 and coverR=1,6,12.
(a)(b)


### 2.4. Bilinear Map and Complexity Assumptions

In this section, we first introduce the bilinear map used in our scheme and then briefly describe theq-bilinear Diffie–Hellman exponent (q-BDHE) assumption and the l-strong Diffie–Hellman (l-SDH) assumption, which will be used to prove the security of the proposed scheme.Bilinear Map. Let G and GT be two multiplicative cycle groups with prime order p, and g be a generator of G. A map e:G×G⟶GT is a bilinear map [16] if it satisfies the properties:(i)
Bilinearity: for∀u,v∈G,a,b∈ℤp∗,eua,vb=eub,va=eu,vab(ii)
Non-Degeneracy:eu,v≠1(iii)
Computability: for∀u,v∈G, there exists an efficient algorithm to compute eu,vAssumption 1 (q-BDHE Assumption [31]).
LetG be a bilinear group of prime order p, and let g be a generator of G. A decisional q-BDHE problem can be described as follows: d,s∈ℤp∗ is randomly chosen and given as follows:(1)y⟶=g,gs,gd,…,gdq,gdq+2,…,gd2q.
It is hard for the algorithmA to distinguish eg,gdq+1s∈GT from an element Z, which is randomly chosen from GT. Algorithm A can solve the q-BDHE problem with the advantage ε if(2)PrAy⟶,T=eg,gdq+1s=0−PrAy⟶,T=Z=0≥ε.Definition 3.
The decisionalq-BDHE assumption holds, if no polynomial-time algorithm A has a non-negligible advantage in solving the q-BDHE problem.Assumption 2 (l-SDH Assumption [33]).
LetG be a bilinear group of prime order p, and let g be a generator of G. An l-SDH problem can be described as follows: x∈ℤp∗ is randomly chosen, and given a l+1-tuple g,gx,gx2,…,gxl, a pair c,g1/x+c∈ℤp×G is output.
AlgorithmA can solve the l-SDH problem with the advantage ε if(3)PrAg,gx,gx2,…,gxl=c,g1/x+c≥ε.Definition 4.
Thel-SDH assumption holds, if no polynomial-time algorithm A can solve the l-SDH problem with a non-negligible advantage.


## 2.1. Access Structure

Definition 1 (Access Structure [30]).
LetP=P1,P2,…,Pn be a set of parties. A collection A⊆2P is called monotone if ∀B,C: if B∈A and B⊆C, then C∈A. The (monotone) access structure is a (monotone) collection A of non-empty subsets of P, i.e., A⊆2P/∅. The sets in A are called authorized sets, or else the sets are called the unauthorized sets.
In CP-ABE, since the role of the parties is taken by the attributes, the access structure contains the authorized sets of attributes. We restrict our attention to the monotone access structure in this study.


## 2.2. Linear Secret-Sharing Scheme

Definition 2 (Linear Secret-Sharing Schemes (LSSS) [31]).
A secret-sharing schemeΠ over a set of parties P is called linear (over ℤp) if(i)
The shares for each party form a vector overℤp.(ii)
There exists a matrix M withℓ rows and n columns called the share-generating matrix for Π. For i=1,2,…,ℓ, the i’th row Mi of M is labeled by a party ρi, where ρ is a function that maps a row of M into a party ∈P. Consider the column vector v⟶=s,t2,t3,…,tn, where s∈ℤp is the secret to be shared and t2,t3,…,tn∈ℤp are randomly selected. Then, Mv⟶ is the vector of l shares of the secret s; here, the share λi=Mi⋅v⟶ belongs to the corresponding party ρi.
It is shown in [32] that according to the above definition, each secret-sharing scheme also enjoys the linear reconstruction property, defined as follows.
Assuming thatΠ is an LSSS for the access structure A, suppose S∈A is any authorized set, and let I∈1,2,…,ℓ be defined as I=i:ρi∈S. There exists a set of constants wi∈ℤpi∈I satisfying that ∑i∈IwiMi=1,0,…,0, such that, if λi are valid shares of the secret s according to Π, we have ∑i∈Iwiλi=s. In addition, those constants wi can be found in polynomial time in the size of the share-generating matrix M [32].


## 2.3. Binary Tree

LetU be the set of users and R be the revocation list in system. A binary tree will be used in both key generation and ciphertext generation processes. Now, we briefly introduce the binary tree BT [15] as follows. A leaf node in the binary tree is associated with a user in the system. Let d denote the depth of the binary tree, we have U=2d, and the number of nodes in this tree is 2U−1. Those nodes are numbered by the breadth-first search; as such, the root is 0 and the last node is 2U−2. Let pathu=root,…,uid denote the path from the root to a leaf node related to u, where root denotes the root node, and uid is the leaf node associated with the user u. The minimum cover set coverR is a minimum set of nodes that cover all users who are not in the revocation list R. Note that for ∀u∈R, we have coverR∩pathu=∅. As for user u∉R, there exists only one node in the intersection of coverR and pathu.We take Figure1 as an example of the binary tree and by supposing that the revoked user is u5 such that revocation list R=u5. Then, we get coverR=1,6,12. For a non-revoked user, u1 for example, pathu1=0,1,3,7. The interaction of coverR and pathu1 is {1}.Figure 1
Binary tree. (a) No user is revoked.R=∅ and coverR=0. (b) User u5 is revoked. R=u5 and coverR=1,6,12.
(a)(b)


## 2.4. Bilinear Map and Complexity Assumptions

In this section, we first introduce the bilinear map used in our scheme and then briefly describe theq-bilinear Diffie–Hellman exponent (q-BDHE) assumption and the l-strong Diffie–Hellman (l-SDH) assumption, which will be used to prove the security of the proposed scheme.Bilinear Map. Let G and GT be two multiplicative cycle groups with prime order p, and g be a generator of G. A map e:G×G⟶GT is a bilinear map [16] if it satisfies the properties:(i)
Bilinearity: for∀u,v∈G,a,b∈ℤp∗,eua,vb=eub,va=eu,vab(ii)
Non-Degeneracy:eu,v≠1(iii)
Computability: for∀u,v∈G, there exists an efficient algorithm to compute eu,vAssumption 1 (q-BDHE Assumption [31]).
LetG be a bilinear group of prime order p, and let g be a generator of G. A decisional q-BDHE problem can be described as follows: d,s∈ℤp∗ is randomly chosen and given as follows:(1)y⟶=g,gs,gd,…,gdq,gdq+2,…,gd2q.
It is hard for the algorithmA to distinguish eg,gdq+1s∈GT from an element Z, which is randomly chosen from GT. Algorithm A can solve the q-BDHE problem with the advantage ε if(2)PrAy⟶,T=eg,gdq+1s=0−PrAy⟶,T=Z=0≥ε.Definition 3.
The decisionalq-BDHE assumption holds, if no polynomial-time algorithm A has a non-negligible advantage in solving the q-BDHE problem.Assumption 2 (l-SDH Assumption [33]).
LetG be a bilinear group of prime order p, and let g be a generator of G. An l-SDH problem can be described as follows: x∈ℤp∗ is randomly chosen, and given a l+1-tuple g,gx,gx2,…,gxl, a pair c,g1/x+c∈ℤp×G is output.
AlgorithmA can solve the l-SDH problem with the advantage ε if(3)PrAg,gx,gx2,…,gxl=c,g1/x+c≥ε.Definition 4.
Thel-SDH assumption holds, if no polynomial-time algorithm A can solve the l-SDH problem with a non-negligible advantage.


## 3. System and Security Models

In this section, we give the system architecture of the proposed CP-ABE scheme and formalize its definition and security model.


### 3.1. System Architecture

The four entities in the system architecture are as follows:(i)
Trusted Authority (TA). TA publishes the public parameters of the system, generates decryption keys for non-revoked users, and is in charge of realizing traceability and updating the user revocation listR. In our system, the TA is fully trusted.(ii)
Data Owner (DO). DO takes charge of specifying an access structure and of completing the local encryption under the access structure before outsourcing to a cloud service provider.(iii)
Cloud Service Provider (CSP). CSP is responsible for re-encrypting the original ciphertext that DO upload and storing the re-encrypted ciphertext. CSP undertakes the task of updating ciphertexts once a revocation event occurs. We suppose that the CSP is honest but curious, which means CSP will faithfully execute every authorization request and not disclose the data, but attempt to obtain as much information as possible from both process and results.(iv)
Data User (DU). DU is an entity that intends to access encrypted data. A DU can eventually decrypt the ciphertext if and only if his/her attributes satisfy the access policy and he/she is not in the current revocation list.


### 3.2. Formal Definition of ABE

The proposed scheme includes the following eight algorithms.(i)
Setupλ,U,BT⟶APK,ASK: TA runs this setup algorithm and takes as input a security parameter λ, an attribute universe U, and the binary tree BT illustrated in Section 2.3. It outputs a public parameter APK and TA’s secret key ASK. It initializes a user revocation list R=∅.(ii)
KeyGenASK,u,S⟶SKu: the KeyGen algorithm takes as input a user identity u, an attribute set S owned by u, and the TA’s secret key ASK. It outputs the corresponding decryption key SKu for u.(iii)
LocalEncryptAPK,m,M,ρ,R⟶CT: the data owner runs this algorithm and inputs the public parameter APK, an LSSS access structure M,ρ, and the current user revocation list R and a message m to be encrypted. M is an l×n matrix and ρ is a function that maps rows of M to attributes. The algorithm outputs the original ciphertext CT.(iv)
ReEncryptCT,APK,R⟶CT˜: given the original ciphertext CT, the public parameter APK, and the latest user revocation list R, the semi-trusted cloud service provider runs this algorithm to produce and store re-encrypted ciphertext CT˜.(v)
DecryptSKu,CT˜⟶mor⊥: based on the ciphertext CT˜ and a decryption key SKu, a data user can successfully decrypt if and only if he/she is absent from the current user revocation list and his/her attribute set satisfies the access structure of CT˜; otherwise, it outputs ⊥ indicating a failed decryption.(vi)
TraceSKu,APK,ASK⟶uor⊥: the tracing algorithm first determines whether the decryption key needs to be traced by verifying whether the SKu is well-formed. A decryption key is well-formed if it passes Key Sanity Check [34]. If the decryption key SKu is well-formed, the tracing algorithm outputs a user’s identity u indicating that SKu is linked to the user u. Otherwise, the tracing algorithm returns a symbol ⊥ implying that SKu does not need to be traced.(vii)
Revokeu,R⟶R′: the revocation algorithm takes in the revocation list R and a user u who is supposed to be revoked. TA runs this algorithm and publishes the latest revocation list R′.(viii)
CTUpdateCT˜,R′,APK,k⟶CT˜˜: the CTUpdate algorithm is executed by the CSP when a user revocation event occurs. It takes as input the latest user revocation list R′, an update key k, and the ciphertext CT˜ to be updated and outputs the updated ciphertext CT˜˜.


### 3.3. IND-CPA Security Model

We introduce the security definition of indistinguishability under selective chosen-plaintext attacks (IND-CPAs) for our scheme by the following game between an adversary and a challenger. Since the original ciphertext and the updated ciphertext are identically distributed, we only give the indistinguishability of the original ciphertext.(i)
Init: the adversary chooses a challenged access structure M∗,ρ∗ and a revocation list R∗, where M∗ is an l∗×n∗ matrix and n∗<q, ρ∗ maps rows of M∗ into attributes. The adversary sends M∗,ρ∗ and R∗ to the challenger.(ii)
Setup: the challenger runs the setup algorithm and sends the public parameters APK to the adversary.(iii)
Phase 1: the adversary queries the challenger for decryption keys corresponding to u1,S1,…,uq1,Sq1. The challenger generates a decryption key and returns it to the adversary except in the case that ui∉R∗∧Si∈M∗,ρ∗.(iv)
Challenge: the adversary submits two equal length messages m0 and m1. The challenger flips a random coin β∈0,1 and encrypts mβ under the challenged access structure M∗,ρ∗ and the revocation list R∗. After that, the challenger sends the adversary the final challenge ciphertext CT∗.(v)
Phase 2: the Phase 2 is the same as Phase 1. The adversary submits a set of tuples uq1+1,Sq1+1,…,uq,Sq to ask for those related decryption keys.(vi)
Guess: the adversary outputs a guess β′∈0,1 of β.The advantage of an adversary in the above game is defined to bePrβ′=β−1/2.Definition 5.
A directly revocable CP-ABE is selectively secure if all polynomial-time adversaries have at most negligible advantage in this security game.


### 3.4. Traceability Security Model

Here, we introduce the traceability model used in our scheme. We note that the model is similar to that of Liu et al.’s work [15], but since we have modified the structure of the decryption key, we will show that our scheme is adapted to this model in security analysis. The model is described by a security game between a challenger and an adversary as follows.(i)
Setup: the challenger runs the setup algorithm and then sends the public parameters APK to the adversary.(ii)
Key Query: the adversary submits a series of tuples u1,S1,…,uq,Sq to query the related decryption keys, where ui∈RorSi∉M∗,ρ∗,i=1,…,q.(iii)
Key Forgery: the adversary outputs a decryption key SKu∗.The adversary wins the game ifTraceAPK,R,SKu∗≠⊥ and TraceAPK,R,SKu∗∉u1,…,uq. Thus, the advantage of the adversary in this game is defined as PrTraceAPK,R,SKu∗∉⊥∪u1,…,uq.Definition 6.
A directly revocable CP-ABE is traceable if there is no polynomial-time adversary having non-negligible advantage in the above game.


## 3.1. System Architecture

The four entities in the system architecture are as follows:(i)
Trusted Authority (TA). TA publishes the public parameters of the system, generates decryption keys for non-revoked users, and is in charge of realizing traceability and updating the user revocation listR. In our system, the TA is fully trusted.(ii)
Data Owner (DO). DO takes charge of specifying an access structure and of completing the local encryption under the access structure before outsourcing to a cloud service provider.(iii)
Cloud Service Provider (CSP). CSP is responsible for re-encrypting the original ciphertext that DO upload and storing the re-encrypted ciphertext. CSP undertakes the task of updating ciphertexts once a revocation event occurs. We suppose that the CSP is honest but curious, which means CSP will faithfully execute every authorization request and not disclose the data, but attempt to obtain as much information as possible from both process and results.(iv)
Data User (DU). DU is an entity that intends to access encrypted data. A DU can eventually decrypt the ciphertext if and only if his/her attributes satisfy the access policy and he/she is not in the current revocation list.


## 3.2. Formal Definition of ABE

The proposed scheme includes the following eight algorithms.(i)
Setupλ,U,BT⟶APK,ASK: TA runs this setup algorithm and takes as input a security parameter λ, an attribute universe U, and the binary tree BT illustrated in Section 2.3. It outputs a public parameter APK and TA’s secret key ASK. It initializes a user revocation list R=∅.(ii)
KeyGenASK,u,S⟶SKu: the KeyGen algorithm takes as input a user identity u, an attribute set S owned by u, and the TA’s secret key ASK. It outputs the corresponding decryption key SKu for u.(iii)
LocalEncryptAPK,m,M,ρ,R⟶CT: the data owner runs this algorithm and inputs the public parameter APK, an LSSS access structure M,ρ, and the current user revocation list R and a message m to be encrypted. M is an l×n matrix and ρ is a function that maps rows of M to attributes. The algorithm outputs the original ciphertext CT.(iv)
ReEncryptCT,APK,R⟶CT˜: given the original ciphertext CT, the public parameter APK, and the latest user revocation list R, the semi-trusted cloud service provider runs this algorithm to produce and store re-encrypted ciphertext CT˜.(v)
DecryptSKu,CT˜⟶mor⊥: based on the ciphertext CT˜ and a decryption key SKu, a data user can successfully decrypt if and only if he/she is absent from the current user revocation list and his/her attribute set satisfies the access structure of CT˜; otherwise, it outputs ⊥ indicating a failed decryption.(vi)
TraceSKu,APK,ASK⟶uor⊥: the tracing algorithm first determines whether the decryption key needs to be traced by verifying whether the SKu is well-formed. A decryption key is well-formed if it passes Key Sanity Check [34]. If the decryption key SKu is well-formed, the tracing algorithm outputs a user’s identity u indicating that SKu is linked to the user u. Otherwise, the tracing algorithm returns a symbol ⊥ implying that SKu does not need to be traced.(vii)
Revokeu,R⟶R′: the revocation algorithm takes in the revocation list R and a user u who is supposed to be revoked. TA runs this algorithm and publishes the latest revocation list R′.(viii)
CTUpdateCT˜,R′,APK,k⟶CT˜˜: the CTUpdate algorithm is executed by the CSP when a user revocation event occurs. It takes as input the latest user revocation list R′, an update key k, and the ciphertext CT˜ to be updated and outputs the updated ciphertext CT˜˜.


## 3.3. IND-CPA Security Model

We introduce the security definition of indistinguishability under selective chosen-plaintext attacks (IND-CPAs) for our scheme by the following game between an adversary and a challenger. Since the original ciphertext and the updated ciphertext are identically distributed, we only give the indistinguishability of the original ciphertext.(i)
Init: the adversary chooses a challenged access structure M∗,ρ∗ and a revocation list R∗, where M∗ is an l∗×n∗ matrix and n∗<q, ρ∗ maps rows of M∗ into attributes. The adversary sends M∗,ρ∗ and R∗ to the challenger.(ii)
Setup: the challenger runs the setup algorithm and sends the public parameters APK to the adversary.(iii)
Phase 1: the adversary queries the challenger for decryption keys corresponding to u1,S1,…,uq1,Sq1. The challenger generates a decryption key and returns it to the adversary except in the case that ui∉R∗∧Si∈M∗,ρ∗.(iv)
Challenge: the adversary submits two equal length messages m0 and m1. The challenger flips a random coin β∈0,1 and encrypts mβ under the challenged access structure M∗,ρ∗ and the revocation list R∗. After that, the challenger sends the adversary the final challenge ciphertext CT∗.(v)
Phase 2: the Phase 2 is the same as Phase 1. The adversary submits a set of tuples uq1+1,Sq1+1,…,uq,Sq to ask for those related decryption keys.(vi)
Guess: the adversary outputs a guess β′∈0,1 of β.The advantage of an adversary in the above game is defined to bePrβ′=β−1/2.Definition 5.
A directly revocable CP-ABE is selectively secure if all polynomial-time adversaries have at most negligible advantage in this security game.


## 3.4. Traceability Security Model

Here, we introduce the traceability model used in our scheme. We note that the model is similar to that of Liu et al.’s work [15], but since we have modified the structure of the decryption key, we will show that our scheme is adapted to this model in security analysis. The model is described by a security game between a challenger and an adversary as follows.(i)
Setup: the challenger runs the setup algorithm and then sends the public parameters APK to the adversary.(ii)
Key Query: the adversary submits a series of tuples u1,S1,…,uq,Sq to query the related decryption keys, where ui∈RorSi∉M∗,ρ∗,i=1,…,q.(iii)
Key Forgery: the adversary outputs a decryption key SKu∗.The adversary wins the game ifTraceAPK,R,SKu∗≠⊥ and TraceAPK,R,SKu∗∉u1,…,uq. Thus, the advantage of the adversary in this game is defined as PrTraceAPK,R,SKu∗∉⊥∪u1,…,uq.Definition 6.
A directly revocable CP-ABE is traceable if there is no polynomial-time adversary having non-negligible advantage in the above game.


## 4. Our Construction

### 4.1. Technical Overview

In this subsection, we provide a brief overview of our main ideas and techniques. We start with the prior revocation constructions of [15, 22] and the challenge in making them resisting to user collusion. In these systems, the trusted authority distributes a set of secret values to each user (e.g., X1=x0,x1,x3 for a user and X2=x0,x1,x4 for another user). The ciphertext is associated with a minimum cover set obtained according to a revocation list. The intersection of this minimum cover set and the set owned by each legitimate user has one and only one element, and the intersection calculated for a revoked user is empty. In the specific constructions, the minimum cover set is used to compute an intermediate value (e.g., Yid in [15]) for decryption. That is to say, only users who have the elements in the minimum cover set can correctly calculate the intermediate value and perform subsequent decryption operations.However, there is a security issue in such constructions. Since these secret values are distributed directly to legitimate users in key generation process, a revoked user can obtain a necessary secret value from a non-revoked user and illegally restore its decryption capability through such complicity without catching. Note that this system is very likely to suffer from user collusion attacks. As the same secret value is usually owned by multiple non-revoked users while the white-box tracing technology only works with a fully exposed key, it is almost impossible to determine who leaked a single secret element. As a result, not only is the revocation mechanism severely challenged, but the white-box tracing technology will also fail.Our goal is to resist collusion between the revoked user and another user who still has decryption privilege, which is the bottleneck suffered by many schemes [15, 22, 35, 36]. We managed to keep the indispensable information for revocation out of the user’s reach, whereas in [15] such information is sent to legitimate users and used in decryption. If a user u implicitly owns each secret value xi of the set Xu without knowing the exact values anymore, the user cannot leak such secret. This means that we need to redesign the structure of the decryption key and hence the algorithm of encryption and decryption. Inspired by Li’s scheme [19], we further bind a unique element r to every component that contains secret value xi. To adapt to the change in user key generation, we designed a new direct revocation mechanism and reconstructed the attribute-related ciphertext. In our revocation mechanism, we enable legitimate users to successfully calculate a necessary but “exclusive” intermediate value when decrypting, where “exclusive” means that this intermediate value is useless to other users. As a result, any part of one user’s decryption key will make no sense in revalidating another revoked user’s decryption key. In addition, once a malicious user discloses a full version of decryption key, the malicious user will be captured by white-box tracing technology and then revoked. A well-established revocation mechanism also enables white-box tracing algorithm to work.We point out that in the above constructions, it is not clear how to realize life circle of data protection; indeed, these constructions tried to prevent the revoked user from decrypting the data encrypted before revocation (backward secrecy, in other words) and the data encrypted in the future (forward secrecy). As we mentioned above, forward security is vulnerable to user collusion attacks. Since ciphertext update algorithm also focuses on revocation mechanism in this construction, backward secrecy is also threatened by complicity. Furthermore, we observe that if a user computes and saves the intermediate value (e.g.,Yid in [15]) or even eg,gαs (that is used to hide a plaintext m) before being revoked, the user will also acquire illegal decryption capabilities. To achieve life cycle data protection, we redesign the ciphertext update algorithm, which not only updates the ciphertext related to revocation but also removes the hidden risks brought by any intermediate value in the decryption process.Another challenge lies in that the complete ciphertext update algorithm comes with additional computational overhead to the data owner. For devices with limited processing speed or limited battery power, such as mobile devices and Internet of things devices, this might be a burden that should not be ignored. Considering that the cloud allows users to trade capital expenses (such as data centers and physical servers) for variable expenses, and only pay for services as we consume it, the variable expenses are much lower because of the economies of scale. So, we choose to outsource the ciphertext update algorithm to the cloud. To complete the ciphertext update process, the algorithm will choose a new sharing secrets′∈ℤp and generate shares of the secret s′. Finally, the new secret and the corresponding shares will be embedded into the ciphertext. Note that all operations should be performed on the ciphertext. We carefully design the structure of the ciphertext to ensure that the update can be done without revealing the plaintext.To further ease the burden on data owners, we split the encryption algorithm into local encryption and re-encryption and outsourced the re-encryption algorithm to the cloud. Compared with Li’s scheme [19] and Wang’s scheme [37] in which the workload of proxy encryption is assigned to the trusted authority, our scheme better regulates participants’ different roles and eliminates communication overhead.


### 4.2. Concrete Construction

Now, we present the concrete directly revocable CP-ABE scheme with white-box traceability, collusion resistance, and ciphertext delegation based on [6, 15]. We design a new direct revocation mechanism, manifested in the key generation algorithm, encryption algorithm, and decryption algorithm. In the proposed scheme, the encryption algorithm consists of two steps. The data owner generates a local ciphertext; then, a semi-trusted CSP re-encrypts that local ciphertext and stores the re-encrypted data. To prevent the revoked user from accessing previous ciphertexts and implement revocable storage, the scheme implements an effective ciphertext update algorithm. Our proxy mechanism in re-encryption and ciphertext update algorithms is friendly to resource-constrained data owners. The specific algorithms are described as follows.Setupλ,U,BT⟶APK,ASK: TA runs the setup algorithm. It firstly generates a binary tree BT and associates each user in U with a different leaf node in BT. Let R be an initially empty revocation list. TA randomly chooses α, a∈ℤp, and h∈G and picks Uatt∈G for each attribute att∈U. For each node in BT, it randomly chooses X=xii=02U−2 in ℤp and then computes Y=yi|yi=gxii=02U−2. Note that in our scheme, X is reserved by the TA and will not be distributed to any user. A probabilistic encryption scheme (Enc, Dec) [38] is chosen, which is a symmetric encryption from 0,1∗ to ℤp with secret key k¯∈ℤp and encrypts the same message to different ciphertexts each time.The TA’s secret key is set to(4)ASK=α,a,X=xii=02U−2,k¯.The public parameters are published as follows:(5)APK=g,h,eg,gα,ga,Uattatt∈U,Y=yi|yi=gxii=02U−2.KeyGenASK,u,S⟶SKu: the decryption key generation algorithm is executed by the trusted authority. Let pathu=root,…,uid denote the path from the root to the leaf node associated with the user u (namely uid) in the binary tree. c=Enck¯uid is computed, where k¯ is the secret key for the probabilistic encryption, and the result c is not distinguished from a random number in ℤp. r∈ℤp is randomly chosen, and then, the decryption key component with respect to the attribute set of the user can be constructed as follows:(6)K=gα/a+chr,K′=c,L=gr,L′=gar,Katt=Uatta+cratt∈S.In the presented scheme, because a useru implicitly owns each xi of the pathu without knowing the exact values, the user cannot leak such secret. However, this is not enough to resist collusion attacks between users. Since paths of different users might have shared nodes, which means secret xi might not be exclusive and could allow complicity, we further bind a unique element r to every component that contains xi where i∈pathu. As a result, any part of one user’s decryption key will make no sense in revalidating another revoked user’s decryption key. Formally, the decryption key component corresponding to the user’s identity u is set to(7)D=di|di=gra+c/xii∈pathu.Finally, the above two components form the complete decryption key:(8)SKu=K,K′,L,L′,Kattatt∈S,Dii∈pathu.LocalEncryptAPK,m,M,ρ,R⟶CT: the data owner runs the algorithm and inputs the public parameter APK, an LSSS access structure M,ρ, and the current user revocation list R, as well as a message m to be encrypted. To complete the local encryption, the algorithm first chooses a random vector v⟶=s,t2,t3,…,tn to share the encryption exponent s and then generates l shares of the secret s by calculating λi=Miv⟶ for i=1,2,…,l. The original ciphertext CT corresponding to M,ρ and R is computed as follows:(9)C=m⋅eg,gαs,C0=gs,C0′=gas,Ci=hλiUρi−si∈1,…,ℓ,CT=C,C0,C0′,Cii∈1,…,ℓ,M,ρ,R.After the encryption operation, the data owner uploadsCT to the cloud service provider.ReEncryptCT,APK,R⟶CT˜: the re-encryption algorithm is outsourced to the semi-trusted cloud service provider. In particular, the CSP randomly choose k∈ℤp and re-encrypts the local ciphertext CT as follows:(10)C˜=C,C0˜=C0,C0′˜=C0′,Ci˜=Ci×gk=hλiUρi−sgki∈1,…,ℓ.LetcoverR be the minimum cover set of the revocation list R. The ciphertext component related to the revocation list R can be described as follows:(11)Y˜=yj˜|yj˜=yjkj∈coverR.Finally, the CSP storages the full ciphertextCT˜:(12)CT˜=C˜,C0˜,C0′˜,Ci˜i∈1,…,ℓ,Yj˜j∈coverR,M,ρ,R.DecryptSKu,CT˜⟶m: for a data user who is among the current user revocation list, or whose attribute set does not satisfy the access policy of CT˜, the algorithm outputs ⊥ to indicate a failure of decryption; otherwise, it does the following decryption algorithm.Supposepathu=root,…,uid, where uid is the leaf node associated with the user u. For u∉R, there exists a node j such that j∈pathu∩coverR. For S∈M,ρ, let I=i:ρi∈S⊆1,2,…,ℓ, and there exist coefficients ci|i∈I such that ∑i∈IciMi=1,0,…,0. Thus, we have ∑i∈Iciλi=s. The original plaintext m can be retrieved through these steps:(13)Z1=eK,C0˜K′⋅C0′˜=egα/a+chr,ga+cs=eg,gαseg,ha+crs,Z2=∏i∈IeLK′⋅L′,Ci˜⋅eKρi,C0˜⋅eYj˜,Dj−1ci=∏i∈Ieg,ha+crciλi=eg,ha+crs,m=C˜⋅Z2Z1.TraceSKu,APK,ASK⟶uor⊥: taking as input a suspected decryption key SKu, the tracing algorithm determines whether the decryption key needs to be traced by first verifying whether the SKu is well-formed. A decryption key is well-formed if it passes Key Sanity Check [34]. Similar to that in previous works [6, 15], our scheme’s Key Sanity Check is a deterministic algorithm containing the following checks:(1)
K′∈ℤp,K,L,L′,Katt,D∈G(2)
eg,L′=ega,L≠1(3)
∃att∈S,s.t.Uatt,LK′L′=eg,Katt≠1If the decryption keySKu does not pass the Key Sanity Check, the tracing algorithm returns the symbol ⊥ implying that SKu does not need to be traced. Otherwise, the tracing algorithm outputs an identity u indicating that SKu is linked to the user u. In detail, the tracing algorithm computes Deck¯K′ to retrieve uid, the leaf node that points to the malicious user u. Then, it further launches the revoke algorithm to revoke u.Revokeu,R⟶R′: if a user u is supposed to be revoked, the algorithm adds u into the revocation list and outputs the latest revocation list R′=R∪u.CTUpdateCT˜,R′,APK,k⟶CT˜˜: taking the original ciphertext CT˜, the latest revocation list R′, the public key APK, and the previous update key k as input, the semi-trusted CSP updates the archetype to a refined CT˜˜. To complete the ciphertext update process, the algorithm randomly picks k′, s′∈ℤp, and lets coverR′ be the minimum cover set of revocation list R′. After that, the algorithm chooses a random vector u⟶∈ℤpn with s′ as the first entry and then generates l shares of the secret s′ by calculating μi=Mu⟶i for i=1,2,…,l. Ciphertext components related to the revocation list R′ can be computed as follows:(14)Y˜˜=yj˜˜|yj˜˜=yjk′j∈coverR′,Ci˜˜=Ci˜⋅hμi⋅gk′−k⋅Uρi−s′=hλi+μiUρi−s+s′gk′i=1ℓ.The rest of the ciphertext components are transformed to(15)C˜˜=C˜⋅eg,gαs′=m⋅eg,gαs+s′,C0˜˜=C0˜⋅gs′=gs+s′,C0′˜˜=C0′˜⋅gas′=gas+s′.Finally, the updated ciphertext is kept as follows:(16)CT˜˜=C˜˜,C0˜˜,C0′˜˜,Ci˜˜i∈1,…,ℓ,Yj˜˜j∈coverR′,M,ρ,R′.Correctness: suppose pathu=root,…,uid, where uid is the leaf node associated with the user u. For u∉R, there exists a node j such that j∈pathu∩coverR. For S∈M,ρ, let I=i:ρi∈S⊆1,2,…,ℓ, there exist coefficients ci|i∈I such that ∑i∈IciMi=1,0,…,0. Thus, we have ∑i∈Iciλi+μi=s+s′. The original plaintext m can be retrieved through these steps:(17)Z1=eK,C0˜˜K′⋅C0′˜˜=egα/a+chr,ga+cs+s′=eg,gs+s′αeg,hs+s′a+cr,Z2=∏i∈IeLK′⋅L′,Ci˜˜⋅eKρi,C0˜˜⋅eYj˜˜,Dj−1ci=∏i∈Ieg,ha+crciλi+μi=eg,hs+s′a+cr,m=C˜˜⋅Z2Z1.Combined with the revocation mechanism, the proposed scheme achieved both forward secrecy and backward secrecy. That is to say, a revoked user cannot successfully decrypt the ciphertexts that are generated later, not even in the past.


## 4.1. Technical Overview

In this subsection, we provide a brief overview of our main ideas and techniques. We start with the prior revocation constructions of [15, 22] and the challenge in making them resisting to user collusion. In these systems, the trusted authority distributes a set of secret values to each user (e.g., X1=x0,x1,x3 for a user and X2=x0,x1,x4 for another user). The ciphertext is associated with a minimum cover set obtained according to a revocation list. The intersection of this minimum cover set and the set owned by each legitimate user has one and only one element, and the intersection calculated for a revoked user is empty. In the specific constructions, the minimum cover set is used to compute an intermediate value (e.g., Yid in [15]) for decryption. That is to say, only users who have the elements in the minimum cover set can correctly calculate the intermediate value and perform subsequent decryption operations.However, there is a security issue in such constructions. Since these secret values are distributed directly to legitimate users in key generation process, a revoked user can obtain a necessary secret value from a non-revoked user and illegally restore its decryption capability through such complicity without catching. Note that this system is very likely to suffer from user collusion attacks. As the same secret value is usually owned by multiple non-revoked users while the white-box tracing technology only works with a fully exposed key, it is almost impossible to determine who leaked a single secret element. As a result, not only is the revocation mechanism severely challenged, but the white-box tracing technology will also fail.Our goal is to resist collusion between the revoked user and another user who still has decryption privilege, which is the bottleneck suffered by many schemes [15, 22, 35, 36]. We managed to keep the indispensable information for revocation out of the user’s reach, whereas in [15] such information is sent to legitimate users and used in decryption. If a user u implicitly owns each secret value xi of the set Xu without knowing the exact values anymore, the user cannot leak such secret. This means that we need to redesign the structure of the decryption key and hence the algorithm of encryption and decryption. Inspired by Li’s scheme [19], we further bind a unique element r to every component that contains secret value xi. To adapt to the change in user key generation, we designed a new direct revocation mechanism and reconstructed the attribute-related ciphertext. In our revocation mechanism, we enable legitimate users to successfully calculate a necessary but “exclusive” intermediate value when decrypting, where “exclusive” means that this intermediate value is useless to other users. As a result, any part of one user’s decryption key will make no sense in revalidating another revoked user’s decryption key. In addition, once a malicious user discloses a full version of decryption key, the malicious user will be captured by white-box tracing technology and then revoked. A well-established revocation mechanism also enables white-box tracing algorithm to work.We point out that in the above constructions, it is not clear how to realize life circle of data protection; indeed, these constructions tried to prevent the revoked user from decrypting the data encrypted before revocation (backward secrecy, in other words) and the data encrypted in the future (forward secrecy). As we mentioned above, forward security is vulnerable to user collusion attacks. Since ciphertext update algorithm also focuses on revocation mechanism in this construction, backward secrecy is also threatened by complicity. Furthermore, we observe that if a user computes and saves the intermediate value (e.g.,Yid in [15]) or even eg,gαs (that is used to hide a plaintext m) before being revoked, the user will also acquire illegal decryption capabilities. To achieve life cycle data protection, we redesign the ciphertext update algorithm, which not only updates the ciphertext related to revocation but also removes the hidden risks brought by any intermediate value in the decryption process.Another challenge lies in that the complete ciphertext update algorithm comes with additional computational overhead to the data owner. For devices with limited processing speed or limited battery power, such as mobile devices and Internet of things devices, this might be a burden that should not be ignored. Considering that the cloud allows users to trade capital expenses (such as data centers and physical servers) for variable expenses, and only pay for services as we consume it, the variable expenses are much lower because of the economies of scale. So, we choose to outsource the ciphertext update algorithm to the cloud. To complete the ciphertext update process, the algorithm will choose a new sharing secrets′∈ℤp and generate shares of the secret s′. Finally, the new secret and the corresponding shares will be embedded into the ciphertext. Note that all operations should be performed on the ciphertext. We carefully design the structure of the ciphertext to ensure that the update can be done without revealing the plaintext.To further ease the burden on data owners, we split the encryption algorithm into local encryption and re-encryption and outsourced the re-encryption algorithm to the cloud. Compared with Li’s scheme [19] and Wang’s scheme [37] in which the workload of proxy encryption is assigned to the trusted authority, our scheme better regulates participants’ different roles and eliminates communication overhead.


## 4.2. Concrete Construction

Now, we present the concrete directly revocable CP-ABE scheme with white-box traceability, collusion resistance, and ciphertext delegation based on [6, 15]. We design a new direct revocation mechanism, manifested in the key generation algorithm, encryption algorithm, and decryption algorithm. In the proposed scheme, the encryption algorithm consists of two steps. The data owner generates a local ciphertext; then, a semi-trusted CSP re-encrypts that local ciphertext and stores the re-encrypted data. To prevent the revoked user from accessing previous ciphertexts and implement revocable storage, the scheme implements an effective ciphertext update algorithm. Our proxy mechanism in re-encryption and ciphertext update algorithms is friendly to resource-constrained data owners. The specific algorithms are described as follows.Setupλ,U,BT⟶APK,ASK: TA runs the setup algorithm. It firstly generates a binary tree BT and associates each user in U with a different leaf node in BT. Let R be an initially empty revocation list. TA randomly chooses α, a∈ℤp, and h∈G and picks Uatt∈G for each attribute att∈U. For each node in BT, it randomly chooses X=xii=02U−2 in ℤp and then computes Y=yi|yi=gxii=02U−2. Note that in our scheme, X is reserved by the TA and will not be distributed to any user. A probabilistic encryption scheme (Enc, Dec) [38] is chosen, which is a symmetric encryption from 0,1∗ to ℤp with secret key k¯∈ℤp and encrypts the same message to different ciphertexts each time.The TA’s secret key is set to(4)ASK=α,a,X=xii=02U−2,k¯.The public parameters are published as follows:(5)APK=g,h,eg,gα,ga,Uattatt∈U,Y=yi|yi=gxii=02U−2.KeyGenASK,u,S⟶SKu: the decryption key generation algorithm is executed by the trusted authority. Let pathu=root,…,uid denote the path from the root to the leaf node associated with the user u (namely uid) in the binary tree. c=Enck¯uid is computed, where k¯ is the secret key for the probabilistic encryption, and the result c is not distinguished from a random number in ℤp. r∈ℤp is randomly chosen, and then, the decryption key component with respect to the attribute set of the user can be constructed as follows:(6)K=gα/a+chr,K′=c,L=gr,L′=gar,Katt=Uatta+cratt∈S.In the presented scheme, because a useru implicitly owns each xi of the pathu without knowing the exact values, the user cannot leak such secret. However, this is not enough to resist collusion attacks between users. Since paths of different users might have shared nodes, which means secret xi might not be exclusive and could allow complicity, we further bind a unique element r to every component that contains xi where i∈pathu. As a result, any part of one user’s decryption key will make no sense in revalidating another revoked user’s decryption key. Formally, the decryption key component corresponding to the user’s identity u is set to(7)D=di|di=gra+c/xii∈pathu.Finally, the above two components form the complete decryption key:(8)SKu=K,K′,L,L′,Kattatt∈S,Dii∈pathu.LocalEncryptAPK,m,M,ρ,R⟶CT: the data owner runs the algorithm and inputs the public parameter APK, an LSSS access structure M,ρ, and the current user revocation list R, as well as a message m to be encrypted. To complete the local encryption, the algorithm first chooses a random vector v⟶=s,t2,t3,…,tn to share the encryption exponent s and then generates l shares of the secret s by calculating λi=Miv⟶ for i=1,2,…,l. The original ciphertext CT corresponding to M,ρ and R is computed as follows:(9)C=m⋅eg,gαs,C0=gs,C0′=gas,Ci=hλiUρi−si∈1,…,ℓ,CT=C,C0,C0′,Cii∈1,…,ℓ,M,ρ,R.After the encryption operation, the data owner uploadsCT to the cloud service provider.ReEncryptCT,APK,R⟶CT˜: the re-encryption algorithm is outsourced to the semi-trusted cloud service provider. In particular, the CSP randomly choose k∈ℤp and re-encrypts the local ciphertext CT as follows:(10)C˜=C,C0˜=C0,C0′˜=C0′,Ci˜=Ci×gk=hλiUρi−sgki∈1,…,ℓ.LetcoverR be the minimum cover set of the revocation list R. The ciphertext component related to the revocation list R can be described as follows:(11)Y˜=yj˜|yj˜=yjkj∈coverR.Finally, the CSP storages the full ciphertextCT˜:(12)CT˜=C˜,C0˜,C0′˜,Ci˜i∈1,…,ℓ,Yj˜j∈coverR,M,ρ,R.DecryptSKu,CT˜⟶m: for a data user who is among the current user revocation list, or whose attribute set does not satisfy the access policy of CT˜, the algorithm outputs ⊥ to indicate a failure of decryption; otherwise, it does the following decryption algorithm.Supposepathu=root,…,uid, where uid is the leaf node associated with the user u. For u∉R, there exists a node j such that j∈pathu∩coverR. For S∈M,ρ, let I=i:ρi∈S⊆1,2,…,ℓ, and there exist coefficients ci|i∈I such that ∑i∈IciMi=1,0,…,0. Thus, we have ∑i∈Iciλi=s. The original plaintext m can be retrieved through these steps:(13)Z1=eK,C0˜K′⋅C0′˜=egα/a+chr,ga+cs=eg,gαseg,ha+crs,Z2=∏i∈IeLK′⋅L′,Ci˜⋅eKρi,C0˜⋅eYj˜,Dj−1ci=∏i∈Ieg,ha+crciλi=eg,ha+crs,m=C˜⋅Z2Z1.TraceSKu,APK,ASK⟶uor⊥: taking as input a suspected decryption key SKu, the tracing algorithm determines whether the decryption key needs to be traced by first verifying whether the SKu is well-formed. A decryption key is well-formed if it passes Key Sanity Check [34]. Similar to that in previous works [6, 15], our scheme’s Key Sanity Check is a deterministic algorithm containing the following checks:(1)
K′∈ℤp,K,L,L′,Katt,D∈G(2)
eg,L′=ega,L≠1(3)
∃att∈S,s.t.Uatt,LK′L′=eg,Katt≠1If the decryption keySKu does not pass the Key Sanity Check, the tracing algorithm returns the symbol ⊥ implying that SKu does not need to be traced. Otherwise, the tracing algorithm outputs an identity u indicating that SKu is linked to the user u. In detail, the tracing algorithm computes Deck¯K′ to retrieve uid, the leaf node that points to the malicious user u. Then, it further launches the revoke algorithm to revoke u.Revokeu,R⟶R′: if a user u is supposed to be revoked, the algorithm adds u into the revocation list and outputs the latest revocation list R′=R∪u.CTUpdateCT˜,R′,APK,k⟶CT˜˜: taking the original ciphertext CT˜, the latest revocation list R′, the public key APK, and the previous update key k as input, the semi-trusted CSP updates the archetype to a refined CT˜˜. To complete the ciphertext update process, the algorithm randomly picks k′, s′∈ℤp, and lets coverR′ be the minimum cover set of revocation list R′. After that, the algorithm chooses a random vector u⟶∈ℤpn with s′ as the first entry and then generates l shares of the secret s′ by calculating μi=Mu⟶i for i=1,2,…,l. Ciphertext components related to the revocation list R′ can be computed as follows:(14)Y˜˜=yj˜˜|yj˜˜=yjk′j∈coverR′,Ci˜˜=Ci˜⋅hμi⋅gk′−k⋅Uρi−s′=hλi+μiUρi−s+s′gk′i=1ℓ.The rest of the ciphertext components are transformed to(15)C˜˜=C˜⋅eg,gαs′=m⋅eg,gαs+s′,C0˜˜=C0˜⋅gs′=gs+s′,C0′˜˜=C0′˜⋅gas′=gas+s′.Finally, the updated ciphertext is kept as follows:(16)CT˜˜=C˜˜,C0˜˜,C0′˜˜,Ci˜˜i∈1,…,ℓ,Yj˜˜j∈coverR′,M,ρ,R′.Correctness: suppose pathu=root,…,uid, where uid is the leaf node associated with the user u. For u∉R, there exists a node j such that j∈pathu∩coverR. For S∈M,ρ, let I=i:ρi∈S⊆1,2,…,ℓ, there exist coefficients ci|i∈I such that ∑i∈IciMi=1,0,…,0. Thus, we have ∑i∈Iciλi+μi=s+s′. The original plaintext m can be retrieved through these steps:(17)Z1=eK,C0˜˜K′⋅C0′˜˜=egα/a+chr,ga+cs+s′=eg,gs+s′αeg,hs+s′a+cr,Z2=∏i∈IeLK′⋅L′,Ci˜˜⋅eKρi,C0˜˜⋅eYj˜˜,Dj−1ci=∏i∈Ieg,ha+crciλi+μi=eg,hs+s′a+cr,m=C˜˜⋅Z2Z1.Combined with the revocation mechanism, the proposed scheme achieved both forward secrecy and backward secrecy. That is to say, a revoked user cannot successfully decrypt the ciphertexts that are generated later, not even in the past.


## 5. Security Analysis

In this section, we first prove the IND-CPA security based onq-BDHE hardness assumption and then prove the traceability based on l-SDH hardness assumption.


### 5.1. IND-CPA Security

Since the distribution of the updated ciphertext is identical to the original ciphertext, we only need to prove IND-CPA security related to the original.Theorem 1.
If theq-BDHE hardness assumption holds, no polynomial-time adversary can break the proposed CP-ABE scheme with non-negligible advantage under selective access policy and chosen-plaintext attacks (whereq>2U−2andUis the number of user setU).Proof.
Suppose there exists a polynomial-time adversaryA that can break our CP-ABE scheme under selective access policy and chosen-plaintext attacks with non-negligible advantage ε; then, we can construct a simulator ℬ with a non-negligible advantage to break the q-BDHE assumption. The simulator ℬ runs as follows.
LetG and GT be multiplication cycle groups of prime order p. Let g be the generator of G. Let e:G×G⟶GT be a bilinear map. ℬ flips a fair coin η∈0,1. Given y⟶=g,gs,gd,…,gdq,gdq+2,…,gd2q, then if η=0, ℬ sets Z=eg,gdq+1s; otherwise, ℬ randomly picks γ∈GT and sets Z=γ.
Init: the adversary A chooses an access structure M∗,ρ∗ and a revocation list R∗, where M∗ is an ℓ∗×n∗ matrix with n∗<q, and ρ∗ maps rows of M∗ into attributes.
Setup:ℬ randomly chooses α′∈ℤp and sets eg,gα=egd,gdqeg,gα′, which implicitly sets α=α′+dq+1. For each att∈U, zatt∈ℤp is randomly chosen and then Uatt is generated as follows:(i)
If there exists ani∈1,2,…,ℓ∗ such that ρ∗i=att, Uatt=gzattgdMi,1∗gd2Mi,2∗…gdn∗Mi,n∗∗ is set;(ii)
Otherwise,Uatt=gzatt is set.
ℬ randomly selects a∈ℤp, computes ga, and lets h=gd. For ∀i=0,1,…,2U−2, vi∈ℤp is randomly picked, and let yi=gdvi, which implicitly sets xi=d⋅vi. Finally, ℬ outputs the public parameters:(18)APK=g,h,eg,gα,ga,Uattatt∈U,Y=yi|yi=gxii=02U−2.
Phase 1:A submits a set of pairs u,S to ℬ for petitioning the related decryption keys. To respond, ℬ does as follows.Case 1.
IfS∈M∗,ρ∗ and u∉R∗, then it is aborted.Case 2.
IfS∈M∗,ρ∗ and u∈R∗, c∈ℤp is picked randomly, and K,K′,L,L′,Katt,Di is computed as follows:(19)K′=c,K=gα′/a+cgdqMi,1∗/a+cMi,2∗=gα/a+chr,L=gdq1/a+c−1gdq−1Mi,1∗/a+cMi,2∗=gr,L′=La=gar,Katt=gdqzatt−1gdq−1zattMi,1∗/Mi,2∗⋅∏j=2,…,n∗gdj+qMi,j∗−1⋅∏j=1,…,n∗,j≠2gdj+q−1Mi,j∗Mi,1∗/Mi,2∗=Uatta+cr,which implicitly sets r=−dq/a+c+dq−1/a+c⋅Mi,1∗/Mi,2∗.
Supposepathu=root,…,uid, where root denotes the root node and uid is a leaf node associated with the user u. ℬ picks xi where i∈pathu and computes Di as follows:(20)Di=gdq−1−1gdq−2Mi,1∗/Mi,2∗1/vi=gra+c/xi.Case 3.
IfS∉M∗,ρ∗ and u∈R∗, ℬ computes K,K′,L,L′,Katt,Di as follows. Given M∗,ρ∗, there exists a vector w⟶=w1,w2,…,wn∗∈ℤpn∗ such that w1=−1 and Mi∗⋅w⟶=0 for any i satisfying ρ∗i∈S. ℬ randomly picks c,t∈ℤp and sets K′=c. After that, ℬ computes(21)K=gα′gd2t∏i=2,…,n∗gdq+2−iwi1/a+c=gα/a+chr,L=gdt/a+c∏i=1,…,n∗gdq+1−iwi1/a+c=gr,L′=gdat/a+c∏i=1,…,n∗gdq+1−iwia/a+c=gar,which implicitly sets r=1/a+ctd+w1dq+w2dq−1+⋯+wn∗dq−n∗+1. Since S∉M∗,ρ∗, B computes Katt as follows. For each att∈S, if there exists i such that ρ∗i=att, then the following is computed(22)Katt=La+czatt∏j=1,…,n∗gdj+1t×∏k=1,…,n∗,k≠jgdq+1+j−kwkMi,j∗=Uatta+cr,otherwise let Katt=La+czatt. Suppose pathu=root,…,uid, where root denotes the root node and uid is the leaf node associated with the user u, and then, xi is picked, where i∈pathu. ℬ computes Di as follows:(23)Di=gt∏j=1,…,n∗gdq−jwj1/vi=gra+c/xi.Case 4.
IfS∉M∗,ρ∗ and u∉R∗, ℬ computes K,K′,L,L′,Katt,Di as was done in Case 3.
Challenge: the adversary A submits two equal length messages M0 and M1. Then, the simulator ℬ flips a random coin β∈0,1 and calculates the ciphertext as follows.
LocalEncrypt:ℬ starts with computing(24)C=Mβ⋅Z⋅egs,gα′,C0=gs,C0′=gas.
ℬ picks r2′,r3′,…,rn∗′∈ℤp∗ randomly, then lets v⟶=s,sd+r2′,sd2+r3′,…,sdn∗−1+rn∗′∈ℤpn∗ and calculates Ci as follows:(25)Ci=∏j=2,3,…,n∗gdMi,j∗rj′⋅gs−zρ∗i=hλiUρi−s,where i∈1,2,…,ℓ.
ReEncrypt: letC,C0,C0′ remain unchanged: C˜=C,C0˜=C0,C0′˜=C0′. k′∈ℤp∗ is randomly picked, and Ci˜ is computed as follows:(26)Ci˜=∏j=2,3,…,n∗gdMi,j∗rj′⋅gs−zρ∗i⋅gdq−1k′=hλiUρi−sgk,where i∈1,2,…,ℓ, and it implicitly sets k=dq−1⋅k′.
LetcoverR∗ be the minimum cover set of the revocation list R∗. The ciphertext component is computed related to R∗ as follows:(27)Y˜=yj˜|yj˜=gdqvjk′=yjkj∈coverR∗.
Finally,ℬ gives the final ciphertext as follows:(28)CT˜=C˜,C0˜,C0′˜,Ci˜i∈1,…,ℓ,Yj˜j∈coverR∗,M∗,ρ∗,R∗.
Phase 2: it is same as Phase 1.
Guess: the adversary A will eventually output a guess β′ of β. If β′=β, the simulator ℬ outputs η′=0 to indicate that Z=eg,gdq+1s; otherwise, it outputs η′=1 to indicate that Z is a random group element in GT.
In the case whereη=0, the adversary A obtains Z=eg,gdq+1s. Supposing the adversary’s advantage is ϵ, then the probability that A wins the game is Prβ′=β|η=0=1/2+ϵ. Since the simulator outputs η′=0 when β′=β, there exists Prη′=η|η=0=Prβ′=β|η=0=1/2+ϵ.
In the case whereη=1, the adversary A obtains Z=γ, which is a random element in GT, such that the adversary has no information about β and loses the advantage. We get Prη′=η|η=1=Prβ′=β|η=1=1/2.
In the end, the advantage ofℬ to solving q-BDHE hardness assumption is as follows: Prη′=η=Prη′=η|η=0⋅Prη=0+Prη′=η|η=1⋅Prη=1−1/2=1/2+ϵ⋅1/2+1/2⋅1/2−1/2=1/2ϵ.


### 5.2. Traceability

Based on Liu’s proof method [15], we reduce the traceability of our CP-ABE scheme to the l-SDH hardness assumption. Note that our work in this subsection is mainly to illustrate that the reconstructed key maintains traceability instead of proposing new proof tools. So, we basically follow the approach in [15]. The specific analysis can be found in appendix.


### 5.3. Forward and Backward Secrecy

Once a user is revoked, all of the components encrypted with a secret elements in the ciphertext are updated by the semi-trusted CSP with a new secret s′, and the components related to revocation list are also renewed. Even if the revoked user has stored the previous partial decryption result eg,gαs, it would not help to recover the desired value eg,gαs+s′. Thus, the backward secrecy of the updated ciphertext is guaranteed in the proposed scheme.In the proposed CP-ABE, the data owner will embed the latest revocation list into the ciphertext in the process of local encryption. For a data user who is included in the revocation list, his/her decryption key cannot satisfy the access control policy of subsequent ciphertexts anymore; as a result, the backward secrecy is guaranteed.


## 5.1. IND-CPA Security

Since the distribution of the updated ciphertext is identical to the original ciphertext, we only need to prove IND-CPA security related to the original.Theorem 1.
If theq-BDHE hardness assumption holds, no polynomial-time adversary can break the proposed CP-ABE scheme with non-negligible advantage under selective access policy and chosen-plaintext attacks (whereq>2U−2andUis the number of user setU).Proof.
Suppose there exists a polynomial-time adversaryA that can break our CP-ABE scheme under selective access policy and chosen-plaintext attacks with non-negligible advantage ε; then, we can construct a simulator ℬ with a non-negligible advantage to break the q-BDHE assumption. The simulator ℬ runs as follows.
LetG and GT be multiplication cycle groups of prime order p. Let g be the generator of G. Let e:G×G⟶GT be a bilinear map. ℬ flips a fair coin η∈0,1. Given y⟶=g,gs,gd,…,gdq,gdq+2,…,gd2q, then if η=0, ℬ sets Z=eg,gdq+1s; otherwise, ℬ randomly picks γ∈GT and sets Z=γ.
Init: the adversary A chooses an access structure M∗,ρ∗ and a revocation list R∗, where M∗ is an ℓ∗×n∗ matrix with n∗<q, and ρ∗ maps rows of M∗ into attributes.
Setup:ℬ randomly chooses α′∈ℤp and sets eg,gα=egd,gdqeg,gα′, which implicitly sets α=α′+dq+1. For each att∈U, zatt∈ℤp is randomly chosen and then Uatt is generated as follows:(i)
If there exists ani∈1,2,…,ℓ∗ such that ρ∗i=att, Uatt=gzattgdMi,1∗gd2Mi,2∗…gdn∗Mi,n∗∗ is set;(ii)
Otherwise,Uatt=gzatt is set.
ℬ randomly selects a∈ℤp, computes ga, and lets h=gd. For ∀i=0,1,…,2U−2, vi∈ℤp is randomly picked, and let yi=gdvi, which implicitly sets xi=d⋅vi. Finally, ℬ outputs the public parameters:(18)APK=g,h,eg,gα,ga,Uattatt∈U,Y=yi|yi=gxii=02U−2.
Phase 1:A submits a set of pairs u,S to ℬ for petitioning the related decryption keys. To respond, ℬ does as follows.Case 1.
IfS∈M∗,ρ∗ and u∉R∗, then it is aborted.Case 2.
IfS∈M∗,ρ∗ and u∈R∗, c∈ℤp is picked randomly, and K,K′,L,L′,Katt,Di is computed as follows:(19)K′=c,K=gα′/a+cgdqMi,1∗/a+cMi,2∗=gα/a+chr,L=gdq1/a+c−1gdq−1Mi,1∗/a+cMi,2∗=gr,L′=La=gar,Katt=gdqzatt−1gdq−1zattMi,1∗/Mi,2∗⋅∏j=2,…,n∗gdj+qMi,j∗−1⋅∏j=1,…,n∗,j≠2gdj+q−1Mi,j∗Mi,1∗/Mi,2∗=Uatta+cr,which implicitly sets r=−dq/a+c+dq−1/a+c⋅Mi,1∗/Mi,2∗.
Supposepathu=root,…,uid, where root denotes the root node and uid is a leaf node associated with the user u. ℬ picks xi where i∈pathu and computes Di as follows:(20)Di=gdq−1−1gdq−2Mi,1∗/Mi,2∗1/vi=gra+c/xi.Case 3.
IfS∉M∗,ρ∗ and u∈R∗, ℬ computes K,K′,L,L′,Katt,Di as follows. Given M∗,ρ∗, there exists a vector w⟶=w1,w2,…,wn∗∈ℤpn∗ such that w1=−1 and Mi∗⋅w⟶=0 for any i satisfying ρ∗i∈S. ℬ randomly picks c,t∈ℤp and sets K′=c. After that, ℬ computes(21)K=gα′gd2t∏i=2,…,n∗gdq+2−iwi1/a+c=gα/a+chr,L=gdt/a+c∏i=1,…,n∗gdq+1−iwi1/a+c=gr,L′=gdat/a+c∏i=1,…,n∗gdq+1−iwia/a+c=gar,which implicitly sets r=1/a+ctd+w1dq+w2dq−1+⋯+wn∗dq−n∗+1. Since S∉M∗,ρ∗, B computes Katt as follows. For each att∈S, if there exists i such that ρ∗i=att, then the following is computed(22)Katt=La+czatt∏j=1,…,n∗gdj+1t×∏k=1,…,n∗,k≠jgdq+1+j−kwkMi,j∗=Uatta+cr,otherwise let Katt=La+czatt. Suppose pathu=root,…,uid, where root denotes the root node and uid is the leaf node associated with the user u, and then, xi is picked, where i∈pathu. ℬ computes Di as follows:(23)Di=gt∏j=1,…,n∗gdq−jwj1/vi=gra+c/xi.Case 4.
IfS∉M∗,ρ∗ and u∉R∗, ℬ computes K,K′,L,L′,Katt,Di as was done in Case 3.
Challenge: the adversary A submits two equal length messages M0 and M1. Then, the simulator ℬ flips a random coin β∈0,1 and calculates the ciphertext as follows.
LocalEncrypt:ℬ starts with computing(24)C=Mβ⋅Z⋅egs,gα′,C0=gs,C0′=gas.
ℬ picks r2′,r3′,…,rn∗′∈ℤp∗ randomly, then lets v⟶=s,sd+r2′,sd2+r3′,…,sdn∗−1+rn∗′∈ℤpn∗ and calculates Ci as follows:(25)Ci=∏j=2,3,…,n∗gdMi,j∗rj′⋅gs−zρ∗i=hλiUρi−s,where i∈1,2,…,ℓ.
ReEncrypt: letC,C0,C0′ remain unchanged: C˜=C,C0˜=C0,C0′˜=C0′. k′∈ℤp∗ is randomly picked, and Ci˜ is computed as follows:(26)Ci˜=∏j=2,3,…,n∗gdMi,j∗rj′⋅gs−zρ∗i⋅gdq−1k′=hλiUρi−sgk,where i∈1,2,…,ℓ, and it implicitly sets k=dq−1⋅k′.
LetcoverR∗ be the minimum cover set of the revocation list R∗. The ciphertext component is computed related to R∗ as follows:(27)Y˜=yj˜|yj˜=gdqvjk′=yjkj∈coverR∗.
Finally,ℬ gives the final ciphertext as follows:(28)CT˜=C˜,C0˜,C0′˜,Ci˜i∈1,…,ℓ,Yj˜j∈coverR∗,M∗,ρ∗,R∗.
Phase 2: it is same as Phase 1.
Guess: the adversary A will eventually output a guess β′ of β. If β′=β, the simulator ℬ outputs η′=0 to indicate that Z=eg,gdq+1s; otherwise, it outputs η′=1 to indicate that Z is a random group element in GT.
In the case whereη=0, the adversary A obtains Z=eg,gdq+1s. Supposing the adversary’s advantage is ϵ, then the probability that A wins the game is Prβ′=β|η=0=1/2+ϵ. Since the simulator outputs η′=0 when β′=β, there exists Prη′=η|η=0=Prβ′=β|η=0=1/2+ϵ.
In the case whereη=1, the adversary A obtains Z=γ, which is a random element in GT, such that the adversary has no information about β and loses the advantage. We get Prη′=η|η=1=Prβ′=β|η=1=1/2.
In the end, the advantage ofℬ to solving q-BDHE hardness assumption is as follows: Prη′=η=Prη′=η|η=0⋅Prη=0+Prη′=η|η=1⋅Prη=1−1/2=1/2+ϵ⋅1/2+1/2⋅1/2−1/2=1/2ϵ.


## 5.2. Traceability

Based on Liu’s proof method [15], we reduce the traceability of our CP-ABE scheme to the l-SDH hardness assumption. Note that our work in this subsection is mainly to illustrate that the reconstructed key maintains traceability instead of proposing new proof tools. So, we basically follow the approach in [15]. The specific analysis can be found in appendix.


## 5.3. Forward and Backward Secrecy

Once a user is revoked, all of the components encrypted with a secret elements in the ciphertext are updated by the semi-trusted CSP with a new secret s′, and the components related to revocation list are also renewed. Even if the revoked user has stored the previous partial decryption result eg,gαs, it would not help to recover the desired value eg,gαs+s′. Thus, the backward secrecy of the updated ciphertext is guaranteed in the proposed scheme.In the proposed CP-ABE, the data owner will embed the latest revocation list into the ciphertext in the process of local encryption. For a data user who is included in the revocation list, his/her decryption key cannot satisfy the access control policy of subsequent ciphertexts anymore; as a result, the backward secrecy is guaranteed.


## 6. Performance Analysis

In this section, the proposed scheme is compared in terms of functionality and performance with several related works.As shown in Table1, the schemes of Ning et al. [6], Liu et al. [15], Sethi et al. [27], Han et al. [22], and this proposal all provide traceability, but Ning et al.’s scheme [6] does not sustain a revocation mechanism, and it cannot revoke a malicious user to ensure security even if that malicious user is traced. Meanwhile, [27] adopts an indirect revocation mechanism and cannot revoke a malicious user timely. Since a malicious user is desired to be revoked immediately, a direct revocation mechanism is more suitable for a CP-ABE with traceability. The schemes of Liu et al. [15], Xu et al. [28], Sethi et al. [27], Han et al. [22], and this proposal try to support the ciphertext update when revocation occurs. The difference is that neither [15] nor [22] can resist user collusion attacks among users, and they cannot provide sufficient forward and backward secrecy. Moreover, Table 1 shows that schemes [6, 15, 22, 28] and ours are proved to be secure under a selective access policy against chosen-plaintext attacks in the standard model. Sethi et al.’s scheme [27] is proved statically [39] secure in the random oracle model. Generally, the standard model is more realistic than the random oracle model.Table 1
Functionality comparisons.
SchemeTraceabilityRevocationCiphertext updatingUser collusion resistanceSecurity[6]√××√Selective[15]√Direct√×Selective[22]√Direct√×Selective[27]√Indirect√√Static[28]×Indirect√√SelectiveOurs√Direct√√Selective√ denotes that the scheme has this functionality. × denotes that the scheme does not have this function.In Table2, our scheme’s efficiency is compared against several related ones. Note that [27] supports multi-authority functionality; here, we make comparisons in a single-authority scenario without reducing its efficiency. Our scheme’s complete encryption phase period consists of two parts. One is the LocalEncrypt algorithm performed by a DO, and the other is the ReEncrypt algorithm executed by a CSP, thereby reducing computing overhead for the DO by outsourcing the latter algorithm to the CSP. In the LocalEncrypt algorithm, our scheme is slightly better than previously published schemes [15, 22] and is significantly more efficient than schemes [6, 27, 28]. When we take the ReEncrypt algorithm into consideration, both the exponentiation operations and multiplication operations of our complete encryption process are less than that in [6, 22]. Compared with [15], our complete encryption process has one more exponentiation operation and ℓ additional multiplication operations. Since multiplication is not as costly as exponentiation, it will not bring unacceptable overhead. A more intuitive illustration will be presented in the following experimental analysis. Our scheme is still competitive after accounting for computations of the ReEncrypt algorithm. Compared with these direct revocable schemes [15, 22], the computational effort of our KeyGen algorithm is related to the depth of the binary tree. We note that it is acceptable because we only need to do it once for a user. For those indirect revocable schemes [27, 28], an update key generation (UpdateKeyGen) algorithm is required in addition to the basic KeyGen algorithm, which brings additional overhead. As for the overhead of the Decrypt algorithm, our scheme is similar to that in schemes [15] and is more efficient than [6, 22, 27]. The computation of the Decrypt algorithm in [28] is further affected by the length of the binary representation of a valid period. For the CTUpdate algorithm, our solution performs better than that in [27, 28] but is less efficient than [15, 22]. Our CTUpdate algorithm does bring more computation overhead. With these efforts, our scheme realizes that user collusion attacks resistance and guarantees sufficient backward secrecy, whereas schemes [6, 15, 22] do not hold such functionality. The user collusion resistance is necessary for traceable and revocable CP-ABE. A malicious user in [15, 22] can launch such attacks to illegally revalidate the decryption key without being caught by the trace mechanism. A CP-ABE scheme with user collusion resistance will be more effective and practical. Schemes [27, 28] also achieve backward secrecy by a ciphertext update algorithm. On the premise of meeting the backward secrecy, our ciphertext update algorithm is more efficient among these existing works. Furthermore, as the complete workload of the CTUpdate algorithm is outsourced to the semi-trusted CSP, data owners do not need to worry about such computational pressure.Table 2
Efficiency comparisons.
SchemeKeyGenUpdateKeyGenLocalEncryptReEncryptDecryptTraceCTUpdate[6](5 + 3s)E+(1 + 2 s)M—(3 + 5ℓ)E + (1 + 2 ℓ)M—(1 + 3n)P + (2 + n)E + (3 + 3 n)M(5 + 3s)P + (2 + s)E + (3 + 2 s)M—[15](7 +s)E + 2M—(3 + 2ℓ + r)E + (1 + ℓ)M—(3 + 2n)P + (3 + n)E + (6 + 2 n)M(2 + 2s)P + E + Mt E[22](6 +s)E + (1 + s)M—(3 + 4ℓ + r)E + (1 + ℓ)M—(2 + 3n)P + (3 + n)E + (4 + 3 n)M(6 +s)P + (2 + s)E + (3 + s)Mt E[27](3 +s+d)E + sdM(3 +r+v)E + r+vM(1 +v  + 9 ℓ + vℓ)E + (1 + v+2ℓ)M—4nP + 4 n E + 8 n M(3 +s + sd)P + 3E + (4 + 2 sd)M1+v+v′+9ℓ+v′ℓE+2+8ℓ+v+2v′M[28](3 + 3s + d)E + (2 s + d)M(3 + 3v + d)E + (2 v + d)M(2 + 5ℓ + 5 v)E + (1 + 2 ℓ + 2 v)M—(1 + 3n + 3 v)P + n+vE + (1 + 3 n + 3 v)M—(2 + 5ℓ + 5 v)E + (2 + 5 ℓ + 5 v)MOurs(4 +s + d)E + M—(3 + 2ℓ)E + (1 + ℓ)M1+r E + ℓM(2 + 2n)P + (2 + n)E + (3 + 3 n)M(2 + 2s)P + E + M(4 +r+2ℓ)E + (3 + 3ℓ)Ms denotes the number of user’ attributes. ℓ denotes the number of attributes in the access structure. n denotes the number of attributes in the decryption key that satisfy the access structure. r denotes the number of nodes in coverR. d denotes the depth of the binary tree. v denotes the length of a valid period formatted in binary representation [27, 28]. v′ denotes the hamming distance between the binary strings of two different periods in [27]. t=∑j∈coverR′depthj′−1−depthj denotes the ciphertext affected by revocation. E denotes an exponentiation operation in G and GT. M denotes a multiplication operation in G and GT. P denotes a bilinear pairing operation.For the schemes listed in Table2, Figures 2(a)–2(e) depict the time cost comparisons on KeyGen, Encrypt, Decrypt, Trace, and CTUpdate algorithms. The experiment was carried out on a Linux system with an Intel Core i7-10750H CPU @2.60 GHz and 4.00 GB RAM. To build the code, we used PBC-0.5.14 Library, Charm-Crypto 0.50 framework, and PyCharm Community 2021.1 IDE.Figure 2
Time cost comparisons. (a) KeyGen time, (b) Encrypt time, (c) Decrypt time, (d) Trace time, and (e) CTUpdate time.
(a)(b)(c)(d)(e)We take Figure1 as the binary tree in the experiment, and by supposing the previous user revocation list R=u5, we have coverR=1,6,12. Then, it is assumed that the newly captured malicious user is u1, which means R′=u1,u5 and coverR′=4,6,8,12. In our experiment, the number of user attributes ranges from 10 to 50 with a step of 10. The final result is the mean of 100 replicates. In addition, since schemes [27, 28] introduce a valid period formatted in binary representation but do not specify the length of the binary string, we restrict it to 1 for simplicity.Figure2(a) shows that the KeyGen time of the proposed scheme is highly approximate to that of schemes [15, 22], and all of those two schemes and ours are significantly more efficient than schemes [6, 27, 28]. To make a clear description, we present the overhead of LocalEncrypt and ReEncrypt algorithms simultaneously in Figure 2(b). Our scheme is still competitive with these schemes after accounting for computations of the ReEncrypt algorithm. Figures 2(c) and 2(d) present the data of decrypt time and trace time, respectively, and the results indicate that our scheme is more efficient in both the Decrypt algorithm and Trace algorithm. Figure 2(e) shows that both [15, 22] have higher ciphertext updating efficiency, but the CTUpdate algorithm in these two schemes is limited by their revocation mechanisms and cannot resist a revoked user who preserves the intermediate values (e.g., Yid in [15]) or launches user collusion attacks. The other two schemes [27, 28] and ours do not suffer from such problems. On the premise of meeting the security requirement, our CTUpdate algorithm is more efficient among them. In general, the simulation results agree with the above theoretical analysis.


## 7. Related Work

Sahai and Waters [2] were the first of many investigators to introduce attribute-based encryption (ABE). In such an attribute-based encryption system, different from the case in traditional public key cryptography, there is no need to prepare exclusive ciphertexts for various users. A data owner could share data with multiple expected data users without complex key distribution techniques. The advent of ABE brings a unique “one-to-many” public key encryption capability that enables fine-granted access control over encrypted data.In subsequent studies, to meet various functional requirements, ABE schemes have become increasingly complicated. Revocation is a critical bottleneck limiting its practical application. Given a cloud storage system based on a primitive class of CP-ABE scheme, the case where a malicious user wants to sell his/her decryption key for profit should be considered. Since those attributes associated with the mentioned decryption key might be shared by multiple users with no unique information indicating the holder’s identity, the malicious user can avoid being held accountable. To address this issue, traceable CP-ABE schemes [5, 6] in which whoever leaks a decryption key can be identified were proposed.Improving traceability, though it might identify the leakage, does not guarantee a solution to the problem, of course, since it does not necessarily lead to removing the malicious user. ABE schemes require not only tracing a defected user but also revoking him/her from the system.Li et al. [7] presented a CP-ABE, which enables directly revoking corrupted users. Liu and Wong [40] gave constructions of both KP-ABE and CP-ABE that sustain revocation. Liu et al. [14] realized direct user revocation mechanisms by embedding a valid period value and a revocation list into the ciphertext. Shi et al. [41] proposed a novel KP-ABE scheme, in which outsourced encrypted data can be updated by an untrusted third party and those revoked users cannot decrypt the prior ciphertexts. Inspired by [5, 41], Liu et al. [15] constructed a CP-ABE scheme with white-box traceability and user revocation that allows, once a malicious user is traced, a user’s identity will be added to a revocation list; when combined with a ciphertext update algorithm, backward secrecy is achieved as the revoked user is denied access to the previously encrypted data. Han et al. [22], focusing on protecting access policy, proposed a CP-ABE scheme that realizes white-box traceability, revocation, and the application of hidden policy. However, both schemes of Liu et al. [15] and Han et al. [22] suffer from collusion attacks between users.User collusion resistance and backward secrecy are inherent required but easily overlooked properties of a secure CP-ABE system. Li et al.’s scheme [7] supported user collusion resistance, but did not realize backward secrecy. Zhang et al. [42] showed an effective white-box traceable CP-ABE scheme that can resist user collusion attacks, but it lacked a revocation mechanism. Li et al. [19] tried to address collusion attacks executed by the existing users cooperating with those revoked users with a scheme achieving indirect revocation by binding together the user’s decryption key and group secret key. The downside in Li et al.’s scheme [19] was that the trusted authority bore the burden of re-encryption and updating the decryption key whenever revocation was required. For a system with a large number of users, communication protocol and computing overhead would be equally large.


## 8. Conclusion

In this work, we presented a directly revocable CP-ABE scheme with user collusion resistance, white-box traceability, and both forward and backward secrecy. Once a malicious user is revoked, he/she will lose access to subsequent and previous encrypted data. The scheme also prevents complicity between a revoked user and a legitimate user in the system. Any component of another user’s decryption key will make no sense in revalidating the revoked user’s decryption key, and even if a malicious user chooses to leak the full decryption key, the malicious user could be captured by white-box tracing technology. In addition, using an effective proxy re-encryption mechanism and an outsourced ciphertext update algorithm, the scheme reduces the computational burden on data owners and cuts down the communication overhead between data owners and cloud service providers, respectively. The performance analysis showed that our proposal is better in functionality and competitive in efficiency compared with existing schemes. Further, our scheme was proved selectively secure against chosen-plaintext attacks in the standard model.



---

*Source: 6074322-2022-09-23.xml*