# An Efficient User’s Attribute Revocation Scheme Suitable for Data Outsourcing in Cloud Storage

Authors: Fang Zheng; Xinguang Peng; Zhidan Li
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

With the advances of cloud data centers and cloud service, many application scenarios are developed such as enterprise business, the Vehicular Ad Hoc Networks (VANET), Sensor network. Confidentiality and efficiency are two key problems. CP-ABE is one of fine-grained access control cryptographic technologies and it is widely applied in outsourced data in cloud storage to protect the user’s privacy. In addition, besides confidentiality, computational cost is an important factor which makes the application of CP-ABE possible in the situations. In this paper, we propose a novel and fast scheme based on CP-ABE algorithm from the respect of the user’s attribute revocation to make it faster. In this scheme, we construct an identical tree T2 that has the same structure as the actual access control tree T1. When the user issues to request the encrypted text preserved on CSP, CSP first tries to decrypt CT2 which is encrypted according to the access policy based on the identical tree T2 and also preserved on it, with the subset of the secret keys corresponding to the indexes of the attributes provided by the user. If CSP can successfully decrypt it, it proves that he/she has the authorization to access the cryptographic text CT1 and CSP will send CT1 to the user. Otherwise, CSP recognizes that the user has no access to CT1 and rejects to send CT1 to the user. Namely, we can decide if we authorize the right to access CT1 by judging if the secret key provided by the user can decrypt CT2. Because CT1 and CT2 have the same access control structure, they have the same secret key for decryption; that is, when some attributes are revoked, if the secret key cannot decrypt CT2, it cannot decrypt CT1. While CSP can directly decrypt CT2, but not CT1, CSP can judge if the user has access to CT1 after the attribute revocation by decryption of CT2. Moreover, we propose the construction method of CT1 and CT2. Finally, we prove that the scheme is secure and viable.


---

## Body

## 1. Introduction

With the development of cloud services, many application scenarios based on cloud data centers appear, such as enterprise business, the Vehicular Ad Hoc Networks (VANET), and Sensor network. Meanwhile these services require confidentiality and efficiency.As one of fine-grained access control technologies, CP-ABE (Ciphertext-Policy Attribute-Based Encryption) is widely applied in the outsourced data in cloud storage to protect the user’s privacy and prevent CSP (Cloud Service Provider) from peeping the user’s contents. But it meets a problem about revocation which includes three kinds [1–5]. One is system attributes revocation which denotes that one or more attributes on access control tree is revoked including the attributes being removed or the logic relationship among attributes being destroyed; that is, it means the access control tree is changed. The second is user revocation, which denotes that the user loses the access to the cryptographic text. The third is user’s attributes revocation, which means that the user’s partial attributes are revoked; that is, AA (Attribute Authorization) revokes the user’s partial attributes which probably makes him/her lose the right to visit the ciphertext. For example, assume that A is one of teachers in university B and A has the attributes of Prof (Professor), Dr (Doctor), and CD (Computer Department). In this system, B takes the role of AA and the three attributes of A are authorized by B and B can revoke one of the attributes, such as Dr. Then the attributes owned by A have been changed from {Prof, Dr, CD} to {Prof, CD}. Suppose that the access control tree is as in Figure 1 and ciphertext C is encrypted according to the access control policy. Then when the attribute CD is revoked, the user will lose the right to visit ciphertext C, while if the revoked attribute is Dr, then the user still has the access to C. So, we can conclude that the user’s attributes revocation can influence him/her to visit the ciphertext.Figure 1
The example of CP-ABE.There are many literature studies on the three cases. When all the attributes of the user are revoked, we will think that the user been revoked. In this paper, we will discuss the last two cases, that is, the user revocation and user’s attributes revocation.To the situations which require the high time efficiency, for example, the Vehicular Ad Hoc Networks (VANET) and Sensor network, a fast CP-ABE algorithm is very important. The existing schemes of user’s attribute revocation are mainly realized by reencrypting the ciphertext [6–8] or updating the private keys of the nonrevoked users and reencrypting the ciphertext. Our scheme neither updates the secret keys nor reencrypts the ciphertext. We accomplish the attribute revocation and user revocation by constructing a tree T2 identical with the real access control tree T1 for every user. The two trees have the same complete nodes and structure. The leaf nodes denote the different attributes. To a fixed system, its system tree with all the attributes provided by the system is fixed. So, we can define the secret keys set for the system tree as SK=ski|i=1,2,…,n and the attributes set as S=si|i=1,2,…,n and the leaf nodes set as LF=xi|i=1,2,…,n; then there is one-to-one correspondence between the elements in SK and S and there is one-to-one correspondence between the elements in S and LF. When the system tree is generated, SK, S, and LF will be generated and fixed. To the different users, they have different leaf nodes which are authorized by AA. Figure 2(a) is a system tree which has four leaf nodes and the whole attributes set is S=A1,A2,A3,A4,A5, while Figures 2(b) and 2(c) show two trees, T1 and T2, which both belong to the same user and the attributes set is S1=S2=A1,A3,A4. From the figure, we can know that the tree corresponding to any user is a subtree whose leaf nodes are a subset of the system tree and the attributes set of any user is a subset of the whole attributes set of the system. So, the secret keys based on the subtree are the subset of those based on the system tree if they are all generated by the same curve parameters. To one user, suppose that his/her secret keys are set as SK1 and SK2 which are, respectively, generated according to trees T1 and T2 which have the same structure. If SK1 can decrypt the ciphertext encrypted based on the access control tree T1, then the cryptographic text encrypted based on tree T2 can also be decrypted by SK2 which are from the same leaf nodes as SK1. According to this principle, we can know whether the nonrevoked attributes set of the user has the right to decrypt the ciphertext CT1 by judging if CT2 encrypted based on the identical tree T2 can be decrypted with the secret keys on the corresponding leaf nodes. Although SK1 and SK2 are generated from the same leaves of trees that have the same structure, SK1 and SK2 are not the same if the parameters that generate their elliptic curves are different. So, SK2 is generated by and preserved on CSP; in the same way, ciphertext CT2 is encrypted by and preserved on CSP. CSP can decide if the user has access to CT1 which is encrypted by the user itself and uploaded on CSP by judging if CT2 can be decrypted by SK2. SK2 varies with the variation of the leaf nodes on the access control tree, which is noticed by uploading the new leaf node indexes of tree T1 to CSP.Figure 2
(a) The system tree to a fixed system. (b) The access control policy tree T1 corresponding to a fixed user. (c) The identical tree T2 corresponding to a fixed user.
(a)(b)(c)The contributions of this paper are as follows:(1)
Our scheme is novel. We construct a treeT2 that is identical with the access control tree T1. By judging whether the identical tree T2 can be decrypted by SK2, CSPs decide whether to send ciphertext CT1 to the users.(2)
Our scheme is fast. The secret keys- (SK-) based system trees are shared by all the users and only generated once. To the different user, the secret key SK2 based on T2 is a subset of SK. It is not necessary to regenerate SK2 but select the elements from SK to reconstruct SK2, which saves the elapsed time.(3)
Our scheme is secure. TreesT1 and T2 have different curve parameters. So, the secret keys of T2 cannot decrypt ciphertext encrypted based on T1.Therefore, CSP cannot decrypt the data owner’s cryptographic text.(4)
Our scheme does not need to update the secret keys and ciphertext and suits the scenarios that require high time efficiency, such as the Vehicular Ad Hoc Networks (VANET) and IoT network.The remainder of the paper is organized as follows: Section2 presents related work; Section 3 discusses preliminaries of cryptography; Section 4 gives the definition of our scheme; Section 5 discusses the detailed realization of our scheme; Section 6 presents the secure analysis; Section 7 presents the time efficiency analysis; Section 8 gives optimization scheme; Section 9 discusses the experiment; Section 10 gives the conclusion.


## 2. Related Work

### 2.1. Green Energy and Time Efficiency in Cloud Data Centers

Green energy and time efficiency in cloud data centers are two hot spots, which can keep the applications setup on it running efficiently. The existing literature focus on the energy saving, resource distribution, overload reduction, algorithm improvement, and so forth.Mohammed Joda Usman et al. in 2019 [9] proposed a scheme to solve the problem of distributing virtual resources in cloud data centers with an Energy-oriented Flower Pollination Algorithm (E-FPA), which minimizes resource wastage and increases energy efficiency. Jitendra Kumar Verma et al. [10] proposed three heuristic models combining the relation between power consumption and resource utilization and virtual machine technique to reduce energy consumption with minimal variation in service-level agreements negotiated. Sourya Joyee et al. in 2015 [11] proposed an efficient encryption based on CP-ABE by dividing the encryption process into two phases, offline phase and online phase, as well as a fast decryption scheme by introducing a third proxy server to partially decrypt the ciphertext and then transmit the rest to the mobile device to compensate the shortcoming of the slow speed of the mobile device. The works in [9, 10] kept the cloud servers running efficiently from the aspect of energy leverage. The work in [11] improved the algorithm to reduce the overload of the cloud server. Compared with the previously mentioned schemes, our methods boost the efficiency of cloud server from the improvement of user’s attribute revocation.


### 2.2. CP-ABE Algorithm

