# Multiauthority Attribute-Based Encryption with Traceable and Dynamic Policy Updating

Authors: Jie Ling; Junwei Chen; Jiahui Chen; Wensheng Gan
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Ciphertext policy attribute-based encryption (CP-ABE) is an encryption mechanism that can provide fine-grained access control and adequate cloud storage security for Internet of Things (IoTs). In this field, the original CP-ABE scheme usually has only a single trusted authority, which will become a bottleneck in IoTs. In addition, different users may illegally share their private keys to obtain improper benefits. Besides, the data owners also require the flexibility to change their access policy. In this paper, we construct a multiauthority CP-ABE scheme on prime order groups over a large attribute universe. Our scheme can support white-box traceability along with policy updates to solve the abovementioned three problems and, thus, can fix the potential requirements of IoTs. More precisely, the proposed scheme supports multiple authority, white box traceability, large attribute domains, access policy updates, and high expressiveness. We prove that our designed scheme is static secure and traceable secure based on the state-of-the-art security models. Moreover, by theoretical comparison, our scheme has better performance than other schemes. Finally, extensive experimental comparisons show that our proposed algorithm can be better than the baseline algorithms.


---

## Body

## 1. Introduction

With the help of cloud computing technology, Internet of Things (IoTs) [1] can bridge physical devices and virtual objects, which has become a promising networking scenario in the cyber world. In IoTs, more and more companies and individuals store data in the cloud, requiring the cloud servers to provide data access services. However, cloud servers are generally considered to be untrustworthy for the reason that the data of IoTs often contain sensitive information. In order to protect the privacy of these data, one of the traditional technologies is to encrypt the data, and data owners need to be online at all times to distribute their secret keys. Although these technologies achieve access control, the management of these keys will become a bottleneck when more and more users joined the system. In addition, for each type of data, it is necessary to maintain one or more copies of the ciphertext for different users with different keys, which will cause a waste of storage overhead in an IoTs system [2]. To this end, Sahai et al. [3] firstly proposed attribute-based encryption. The concept of attribute-based encryption (ABE) is a one-to-many encryption mechanism that can provide fine-grained access control and data security. Goyal et al. [4] further proposed the key policy ABE (KP-ABE) and ciphertext policy ABE (CP-ABE). Then, Bethencourt et al. [5] studied the CP-ABE scheme with a complete description, showing that CP-ABE allows data owners to define access strategies under the user’s attributes. Once the user encrypts specific data, other users can decrypt them if and only if their attributes meet the access policy. Thanks to these characteristics, the CP-ABE scheme is considered a more suitable encryption mechanism for cloud storage access control than KP-ABE.However, the original CP-ABE scheme only has a single, trusted authority dealing with the user’s key distribution and attribute management, which will become a bottleneck in the cloud, especially in an IoTs system. Liu et al. [6] proposed a scheme under a different hierarchy of attributes with the name of ciphertext-policy hierarchical attribute-based encryption. Deng et al. [7] elaborate on ABE and propose a new versatile cryptosystem referred to as ciphertext-policy hierarchical ABE. Wang et al. [8], based on the access structure layered model, proposed a novel access control scheme about file hierarchy by using ABE to solve the problem. Liu et al. [9] propose a novel T-CP-ABE system that gives high policies expressiveness in any monotone access structures and add traceability. Liang et al. [10] propose a CP-ABPRE to deal with the security problem by using the dual system encryption technology with the selective proof technique. But, the schemes mentioned above are all single attribute authorization (AA) ABE schemes. It is completely borne in the cloud environment, which not only brings a serious burden to the authorization center but also requires the authorization center to be completely trusted. Single-attribute authority cannot meet the development needs of practical applications because different attributes in different fields in many application scenarios are caused by different environments. For example, there is a situation that the data owner wants to share data with the researchers in the research institutes and the managers in the government departments. In this case, the attributes of researchers are determined by the research institutes. At the same time, the “government attributes” are managed by the government department. The abovementioned ABE schemes are not suitable for this situation where the attributes need to be managed by multiple agencies.On the other side, in some CP-ABE schemes, it is easy to discover their attributes in the private key. There may be another situation that some malicious users illegally share their private keys to obtain economic benefits. Thus, the features of the CP-ABE scheme that can track leaked secret keys are particularly important. Therefore, we also need a traceability mechanism to track these malicious users. For example, attackers can access critical vulnerabilities in a wide variety of IoTs applications and devices to perform their malicious activities. This requires the design of effective security mechanisms in an IoTs-related application.Except for the traceability, the policy update of the CP-ABE system also needs to be considered for supplying more functions. For instance, when addressing security, trust, and privacy in IoTs, the data owner may need to alter the access policy stored on the cloud. In that case, the traditional solution is to let the data owner find the cloud storage server’s relevant ciphertext and decrypt it, then encrypt the ciphertext using a new access strategy, and upload the newly encrypted ciphertext back to the cloud server. It, thus, brings much computational burden to the system. Therefore, the policy update is another important characteristic of the actual system.To sum up, there are three major challenges in CP-ABE that we need to solve as follows:(1)
How to solve the bottleneck of single authority authorization in cloud storage applications, especially in an IoTs system?(2)
How to prevent some malicious users from illegally sharing their private keys?(3)
How to propose an algorithm that makes the data owner’s access control more flexible in IoTs-enabled applications?


### 1.1. Our Contribution

This paper addresses the abovementioned challenges by proposing a scheme named T-DPU-MCP-ABE (Traceable and Dynamic Policy Updating Multiauthority Attribute-based Encryption). More precisely, we propose a T-DPU-MCP-ABE based on the prime order bilinear group, and we prove its static security and resistance to traceable attacks under two related security models. Our security assumption utilizes theq-type hypothesis [11] and is based on the LRSW hypothesis [12]. As far as we know, we are the first one to support the properties of large attribute domain, policy update, white box traceability, multiauthorization, and high expressiveness and still have good performance. Especially, the features are described in detail as follows:(1)
Large attribute domain: the size of public parameters is affected by the number of authorized institutions and will not increase linearly with the number of attributes. There is no need to determine the system attribute domain when the system is established.(2)
Policy update: data owners may often need to modify the ciphertext access policy according to various requirements. Policy updates provide flexibility and allow data owners to adjust their encrypted data access policies to achieve fine-grained control.(3)
White box Traceability: it can track malicious users who illegally share private keys. Through white box tracking that does not need to maintain a user list, the efficiency of the solution is improved, and no additional storage overhead is consumed.(4)
Multiple authorized authorities: multiple authorized authorities undertake the key distribution work and, thus, reduce the workload and solve the problem of incomplete trustworthiness of the single authority.(5)
High expressiveness: supports flexible access control and supports any monotonous access structure access strategy.


### 1.2. Organization

The rest of this paper is arranged as follows. In Section3, we introduce the necessary background knowledge. In Section 4, we give the formal definition and security model of auditable ABE. In Section 5, we give the main constructions and security analysis. In Section 6, we provide a performance and experiment evaluation. Finally, Section 7 presents a brief conclusion and future work.


## 1.1. Our Contribution

This paper addresses the abovementioned challenges by proposing a scheme named T-DPU-MCP-ABE (Traceable and Dynamic Policy Updating Multiauthority Attribute-based Encryption). More precisely, we propose a T-DPU-MCP-ABE based on the prime order bilinear group, and we prove its static security and resistance to traceable attacks under two related security models. Our security assumption utilizes theq-type hypothesis [11] and is based on the LRSW hypothesis [12]. As far as we know, we are the first one to support the properties of large attribute domain, policy update, white box traceability, multiauthorization, and high expressiveness and still have good performance. Especially, the features are described in detail as follows:(1)
Large attribute domain: the size of public parameters is affected by the number of authorized institutions and will not increase linearly with the number of attributes. There is no need to determine the system attribute domain when the system is established.(2)
Policy update: data owners may often need to modify the ciphertext access policy according to various requirements. Policy updates provide flexibility and allow data owners to adjust their encrypted data access policies to achieve fine-grained control.(3)
White box Traceability: it can track malicious users who illegally share private keys. Through white box tracking that does not need to maintain a user list, the efficiency of the solution is improved, and no additional storage overhead is consumed.(4)
Multiple authorized authorities: multiple authorized authorities undertake the key distribution work and, thus, reduce the workload and solve the problem of incomplete trustworthiness of the single authority.(5)
High expressiveness: supports flexible access control and supports any monotonous access structure access strategy.


## 1.2. Organization

The rest of this paper is arranged as follows. In Section3, we introduce the necessary background knowledge. In Section 4, we give the formal definition and security model of auditable ABE. In Section 5, we give the main constructions and security analysis. In Section 6, we provide a performance and experiment evaluation. Finally, Section 7 presents a brief conclusion and future work.


## 2. Related Work

Melissa [13] proposed a ciphertext strategy-based multiagency authorization attribute-based encryption (MCP-ABE) scheme. The scheme has a central authority with the ability to decrypt each ciphertext, which reduces the security of decryption key storage. Lewko et al. [14] proposed a multiagency authorization scheme that supports arbitrary access structures based on the groups in composite order, resulting in a low efficiency. In order to improve the efficiency of the scheme, Yannis et al. [15] proposed a CP-ABE scheme based on prime order groups and made it support large attribute domains. Then, Yannis et al. [11] proposed a multiagency authorization CP-ABE scheme based on prime order groups and also support large attribute domains. In this scheme, the authors used the linear secret-sharing scheme (LSSS) to improve expression ability. However, none of the abovementioned studies support traceability.The traceability in ABE is divided into white-box traceable and black-box traceable [16]. In this field, Ning et al. [17] proposed a white-box traceable method that enables large attribute domains and high expressive capability. Their white-box traceable scheme is based on a single authorization center. To improve this, Li et al. [18] proposed a CP-ABE scheme with multiauthorization centers. However, this scheme only supports the access strategy of the AND gate, which limits in low expressive capability. Then, Zhou et al. [19] proposed a multiagency authorization CP-ABE scheme with white-box traceable that supports high expressive capability on medical cloud systems. However, their scheme does not support large attribute domains, and each authorization center has to maintain an identification table, which increases the storage overhead for tracking.In the study of policy update, Ying et al. [20] proposed the first CP-ABE scheme that supports the modification of any form of fine-grained access control policy, and it is proved to be adaptive and secure under the standard model, but the system’s communication overhead and storage overhead are high. After that, Liu et al. [21] proposed an ABE scheme that supports outsourcing decryption, attribute revocation, and policy update. This scheme is more flexible and practical in practice, but its privacy-protection capabilities are slightly lacking. Recently, Jing et al. [22] proposed a CP-ABE scheme that supports access policy update and rapid expansion of attributes but did not consider the application scenarios of multiauthorization agencies.


