# A Traceable and Revocable Multiauthority Attribute-Based Encryption Scheme with Fast Access

Authors: Kai Zhang; Yanping Li; Yun Song; Laifeng Lu; Tao Zhang; Qi Jiang
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Multiauthority ciphertext-policy attribute-based encryption (MA-CP-ABE) is a promising technique for secure data sharing in cloud storage. As multiple users with same attributes have same decryption privilege in MA-CP-ABE, the identity of the decryption key owner cannot be accurately traced by the exposed decryption key. This will lead to the key abuse problem, for example, the malicious users may sell their decryption keys to others. In this paper, we first present a traceable MA-CP-ABE scheme supporting fast access and malicious users’ accountability. Then, we prove that the proposed scheme is adaptively secure under the symmetric external Diffie–Hellman assumption and fully traceable under theq-Strong Diffie–Hellman assumption. Finally, we design a traceable and revocable MA-CP-ABE system for secure and efficient cloud storage from the proposed scheme. When a malicious user leaks his decryption key, our proposed system can not only confirm his identity but also revoke his decryption privilege. Extensive efficiency analysis results indicate that our system requires only constant number of pairing operations for ciphertext data access.


---

## Body

## 1. Introduction

In recent years, the rise of the Internet of things [1] promotes the application and development of sensor technology [2–4]. As an important sensing paradigm, mobile crowdsensing [5] has been widely used in various industries due to its large coverage area and low deployment cost characteristics. One of the most significant services for mobile crowdsensing is cloud storage [6], which supports large-scale data sharing. In cloud storage, the individuals or organizations often need to share the sensitive data with the users whose attributes satisfy a specific policy. For example, a patient wants to share his medical data with nurses and doctors in neurosurgery, but he does not know the identities of the nurses and doctors. Security is a very important issue [7, 8] in the Internet, and a potential solution for achieving data security is to encrypt the sensitive data before sharing it by the cloud. Unfortunately, the traditional public key encryption [9] requires the data owner to know the receiver’s exact identity, so it is not suitable for the above scenario.To address this issue, ciphertext-policy attribute-based encryption (CP-ABE) [10, 11] was introduced as an expansion of the traditional public key encryption. In CP-ABE, the user’s secret key is associated with his attributes, and the ciphertext is associated with an access policy, which is defined in the form of Boolean formula over a set of attributes; the user can decrypt the ciphertext only when his attributes satisfy the access policy. By using CP-ABE in the above example, the patient can encrypt the medical data with the access policy (“Doctor” AND “Neurosurgery”) OR (“Nurse” AND “Neurosurgery”) and upload the ciphertext to the cloud; then, only nurses and doctors in neurosurgery can access the medical data.In the typical CP-ABE system, a single central authority should manage all attributes and generate all users’ decryption keys. However, many scenarios require multiple authorities to manage different attribute domains. For instance, a patient wants to share his medical document with the users with the attribute “Doctor” that is issued by a hospital and attribute “Researcher” that is issued by a medical research institute. To solve this problem, Chase [12] introduced the multiauthority attribute-based encryption (MA-ABE), in which different authorities manage different attribute sets and each authority issues secret keys only for the attributes it manages. However, before the MA-ABE being applied in practice, there exist the following issues that need to be solved.The standard MA-ABE suffers the decryption key abuse problem. In multiauthority ciphertext-policy attribute-based encryption (MA-CP-ABE), the decryption privilege is only based on the user’s attributes and the ciphertext does not contain the user’s identity information. Hence, a ciphertext can be decrypted by multiple users with same attributes. For example, Alice and Bob have the attributes {“Researcher,” “Neurosurgery”}; then, both of them can decrypt the ciphertext associated with the access policy (“Doctor” AND “Neurosurgery”) OR (“Researcher” AND “Neurosurgery”). In the MA-CP-ABE system, if a malicious user who has same attributes with others sells his decryption key on the Internet, how to identify the malicious user?Another major issue in MA-ABE is malicious user revocation. In the MA-CP-ABE system, the decryption keys may be compromised and the corresponding malicious users should be removed from the system. Hence, the user revocation mechanism should be designed for the MA-CP-ABE system. The user revocation mechanism was divided into direct revocation and indirect revocation. In direct revocation, the data owner encrypts the data by a specified revocation list, and the revoked users who in this list cannot decrypt the corresponding ciphertext. Unfortunately, the direct revocation mechanism requires each data owner to keep a revocation user identity list and breaks the user anonymity in the ABE system. In indirect revocation, the authorities help the nonrevoked users to update their decryption keys periodically, so the revoked users cannot decrypt the new ciphertexts. In this paper, we focus on the indirect user revocation issue in the MA-CP-ABE system.One efficiency drawback for MA-ABE is the significant cost of data access. In the MA-CP-ABE system, the number of resource-consuming pairing operations required to decrypt a ciphertext grows linearly with the number of attributes used for decryption, which makes the data access too expensive. This drawback hinders the large-scale application of the MA-CP-ABE system in lightweight devices. For example, consider a medical cloud system based on MA-CP-ABE, the patients encrypt the data and upload the ciphertexts in cloud, and the doctor may need to real-time access the medical data by a smartphone. Due to the expensive access cost, the traditional MA-CP-ABE system is obviously unsuitable in this scenario.


### 1.1. Our Contributions

Seeking to address the above issues, we first give the formal definition and security model for traceable MA-CP-ABE (T-MA-CP-ABE) scheme and propose a concrete construction of T-MA-CP-ABE on prime order bilinear groups. Then, we prove the construction is adaptively secure under the symmetric external Diffie–Hellman assumption and fully traceable under theq-Strong Diffie–Hellman assumption in the random oracle model. Based on the T-MA-CP-ABE construction, we further present a traceable and revocable MA-CP-ABE (TR-MA-CP-ABE) system for secure cloud storage. To the best of our knowledge, this is the first practical MA-ABE system that simultaneously supports traceability, revocation, and fast access. The major features of our TR-MA-CP-ABE system are outlined as follows:(1)
Multiauthority. There exists a central authority (CA) and multiple attribute authorities in our TR-MA-CP-ABE system. Each attribute authority (AA) is responsible for generating the user secret keys for the attributes under its control, and CA is responsible for tracing and revoking the malicious users. Unlike prior MA-ABE schemes, neither CA nor AA can independently generate user decryption keys in our system, even for just one attribute. In addition, the access policies can be expressed as any monotone access structures, which make our system more practical.(2)
Traceability. Our TR-MA-CP-ABE system supports white-box traceability (traceability can be divided into white-box traceability and black-box traceability. White-box traceability can catch the malicious user who leaks his decryption keys to others, while black-box traceability can catch the malicious user who leaks a decryption black-box). In our system, CA generates tracing information and user secret keys for the identity. If a malicious user leaks his decryption key to others, then CA can trace the malicious user identity from the corresponding decryption key. By adopting a full signature technique, our system does not require any identity table for tracing, which significantly reduces the storage overhead for CA.(3)
Revocation. Our TR-MA-CP-ABE system supports indirect user revocation. If a malicious user was caught by CA, then CA adds his identity into a revocation list, and AAs only periodically update the attribute-based secret keys for the users whose identities do not belong to the revocation list. Hence, the malicious users cannot obtain the new decryption keys and access the new ciphertext data created in the current time period.(4)
Fast access. In our TR-MA-CP-ABE system, the number of pairings for decrypt a ciphertext is only 6, rather than increases linearly with the number of attributes used during decryption. Furthermore, our decryption operation is run on prime order bilinear groups, which makes access speed significantly faster. The efficiency comparison shows that the data access in our system is more efficient than that in other related works.Table1 compares the specific features of our TR-MA-CP-ABE system with the existing ABE schemes [13–16] that achieve multiauthority and traceability simultaneously.Table 1
Features comparison with other related works.
AS2MAS3ZST4POGFA5R[13]××✓✓××[14]✓✓×××✓[15]✓✓✓×××[16]×✓✓✓××This paper✓✓✓✓✓✓AS represents adaptively secure, MAS represents supporting any monotone access structures, ZST represents zero storage cost for tracing, POG represents constructed in prime order groups, FA represents constant pairing operations for data access, andR represents revocation. 2The scheme [13] achieves selectively secure and the scheme [16] only achieves statically secure. 3In [13], their scheme only supports “AND gates with wildcard.” 4In [14], the number of identity tables for tracing is equal to the number of central authorities in the scheme. 5In [13–16], the number of pairing operations for decryption grows linearly with the number of attributes used for decryption.


### 1.2. Related Works

Chase [12] introduced the notion of MA-ABE and gave the first concrete construction of MA-ABE. As CA is assumed to be able to decrypt every ciphertext in [12], Chase and Chow [17] proposed a MA-ABE scheme without any CA, which was limited to expressing a strict “AND” policy over a predetermined set of authorities. Later, Lewko and Waters [18] presented an adaptively secure MA-ABE scheme where a policy could be expressed as any monotonic Boolean formula. Based on [18], Cui and Deng [19] presented a revocable MA-ABE that achieves attribute revocation. Zhang et al. [20] presented a shorter MA-ABE where a ciphertext can be decrypted with a constant number of pairing operations. Wang et al. [21] constructed a MA-ABE scheme from the LWE assumption. More recently, Xiong et al. [22] presented a revocable MA-ABE with outsourced decryption. However, these schemes did not consider the trace problem.Hinek et al. [23] proposed the first traceable CP-ABE, but their scheme only supports “AND gates with wildcard.” To improve the expression ability, Liu et al. [24] presented the first traceable CP-ABE that supports monotonic access structures. Later, Wang et al [25] presented a traceable CP-ABE that can catch the malicious user who leaks a black-box decryption equipment. Ning et al. [26] presented a traceable and revocable CP-ABE that supports both accountable authority and public auditing. Liu and Wong [27] proposed a traceable and revocable CP-ABE for large universe. Xu [28] constructed a traceable CP-ABE with short decryption key. Recently, Han et al. [29] presented a traceable and revocable CP-ABE with hidden policy. Unfortunately, the above schemes can only apply to the single-authority setting.To address the key abuse problem in MA-ABE, Li et al. [13] presented a traceable MA-CP-ABE with limited access policy and security. Later, Zhou et al. [14] proposed a revocable and traceable MA-CP-ABE that achieves high expressiveness and full security. However, there exists multiple CAs in their scheme, and each CA needs to maintain a tracing identity table. Yu et al. [15] constructed a traceable MA-CP-ABE without any identity table and proved it is adaptively secure in composite order groups. Recently, Zhang et al. [16] presented a more efficient traceable MA-CP-ABE in prime order groups. Unfortunately, their scheme only achieves statically secure and does not support user revocation. In addition, the common efficiency drawback of these schemes is that the number of pairing operations required to decrypt a ciphertext increases linearly with the number of attributes satisfying the access policy, which presents significant challenges for the users who access data by mobile devices.


### 1.3. Organization

Section2 introduces the relevant preliminaries, which includes the access structure, bilinear group, and complexity assumptions. Section 3 gives the system architecture, algorithm definition, and security model of TR-MA-CP-ABE. Section 4 presents the detailed constructions and formal security analysis of T-MA-CP-ABE scheme. Section 5 designs a TR-MA-CP-ABE system and compares its efficiency with other related works. Section 6 concludes the whole paper.


## 1.1. Our Contributions

Seeking to address the above issues, we first give the formal definition and security model for traceable MA-CP-ABE (T-MA-CP-ABE) scheme and propose a concrete construction of T-MA-CP-ABE on prime order bilinear groups. Then, we prove the construction is adaptively secure under the symmetric external Diffie–Hellman assumption and fully traceable under theq-Strong Diffie–Hellman assumption in the random oracle model. Based on the T-MA-CP-ABE construction, we further present a traceable and revocable MA-CP-ABE (TR-MA-CP-ABE) system for secure cloud storage. To the best of our knowledge, this is the first practical MA-ABE system that simultaneously supports traceability, revocation, and fast access. The major features of our TR-MA-CP-ABE system are outlined as follows:(1)
Multiauthority. There exists a central authority (CA) and multiple attribute authorities in our TR-MA-CP-ABE system. Each attribute authority (AA) is responsible for generating the user secret keys for the attributes under its control, and CA is responsible for tracing and revoking the malicious users. Unlike prior MA-ABE schemes, neither CA nor AA can independently generate user decryption keys in our system, even for just one attribute. In addition, the access policies can be expressed as any monotone access structures, which make our system more practical.(2)
Traceability. Our TR-MA-CP-ABE system supports white-box traceability (traceability can be divided into white-box traceability and black-box traceability. White-box traceability can catch the malicious user who leaks his decryption keys to others, while black-box traceability can catch the malicious user who leaks a decryption black-box). In our system, CA generates tracing information and user secret keys for the identity. If a malicious user leaks his decryption key to others, then CA can trace the malicious user identity from the corresponding decryption key. By adopting a full signature technique, our system does not require any identity table for tracing, which significantly reduces the storage overhead for CA.(3)
Revocation. Our TR-MA-CP-ABE system supports indirect user revocation. If a malicious user was caught by CA, then CA adds his identity into a revocation list, and AAs only periodically update the attribute-based secret keys for the users whose identities do not belong to the revocation list. Hence, the malicious users cannot obtain the new decryption keys and access the new ciphertext data created in the current time period.(4)
Fast access. In our TR-MA-CP-ABE system, the number of pairings for decrypt a ciphertext is only 6, rather than increases linearly with the number of attributes used during decryption. Furthermore, our decryption operation is run on prime order bilinear groups, which makes access speed significantly faster. The efficiency comparison shows that the data access in our system is more efficient than that in other related works.Table1 compares the specific features of our TR-MA-CP-ABE system with the existing ABE schemes [13–16] that achieve multiauthority and traceability simultaneously.Table 1
Features comparison with other related works.
AS2MAS3ZST4POGFA5R[13]××✓✓××[14]✓✓×××✓[15]✓✓✓×××[16]×✓✓✓××This paper✓✓✓✓✓✓AS represents adaptively secure, MAS represents supporting any monotone access structures, ZST represents zero storage cost for tracing, POG represents constructed in prime order groups, FA represents constant pairing operations for data access, andR represents revocation. 2The scheme [13] achieves selectively secure and the scheme [16] only achieves statically secure. 3In [13], their scheme only supports “AND gates with wildcard.” 4In [14], the number of identity tables for tracing is equal to the number of central authorities in the scheme. 5In [13–16], the number of pairing operations for decryption grows linearly with the number of attributes used for decryption.


## 1.2. Related Works