CP-ABE is a classical public key encryption algorithm based on ciphertext attributions widely used on many scenarios, especially in cloud services. In this section, we will introduce the study trajectory.Yu et al. in 2012 [12] proposed an attribute revocation scheme, the idea of which is that when the attributes are revoked, AA reencrypts the ciphertexts and updates the private keys for all the nonrevoked users. To the situation where a lot of attributes or users are revoked, the scheme cannot satisfy the need. Hur and Noh in 2011 [13] and Xie et al. in 2013 [14] proposed the user and attributes revocation scheme based on the attribute key encryption keys (KEKs) generated by a global binary tree in which the leaf nodes denote the users. Naruse et al. in 2014 [15] proposed an attribute revocation scheme to CP-ABE schemes using a cloud server by proxy reencryption to revoke attributes. This scheme does not require generation of the new secret key when granting attributes to a user. In this scheme, the ciphertext needs to be updated. Cheng et al. in 2013 [16] proposed an optimization revocation scheme based on CP-ABE by selecting a random partial block instead of the whole file to perform revocation to decrease the cost of revocation. But the overhead of data publishing and retrieval is increased. Genlang et al. in 2019 [17] proposed a revocation scheme that constructs an AA tree in which every attribute is a child node of the root and has many leaf nodes named accumulators representing a user. One user has one or more attributes. When the user requests to visit the ciphertext, CSPs will generate the reencryption key to encrypt the ciphertext for the user with the nonrevoked attributes. This scheme needs to reencrypt the ciphertext. Shan-shan Tu et al. in 2012 [18] proposed a fully fine-grained direct attribute revocation scheme based on composite order bilinear groups and LSSS including all revoked user lists corresponding to every attribute. CSPs need to reencrypt the ciphertext. Benjamin Wesolowski et al. in 2016 [19] proposed a ciphertext-policy attribute-based broadcast encryption scheme (CP-ABBE) supporting negative attributes and able to handle access policies in conjunctive normal form (CNF). The ciphertext length remains linear in the size of the access policy and in the number of revoked receivers but independent of all the users in the system. But this ciphertext is associated with the revoked users; when the revoked users change, the ciphertext needs to be reencrypted. Liu et al. in 2018 [20] proposed a solution adopting techniques on secure outsourcing of pairings to support outsourcing computation and adopting some techniques based on the tree-based scheme to solve user revocation and attribute revocation. But this scheme needs to reencrypt the ciphertext. Shangping et al. in 2018 [21] proposed an attribute revocation by delegating the update of the secret key and ciphertext. Premkamal et al. in 2019 [22] proposed a scheme of verifiable outsourced CP-ABE and transfer of the computational overhead to the proxy server. Li et al. in 2020 [23] proposed verifiable outsourced decryption scheme which can simultaneously verify the correctness for transformed ciphertext for the authorized users and unauthorized users. Gao et al. in 2020 [24] proposed a new trustworthy secure ciphertext-policy and attribute hiding access control scheme based on blockchain to solve the problems of high trust-building cost, single point of failure, and privacy leakage. Li et al. in 2021 [25] proposed an efficient extended file hierarchy CP-ABE scheme (EFH-CP-ABE) to encrypt multiple files on the same access level.The above schemes improve the security, computational efficiency, and verifiability of the CP-ABE algorithm. But all these schemes need to update the secret keys and ciphertext when CSP judges if the user’s authority is revoked, which will spend a lot of time.


### 2.3. The Application of CP-ABE Algorithm

Taha et al. in 2019 [26] proposed a scheme of vehicles cluster based on CP-ABE, which assigns the encryption tasks through the vehicle information to save the computational cost. Laaboudi et al. in 2019 [27] proposed the scheme based on group encryption CP-ABE applied to communication protection of IPS and IDS. Zhang et al. in 2021 [28] designed an online privacy-protective decryption testing algorithm using a partially HP-CP-ABE (PHP-CP-ABE) method to prevent the attribute values guessing attacks (AVGA). Sowjanya et al. in 2021 [29] proposed a lightweight key management mechanism for the CP-ABE scheme using Elliptic Curve Cryptography (ECC) to solve the problems of security, privacy, and computational complexity in IoT in medical care.The above literature focus on application of CP-ABE in Vehicular Ad Hoc Networks, IoT network, and so forth. The focus of such applications takes attentions on security, efficiency, and privacy, especially in computational cost. But all these schemes need to update the secret keys and ciphertext when CSP judges if the user’s authority is revoked, which will spend a lot of time.


## 2.1. Green Energy and Time Efficiency in Cloud Data Centers

Green energy and time efficiency in cloud data centers are two hot spots, which can keep the applications setup on it running efficiently. The existing literature focus on the energy saving, resource distribution, overload reduction, algorithm improvement, and so forth.Mohammed Joda Usman et al. in 2019 [9] proposed a scheme to solve the problem of distributing virtual resources in cloud data centers with an Energy-oriented Flower Pollination Algorithm (E-FPA), which minimizes resource wastage and increases energy efficiency. Jitendra Kumar Verma et al. [10] proposed three heuristic models combining the relation between power consumption and resource utilization and virtual machine technique to reduce energy consumption with minimal variation in service-level agreements negotiated. Sourya Joyee et al. in 2015 [11] proposed an efficient encryption based on CP-ABE by dividing the encryption process into two phases, offline phase and online phase, as well as a fast decryption scheme by introducing a third proxy server to partially decrypt the ciphertext and then transmit the rest to the mobile device to compensate the shortcoming of the slow speed of the mobile device. The works in [9, 10] kept the cloud servers running efficiently from the aspect of energy leverage. The work in [11] improved the algorithm to reduce the overload of the cloud server. Compared with the previously mentioned schemes, our methods boost the efficiency of cloud server from the improvement of user’s attribute revocation.


## 2.2. CP-ABE Algorithm

CP-ABE is a classical public key encryption algorithm based on ciphertext attributions widely used on many scenarios, especially in cloud services. In this section, we will introduce the study trajectory.Yu et al. in 2012 [12] proposed an attribute revocation scheme, the idea of which is that when the attributes are revoked, AA reencrypts the ciphertexts and updates the private keys for all the nonrevoked users. To the situation where a lot of attributes or users are revoked, the scheme cannot satisfy the need. Hur and Noh in 2011 [13] and Xie et al. in 2013 [14] proposed the user and attributes revocation scheme based on the attribute key encryption keys (KEKs) generated by a global binary tree in which the leaf nodes denote the users. Naruse et al. in 2014 [15] proposed an attribute revocation scheme to CP-ABE schemes using a cloud server by proxy reencryption to revoke attributes. This scheme does not require generation of the new secret key when granting attributes to a user. In this scheme, the ciphertext needs to be updated. Cheng et al. in 2013 [16] proposed an optimization revocation scheme based on CP-ABE by selecting a random partial block instead of the whole file to perform revocation to decrease the cost of revocation. But the overhead of data publishing and retrieval is increased. Genlang et al. in 2019 [17] proposed a revocation scheme that constructs an AA tree in which every attribute is a child node of the root and has many leaf nodes named accumulators representing a user. One user has one or more attributes. When the user requests to visit the ciphertext, CSPs will generate the reencryption key to encrypt the ciphertext for the user with the nonrevoked attributes. This scheme needs to reencrypt the ciphertext. Shan-shan Tu et al. in 2012 [18] proposed a fully fine-grained direct attribute revocation scheme based on composite order bilinear groups and LSSS including all revoked user lists corresponding to every attribute. CSPs need to reencrypt the ciphertext. Benjamin Wesolowski et al. in 2016 [19] proposed a ciphertext-policy attribute-based broadcast encryption scheme (CP-ABBE) supporting negative attributes and able to handle access policies in conjunctive normal form (CNF). The ciphertext length remains linear in the size of the access policy and in the number of revoked receivers but independent of all the users in the system. But this ciphertext is associated with the revoked users; when the revoked users change, the ciphertext needs to be reencrypted. Liu et al. in 2018 [20] proposed a solution adopting techniques on secure outsourcing of pairings to support outsourcing computation and adopting some techniques based on the tree-based scheme to solve user revocation and attribute revocation. But this scheme needs to reencrypt the ciphertext. Shangping et al. in 2018 [21] proposed an attribute revocation by delegating the update of the secret key and ciphertext. Premkamal et al. in 2019 [22] proposed a scheme of verifiable outsourced CP-ABE and transfer of the computational overhead to the proxy server. Li et al. in 2020 [23] proposed verifiable outsourced decryption scheme which can simultaneously verify the correctness for transformed ciphertext for the authorized users and unauthorized users. Gao et al. in 2020 [24] proposed a new trustworthy secure ciphertext-policy and attribute hiding access control scheme based on blockchain to solve the problems of high trust-building cost, single point of failure, and privacy leakage. Li et al. in 2021 [25] proposed an efficient extended file hierarchy CP-ABE scheme (EFH-CP-ABE) to encrypt multiple files on the same access level.The above schemes improve the security, computational efficiency, and verifiability of the CP-ABE algorithm. But all these schemes need to update the secret keys and ciphertext when CSP judges if the user’s authority is revoked, which will spend a lot of time.


## 2.3. The Application of CP-ABE Algorithm