## 3. Background

### 3.1. Access Structure

We defineU as a set of attributes, an access structure A is a collection of nonempty subsets of U, that is, A∈2U/ϕ, and the collection contained in A is called an authorization set. If the user has an authorized attribute set, the user can perform decryption, but not vice versa.For allB and C, B∈A, and B⊆C, if C∈A, we say that the access structure A is monotonous. We restrict to a monotone access structure in this paper.


### 3.2. Prime-Order Bilinear Groups

Letp be a big prime and G and GT be cyclic groups with prime order p; we say that e: G×G⟶GT is a computable bilinear map if it has the following properties:(1)
Bilinear, i.e.,ePa,Qb=eP,Qab for all P,Q∈G,a,b∈ℤq(2)
Nondegeneracy, i.e., there existsP,Q∈G such that eP,Q≠1, namely, the map does not send all pairs in G×G to the identity in GT(3)
Computability, i.e., there is an efficient algorithm to computeeP,Q for all P,Q∈G


### 3.3. Linear Secret-Sharing Schemes

LetU be the set of attributes, as shown in [23]; ∏ is a linear secret-sharing scheme (LSSS) on U if it has the following properties:(1)
For each attribute form of a vector overℤp, there is a secret share s∈ℤp.(2)
The matrix for∏ is called a share-generating matrix meaning a matrix M with l rows and n columns for each access structure A on S. For i=1,…,l, we define a function ρ labels row i of M with attribute ρi. We consider the column vector υ⟶=s,r2,…,rn, where s∈ℤp is the secret to be shared and r2,…,rn∈ℤp are randomly chosen. Then, Mυ⟶∈ℤpl×1 is the vector of l shares of the secret s according to ∏.For the LSSS scheme, it enjoys the linear reconstruction property. More precisely, let∏ be an LSSS for the access structure A, S∗∈A be an authorized set, and let I⊂1,2,…,l be defined as I=i∈l∧ρi∈S∗. Then, for constants ωi∈ℤpi∈I such that, for any valid shares λi=Mυ⟶ii∈I of a secret s according to ∏, we have ∑i∈Iωiλi=s.


### 3.4. Problem Assumption

Decisionalq-parallel bilinear Diffie–Hellman exponent (q-PBDHE) assumption: the decisional q-parallel bilinear Diffie–Hellman exponent (decisional q−PBDHE) problem [11] is saying that, given the tuple G,p,e,g,gs, it satisfies(1)∀i∈1,…,2q,j∈1,…,q,i≠q+1:gai,gbjai,(2)∀i∈1,…,q:gs/bi,(3)∀i∈1,…,q+1,j,j′∈1,…,q,j≠j′:gsaibj/bj′,if we can distinguish Z=eg,gaq+1s from a random value in GT.Formally speaking, ifPrAy⟶,Z=eg,gaq+1s=0−PrAy⟶,R=0≥ε, we say that an algorithm A has advantage ε in solving the abovementioned decisional q−PBDHE problem. Then, if all probabilistic polynomial time (PPT) algorithms have, at most, a negligible advantage in solving the decisional q−PBDHE problem, we say that the decisional q−PBDHE assumption holds.LRSW assumption [12]: let G be the cyclic group of order p, g be a generator of G, and two random values x,y∈ℤp satisfy X=gx and Y=gy. Let OX,Y· be the random oracle, which inputs m∈ℤp and outputs a triplet A=a,ay,ax+mxy, where a∈G. If there is no probability polynomial time algorithm that can generate m,a,b,c satisfying m∉Q, Q∈OX,Y·, m∈ℤp,m≠0,a∈G,b=ax, c=ax+mxy with probability at the least ε, then the LRSW assumption in group G is said to be true.


## 3.1. Access Structure

We defineU as a set of attributes, an access structure A is a collection of nonempty subsets of U, that is, A∈2U/ϕ, and the collection contained in A is called an authorization set. If the user has an authorized attribute set, the user can perform decryption, but not vice versa.For allB and C, B∈A, and B⊆C, if C∈A, we say that the access structure A is monotonous. We restrict to a monotone access structure in this paper.


## 3.2. Prime-Order Bilinear Groups

Letp be a big prime and G and GT be cyclic groups with prime order p; we say that e: G×G⟶GT is a computable bilinear map if it has the following properties:(1)
Bilinear, i.e.,ePa,Qb=eP,Qab for all P,Q∈G,a,b∈ℤq(2)
Nondegeneracy, i.e., there existsP,Q∈G such that eP,Q≠1, namely, the map does not send all pairs in G×G to the identity in GT(3)
Computability, i.e., there is an efficient algorithm to computeeP,Q for all P,Q∈G


## 3.3. Linear Secret-Sharing Schemes

LetU be the set of attributes, as shown in [23]; ∏ is a linear secret-sharing scheme (LSSS) on U if it has the following properties:(1)
For each attribute form of a vector overℤp, there is a secret share s∈ℤp.(2)
The matrix for∏ is called a share-generating matrix meaning a matrix M with l rows and n columns for each access structure A on S. For i=1,…,l, we define a function ρ labels row i of M with attribute ρi. We consider the column vector υ⟶=s,r2,…,rn, where s∈ℤp is the secret to be shared and r2,…,rn∈ℤp are randomly chosen. Then, Mυ⟶∈ℤpl×1 is the vector of l shares of the secret s according to ∏.For the LSSS scheme, it enjoys the linear reconstruction property. More precisely, let∏ be an LSSS for the access structure A, S∗∈A be an authorized set, and let I⊂1,2,…,l be defined as I=i∈l∧ρi∈S∗. Then, for constants ωi∈ℤpi∈I such that, for any valid shares λi=Mυ⟶ii∈I of a secret s according to ∏, we have ∑i∈Iωiλi=s.


## 3.4. Problem Assumption

Decisionalq-parallel bilinear Diffie–Hellman exponent (q-PBDHE) assumption: the decisional q-parallel bilinear Diffie–Hellman exponent (decisional q−PBDHE) problem [11] is saying that, given the tuple G,p,e,g,gs, it satisfies(1)∀i∈1,…,2q,j∈1,…,q,i≠q+1:gai,gbjai,(2)∀i∈1,…,q:gs/bi,(3)∀i∈1,…,q+1,j,j′∈1,…,q,j≠j′:gsaibj/bj′,if we can distinguish Z=eg,gaq+1s from a random value in GT.Formally speaking, ifPrAy⟶,Z=eg,gaq+1s=0−PrAy⟶,R=0≥ε, we say that an algorithm A has advantage ε in solving the abovementioned decisional q−PBDHE problem. Then, if all probabilistic polynomial time (PPT) algorithms have, at most, a negligible advantage in solving the decisional q−PBDHE problem, we say that the decisional q−PBDHE assumption holds.LRSW assumption [12]: let G be the cyclic group of order p, g be a generator of G, and two random values x,y∈ℤp satisfy X=gx and Y=gy. Let OX,Y· be the random oracle, which inputs m∈ℤp and outputs a triplet A=a,ay,ax+mxy, where a∈G. If there is no probability polynomial time algorithm that can generate m,a,b,c satisfying m∉Q, Q∈OX,Y·, m∈ℤp,m≠0,a∈G,b=ax, c=ax+mxy with probability at the least ε, then the LRSW assumption in group G is said to be true.


## 4. Definition and Security Model

### 4.1. System Model

We show the framework of our system in Figure1. There are six main entities, namely, cloud storage provider, attribute authorities (AAs), data owners, data users, system party, and trusted party. The system party will invoke the system setup algorithm and generate the public parameters (PP). The PP is then firstly distributed to the attribute authorities, data owners, data users, and the trusted party. Then, the AAs invoke the authority setup process to generate public keys (PKs) and send their public keys to the data owners, data users, and the trusted party. Also, if the data users possess valid credentials, AAs will assign the attributes to them according to their request. The data owner generates ciphertext (CT) for the message he wants to encrypt and uploads to the cloud storage provider. Once the data owner wishes to alter the access policy over the existing CT, he/she sends a policy update key to the cloud storage provider. Then, in the cloud storage, the ciphertext will be updated accordingly. Subsequently, if the users’ attributes satisfy the access policy of the CT, they can use the components of secret key to generate their secret key SK and perform decryption operation. Finally, the trusted party invokes the tracing algorithm if there is dispute or suspicion and reports the suspected user’s ID (gid) to the AAs.Figure 1
Framework of the system model.


### 4.2. Definition

Our proposed cryptosystem according to the abovedescription consists of the following eight algorithms:Setupλ⟶PP: on input of a security parameter λ, the algorithm (run by the system) outputs the global PPs.AuthoritySetupaid,PP⟶SKaid,PKaid: we assume each authority is recognized by an identifier aid. On input of the global PPs and aid, the algorithm outputs the public key PKaid and the cloud secret key SKaid.KeyGengid,S,SKaid,PP⟶SKS,gid: on input of the user identity (gid), a set of user’s attributes S, and the corresponding authority’s secret keys SKaid and PP, the algorithm outputs the private key SKS,gid for user matching his/her attribute set S.Encryptmsg,M,ρ,PKaid,PP⟶CT: this algorithm is run by a data owner who wants to share the data in the cloud. The algorithm inputs the message (msg) concerning an access policy M,ρ, a set of respective public keys PKaid and PP, and outputs the ciphertext CT.DecryptCT,SKS,gid,PP⟶msg: this algorithm is run by a data user. On input of the global PPs, a ciphertext CT and a private key SKS,gid matching an attribute set S and the algorithm outputs the message msg if decryption is possible.PolicyUpdateKeyGenPP,PKaid,SharesInfomsg,M,ρ,M′,ρ′⟶UKmsg: this algorithm is run by a data owner. On input of the global PPs, a set of public keys PKaid, the encryption information SharesInfomsg, the old access policy M,ρ, and new access policy M′,ρ′, the algorithm outputs the policy update key UKmsg.CTUpteCT,UKmsg⟶CT′: this algorithm is run by the cloud storage provider. On input of the ciphertext CT and updated key UKmsg, the algorithm outputs an updated ciphertext CT′.TraceSKS,gid,PKaid,PP⟶gid or ⊥: this algorithm is run by the trusted party. On input of the decryption key SKS,gid and the public keys PKaid for corresponding authorities and PPs, the algorithm outputs an authority gid.