Chase [12] introduced the notion of MA-ABE and gave the first concrete construction of MA-ABE. As CA is assumed to be able to decrypt every ciphertext in [12], Chase and Chow [17] proposed a MA-ABE scheme without any CA, which was limited to expressing a strict “AND” policy over a predetermined set of authorities. Later, Lewko and Waters [18] presented an adaptively secure MA-ABE scheme where a policy could be expressed as any monotonic Boolean formula. Based on [18], Cui and Deng [19] presented a revocable MA-ABE that achieves attribute revocation. Zhang et al. [20] presented a shorter MA-ABE where a ciphertext can be decrypted with a constant number of pairing operations. Wang et al. [21] constructed a MA-ABE scheme from the LWE assumption. More recently, Xiong et al. [22] presented a revocable MA-ABE with outsourced decryption. However, these schemes did not consider the trace problem.Hinek et al. [23] proposed the first traceable CP-ABE, but their scheme only supports “AND gates with wildcard.” To improve the expression ability, Liu et al. [24] presented the first traceable CP-ABE that supports monotonic access structures. Later, Wang et al [25] presented a traceable CP-ABE that can catch the malicious user who leaks a black-box decryption equipment. Ning et al. [26] presented a traceable and revocable CP-ABE that supports both accountable authority and public auditing. Liu and Wong [27] proposed a traceable and revocable CP-ABE for large universe. Xu [28] constructed a traceable CP-ABE with short decryption key. Recently, Han et al. [29] presented a traceable and revocable CP-ABE with hidden policy. Unfortunately, the above schemes can only apply to the single-authority setting.To address the key abuse problem in MA-ABE, Li et al. [13] presented a traceable MA-CP-ABE with limited access policy and security. Later, Zhou et al. [14] proposed a revocable and traceable MA-CP-ABE that achieves high expressiveness and full security. However, there exists multiple CAs in their scheme, and each CA needs to maintain a tracing identity table. Yu et al. [15] constructed a traceable MA-CP-ABE without any identity table and proved it is adaptively secure in composite order groups. Recently, Zhang et al. [16] presented a more efficient traceable MA-CP-ABE in prime order groups. Unfortunately, their scheme only achieves statically secure and does not support user revocation. In addition, the common efficiency drawback of these schemes is that the number of pairing operations required to decrypt a ciphertext increases linearly with the number of attributes satisfying the access policy, which presents significant challenges for the users who access data by mobile devices.


## 1.3. Organization

Section2 introduces the relevant preliminaries, which includes the access structure, bilinear group, and complexity assumptions. Section 3 gives the system architecture, algorithm definition, and security model of TR-MA-CP-ABE. Section 4 presents the detailed constructions and formal security analysis of T-MA-CP-ABE scheme. Section 5 designs a TR-MA-CP-ABE system and compares its efficiency with other related works. Section 6 concludes the whole paper.


## 2. Preliminaries

### 2.1. Notations

For convenience, we define some notations that will be used in this paper. For a finite set S, we denote bys←SR, the fact that s is chosen uniformly at random from S. Let ℤp be a set 0,1,2,…,p−1, where p is a prime. Let ℤpn and ℤpl×n denote the set of all n-dimensional vectors and l×n matrices (l rows and n columns) in ℤp, respectively. We denote a matrix by a bold letter. For a matrix A∈ℤpl×n, let A⊤ be the transposition of A, and aij∈ℤp be the i,jth (the ith row and jth column) element of A. For group G, g∈G, and matrix A∈ℤpl×n, we use gA to denote the l×n matrix, in which its i,jth element is gaij. For matrix B∈ℤpn×m, we denote gAB=gAB∈Gl×m. For v⟶=v1,v2,…,vn∈ℤpn, we denote gv⟶=gv1,gv2,…,gvn∈Gn. For two vectors v⟶=v1,v2,…,vnandω⟶=ω1,ω2,…,ωn∈ℤpn, we denote the inner product of v⟶ and ω⟶ by v⟶,ω⟶=∑i=1i=nviωi. We can also denote the above inner product notation for row and column vectors as follows.(1)v⟶,ω⟶=v⟶ω⟶⊤,ifv⟶andω⟶are both row vectors,v⟶ω⟶,ifv⟶is a row vector andω⟶is a column vector,v⟶⊤ω⟶⊤,ifv⟶is a column vector andω⟶is a row vector,v⟶⊤ω⟶,ifv⟶andω⟶are both column vectors.Note thatv⟶,ω⟶=v⟶,ω⟶⊤ and v⟶⊤ω⟶⊤=v⟶⊤ω⟶⊤⊤=ω⟶v⟶.


### 2.2. Access Structures

Definition 1 (Access structure [30]).
LetU be the attributes universe. An access structure A is a collection of nonempty subsets of U, i.e., A⊆2U∖∅. If for ∀B,C, we have B∈A,B⊆C⇒C∈A; then, we say A is monotone. The sets in A are called authorized sets, while the sets not in A are called unauthorized sets.Definition 2 (Linear secret-sharing schemes (LSSS) [30]).
A secret-sharing schemeΠ over the attributes universe U is called linear over ℤp if(1)
The shares for each attribute form a vector overℤp(2)
There exists a matrixA∈ℤpl×n and function ρ:1,2,…,l⟶U satisfy the following: let the column vector v⟶=s,r2,…,rn∈ℤp1×n, where s∈ℤp is the secret to be shared, and r2,…,rn←Rℤp; then, Av⟶⊤ is equal to the vector of l shares of the secret s according to Π. The share Av⟶⊤i belongs to attribute ρi.
LetΠ be an LSSS for the access structure A and A,ρ be the access policy for A. According to [30], LSSS enjoys the linear reconstruction as follows. Let S∈A be an authorized set, and let I=i:ρi∈S⊂1,2,…,l. Then, there exist constants ωi∈ℤpi∈I such that ∑i∈IciAi⟶=1,0,…,0∈ℤp1×n, where Ai⟶ is the row i of matrix A.


### 2.3. Bilinear Groups and Assumptions

LetG be an asymmetric bilinear group generator that takes as input a security parameter λ and outputs a tuple G=p,G1,G2,GT,g1,g2,e, where G1,G2, and GT are the cyclic groups of prime order p, g1 (respectively, g2) is a generator of G1 (respectively, G2), and e:G1×G2⟶GT is an efficiently computable bilinear map such that(1)
Bilinear:∀g∈G1,h∈G2,a,b∈ℤp,ega,hb=eg,hab(2)
Nondegenerate:eg1,g2≠1Forg∈G1,h∈G2,v⟶,ω⟶∈ℤpn, we denote egv⟶,hω⟶=∏i=1negvi,hωi=eg,hv⟶,ω⟶∈GT.Definition 3 (SXDH, Symmetric External Diffie–Hellman assumption [31]).
The adversaryA’s advantage in SXDH assumption is defined as(2)AdvASXDHλ=PrAD,T0,i=0−PrAD,T1,i=0,where G=p,G1,G2,GT,g1,g2,e←Gλ, a,b,c←Rℤp, i∈1,2, D=G,gia,gib, T0,i=giab,andT1,i=giab+c. We say the SXDH assumption holds if for all polynomial time algorithm adversaries A and both i∈1,2, AdvASXDHλ is negligible in λ.Definition 4 (q-SDH, q-Strong Diffie–Hellman assumption [32]).
The adversaryA’s advantage in q-SDH assumption is defined as(3)AdvAq−SDHλ=PrAg1,g1x,g2,g2x,g2x2,…,g2xq=d,g21/x+d,where G=p,G1,G2,GT,g1,g2,e←Gλ, x←Rℤp, and d∈ℤp\−x. We say the q-SDH assumption holds if for all polynomial time algorithm adversaries A, AdvAq−SDHλ is negligible in λ.
Note that compared with theq-SDH assumption in [32], g1 and g2 have exchanged places here. However, this will not affect the security of full signature scheme [32], that is, strong existential unforgeability under an adaptive chosen message attack based on q-SDH assumption because we will also exchange the places of g1 and g2 in the full signature scheme. The modified full signature scheme (BB scheme) is briefly described as follows:(i)
Setupλ. Run Gλ to obtain p,G1,G2,GT,g1,g2,e. Pick a,b⟵Rℤp, set the public key PK=p,G1,G2,GT,g1,g2,e,u=g1a,v=g1b,z=eg1,g2, and secret key SK=g2,a,b.(ii)
SignSK,M. Given a message M and SK, pick r←Rℤp\−a+M/b, compute σ=g21/a+M+br, and set the signature as σ,r(iii)
VerifyPK,M,σ,r. If eug1Mvr,σ=z, it outputs 1 meaning that the signature σ,r is valid. Otherwise, it outputs 0 meaning that the signature σ,r is invalid.


## 2.1. Notations

For convenience, we define some notations that will be used in this paper. For a finite set S, we denote bys←SR, the fact that s is chosen uniformly at random from S. Let ℤp be a set 0,1,2,…,p−1, where p is a prime. Let ℤpn and ℤpl×n denote the set of all n-dimensional vectors and l×n matrices (l rows and n columns) in ℤp, respectively. We denote a matrix by a bold letter. For a matrix A∈ℤpl×n, let A⊤ be the transposition of A, and aij∈ℤp be the i,jth (the ith row and jth column) element of A. For group G, g∈G, and matrix A∈ℤpl×n, we use gA to denote the l×n matrix, in which its i,jth element is gaij. For matrix B∈ℤpn×m, we denote gAB=gAB∈Gl×m. For v⟶=v1,v2,…,vn∈ℤpn, we denote gv⟶=gv1,gv2,…,gvn∈Gn. For two vectors v⟶=v1,v2,…,vnandω⟶=ω1,ω2,…,ωn∈ℤpn, we denote the inner product of v⟶ and ω⟶ by v⟶,ω⟶=∑i=1i=nviωi. We can also denote the above inner product notation for row and column vectors as follows.(1)v⟶,ω⟶=v⟶ω⟶⊤,ifv⟶andω⟶are both row vectors,v⟶ω⟶,ifv⟶is a row vector andω⟶is a column vector,v⟶⊤ω⟶⊤,ifv⟶is a column vector andω⟶is a row vector,v⟶⊤ω⟶,ifv⟶andω⟶are both column vectors.Note thatv⟶,ω⟶=v⟶,ω⟶⊤ and v⟶⊤ω⟶⊤=v⟶⊤ω⟶⊤⊤=ω⟶v⟶.


## 2.2. Access Structures

Definition 1 (Access structure [30]).
LetU be the attributes universe. An access structure A is a collection of nonempty subsets of U, i.e., A⊆2U∖∅. If for ∀B,C, we have B∈A,B⊆C⇒C∈A; then, we say A is monotone. The sets in A are called authorized sets, while the sets not in A are called unauthorized sets.Definition 2 (Linear secret-sharing schemes (LSSS) [30]).
A secret-sharing schemeΠ over the attributes universe U is called linear over ℤp if(1)
The shares for each attribute form a vector overℤp(2)
There exists a matrixA∈ℤpl×n and function ρ:1,2,…,l⟶U satisfy the following: let the column vector v⟶=s,r2,…,rn∈ℤp1×n, where s∈ℤp is the secret to be shared, and r2,…,rn←Rℤp; then, Av⟶⊤ is equal to the vector of l shares of the secret s according to Π. The share Av⟶⊤i belongs to attribute ρi.
LetΠ be an LSSS for the access structure A and A,ρ be the access policy for A. According to [30], LSSS enjoys the linear reconstruction as follows. Let S∈A be an authorized set, and let I=i:ρi∈S⊂1,2,…,l. Then, there exist constants ωi∈ℤpi∈I such that ∑i∈IciAi⟶=1,0,…,0∈ℤp1×n, where Ai⟶ is the row i of matrix A.


## 2.3. Bilinear Groups and Assumptions

LetG be an asymmetric bilinear group generator that takes as input a security parameter λ and outputs a tuple G=p,G1,G2,GT,g1,g2,e, where G1,G2, and GT are the cyclic groups of prime order p, g1 (respectively, g2) is a generator of G1 (respectively, G2), and e:G1×G2⟶GT is an efficiently computable bilinear map such that(1)
Bilinear:∀g∈G1,h∈G2,a,b∈ℤp,ega,hb=eg,hab(2)
Nondegenerate:eg1,g2≠1Forg∈G1,h∈G2,v⟶,ω⟶∈ℤpn, we denote egv⟶,hω⟶=∏i=1negvi,hωi=eg,hv⟶,ω⟶∈GT.Definition 3 (SXDH, Symmetric External Diffie–Hellman assumption [31]).
The adversaryA’s advantage in SXDH assumption is defined as(2)AdvASXDHλ=PrAD,T0,i=0−PrAD,T1,i=0,where G=p,G1,G2,GT,g1,g2,e←Gλ, a,b,c←Rℤp, i∈1,2, D=G,gia,gib, T0,i=giab,andT1,i=giab+c. We say the SXDH assumption holds if for all polynomial time algorithm adversaries A and both i∈1,2, AdvASXDHλ is negligible in λ.Definition 4 (q-SDH, q-Strong Diffie–Hellman assumption [32]).
The adversaryA’s advantage in q-SDH assumption is defined as(3)AdvAq−SDHλ=PrAg1,g1x,g2,g2x,g2x2,…,g2xq=d,g21/x+d,where G=p,G1,G2,GT,g1,g2,e←Gλ, x←Rℤp, and d∈ℤp\−x. We say the q-SDH assumption holds if for all polynomial time algorithm adversaries A, AdvAq−SDHλ is negligible in λ.
Note that compared with theq-SDH assumption in [32], g1 and g2 have exchanged places here. However, this will not affect the security of full signature scheme [32], that is, strong existential unforgeability under an adaptive chosen message attack based on q-SDH assumption because we will also exchange the places of g1 and g2 in the full signature scheme. The modified full signature scheme (BB scheme) is briefly described as follows:(i)
Setupλ. Run Gλ to obtain p,G1,G2,GT,g1,g2,e. Pick a,b⟵Rℤp, set the public key PK=p,G1,G2,GT,g1,g2,e,u=g1a,v=g1b,z=eg1,g2, and secret key SK=g2,a,b.(ii)
SignSK,M. Given a message M and SK, pick r←Rℤp\−a+M/b, compute σ=g21/a+M+br, and set the signature as σ,r(iii)
VerifyPK,M,σ,r. If eug1Mvr,σ=z, it outputs 1 meaning that the signature σ,r is valid. Otherwise, it outputs 0 meaning that the signature σ,r is invalid.


## 3. Problem Formulation

In this section, we first describe the system architecture of our TR-MA-CP-ABE. Then, we give the formal algorithm definition and security model for T-MA-CP-ABE and TR-MA-CP-ABE scheme.


### 3.1. System Architecture