Taha et al. in 2019 [26] proposed a scheme of vehicles cluster based on CP-ABE, which assigns the encryption tasks through the vehicle information to save the computational cost. Laaboudi et al. in 2019 [27] proposed the scheme based on group encryption CP-ABE applied to communication protection of IPS and IDS. Zhang et al. in 2021 [28] designed an online privacy-protective decryption testing algorithm using a partially HP-CP-ABE (PHP-CP-ABE) method to prevent the attribute values guessing attacks (AVGA). Sowjanya et al. in 2021 [29] proposed a lightweight key management mechanism for the CP-ABE scheme using Elliptic Curve Cryptography (ECC) to solve the problems of security, privacy, and computational complexity in IoT in medical care.The above literature focus on application of CP-ABE in Vehicular Ad Hoc Networks, IoT network, and so forth. The focus of such applications takes attentions on security, efficiency, and privacy, especially in computational cost. But all these schemes need to update the secret keys and ciphertext when CSP judges if the user’s authority is revoked, which will spend a lot of time.


## 3. Preliminaries

### 3.1. Symbols Abbreviations

Table1 shows the symbols abbreviations and their corresponding descriptions.Table 1
Symbols abbreviations.
AbbreviationDescriptionTThe system treeT1The access control policy treeT2The tree identical withT1SKThe secret keys set for the system treeTCT1Ciphertext encrypted by the user itself according toS1 with the elliptic curves parameter G01,g1CT2Ciphertext encrypted by the CSP according toS2 with the elliptic curves parameter G02,g2G01,g1The parameters of constructingT1G02,g2The parameters of constructingT 2SiTheith user’s attributes setSK1iTheith user’s secret keys set of T1iSK2iTheith user’s secret keys set of T2ip,g,α,βThe parameters related to the algorithm of CP-ABECT1iCiphertext encrypted by theith user itself according to SiCT2iCiphertext encrypted by theith user according to SiS1The attributes set ofT1S2The attributes set ofT2SK1The secret key set ofT1SK2The secret key set ofT2PK1The public key ofT1PK2The public key ofT2MSK1The main secret key ofT1MSK2The main secret key ofT2T1iThe access control tree corresponding to theith userT2iThe tree identical withT1iIiThe indexes set to theith user’s attributes setC˜,C,Cy1,Cy1'The components involved inCT1Cy2,Cy2'The components involved inCT2MThe plain text


### 3.2. Bilinear Maps

DefineG and GT as two cyclic groups of prime order p. Then the Discrete Logarithm Problem on G and GT is a hard problem. A bilinear function map e is defined as G∗G−>GT; its properties are as follows [2]:(1)
∀g∈G and a,b∈ZP∗, ega,gb=eg,gab(2)
eg,g≠1


### 3.3. BDHE Assumption

The BDHE problem [6, 14] is to compute eg,gaq+1s∈GT, in which g is a generator of group G and y⟶=g1,…,gq,gq+1,…,g2q,gs. Let gi denote gai.IfPrℬy⟶,g,T=eg,gaq+1s=0−Prℬy⟶,T=R=0≥ε, we will regard that there exists a polynomial-time algorithm ℬ that has advantage ϵx to solve the decisional BDHE problem.


### 3.4. Lagrange Coefficient [30]

(1)Δi,Sx=∏jϵS,j≠ix−ji−j,i∈ZpandSis a set of elements inZp.


### 3.5. Waters’ CP-ABE Scheme

Setup. The algorithm is used to initialize the system. It takes as input an implicit security parameter and outputs the public parameter PK and a master key MK.EncryptPK,M,A. The algorithm is used to encrypt the message. It takes as input PK, a message M, and an access structure A. It encrypts M and generates a ciphertext CT. Only when the attributes set that the user owns satisfies A can the user decrypt the message.KeyGenerationMK,S. The algorithm is used to produce the private keys. It takes as input the master key MK and a set of attributes S and outputs the private key SK.DecryptPK,CT,SK. The algorithm is used to decrypt the ciphertext. It takes as input the public parameter PK, a ciphertext CT, and a private key SK. If the set of attributes S satisfies the access structure A, then it will decrypt the ciphertext CT and return the message M [31].


### 3.6. Access Structure

LetP1,P2,…,Pn be a set of parties. A collection A⊆2P1,P2,…,Pn is monotone if, ∀B,C, if B∈Λ and B⊆C then C∈Λ. An access structure (respectively, monotone access structure) is a collection (resp. monotone collection) Λ of nonempty subsets of P1,P2,…,Pn; that is, Λ⊆2P1,P2,…,Pn/ϕ. The sets in Λ are called the authorized sets, and the sets not in Λ are called unauthorized sets [32].


### 3.7. Access Trees

Every nonleaf node of the tree represents a threshold gate, described by its children and a threshold value. Definenx as the children number of a node x and kx is its threshold value (0<kx<nx). If the threshold gate is an OR gate and then kx=1, while the threshold gate is an AND gate and then kx=nx. Each leaf node x of the tree represents an attribute in the attribute set S and the value of it is kx.


## 3.1. Symbols Abbreviations

Table1 shows the symbols abbreviations and their corresponding descriptions.Table 1
Symbols abbreviations.
AbbreviationDescriptionTThe system treeT1The access control policy treeT2The tree identical withT1SKThe secret keys set for the system treeTCT1Ciphertext encrypted by the user itself according toS1 with the elliptic curves parameter G01,g1CT2Ciphertext encrypted by the CSP according toS2 with the elliptic curves parameter G02,g2G01,g1The parameters of constructingT1G02,g2The parameters of constructingT 2SiTheith user’s attributes setSK1iTheith user’s secret keys set of T1iSK2iTheith user’s secret keys set of T2ip,g,α,βThe parameters related to the algorithm of CP-ABECT1iCiphertext encrypted by theith user itself according to SiCT2iCiphertext encrypted by theith user according to SiS1The attributes set ofT1S2The attributes set ofT2SK1The secret key set ofT1SK2The secret key set ofT2PK1The public key ofT1PK2The public key ofT2MSK1The main secret key ofT1MSK2The main secret key ofT2T1iThe access control tree corresponding to theith userT2iThe tree identical withT1iIiThe indexes set to theith user’s attributes setC˜,C,Cy1,Cy1'The components involved inCT1Cy2,Cy2'The components involved inCT2MThe plain text


## 3.2. Bilinear Maps

DefineG and GT as two cyclic groups of prime order p. Then the Discrete Logarithm Problem on G and GT is a hard problem. A bilinear function map e is defined as G∗G−>GT; its properties are as follows [2]:(1)
∀g∈G and a,b∈ZP∗, ega,gb=eg,gab(2)
eg,g≠1


## 3.3. BDHE Assumption

The BDHE problem [6, 14] is to compute eg,gaq+1s∈GT, in which g is a generator of group G and y⟶=g1,…,gq,gq+1,…,g2q,gs. Let gi denote gai.IfPrℬy⟶,g,T=eg,gaq+1s=0−Prℬy⟶,T=R=0≥ε, we will regard that there exists a polynomial-time algorithm ℬ that has advantage ϵx to solve the decisional BDHE problem.


## 3.4. Lagrange Coefficient [30]

(1)Δi,Sx=∏jϵS,j≠ix−ji−j,i∈ZpandSis a set of elements inZp.


## 3.5. Waters’ CP-ABE Scheme

Setup. The algorithm is used to initialize the system. It takes as input an implicit security parameter and outputs the public parameter PK and a master key MK.EncryptPK,M,A. The algorithm is used to encrypt the message. It takes as input PK, a message M, and an access structure A. It encrypts M and generates a ciphertext CT. Only when the attributes set that the user owns satisfies A can the user decrypt the message.KeyGenerationMK,S. The algorithm is used to produce the private keys. It takes as input the master key MK and a set of attributes S and outputs the private key SK.DecryptPK,CT,SK. The algorithm is used to decrypt the ciphertext. It takes as input the public parameter PK, a ciphertext CT, and a private key SK. If the set of attributes S satisfies the access structure A, then it will decrypt the ciphertext CT and return the message M [31].


## 3.6. Access Structure

LetP1,P2,…,Pn be a set of parties. A collection A⊆2P1,P2,…,Pn is monotone if, ∀B,C, if B∈Λ and B⊆C then C∈Λ. An access structure (respectively, monotone access structure) is a collection (resp. monotone collection) Λ of nonempty subsets of P1,P2,…,Pn; that is, Λ⊆2P1,P2,…,Pn/ϕ. The sets in Λ are called the authorized sets, and the sets not in Λ are called unauthorized sets [32].


## 3.7. Access Trees

Every nonleaf node of the tree represents a threshold gate, described by its children and a threshold value. Definenx as the children number of a node x and kx is its threshold value (0<kx<nx). If the threshold gate is an OR gate and then kx=1, while the threshold gate is an AND gate and then kx=nx. Each leaf node x of the tree represents an attribute in the attribute set S and the value of it is kx.


## 4. The Definition of Our Scheme

### 4.1. Formal Definition of Our Scheme