### 4.3. Security Model

We focus on two types of adversaries as follows:(1)
We consider the malicious data users as thestatic adversary. For static adversaries [11], we request that no unauthorized user can decrypt encrypted data stored in the cloud. In addition, we request that the collusion of a group of unauthorized malicious users is still unable to obtain unauthorized decryption privileges, which means our scheme needs to have collusion resistance.(2)
We consider the “honest but curious” cloud provider as thetraceable adversary. We assume that the traceable adversary [24] will follow the protocol’s specification but will collect as much information as possible, i.e., secret/private keys. The traceable adversary is not allowed to obtain more secret information than it already has. In addition, it cannot identify “who has accessed the encrypted data” and “who has requested the decryption service.” Also, it cannot link a valid decryption request to a previous decryption request.Then, we have the following two security models.


#### 4.3.1. Model 1: Security for Static Adversary

The security model for static adversary is based on the static security model [11]. To define the security of our scheme (satisfying the abovementioned requirements), we design the following security games:Init. The adversary A selects a set of corrupted authorization agencies, records it as Caid⊆Uaid, and keeps it unchanged throughout the game. The normal authorized agencies are recorded as Naid⊆Uaid with Naid⊆Uaid=∅; A knows the secret key of each corrupted organization SKaidaid∈Caid.Setup. The challenger C runs the system Setup of the solution in this article and sends the global PP to the opponent.Query. A requests gidj,Sjj∈m as the relevant private key, where Sj⊆U is the attribute set of the user with identity gidj. All users’ identities are unique, and for arbitrary i∈S, there holds Ti∉Caid. Then, the adversary sends two messages msg0 and msg1 with the same length and a set of challenges Mi,ρi,…,Mp,ρp. For each challenge, the access policy must satisfy the nonauthorization set. Finally, the ciphertext policy is requested to update any two access policies of the query challenge message and among them.Challenge. The challenger C randomly selects and responds to the adversary according to the RW scheme [11], including a set of public keys of the normal authority, a satisfied user private key, and a set of verification ciphertexts used to challenge the adversary. We use the simulator to convert the adversary’s query into a form that the challenger can recognize as a RW scheme and also convert the challenger’s response to the adversary.Guess. A outputs a guess b′=0,1 for b.As can be seen in this game, the advantage ofA is defined as Adv=Prb′=b−1/2.According to [11], we have the following definition.Definition 1.
The T-DPU-MCP-ABE scheme is static secure if all PPT adversaries have at most a negligible advantage in the abovementioned game.


#### 4.3.2. Model 2: Security for Traceable Adversary

The security game for traceable adversary is similar to the game of the static one except theSetup, Query, and Forgery (identical to Guess) as follows:Setup. C runs Setupλ and AuthoritySetupaid,PP and sends the PP and the authority public key PKaid to A.Query. A requests gidj,Sjj∈m as the relevant private key, where Sj⊆U is the attribute set of the user with identity gidj. Then, C runs KeyGengidj,Sj,SKaid,PP and sends SKSj,gidjj∈m to A.Forgery. A outputs a forgery secret key SK∗, if TraceSKS,gid,PKaid,PP∉Δ, and gid∉gid1,…,gidm.According to [24], we have the following definition.Definition 2.
The T-DPU-MCP-ABE scheme is traceable secure if all PPT adversaries have at most a negligible advantagePrTraceSK∗,PKaid,PP∉Δ,gid1,…,gidm in the abovementioned game.


## 4.1. System Model

We show the framework of our system in Figure1. There are six main entities, namely, cloud storage provider, attribute authorities (AAs), data owners, data users, system party, and trusted party. The system party will invoke the system setup algorithm and generate the public parameters (PP). The PP is then firstly distributed to the attribute authorities, data owners, data users, and the trusted party. Then, the AAs invoke the authority setup process to generate public keys (PKs) and send their public keys to the data owners, data users, and the trusted party. Also, if the data users possess valid credentials, AAs will assign the attributes to them according to their request. The data owner generates ciphertext (CT) for the message he wants to encrypt and uploads to the cloud storage provider. Once the data owner wishes to alter the access policy over the existing CT, he/she sends a policy update key to the cloud storage provider. Then, in the cloud storage, the ciphertext will be updated accordingly. Subsequently, if the users’ attributes satisfy the access policy of the CT, they can use the components of secret key to generate their secret key SK and perform decryption operation. Finally, the trusted party invokes the tracing algorithm if there is dispute or suspicion and reports the suspected user’s ID (gid) to the AAs.Figure 1
Framework of the system model.


## 4.2. Definition

Our proposed cryptosystem according to the abovedescription consists of the following eight algorithms:Setupλ⟶PP: on input of a security parameter λ, the algorithm (run by the system) outputs the global PPs.AuthoritySetupaid,PP⟶SKaid,PKaid: we assume each authority is recognized by an identifier aid. On input of the global PPs and aid, the algorithm outputs the public key PKaid and the cloud secret key SKaid.KeyGengid,S,SKaid,PP⟶SKS,gid: on input of the user identity (gid), a set of user’s attributes S, and the corresponding authority’s secret keys SKaid and PP, the algorithm outputs the private key SKS,gid for user matching his/her attribute set S.Encryptmsg,M,ρ,PKaid,PP⟶CT: this algorithm is run by a data owner who wants to share the data in the cloud. The algorithm inputs the message (msg) concerning an access policy M,ρ, a set of respective public keys PKaid and PP, and outputs the ciphertext CT.DecryptCT,SKS,gid,PP⟶msg: this algorithm is run by a data user. On input of the global PPs, a ciphertext CT and a private key SKS,gid matching an attribute set S and the algorithm outputs the message msg if decryption is possible.PolicyUpdateKeyGenPP,PKaid,SharesInfomsg,M,ρ,M′,ρ′⟶UKmsg: this algorithm is run by a data owner. On input of the global PPs, a set of public keys PKaid, the encryption information SharesInfomsg, the old access policy M,ρ, and new access policy M′,ρ′, the algorithm outputs the policy update key UKmsg.CTUpteCT,UKmsg⟶CT′: this algorithm is run by the cloud storage provider. On input of the ciphertext CT and updated key UKmsg, the algorithm outputs an updated ciphertext CT′.TraceSKS,gid,PKaid,PP⟶gid or ⊥: this algorithm is run by the trusted party. On input of the decryption key SKS,gid and the public keys PKaid for corresponding authorities and PPs, the algorithm outputs an authority gid.


## 4.3. Security Model

We focus on two types of adversaries as follows:(1)
We consider the malicious data users as thestatic adversary. For static adversaries [11], we request that no unauthorized user can decrypt encrypted data stored in the cloud. In addition, we request that the collusion of a group of unauthorized malicious users is still unable to obtain unauthorized decryption privileges, which means our scheme needs to have collusion resistance.(2)
We consider the “honest but curious” cloud provider as thetraceable adversary. We assume that the traceable adversary [24] will follow the protocol’s specification but will collect as much information as possible, i.e., secret/private keys. The traceable adversary is not allowed to obtain more secret information than it already has. In addition, it cannot identify “who has accessed the encrypted data” and “who has requested the decryption service.” Also, it cannot link a valid decryption request to a previous decryption request.Then, we have the following two security models.


### 4.3.1. Model 1: Security for Static Adversary

The security model for static adversary is based on the static security model [11]. To define the security of our scheme (satisfying the abovementioned requirements), we design the following security games:Init. The adversary A selects a set of corrupted authorization agencies, records it as Caid⊆Uaid, and keeps it unchanged throughout the game. The normal authorized agencies are recorded as Naid⊆Uaid with Naid⊆Uaid=∅; A knows the secret key of each corrupted organization SKaidaid∈Caid.Setup. The challenger C runs the system Setup of the solution in this article and sends the global PP to the opponent.Query. A requests gidj,Sjj∈m as the relevant private key, where Sj⊆U is the attribute set of the user with identity gidj. All users’ identities are unique, and for arbitrary i∈S, there holds Ti∉Caid. Then, the adversary sends two messages msg0 and msg1 with the same length and a set of challenges Mi,ρi,…,Mp,ρp. For each challenge, the access policy must satisfy the nonauthorization set. Finally, the ciphertext policy is requested to update any two access policies of the query challenge message and among them.Challenge. The challenger C randomly selects and responds to the adversary according to the RW scheme [11], including a set of public keys of the normal authority, a satisfied user private key, and a set of verification ciphertexts used to challenge the adversary. We use the simulator to convert the adversary’s query into a form that the challenger can recognize as a RW scheme and also convert the challenger’s response to the adversary.Guess. A outputs a guess b′=0,1 for b.As can be seen in this game, the advantage ofA is defined as Adv=Prb′=b−1/2.According to [11], we have the following definition.Definition 1.
The T-DPU-MCP-ABE scheme is static secure if all PPT adversaries have at most a negligible advantage in the abovementioned game.


### 4.3.2. Model 2: Security for Traceable Adversary

The security game for traceable adversary is similar to the game of the static one except theSetup, Query, and Forgery (identical to Guess) as follows:Setup. C runs Setupλ and AuthoritySetupaid,PP and sends the PP and the authority public key PKaid to A.Query. A requests gidj,Sjj∈m as the relevant private key, where Sj⊆U is the attribute set of the user with identity gidj. Then, C runs KeyGengidj,Sj,SKaid,PP and sends SKSj,gidjj∈m to A.Forgery. A outputs a forgery secret key SK∗, if TraceSKS,gid,PKaid,PP∉Δ, and gid∉gid1,…,gidm.According to [24], we have the following definition.Definition 2.
The T-DPU-MCP-ABE scheme is traceable secure if all PPT adversaries have at most a negligible advantagePrTraceSK∗,PKaid,PP∉Δ,gid1,…,gidm in the abovementioned game.


## 4.3.1. Model 1: Security for Static Adversary