As shown in Figure1, our TR-MA-CP-ABE system comprises the following entities: a cloud sever (CS), a central authority (CA), multiple attribute authorities (AAs), data owners (DOs), and data users (DUs). The role of each party is described as follows:Figure 1
System architecture of TR-MA-CP-ABE.(i)
CS: CS is responsible for storing the ciphertexts and processing the ciphertext upload and download requests(ii)
CA: CA is not only responsible for generating the identity keys for data users but also for tracing and revoking the malicious users(iii)
AA: each AA generates the attribute keys for data users and updates the attribute keys for nonrevoked users(iv)
DO: each DO encrypts his own data and outsources the corresponding ciphertext to CS(v)
DU: each DU downloads the ciphertext from CS and accesses the corresponding data by his decryption keyMore specifically, CA generates its own public/secret key pair, publishes the CA public key, and uses the CA secret key to generate the identity keys for all DUs. Each AA generates its own public/secret key pair, publishes the AA public key, and generates the user keys corresponding to the attributes that are managed by it. Then, DU uses the identity key and attribute keys to generate his own decryption key. Next, DO encrypts the data by the public keys and an access policy and uploads the ciphertext to CS. Finally, the nonrevoked uses can decrypt the ciphertext when their attributes satisfy the access policy, and other users cannot access the data. In our system, when a malicious user sells his decryption key, CA first identifies him by a tracing algorithm and then revokes him by adding his identity to a revocation list. Since AA will not update the attribute keys for the users whose identities are in the revocation list, the malicious users cannot update their decryption keys and access new ciphertext data.In our system, DOs are fully trusted entities who honestly execute the encryption algorithm. CS, CA, and AAs are both honest but curious, who correctly execute the algorithms in the system, but try to learn any sensitive information about the data. Our system does not allow CS to modify or delete the stored ciphertext, but allows several corrupt AAs to make an attack on the unauthorized ciphertext whose policy cannot be satisfied by the corrupt attributes. Note that the decryption key is generated by the combination of identity key and attribute keys, so neither CA nor AA can independently construct the complete decryption key in our system. DUs are untrusted entities that may not only try to access the unauthorized data but also sell their decryption keys on the Internet. To formally describe the above system and attacks,Section 3.2 defines the TR-MA-CP-ABE algorithms, and Section 3.3 presents an adaptive security model against the adversary who try to learn any information about the unauthorized data and a traceable security model against the malicious data user who leaks his decryption key.


### 3.2. Algorithm Definition