Based on Waters’ scheme of CP-ABE [31], we propose our scheme which includes six steps and is shown as follows:Setup. It takes as input G01,G02,g1, and g2 and outputs the public keys PK1 and PK2 and the master keys MSK1 and MSK2, respectively, for trees T1 and T2. This step is executed by DO.EncryptCTPK,M,T. It takes PK1,M,T1 as input and generates CT1. At the same time, it takes PK2,T2 as input and generates CT2.KeyGenMSK,S. It takes MSK1 and the user’s attributes S⊂A as input and generates the decryption secret key SK1 based on tree T1. At the same time, it takes MSK2 and S⊂A as input and generates the decryption key SK2 based on tree T2.ComputeTCx,Cx',SK,x. It takes CX,Cx′ involved in CT and SK as input, in which x is the node of the tree. The algorithm is recursively executed from the leaf node of the tree until the root node R. If SK satisfies the condition, the result of the algorithm is FR; otherwise, the result is ⊥.JudgeTCT2,SK2,Ii,Cy2,Cy2'. CSP judges if the attributes set Ii satisfies Ii⊆S by calling ComputeTCx,Cx′,SK,x. If the result is not ⊥, it proves that SK2 can decrypt CT2; that is, Ii⊆S, which proves that SK1 can decrypt CT1.DecryptCT1,SK1i. It takes CT1,SK1 as input and obtains the plaint text M.


### 4.2. Threat Model and Security Requirement

#### 4.2.1. CPA Security

Waters’ scheme [31] satisfies CPA security. Our scheme is constructed based on Waters’; so our scheme also satisfies CPA security. We design a game between the challenge and the adversary to describe the process which is as follows:Setup. The challenger generates the master keys MSK1 and MSK2 and the public keys PK1 and PK2, respectively, for trees T1W and T2W.Queryphase1. The adversary constructs many attribute sets S1,S2,S3… to issue corresponding requests of secret keys to the challenger. At the same time, the adversary sends the encrypted index sets corresponding to the attribute sets—EI1,EI2,EI3... to the challenger. The challenger generates SK1,SK2,SK3… . and adds j++,Si,SK1i,Ii to table T.Challenge. The adversary sends two equal-length messages M0,ρx∗,EIk and M1,ρx∗,EIk to the challenger. In these messages, Si constructed in query phase does not satisfy ρx∗. The challenger randomly selects β∈0,1 and encrypts Mβ as CT∗ with the access structure ρx∗ and then sends CT∗ to the adversary.Queryphase2. Run query phase 1. But, in this phase, the attribute sets issued by the adversary cannot be equal to the access structure ρx∗.Guess. The adversary outputs β′∈0,1 to the challenger.The advantage of the adversary in this game is defined asPrβ−β′−1/2 where the probability is taken over the random bits used by the challenger and the adversary.


#### 4.2.2. Data Confidentiality

CSP has no right to access the encrypted data and the user who does not satisfy the access control policy cannot visit the ciphertext.


#### 4.2.3. Collusion Resistance

Even if multiple users combine their attribute keys, they cannot decrypt the ciphertext.(i)
Backward Security. Backward security means that when a new user joins, if he/she is not authorized, he/she cannot access the plain text.


#### 4.2.4. Forward Security

Forward security means that if a user is revoked, even if he/she preserved the secret key before being revoked, he/she has no right to access the plain text.


## 4.1. Formal Definition of Our Scheme

Based on Waters’ scheme of CP-ABE [31], we propose our scheme which includes six steps and is shown as follows:Setup. It takes as input G01,G02,g1, and g2 and outputs the public keys PK1 and PK2 and the master keys MSK1 and MSK2, respectively, for trees T1 and T2. This step is executed by DO.EncryptCTPK,M,T. It takes PK1,M,T1 as input and generates CT1. At the same time, it takes PK2,T2 as input and generates CT2.KeyGenMSK,S. It takes MSK1 and the user’s attributes S⊂A as input and generates the decryption secret key SK1 based on tree T1. At the same time, it takes MSK2 and S⊂A as input and generates the decryption key SK2 based on tree T2.ComputeTCx,Cx',SK,x. It takes CX,Cx′ involved in CT and SK as input, in which x is the node of the tree. The algorithm is recursively executed from the leaf node of the tree until the root node R. If SK satisfies the condition, the result of the algorithm is FR; otherwise, the result is ⊥.JudgeTCT2,SK2,Ii,Cy2,Cy2'. CSP judges if the attributes set Ii satisfies Ii⊆S by calling ComputeTCx,Cx′,SK,x. If the result is not ⊥, it proves that SK2 can decrypt CT2; that is, Ii⊆S, which proves that SK1 can decrypt CT1.DecryptCT1,SK1i. It takes CT1,SK1 as input and obtains the plaint text M.


## 4.2. Threat Model and Security Requirement

### 4.2.1. CPA Security

Waters’ scheme [31] satisfies CPA security. Our scheme is constructed based on Waters’; so our scheme also satisfies CPA security. We design a game between the challenge and the adversary to describe the process which is as follows:Setup. The challenger generates the master keys MSK1 and MSK2 and the public keys PK1 and PK2, respectively, for trees T1W and T2W.Queryphase1. The adversary constructs many attribute sets S1,S2,S3… to issue corresponding requests of secret keys to the challenger. At the same time, the adversary sends the encrypted index sets corresponding to the attribute sets—EI1,EI2,EI3... to the challenger. The challenger generates SK1,SK2,SK3… . and adds j++,Si,SK1i,Ii to table T.Challenge. The adversary sends two equal-length messages M0,ρx∗,EIk and M1,ρx∗,EIk to the challenger. In these messages, Si constructed in query phase does not satisfy ρx∗. The challenger randomly selects β∈0,1 and encrypts Mβ as CT∗ with the access structure ρx∗ and then sends CT∗ to the adversary.Queryphase2. Run query phase 1. But, in this phase, the attribute sets issued by the adversary cannot be equal to the access structure ρx∗.Guess. The adversary outputs β′∈0,1 to the challenger.The advantage of the adversary in this game is defined asPrβ−β′−1/2 where the probability is taken over the random bits used by the challenger and the adversary.


### 4.2.2. Data Confidentiality

CSP has no right to access the encrypted data and the user who does not satisfy the access control policy cannot visit the ciphertext.


### 4.2.3. Collusion Resistance

Even if multiple users combine their attribute keys, they cannot decrypt the ciphertext.(i)
Backward Security. Backward security means that when a new user joins, if he/she is not authorized, he/she cannot access the plain text.


### 4.2.4. Forward Security

Forward security means that if a user is revoked, even if he/she preserved the secret key before being revoked, he/she has no right to access the plain text.


## 4.2.1. CPA Security

Waters’ scheme [31] satisfies CPA security. Our scheme is constructed based on Waters’; so our scheme also satisfies CPA security. We design a game between the challenge and the adversary to describe the process which is as follows:Setup. The challenger generates the master keys MSK1 and MSK2 and the public keys PK1 and PK2, respectively, for trees T1W and T2W.Queryphase1. The adversary constructs many attribute sets S1,S2,S3… to issue corresponding requests of secret keys to the challenger. At the same time, the adversary sends the encrypted index sets corresponding to the attribute sets—EI1,EI2,EI3... to the challenger. The challenger generates SK1,SK2,SK3… . and adds j++,Si,SK1i,Ii to table T.Challenge. The adversary sends two equal-length messages M0,ρx∗,EIk and M1,ρx∗,EIk to the challenger. In these messages, Si constructed in query phase does not satisfy ρx∗. The challenger randomly selects β∈0,1 and encrypts Mβ as CT∗ with the access structure ρx∗ and then sends CT∗ to the adversary.Queryphase2. Run query phase 1. But, in this phase, the attribute sets issued by the adversary cannot be equal to the access structure ρx∗.Guess. The adversary outputs β′∈0,1 to the challenger.The advantage of the adversary in this game is defined asPrβ−β′−1/2 where the probability is taken over the random bits used by the challenger and the adversary.


## 4.2.2. Data Confidentiality

CSP has no right to access the encrypted data and the user who does not satisfy the access control policy cannot visit the ciphertext.


## 4.2.3. Collusion Resistance

Even if multiple users combine their attribute keys, they cannot decrypt the ciphertext.(i)
Backward Security. Backward security means that when a new user joins, if he/she is not authorized, he/she cannot access the plain text.


## 4.2.4. Forward Security

Forward security means that if a user is revoked, even if he/she preserved the secret key before being revoked, he/she has no right to access the plain text.


## 5. The Detailed Implementation Scheme

We construct an identical treeT2 that has the completely same structure as the access control tree T1. The access control tree T1 is shown in Figure 2(b) marked with a yellow rectangle and the identical tree T2 is shown in Figure 2(c) marked with a red rectangle. They have the completely same structure including nodes and the relationship among nodes.


### 5.1. Architecture of Our Scheme