The security model for static adversary is based on the static security model [11]. To define the security of our scheme (satisfying the abovementioned requirements), we design the following security games:Init. The adversary A selects a set of corrupted authorization agencies, records it as Caid⊆Uaid, and keeps it unchanged throughout the game. The normal authorized agencies are recorded as Naid⊆Uaid with Naid⊆Uaid=∅; A knows the secret key of each corrupted organization SKaidaid∈Caid.Setup. The challenger C runs the system Setup of the solution in this article and sends the global PP to the opponent.Query. A requests gidj,Sjj∈m as the relevant private key, where Sj⊆U is the attribute set of the user with identity gidj. All users’ identities are unique, and for arbitrary i∈S, there holds Ti∉Caid. Then, the adversary sends two messages msg0 and msg1 with the same length and a set of challenges Mi,ρi,…,Mp,ρp. For each challenge, the access policy must satisfy the nonauthorization set. Finally, the ciphertext policy is requested to update any two access policies of the query challenge message and among them.Challenge. The challenger C randomly selects and responds to the adversary according to the RW scheme [11], including a set of public keys of the normal authority, a satisfied user private key, and a set of verification ciphertexts used to challenge the adversary. We use the simulator to convert the adversary’s query into a form that the challenger can recognize as a RW scheme and also convert the challenger’s response to the adversary.Guess. A outputs a guess b′=0,1 for b.As can be seen in this game, the advantage ofA is defined as Adv=Prb′=b−1/2.According to [11], we have the following definition.Definition 1.
The T-DPU-MCP-ABE scheme is static secure if all PPT adversaries have at most a negligible advantage in the abovementioned game.


## 4.3.2. Model 2: Security for Traceable Adversary

The security game for traceable adversary is similar to the game of the static one except theSetup, Query, and Forgery (identical to Guess) as follows:Setup. C runs Setupλ and AuthoritySetupaid,PP and sends the PP and the authority public key PKaid to A.Query. A requests gidj,Sjj∈m as the relevant private key, where Sj⊆U is the attribute set of the user with identity gidj. Then, C runs KeyGengidj,Sj,SKaid,PP and sends SKSj,gidjj∈m to A.Forgery. A outputs a forgery secret key SK∗, if TraceSKS,gid,PKaid,PP∉Δ, and gid∉gid1,…,gidm.According to [24], we have the following definition.Definition 2.
The T-DPU-MCP-ABE scheme is traceable secure if all PPT adversaries have at most a negligible advantagePrTraceSK∗,PKaid,PP∉Δ,gid1,…,gidm in the abovementioned game.


## 5. Traceable and Dynamic Policy Updating Multiauthority Attribute-Based Encryption

Here, we present our attribute-based key encryption scheme. Our scheme is constructed on the bilinear groupG with a large prime order p and utilizes the LSSS access strategy together with two random oracle hash functions H1 and H2. We realize the traceability by adopting the CL (Camenisch–Lysyanskaya) signature scheme [25]. Our scheme has two domains, namely, the attribute domain U and the authority domain Uaid. There is a corresponding authorized authority aid releasing an effective attribute set to the users for each attribute.Then, our scheme is specifically constructed as follows.


### 5.1. Our Construction

Setupλ⟶PP: this algorithm takes as input the security parameter λ and gets D=G,GT,p,e, where p is the prime order and GT, e is the bilinear mapping e:G×G⟶GT. It sets the attribute universe be U=ℤp. It then chooses random g∈G and three cryptographic hash functions H1, H2, and T, where H1,H2:0,1∗⟶G are used to hash the identity and the attribute of a user into an element of G, respectively. Also, T:0,1∗⟶ℤq∗ is used to hash the attribute i into the corresponding aid. Finally, this algorithm sets the global public parameters PP=G,GT,p,e,g,H1,H2,T as output.AuthoritySetupaid,PP⟶SKaid,PKaid: the algorithm chooses three random αaid,βaid,γaid∈ℤp. Together with the inputs aid and PP, it then publishes the public key PKaid=eg,gαaid,gβaid,gγaid of the AU and sets the secret key as SKaid=αaid,βaid,γaid.KeyGengid,S,SKaid,PP⟶SKS,gid: the algorithm chooses random t∈ℤp, u∈G,u∉H1gid and computes(4)K1,i,gid=gαaid·H1gidβaid·H2it·uβaidgid+γaidK2,i,gid=uγaidK3,i,gid=uK4,i,gid=gtK5,gid=gid.It outputs the secret keySKS,gid=K1,i,gid,K2,i,gid,K3,i,gid,K4,i,gidi∈S,K5,gid.Encryptmsg,M,ρ,PKaidPP⟶CT: on input of the message (msg), the PPs and an access policy M,ρ (where M is an l×n matrix), the public key of the agency PKaid, and the public parameters PP, the algorithm firstly chooses a random s∈ℤp. Then, it chooses random x2,…,xn∈ℤp, sets two vectors v=s,x1,x2,…,xn and υ=0,υ2,…,υn, and computes the vectors of shares of s and 0 as λx=MxvT and ωx=MxυT, respectively (where T denotes the transpose of the matrix).Finally, it chooses randomrx∈ℤp and computes(5)C0=msg·eg,gs,C1,x=eg,gλx+αδxrx,C2,x=gωx,C3,x=gβδxrx,C4,x=H2ρxrx,C5,x=g−rx.The ciphertextCT is set as CT=C0,C1,x,C2,x,C3,x,C4,x,C5,xx∈1,…,l.DecryptCT,SKS,gid,PP⟶msg: on input of CT=C0,C1,x,C2,x,C3,x,C4,x,C5,xx∈1,…,l, S, SKS,gid, and PP, the algorithm sets the identification set as I⊆1,…,l. For all x∈I and x:ρx∈S, the algorithm computes(6)Dx=C1,x·eH1K5,gid,C2,x·C3,x·eK2,ρx,gid·K3,ρx,gidK5,gid,C3,x·eC4,x,K4,ρx,gid·eK1,ρx,gid,C5,x,wherecxx∈I and ∑x∈IcxMx=1,0,…,0.Finally, the message is recovered by computing(7)msg=C0∏x∈IDxcx.PolicyUpteKeyGenPP,PKaid,Shares,M,ρ,M′,ρ′⟶UKmsg: M is a generator matrix of 1,…,n, and Shares represents the information of the two random vectors v and υ contained in the encryption algorithm. We define the function δi=Tρii∈I and δ′j=T′ρjj∈I.First, the new access strategy and the old access strategy are used as input through the strategy comparison method in the literature [26] to generate three subset record rows indexes I1,M,I2,M,I3,M. Then, it picks two random vectors v′=s,v2′,…,vn′ and υ′=0,υ2′,…,υn′ and then calculates λj′=Mj′v′T and ωj′=Mj′υ′T with j∈1,…,l′.When the row index satisfiesj,i∈I1,M′ (marked as module 1), the algorithm generates the update key as(8)UKj,i,msg1=UK1,j,i,msg=gλj′−λi,UK2,j,i,msg=gωj′−ωi.When the row index satisfiesj,i∈I2,M′ (marked as module 2), the algorithm randomly picks aj∈ℤp and calculates the update key as(9)UKj,i,msg2=aj,UK1,j,i,msg=giλj′−ajλ,UK2,j,i,msg=gωj′−ajωi.When the row index satisfiesj,i∈I3,M′ (marked as Module 3), the algorithm randomly picks rj′∈ℤp and generates the update key as(10)UKj,i,msg3=UK1,j,i,msg=gλj+αδ′jrj′,UK2,j,i,msg=gωj′,UK3,j,i,msg=gβδ′jrj′,UK4,j,i,msg=H2ρ′jrj′,UK5,j,i,msg=grj′.Finally, the data owner sends the updated keyUKmsg to the cloud storage service provider with UKmsg=UKj,i,msg1,UKj,i,msg2,UKj,i,msg3.CTUpdateCT,UKmsg⟶CT′: after the cloud storage service provider receives the update key, it updates the ciphertext CT to CT′. By doing so, the cloud storage service provider cannot obtain relevant information during the re-encryption process of the ciphertext. The specific updates are as follows:When the row index belongs to module 1, the update parameter is(11)C1,j′=C1,i·eg,UK1,j,i,msg=eg,gλj′+αδ′jrj′,C2,j′=C2,i·UK2,j,i,msg=gωj′,C3,j′=C3,i=gβδ′jrj′,C4,j′=C4,i=H2ρ′jrj′,C5,j′=C5,i=g−rj′,rj′=ri,δ′j=δi=H2ρ′j=H2ρi.When the row index belongs to module 2, the update parameter is(12)C1,j′=C1,iaj·eg,UK1,j,i,msg=eg,gλj′+αδ′jrj′,C2,j′=C2,iaj·UK2,j,i,msg=gωj′,C3,j′=C3,iaj=gβδiriaj=gβδ′jrj′,C4,j′=C4,iaj=H2ρiriaj=H2ρ′jrj′,C5,j′=C5,iaj=g−riaj=g−rj′,rj′=riaj,δ′j=δi.When the row index belongs to module 3, the update parameter is(13)C1,j′=eg,UK1,j,i,msg=eg,gλj′+αδ′jrj′,C2,j′=UK2,j,i,msg=gωj′,C3,j′=UK3,j,i,msg=gβδ′jrj′,C4,j′=UK4,j,i,msg=H2ρ′jrj′,C5,j′=UK5,j,i,msg=g−rj′,rj′=riaj,δ′j=δi.Finally, the updated ciphertextCT′ is CT′=C0,C1,j′,C2,j′,C3,j′,C4,j′,C5,j′j∈1,…,l′.TraceSKS,gid,PKaid,PP⟶gid or ⊥: the algorithm inputs the decryption key SKS,gid and the public key PKaid associated with the global public parameter PP. If the decryption key SKS,gid is not in the form SKS,gid=K1,i,gid,K2,i,gid,K3,i,gid,K4,i,gidi∈S,K5,gid or cannot pass the key integrity check, the algorithm will output a special symbol to indicate that there is no need to trace SKS,gid. The key integrity check of this scheme is as follows:(14)K1,i,gid,K2,i,gid,K3,i,gid,K4,i,gid∈G,K5,gid∈ℤp∗,eK2,i,gid,g=eK3,i,gid,gγaid,eK1,i,gid,g=eg,gαaid·eHK5,gid,gβaid·eFi,K4,i,gid·eK2,ρx,gid·K3,ρx,gidK5,gid,gβaid.If there is an attributei∈S that satisfies equations (14), it is considered that the key SKS,gid passes the integrity check, and the identity gid is output as the trace identity.


### 5.2. Correctness