A T-MA-CP-ABE scheme consists of eight algorithms:(i)
Global Setupλ. On input a security parameter λ, it outputs the global parameters GP for the system(ii)
CA SetupGP. CA runs this algorithm with the global parameters GP as input, and outputs its public/secret key pair CPK,CSK(iii)
AA SetupGP,Sj. Each attribute authority AAj runs this algorithm with the global parameters GP and its attributes set Sj as input and outputs its public/secret key pair APKj,ASKj(iv)
CA KeyGenGID,CSK,GP. On input an identity GID, the CA secret key CSK and the global parameters GP, the CA key generation algorithm outputs the user’s CA key CSKGID(v)
AA KeyGenGID,GP,S,CSKGID,{ASKj. On input an identity GID, the global parameters GP, a set of attributes S, a user’s CA key CSKGID, and the set of AA secret keys ASKj for the relevant AAs, the AA key generation algorithm outputs the user’s decryption key SKS,GID(vi)
EncryptGP,CPK,{APKj,M,A,ρ. On input the global parameters GP, the CA public key CPK, the set of AA public keys APKj for the relevant AAs, a message M, and an access policy A,ρ, the encryption algorithm outputs a ciphertext CT(vii)
DecryptGP,SKS,GID,CT. On input the global parameters GP, a decryption key SKS,GID for an attributes set S, and a ciphertext CT for an access policy A,ρ, the decryption algorithm returns either the message M when the attributes set S satisfies the access policy A,ρ or the error symbol ⊥ meaning that decryption fails(viii)
TraceGP,CPK,{APKj,SKS,GID. On input the global parameters GP, the CA public key CPK, the AA public keys APKj, and a decryption key SKS,GID, the tracing algorithm returns either an identity GID when SKS,GID passes the key sanity check, or the symbol ⊤ meaning that SKS,GID does not need to be traced. The key sanity check is a deterministic algorithm to determine whether SKS,GID needs to be tracedOur TR-MA-CP-ABE scheme is almost the same with the T-MA-CP-ABE scheme, except for modifying CA Setup by adding a revocation list, Encrypt and Decrypt by adding a time period, and replacing AA KeyGen by AA KeyGen and KeyUpdate and Trace by Trace and Revoke. The above modified and replaced algorithms in TR-MA-CP-ABE scheme are described as follows.(ix)
CA SetupGP. CA runs the CA setup algorithm with the global parameters GP as input to generate its public/secret key pair CPK,CSK. In addition, CA initializes an empty revocation identity list RL.(x)
AA KeyGen and KeyUpdateGID,GP,S,CSKGID,T,RL,{ASKj. It takes as input an identity GID, the global parameters GP, a set of attributes S, a time period T, a user’s CA key CSKGID, a revocation list RL, and the set of AA secret keys ASKj for the relevant AAs. If GID∈RL, it outputs ⊥. Otherwise, it outputs the user’s decryption key SKS,GID.(xi)
EncryptGP,CPK,{APKj,M,A,ρ,T′. It takes as input the global parameters GP, the CA public key CPK, the set of AA public keys APKj for the relevant authorities, an access policy A,ρ, a message M, and a time period T′. It outputs a ciphertext CT.(xii)
DecryptGP,SKS,GID,CT. It takes as input the global parameters GP, a decryption key SKS,GID for an attributes set S for a time period T, and a ciphertext CT for an access policy A,ρ for a time period T′. If T=T′ and S satisfies A,ρ, it outputs the message M. Otherwise, it outputs the error symbol ⊥.(xiii)
Trace and RevokeGP,CPK,{APKj,SKS,GID. It takes as input the global parameters GP, the CA public key CPK, the AA public keys APKj, and a decryption key SKS,GID. If SKS,GID passes the key sanity check, it returns an identity GID and add it to the revocation list RL. Otherwise, it returns the symbol ⊤.


### 3.3. Security Model

We now describe the adaptive security model for T-MA-CP-ABE scheme. In our security model, an AA can manage multiple attributes, while each attribute can only be controlled by one AA. LetV be the attribute authority universe and U be the attribute universe. The adaptive security game between a challenger and an adversary is defined as follows.(i)
Setup. The challenger runs the global setup and CA setup algorithms and then givesGP and CPK to the adversary. The adversary specifies a set of corrupt AAs V′⊆V. For noncorrupt AAs in V−V′, the challenger runs the AA setup algorithm and provides the AA public keys to the adversary.(ii)
Phase 1. The adversary can repeatedly make two types of key queries as follows(1)
CA key query. The adversary sends a user’s identityGID to the challenger. The challenger returns the corresponding private key CSKGID to the adversary.(2)
AA key query. The adversary sends a pairS,GID to the challenger, where GID is an identity, and S is a set of attributes belonging to noncorrupt AAs. The challenger returns the corresponding decryption key SKS,GID to the adversary. Note that the user’s AA private key is part of his decryption key in our scheme, so the challenger gives the user’s AA private key to the adversary in this query.(iii)
Challenge. The adversary submits two messagesM0,M1 and an access policy A,ρ, where A,ρ satisfies the following constraint. Let SV′ denote the attributes controlled by corrupt AAs, and SGID denotes the attributes in which the adversary has queried for identity GID. For each GID, we require that SV′∪SGID does not satisfy A,ρ. The challenger chooses a random coin β∈0,1 and returns ciphertext CT∗=EncryptGP,CPK,{APKj,Mβ,A,ρ to the adversary.(iv)
Phase 2. The adversary can make the key queries as Phase 1, with the restriction ofA,ρ as described above(v)
Guess. The adversary submits a guessβ′∈0,1 and wins if β=β′. The advantage of an adversary in this game is defined as Prβ=β′−1/2.Definition 5.
A T-MA-CP-ABE scheme is adaptively (or fully) secure if for any probabilistic polynomial time adversary, its advantage is negligible inλ.
A T-MA-CP-ABE scheme is called selectively secure if the adversary submits the access policyA,ρ before the Setup phase. A T-MA-CP-ABE scheme is called statically secure if the adversary submits all queries immediately after seeing the global parameters. Our construction will be proved to satisfy adaptively secure without the above restrictions.
Traceability of the T-MA-CP-ABE is described by a game as follows:(i)
Setup. The challenger runs the global setup, CA setup, and AA setup algorithms and then givesGP, CPK, and APKj to the adversary(ii)
Key query. The adversary makes the following queries(1)
CA key query. The adversary sendsGIDii=1m to the challenger, where GIDi is an identity. The challenger returns the corresponding private keys SKGIDii=1m.(2)
AA key query. The adversary sendsSi,GIDii=1m to the challenger, where Si is an attributes set. The challenger returns the corresponding decryption keys SKSi,GIDii=1m.(iii)
Key forgery. The adversary submits a decryption keySK∗ and wins if TraceGP,CPK,{APKj,SK∗∉⊤,GID1,…,GIDm.
The advantage of an adversary in this game is defined as(4)PrTraceGP,CPK,{APKj,SK∗∉⊤,GID1,…,GIDm.Definition 6.
A T-MA-CP-ABE scheme is fully traceable if for any probabilistic polynomial time adversary, its advantage is negligible inλ.
In our TR-MA-CP-ABE scheme, the AA key generation algorithm is same with the AA key update algorithm. Hence, the security model of our TR-MA-CP-ABE scheme is same with that of our T-MA-CP-ABE scheme.


## 3.1. System Architecture

As shown in Figure1, our TR-MA-CP-ABE system comprises the following entities: a cloud sever (CS), a central authority (CA), multiple attribute authorities (AAs), data owners (DOs), and data users (DUs). The role of each party is described as follows:Figure 1
System architecture of TR-MA-CP-ABE.(i)
CS: CS is responsible for storing the ciphertexts and processing the ciphertext upload and download requests(ii)
CA: CA is not only responsible for generating the identity keys for data users but also for tracing and revoking the malicious users(iii)
AA: each AA generates the attribute keys for data users and updates the attribute keys for nonrevoked users(iv)
DO: each DO encrypts his own data and outsources the corresponding ciphertext to CS(v)
DU: each DU downloads the ciphertext from CS and accesses the corresponding data by his decryption keyMore specifically, CA generates its own public/secret key pair, publishes the CA public key, and uses the CA secret key to generate the identity keys for all DUs. Each AA generates its own public/secret key pair, publishes the AA public key, and generates the user keys corresponding to the attributes that are managed by it. Then, DU uses the identity key and attribute keys to generate his own decryption key. Next, DO encrypts the data by the public keys and an access policy and uploads the ciphertext to CS. Finally, the nonrevoked uses can decrypt the ciphertext when their attributes satisfy the access policy, and other users cannot access the data. In our system, when a malicious user sells his decryption key, CA first identifies him by a tracing algorithm and then revokes him by adding his identity to a revocation list. Since AA will not update the attribute keys for the users whose identities are in the revocation list, the malicious users cannot update their decryption keys and access new ciphertext data.In our system, DOs are fully trusted entities who honestly execute the encryption algorithm. CS, CA, and AAs are both honest but curious, who correctly execute the algorithms in the system, but try to learn any sensitive information about the data. Our system does not allow CS to modify or delete the stored ciphertext, but allows several corrupt AAs to make an attack on the unauthorized ciphertext whose policy cannot be satisfied by the corrupt attributes. Note that the decryption key is generated by the combination of identity key and attribute keys, so neither CA nor AA can independently construct the complete decryption key in our system. DUs are untrusted entities that may not only try to access the unauthorized data but also sell their decryption keys on the Internet. To formally describe the above system and attacks,Section 3.2 defines the TR-MA-CP-ABE algorithms, and Section 3.3 presents an adaptive security model against the adversary who try to learn any information about the unauthorized data and a traceable security model against the malicious data user who leaks his decryption key.


## 3.2. Algorithm Definition

A T-MA-CP-ABE scheme consists of eight algorithms:(i)
Global Setupλ. On input a security parameter λ, it outputs the global parameters GP for the system(ii)
CA SetupGP. CA runs this algorithm with the global parameters GP as input, and outputs its public/secret key pair CPK,CSK(iii)
AA SetupGP,Sj. Each attribute authority AAj runs this algorithm with the global parameters GP and its attributes set Sj as input and outputs its public/secret key pair APKj,ASKj(iv)
CA KeyGenGID,CSK,GP. On input an identity GID, the CA secret key CSK and the global parameters GP, the CA key generation algorithm outputs the user’s CA key CSKGID(v)
AA KeyGenGID,GP,S,CSKGID,{ASKj. On input an identity GID, the global parameters GP, a set of attributes S, a user’s CA key CSKGID, and the set of AA secret keys ASKj for the relevant AAs, the AA key generation algorithm outputs the user’s decryption key SKS,GID(vi)
EncryptGP,CPK,{APKj,M,A,ρ. On input the global parameters GP, the CA public key CPK, the set of AA public keys APKj for the relevant AAs, a message M, and an access policy A,ρ, the encryption algorithm outputs a ciphertext CT(vii)
DecryptGP,SKS,GID,CT. On input the global parameters GP, a decryption key SKS,GID for an attributes set S, and a ciphertext CT for an access policy A,ρ, the decryption algorithm returns either the message M when the attributes set S satisfies the access policy A,ρ or the error symbol ⊥ meaning that decryption fails(viii)
TraceGP,CPK,{APKj,SKS,GID. On input the global parameters GP, the CA public key CPK, the AA public keys APKj, and a decryption key SKS,GID, the tracing algorithm returns either an identity GID when SKS,GID passes the key sanity check, or the symbol ⊤ meaning that SKS,GID does not need to be traced. The key sanity check is a deterministic algorithm to determine whether SKS,GID needs to be tracedOur TR-MA-CP-ABE scheme is almost the same with the T-MA-CP-ABE scheme, except for modifying CA Setup by adding a revocation list, Encrypt and Decrypt by adding a time period, and replacing AA KeyGen by AA KeyGen and KeyUpdate and Trace by Trace and Revoke. The above modified and replaced algorithms in TR-MA-CP-ABE scheme are described as follows.(ix)
CA SetupGP. CA runs the CA setup algorithm with the global parameters GP as input to generate its public/secret key pair CPK,CSK. In addition, CA initializes an empty revocation identity list RL.(x)
AA KeyGen and KeyUpdateGID,GP,S,CSKGID,T,RL,{ASKj. It takes as input an identity GID, the global parameters GP, a set of attributes S, a time period T, a user’s CA key CSKGID, a revocation list RL, and the set of AA secret keys ASKj for the relevant AAs. If GID∈RL, it outputs ⊥. Otherwise, it outputs the user’s decryption key SKS,GID.(xi)
EncryptGP,CPK,{APKj,M,A,ρ,T′. It takes as input the global parameters GP, the CA public key CPK, the set of AA public keys APKj for the relevant authorities, an access policy A,ρ, a message M, and a time period T′. It outputs a ciphertext CT.(xii)
DecryptGP,SKS,GID,CT. It takes as input the global parameters GP, a decryption key SKS,GID for an attributes set S for a time period T, and a ciphertext CT for an access policy A,ρ for a time period T′. If T=T′ and S satisfies A,ρ, it outputs the message M. Otherwise, it outputs the error symbol ⊥.(xiii)
Trace and RevokeGP,CPK,{APKj,SKS,GID. It takes as input the global parameters GP, the CA public key CPK, the AA public keys APKj, and a decryption key SKS,GID. If SKS,GID passes the key sanity check, it returns an identity GID and add it to the revocation list RL. Otherwise, it returns the symbol ⊤.


## 3.3. Security Model

We now describe the adaptive security model for T-MA-CP-ABE scheme. In our security model, an AA can manage multiple attributes, while each attribute can only be controlled by one AA. LetV be the attribute authority universe and U be the attribute universe. The adaptive security game between a challenger and an adversary is defined as follows.(i)
Setup. The challenger runs the global setup and CA setup algorithms and then givesGP and CPK to the adversary. The adversary specifies a set of corrupt AAs V′⊆V. For noncorrupt AAs in V−V′, the challenger runs the AA setup algorithm and provides the AA public keys to the adversary.(ii)
Phase 1. The adversary can repeatedly make two types of key queries as follows(1)
CA key query. The adversary sends a user’s identityGID to the challenger. The challenger returns the corresponding private key CSKGID to the adversary.(2)
AA key query. The adversary sends a pairS,GID to the challenger, where GID is an identity, and S is a set of attributes belonging to noncorrupt AAs. The challenger returns the corresponding decryption key SKS,GID to the adversary. Note that the user’s AA private key is part of his decryption key in our scheme, so the challenger gives the user’s AA private key to the adversary in this query.(iii)
Challenge. The adversary submits two messagesM0,M1 and an access policy A,ρ, where A,ρ satisfies the following constraint. Let SV′ denote the attributes controlled by corrupt AAs, and SGID denotes the attributes in which the adversary has queried for identity GID. For each GID, we require that SV′∪SGID does not satisfy A,ρ. The challenger chooses a random coin β∈0,1 and returns ciphertext CT∗=EncryptGP,CPK,{APKj,Mβ,A,ρ to the adversary.(iv)
Phase 2. The adversary can make the key queries as Phase 1, with the restriction ofA,ρ as described above(v)
Guess. The adversary submits a guessβ′∈0,1 and wins if β=β′. The advantage of an adversary in this game is defined as Prβ=β′−1/2.Definition 5.
A T-MA-CP-ABE scheme is adaptively (or fully) secure if for any probabilistic polynomial time adversary, its advantage is negligible inλ.
A T-MA-CP-ABE scheme is called selectively secure if the adversary submits the access policyA,ρ before the Setup phase. A T-MA-CP-ABE scheme is called statically secure if the adversary submits all queries immediately after seeing the global parameters. Our construction will be proved to satisfy adaptively secure without the above restrictions.
Traceability of the T-MA-CP-ABE is described by a game as follows:(i)
Setup. The challenger runs the global setup, CA setup, and AA setup algorithms and then givesGP, CPK, and APKj to the adversary(ii)
Key query. The adversary makes the following queries(1)
CA key query. The adversary sendsGIDii=1m to the challenger, where GIDi is an identity. The challenger returns the corresponding private keys SKGIDii=1m.(2)
AA key query. The adversary sendsSi,GIDii=1m to the challenger, where Si is an attributes set. The challenger returns the corresponding decryption keys SKSi,GIDii=1m.(iii)
Key forgery. The adversary submits a decryption keySK∗ and wins if TraceGP,CPK,{APKj,SK∗∉⊤,GID1,…,GIDm.
The advantage of an adversary in this game is defined as(4)PrTraceGP,CPK,{APKj,SK∗∉⊤,GID1,…,GIDm.Definition 6.
A T-MA-CP-ABE scheme is fully traceable if for any probabilistic polynomial time adversary, its advantage is negligible inλ.
In our TR-MA-CP-ABE scheme, the AA key generation algorithm is same with the AA key update algorithm. Hence, the security model of our TR-MA-CP-ABE scheme is same with that of our T-MA-CP-ABE scheme.


## 4. Our T-MA-CP-ABE Scheme

In this section, we present a T-MA-CP-ABE scheme in an asymmetric bilinear group and prove it is adaptively secure and fully traceable in the random oracle model.


### 4.1. Construction

Inspired by [18, 20], we adopt a hash function H to map user identities to the elements in group G2. Unlike with [18, 20], we use a CA to personalize the identity key for each user and the AAs to generate the corresponding attribute keys, so our construction can achieve multiple authorities and the AAs cannot get the user decryption key. Furthermore, we employ a full signature scheme [32] to realize traceability. More specifically, the CA injects the signature of the user identity into the user identity key and traces the user by his decryption key. We now present our T-MA-CP-ABE construction based on [18, 20], in which each attribute authority AAj manages an attributes set Sj.(i)
Global Setupλ. The algorithm first runs Gλ to obtain p,G1,G2,GT,g1,g2,e. G1,G2, and GT are the cyclic groups of prime order p, g1 is a generator of G1, g2 is a generator of G2, and e:G1×G2⟶GT is a bilinear map. It then samples B=bij3×3←GL3ℤp and sets B∗=B−1⊤ and b1⟶=b11,b21,b23⊤. It chooses a hash function H:ℤp∗⟶G23 and publishes GP=p,G13,G23,GT,g1,g2,e,g1b1⟶,H as the global parameters.(ii)
CA SetupGP. CA picks a,b←Rℤp and computes cpk1=g1b1⟶a=g1ab1⟶, cpk2=g1b1⟶b=g1bb1⟶. Then, CA publishes the public key CPK=cpk1,cpk2 and sets CSK=a,b as its secret key.(iii)
AA SetupGP,Sj. For each attribute i∈Sj, AAj picks ki⟶←Rℤp3,Yi←Rℤp3×3 and computes apki,1=g1b1⟶⊤Yi⊤=g1Yi⊤b1⟶, and apki,2=eg1b1⟶,g2ki⟶=eg1,g2b1⟶⊤ki⟶⊤=eg1,g2ki⟶b1⟶. Then, AAj publishes the public key APKj=apki,1,apki,2i∈Sj and sets ASKj=ki⟶,Yi⊤i∈Sj as its secret key.(iv)
CA KeyGenGID,CSK,GP. For a user’s identity GID∈ℤp, CA picks rGID←Rℤp∖−a+GID/b and sets K1,GID=GID,K2,GID=rGID,K3,GID=g21/a+GID+brGID,andK4,GID=HGID1/a+GID+brGID. Then, CA sends the private key CSKGID=K1,GID,K2,GID,K3,GID,K4,GID to the user whose identity is GID.(v)
AA KeyGenGID,GP,S,CSKGID,{ASKj. A user submits his identity GID and attributes set S and K3,GID,K4,GID to the relevant authorities AAj. For each attribute i∈S∩Sj, AAj computes and sends the private key SKi,GID=K3,GIDki⟶K4,GIDYi⊤ to the corresponding user. When the user receives SKi,GIDi∈S, he sets SKS,GID=K1,GID,K2,GID,SKi,GIDi∈S as his decryption key.(vi)
EncryptGP,CPK,{APKj,M,A,ρ. On input a message M and an access policy A,ρ. A is a l×n matrix, and ρ maps its rows to attributes. It first picks U2,U3,…,Un←Rℤp3×3,0⟶←ℤp3,v⟶=s0,v2,v3,…,vn←Rℤpn,s←Rℤp. For each x∈1,2,…l, it computes λx=Ax⟶,v⟶, $ $, where Ax⟶ is the row x of A. The ciphertext CT is computed as(5)C=Meg1,g2s0,C0=g1sb1⟶,C1=g1sab1⟶,C2=g1sbb1⟶,C1,x=eg1,g2λxeg1,g2skρx⟶b1⟶,C2,x=g10⟶⊤,sU2⊤b1⟶,…,sUl⊤b1⟶Ax⟶⊤g1sYρx⊤b1⟶.DecryptGP,SKS,GID,CT. On input a ciphertext CT for a policy A,ρ and a decryption key SKS,GID for an attributes set S. Let I=x:ρx∈S. If S does not satisfy A,ρ, it outputs ⊥. Otherwise, it chooses constants cx∈ℤpx∈I such that ∑x∈IcxAx⟶=1,0,…,0 and computes(6)∏x∈IC1,xcxe∏x∈IC2,xcx,HK1,GIDeC0K1,GIDC1C2K2,GID,∏x∈ISKρx,GIDcx=eg1,g2s0.Finally, the message can be recovered asM=C/eg1,g2s0(vii)
TraceGP,CPK,{APKj,SKS,GID. If the decryption key SKS,GID is not in the form of SKS,GID=K1,GID,K2,GID,SKi,GIDi∈S, it outputs ⊤. Otherwise, it runs a key sanity check on SKS,GID as follows: K1,GID∈ℤp,K2,GID∈ℤp, ∃i∈S, s.t. SKi,GID∈G23 and(7)eg1b1⟶K1,GIDcpk1cpk2K2,GID,SKi,GID=eapki,1,HK1,GIDapki,2.IfSKS,GID passes the above check, it outputs the identity K1,GID. Otherwise, it outputs ⊤.(viii)
CorrectnessIf the attributes setS satisfies the policy A,ρ, we have that ∑x∈IcxAx⟶=1,0,…,0. Then,(8)∑x∈Icxλx=∑x∈IcxAx⟶v⟶⊤=s0,∑x∈Icx0⟶⊤,sU2⊤b1⟶,…,sUl⊤b1⟶Ax⟶⊤=0⟶⊤,sU2⊤b1⟶,…,sUl⊤b1⟶1,0,…,0⊤=0⟶⊤.Therefore,(9)∏x∈IC1,xcx=eg1,g2∑x∈Icxλxeg1,g2∑x∈Icxskρx⟶b1⟶=g1,g2s0eg1,g2∑x∈Icxskρx⟶b1⟶.Note thatHK1,GID=HGID∈G23, so there exists an unknown vector tGID⟶∈ℤp3 such that HGID=g2tGID⟶. Then, we have(10)e∏x∈IC2,xcx,HK1,GID=e∏x∈Ig10⟶⊤,sU2⊤b1⟶,…,sUl⊤b1⟶Ax⟶⊤+sYρx⊤b1⟶,g2tGID⟶=eg1∑x∈IcxsYρx⊤b1⟶,g2tGID⟶=eg1,g2tGID⟶∑x∈IcxsYρx⊤b1⟶,eC0K1,GIDC1C2K2,GID,∏x∈ISKρx,GIDcx=eg1sa+GID+brGIDb1⟶,∏x∈Ig2cxkρx⟶/a+GID+brGIDHGIDcxYρx⊤/a+GID+brGID=eg1sb1⟶,g2∑x∈Icxkρx⟶g2tGID⟶∑x∈IcxYρx⊤=eg1,g2∑x∈Icxskρx⟶b1⟶eg1,g2tGID⟶∑x∈IcxsYρx⊤b1⟶.Hence,∏x∈IC1,xcxe∏x∈IC2,xcx,HK1,GID/eC0K1,GIDC1C2K2,GID,∏x∈ISKρx,GIDcx=eg1,g2s0.


### 4.2. Security Analysis

In this section, we first prove that our T-MA-CP-ABE scheme is adaptively secure based on the SXDH assumption by a reduction to the underlying scheme in [20]. More specifically, we assume an adversary A breaks our T-MA-CP-ABE scheme in the random oracle model with advantage ɛ; then, we build a simulator ℬ that breaks the scheme [20] in the random oracle model with advantage ɛ. Then, we prove our T-MA-CP-ABE scheme is fully traceable based on the q-SDH assumption by a reduction to a signature scheme [32]. More specifically, we assume an adversary A breaks our T-MA-CP-ABE scheme in the traceability game; then, we build a simulator ℬ that breaks the signature scheme [32] under an adaptive chosen message attack.


#### 4.2.1. Adaptive Security

Note that there are two typos (that make encryption and decryption algorithms cannot be completely executed) in the scheme [20] that should be corrected: C1,x should be corrected as C1,x=eg1,g2λxeg1,g2kρx⟶b1⟶s⟶, and SKGID,i should be corrected as SKGID,i=g2ki⟶HGIDYi⊤. We denote the scheme [20] with k=1 as ZCGM1 scheme, which has been proved adaptively secure in [20].Lemma 1 (see [20]).
If the SXDH assumption holds, then the ZCGM1 scheme is adaptively secure in the random oracle model.Lemma 2.
Assuming that the ZCGM1 scheme [20] is adaptively secure, then our T-MA-CP-ABE scheme is adaptively secure.Proof.
LetC denote the challenger corresponding to ℬ in the adaptive security game of ZCGM1 scheme.(i)
Setup. Whenℬ receives the global parameters GP from C, it picks a,b←Rℤp and computes cpk1=g1b1⟶a=g1ab1⟶, and cpk2=g1b1⟶b=g1bb1⟶. Then, ℬ stores a,b and sends GP and CPK=cpk1,cpk2 to A. Next, A submits a corrupt AAs set V′⊆V to ℬ, and ℬ submits V−V′ to C to request the AA public keys for noncorrupt AAs. When ℬ obtains AA public keys APKjj∈V−V′ from C, it sends APKjj∈V−V′ to A.(ii)
Phase 1.ℬ initializes an empty table Q and answers the CA key and AA key queries as follows:(1)
CA key query. WhenA submits an identity GID to ℬ to request the corresponding CA key, ℬ first searches the entry GID,rGID,K3,GID,K4,GID in table Q. If such entry exists, ℬ returns GID,rGID,K3,GID,K4,GID to A. Otherwise, ℬ picks rGID←Rℤp∖−a+GID/b and computes K3,GID=g21/a+GID+brGID,K4,GID=HGID1/a+GID+brGID. Then, ℬ sends CSKGID=GID,rGID,K3,GID,K4,GID to A and stores it in Q.(2)
AA key query. WhenA submits a pair S,GID to ℬ to request the corresponding decryption key, ℬ first searches the entry GID,rGID,K3,GID,K4,GID in table Q. If such entry exists, ℬ can obtain rGID from table Q. Otherwise, ℬ picks rGID←Rℤp∖−a+GID/b, computes K3,GID=g21/a+GID+brGID,K4,GID=HGID1/a+GID+brGID, and stores GID,rGID,K3,GID,K4,GID in table Q. Then, ℬ calls the ZCGM1 AA key generation oracle on S,GID to obtain the private key SKGID,ii∈S. For each i∈S, ℬ computes SKi,GID=SKGID,i1/a+GID+brGID. Finally, ℬ sets the corresponding decryption key as SKS,GID=GID,rGID,SKi,GIDi∈S and sends it to A.(iii)
Challenge. The adversaryA submits two messages M0,M1 and an access policy A,ρ, where A,ρ satisfies the following constraint. Let SV′ denote the attributes controlled by corrupt AAs, and SGID denotes the attributes in which the adversary has queried for identity GID. For each GID, we require that SV′∪SGID does not satisfy A,ρ. The challenger ℬ sends M0,M1, and A,ρ to C to obtain the ZCGM1 challenge ciphertext CT=C,C0,C1,x,C2,xx∈1,2,…,n. Then, ℬ computes C1=C0a=g1sab1⟶,C2=C0b=g1sbb1⟶ and sends CT∗=C,C0,C1,C2,C1,x,C2,xx∈1,2,…,n to A.(iv)
Phase 2. The adversary makes the key queries as Phase 1, but with the restriction ofA,ρ as described above. ℬ responds the queries in the same way as Phase 1.(v)
Guess. WhenA outputs a guess β′, then ℬ outputs β′.
Sinceℬ perfectly simulates the ZCGM1 security game for A, the advantage of ℬ breaks the ZCGM1 scheme equals to the advantage of A breaks our scheme.Theorem 1.
If the SXDH assumption holds, then our T-MA-CP-ABE scheme is adaptively secure.Proof.
This proof follows directly from Lemmas1 and 2.


#### 4.2.2. Traceability

Now, we prove our T-MA-CP-ABE scheme is fully traceable by a reduction to BB scheme [32], which is strongly existentially unforgeable.Lemma 3 (See [32]).
If theq-SDH assumption holds, then the BB scheme is strongly existentially unforgeable under an adaptive chosen message attack.Lemma 4.
Assuming that the BB scheme [32] is strongly existentially unforgeable under an adaptive chosen message attack, then our T-MA-CP-ABE scheme is fully traceable in the random oracle model.Proof.
Letp,G1,G2,GT,g1,g2,e be a prime order bilinear group, and p,g1,g2,g1a,g1b be the public key of BB scheme. Let Sj be the attributes set managed by attribute authority AAj, and C be the challenger corresponding to ℬ in the BB security game.(i)
Setup. Whenℬ receives public key p,g1,g2,g1a,g1b from C, it first samples B=bij3×3←GL3ℤp, sets B∗=B−1⊤, b1⟶=b11,b21,b23⊤, and GP=p,G13,G23,GT,g1,g2,e,g1b1⟶. Then, ℬ computes cpk1=g1b1⟶a=g1ab1⟶, cpk2=g1b1⟶b=g1bb1⟶, and sets CPK=cpk1,cpk2. For each attribute i∈Sj, ℬ picks ki⟶←Rℤp3,Yi←Rℤp3×3, computes apki,1=g1Yi⊤b1⟶ and apki,2=eg1b1⟶,g2ki⟶, and sets APKj=apki,1,apki,2i∈Sj. Finally, ℬ sends global parameters GP, CA public key CPK, and AA public keys APKj to A. ℬ stores b1⟶,ki⟶,Yi and controls the random oracle H.(ii)
Key query. In this phase,A queries the CA keys corresponding to GIDii=1m and AA keys corresponding to Si,GIDii=1m. ℬ initializes two empty tables Q1andQ2 and answers A’s queries as follows:(1)
Random oracle hash query. WhenA submits an identity GID to ℬ to request the corresponding random oracle hash value HGID, ℬ first searches the entry GID,tGID⟶,g2tGID⟶ in Q1. If such entry exists, ℬ returns g2tGID⟶. Otherwise, ℬ picks tGID⟶←Rℤp3, sends g2tGID⟶ to A, and stores GID,tGID⟶,g2tGID⟶ in Q1.(2)
CA key query. WhenA submits an identity GIDi to ℬ to request the corresponding CA key SKGIDi, ℬ first searches the entry SKGIDi=GIDi,rGIDi,K3,GIDi,K4,GIDi in Q2. If such entry exists, ℬ returns SKGIDi to A. Otherwise, ℬ submits GIDi to C to request the corresponding signature. When ℬ receives signature rGIDi,σGIDi=g21/a+GIDi+brGIDi from C, ℬ searches the entry GIDi,tGIDi⟶,g2tGIDi⟶ in Q1. If no such entry exists, ℬ picks tGIDi⟶←Rℤp3 and stores GIDi,tGIDi⟶,g2tGIDi⟶ in Q1. Next, ℬ obtains tGIDi⟶ from table Q1 and sets SKGIDi=GIDi,rGIDi,K3,GIDi=σGIDi,K4,GIDi=σGIDitGIDi⟶ as the corresponding CA private key. Finally, ℬ sends SKGIDi to A and stores it in Q2.(3)
AA key query. WhenA submits a pair Si,GIDi to ℬ to request the corresponding decryption key SKSi,GIDi, ℬ first searches CA key SKGIDi=GIDi,rGIDi,K3,GIDi,K4,GIDi in Q2. If no such entry exists, ℬ generates CA key SKGIDi as in (2) and stores it in Q2. For each l∈Si, ℬ computes SKl,GIDi=K3,GIDikl⟶K4,GIDiYl⊤. Finally, ℬ sends the corresponding decryption key SKSi,GIDi=GIDi,rGIDi,SKl,GIDil∈Si to A.(iii)
Key forgery.A returns a decryption key SK∗ to ℬ.IfA wins this game, then TraceGP,CPK,{APKj},SK∗∉⊤,GID1,…,GIDm. Therefore, the decryption key SK∗=K1,GID,K2,GID,SKi,GIDi∈S passes the key sanity check, and K1,GID∉GID1,…,GIDm. Hence, K1,GID∈ℤp,K2,GID∈ℤp, ∃i∈S, s.t. SKi,GID∈G23, and(11)eg1b1⟶K1,GIDcpk1cpk2K2,GID,SKi,GID=eapki,1,HK1,GIDapki,2.
ℬ queries the random oracle hash HK1,GID as in (1) and gets the record K1,GID,tK1,GID⟶,g2tK1,GID⟶ from Q1. Then,(12)eg1K1,GID+a+bK2,GIDb1⟶,SKi,GID=eg1Yi⊤b1⟶,g2tK1,GID⟶eg1b1⟶,g2ki⟶=eg1b1⟶,g2ki⟶+tK1,GID⟶Yi⊤.
Hence, we haveSKi,GID=g2ki⟶+tK1,GID⟶Yi⊤/K1,GID+a+bK2,GID. As ℬ knows the pairs tK1,GID⟶,ki⟶,Yi⊤, it can compute ki⟶+tK1,GID⟶Yi⊤=a1,a2,a3∈ℤp3. Then, ℬ obtains SKi,GID,1=g2a1/K1,GID+a+bK2,GID from SKi,GID and sets σ=SKi,GID,11/a1=g21/K1,GID+a+bK2,GID.
Sinceeg1ag1K1,GIDg1bK2,GID,σ=z, ℬ can output a valid signature σ,K2,GID on message K1,GID in the BB security game. Note that K1,GID∉GID1,…,GIDm, so ℬ has never queried a signature on K1,GID, and then, ℬ wins the BB security game. Hence, if A breaks our T-MA-CP-ABE scheme in the traceability game with advantage ɛ, then ℬ breaks the BB scheme with advantage ɛ.Theorem 2.
If theq-SDH assumption holds, then our T-MA-CP-ABE scheme is fully traceable in the random oracle model.Proof.
This proof follows directly from Lemmas3 and 4.


## 4.1. Construction

Inspired by [18, 20], we adopt a hash function H to map user identities to the elements in group G2. Unlike with [18, 20], we use a CA to personalize the identity key for each user and the AAs to generate the corresponding attribute keys, so our construction can achieve multiple authorities and the AAs cannot get the user decryption key. Furthermore, we employ a full signature scheme [32] to realize traceability. More specifically, the CA injects the signature of the user identity into the user identity key and traces the user by his decryption key. We now present our T-MA-CP-ABE construction based on [18, 20], in which each attribute authority AAj manages an attributes set Sj.(i)
Global Setupλ. The algorithm first runs Gλ to obtain p,G1,G2,GT,g1,g2,e. G1,G2, and GT are the cyclic groups of prime order p, g1 is a generator of G1, g2 is a generator of G2, and e:G1×G2⟶GT is a bilinear map. It then samples B=bij3×3←GL3ℤp and sets B∗=B−1⊤ and b1⟶=b11,b21,b23⊤. It chooses a hash function H:ℤp∗⟶G23 and publishes GP=p,G13,G23,GT,g1,g2,e,g1b1⟶,H as the global parameters.(ii)
CA SetupGP. CA picks a,b←Rℤp and computes cpk1=g1b1⟶a=g1ab1⟶, cpk2=g1b1⟶b=g1bb1⟶. Then, CA publishes the public key CPK=cpk1,cpk2 and sets CSK=a,b as its secret key.(iii)
AA SetupGP,Sj. For each attribute i∈Sj, AAj picks ki⟶←Rℤp3,Yi←Rℤp3×3 and computes apki,1=g1b1⟶⊤Yi⊤=g1Yi⊤b1⟶, and apki,2=eg1b1⟶,g2ki⟶=eg1,g2b1⟶⊤ki⟶⊤=eg1,g2ki⟶b1⟶. Then, AAj publishes the public key APKj=apki,1,apki,2i∈Sj and sets ASKj=ki⟶,Yi⊤i∈Sj as its secret key.(iv)
CA KeyGenGID,CSK,GP. For a user’s identity GID∈ℤp, CA picks rGID←Rℤp∖−a+GID/b and sets K1,GID=GID,K2,GID=rGID,K3,GID=g21/a+GID+brGID,andK4,GID=HGID1/a+GID+brGID. Then, CA sends the private key CSKGID=K1,GID,K2,GID,K3,GID,K4,GID to the user whose identity is GID.(v)
AA KeyGenGID,GP,S,CSKGID,{ASKj. A user submits his identity GID and attributes set S and K3,GID,K4,GID to the relevant authorities AAj. For each attribute i∈S∩Sj, AAj computes and sends the private key SKi,GID=K3,GIDki⟶K4,GIDYi⊤ to the corresponding user. When the user receives SKi,GIDi∈S, he sets SKS,GID=K1,GID,K2,GID,SKi,GIDi∈S as his decryption key.(vi)
EncryptGP,CPK,{APKj,M,A,ρ. On input a message M and an access policy A,ρ. A is a l×n matrix, and ρ maps its rows to attributes. It first picks U2,U3,…,Un←Rℤp3×3,0⟶←ℤp3,v⟶=s0,v2,v3,…,vn←Rℤpn,s←Rℤp. For each x∈1,2,…l, it computes λx=Ax⟶,v⟶, $ $, where Ax⟶ is the row x of A. The ciphertext CT is computed as(5)C=Meg1,g2s0,C0=g1sb1⟶,C1=g1sab1⟶,C2=g1sbb1⟶,C1,x=eg1,g2λxeg1,g2skρx⟶b1⟶,C2,x=g10⟶⊤,sU2⊤b1⟶,…,sUl⊤b1⟶Ax⟶⊤g1sYρx⊤b1⟶.DecryptGP,SKS,GID,CT. On input a ciphertext CT for a policy A,ρ and a decryption key SKS,GID for an attributes set S. Let I=x:ρx∈S. If S does not satisfy A,ρ, it outputs ⊥. Otherwise, it chooses constants cx∈ℤpx∈I such that ∑x∈IcxAx⟶=1,0,…,0 and computes(6)∏x∈IC1,xcxe∏x∈IC2,xcx,HK1,GIDeC0K1,GIDC1C2K2,GID,∏x∈ISKρx,GIDcx=eg1,g2s0.Finally, the message can be recovered asM=C/eg1,g2s0(vii)
TraceGP,CPK,{APKj,SKS,GID. If the decryption key SKS,GID is not in the form of SKS,GID=K1,GID,K2,GID,SKi,GIDi∈S, it outputs ⊤. Otherwise, it runs a key sanity check on SKS,GID as follows: K1,GID∈ℤp,K2,GID∈ℤp, ∃i∈S, s.t. SKi,GID∈G23 and(7)eg1b1⟶K1,GIDcpk1cpk2K2,GID,SKi,GID=eapki,1,HK1,GIDapki,2.IfSKS,GID passes the above check, it outputs the identity K1,GID. Otherwise, it outputs ⊤.(viii)
CorrectnessIf the attributes setS satisfies the policy A,ρ, we have that ∑x∈IcxAx⟶=1,0,…,0. Then,(8)∑x∈Icxλx=∑x∈IcxAx⟶v⟶⊤=s0,∑x∈Icx0⟶⊤,sU2⊤b1⟶,…,sUl⊤b1⟶Ax⟶⊤=0⟶⊤,sU2⊤b1⟶,…,sUl⊤b1⟶1,0,…,0⊤=0⟶⊤.Therefore,(9)∏x∈IC1,xcx=eg1,g2∑x∈Icxλxeg1,g2∑x∈Icxskρx⟶b1⟶=g1,g2s0eg1,g2∑x∈Icxskρx⟶b1⟶.Note thatHK1,GID=HGID∈G23, so there exists an unknown vector tGID⟶∈ℤp3 such that HGID=g2tGID⟶. Then, we have(10)e∏x∈IC2,xcx,HK1,GID=e∏x∈Ig10⟶⊤,sU2⊤b1⟶,…,sUl⊤b1⟶Ax⟶⊤+sYρx⊤b1⟶,g2tGID⟶=eg1∑x∈IcxsYρx⊤b1⟶,g2tGID⟶=eg1,g2tGID⟶∑x∈IcxsYρx⊤b1⟶,eC0K1,GIDC1C2K2,GID,∏x∈ISKρx,GIDcx=eg1sa+GID+brGIDb1⟶,∏x∈Ig2cxkρx⟶/a+GID+brGIDHGIDcxYρx⊤/a+GID+brGID=eg1sb1⟶,g2∑x∈Icxkρx⟶g2tGID⟶∑x∈IcxYρx⊤=eg1,g2∑x∈Icxskρx⟶b1⟶eg1,g2tGID⟶∑x∈IcxsYρx⊤b1⟶.Hence,∏x∈IC1,xcxe∏x∈IC2,xcx,HK1,GID/eC0K1,GIDC1C2K2,GID,∏x∈ISKρx,GIDcx=eg1,g2s0.


## 4.2. Security Analysis

In this section, we first prove that our T-MA-CP-ABE scheme is adaptively secure based on the SXDH assumption by a reduction to the underlying scheme in [20]. More specifically, we assume an adversary A breaks our T-MA-CP-ABE scheme in the random oracle model with advantage ɛ; then, we build a simulator ℬ that breaks the scheme [20] in the random oracle model with advantage ɛ. Then, we prove our T-MA-CP-ABE scheme is fully traceable based on the q-SDH assumption by a reduction to a signature scheme [32]. More specifically, we assume an adversary A breaks our T-MA-CP-ABE scheme in the traceability game; then, we build a simulator ℬ that breaks the signature scheme [32] under an adaptive chosen message attack.


### 4.2.1. Adaptive Security

Note that there are two typos (that make encryption and decryption algorithms cannot be completely executed) in the scheme [20] that should be corrected: C1,x should be corrected as C1,x=eg1,g2λxeg1,g2kρx⟶b1⟶s⟶, and SKGID,i should be corrected as SKGID,i=g2ki⟶HGIDYi⊤. We denote the scheme [20] with k=1 as ZCGM1 scheme, which has been proved adaptively secure in [20].Lemma 1 (see [20]).
If the SXDH assumption holds, then the ZCGM1 scheme is adaptively secure in the random oracle model.Lemma 2.
Assuming that the ZCGM1 scheme [20] is adaptively secure, then our T-MA-CP-ABE scheme is adaptively secure.Proof.
LetC denote the challenger corresponding to ℬ in the adaptive security game of ZCGM1 scheme.(i)
Setup. Whenℬ receives the global parameters GP from C, it picks a,b←Rℤp and computes cpk1=g1b1⟶a=g1ab1⟶, and cpk2=g1b1⟶b=g1bb1⟶. Then, ℬ stores a,b and sends GP and CPK=cpk1,cpk2 to A. Next, A submits a corrupt AAs set V′⊆V to ℬ, and ℬ submits V−V′ to C to request the AA public keys for noncorrupt AAs. When ℬ obtains AA public keys APKjj∈V−V′ from C, it sends APKjj∈V−V′ to A.(ii)
Phase 1.ℬ initializes an empty table Q and answers the CA key and AA key queries as follows:(1)
CA key query. WhenA submits an identity GID to ℬ to request the corresponding CA key, ℬ first searches the entry GID,rGID,K3,GID,K4,GID in table Q. If such entry exists, ℬ returns GID,rGID,K3,GID,K4,GID to A. Otherwise, ℬ picks rGID←Rℤp∖−a+GID/b and computes K3,GID=g21/a+GID+brGID,K4,GID=HGID1/a+GID+brGID. Then, ℬ sends CSKGID=GID,rGID,K3,GID,K4,GID to A and stores it in Q.(2)
AA key query. WhenA submits a pair S,GID to ℬ to request the corresponding decryption key, ℬ first searches the entry GID,rGID,K3,GID,K4,GID in table Q. If such entry exists, ℬ can obtain rGID from table Q. Otherwise, ℬ picks rGID←Rℤp∖−a+GID/b, computes K3,GID=g21/a+GID+brGID,K4,GID=HGID1/a+GID+brGID, and stores GID,rGID,K3,GID,K4,GID in table Q. Then, ℬ calls the ZCGM1 AA key generation oracle on S,GID to obtain the private key SKGID,ii∈S. For each i∈S, ℬ computes SKi,GID=SKGID,i1/a+GID+brGID. Finally, ℬ sets the corresponding decryption key as SKS,GID=GID,rGID,SKi,GIDi∈S and sends it to A.(iii)
Challenge. The adversaryA submits two messages M0,M1 and an access policy A,ρ, where A,ρ satisfies the following constraint. Let SV′ denote the attributes controlled by corrupt AAs, and SGID denotes the attributes in which the adversary has queried for identity GID. For each GID, we require that SV′∪SGID does not satisfy A,ρ. The challenger ℬ sends M0,M1, and A,ρ to C to obtain the ZCGM1 challenge ciphertext CT=C,C0,C1,x,C2,xx∈1,2,…,n. Then, ℬ computes C1=C0a=g1sab1⟶,C2=C0b=g1sbb1⟶ and sends CT∗=C,C0,C1,C2,C1,x,C2,xx∈1,2,…,n to A.(iv)
Phase 2. The adversary makes the key queries as Phase 1, but with the restriction ofA,ρ as described above. ℬ responds the queries in the same way as Phase 1.(v)
Guess. WhenA outputs a guess β′, then ℬ outputs β′.
Sinceℬ perfectly simulates the ZCGM1 security game for A, the advantage of ℬ breaks the ZCGM1 scheme equals to the advantage of A breaks our scheme.Theorem 1.
If the SXDH assumption holds, then our T-MA-CP-ABE scheme is adaptively secure.Proof.
This proof follows directly from Lemmas1 and 2.


### 4.2.2. Traceability

Now, we prove our T-MA-CP-ABE scheme is fully traceable by a reduction to BB scheme [32], which is strongly existentially unforgeable.Lemma 3 (See [32]).
If theq-SDH assumption holds, then the BB scheme is strongly existentially unforgeable under an adaptive chosen message attack.Lemma 4.
Assuming that the BB scheme [32] is strongly existentially unforgeable under an adaptive chosen message attack, then our T-MA-CP-ABE scheme is fully traceable in the random oracle model.Proof.
Letp,G1,G2,GT,g1,g2,e be a prime order bilinear group, and p,g1,g2,g1a,g1b be the public key of BB scheme. Let Sj be the attributes set managed by attribute authority AAj, and C be the challenger corresponding to ℬ in the BB security game.(i)
Setup. Whenℬ receives public key p,g1,g2,g1a,g1b from C, it first samples B=bij3×3←GL3ℤp, sets B∗=B−1⊤, b1⟶=b11,b21,b23⊤, and GP=p,G13,G23,GT,g1,g2,e,g1b1⟶. Then, ℬ computes cpk1=g1b1⟶a=g1ab1⟶, cpk2=g1b1⟶b=g1bb1⟶, and sets CPK=cpk1,cpk2. For each attribute i∈Sj, ℬ picks ki⟶←Rℤp3,Yi←Rℤp3×3, computes apki,1=g1Yi⊤b1⟶ and apki,2=eg1b1⟶,g2ki⟶, and sets APKj=apki,1,apki,2i∈Sj. Finally, ℬ sends global parameters GP, CA public key CPK, and AA public keys APKj to A. ℬ stores b1⟶,ki⟶,Yi and controls the random oracle H.(ii)
Key query. In this phase,A queries the CA keys corresponding to GIDii=1m and AA keys corresponding to Si,GIDii=1m. ℬ initializes two empty tables Q1andQ2 and answers A’s queries as follows:(1)
Random oracle hash query. WhenA submits an identity GID to ℬ to request the corresponding random oracle hash value HGID, ℬ first searches the entry GID,tGID⟶,g2tGID⟶ in Q1. If such entry exists, ℬ returns g2tGID⟶. Otherwise, ℬ picks tGID⟶←Rℤp3, sends g2tGID⟶ to A, and stores GID,tGID⟶,g2tGID⟶ in Q1.(2)
CA key query. WhenA submits an identity GIDi to ℬ to request the corresponding CA key SKGIDi, ℬ first searches the entry SKGIDi=GIDi,rGIDi,K3,GIDi,K4,GIDi in Q2. If such entry exists, ℬ returns SKGIDi to A. Otherwise, ℬ submits GIDi to C to request the corresponding signature. When ℬ receives signature rGIDi,σGIDi=g21/a+GIDi+brGIDi from C, ℬ searches the entry GIDi,tGIDi⟶,g2tGIDi⟶ in Q1. If no such entry exists, ℬ picks tGIDi⟶←Rℤp3 and stores GIDi,tGIDi⟶,g2tGIDi⟶ in Q1. Next, ℬ obtains tGIDi⟶ from table Q1 and sets SKGIDi=GIDi,rGIDi,K3,GIDi=σGIDi,K4,GIDi=σGIDitGIDi⟶ as the corresponding CA private key. Finally, ℬ sends SKGIDi to A and stores it in Q2.(3)
AA key query. WhenA submits a pair Si,GIDi to ℬ to request the corresponding decryption key SKSi,GIDi, ℬ first searches CA key SKGIDi=GIDi,rGIDi,K3,GIDi,K4,GIDi in Q2. If no such entry exists, ℬ generates CA key SKGIDi as in (2) and stores it in Q2. For each l∈Si, ℬ computes SKl,GIDi=K3,GIDikl⟶K4,GIDiYl⊤. Finally, ℬ sends the corresponding decryption key SKSi,GIDi=GIDi,rGIDi,SKl,GIDil∈Si to A.(iii)
Key forgery.A returns a decryption key SK∗ to ℬ.IfA wins this game, then TraceGP,CPK,{APKj},SK∗∉⊤,GID1,…,GIDm. Therefore, the decryption key SK∗=K1,GID,K2,GID,SKi,GIDi∈S passes the key sanity check, and K1,GID∉GID1,…,GIDm. Hence, K1,GID∈ℤp,K2,GID∈ℤp, ∃i∈S, s.t. SKi,GID∈G23, and(11)eg1b1⟶K1,GIDcpk1cpk2K2,GID,SKi,GID=eapki,1,HK1,GIDapki,2.
ℬ queries the random oracle hash HK1,GID as in (1) and gets the record K1,GID,tK1,GID⟶,g2tK1,GID⟶ from Q1. Then,(12)eg1K1,GID+a+bK2,GIDb1⟶,SKi,GID=eg1Yi⊤b1⟶,g2tK1,GID⟶eg1b1⟶,g2ki⟶=eg1b1⟶,g2ki⟶+tK1,GID⟶Yi⊤.
Hence, we haveSKi,GID=g2ki⟶+tK1,GID⟶Yi⊤/K1,GID+a+bK2,GID. As ℬ knows the pairs tK1,GID⟶,ki⟶,Yi⊤, it can compute ki⟶+tK1,GID⟶Yi⊤=a1,a2,a3∈ℤp3. Then, ℬ obtains SKi,GID,1=g2a1/K1,GID+a+bK2,GID from SKi,GID and sets σ=SKi,GID,11/a1=g21/K1,GID+a+bK2,GID.
Sinceeg1ag1K1,GIDg1bK2,GID,σ=z, ℬ can output a valid signature σ,K2,GID on message K1,GID in the BB security game. Note that K1,GID∉GID1,…,GIDm, so ℬ has never queried a signature on K1,GID, and then, ℬ wins the BB security game. Hence, if A breaks our T-MA-CP-ABE scheme in the traceability game with advantage ɛ, then ℬ breaks the BB scheme with advantage ɛ.Theorem 2.
If theq-SDH assumption holds, then our T-MA-CP-ABE scheme is fully traceable in the random oracle model.Proof.
This proof follows directly from Lemmas3 and 4.


## 4.2.1. Adaptive Security

Note that there are two typos (that make encryption and decryption algorithms cannot be completely executed) in the scheme [20] that should be corrected: C1,x should be corrected as C1,x=eg1,g2λxeg1,g2kρx⟶b1⟶s⟶, and SKGID,i should be corrected as SKGID,i=g2ki⟶HGIDYi⊤. We denote the scheme [20] with k=1 as ZCGM1 scheme, which has been proved adaptively secure in [20].Lemma 1 (see [20]).
If the SXDH assumption holds, then the ZCGM1 scheme is adaptively secure in the random oracle model.Lemma 2.
Assuming that the ZCGM1 scheme [20] is adaptively secure, then our T-MA-CP-ABE scheme is adaptively secure.Proof.
LetC denote the challenger corresponding to ℬ in the adaptive security game of ZCGM1 scheme.(i)
Setup. Whenℬ receives the global parameters GP from C, it picks a,b←Rℤp and computes cpk1=g1b1⟶a=g1ab1⟶, and cpk2=g1b1⟶b=g1bb1⟶. Then, ℬ stores a,b and sends GP and CPK=cpk1,cpk2 to A. Next, A submits a corrupt AAs set V′⊆V to ℬ, and ℬ submits V−V′ to C to request the AA public keys for noncorrupt AAs. When ℬ obtains AA public keys APKjj∈V−V′ from C, it sends APKjj∈V−V′ to A.(ii)
Phase 1.ℬ initializes an empty table Q and answers the CA key and AA key queries as follows:(1)
CA key query. WhenA submits an identity GID to ℬ to request the corresponding CA key, ℬ first searches the entry GID,rGID,K3,GID,K4,GID in table Q. If such entry exists, ℬ returns GID,rGID,K3,GID,K4,GID to A. Otherwise, ℬ picks rGID←Rℤp∖−a+GID/b and computes K3,GID=g21/a+GID+brGID,K4,GID=HGID1/a+GID+brGID. Then, ℬ sends CSKGID=GID,rGID,K3,GID,K4,GID to A and stores it in Q.(2)
AA key query. WhenA submits a pair S,GID to ℬ to request the corresponding decryption key, ℬ first searches the entry GID,rGID,K3,GID,K4,GID in table Q. If such entry exists, ℬ can obtain rGID from table Q. Otherwise, ℬ picks rGID←Rℤp∖−a+GID/b, computes K3,GID=g21/a+GID+brGID,K4,GID=HGID1/a+GID+brGID, and stores GID,rGID,K3,GID,K4,GID in table Q. Then, ℬ calls the ZCGM1 AA key generation oracle on S,GID to obtain the private key SKGID,ii∈S. For each i∈S, ℬ computes SKi,GID=SKGID,i1/a+GID+brGID. Finally, ℬ sets the corresponding decryption key as SKS,GID=GID,rGID,SKi,GIDi∈S and sends it to A.(iii)
Challenge. The adversaryA submits two messages M0,M1 and an access policy A,ρ, where A,ρ satisfies the following constraint. Let SV′ denote the attributes controlled by corrupt AAs, and SGID denotes the attributes in which the adversary has queried for identity GID. For each GID, we require that SV′∪SGID does not satisfy A,ρ. The challenger ℬ sends M0,M1, and A,ρ to C to obtain the ZCGM1 challenge ciphertext CT=C,C0,C1,x,C2,xx∈1,2,…,n. Then, ℬ computes C1=C0a=g1sab1⟶,C2=C0b=g1sbb1⟶ and sends CT∗=C,C0,C1,C2,C1,x,C2,xx∈1,2,…,n to A.(iv)
Phase 2. The adversary makes the key queries as Phase 1, but with the restriction ofA,ρ as described above. ℬ responds the queries in the same way as Phase 1.(v)
Guess. WhenA outputs a guess β′, then ℬ outputs β′.
Sinceℬ perfectly simulates the ZCGM1 security game for A, the advantage of ℬ breaks the ZCGM1 scheme equals to the advantage of A breaks our scheme.Theorem 1.
If the SXDH assumption holds, then our T-MA-CP-ABE scheme is adaptively secure.Proof.
This proof follows directly from Lemmas1 and 2.


## 4.2.2. Traceability

Now, we prove our T-MA-CP-ABE scheme is fully traceable by a reduction to BB scheme [32], which is strongly existentially unforgeable.Lemma 3 (See [32]).
If theq-SDH assumption holds, then the BB scheme is strongly existentially unforgeable under an adaptive chosen message attack.Lemma 4.
Assuming that the BB scheme [32] is strongly existentially unforgeable under an adaptive chosen message attack, then our T-MA-CP-ABE scheme is fully traceable in the random oracle model.Proof.
Letp,G1,G2,GT,g1,g2,e be a prime order bilinear group, and p,g1,g2,g1a,g1b be the public key of BB scheme. Let Sj be the attributes set managed by attribute authority AAj, and C be the challenger corresponding to ℬ in the BB security game.(i)
Setup. Whenℬ receives public key p,g1,g2,g1a,g1b from C, it first samples B=bij3×3←GL3ℤp, sets B∗=B−1⊤, b1⟶=b11,b21,b23⊤, and GP=p,G13,G23,GT,g1,g2,e,g1b1⟶. Then, ℬ computes cpk1=g1b1⟶a=g1ab1⟶, cpk2=g1b1⟶b=g1bb1⟶, and sets CPK=cpk1,cpk2. For each attribute i∈Sj, ℬ picks ki⟶←Rℤp3,Yi←Rℤp3×3, computes apki,1=g1Yi⊤b1⟶ and apki,2=eg1b1⟶,g2ki⟶, and sets APKj=apki,1,apki,2i∈Sj. Finally, ℬ sends global parameters GP, CA public key CPK, and AA public keys APKj to A. ℬ stores b1⟶,ki⟶,Yi and controls the random oracle H.(ii)
Key query. In this phase,A queries the CA keys corresponding to GIDii=1m and AA keys corresponding to Si,GIDii=1m. ℬ initializes two empty tables Q1andQ2 and answers A’s queries as follows:(1)
Random oracle hash query. WhenA submits an identity GID to ℬ to request the corresponding random oracle hash value HGID, ℬ first searches the entry GID,tGID⟶,g2tGID⟶ in Q1. If such entry exists, ℬ returns g2tGID⟶. Otherwise, ℬ picks tGID⟶←Rℤp3, sends g2tGID⟶ to A, and stores GID,tGID⟶,g2tGID⟶ in Q1.(2)
CA key query. WhenA submits an identity GIDi to ℬ to request the corresponding CA key SKGIDi, ℬ first searches the entry SKGIDi=GIDi,rGIDi,K3,GIDi,K4,GIDi in Q2. If such entry exists, ℬ returns SKGIDi to A. Otherwise, ℬ submits GIDi to C to request the corresponding signature. When ℬ receives signature rGIDi,σGIDi=g21/a+GIDi+brGIDi from C, ℬ searches the entry GIDi,tGIDi⟶,g2tGIDi⟶ in Q1. If no such entry exists, ℬ picks tGIDi⟶←Rℤp3 and stores GIDi,tGIDi⟶,g2tGIDi⟶ in Q1. Next, ℬ obtains tGIDi⟶ from table Q1 and sets SKGIDi=GIDi,rGIDi,K3,GIDi=σGIDi,K4,GIDi=σGIDitGIDi⟶ as the corresponding CA private key. Finally, ℬ sends SKGIDi to A and stores it in Q2.(3)
AA key query. WhenA submits a pair Si,GIDi to ℬ to request the corresponding decryption key SKSi,GIDi, ℬ first searches CA key SKGIDi=GIDi,rGIDi,K3,GIDi,K4,GIDi in Q2. If no such entry exists, ℬ generates CA key SKGIDi as in (2) and stores it in Q2. For each l∈Si, ℬ computes SKl,GIDi=K3,GIDikl⟶K4,GIDiYl⊤. Finally, ℬ sends the corresponding decryption key SKSi,GIDi=GIDi,rGIDi,SKl,GIDil∈Si to A.(iii)
Key forgery.A returns a decryption key SK∗ to ℬ.IfA wins this game, then TraceGP,CPK,{APKj},SK∗∉⊤,GID1,…,GIDm. Therefore, the decryption key SK∗=K1,GID,K2,GID,SKi,GIDi∈S passes the key sanity check, and K1,GID∉GID1,…,GIDm. Hence, K1,GID∈ℤp,K2,GID∈ℤp, ∃i∈S, s.t. SKi,GID∈G23, and(11)eg1b1⟶K1,GIDcpk1cpk2K2,GID,SKi,GID=eapki,1,HK1,GIDapki,2.
ℬ queries the random oracle hash HK1,GID as in (1) and gets the record K1,GID,tK1,GID⟶,g2tK1,GID⟶ from Q1. Then,(12)eg1K1,GID+a+bK2,GIDb1⟶,SKi,GID=eg1Yi⊤b1⟶,g2tK1,GID⟶eg1b1⟶,g2ki⟶=eg1b1⟶,g2ki⟶+tK1,GID⟶Yi⊤.
Hence, we haveSKi,GID=g2ki⟶+tK1,GID⟶Yi⊤/K1,GID+a+bK2,GID. As ℬ knows the pairs tK1,GID⟶,ki⟶,Yi⊤, it can compute ki⟶+tK1,GID⟶Yi⊤=a1,a2,a3∈ℤp3. Then, ℬ obtains SKi,GID,1=g2a1/K1,GID+a+bK2,GID from SKi,GID and sets σ=SKi,GID,11/a1=g21/K1,GID+a+bK2,GID.
Sinceeg1ag1K1,GIDg1bK2,GID,σ=z, ℬ can output a valid signature σ,K2,GID on message K1,GID in the BB security game. Note that K1,GID∉GID1,…,GIDm, so ℬ has never queried a signature on K1,GID, and then, ℬ wins the BB security game. Hence, if A breaks our T-MA-CP-ABE scheme in the traceability game with advantage ɛ, then ℬ breaks the BB scheme with advantage ɛ.Theorem 2.
If theq-SDH assumption holds, then our T-MA-CP-ABE scheme is fully traceable in the random oracle model.Proof.
This proof follows directly from Lemmas3 and 4.


## 5. Our TR-MA-CP-ABE System

Based on our T-MA-CP-ABE scheme, we design a TR-MA-CP-ABE system for secure and flexible data access control in cloud storage. In our system, each data owner can share his data with multiple data users whose attributes satisfy the specific access policy. The malicious users who leak their decryption keys on the Internet will be caught and revoked by CA. Furthermore, we give an efficiency comparison that shows our system accesses the data significantly faster than other related works.


### 5.1. Concrete System

Inspired by [9, 19], we extend our construction to realize malicious user revocation by adopting a hash function F:0,1∗⟶ℤp and a revocation identity list RL. In our TR-MA-CP-ABE system, CA adds the malicious user’s GID to the revocation identity list RL in the user tracing and revocation phase, and AAs help the nonrevoked users to update their decryption keys in the key update phase. More specifically, we first use the hash function F to map the time period T and user attribute i in ℤp, and then add T into the system by embedding the element FT‖i into the decryption key and ciphertext. The malicious users’ time elements will not be updated by AAs, so they cannot update their decryption keys and decrypt the new ciphertexts encrypted in new time period.Let TMABE = (TMABE : GlobalSetup; TMABE : CASetup; TMABE : AASetup; TMABE : CAKeyGen; TMABE : AAKeyGen; TMABE : Encrypt; TMABE : Decrypt; TMABE : Trace.) be the T-MA-CP-ABE scheme inSection 4.1. Below, we give the details of our TR-MA-CP-ABE system.


#### 5.1.1. System Initialization

In this phase, CA generates the system parameters, revocation list, and its public and secret keys. EachAAj creates a secret key for itself and a corresponding public key for public usage.CA first runs the algorithm TMABE : GlobalSetupλ to obtain p,G13,G23,GT,g1,g2,e,g1b1⟶,H and chooses a hash function F:0,1∗⟶ℤp. Then, CA runs the algorithm TMABE : CASetup (GP) to obtain its own public key CPK=cpk1,cpk2 and secret key CSK=a,b. Next, CA publishes the system parameters GP=p,G13,G23,GT,g1,g2,e,g1b1⟶,H,F and its public key CPK. Finally, CA initializes an empty revocation identity list RL.AAj first runs the algorithm TMABE : AASetup GP,Sj to generate its own public key APKj and secret key ASKj. Then, AAj keeps ASKj secret and publishes APKj to others.


#### 5.1.2. User Registration

When a data user wants to join the system, he should register himself to the CA and relevant AAs. In this phase, CA issues the identity keys, and AAs issue the attribute keys to the registered users. From the identity and attribute keys, the registered users can crate their decrypt keys, which can be used for decrypting the policy-matching ciphertext.First, the data user with identityGID makes a registration request to CA. CA runs the algorithm TMABE : CAKeyGen (GID,CSK,GP) to obtain CSKGID=K1,GID,K2,GID,K3,GID,K4,GID, sets CSKGID as the user identity key, and sends it to the data user.Next, the data user submits his identityGID and attributes set S and K3,GID,K4,GID to the relevant authorities AAj. For each attribute i∈S∩Sj, AAj sets the corresponding user attribute key SKi,GID=K3,GIDFT‖iki⟶K4,GIDYi⊤ and sends it to the data user, where T is a time period.Finally, the user setsSKS,GID=K1,GID,K2,GID,SKi,GIDi∈S as his decryption key.


#### 5.1.3. Data Outsource

In this phase, each data owner encrypts his data with a specific access policy and then outsources the ciphertext data in the cloud. When a data owner wants to share dataF with the specific data users, he should generate a ciphertext data that is composed of the body and header as follows.First, the data owner picks a symmetric session keyK∈GT, uses it to encrypt the data F under a symmetric encryption algorithm (such as AES), and sets the resulting ciphertext CTF as the ciphertext body.Then, the data owner encrypts the session keyK∈GT under an access policy A,ρ and a time period T′ as follows. He picks U2,U3,…,Un←Rℤp3×3,0⟶←ℤp3,v⟶=s0,v2,v3,…,vn←Rℤpn,s←ℤp. For each x∈1,2,…,l, he sets λx=Ax⟶,v⟶, and computes(13)C=Keg1,g2s0,C0=g1sb1⟶,C1=g1sab1⟶,C2=g1sbb1⟶,C1,x=eg1,g2λxeg1,g2sFT′ρxkρx⟶b1⟶,C2,x=g10⟶⊤,sU2⊤b1⟶,…,sUl⊤b1⟶Ax⟶⊤g1sYρx⊤b1⟶.Finally, the data owner sets ciphertext headCTK=A,ρ,T′,C,C0,C1,C2,C1,x,C2,x1,2,⋯l and outsources the ciphertext data CTK,CTF to the cloud server.


#### 5.1.4. Data Access

In our system, each data user can download any ciphertext data from the cloud server, but can only access the limited plain data by decryption of the corresponding ciphertext data successfully. In this phase, the data user has a decryption keySKS,GID for an attributes set S for a time period T and tries to access the data in the cloud.The data user first queries an interested ciphertext data and gets the ciphertextCTK,CTF from the cloud server. Then, the data user checks whether he has the access permission or not. If S does not satisfy A,ρ or T≠T′, then he outputs ⊥ meaning that he cannot access this data. Otherwise, the data user runs the algorithm TMABE : Decrypt GP,SKS,GID,CTK and gets the session key K. Finally, the data user decrypts the ciphertext body CTF by the key K and recovers the plain data F.


#### 5.1.5. Key Update

In this phase, AAs help the nonrevoked data users update their decryption keys in a new time periodT″. When the data user wants to update his decryption key, he submits his identity GID and attributes set S and K3,GID,K4,GID to the relevant authorities AAj. AAj first checks whether the data user has been revoked or not. If GID∈RL, AAj outputs ⊥ meaning that the revoked data user cannot update his decryption key. Otherwise, for each attribute i∈S∩Sj, AAj computes the user attribute key SKi,GID=K3,GIDFT″‖iki⟶K4,GIDYi⊤. After that, AAj sends the update attribute key SKi,GIDi∈S∩Sj to the data user. Finally, the data user sets the decryption key as SKS,GID=K1,GID,K2,GID,SKi,GIDi∈S, which can be used for decrypt the ciphertext data in the new time period T″.


#### 5.1.6. User Tracing and Revocation

In this phase, CA traces the malicious users who leak their decryption key to others and revokes their access permissions in the system. When CA finds a decryption keySKS,GID is sold on the Internet, it first runs the algorithm TMABE : Trace GP,CPK,APKj,SKS,GID. If the algorithm outputs ⊤, CA outputs ⊤ meaning that SKS,GID does not need to be traced. If the algorithm outputs an identity GID, then CA sets GID as the identity of the malicious user who leaks his decryption key SKS,GID. Finally, CA adds GID into the revocation list RL and updates RL for public usage.Alike with [9, 19], we view hash function F as a random oracle, and our TR-MA-CP-ABE scheme has the same security conclusion with our T-MA-CP-ABE scheme. The correctness and security proofs are almost the same with that in Section 4.


### 5.2. Efficiency Comparison

In this section, we give an efficiency comparison between our TR-MA-CP-ABE system with other T-MA-CP-ABE schemes, all of which support multiauthority and traceability. In Table2, PK represents the public key (including the CA and AA public keys) size, DK represents the decryption key size, CT represents the ciphertext size, PID represents the number of pairing operations in decryption, and GO represents the group order. Let U be the number of attributes in the system, V the number of AAs in the system, D the number of CAs in the system, ρ the bit length of the user identity, S the number of attributes in the decryption key, l the number of rows of the matrix in the access policy, and I (I≤S,l ) the number of attributes used for decryption.Table 2
Efficiency comparison with other related works.
PKDKCTPIDGO[13]3U+V+3ρ3S+3ρ+12U+4ρ+23S+3ρPrime[14]U+DV+3S+DV+52l+D+24I+D+2Composite[15]2V2S+14l+13IComposite[16]4V4S+16l+13IPrimeThis paper4U+63S+24l+106PrimeAs shown in Table2, the number of resource-consuming pairing operations required to decrypt a ciphertext in [13–16] increases with the number of attributes used for decryption. While our TR-MA-CP-ABE system only needs to compute 6 pairings for decryption. Since an element in prime order groups is 12 times shorter than that in composite order groups [33], the storage overhead of our system is significantly smaller than that of the schemes [14, 15] which are constructed in composite order groups. Compared with our TR-MA-CP-ABE system, the schemes [13, 16] in prime order groups achieve smaller public key size, but they neither achieve adaptively secure nor support user revocation.We evaluate our pairing operations in Python language using the PBC library [34] with type A curve. The experiment is performed on a Macbook laptop with a 2.8 GHz Intel Core i7 processor and 16 GB memory. Figure 2 illustrates the pairing costs for decryption in our TR-MA-CP-ABE system and other two T-MA-CP-ABE schemes [13, 16] in prime order groups. We set S=I and ρ=10 and increase the value of I from 1 to 50. It is easy to see that pairing costs for decryption in our system is a constant time and significantly shorter than that grows linearly with the number of attributes in [13, 16]. Note that a pairing operation in prime order groups is about 100 times faster than that in composite (3 primes) order groups [35], which makes the data access speed in our system is significantly faster than that in schemes [14, 15] constructed in composite order groups.Figure 2
Pairing costs for decryption.


## 5.1. Concrete System

Inspired by [9, 19], we extend our construction to realize malicious user revocation by adopting a hash function F:0,1∗⟶ℤp and a revocation identity list RL. In our TR-MA-CP-ABE system, CA adds the malicious user’s GID to the revocation identity list RL in the user tracing and revocation phase, and AAs help the nonrevoked users to update their decryption keys in the key update phase. More specifically, we first use the hash function F to map the time period T and user attribute i in ℤp, and then add T into the system by embedding the element FT‖i into the decryption key and ciphertext. The malicious users’ time elements will not be updated by AAs, so they cannot update their decryption keys and decrypt the new ciphertexts encrypted in new time period.Let TMABE = (TMABE : GlobalSetup; TMABE : CASetup; TMABE : AASetup; TMABE : CAKeyGen; TMABE : AAKeyGen; TMABE : Encrypt; TMABE : Decrypt; TMABE : Trace.) be the T-MA-CP-ABE scheme inSection 4.1. Below, we give the details of our TR-MA-CP-ABE system.


### 5.1.1. System Initialization

In this phase, CA generates the system parameters, revocation list, and its public and secret keys. EachAAj creates a secret key for itself and a corresponding public key for public usage.CA first runs the algorithm TMABE : GlobalSetupλ to obtain p,G13,G23,GT,g1,g2,e,g1b1⟶,H and chooses a hash function F:0,1∗⟶ℤp. Then, CA runs the algorithm TMABE : CASetup (GP) to obtain its own public key CPK=cpk1,cpk2 and secret key CSK=a,b. Next, CA publishes the system parameters GP=p,G13,G23,GT,g1,g2,e,g1b1⟶,H,F and its public key CPK. Finally, CA initializes an empty revocation identity list RL.AAj first runs the algorithm TMABE : AASetup GP,Sj to generate its own public key APKj and secret key ASKj. Then, AAj keeps ASKj secret and publishes APKj to others.


### 5.1.2. User Registration

When a data user wants to join the system, he should register himself to the CA and relevant AAs. In this phase, CA issues the identity keys, and AAs issue the attribute keys to the registered users. From the identity and attribute keys, the registered users can crate their decrypt keys, which can be used for decrypting the policy-matching ciphertext.First, the data user with identityGID makes a registration request to CA. CA runs the algorithm TMABE : CAKeyGen (GID,CSK,GP) to obtain CSKGID=K1,GID,K2,GID,K3,GID,K4,GID, sets CSKGID as the user identity key, and sends it to the data user.Next, the data user submits his identityGID and attributes set S and K3,GID,K4,GID to the relevant authorities AAj. For each attribute i∈S∩Sj, AAj sets the corresponding user attribute key SKi,GID=K3,GIDFT‖iki⟶K4,GIDYi⊤ and sends it to the data user, where T is a time period.Finally, the user setsSKS,GID=K1,GID,K2,GID,SKi,GIDi∈S as his decryption key.


### 5.1.3. Data Outsource

In this phase, each data owner encrypts his data with a specific access policy and then outsources the ciphertext data in the cloud. When a data owner wants to share dataF with the specific data users, he should generate a ciphertext data that is composed of the body and header as follows.First, the data owner picks a symmetric session keyK∈GT, uses it to encrypt the data F under a symmetric encryption algorithm (such as AES), and sets the resulting ciphertext CTF as the ciphertext body.Then, the data owner encrypts the session keyK∈GT under an access policy A,ρ and a time period T′ as follows. He picks U2,U3,…,Un←Rℤp3×3,0⟶←ℤp3,v⟶=s0,v2,v3,…,vn←Rℤpn,s←ℤp. For each x∈1,2,…,l, he sets λx=Ax⟶,v⟶, and computes(13)C=Keg1,g2s0,C0=g1sb1⟶,C1=g1sab1⟶,C2=g1sbb1⟶,C1,x=eg1,g2λxeg1,g2sFT′ρxkρx⟶b1⟶,C2,x=g10⟶⊤,sU2⊤b1⟶,…,sUl⊤b1⟶Ax⟶⊤g1sYρx⊤b1⟶.Finally, the data owner sets ciphertext headCTK=A,ρ,T′,C,C0,C1,C2,C1,x,C2,x1,2,⋯l and outsources the ciphertext data CTK,CTF to the cloud server.


### 5.1.4. Data Access

In our system, each data user can download any ciphertext data from the cloud server, but can only access the limited plain data by decryption of the corresponding ciphertext data successfully. In this phase, the data user has a decryption keySKS,GID for an attributes set S for a time period T and tries to access the data in the cloud.The data user first queries an interested ciphertext data and gets the ciphertextCTK,CTF from the cloud server. Then, the data user checks whether he has the access permission or not. If S does not satisfy A,ρ or T≠T′, then he outputs ⊥ meaning that he cannot access this data. Otherwise, the data user runs the algorithm TMABE : Decrypt GP,SKS,GID,CTK and gets the session key K. Finally, the data user decrypts the ciphertext body CTF by the key K and recovers the plain data F.


### 5.1.5. Key Update

In this phase, AAs help the nonrevoked data users update their decryption keys in a new time periodT″. When the data user wants to update his decryption key, he submits his identity GID and attributes set S and K3,GID,K4,GID to the relevant authorities AAj. AAj first checks whether the data user has been revoked or not. If GID∈RL, AAj outputs ⊥ meaning that the revoked data user cannot update his decryption key. Otherwise, for each attribute i∈S∩Sj, AAj computes the user attribute key SKi,GID=K3,GIDFT″‖iki⟶K4,GIDYi⊤. After that, AAj sends the update attribute key SKi,GIDi∈S∩Sj to the data user. Finally, the data user sets the decryption key as SKS,GID=K1,GID,K2,GID,SKi,GIDi∈S, which can be used for decrypt the ciphertext data in the new time period T″.


### 5.1.6. User Tracing and Revocation

In this phase, CA traces the malicious users who leak their decryption key to others and revokes their access permissions in the system. When CA finds a decryption keySKS,GID is sold on the Internet, it first runs the algorithm TMABE : Trace GP,CPK,APKj,SKS,GID. If the algorithm outputs ⊤, CA outputs ⊤ meaning that SKS,GID does not need to be traced. If the algorithm outputs an identity GID, then CA sets GID as the identity of the malicious user who leaks his decryption key SKS,GID. Finally, CA adds GID into the revocation list RL and updates RL for public usage.Alike with [9, 19], we view hash function F as a random oracle, and our TR-MA-CP-ABE scheme has the same security conclusion with our T-MA-CP-ABE scheme. The correctness and security proofs are almost the same with that in Section 4.


## 5.1.1. System Initialization

In this phase, CA generates the system parameters, revocation list, and its public and secret keys. EachAAj creates a secret key for itself and a corresponding public key for public usage.CA first runs the algorithm TMABE : GlobalSetupλ to obtain p,G13,G23,GT,g1,g2,e,g1b1⟶,H and chooses a hash function F:0,1∗⟶ℤp. Then, CA runs the algorithm TMABE : CASetup (GP) to obtain its own public key CPK=cpk1,cpk2 and secret key CSK=a,b. Next, CA publishes the system parameters GP=p,G13,G23,GT,g1,g2,e,g1b1⟶,H,F and its public key CPK. Finally, CA initializes an empty revocation identity list RL.AAj first runs the algorithm TMABE : AASetup GP,Sj to generate its own public key APKj and secret key ASKj. Then, AAj keeps ASKj secret and publishes APKj to others.


## 5.1.2. User Registration

When a data user wants to join the system, he should register himself to the CA and relevant AAs. In this phase, CA issues the identity keys, and AAs issue the attribute keys to the registered users. From the identity and attribute keys, the registered users can crate their decrypt keys, which can be used for decrypting the policy-matching ciphertext.First, the data user with identityGID makes a registration request to CA. CA runs the algorithm TMABE : CAKeyGen (GID,CSK,GP) to obtain CSKGID=K1,GID,K2,GID,K3,GID,K4,GID, sets CSKGID as the user identity key, and sends it to the data user.Next, the data user submits his identityGID and attributes set S and K3,GID,K4,GID to the relevant authorities AAj. For each attribute i∈S∩Sj, AAj sets the corresponding user attribute key SKi,GID=K3,GIDFT‖iki⟶K4,GIDYi⊤ and sends it to the data user, where T is a time period.Finally, the user setsSKS,GID=K1,GID,K2,GID,SKi,GIDi∈S as his decryption key.


## 5.1.3. Data Outsource

In this phase, each data owner encrypts his data with a specific access policy and then outsources the ciphertext data in the cloud. When a data owner wants to share dataF with the specific data users, he should generate a ciphertext data that is composed of the body and header as follows.First, the data owner picks a symmetric session keyK∈GT, uses it to encrypt the data F under a symmetric encryption algorithm (such as AES), and sets the resulting ciphertext CTF as the ciphertext body.Then, the data owner encrypts the session keyK∈GT under an access policy A,ρ and a time period T′ as follows. He picks U2,U3,…,Un←Rℤp3×3,0⟶←ℤp3,v⟶=s0,v2,v3,…,vn←Rℤpn,s←ℤp. For each x∈1,2,…,l, he sets λx=Ax⟶,v⟶, and computes(13)C=Keg1,g2s0,C0=g1sb1⟶,C1=g1sab1⟶,C2=g1sbb1⟶,C1,x=eg1,g2λxeg1,g2sFT′ρxkρx⟶b1⟶,C2,x=g10⟶⊤,sU2⊤b1⟶,…,sUl⊤b1⟶Ax⟶⊤g1sYρx⊤b1⟶.Finally, the data owner sets ciphertext headCTK=A,ρ,T′,C,C0,C1,C2,C1,x,C2,x1,2,⋯l and outsources the ciphertext data CTK,CTF to the cloud server.


## 5.1.4. Data Access

In our system, each data user can download any ciphertext data from the cloud server, but can only access the limited plain data by decryption of the corresponding ciphertext data successfully. In this phase, the data user has a decryption keySKS,GID for an attributes set S for a time period T and tries to access the data in the cloud.The data user first queries an interested ciphertext data and gets the ciphertextCTK,CTF from the cloud server. Then, the data user checks whether he has the access permission or not. If S does not satisfy A,ρ or T≠T′, then he outputs ⊥ meaning that he cannot access this data. Otherwise, the data user runs the algorithm TMABE : Decrypt GP,SKS,GID,CTK and gets the session key K. Finally, the data user decrypts the ciphertext body CTF by the key K and recovers the plain data F.


## 5.1.5. Key Update

In this phase, AAs help the nonrevoked data users update their decryption keys in a new time periodT″. When the data user wants to update his decryption key, he submits his identity GID and attributes set S and K3,GID,K4,GID to the relevant authorities AAj. AAj first checks whether the data user has been revoked or not. If GID∈RL, AAj outputs ⊥ meaning that the revoked data user cannot update his decryption key. Otherwise, for each attribute i∈S∩Sj, AAj computes the user attribute key SKi,GID=K3,GIDFT″‖iki⟶K4,GIDYi⊤. After that, AAj sends the update attribute key SKi,GIDi∈S∩Sj to the data user. Finally, the data user sets the decryption key as SKS,GID=K1,GID,K2,GID,SKi,GIDi∈S, which can be used for decrypt the ciphertext data in the new time period T″.


## 5.1.6. User Tracing and Revocation

In this phase, CA traces the malicious users who leak their decryption key to others and revokes their access permissions in the system. When CA finds a decryption keySKS,GID is sold on the Internet, it first runs the algorithm TMABE : Trace GP,CPK,APKj,SKS,GID. If the algorithm outputs ⊤, CA outputs ⊤ meaning that SKS,GID does not need to be traced. If the algorithm outputs an identity GID, then CA sets GID as the identity of the malicious user who leaks his decryption key SKS,GID. Finally, CA adds GID into the revocation list RL and updates RL for public usage.Alike with [9, 19], we view hash function F as a random oracle, and our TR-MA-CP-ABE scheme has the same security conclusion with our T-MA-CP-ABE scheme. The correctness and security proofs are almost the same with that in Section 4.


## 5.2. Efficiency Comparison

In this section, we give an efficiency comparison between our TR-MA-CP-ABE system with other T-MA-CP-ABE schemes, all of which support multiauthority and traceability. In Table2, PK represents the public key (including the CA and AA public keys) size, DK represents the decryption key size, CT represents the ciphertext size, PID represents the number of pairing operations in decryption, and GO represents the group order. Let U be the number of attributes in the system, V the number of AAs in the system, D the number of CAs in the system, ρ the bit length of the user identity, S the number of attributes in the decryption key, l the number of rows of the matrix in the access policy, and I (I≤S,l ) the number of attributes used for decryption.Table 2
Efficiency comparison with other related works.
PKDKCTPIDGO[13]3U+V+3ρ3S+3ρ+12U+4ρ+23S+3ρPrime[14]U+DV+3S+DV+52l+D+24I+D+2Composite[15]2V2S+14l+13IComposite[16]4V4S+16l+13IPrimeThis paper4U+63S+24l+106PrimeAs shown in Table2, the number of resource-consuming pairing operations required to decrypt a ciphertext in [13–16] increases with the number of attributes used for decryption. While our TR-MA-CP-ABE system only needs to compute 6 pairings for decryption. Since an element in prime order groups is 12 times shorter than that in composite order groups [33], the storage overhead of our system is significantly smaller than that of the schemes [14, 15] which are constructed in composite order groups. Compared with our TR-MA-CP-ABE system, the schemes [13, 16] in prime order groups achieve smaller public key size, but they neither achieve adaptively secure nor support user revocation.We evaluate our pairing operations in Python language using the PBC library [34] with type A curve. The experiment is performed on a Macbook laptop with a 2.8 GHz Intel Core i7 processor and 16 GB memory. Figure 2 illustrates the pairing costs for decryption in our TR-MA-CP-ABE system and other two T-MA-CP-ABE schemes [13, 16] in prime order groups. We set S=I and ρ=10 and increase the value of I from 1 to 50. It is easy to see that pairing costs for decryption in our system is a constant time and significantly shorter than that grows linearly with the number of attributes in [13, 16]. Note that a pairing operation in prime order groups is about 100 times faster than that in composite (3 primes) order groups [35], which makes the data access speed in our system is significantly faster than that in schemes [14, 15] constructed in composite order groups.Figure 2
Pairing costs for decryption.


## 6. Conclusion and Future Work

In this work, we presented a traceable and revocable MA-CP-ABE system in the prime order groups. Specifically, the proposed system has the following advantages: (1) the ciphertext cannot be decrypted by any individual authority, and the ciphertext policy can be any monotone access structures; (2) CA can not only catch the malicious user by his decryption key but also revoke the corresponding decryption privilege; and (3) the system achieves adaptively secure and fast access.As far as we know, our TR-MA-CP-ABE system is the first MA-CP-ABE system that supports traceability, revocation, and fast access simultaneously. However, our system only supports white-box traceability: the decryption key leaked by the malicious user is assumed to pass the key sanity check. Hence, our system is not suitable for black-box traceability scenario: the malicious user can construct a decryption black-box by his decryption key and unknown decryption algorithm and leak a decryption black-box instead of his decryption key. We leave it as our future work to obtain a black-box traceable and revocable MA-CP-ABE system with fast access.



---

*Source: 6661243-2020-12-22.xml*