The CP-ABE system consists of DO (Data Owner), CSPs (Cloud Service Providers), DU (Data User), and AA (Attribute Authority). The architecture of our system is shown in Figure3 and the work flow of it is as follows:(1)
DO callsSetup to compute MSK1, PK1 and MSK2, PK2 and then publishes PK1 and PK2.(2)
DO callsEncryptCT to encrypt M as CT1.(3)
DO callsEncryptCT to compute CT2.(4)
AA generates a set of private keysSK1i based on tree T1 according to his/her attributes Si for each user, in which i denotes the ith user, and a set of secret keys SK2=ski|i=1,2... according to the identical tree T2 shared by all the users.(5)
AA transmitsSK2 to DO.(6)
DO uploads {CT1, CT2, SK2} to CSP.(7)
Theith DU requests to visit CT1 to CSPs.(8)
DU logs on AA and asks for private keys.(9)
AA sendsSK1i to DU.(10)
AA encrypts the indexes setIi which is corresponding to the attributes set of SK1i with the public key of CSPs and sends it to DU:(2)EuiSK1i,EcspIi,Ii=i|i=indexattx=indexSK1i,x∈Si.Now we take Figure2 as an example to illustrate the relationship between Ii and Si. Suppose that the attributes set Si is A1,A3,A4; then the indexes set Ii is 1,3,4.(11)
DU sendsSK1i,EcspIi to CSPs.(12)
CSP reconstructsSK2i from SK2 according to Ii ; for example, if Ii=1,3,4, SK2i=sk1,sk3,sk4.(13)
CSP callsJudgeTCT2 to decide if the user has the right to access CT1. If the returned result is equal to ⊥, CSP rejects the DU’s request.(14)
If the returned result is not equal to⊥, CSP sends CT1 to DU.(15)
DU callsDecryptCT to decrypt CT1.Figure 3
The architecture of our scheme.The algorithm process is given in Algorithm 1.Algorithm 1: An improved CP-ABE algorithm based identical tree.
DO:Setup() ⟶ MSK1, PK1 and MSK 2, PK2EncryptCT(PK1, M, T1) ⟶ CT1EncryptCT(PK2, T2) ⟶ CT2AA:KeyGenMSK1,Si ⟶ SK1iKeyGenMSK2,T2 ⟶ SK2SendsSK2 to DODO:Uploads {CT1,CT2,SK2} to CSPDU(the ith user):Request to visitCT1 to CSPLog on AA to ask for private keyAA:SendsSK1i to DUCompute:Ii=i|i=indexattx=indexSK1i,x∈SiEuiSK1i,EcspIiSend to DUDU:SendSK1i,EcspIiCSP:KeyGenMSK2,Ii ⟶ SK2iJudgeTCT2,SK2i,Ii,Cy2,Cy2′ ⟶ xIfx==⊥, return rejectelseDecryptCT1,SK1i ⟶ MSendM to DU


### 5.2. The Detailed Realization

Our scheme is based on the scheme in [31]. The basic principles of the algorithm Setup, EncryptCT, KeyGen, and DecryptCT are completely the same as those of the scheme in [31]. The difference between the scheme in [31] and ours is that we introduce the identical tree T2 and construct CT2 and another new algorithm JudgeT, which helps to decide whether to allow CT1 to be accessed. Before defining the algorithms, we will illustrate some key notations:(1)
T1W and T2W denote the system tree when a system is fixed and they have the same structure as the system tree(2)
T1i and T2i represent the trees corresponding to the ith userThe detailed algorithms are as follows:Setup. DO calls Setup to, respectively, generate MSK1,PK1 and MSK2,PK2 for system trees T1W and T2W. The detailed function of Setup algorithm is that it chooses a bilinear group G0 of prime order p with generator g. Next it will choose two random exponents α,βεZP. The public key is published as(3)PK=G0,g,h=gβ,eg,gα.The master keyMSK is (β,gα). So(4)PK1=G01,g1,h1=gβ1,eg1,g1α1,MSK1=β1,g2α1,PK2=G02,g2,h2=gβ2,eg2,g2α2,MSK2=β2,g2α2.EncryptCTPK,M,T. The encryption algorithm encrypts a message M according to the access policy. The algorithm first chooses a polynomial qx for each node x (including the leaves) in the tree. These polynomials are chosen in the following way in a top-down manner, starting from the root node R. For each node x in the tree, set the degree dx of the polynomial qx to be one less than the threshold value kx of that node; that is, dx=kx−1.Starting with the root nodeR, the algorithm chooses a random s∈Zp and sets qR0=s. Then, it chooses dR other points of the polynomial qR randomly to define it completely. For any other node x, it sets qx0=qparentxindexx and chooses dx other points randomly to completely define qx.LetY1 be the set of leaf nodes on tree T1 and let Y2 be the set of leaf nodes on tree T2. We can obtain CT1 and CT2.(5)CT1=T1,C˜=Meg1,g1α1s,C=h1s,∀y∈Y1:Cy1=g1q1y0,Cy1′=Hatty1q1y0,CT2=T2,∀y∈Y2:Cy2=g2q2y0,Cy2′=Hatty2q2y0.KeyGenMSK,S. For T1, the key generation algorithm will take as input a set of attributes Si⊆Y1=A which is possessed by a user and authorized to the user by AA and output a key that identifies with that set. The algorithm first chooses a random number r∈Zp and then random rj∈Zp for each attribute j∈S. Then it computes the key for user ui as follows:(6)SK1i=D=g1α1+r/β1,∀j∈Si⊆A:Dj=g1r×Hjrj,Dj′=g1rj.ForT2, the objective of introducing it is to judge if the user has right to access ciphertext CT1, so all the users share the secret keys SK2=sk2i|i=1,2,…,numY2, in which num denotes the number of the leaf nodes. AA computes every key sk2i corresponding to every leaf node y on tree T2; that is, AA generates a key for every attribute y∈Y2=B. Because these attributes are shared by every user, the keys are only generated once and there is no difference for every user. So, in the algorithm of generating SK2, we do not introduce random r to distinguish every user like the process of generating SK1i. The formula is as follows:(7)SK2=D=g2α2/β2,∀k∈B:Dk=Hjrk,Dk′=g2rk.The private keySK2 only is generated once and uploaded to CSPs for all the users to share.JudgeTCT2,SK2,Ii,Cy2,Cy2'. After receiving Ii from the ith DU, CSPs will obtain the indexes in set Ii. For every j∈Ii, CSP finds the corresponding key sk2j∈SK2 and then forms a key set SK2i.This algorithm judges ifSK2i satisfies the access policies of tree T2i by calling ComputeTCy2,Cy2′,SK2i,R2, in which R2 is the root node of T2i. If the result FR2 of ComputeTCy2,Cy2′,SK2i,R2 is a certain value, we think that SK2i satisfies the access policies. So, we can conclude that CT1 can be sent to the user ui. Otherwise, we reject the request of the user. The computing process of ComputeTCx,Cx′,SK,x is as follows:ComputeTCx,Cx′,SK,x. First we define a recursive function ComputeTCx,Cx′,SK,x that takes as input Cx and Cx′ involved in ciphertext CT; SK is the secret key associated with attributes set S authorized by AA to DU and x is a node of tree T. Define nx as the children number of a node x and kx is its threshold value (0<kx<nx). If the threshold gate is an OR gate, then kx=1, and if the threshold gate is an AND gate, then kx=nx. Each leaf node x of the tree represents an attribute in the attribute set S and the value of it is kx.Now we are going to compute the functionComputeTCx,Cx′,SK,x, which is proposed in the scheme in [31]. If x is the leaf node of the tree and i=attx∈S, then(8)Fx=CoputeTCx,Cx′,SK,x=eDi,CxeDi′,Cx′=egr×Hiri,gqx0egri,Hiqx0=eg,grqx0.Ifi∉S, then CoputeTCx,Cx′,SK,x=⊥.Whenx is a nonleaf node, the computing process is as follows:Let the children ofx be zi,i∈1,…,nx and let Sx be the attributes set on the threshold gate. The algorithm calls CoputeTCx,Cx′,SK,zi. Only when kx<Sx<nx can Fzi return a certain value. Otherwise, Fzi=⊥. The computing process of Fx is as follows:(9)Fx=∏zi∈SxFziΔi,Sx′0=∏zi∈Sxeg,gr⋅qzi0Δi,Sx′0,=∏zi∈Sxeg,gr⋅qxiΔi,Sx′0=eg,gr⋅qx0.JudgeTCT2,SK2i,Ii,Cy2,Cy2′ recursively calls ComputeTCy2,Cy2′,SK2i,x until x is equal to R2 and FR2 is obtained, in which R2 is the root node of tree T2i. If FR2=⊥, it means that the attributes set of the user does not satisfy the access control structure. CSP rejects to provide CT1 to the user.DecryptCT1,SK1i. If FR2 returns a certain result, it means that the attributes set of the user satisfies the access control structure. CSP will send CT1 to the user. The user will recursively call CoputeTCy1,Cy1',SK1i,x until finally obtaining FR1=eg,gr⋅qR10=eg,gr⋅s. At last, the plain text is decrypted and got by computing(10)C˜eC,D/FR1=C˜ehs,gα+r/β/eg,grs=M.


## 5.1. Architecture of Our Scheme