The correctness of our scheme can be obtained from the following equations. It is known that(15)Dx=C1,x·eH1K5,gid,C2,x·C3,x·eK2,ρx,gid·K3,ρx,gidK5,gid,C3,x·eC4,x,K4,ρx,gid·eK1,ρx,gid,C5,x.According to the corresponding values ofCT and SKS,gid, we can obtain(16)Dx=eg,gλx+αδxrx·eH1gid,gωx·gβδxrx·euγδx·ugid,gβδxrx·eH2ρxrx,gt·egαδx·H1gidβδx·H2it·uβδxgid+γδx,g−rx,=eg,gλx+αδxrx·eH1gid,gωx+βδxrx·eu,gγδx+gidβδxrx·eH2ρx,grxt·eg,g−αδxrx·eH1gid,g−βδxrx·eH2ρx,g−rxt·eu,g−γδx+gidβδxrx,=eg,gλx·eH1gid,gωx.Then, forcxx∈I and ∑x∈IcxMx=1,0,…,0, we have(17)∑x∈Iλxcx=∑x∈IMxνTcx=1,0,…,0·νT=s,∑x∈Iωxcx=∑x∈IMxυTcx=1,0,…,0·υT=0.Hence, we have(18)∏x∈IDxcx=∏x∈Ieg,gλx·eH1gid,gωxcx,=eg,gΣx∈Iλxcx·eg,gΣx∈Iωxcx,=eg,gs.This proves that the message can be correctly restored to(19)msg=C0∏x∈IDxcx.


### 5.3. Security Analysis

Theorem 1.
Assume the CP-ABE system in [11] is statically secure; then, the T-DPU-MCP-ABE system is static secure with respect to Definition 1.Proof.
For simplicity, we useΣRW, Σtdpum to denote the CP-ABE system in [11] and our T-DPU-MCP-ABE system, respectively. We suppose there exists a static polynomial time attacker A that breaks ΣRW with a nonnegligible advantage in selectively with a challenge LSSS access policy M∗,ρ∗, where M∗ is an l×n matrix. We will build a PPT algorithm ℬ that breaks Σtdpum with a nonnegligible advantage.Init:ℬ gets a challenge LSSS access policy M∗,ρ∗ from A and transmits the received M∗,ρ∗ to the Σe challenger C.Setup:C generates the common parameter PP=G,GT,p,e,g,H1,H2,T and sends it to A.Query:ℬ initializes an integer counter j=0 and an empty table T. Then, A makes the following queries:
ReceivingA’s decryption key query with an attribute does not satisfy M∗,ρ∗, ℬ sets the attribute as Sj and j=j+1, then sends them to the Σtdpum challenger, and obtains a secret key SKS,gid′=K1,τ,gid′,K2,τ,gid′,K3,τ,gid′,K4,τ,gid′τ∈|S|,K5,gid′. A chooses a corrupted AA Caid∈Uaid and generates the corresponding public key PKaid′=eg,gaid,gβaid in SRW. Also, for each aid∈Caid, A randomly chooses γaid∈ℤp∗ and generates the system public key PKaid=eg,gaid,gβaid,gγaid. Then, A responses for the normal AA Naid, the corrupted AA Caid by interacting with ℬ as follows. A requires gidj,Sjj∈m, where Sj⊂U is the corresponding attribute set of user gidj. All users’ gidj are unique and for arbitrary i∈S, we have Ti∉Caid. Then, A fixes a coin b∈0,1, which is used to generates message msg0 or msg1 with the same length. A chooses a set of challenge M1,ρ,…,Mq,ρq. Finally, A sends all the chosen parameters to ℬ.Challenge:A chooses two same length messages m0,m1 and sends to ℬ. Then, ℬ submits m0,m1 to the Σtdpum challenger, obtains a challenge common public key PKaid′=eg,gaid,gβaid, and generates a ciphertext ct∗=C0∗C1,x∗,C2,x∗,C3,x∗,C4,x∗,C5,x∗x∈1,…,l. ℬ chooses a random bit bℬ∈0,1, computes keybℬ=C∗/mbℬ, and sends the new ciphertext ct∗=C0∗C1,x∗,C2,x∗,C3,x∗,C4,x∗,C5,x∗x∈1,…,l to A.Guess: finally, after receiving the abovementioned responses,A outputs a guess bA∈0,1. If bA=1, it means that A guesses that keybℬ is a random key, and ℬ outputs 1−bℬ. If bA=0, meaning that A guesses that keybℬ is the key from ctnew∗, ℬ outputs bℬ.
Since the real system is the same as the distributions of the challenge ciphertext, ifA breaks the security of SRW with a nonnegligible advantage, then the simulator ℬ can selectively break Stdpum with the same advantage.Theorem 2.
Assume the CL signature scheme in [25] is against existing forgery, and the T-DPU-MCP-ABE system in Section 5.1 is traceable secure with respect to Definition 2.Proof.
The security proof of the T-DPU-MCP-ABE system with respect to Definition2 (i.e., for traceable adversary) is identical to the abovementioned proof except that the adversary runs the Forgery phase instead of the Guess phase. Here, we suppose there exists a PPT attacker A that selectively breaks the CL scheme with a nonnegligible advantage. We can build a PPT simulator algorithm ℬ that selectively breaks Σtdpum with a nonnegligible advantage. It is proved that the CL scheme is secure against existential forgery under adaptive chosen message attack with LRSW assumption.Setup: theCL scheme challenger C delivers each authority’s public keys G,GT,p,g,gβaid,gγaid to the simulator algorithm ℬ. ℬ chooses random values αaid∈ℤp∗ for each authority, runs Setupλ and AuthoritySetupaid,PP to generate the public key PKaid=eg,gαaid,gβaid,gγaid, and sends the public parameter PP and the authority public key PKaid to A.The two hash functions H1 and H2 of our scheme are managed by simulator ℬ.Query.A requests gidj,Sjj∈m as the relevant private key, where Sj⊆U means the attribute set of the user gidj. Before A forges the key, to maintain hash functions H1 and H2, ℬ will set two empty tables, T1 and T2, respectively, and update them according to the query of A. When the gid queried by A does not exist in the table of T1 and T2, ℬ will select a random element tgid∈ℤp∗ and a random element ti∈ℤp∗ and then record tgid,gtgid and ti,gti with T1 and T2, respectively. At the same time, simulator ℬ will return the hash value of H1 or H2 according to opponent the query of A. For each i∈Sj, if the attribute authority aid=Ti, then B will submit gidj,aid to Challenger C according to the query of A so as to obtain the signature u,uγaid,uβaid·γaid/gidj+1 in the CL scheme. Then, ℬ takes the random value t∈ℤp∗ and runs KeyGen(gidj,Sj,SKaid,PP) as well as sends SKSj,gidjj∈m to A. In this step, ℬ should computes the following:(20)K1,i,gid=gαaid·H1gidjβaid·H2it·uβaidgid+γaid,K2,i,gid=uγaid,K3,i,gid=u,K4,i,gid=gt,K5,gid=gid.Then, the final calculation isSKSj,gidj as K1,i,gidj,K2,i,gidj,K3,i,gidj,K4,i,gidji∈Sj,K5,gidj.Forgery. in this step,A already queries from simulator ℬ the value of H1gid and H2i and obtains H1gid as gtK5,gid and H2i as gti. A assumes the unknown K3,i,gid=gt3 and K4,i,gid=gt4. Through formula (14) in Section 5.1, we could get that K2,i,gid=K3,i,gid=gt3γaid. Also through formula (14) in Section 5.1, we could get that K1,i,gid=gαaid+tK5,gidβaid·K4,i,gidti·K3,i,gidβaidK5,gid+γaid.
Then,ℬ calculates a legal signature σ according to the CL scheme, and the calculation process is as follows:(21)σ1=K1,i,gidgαaid+tK5,gidβaid·K4,i,gidti,=K3,i,gidβaidK5,gid+γaid.
Then,A picks a gid as a message and gives σ=K3,i,gid,K2,i,gid,σ1/K3,i,gidgid as the signature of the message gid according to the CL scheme.
Finally,A outputs a forgery secret key SK∗, if TraceSKS,gid,PKaid,PP∉Δ and gid∉gid1,…,gidm. As gid∉gid1,…,gidm, we know that the signature of message gid is not invoked by ℬ yet. Thus, the simulator ℬ breaks the CL scheme with the same advantage.
Since in the abovementioned game the whole system has the decryption keys, the distributions of the public parameters, and challenge ciphertext, ifA breaks the security of the CL scheme, then the simulator ℬ can selectively break Stdpum with the same advantage. Hence, if the LRSW assumption holds true, the proposed cryptosystem is against forgery, meaning that our scheme is traceable secure for the adversary.


### 5.4. Proof of Collusion Prevention

In our scheme, we use the uniquegid and construct the hash function value corresponding to gid to resist collusion attack, which has been proved to be feasible by Allison and Waters [14]. In the process of decryption, the data user needs to calculate Dx=eg,gxλ·eH1gid,gωx. For a single user with the access policy satisfaction attribute set, since ωx are the shares of secret value 0, eH1gid,gωx can be eliminated, where eH1gid,gωx=1. In case of collusion attack, two or more users will have different gid; thus, the value of H1gid will also be different; eH1gid,gωx with a secret value of 0 cannot be constructed, and thus, it cannot be eliminated. Therefore, two or more users cannot share their attribute key values to generate collusion attacks, which means this scheme is resistant to collusion attack.


## 5.1. Our Construction