The CP-ABE system consists of DO (Data Owner), CSPs (Cloud Service Providers), DU (Data User), and AA (Attribute Authority). The architecture of our system is shown in Figure3 and the work flow of it is as follows:(1)
DO callsSetup to compute MSK1, PK1 and MSK2, PK2 and then publishes PK1 and PK2.(2)
DO callsEncryptCT to encrypt M as CT1.(3)
DO callsEncryptCT to compute CT2.(4)
AA generates a set of private keysSK1i based on tree T1 according to his/her attributes Si for each user, in which i denotes the ith user, and a set of secret keys SK2=ski|i=1,2... according to the identical tree T2 shared by all the users.(5)
AA transmitsSK2 to DO.(6)
DO uploads {CT1, CT2, SK2} to CSP.(7)
Theith DU requests to visit CT1 to CSPs.(8)
DU logs on AA and asks for private keys.(9)
AA sendsSK1i to DU.(10)
AA encrypts the indexes setIi which is corresponding to the attributes set of SK1i with the public key of CSPs and sends it to DU:(2)EuiSK1i,EcspIi,Ii=i|i=indexattx=indexSK1i,x∈Si.Now we take Figure2 as an example to illustrate the relationship between Ii and Si. Suppose that the attributes set Si is A1,A3,A4; then the indexes set Ii is 1,3,4.(11)
DU sendsSK1i,EcspIi to CSPs.(12)
CSP reconstructsSK2i from SK2 according to Ii ; for example, if Ii=1,3,4, SK2i=sk1,sk3,sk4.(13)
CSP callsJudgeTCT2 to decide if the user has the right to access CT1. If the returned result is equal to ⊥, CSP rejects the DU’s request.(14)
If the returned result is not equal to⊥, CSP sends CT1 to DU.(15)
DU callsDecryptCT to decrypt CT1.Figure 3
The architecture of our scheme.The algorithm process is given in Algorithm 1.Algorithm 1: An improved CP-ABE algorithm based identical tree.
DO:Setup() ⟶ MSK1, PK1 and MSK 2, PK2EncryptCT(PK1, M, T1) ⟶ CT1EncryptCT(PK2, T2) ⟶ CT2AA:KeyGenMSK1,Si ⟶ SK1iKeyGenMSK2,T2 ⟶ SK2SendsSK2 to DODO:Uploads {CT1,CT2,SK2} to CSPDU(the ith user):Request to visitCT1 to CSPLog on AA to ask for private keyAA:SendsSK1i to DUCompute:Ii=i|i=indexattx=indexSK1i,x∈SiEuiSK1i,EcspIiSend to DUDU:SendSK1i,EcspIiCSP:KeyGenMSK2,Ii ⟶ SK2iJudgeTCT2,SK2i,Ii,Cy2,Cy2′ ⟶ xIfx==⊥, return rejectelseDecryptCT1,SK1i ⟶ MSendM to DU


## 5.2. The Detailed Realization

Our scheme is based on the scheme in [31]. The basic principles of the algorithm Setup, EncryptCT, KeyGen, and DecryptCT are completely the same as those of the scheme in [31]. The difference between the scheme in [31] and ours is that we introduce the identical tree T2 and construct CT2 and another new algorithm JudgeT, which helps to decide whether to allow CT1 to be accessed. Before defining the algorithms, we will illustrate some key notations:(1)
T1W and T2W denote the system tree when a system is fixed and they have the same structure as the system tree(2)
T1i and T2i represent the trees corresponding to the ith userThe detailed algorithms are as follows:Setup. DO calls Setup to, respectively, generate MSK1,PK1 and MSK2,PK2 for system trees T1W and T2W. The detailed function of Setup algorithm is that it chooses a bilinear group G0 of prime order p with generator g. Next it will choose two random exponents α,βεZP. The public key is published as(3)PK=G0,g,h=gβ,eg,gα.The master keyMSK is (β,gα). So(4)PK1=G01,g1,h1=gβ1,eg1,g1α1,MSK1=β1,g2α1,PK2=G02,g2,h2=gβ2,eg2,g2α2,MSK2=β2,g2α2.EncryptCTPK,M,T. The encryption algorithm encrypts a message M according to the access policy. The algorithm first chooses a polynomial qx for each node x (including the leaves) in the tree. These polynomials are chosen in the following way in a top-down manner, starting from the root node R. For each node x in the tree, set the degree dx of the polynomial qx to be one less than the threshold value kx of that node; that is, dx=kx−1.Starting with the root nodeR, the algorithm chooses a random s∈Zp and sets qR0=s. Then, it chooses dR other points of the polynomial qR randomly to define it completely. For any other node x, it sets qx0=qparentxindexx and chooses dx other points randomly to completely define qx.LetY1 be the set of leaf nodes on tree T1 and let Y2 be the set of leaf nodes on tree T2. We can obtain CT1 and CT2.(5)CT1=T1,C˜=Meg1,g1α1s,C=h1s,∀y∈Y1:Cy1=g1q1y0,Cy1′=Hatty1q1y0,CT2=T2,∀y∈Y2:Cy2=g2q2y0,Cy2′=Hatty2q2y0.KeyGenMSK,S. For T1, the key generation algorithm will take as input a set of attributes Si⊆Y1=A which is possessed by a user and authorized to the user by AA and output a key that identifies with that set. The algorithm first chooses a random number r∈Zp and then random rj∈Zp for each attribute j∈S. Then it computes the key for user ui as follows:(6)SK1i=D=g1α1+r/β1,∀j∈Si⊆A:Dj=g1r×Hjrj,Dj′=g1rj.ForT2, the objective of introducing it is to judge if the user has right to access ciphertext CT1, so all the users share the secret keys SK2=sk2i|i=1,2,…,numY2, in which num denotes the number of the leaf nodes. AA computes every key sk2i corresponding to every leaf node y on tree T2; that is, AA generates a key for every attribute y∈Y2=B. Because these attributes are shared by every user, the keys are only generated once and there is no difference for every user. So, in the algorithm of generating SK2, we do not introduce random r to distinguish every user like the process of generating SK1i. The formula is as follows:(7)SK2=D=g2α2/β2,∀k∈B:Dk=Hjrk,Dk′=g2rk.The private keySK2 only is generated once and uploaded to CSPs for all the users to share.JudgeTCT2,SK2,Ii,Cy2,Cy2'. After receiving Ii from the ith DU, CSPs will obtain the indexes in set Ii. For every j∈Ii, CSP finds the corresponding key sk2j∈SK2 and then forms a key set SK2i.This algorithm judges ifSK2i satisfies the access policies of tree T2i by calling ComputeTCy2,Cy2′,SK2i,R2, in which R2 is the root node of T2i. If the result FR2 of ComputeTCy2,Cy2′,SK2i,R2 is a certain value, we think that SK2i satisfies the access policies. So, we can conclude that CT1 can be sent to the user ui. Otherwise, we reject the request of the user. The computing process of ComputeTCx,Cx′,SK,x is as follows:ComputeTCx,Cx′,SK,x. First we define a recursive function ComputeTCx,Cx′,SK,x that takes as input Cx and Cx′ involved in ciphertext CT; SK is the secret key associated with attributes set S authorized by AA to DU and x is a node of tree T. Define nx as the children number of a node x and kx is its threshold value (0<kx<nx). If the threshold gate is an OR gate, then kx=1, and if the threshold gate is an AND gate, then kx=nx. Each leaf node x of the tree represents an attribute in the attribute set S and the value of it is kx.Now we are going to compute the functionComputeTCx,Cx′,SK,x, which is proposed in the scheme in [31]. If x is the leaf node of the tree and i=attx∈S, then(8)Fx=CoputeTCx,Cx′,SK,x=eDi,CxeDi′,Cx′=egr×Hiri,gqx0egri,Hiqx0=eg,grqx0.Ifi∉S, then CoputeTCx,Cx′,SK,x=⊥.Whenx is a nonleaf node, the computing process is as follows:Let the children ofx be zi,i∈1,…,nx and let Sx be the attributes set on the threshold gate. The algorithm calls CoputeTCx,Cx′,SK,zi. Only when kx<Sx<nx can Fzi return a certain value. Otherwise, Fzi=⊥. The computing process of Fx is as follows:(9)Fx=∏zi∈SxFziΔi,Sx′0=∏zi∈Sxeg,gr⋅qzi0Δi,Sx′0,=∏zi∈Sxeg,gr⋅qxiΔi,Sx′0=eg,gr⋅qx0.JudgeTCT2,SK2i,Ii,Cy2,Cy2′ recursively calls ComputeTCy2,Cy2′,SK2i,x until x is equal to R2 and FR2 is obtained, in which R2 is the root node of tree T2i. If FR2=⊥, it means that the attributes set of the user does not satisfy the access control structure. CSP rejects to provide CT1 to the user.DecryptCT1,SK1i. If FR2 returns a certain result, it means that the attributes set of the user satisfies the access control structure. CSP will send CT1 to the user. The user will recursively call CoputeTCy1,Cy1',SK1i,x until finally obtaining FR1=eg,gr⋅qR10=eg,gr⋅s. At last, the plain text is decrypted and got by computing(10)C˜eC,D/FR1=C˜ehs,gα+r/β/eg,grs=M.


## 6. Security Analysis

### 6.1. Security Proof

Theorem 1.
Suppose that the scheme of Waters [31] is a CPA-secure CP-ABE. Then our scheme is also CPA-secure.Proof.
Suppose that there exist a polynomial-time adversaryA that can attack our scheme with advantage ϵ in the CPA-secure model, a challenger C that is a simulator to the scheme of Waters, and a simulator of our scheme ℬ that can attack Waters’ scheme with advantage ϵ in the CPA-secure model:Setup.C generates MSK1 and PK1=G01,g1,h1=gβ1,eg1,g1α1 according to Waters’ scheme. Then C sends PK1 to ℬ. ℬ generates PK2=G02,g2,h2=gβ2,eg2,g2α2 and MSK2 according to our scheme and publishes PK1 and PK2.Queryphase1. A constructs many attributes set S1,S2,S3… to issue corresponding requests of secret keys to ℬ. At the same time, A sends EI1,EI2,EI3… to ℬ. ℬ sends Si to C. C generates SK1,SK2,SK3… to ℬ. Then B sends them to A. ℬ generates a Table T and adds j++,Si,SK1i,Ii to T.EncryptM∗. A constructs M∗,ρ∗,EIK∗ to ℬ and ℬ sends it to C for encryption. C randomly selects s∈ZP and runs encryption algorithm EncryptCT and returns CT1∗ to ℬ. B runs encryption algorithm and returnsCT2∗. Thenℬsearches table T forIk==Ii.(a)
If the query result is not null,ℬcallsJudgeT. If the return value ofJudgeTis certain,ℬsendsCT1∗toA. If the return value is⊥,⊥is returned toA.(b)
If the query result is null,ℬreturns⊥toA.Challenge.A sends two equal-length messages M0,ρx∗,EIk and M1,ρx∗,EIk to ℬ and ℬ sends them to C. In these messages, Si constructed in query phase does not satisfy ρx∗, so IK∗ is not equal to IK. C randomly selects β∈0,1 and encrypts Mβ as CT∗ by calling the step of Encrypt M∗.Queryphase2. Run Query phase 1, but Si constructed in query phase 1 does not satisfy ρx∗.IfA receives ⊥, A generates a random number β′∈0,1. Then, in this situation, ϵ=Prβ=β′−1/2=1/2−1/2=0. If what A receives is not ⊥, according to the scheme of Waters, ϵ can be negligible.Guess.A outputs β′∈0,1 to C.
Because the algorithms ofSetup,EncryptCT,KeyGen,Decrypt are all identical to Waters’ algorithms and Waters’ scheme satisfies CPA security, our scheme also satisfies CPA security.
The proof of Theorem1 is complete.


### 6.2. Resisting Collusion Attacks

Our scheme employs the method of the scheme in [31] to encrypt the plain text and generate the secret key for every user. The technique generates a random number r for every user when distributing secret key, which means that only the secret keys with same r can decrypt CT, while every user has different r. So, even if multiple users collude and every user provides a secret key and at last they collect every secret key corresponding to every attribute, the collusion is not successful for parameter r corresponding to every user is different, which makes it is impossible to conspire among many users. The security of the scheme has been proved in literature [31].


### 6.3. Invisible to CSPs

Although treesT2 and T1 have the same structure, the private keys of T2 cannot decrypt CT1 for the master key and public parameters are not the same as trees T1 and T2. So, although CSP can compute the value of FR2, it cannot compute the value of FR1. Therefore, CSP cannot decrypt ciphertext CT1. So, the message is safe to be preserved on CSP.


### 6.4. Backward Safe

Our scheme is backward safe. When a new user joins the system, if he/she did not distribute the private key corresponding to the access control tree of the old ciphertext, he/she cannot decrypt the oldCT. So, our scheme is backward safe.


### 6.5. Forward Safe

Suppose that after some attributes of one user are revoked by AA, he/she does not satisfy the access control policy; then he/she cannot access the ciphertext. If he/she can decrypt the ciphertext before the attributes are revoked and he/she preserved the secret key, for he/she is rejected to visit the ciphertext if he/she does not satisfy the access control policy at the current, he/she cannot obtain the ciphertextCT. So, even if the secret key before the attributes are revoked is preserved by the user, he/she cannot get the CT and decrypt it. So, our scheme is forward safe.


### 6.6. Protection of the Attribute Privacy and Access Control Policy

Although treeT2 has the same structure as tree T1, we cannot discover the attribute names and relationship from CT1. So, CSPs cannot discover the attribute names and relationship from CT2 although CSPs have abilities to decrypt tree T2. Therefore, our scheme will not leak the privacy of the attributes and relationship.


### 6.7. Revocation Analysis

Our scheme constructs treeT2 which is identical with the real access control tree T1 for every user. The two trees have the same structure. The secret keys corresponding to the leaf nodes of tree T2 are shared by all the users and preserved on CSP. CSP judges if the user has the access to tree T1 by the secret indexes transmitted from AA. CSP finds the real secret keys according to the secret indexes to compute the value of FR2 of tree T2. If the returned result is null, it proves that the user has no right to access the ciphertext and CSP rejects to send CT1 to the user. So, although the user saved the secret keys when he had had right to visit CT1, he/she cannot visit the message for this time he/she has been revoked some attributes which results in not obtaining CT1. So, our revocation scheme is safe.CSP judges if the user has the right to visit theCT according to the secret indexes which represent the attributes that the user possesses now. If the indexes set I is null, it means that the user has no attribute authorized by AA, that is, the user has been revoked. So, our scheme can realize the user’s attribute revocation and user revocation.


## 6.1. Security Proof

Theorem 1.
Suppose that the scheme of Waters [31] is a CPA-secure CP-ABE. Then our scheme is also CPA-secure.Proof.
Suppose that there exist a polynomial-time adversaryA that can attack our scheme with advantage ϵ in the CPA-secure model, a challenger C that is a simulator to the scheme of Waters, and a simulator of our scheme ℬ that can attack Waters’ scheme with advantage ϵ in the CPA-secure model:Setup.C generates MSK1 and PK1=G01,g1,h1=gβ1,eg1,g1α1 according to Waters’ scheme. Then C sends PK1 to ℬ. ℬ generates PK2=G02,g2,h2=gβ2,eg2,g2α2 and MSK2 according to our scheme and publishes PK1 and PK2.Queryphase1. A constructs many attributes set S1,S2,S3… to issue corresponding requests of secret keys to ℬ. At the same time, A sends EI1,EI2,EI3… to ℬ. ℬ sends Si to C. C generates SK1,SK2,SK3… to ℬ. Then B sends them to A. ℬ generates a Table T and adds j++,Si,SK1i,Ii to T.EncryptM∗. A constructs M∗,ρ∗,EIK∗ to ℬ and ℬ sends it to C for encryption. C randomly selects s∈ZP and runs encryption algorithm EncryptCT and returns CT1∗ to ℬ. B runs encryption algorithm and returnsCT2∗. Thenℬsearches table T forIk==Ii.(a)
If the query result is not null,ℬcallsJudgeT. If the return value ofJudgeTis certain,ℬsendsCT1∗toA. If the return value is⊥,⊥is returned toA.(b)
If the query result is null,ℬreturns⊥toA.Challenge.A sends two equal-length messages M0,ρx∗,EIk and M1,ρx∗,EIk to ℬ and ℬ sends them to C. In these messages, Si constructed in query phase does not satisfy ρx∗, so IK∗ is not equal to IK. C randomly selects β∈0,1 and encrypts Mβ as CT∗ by calling the step of Encrypt M∗.Queryphase2. Run Query phase 1, but Si constructed in query phase 1 does not satisfy ρx∗.IfA receives ⊥, A generates a random number β′∈0,1. Then, in this situation, ϵ=Prβ=β′−1/2=1/2−1/2=0. If what A receives is not ⊥, according to the scheme of Waters, ϵ can be negligible.Guess.A outputs β′∈0,1 to C.
Because the algorithms ofSetup,EncryptCT,KeyGen,Decrypt are all identical to Waters’ algorithms and Waters’ scheme satisfies CPA security, our scheme also satisfies CPA security.
The proof of Theorem1 is complete.


## 6.2. Resisting Collusion Attacks

Our scheme employs the method of the scheme in [31] to encrypt the plain text and generate the secret key for every user. The technique generates a random number r for every user when distributing secret key, which means that only the secret keys with same r can decrypt CT, while every user has different r. So, even if multiple users collude and every user provides a secret key and at last they collect every secret key corresponding to every attribute, the collusion is not successful for parameter r corresponding to every user is different, which makes it is impossible to conspire among many users. The security of the scheme has been proved in literature [31].


## 6.3. Invisible to CSPs

Although treesT2 and T1 have the same structure, the private keys of T2 cannot decrypt CT1 for the master key and public parameters are not the same as trees T1 and T2. So, although CSP can compute the value of FR2, it cannot compute the value of FR1. Therefore, CSP cannot decrypt ciphertext CT1. So, the message is safe to be preserved on CSP.


## 6.4. Backward Safe

Our scheme is backward safe. When a new user joins the system, if he/she did not distribute the private key corresponding to the access control tree of the old ciphertext, he/she cannot decrypt the oldCT. So, our scheme is backward safe.


## 6.5. Forward Safe

Suppose that after some attributes of one user are revoked by AA, he/she does not satisfy the access control policy; then he/she cannot access the ciphertext. If he/she can decrypt the ciphertext before the attributes are revoked and he/she preserved the secret key, for he/she is rejected to visit the ciphertext if he/she does not satisfy the access control policy at the current, he/she cannot obtain the ciphertextCT. So, even if the secret key before the attributes are revoked is preserved by the user, he/she cannot get the CT and decrypt it. So, our scheme is forward safe.


## 6.6. Protection of the Attribute Privacy and Access Control Policy

Although treeT2 has the same structure as tree T1, we cannot discover the attribute names and relationship from CT1. So, CSPs cannot discover the attribute names and relationship from CT2 although CSPs have abilities to decrypt tree T2. Therefore, our scheme will not leak the privacy of the attributes and relationship.