Setupλ⟶PP: this algorithm takes as input the security parameter λ and gets D=G,GT,p,e, where p is the prime order and GT, e is the bilinear mapping e:G×G⟶GT. It sets the attribute universe be U=ℤp. It then chooses random g∈G and three cryptographic hash functions H1, H2, and T, where H1,H2:0,1∗⟶G are used to hash the identity and the attribute of a user into an element of G, respectively. Also, T:0,1∗⟶ℤq∗ is used to hash the attribute i into the corresponding aid. Finally, this algorithm sets the global public parameters PP=G,GT,p,e,g,H1,H2,T as output.AuthoritySetupaid,PP⟶SKaid,PKaid: the algorithm chooses three random αaid,βaid,γaid∈ℤp. Together with the inputs aid and PP, it then publishes the public key PKaid=eg,gαaid,gβaid,gγaid of the AU and sets the secret key as SKaid=αaid,βaid,γaid.KeyGengid,S,SKaid,PP⟶SKS,gid: the algorithm chooses random t∈ℤp, u∈G,u∉H1gid and computes(4)K1,i,gid=gαaid·H1gidβaid·H2it·uβaidgid+γaidK2,i,gid=uγaidK3,i,gid=uK4,i,gid=gtK5,gid=gid.It outputs the secret keySKS,gid=K1,i,gid,K2,i,gid,K3,i,gid,K4,i,gidi∈S,K5,gid.Encryptmsg,M,ρ,PKaidPP⟶CT: on input of the message (msg), the PPs and an access policy M,ρ (where M is an l×n matrix), the public key of the agency PKaid, and the public parameters PP, the algorithm firstly chooses a random s∈ℤp. Then, it chooses random x2,…,xn∈ℤp, sets two vectors v=s,x1,x2,…,xn and υ=0,υ2,…,υn, and computes the vectors of shares of s and 0 as λx=MxvT and ωx=MxυT, respectively (where T denotes the transpose of the matrix).Finally, it chooses randomrx∈ℤp and computes(5)C0=msg·eg,gs,C1,x=eg,gλx+αδxrx,C2,x=gωx,C3,x=gβδxrx,C4,x=H2ρxrx,C5,x=g−rx.The ciphertextCT is set as CT=C0,C1,x,C2,x,C3,x,C4,x,C5,xx∈1,…,l.DecryptCT,SKS,gid,PP⟶msg: on input of CT=C0,C1,x,C2,x,C3,x,C4,x,C5,xx∈1,…,l, S, SKS,gid, and PP, the algorithm sets the identification set as I⊆1,…,l. For all x∈I and x:ρx∈S, the algorithm computes(6)Dx=C1,x·eH1K5,gid,C2,x·C3,x·eK2,ρx,gid·K3,ρx,gidK5,gid,C3,x·eC4,x,K4,ρx,gid·eK1,ρx,gid,C5,x,wherecxx∈I and ∑x∈IcxMx=1,0,…,0.Finally, the message is recovered by computing(7)msg=C0∏x∈IDxcx.PolicyUpteKeyGenPP,PKaid,Shares,M,ρ,M′,ρ′⟶UKmsg: M is a generator matrix of 1,…,n, and Shares represents the information of the two random vectors v and υ contained in the encryption algorithm. We define the function δi=Tρii∈I and δ′j=T′ρjj∈I.First, the new access strategy and the old access strategy are used as input through the strategy comparison method in the literature [26] to generate three subset record rows indexes I1,M,I2,M,I3,M. Then, it picks two random vectors v′=s,v2′,…,vn′ and υ′=0,υ2′,…,υn′ and then calculates λj′=Mj′v′T and ωj′=Mj′υ′T with j∈1,…,l′.When the row index satisfiesj,i∈I1,M′ (marked as module 1), the algorithm generates the update key as(8)UKj,i,msg1=UK1,j,i,msg=gλj′−λi,UK2,j,i,msg=gωj′−ωi.When the row index satisfiesj,i∈I2,M′ (marked as module 2), the algorithm randomly picks aj∈ℤp and calculates the update key as(9)UKj,i,msg2=aj,UK1,j,i,msg=giλj′−ajλ,UK2,j,i,msg=gωj′−ajωi.When the row index satisfiesj,i∈I3,M′ (marked as Module 3), the algorithm randomly picks rj′∈ℤp and generates the update key as(10)UKj,i,msg3=UK1,j,i,msg=gλj+αδ′jrj′,UK2,j,i,msg=gωj′,UK3,j,i,msg=gβδ′jrj′,UK4,j,i,msg=H2ρ′jrj′,UK5,j,i,msg=grj′.Finally, the data owner sends the updated keyUKmsg to the cloud storage service provider with UKmsg=UKj,i,msg1,UKj,i,msg2,UKj,i,msg3.CTUpdateCT,UKmsg⟶CT′: after the cloud storage service provider receives the update key, it updates the ciphertext CT to CT′. By doing so, the cloud storage service provider cannot obtain relevant information during the re-encryption process of the ciphertext. The specific updates are as follows:When the row index belongs to module 1, the update parameter is(11)C1,j′=C1,i·eg,UK1,j,i,msg=eg,gλj′+αδ′jrj′,C2,j′=C2,i·UK2,j,i,msg=gωj′,C3,j′=C3,i=gβδ′jrj′,C4,j′=C4,i=H2ρ′jrj′,C5,j′=C5,i=g−rj′,rj′=ri,δ′j=δi=H2ρ′j=H2ρi.When the row index belongs to module 2, the update parameter is(12)C1,j′=C1,iaj·eg,UK1,j,i,msg=eg,gλj′+αδ′jrj′,C2,j′=C2,iaj·UK2,j,i,msg=gωj′,C3,j′=C3,iaj=gβδiriaj=gβδ′jrj′,C4,j′=C4,iaj=H2ρiriaj=H2ρ′jrj′,C5,j′=C5,iaj=g−riaj=g−rj′,rj′=riaj,δ′j=δi.When the row index belongs to module 3, the update parameter is(13)C1,j′=eg,UK1,j,i,msg=eg,gλj′+αδ′jrj′,C2,j′=UK2,j,i,msg=gωj′,C3,j′=UK3,j,i,msg=gβδ′jrj′,C4,j′=UK4,j,i,msg=H2ρ′jrj′,C5,j′=UK5,j,i,msg=g−rj′,rj′=riaj,δ′j=δi.Finally, the updated ciphertextCT′ is CT′=C0,C1,j′,C2,j′,C3,j′,C4,j′,C5,j′j∈1,…,l′.TraceSKS,gid,PKaid,PP⟶gid or ⊥: the algorithm inputs the decryption key SKS,gid and the public key PKaid associated with the global public parameter PP. If the decryption key SKS,gid is not in the form SKS,gid=K1,i,gid,K2,i,gid,K3,i,gid,K4,i,gidi∈S,K5,gid or cannot pass the key integrity check, the algorithm will output a special symbol to indicate that there is no need to trace SKS,gid. The key integrity check of this scheme is as follows:(14)K1,i,gid,K2,i,gid,K3,i,gid,K4,i,gid∈G,K5,gid∈ℤp∗,eK2,i,gid,g=eK3,i,gid,gγaid,eK1,i,gid,g=eg,gαaid·eHK5,gid,gβaid·eFi,K4,i,gid·eK2,ρx,gid·K3,ρx,gidK5,gid,gβaid.If there is an attributei∈S that satisfies equations (14), it is considered that the key SKS,gid passes the integrity check, and the identity gid is output as the trace identity.


## 5.2. Correctness

The correctness of our scheme can be obtained from the following equations. It is known that(15)Dx=C1,x·eH1K5,gid,C2,x·C3,x·eK2,ρx,gid·K3,ρx,gidK5,gid,C3,x·eC4,x,K4,ρx,gid·eK1,ρx,gid,C5,x.According to the corresponding values ofCT and SKS,gid, we can obtain(16)Dx=eg,gλx+αδxrx·eH1gid,gωx·gβδxrx·euγδx·ugid,gβδxrx·eH2ρxrx,gt·egαδx·H1gidβδx·H2it·uβδxgid+γδx,g−rx,=eg,gλx+αδxrx·eH1gid,gωx+βδxrx·eu,gγδx+gidβδxrx·eH2ρx,grxt·eg,g−αδxrx·eH1gid,g−βδxrx·eH2ρx,g−rxt·eu,g−γδx+gidβδxrx,=eg,gλx·eH1gid,gωx.Then, forcxx∈I and ∑x∈IcxMx=1,0,…,0, we have(17)∑x∈Iλxcx=∑x∈IMxνTcx=1,0,…,0·νT=s,∑x∈Iωxcx=∑x∈IMxυTcx=1,0,…,0·υT=0.Hence, we have(18)∏x∈IDxcx=∏x∈Ieg,gλx·eH1gid,gωxcx,=eg,gΣx∈Iλxcx·eg,gΣx∈Iωxcx,=eg,gs.This proves that the message can be correctly restored to(19)msg=C0∏x∈IDxcx.


## 5.3. Security Analysis