## 6.7. Revocation Analysis

Our scheme constructs treeT2 which is identical with the real access control tree T1 for every user. The two trees have the same structure. The secret keys corresponding to the leaf nodes of tree T2 are shared by all the users and preserved on CSP. CSP judges if the user has the access to tree T1 by the secret indexes transmitted from AA. CSP finds the real secret keys according to the secret indexes to compute the value of FR2 of tree T2. If the returned result is null, it proves that the user has no right to access the ciphertext and CSP rejects to send CT1 to the user. So, although the user saved the secret keys when he had had right to visit CT1, he/she cannot visit the message for this time he/she has been revoked some attributes which results in not obtaining CT1. So, our revocation scheme is safe.CSP judges if the user has the right to visit theCT according to the secret indexes which represent the attributes that the user possesses now. If the indexes set I is null, it means that the user has no attribute authorized by AA, that is, the user has been revoked. So, our scheme can realize the user’s attribute revocation and user revocation.


## 7. Analysis of Performance

### 7.1. Comparisons with the Previous Schemes in Function

In this section, we will compare our scheme with the previous schemes in revocation function from three aspects: (1) if the secret keys are updated; (2) if the ciphertext is updated; (3) if the secret key or ciphertext is related to the number of revoked users or attributes. They are shown in Table2.Table 2
Comparisons of functionalities with the previous works.
(1)(2)(3)Scheme in [31]YesYesYesScheme in [13]NoYesYesScheme in [21]NoYesYesOur schemeNoNoNoFrom Table2, we can see that only our scheme updates neither the secret keys nor the ciphertext. So, our scheme has no overhead on the secret keys and ciphertext update. While in other schemes not only are the secret keys or ciphertext updated, but also the overhead of the update is related to the number of the users or the attributes. Once the number of the users or attributes becomes very large, the computation time or storage overload will increase rapidly.


### 7.2. Comparisons with the Previous Schemes in Computation Complexity

Table3 shows the meanings of the notations which appear in Table 4. Table 4 lists the comparison on computation complexity of four schemes. From the column of TOTAL, we can see that our scheme consumes the shortest time compared to three other schemes in computation complexity.Table 3
The meanings of notations.
NotationMeaningpThe pairing of operationeThe group exponentiationYThe number of attributes in the systemSThe average number of attributes possessed by one userKThe number of revoked usersS˜The average number of revoked attributesIThe number of attributes for decryptionTable 4
Comparison of computation complexity.
SetupKeyGenEncryptDecryptRevocationTotalScheme in [31]1∗e+1∗p2∗S+1∗e∗U2∗Y+1∗e+1∗pI∗p2∗S˜+2∗e∗KOI∗p+OSU+Y+S˜K∗eScheme in [13]p+2∗e3∗S+2∗e∗U2∗Y+2∗e+1∗p2∗I+1∗p+I+logY∗eY+3∗e+S˜∗e∗KOY∗p+OSU+I+YK+S˜K+logY∗eScheme in [21]p+Y+3∗eY+4∗e∗U3∗Y+2∗e+1∗p2∗I+2∗p+2∗I∗e2∗S˜∗e∗KOI∗p+OYU+S˜K+Y∗eOur scheme2∗e+1∗p+p12∗S+1∗e∗U+2∗Y+1∗e2∗2∗Y+1∗e+1∗p+1∗p1I∗p+I∗p10OI∗p+OSU+Y∗e


## 7.1. Comparisons with the Previous Schemes in Function

In this section, we will compare our scheme with the previous schemes in revocation function from three aspects: (1) if the secret keys are updated; (2) if the ciphertext is updated; (3) if the secret key or ciphertext is related to the number of revoked users or attributes. They are shown in Table2.Table 2
Comparisons of functionalities with the previous works.
(1)(2)(3)Scheme in [31]YesYesYesScheme in [13]NoYesYesScheme in [21]NoYesYesOur schemeNoNoNoFrom Table2, we can see that only our scheme updates neither the secret keys nor the ciphertext. So, our scheme has no overhead on the secret keys and ciphertext update. While in other schemes not only are the secret keys or ciphertext updated, but also the overhead of the update is related to the number of the users or the attributes. Once the number of the users or attributes becomes very large, the computation time or storage overload will increase rapidly.


## 7.2. Comparisons with the Previous Schemes in Computation Complexity

Table3 shows the meanings of the notations which appear in Table 4. Table 4 lists the comparison on computation complexity of four schemes. From the column of TOTAL, we can see that our scheme consumes the shortest time compared to three other schemes in computation complexity.Table 3
The meanings of notations.
NotationMeaningpThe pairing of operationeThe group exponentiationYThe number of attributes in the systemSThe average number of attributes possessed by one userKThe number of revoked usersS˜The average number of revoked attributesIThe number of attributes for decryptionTable 4
Comparison of computation complexity.
SetupKeyGenEncryptDecryptRevocationTotalScheme in [31]1∗e+1∗p2∗S+1∗e∗U2∗Y+1∗e+1∗pI∗p2∗S˜+2∗e∗KOI∗p+OSU+Y+S˜K∗eScheme in [13]p+2∗e3∗S+2∗e∗U2∗Y+2∗e+1∗p2∗I+1∗p+I+logY∗eY+3∗e+S˜∗e∗KOY∗p+OSU+I+YK+S˜K+logY∗eScheme in [21]p+Y+3∗eY+4∗e∗U3∗Y+2∗e+1∗p2∗I+2∗p+2∗I∗e2∗S˜∗e∗KOI∗p+OYU+S˜K+Y∗eOur scheme2∗e+1∗p+p12∗S+1∗e∗U+2∗Y+1∗e2∗2∗Y+1∗e+1∗p+1∗p1I∗p+I∗p10OI∗p+OSU+Y∗e


## 8. Optimization

In this scheme, we construct an identical treeT2 to judge if the user who possesses the private keys can decrypt the cipher text CT1 by decrypting CT2. Only can CSPs compute a certain value, it can prove that the user has the ability to decrypt the cipher text. So, it is only related to the ability of decrypting CT2 and has nothing to do with the time complexity of computing FR. In addition, every time before the user visits CT1, CSPs will first call the function JudgeT to compute and decrypt CT2. So, the time consumed on decrypting CT2 influences the system efficiency. Therefore, we can adjust the initialization parameters corresponding to tree T2 for decreasing the time consumed in decrypting CT2. In our system, the initialization parameter is prime order p in ZP. From the experiments in Section 8, we can discover that the performance of the whole system is improved a lot by adjusting parameter p with the same structure as the real access control tree T1. The function of tree T2 is to help judge whether the user has the authorization to access ciphertext CT1.


## 9. Experiments

The experimental environments are four laptop computers: the first with Windows 10 system with Intel® Core™ i5 CPU @ 1.60 GHz and 8.00 GB RAM, the second with Windows 10 system with Intel® Core™ i5-6300HQ CPU @ 2.30 GHz and 12.00 GB RAM, the third with Windows 10 system with Intel i7-7700 CPU@2.8 GHz and 8 GB memory, and the fourth with Windows 10 with Intel CPU @ with 3.2 GHz and 2 GB memory. They-axis in Figure 4 shows the time cost in the four phases, respectively, in four computers and the x-axis represents the different bit order of p in the curve group. From the four figures, we can see the following: (1) the cost time becomes bigger with the increase of the bit order; (2) the cost times in the four phases at the same bit order are different on different CPU and the cost time on CPU 3.2 GHz at the same bit orbit is the minimum and that on CPU i5 1.6 GHz is the maximum, which means that the computing ability of CPU influences the cost time; (3) the cost time in the maximum bit order (159) is about 10 times that in the minimum bit order (7); (4) the decryption time which is the phase’s most consuming time on CPU 3.2 GHz in 7-bit order is about 25 times that on CPU i5 1.6 GHz in 159-bit order. According to the optimization theory in Section 7, the introduction of tree T2 is just to judge whether the user has the right to decrypt CT1 and it is not constrained by confidentiality. We want it to compute fast. From the above experiments, we can see that the small bit order and the CPU with the highest performance can raise the computing speed. Therefore, we can choose the 7-bit prime order and 3.2 GHz CPU as the server of CSP to decrypt tree T2. For ciphertext CT1 must satisfy confidentiality and does not tend to be decrypted, in this situation, the big bit order is required. In addition, the client device is generally in the low performance. So, we choose 159-bit order and CPU i5 1.6 GHz to simulate the client. At this time, we can discover from Figure 4(d) that the cost time in CSP is just 406 ms and about 25 times that in the client, which means that the time cost consumed in decrypting CT2 can be ignored. So, our scheme realizes the attribute revocation and does not add too much computation overload on the system.Figure 4
(a) Setup. (b) KeyGen. (c) Encrypt. (d) Decrypt.
(a)(b)(c)(d)


## 10. Conclusion

In this paper, we innovatively propose a scheme of user’s attribute revocation that is to construct an identical treeT2, preserved on CSPs, according to the access control tree T1 and judge whether DU has the right to access ciphertext CT1 by decrypting CT2. Finally, we analyze the security and time efficiency of our scheme and prove that our scheme is viable.



---

*Source: 5175754-2022-02-15.xml*