Theorem 1.
Assume the CP-ABE system in [11] is statically secure; then, the T-DPU-MCP-ABE system is static secure with respect to Definition 1.Proof.
For simplicity, we useΣRW, Σtdpum to denote the CP-ABE system in [11] and our T-DPU-MCP-ABE system, respectively. We suppose there exists a static polynomial time attacker A that breaks ΣRW with a nonnegligible advantage in selectively with a challenge LSSS access policy M∗,ρ∗, where M∗ is an l×n matrix. We will build a PPT algorithm ℬ that breaks Σtdpum with a nonnegligible advantage.Init:ℬ gets a challenge LSSS access policy M∗,ρ∗ from A and transmits the received M∗,ρ∗ to the Σe challenger C.Setup:C generates the common parameter PP=G,GT,p,e,g,H1,H2,T and sends it to A.Query:ℬ initializes an integer counter j=0 and an empty table T. Then, A makes the following queries:
ReceivingA’s decryption key query with an attribute does not satisfy M∗,ρ∗, ℬ sets the attribute as Sj and j=j+1, then sends them to the Σtdpum challenger, and obtains a secret key SKS,gid′=K1,τ,gid′,K2,τ,gid′,K3,τ,gid′,K4,τ,gid′τ∈|S|,K5,gid′. A chooses a corrupted AA Caid∈Uaid and generates the corresponding public key PKaid′=eg,gaid,gβaid in SRW. Also, for each aid∈Caid, A randomly chooses γaid∈ℤp∗ and generates the system public key PKaid=eg,gaid,gβaid,gγaid. Then, A responses for the normal AA Naid, the corrupted AA Caid by interacting with ℬ as follows. A requires gidj,Sjj∈m, where Sj⊂U is the corresponding attribute set of user gidj. All users’ gidj are unique and for arbitrary i∈S, we have Ti∉Caid. Then, A fixes a coin b∈0,1, which is used to generates message msg0 or msg1 with the same length. A chooses a set of challenge M1,ρ,…,Mq,ρq. Finally, A sends all the chosen parameters to ℬ.Challenge:A chooses two same length messages m0,m1 and sends to ℬ. Then, ℬ submits m0,m1 to the Σtdpum challenger, obtains a challenge common public key PKaid′=eg,gaid,gβaid, and generates a ciphertext ct∗=C0∗C1,x∗,C2,x∗,C3,x∗,C4,x∗,C5,x∗x∈1,…,l. ℬ chooses a random bit bℬ∈0,1, computes keybℬ=C∗/mbℬ, and sends the new ciphertext ct∗=C0∗C1,x∗,C2,x∗,C3,x∗,C4,x∗,C5,x∗x∈1,…,l to A.Guess: finally, after receiving the abovementioned responses,A outputs a guess bA∈0,1. If bA=1, it means that A guesses that keybℬ is a random key, and ℬ outputs 1−bℬ. If bA=0, meaning that A guesses that keybℬ is the key from ctnew∗, ℬ outputs bℬ.
Since the real system is the same as the distributions of the challenge ciphertext, ifA breaks the security of SRW with a nonnegligible advantage, then the simulator ℬ can selectively break Stdpum with the same advantage.Theorem 2.
Assume the CL signature scheme in [25] is against existing forgery, and the T-DPU-MCP-ABE system in Section 5.1 is traceable secure with respect to Definition 2.Proof.
The security proof of the T-DPU-MCP-ABE system with respect to Definition2 (i.e., for traceable adversary) is identical to the abovementioned proof except that the adversary runs the Forgery phase instead of the Guess phase. Here, we suppose there exists a PPT attacker A that selectively breaks the CL scheme with a nonnegligible advantage. We can build a PPT simulator algorithm ℬ that selectively breaks Σtdpum with a nonnegligible advantage. It is proved that the CL scheme is secure against existential forgery under adaptive chosen message attack with LRSW assumption.Setup: theCL scheme challenger C delivers each authority’s public keys G,GT,p,g,gβaid,gγaid to the simulator algorithm ℬ. ℬ chooses random values αaid∈ℤp∗ for each authority, runs Setupλ and AuthoritySetupaid,PP to generate the public key PKaid=eg,gαaid,gβaid,gγaid, and sends the public parameter PP and the authority public key PKaid to A.The two hash functions H1 and H2 of our scheme are managed by simulator ℬ.Query.A requests gidj,Sjj∈m as the relevant private key, where Sj⊆U means the attribute set of the user gidj. Before A forges the key, to maintain hash functions H1 and H2, ℬ will set two empty tables, T1 and T2, respectively, and update them according to the query of A. When the gid queried by A does not exist in the table of T1 and T2, ℬ will select a random element tgid∈ℤp∗ and a random element ti∈ℤp∗ and then record tgid,gtgid and ti,gti with T1 and T2, respectively. At the same time, simulator ℬ will return the hash value of H1 or H2 according to opponent the query of A. For each i∈Sj, if the attribute authority aid=Ti, then B will submit gidj,aid to Challenger C according to the query of A so as to obtain the signature u,uγaid,uβaid·γaid/gidj+1 in the CL scheme. Then, ℬ takes the random value t∈ℤp∗ and runs KeyGen(gidj,Sj,SKaid,PP) as well as sends SKSj,gidjj∈m to A. In this step, ℬ should computes the following:(20)K1,i,gid=gαaid·H1gidjβaid·H2it·uβaidgid+γaid,K2,i,gid=uγaid,K3,i,gid=u,K4,i,gid=gt,K5,gid=gid.Then, the final calculation isSKSj,gidj as K1,i,gidj,K2,i,gidj,K3,i,gidj,K4,i,gidji∈Sj,K5,gidj.Forgery. in this step,A already queries from simulator ℬ the value of H1gid and H2i and obtains H1gid as gtK5,gid and H2i as gti. A assumes the unknown K3,i,gid=gt3 and K4,i,gid=gt4. Through formula (14) in Section 5.1, we could get that K2,i,gid=K3,i,gid=gt3γaid. Also through formula (14) in Section 5.1, we could get that K1,i,gid=gαaid+tK5,gidβaid·K4,i,gidti·K3,i,gidβaidK5,gid+γaid.
Then,ℬ calculates a legal signature σ according to the CL scheme, and the calculation process is as follows:(21)σ1=K1,i,gidgαaid+tK5,gidβaid·K4,i,gidti,=K3,i,gidβaidK5,gid+γaid.
Then,A picks a gid as a message and gives σ=K3,i,gid,K2,i,gid,σ1/K3,i,gidgid as the signature of the message gid according to the CL scheme.
Finally,A outputs a forgery secret key SK∗, if TraceSKS,gid,PKaid,PP∉Δ and gid∉gid1,…,gidm. As gid∉gid1,…,gidm, we know that the signature of message gid is not invoked by ℬ yet. Thus, the simulator ℬ breaks the CL scheme with the same advantage.
Since in the abovementioned game the whole system has the decryption keys, the distributions of the public parameters, and challenge ciphertext, ifA breaks the security of the CL scheme, then the simulator ℬ can selectively break Stdpum with the same advantage. Hence, if the LRSW assumption holds true, the proposed cryptosystem is against forgery, meaning that our scheme is traceable secure for the adversary.


## 5.4. Proof of Collusion Prevention

In our scheme, we use the uniquegid and construct the hash function value corresponding to gid to resist collusion attack, which has been proved to be feasible by Allison and Waters [14]. In the process of decryption, the data user needs to calculate Dx=eg,gxλ·eH1gid,gωx. For a single user with the access policy satisfaction attribute set, since ωx are the shares of secret value 0, eH1gid,gωx can be eliminated, where eH1gid,gωx=1. In case of collusion attack, two or more users will have different gid; thus, the value of H1gid will also be different; eH1gid,gωx with a secret value of 0 cannot be constructed, and thus, it cannot be eliminated. Therefore, two or more users cannot share their attribute key values to generate collusion attacks, which means this scheme is resistant to collusion attack.


## 6. Performance Evaluations

### 6.1. Theoretical Analysis

We first theoretically make a comparison of our scheme with others. The comparison of feature and performance of our work and related works is given in Tables1 and 2 .Table 1
Characteristics comparison of ABE schemes.
YB [11]JZXL [27]QLZH [28]YLLT [29]YLMH [30]ZLML [31]OursOrder groupsPrimeCompositePrimePrimePrimePrimePrimeLarge universe√√×××√√Policy updating××××√×√Traceable×√×××√√Access structureLSSSLSSSTREETREELSSSLSSSLSSSMultiauthority√×√√√√√Table 2
Performance comparison of multiauthority ABE schemes (https://github.com/monzxcv/ABE).
YB [11]SPB [32]YLMH [30]ZLML [31]OursAA’s public keyG+GT3G+GTni+1G+GT3G+GT2G+GTUser’s private key2SG4SG+GT2SG+GT4SG4SG+GTCiphertext3lG+l+1GT4lG+l+1GT2l+1G+GT5lG+l+1GT4lG+l+1GTEncryption cost3lexp+l+1e4lexp+l+1e2l+1exp+e5lexp+l+1e4lexp+l+1eDecryption cost3I4I2S+2I3I4ISecurity assumptionq-typeq-typeq-PBDHEq-typeq-typeIt can be seen from Table1 that the YB scheme [11] does not realize the traceability, nor does it have the function of dynamic access policy update; although the JZXL scheme [27] has both traceability and large attribute domains, it is constructed based on composite orders and is a single authorization which will become a bottleneck. Since the QLZH scheme [28] and the YLLT scheme [29] are based on tree access structure, they do not have the functions of large attribute domain, dynamic access strategy update, and traceability. The YLMH scheme [30] can realize the dynamic access strategy update but does not support traceability; while the ZLML scheme [31] does not have the function of dynamic access policy update. Compared with the above-mentioned related schemes, our scheme not only supports traceability, large attribute domain, and dynamic access policy update at the same time under multiple authorization agencies but also is based on the prime order bilinear group structure, which is more efficient.LetG and GT be the size of elements in G and an exponentiation in GT, respectively. Let e be a pairing and exp be the maximum amounts of time to compute an exponentiation in G. Let A be the number of ciphertext attributes, S be the size of the attribute set of a private key, and l be the output size of a function. Let I be the number of rows of the matrix when decrypting.In Table2, we show the communication cost and the computing cost comparison. Compared with other solutions, our scheme is relatively better in the process of adding multiple functions. On the one hand, for the communication cost, we can draw the following conclusions: Firstly, our scheme has the advantages in the length of the private key that our scheme supports big attribute universe. More precisely, the public key of our scheme does not increase linearly with the size of the attribute domain in an attribute authority, while that of the YLMH scheme will, and the storage occupied by our public key is smaller than that of the SPB scheme [32] and the ZLML scheme. Secondly, although the user’s private keys in the YB scheme and the YLMH scheme are relatively small, none of these schemes support traceability. In order to enhance the security of the system, the scheme in this paper supports the traceability function, and the user’s private key does not increase too much. Furthermore, compared to the YLMH scheme and the ZLML scheme, the length of the ciphertext in our scheme is optimized, which is only linearly related to the number of rows from the generator matrix. On the other hand, for the calculation cost, our scheme supports an access strategy update algorithm, while the YB scheme and the YLMH scheme do not support this function. Finally, for the decryption cost, our scheme is much smaller than that of the YLMH scheme. The decryption cost in our scheme is only related to the number of attribute organizations where the attributes belong. Although the decryption cost in our scheme is slightly higher than that of the YB scheme and the ZLML scheme, the YB scheme does not support traceability and the ZLML scheme does not support access policy update.


### 6.2. Experimental Analysis

In this section, we conduct a simulation experiment to evaluate the comparison of our scheme and the baseline algorithms (the simulation code is available in (https://github.com/monzxcv/ABE)). We select the scheme in [11] (YB scheme) and the scheme in [30] (YLMH scheme) as our baseline algorithms and run the experiments in five aspects: system initialization, key generation, data encryption, user decryption, and access strategy re-encryption. All the experiments are run on a 64-bit operating system of the Ubuntu 14.04 platform with a core 1.8 GHz processor and 4 GB RAM. We used Charm version 0.50 and Python version 3.7 as our program languages. We first convert the YB scheme, YLMH scheme, and our scheme into asymmetric bilinear mapping and use the famous supersingular symmetric elliptic curve group (“SS512”). Then, in the process of encryption and decryption, the YB scheme, YLMH scheme, and our scheme are only related to the number of access policy attributes. Therefore, in this experiment, we change the number of user attributes and calculate the time of system initialization and user key generation under the same condition to get our first comparison. In addition, we change the access policy and calculate the time of the user encryption and decryption to get another comparison. Finally, the time consumed for updating ciphertext under the same condition is calculated. The experimental attributes are constructed with AN,N∈1,…,50. The strategy set is selected (A1∧A2∧⋯∧AN). We increase the number of attributes from 5 to 50, and there are ten different access strategies. In order to ensure the accuracy of the conclusion, every experiment is run 15 times.The system initialization cost and the average time cost of user private key generation are shown in Figures2 and 3 when the number of attributes varies from 5 to 50. We fix the number of AAs in 8, and we also fix the number of attributes in the access policy in 8. Since both our scheme and YB scheme support large attribute domains, the system initialization process has nothing to do with the number of attributes, as is verified in Figure 2. It can be seen that as the number of attributes increases, the cost of the YLMH scheme increases, and the cost of our scheme still keeps a constant value, so the larger the number of attributes, the more the advantage in our scheme. It can be seen from Figure 3 that the cost of the user private key generation time in all the three schemes increases linearly with the increase of attributes. This is because each attribute in the user’s private key must be calculated accordingly. Finally, the generation time cost is not much different from that of the YB scheme and the YLMH scheme.Figure 2
Comparison of the system setup process.Figure 3
Comparison of the KeyGen process.Figure4 shows the average time cost of the encryption and decryption process when the number of attributes used in the access policy varies from 5 to 50. We fix the number of AAs in 8, and the number of attributes for each user is also fixed in 8. It can be seen from Figure 4 that the average execution time of the key generation and encryption/decryption process of the proposed scheme is equivalent to that of the YB scheme, while our scheme is more practical than the YB scheme, such as supporting traceability and dynamic access policy update. Although the YLMH scheme’s encryption cost is the smallest, its decryption cost is the largest among the three schemes and is related to the number of attributes the user has. If the user’s attributes increase, the decryption time cost of the YLMH scheme will be higher.Figure 4
Comparison of encryption algorithms and decryption algorithms.
(a)(b)Figure5 shows the algorithms’ average computing time in the YB scheme, YLMH scheme, and our scheme in policy update. Since the YB scheme does not support dynamic strategy updates, we use the traditional update method. There are three modes for updating of dynamic strategy in the YLMH scheme and our scheme. We use mode 3 (which has the highest cost) for comparison. In addition, the number of AAs is fixed in 8, and the number of attributes for each user is also fixed in 8. We vary the number of attributes by 5, 10, and 15. As it can be seen from Figure 5, our scheme and YLMH scheme can dynamically update the strategy. Thus, the time cost is less than that of the YB scheme. Although our scheme costs slightly more than the YLMH scheme, our scheme supports traceability, which is considered to be more practical.Figure 5
Comparison of policy updating.


## 6.1. Theoretical Analysis

We first theoretically make a comparison of our scheme with others. The comparison of feature and performance of our work and related works is given in Tables1 and 2 .Table 1
Characteristics comparison of ABE schemes.
YB [11]JZXL [27]QLZH [28]YLLT [29]YLMH [30]ZLML [31]OursOrder groupsPrimeCompositePrimePrimePrimePrimePrimeLarge universe√√×××√√Policy updating××××√×√Traceable×√×××√√Access structureLSSSLSSSTREETREELSSSLSSSLSSSMultiauthority√×√√√√√Table 2
Performance comparison of multiauthority ABE schemes (https://github.com/monzxcv/ABE).
YB [11]SPB [32]YLMH [30]ZLML [31]OursAA’s public keyG+GT3G+GTni+1G+GT3G+GT2G+GTUser’s private key2SG4SG+GT2SG+GT4SG4SG+GTCiphertext3lG+l+1GT4lG+l+1GT2l+1G+GT5lG+l+1GT4lG+l+1GTEncryption cost3lexp+l+1e4lexp+l+1e2l+1exp+e5lexp+l+1e4lexp+l+1eDecryption cost3I4I2S+2I3I4ISecurity assumptionq-typeq-typeq-PBDHEq-typeq-typeIt can be seen from Table1 that the YB scheme [11] does not realize the traceability, nor does it have the function of dynamic access policy update; although the JZXL scheme [27] has both traceability and large attribute domains, it is constructed based on composite orders and is a single authorization which will become a bottleneck. Since the QLZH scheme [28] and the YLLT scheme [29] are based on tree access structure, they do not have the functions of large attribute domain, dynamic access strategy update, and traceability. The YLMH scheme [30] can realize the dynamic access strategy update but does not support traceability; while the ZLML scheme [31] does not have the function of dynamic access policy update. Compared with the above-mentioned related schemes, our scheme not only supports traceability, large attribute domain, and dynamic access policy update at the same time under multiple authorization agencies but also is based on the prime order bilinear group structure, which is more efficient.LetG and GT be the size of elements in G and an exponentiation in GT, respectively. Let e be a pairing and exp be the maximum amounts of time to compute an exponentiation in G. Let A be the number of ciphertext attributes, S be the size of the attribute set of a private key, and l be the output size of a function. Let I be the number of rows of the matrix when decrypting.In Table2, we show the communication cost and the computing cost comparison. Compared with other solutions, our scheme is relatively better in the process of adding multiple functions. On the one hand, for the communication cost, we can draw the following conclusions: Firstly, our scheme has the advantages in the length of the private key that our scheme supports big attribute universe. More precisely, the public key of our scheme does not increase linearly with the size of the attribute domain in an attribute authority, while that of the YLMH scheme will, and the storage occupied by our public key is smaller than that of the SPB scheme [32] and the ZLML scheme. Secondly, although the user’s private keys in the YB scheme and the YLMH scheme are relatively small, none of these schemes support traceability. In order to enhance the security of the system, the scheme in this paper supports the traceability function, and the user’s private key does not increase too much. Furthermore, compared to the YLMH scheme and the ZLML scheme, the length of the ciphertext in our scheme is optimized, which is only linearly related to the number of rows from the generator matrix. On the other hand, for the calculation cost, our scheme supports an access strategy update algorithm, while the YB scheme and the YLMH scheme do not support this function. Finally, for the decryption cost, our scheme is much smaller than that of the YLMH scheme. The decryption cost in our scheme is only related to the number of attribute organizations where the attributes belong. Although the decryption cost in our scheme is slightly higher than that of the YB scheme and the ZLML scheme, the YB scheme does not support traceability and the ZLML scheme does not support access policy update.


## 6.2. Experimental Analysis

In this section, we conduct a simulation experiment to evaluate the comparison of our scheme and the baseline algorithms (the simulation code is available in (https://github.com/monzxcv/ABE)). We select the scheme in [11] (YB scheme) and the scheme in [30] (YLMH scheme) as our baseline algorithms and run the experiments in five aspects: system initialization, key generation, data encryption, user decryption, and access strategy re-encryption. All the experiments are run on a 64-bit operating system of the Ubuntu 14.04 platform with a core 1.8 GHz processor and 4 GB RAM. We used Charm version 0.50 and Python version 3.7 as our program languages. We first convert the YB scheme, YLMH scheme, and our scheme into asymmetric bilinear mapping and use the famous supersingular symmetric elliptic curve group (“SS512”). Then, in the process of encryption and decryption, the YB scheme, YLMH scheme, and our scheme are only related to the number of access policy attributes. Therefore, in this experiment, we change the number of user attributes and calculate the time of system initialization and user key generation under the same condition to get our first comparison. In addition, we change the access policy and calculate the time of the user encryption and decryption to get another comparison. Finally, the time consumed for updating ciphertext under the same condition is calculated. The experimental attributes are constructed with AN,N∈1,…,50. The strategy set is selected (A1∧A2∧⋯∧AN). We increase the number of attributes from 5 to 50, and there are ten different access strategies. In order to ensure the accuracy of the conclusion, every experiment is run 15 times.The system initialization cost and the average time cost of user private key generation are shown in Figures2 and 3 when the number of attributes varies from 5 to 50. We fix the number of AAs in 8, and we also fix the number of attributes in the access policy in 8. Since both our scheme and YB scheme support large attribute domains, the system initialization process has nothing to do with the number of attributes, as is verified in Figure 2. It can be seen that as the number of attributes increases, the cost of the YLMH scheme increases, and the cost of our scheme still keeps a constant value, so the larger the number of attributes, the more the advantage in our scheme. It can be seen from Figure 3 that the cost of the user private key generation time in all the three schemes increases linearly with the increase of attributes. This is because each attribute in the user’s private key must be calculated accordingly. Finally, the generation time cost is not much different from that of the YB scheme and the YLMH scheme.Figure 2
Comparison of the system setup process.Figure 3
Comparison of the KeyGen process.Figure4 shows the average time cost of the encryption and decryption process when the number of attributes used in the access policy varies from 5 to 50. We fix the number of AAs in 8, and the number of attributes for each user is also fixed in 8. It can be seen from Figure 4 that the average execution time of the key generation and encryption/decryption process of the proposed scheme is equivalent to that of the YB scheme, while our scheme is more practical than the YB scheme, such as supporting traceability and dynamic access policy update. Although the YLMH scheme’s encryption cost is the smallest, its decryption cost is the largest among the three schemes and is related to the number of attributes the user has. If the user’s attributes increase, the decryption time cost of the YLMH scheme will be higher.Figure 4
Comparison of encryption algorithms and decryption algorithms.
(a)(b)Figure5 shows the algorithms’ average computing time in the YB scheme, YLMH scheme, and our scheme in policy update. Since the YB scheme does not support dynamic strategy updates, we use the traditional update method. There are three modes for updating of dynamic strategy in the YLMH scheme and our scheme. We use mode 3 (which has the highest cost) for comparison. In addition, the number of AAs is fixed in 8, and the number of attributes for each user is also fixed in 8. We vary the number of attributes by 5, 10, and 15. As it can be seen from Figure 5, our scheme and YLMH scheme can dynamically update the strategy. Thus, the time cost is less than that of the YB scheme. Although our scheme costs slightly more than the YLMH scheme, our scheme supports traceability, which is considered to be more practical.Figure 5
Comparison of policy updating.


## 7. Conclusions and Future Work

Regarding the three problems in the CP-ABE scheme of multiauthority, traceability, and the flexibility in changing the access policy, we propose a scheme to achieve good solutions. Our scheme supports multiple authorities, white box traceability, large attribute domains, access policy updates, and high expressiveness. Then, we prove that our scheme is static secure and traceable secure based on the state-of-the-art security models. By supporting the traceability, there is no need to maintain the authorized institution’s identity table; thus, our solution is more practical. The experimental results indicate that our scheme has efficient performance while enjoying the abovementioned features. In future work, we plan to conduct a study on computational outsourcing and hidden access strategies for CP-ABE.



---

*Source: 6661450-2021-02-26.xml*